| Message ID | 20230905015255.81545-1-wuqiang.matt@bytedance.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | lib,kprobes: kretprobe scalability improvement | expand |
Hi Wuqiang, I dug my mail box and found this. Sorry for replying late. On Tue, 5 Sep 2023 09:52:50 +0800 "wuqiang.matt" <wuqiang.matt@bytedance.com> wrote: > This patch series introduces a scalable and lockless ring-array based > object pool and replaces the original freelist (a LIFO queue based on > singly linked list) to improve scalability of kretprobed routines. > > v9: > 1) objpool: raw_local_irq_save/restore added to prevent interruption > > To avoid possible ABA issues, we must ensure objpool_try_add_slot > and objpool_try_add_slot are uninterruptible. If these operations > are blocked or interrupted in the middle, other cores could overrun > the same slot's ages[] of uint32, then after resuming back, the > interrupted pop() or push() could see same value of ages[], which > is a typical ABA problem though the possibility is small. > > The pair of pop()/push() costs about 8.53 cpu cycles, measured > by IACA (Intel Architecture Code Analyzer). That is, on a 4Ghz > core dedicated for pop() & push(), theoretically it would only > need 8.53 seconds to overflow a 32bit value. Testings upon Intel > i7-10700 (2.90GHz) cost 71.88 seconds to overrun a 32bit integer. What does this mean? This sounds like "There is a timing issue if it's enough fast". Let me reivew the patch itself. Thanks, > > 2) codes improvements: thanks to Masami for the thorough inspection > > v8: > 1) objpool: refcount added for objpool lifecycle management > > wuqiang.matt (5): > lib: objpool added: ring-array based lockless MPMC > lib: objpool test module added > kprobes: kretprobe scalability improvement with objpool > kprobes: freelist.h removed > MAINTAINERS: objpool added > > MAINTAINERS | 7 + > include/linux/freelist.h | 129 -------- > include/linux/kprobes.h | 11 +- > include/linux/objpool.h | 174 ++++++++++ > include/linux/rethook.h | 16 +- > kernel/kprobes.c | 93 +++--- > kernel/trace/fprobe.c | 32 +- > kernel/trace/rethook.c | 90 +++-- > lib/Kconfig.debug | 11 + > lib/Makefile | 4 +- > lib/objpool.c | 338 +++++++++++++++++++ > lib/test_objpool.c | 689 +++++++++++++++++++++++++++++++++++++++ > 12 files changed, 1320 insertions(+), 274 deletions(-) > delete mode 100644 include/linux/freelist.h > create mode 100644 include/linux/objpool.h > create mode 100644 lib/objpool.c > create mode 100644 lib/test_objpool.c > > -- > 2.40.1 >
On 2023/9/23 16:57, Masami Hiramatsu (Google) wrote: > Hi Wuqiang, > > I dug my mail box and found this. Sorry for replying late. > > On Tue, 5 Sep 2023 09:52:50 +0800 > "wuqiang.matt" <wuqiang.matt@bytedance.com> wrote: > >> This patch series introduces a scalable and lockless ring-array based >> object pool and replaces the original freelist (a LIFO queue based on >> singly linked list) to improve scalability of kretprobed routines. >> >> v9: >> 1) objpool: raw_local_irq_save/restore added to prevent interruption >> >> To avoid possible ABA issues, we must ensure objpool_try_add_slot >> and objpool_try_add_slot are uninterruptible. If these operations >> are blocked or interrupted in the middle, other cores could overrun >> the same slot's ages[] of uint32, then after resuming back, the >> interrupted pop() or push() could see same value of ages[], which >> is a typical ABA problem though the possibility is small. >> >> The pair of pop()/push() costs about 8.53 cpu cycles, measured >> by IACA (Intel Architecture Code Analyzer). That is, on a 4Ghz >> core dedicated for pop() & push(), theoretically it would only >> need 8.53 seconds to overflow a 32bit value. Testings upon Intel >> i7-10700 (2.90GHz) cost 71.88 seconds to overrun a 32bit integer. > > What does this mean? This sounds like "There is a timing issue if it's enough fast". Yes, that's why local irq must be disabled. If push()/pop() is interrupted or preempted long enough (> 10 seconds for the extreme cases), other nodes could overrun the same ages[] of 32-bit, then after resuming to execution the push() or pop() would see the same value without notifying the overrun, which is a typical ABA. Changing ages[] to 64-bit could be a solution, but it's inappropriate for 32-bit OS and looks too heavy. With local irg disabled, push() or pop() is uninterrupted，thus the ABA is avoided. push() or pop() consumes only ~4 cycles to complete (most of the use cases), so raw_local_irq_save/restore are used instead of local_irq_save/restore to minimize the overhead. > Let me reivew the patch itself. > > Thanks, > >> >> 2) codes improvements: thanks to Masami for the thorough inspection >> >> v8: >> 1) objpool: refcount added for objpool lifecycle management >> >> wuqiang.matt (5): >> lib: objpool added: ring-array based lockless MPMC >> lib: objpool test module added >> kprobes: kretprobe scalability improvement with objpool >> kprobes: freelist.h removed >> MAINTAINERS: objpool added >> >> MAINTAINERS | 7 + >> include/linux/freelist.h | 129 -------- >> include/linux/kprobes.h | 11 +- >> include/linux/objpool.h | 174 ++++++++++ >> include/linux/rethook.h | 16 +- >> kernel/kprobes.c | 93 +++--- >> kernel/trace/fprobe.c | 32 +- >> kernel/trace/rethook.c | 90 +++-- >> lib/Kconfig.debug | 11 + >> lib/Makefile | 4 +- >> lib/objpool.c | 338 +++++++++++++++++++ >> lib/test_objpool.c | 689 +++++++++++++++++++++++++++++++++++++++ >> 12 files changed, 1320 insertions(+), 274 deletions(-) >> delete mode 100644 include/linux/freelist.h >> create mode 100644 include/linux/objpool.h >> create mode 100644 lib/objpool.c >> create mode 100644 lib/test_objpool.c >> >> -- >> 2.40.1 >> > >
On Mon, 9 Oct 2023 02:33:09 +0800 wuqiang <wuqiang.matt@bytedance.com> wrote: > On 2023/9/23 16:57, Masami Hiramatsu (Google) wrote: > > Hi Wuqiang, > > > > I dug my mail box and found this. Sorry for replying late. > > > > On Tue, 5 Sep 2023 09:52:50 +0800 > > "wuqiang.matt" <wuqiang.matt@bytedance.com> wrote: > > > >> This patch series introduces a scalable and lockless ring-array based > >> object pool and replaces the original freelist (a LIFO queue based on > >> singly linked list) to improve scalability of kretprobed routines. > >> > >> v9: > >> 1) objpool: raw_local_irq_save/restore added to prevent interruption > >> > >> To avoid possible ABA issues, we must ensure objpool_try_add_slot > >> and objpool_try_add_slot are uninterruptible. If these operations > >> are blocked or interrupted in the middle, other cores could overrun > >> the same slot's ages[] of uint32, then after resuming back, the > >> interrupted pop() or push() could see same value of ages[], which > >> is a typical ABA problem though the possibility is small. > >> > >> The pair of pop()/push() costs about 8.53 cpu cycles, measured > >> by IACA (Intel Architecture Code Analyzer). That is, on a 4Ghz > >> core dedicated for pop() & push(), theoretically it would only > >> need 8.53 seconds to overflow a 32bit value. Testings upon Intel > >> i7-10700 (2.90GHz) cost 71.88 seconds to overrun a 32bit integer. > > > > What does this mean? This sounds like "There is a timing issue if it's enough fast". > > Yes, that's why local irq must be disabled. If push()/pop() is interrupted or > preempted long enough (> 10 seconds for the extreme cases), other nodes could > overrun the same ages[] of 32-bit, then after resuming to execution the push() > or pop() would see the same value without notifying the overrun, which is a > typical ABA. Yeah, indeed. > > Changing ages[] to 64-bit could be a solution, but it's inappropriate for > 32-bit OS and looks too heavy. With local irg disabled, push() or pop() is > uninterrupted，thus the ABA is avoided. As I found, ages[] can be removed. In that case, you can only update the head and tail to 64 bit (but in that case cmpxchg will be more complicated) Thank you, > > push() or pop() consumes only ~4 cycles to complete (most of the use cases), > so raw_local_irq_save/restore are used instead of local_irq_save/restore to > minimize the overhead. > > > Let me reivew the patch itself. > > > > Thanks, > > > >> > >> 2) codes improvements: thanks to Masami for the thorough inspection > >> > >> v8: > >> 1) objpool: refcount added for objpool lifecycle management > >> > >> wuqiang.matt (5): > >> lib: objpool added: ring-array based lockless MPMC > >> lib: objpool test module added > >> kprobes: kretprobe scalability improvement with objpool > >> kprobes: freelist.h removed > >> MAINTAINERS: objpool added > >> > >> MAINTAINERS | 7 + > >> include/linux/freelist.h | 129 -------- > >> include/linux/kprobes.h | 11 +- > >> include/linux/objpool.h | 174 ++++++++++ > >> include/linux/rethook.h | 16 +- > >> kernel/kprobes.c | 93 +++--- > >> kernel/trace/fprobe.c | 32 +- > >> kernel/trace/rethook.c | 90 +++-- > >> lib/Kconfig.debug | 11 + > >> lib/Makefile | 4 +- > >> lib/objpool.c | 338 +++++++++++++++++++ > >> lib/test_objpool.c | 689 +++++++++++++++++++++++++++++++++++++++ > >> 12 files changed, 1320 insertions(+), 274 deletions(-) > >> delete mode 100644 include/linux/freelist.h > >> create mode 100644 include/linux/objpool.h > >> create mode 100644 lib/objpool.c > >> create mode 100644 lib/test_objpool.c > >> > >> -- > >> 2.40.1 > >> > > > > > >
This patch series introduces a scalable and lockless ring-array based object pool and replaces the original freelist (a LIFO queue based on singly linked list) to improve scalability of kretprobed routines. v9: 1) objpool: raw_local_irq_save/restore added to prevent interruption To avoid possible ABA issues, we must ensure objpool_try_add_slot and objpool_try_add_slot are uninterruptible. If these operations are blocked or interrupted in the middle, other cores could overrun the same slot's ages[] of uint32, then after resuming back, the interrupted pop() or push() could see same value of ages[], which is a typical ABA problem though the possibility is small. The pair of pop()/push() costs about 8.53 cpu cycles, measured by IACA (Intel Architecture Code Analyzer). That is, on a 4Ghz core dedicated for pop() & push(), theoretically it would only need 8.53 seconds to overflow a 32bit value. Testings upon Intel i7-10700 (2.90GHz) cost 71.88 seconds to overrun a 32bit integer. 2) codes improvements: thanks to Masami for the thorough inspection v8: 1) objpool: refcount added for objpool lifecycle management wuqiang.matt (5): lib: objpool added: ring-array based lockless MPMC lib: objpool test module added kprobes: kretprobe scalability improvement with objpool kprobes: freelist.h removed MAINTAINERS: objpool added MAINTAINERS | 7 + include/linux/freelist.h | 129 -------- include/linux/kprobes.h | 11 +- include/linux/objpool.h | 174 ++++++++++ include/linux/rethook.h | 16 +- kernel/kprobes.c | 93 +++--- kernel/trace/fprobe.c | 32 +- kernel/trace/rethook.c | 90 +++-- lib/Kconfig.debug | 11 + lib/Makefile | 4 +- lib/objpool.c | 338 +++++++++++++++++++ lib/test_objpool.c | 689 +++++++++++++++++++++++++++++++++++++++ 12 files changed, 1320 insertions(+), 274 deletions(-) delete mode 100644 include/linux/freelist.h create mode 100644 include/linux/objpool.h create mode 100644 lib/objpool.c create mode 100644 lib/test_objpool.c