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.m...@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
