Re: [PATCH v9 0/5] lib,kprobes: kretprobe scalability improvement

On Mon, 9 Oct 2023 02:33:09 +0800
wuqiang [off-list ref] wrote:

On 2023/9/23 16:57, Masami Hiramatsu (Google) wrote:

quoted

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" [off-list ref] wrote:

quoted

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.

quoted

Let me reivew the patch itself.

Thanks,

quoted

   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) [off-list ref]