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" <[email protected]> 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
>
--
Masami Hiramatsu (Google) <[email protected]>
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" <[email protected]> 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 <[email protected]> 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" <[email protected]> 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
> >>
> >
> >
>
>
--
Masami Hiramatsu (Google) <[email protected]>