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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <30892865-c92e-433e-2dba-ec6004c3d0e2@bytedance.com>
Date:   Mon, 9 Oct 2023 02:33:09 +0800
From:   wuqiang <wuqiang.matt@...edance.com>
To:     "Masami Hiramatsu (Google)" <mhiramat@...nel.org>
Cc:     linux-trace-kernel@...r.kernel.org, davem@...emloft.net,
        anil.s.keshavamurthy@...el.com, naveen.n.rao@...ux.ibm.com,
        rostedt@...dmis.org, peterz@...radead.org,
        akpm@...ux-foundation.org, sander@...nheule.net,
        ebiggers@...gle.com, dan.j.williams@...el.com, jpoimboe@...nel.org,
        linux-kernel@...r.kernel.org, lkp@...el.com, mattwu@....com
Subject: Re: [PATCH v9 0/5] lib,kprobes: kretprobe scalability improvement

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