From patchwork Sun Dec 18 05:03:06 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "wuqiang.matt" X-Patchwork-Id: 34286 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp1789609wrn; Sat, 17 Dec 2022 21:05:18 -0800 (PST) X-Google-Smtp-Source: AA0mqf7phQd+QZQrUIg4xn3pld+tVgaasaAuMvxZwG42bL5TjyLGvUktOutavZFLKOSEXOHZsW1K X-Received: by 2002:a17:906:cecd:b0:7c1:9046:878a with SMTP id si13-20020a170906cecd00b007c19046878amr17188414ejb.38.1671339918506; Sat, 17 Dec 2022 21:05:18 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1671339918; cv=none; d=google.com; s=arc-20160816; b=WQd44vxwHR7S4+HQ08AQHoq10ff4n8krAcYc9NC2Ppz9wnalHICwm4zw8VBq5gYujS 7BKrU4CbnTA1BcHxRY4AAJwdh78RVaRlu9wRJ2CVLw8s1NcVpaYnookved5JuYO8xhzt KVrwEYM5aBqvpbivhtGpVjXmMuw6nNH5dZ64HSZtT01vhz3OgmkRZndBmwqoUm4mdpzH 1/o7kn85iphQBQNGsjwnMHtrxJcM2f3c1c9UMGasXVBHk+sj+BEFVzYIm5T1UFu3G3bx 4b/O05KSsht4BQSd34JQVgtyoSDwBVjdPGuhYOf+MIC6fmezf++bArMoVi1hB62jjNgG b7ug== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=05x1ZopnWwBMtEdmV/JPYNRuKgulXaNLkHsmw7LTL4A=; b=AWCh6VQt4OkO/u7kyN+6No1Ku67gG28QNXjHTmCU2ejE06IWLS4GNQ112aYJse9GRy 7a1e3krdhYAdgpHRTonxwjK+ZpmJfMkPuxvMZeM4J++krdevFqFvAP5zMaZIQeA18krh YL8aoZjUQtDdrl7QNZu4LRdFQzbfVN9fhofi9DOhk5ynaSiV7izkkCxw+Y0zKB3871h3 sJGd6DkzQbH0zeXJ701U3QPoT7MDEfuDSmEPlaiUwrCfdxfXLVMWjqznkxYQSh6Iy89q VS75Tgnv98aEYUltkX2ZR5NpEZU/+EcW/cBC2LyAWd8eCNkWHJHI5CHv3xsGPRH1Yd0X 2AkA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=YHcHjMmZ; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id gb12-20020a170907960c00b007c0aa685133si7255067ejc.34.2022.12.17.21.04.55; Sat, 17 Dec 2022 21:05:18 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=YHcHjMmZ; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229585AbiLRFDv (ORCPT + 99 others); Sun, 18 Dec 2022 00:03:51 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50710 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229483AbiLRFDt (ORCPT ); Sun, 18 Dec 2022 00:03:49 -0500 Received: from mail-pl1-x633.google.com (mail-pl1-x633.google.com [IPv6:2607:f8b0:4864:20::633]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A2186CE1A for ; Sat, 17 Dec 2022 21:03:47 -0800 (PST) Received: by mail-pl1-x633.google.com with SMTP id d15so6074364pls.6 for ; Sat, 17 Dec 2022 21:03:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=05x1ZopnWwBMtEdmV/JPYNRuKgulXaNLkHsmw7LTL4A=; b=YHcHjMmZckEqBWA7m14w0qpwpwaUreVKq3CZi9mWUo6UemdN2BkyYf9cz9YzlzuUar NDmY+yTHG/N2KuuF8amnaM3WEiT6Jsp+ztiafNr4wp4PxR213rIq7jpBz8tf9ieuINKQ y+9mkcEXjKi57eVOaT2QqnjzfpqgsogQV7MiBA88yjrsZoVxeyG00NnKx+Q5omGF4Tzq V3goGYVt92ENnDdrNn6znUdMzg9Sr0i/Ip43A80gUDBN+s+/OyOJSVZ1yzEwWgpEAWBM qne6Xk7JHTdSbMWbmVuw7+jrLn8ZMBeYHNU0A7bZFNt7SfnWsZsHtxGUidRFjBrH1Mg3 VgZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=05x1ZopnWwBMtEdmV/JPYNRuKgulXaNLkHsmw7LTL4A=; b=THfNK6TmnyYBnDOi4A6EWCwpc23+iuxQlY21p/c6NmmYd7Y3rAsE66Ae/Lz9WNPhn2 KgKXuQFhlqrjUONm1OF4UKcDP3+8gMh+H4D6gU5iubZfi2rhg29x+ZAofMUt6DLCnu9X 0vdlNyWMsAFocyvpZnNKCPY7f5ZwTVxMfsH3O7lel52NNskhP73xfftDeatjBYO79Hla RY0oL1hSbIvIEX4iUGk/oLgxx7JOYqs25Yj7CsftGtuSxQC8zAnAmVv4YJB0FA7KkJo3 OwKs3yN5m2Xtk4YBe+alVWeaY2EtFEP2/WMuAriGxrmDGtZw0F7OjOoWxxmJsWVH6brg dapQ== X-Gm-Message-State: ANoB5pl7C9qIMv0lGeHYhqLuUn/lvWgPMw7azVIqbPF3xEsf205csHxb UYH4F792EhOjC4vW036B6wDHmA== X-Received: by 2002:a05:6a21:9188:b0:a4:3fc2:eb10 with SMTP id tp8-20020a056a21918800b000a43fc2eb10mr42409538pzb.37.1671339827060; Sat, 17 Dec 2022 21:03:47 -0800 (PST) Received: from devtp.bytedance.net ([139.177.225.227]) by smtp.gmail.com with ESMTPSA id v20-20020a170902ca9400b001708c4ebbaesm4339348pld.309.2022.12.17.21.03.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Dec 2022 21:03:46 -0800 (PST) From: wuqiang To: mhiramat@kernel.org, davem@davemloft.net, anil.s.keshavamurthy@intel.com, naveen.n.rao@linux.ibm.com, rostedt@goodmis.org, peterz@infradead.org, akpm@linux-foundation.org, sander@svanheule.net, ebiggers@google.com, dan.j.williams@intel.com, jpoimboe@kernel.org Cc: linux-kernel@vger.kernel.org, lkp@intel.com, mattwu@163.com, wuqiang Subject: [PATCH v8 1/5] lib: objpool added: ring-array based lockless MPMC queue Date: Sun, 18 Dec 2022 13:03:06 +0800 Message-Id: <20221218050310.1338630-2-wuqiang.matt@bytedance.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> References: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1752526926431457443?= X-GMAIL-MSGID: =?utf-8?q?1752526926431457443?= The object pool is a scalable implementaion of high performance queue for objects allocation and reclamation, such as kretprobe instances. With leveraging per-cpu ring-array to mitigate the hot spots of memory contention, it could deliver near-linear scalability for high parallel scenarios. The ring-array is compactly managed in a single cache-line to benefit from warmed L1 cache for most cases (<= 4 objects per-core). The body of pre-allocated objects is stored in continuous cache-lines just after the ring-array. The object pool is interrupt safe. Both allocation and reclamation (object pop and push operations) can be preemptible or interruptable. It's best suited for following cases: 1) Memory allocation or reclamation are prohibited or too expensive 2) Consumers are of different priorities, such as irqs and threads Limitations: 1) Maximum objects (capacity) is determined during pool initializing 2) The memory of objects won't be freed until the poll is finalized 3) Object allocation (pop) may fail after trying all cpu slots 4) Object reclamation (push) won't fail but may take long time to finish for imbalanced scenarios. You can try larger max_entries to mitigate, or ( >= CPUS * nr_objs) to avoid Signed-off-by: wuqiang --- include/linux/objpool.h | 116 +++++++++++++ lib/Makefile | 2 +- lib/objpool.c | 372 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 489 insertions(+), 1 deletion(-) create mode 100644 include/linux/objpool.h create mode 100644 lib/objpool.c diff --git a/include/linux/objpool.h b/include/linux/objpool.h new file mode 100644 index 000000000000..d5da724b82f7 --- /dev/null +++ b/include/linux/objpool.h @@ -0,0 +1,116 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifndef _LINUX_OBJPOOL_H +#define _LINUX_OBJPOOL_H + +#include +#include + +/* + * objpool: ring-array based lockless MPMC queue + * + * Copyright: wuqiang.matt@bytedance.com + * + * The object pool is a scalable implementaion of high performance queue + * for objects allocation and reclamation, such as kretprobe instances. + * + * With leveraging per-cpu ring-array to mitigate the hot spots of memory + * contention, it could deliver near-linear scalability for high parallel + * scenarios. The ring-array is compactly managed in a single cache-line + * to benefit from warmed L1 cache for most cases (<= 4 objects per-core). + * The body of pre-allocated objects is stored in continuous cache-lines + * just after the ring-array. + * + * The object pool is interrupt safe. Both allocation and reclamation + * (object pop and push operations) can be preemptible or interruptable. + * + * It's best suited for following cases: + * 1) Memory allocation or reclamation are prohibited or too expensive + * 2) Consumers are of different priorities, such as irqs and threads + * + * Limitations: + * 1) Maximum objects (capacity) is determined during pool initializing + * 2) The memory of objects won't be freed until the poll is finalized + * 3) Object allocation (pop) may fail after trying all cpu slots + */ + +/* + * objpool_slot: per-cpu ring array + * + * Represents a cpu-local array-based ring buffer, its size is specialized + * during initialization of object pool. + * + * The objpool_slot is allocated from local memory for NUMA system, and to + * be kept compact in a single cacheline. ages[] is stored just after the + * body of objpool_slot, and then entries[]. The Array of ages[] describes + * revision of each item, solely used to avoid ABA. And array of entries[] + * contains the pointers of objects. + * + * The default size of objpool_slot is a single cache-line, aka. 64 bytes. + * + * 64bit: + * 4 8 12 16 32 64 + * | head | tail | bits | mask | ages[4] | ents[4]: (8 * 4) | objects + * + * 32bit: + * 4 8 12 16 32 48 64 + * | head | tail | bits | mask | ages[4] | ents[4] | unused | objects + * + */ + +struct objpool_slot { + uint32_t head; /* head of ring array */ + uint32_t tail; /* tail of ring array */ + uint32_t bits; /* log2 of capacity */ + uint32_t mask; /* capacity - 1 */ +} __packed; + +struct objpool_head; + +/* caller-specified callback for object initial setup, only called once */ +typedef int (*objpool_init_obj_cb)(void *obj, void *context); + +/* caller-specified cleanup callback for objpool destruction */ +typedef int (*objpool_fini_cb)(struct objpool_head *head, void *context); + +/* + * objpool_head: object pooling metadata + */ +struct objpool_head { + int obj_size; /* object & element size */ + int nr_objs; /* total objs (to be pre-allocated) */ + int nr_cpus; /* nr_cpu_ids */ + int capacity; /* max objects per cpuslot */ + gfp_t gfp; /* gfp flags for kmalloc & vmalloc */ + refcount_t ref; /* refcount for objpool */ + unsigned long flags; /* flags for objpool management */ + struct objpool_slot **cpu_slots; /* array of percpu slots */ + int *slot_sizes; /* size in bytes of slots */ + objpool_fini_cb release; /* resource cleanup callback */ + void *context; /* caller-provided context */ +}; + +#define OBJPOOL_FROM_VMALLOC (0x800000000) /* objpool allocated from vmalloc area */ +#define OBJPOOL_HAVE_OBJECTS (0x400000000) /* objects allocated along with objpool */ + +/* initialize object pool and pre-allocate objects */ +int objpool_init(struct objpool_head *head, int nr_objs, int object_size, + gfp_t gfp, void *context, objpool_init_obj_cb objinit, + objpool_fini_cb release); + +/* allocate an object from object pool */ +void *objpool_pop(struct objpool_head *head); + +/* reclaim an object to object pool */ +int objpool_push(void *obj, struct objpool_head *head); + +/* drop the allocated object, rather reclaim it to objpool */ +int objpool_drop(void *obj, struct objpool_head *head); + +/* release whole objpool forcely */ +void objpool_free(struct objpool_head *head); + +/* drop unused objects and defref objpool for releasing */ +void objpool_fini(struct objpool_head *head); + +#endif /* _LINUX_OBJPOOL_H */ diff --git a/lib/Makefile b/lib/Makefile index 59bd7c2f793a..f23d9c4fe639 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -34,7 +34,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ nmi_backtrace.o win_minmax.o memcat_p.o \ - buildid.o + buildid.o objpool.o lib-$(CONFIG_PRINTK) += dump_stack.o lib-$(CONFIG_SMP) += cpumask.o diff --git a/lib/objpool.c b/lib/objpool.c new file mode 100644 index 000000000000..8732689d328c --- /dev/null +++ b/lib/objpool.c @@ -0,0 +1,372 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include +#include +#include +#include +#include +#include +#include + +/* + * objpool: ring-array based lockless MPMC/FIFO queues + * + * Copyright: wuqiang.matt@bytedance.com + */ + +/* compute the suitable num of objects to be managed by slot */ +static inline int objpool_nobjs(int size) +{ + return rounddown_pow_of_two((size - sizeof(struct objpool_slot)) / + (sizeof(uint32_t) + sizeof(void *))); +} + +#define SLOT_AGES(s) ((uint32_t *)((char *)(s) + sizeof(struct objpool_slot))) +#define SLOT_ENTS(s) ((void **)((char *)(s) + sizeof(struct objpool_slot) + \ + (sizeof(uint32_t) << (s)->bits))) +#define SLOT_OBJS(s) ((void *)((char *)(s) + sizeof(struct objpool_slot) + \ + ((sizeof(uint32_t) + sizeof(void *)) << (s)->bits))) +#define SLOT_CORE(n) cpumask_nth((n) % num_possible_cpus(), cpu_possible_mask) + +/* allocate and initialize percpu slots */ +static inline int +objpool_init_percpu_slots(struct objpool_head *head, int nobjs, + void *context, objpool_init_obj_cb objinit) +{ + int i, j, n, size, objsz, cpu = 0, nents = head->capacity; + + /* aligned object size by sizeof(void *) */ + objsz = ALIGN(head->obj_size, sizeof(void *)); + /* shall we allocate objects along with objpool_slot */ + if (objsz) + head->flags |= OBJPOOL_HAVE_OBJECTS; + + for (i = 0; i < head->nr_cpus; i++) { + struct objpool_slot *os; + + /* skip the cpus which could never be present */ + if (!cpu_possible(i)) + continue; + + /* compute how many objects to be managed by this slot */ + n = nobjs / num_possible_cpus(); + if (cpu < (nobjs % num_possible_cpus())) + n++; + size = sizeof(struct objpool_slot) + sizeof(void *) * nents + + sizeof(uint32_t) * nents + objsz * n; + + /* decide memory area for cpu-slot allocation */ + if (!cpu && !(head->gfp & GFP_ATOMIC) && size > PAGE_SIZE / 2) + head->flags |= OBJPOOL_FROM_VMALLOC; + + /* allocate percpu slot & objects from local memory */ + if (head->flags & OBJPOOL_FROM_VMALLOC) + os = __vmalloc_node(size, sizeof(void *), head->gfp, + cpu_to_node(i), __builtin_return_address(0)); + else + os = kmalloc_node(size, head->gfp, cpu_to_node(i)); + if (!os) + return -ENOMEM; + + /* initialize percpu slot for the i-th slot */ + memset(os, 0, size); + os->bits = ilog2(head->capacity); + os->mask = head->capacity - 1; + head->cpu_slots[i] = os; + head->slot_sizes[i] = size; + cpu = cpu + 1; + + /* + * start from 2nd round to avoid conflict of 1st item. + * we assume that the head item is ready for retrieval + * iff head is equal to ages[head & mask]. but ages is + * initialized as 0, so in view of the caller of pop(), + * the 1st item (0th) is always ready, but fact could + * be: push() is stalled before the final update, thus + * the item being inserted will be lost forever. + */ + os->head = os->tail = head->capacity; + + if (!objsz) + continue; + + for (j = 0; j < n; j++) { + uint32_t *ages = SLOT_AGES(os); + void **ents = SLOT_ENTS(os); + void *obj = SLOT_OBJS(os) + j * objsz; + uint32_t ie = os->tail & os->mask; + + /* perform object initialization */ + if (objinit) { + int rc = objinit(obj, context); + if (rc) + return rc; + } + + /* add obj into the ring array */ + ents[ie] = obj; + ages[ie] = os->tail; + os->tail++; + head->nr_objs++; + } + } + + return 0; +} + +/* cleanup all percpu slots of the object pool */ +static inline void objpool_fini_percpu_slots(struct objpool_head *head) +{ + int i; + + if (!head->cpu_slots) + return; + + for (i = 0; i < head->nr_cpus; i++) { + if (!head->cpu_slots[i]) + continue; + if (head->flags & OBJPOOL_FROM_VMALLOC) + vfree(head->cpu_slots[i]); + else + kfree(head->cpu_slots[i]); + } + kfree(head->cpu_slots); + head->cpu_slots = NULL; + head->slot_sizes = NULL; +} + +/** + * objpool_init: initialize object pool and pre-allocate objects + * + * args: + * @head: the object pool to be initialized, declared by caller + * @nr_objs: total objects to be pre-allocated by this object pool + * @object_size: size of an object, no objects pre-allocated if 0 + * @gfp: flags for memory allocation (via kmalloc or vmalloc) + * @context: user context for object initialization callback + * @objinit: object initialization callback for extra setting-up + * @release: cleanup callback for private objects/pool/context + * + * return: + * 0 for success, otherwise error code + * + * All pre-allocated objects are to be zeroed. Caller could do extra + * initialization in objinit callback. The objinit callback will be + * called once and only once after the slot allocation. Then objpool + * won't touch any content of the objects since then. It's caller's + * duty to perform reinitialization after object allocation (pop) or + * clearance before object reclamation (push) if required. + */ +int objpool_init(struct objpool_head *head, int nr_objs, int object_size, + gfp_t gfp, void *context, objpool_init_obj_cb objinit, + objpool_fini_cb release) +{ + int nents, rc; + + /* check input parameters */ + if (nr_objs <= 0 || object_size < 0) + return -EINVAL; + + /* calculate percpu slot size (rounded to pow of 2) */ + nents = max_t(int, roundup_pow_of_two(nr_objs), + objpool_nobjs(L1_CACHE_BYTES)); + + /* initialize objpool head */ + memset(head, 0, sizeof(struct objpool_head)); + head->nr_cpus = nr_cpu_ids; + head->obj_size = object_size; + head->capacity = nents; + head->gfp = gfp & ~__GFP_ZERO; + head->context = context; + head->release = release; + + /* allocate array for percpu slots */ + head->cpu_slots = kzalloc(head->nr_cpus * sizeof(void *) + + head->nr_cpus * sizeof(uint32_t), head->gfp); + if (!head->cpu_slots) + return -ENOMEM; + head->slot_sizes = (uint32_t *)&head->cpu_slots[head->nr_cpus]; + + /* initialize per-cpu slots */ + rc = objpool_init_percpu_slots(head, nr_objs, context, objinit); + if (rc) + objpool_fini_percpu_slots(head); + else + refcount_set(&head->ref, nr_objs + 1); + + return rc; +} +EXPORT_SYMBOL_GPL(objpool_init); + +/* adding object to slot tail, the given slot must NOT be full */ +static inline int objpool_add_slot(void *obj, struct objpool_slot *os) +{ + uint32_t *ages = SLOT_AGES(os); + void **ents = SLOT_ENTS(os); + uint32_t tail = atomic_inc_return((atomic_t *)&os->tail) - 1; + + WRITE_ONCE(ents[tail & os->mask], obj); + + /* order matters: obj must be updated before tail updating */ + smp_store_release(&ages[tail & os->mask], tail); + return 0; +} + +/** + * objpool_push: reclaim the object and return back to object pool + * + * args: + * @obj: object pointer to be pushed to object pool + * @head: object pool + * + * return: + * 0 or error code: it fails only when object pool is full + * + * objpool_push is non-blockable, and can be nested + */ +int objpool_push(void *obj, struct objpool_head *head) +{ + int cpu = raw_smp_processor_id(); + + return objpool_add_slot(obj, head->cpu_slots[cpu]); +} +EXPORT_SYMBOL_GPL(objpool_push); + + +/** + * objpool_drop: discard the object and deref objpool + * + * args: + * @obj: object pointer to be discarded + * @head: object pool + * + * return: + * 0 if objpool was released, or error codes + * + * objpool_push is non-blockable, and can be nested + */ +int objpool_drop(void *obj, struct objpool_head *head) +{ + if (!obj || !head) + return -EINVAL; + + if (refcount_dec_and_test(&head->ref)) { + objpool_free(head); + return 0; + } + + return -EAGAIN; +} +EXPORT_SYMBOL_GPL(objpool_drop); + +/* try to retrieve object from slot */ +static inline void *objpool_try_get_slot(struct objpool_slot *os) +{ + uint32_t *ages = SLOT_AGES(os); + void **ents = SLOT_ENTS(os); + /* do memory load of head to local head */ + uint32_t head = smp_load_acquire(&os->head); + + /* loop if slot isn't empty */ + while (head != READ_ONCE(os->tail)) { + uint32_t id = head & os->mask, prev = head; + + /* do prefetching of object ents */ + prefetch(&ents[id]); + + /* + * check whether this item was ready for retrieval ? There's + * possibility * in theory * we might retrieve wrong object, + * in case ages[id] overflows when current task is sleeping, + * but it will take very very long to overflow an uint32_t + */ + if (smp_load_acquire(&ages[id]) == head) { + /* node must have been udpated by push() */ + void *node = READ_ONCE(ents[id]); + /* commit and move forward head of the slot */ + if (try_cmpxchg_release(&os->head, &head, head + 1)) + return node; + } + + /* re-load head from memory and continue trying */ + head = READ_ONCE(os->head); + /* + * head stays unchanged, so it's very likely current pop() + * just preempted/interrupted an ongoing push() operation + */ + if (head == prev) + break; + } + + return NULL; +} + +/** + * objpool_pop: allocate an object from object pool + * + * args: + * @head: object pool + * + * return: + * object: NULL if failed (object pool is empty) + * + * objpool_pop can be nested, so can be used in any context. + */ +void *objpool_pop(struct objpool_head *head) +{ + int i, cpu = raw_smp_processor_id(); + void *obj = NULL; + + for (i = 0; i < num_possible_cpus(); i++) { + obj = objpool_try_get_slot(head->cpu_slots[cpu]); + if (obj) + break; + cpu = cpumask_next_wrap(cpu, cpu_possible_mask, -1, 1); + } + + return obj; +} +EXPORT_SYMBOL_GPL(objpool_pop); + +/** + * objpool_free: release objpool forcely (all objects to be freed) + * + * args: + * @head: object pool to be released + * + */ +void objpool_free(struct objpool_head *head) +{ + if (!head->cpu_slots) + return; + + /* release percpu slots */ + objpool_fini_percpu_slots(head); + + /* call user's cleanup callback if provided */ + if (head->release) + head->release(head, head->context); +} +EXPORT_SYMBOL_GPL(objpool_free); + +/** + * objpool_fini: deref object pool (also releasing unused objects) + * + * args: + * @head: object pool to be dereferenced + * + */ +void objpool_fini(struct objpool_head *head) +{ + void *nod; + + do { + /* grab object from objpool and drop it */ + nod = objpool_pop(head); + + /* drop the extra ref of objpool */ + if (refcount_dec_and_test(&head->ref)) + objpool_free(head); + } while (nod); +} +EXPORT_SYMBOL_GPL(objpool_fini); From patchwork Sun Dec 18 05:03:07 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "wuqiang.matt" X-Patchwork-Id: 34289 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp1792064wrn; Sat, 17 Dec 2022 21:17:19 -0800 (PST) X-Google-Smtp-Source: AA0mqf7LRKwUmGrg6H9698XeNC6V86dbo1eu+Aykd39lPPfGr3iJglknU2ur98Yn1D4npNodUnsB X-Received: by 2002:a05:6a20:c887:b0:ac:f68:33c9 with SMTP id hb7-20020a056a20c88700b000ac0f6833c9mr47654894pzb.33.1671340639683; Sat, 17 Dec 2022 21:17:19 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1671340639; cv=none; d=google.com; s=arc-20160816; b=xLy/e9+qbfMDWNv4rU4NNDdxC2K/0gw/0CTcUt5krI5KC3ljZ3K27NVIHDz8W6fkwx ssAockwcxkhtKAcCxtzNxrl/UupbJg6spYKhkMxx4abOPx4ddZfGSUC+Ea+MwiYIhkw9 BVY/hqNiQeLYfAihfGOAW9DkwZsSyp28Ev34AjdkORcx5ACDKPOwuQa8OJaJP6jCMlf2 BHtqgibltlWNnT0PcThlefJvnf7OZnT5VEs4PtMzGSZPKytVBg2eoH2OQgjVpDDlXWmB WfdP6HVlO3fk0hx+uhQCIfqr/Kv4yyLaaHoVyzwYqGmvNWOd6Geefk6J89+o+YIPbWjV BQSQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=PbYDej34AwE+THrTNclLoDC+HqZB4S12aeHzPhYlomQ=; b=v0dKv028IrpFTdAvOZvLbaKiDsAF/tAZ6j90OM7Pkh5mGZpQ7QTMA/db7aL6uY8Cjv Vf/cdyCTETO8b4ghAioR8+o2UmBSAWWiwPPq+HsaXx0TgSMWqPB12OcqpkqAA85XbYIB 1ITVWMXKFTNIhOyBK3ldRFzXyATsVVMdVWuJtFIkhNcmEeUl3J07zvRjxouBXnpDMfBT YKK6g6LZJdAK40Pmrqhr4vMYItd9CEwbvatuaDOyIpUmV4NSj61+XB8UXCTxt/fZoJer zQDTQP7L12YE8j7j6UgbLdeLysl4jPUMM/P1nhUtLDeLboLXebxrWBwZZl3vRlkN+Hev T9OA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=xESiSIbG; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id cd7-20020a056a00420700b005730a1bbac0si6303558pfb.354.2022.12.17.21.17.07; Sat, 17 Dec 2022 21:17:19 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=xESiSIbG; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230191AbiLRFEf (ORCPT + 99 others); Sun, 18 Dec 2022 00:04:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50742 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229964AbiLRFET (ORCPT ); Sun, 18 Dec 2022 00:04:19 -0500 Received: from mail-pl1-x634.google.com (mail-pl1-x634.google.com [IPv6:2607:f8b0:4864:20::634]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4A7DACE38 for ; Sat, 17 Dec 2022 21:03:54 -0800 (PST) Received: by mail-pl1-x634.google.com with SMTP id g10so6042183plo.11 for ; Sat, 17 Dec 2022 21:03:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=PbYDej34AwE+THrTNclLoDC+HqZB4S12aeHzPhYlomQ=; b=xESiSIbG0lpxQ86Y4m/Hu6h5u9FIsmw82jpn+9futQlB1d5u0EWcaBZk8J7AvFtvlE 3LLZ1FVe/8bfVan+cECuzF/Q552Sjte0v4W9l8zbX0G/evn41JNYvqkOPwry9y5GcpNO 2fM8GvlsQ3i0Iqx+y2yBfozyPFXG5rO0EJdEPFXicXbH7tjbGOtV1Jc+suWsZlrgJwhs nikADNDP2mX86782uAqi358fGzFGdWkvoOiku9Gh/EXuD1JqYaLvoI3CiwNiswe24qod Q5WehcJ6YzyBeSXPYqOJ0ctMGhXIuNIlh0MSDMJ9vZKkOZIukhTZG52UbqyEkmsMCayz 218Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=PbYDej34AwE+THrTNclLoDC+HqZB4S12aeHzPhYlomQ=; b=v0V5L/yN0+/Ow6Ut4mVmR3Cw7lPNTjiXaaZfBxwcPtnRryZv6+xfDq27xTQdVjcxqP LEAC27TmJK8iOOxA2CSLmcBgqpY+I0pbWR7k3f+fK1kyW2LxalgW4eE2h7eJt1m1iS/H uzTroxAfzDKXJVI8YPMziHZW6ZyJtfNRfzMaJTpQT/hdpXFnQ4yshxgDehtE+tmRJW0l QlwXA9ZsiFJYJOFbpqOoWg9YInWHKor2k2VXqgghj1OCTLynudKmbVvhVPTa1opqErSf LtqC1OgkLwLcYDZ7VObZNAFvfATtTlyKKNS006y7JQvV6OBpQSQHuralFN2KriW+sYNT PepQ== X-Gm-Message-State: AFqh2krL252dlSjNcyJrJ0pG3FF7VMpv0nuyaY+fjT9l0PRxbdPB8QLO t1kXSXypAtrh+7zx0JoXWHuJVQ== X-Received: by 2002:a17:903:449:b0:191:24a:63e3 with SMTP id iw9-20020a170903044900b00191024a63e3mr9108872plb.50.1671339833442; Sat, 17 Dec 2022 21:03:53 -0800 (PST) Received: from devtp.bytedance.net ([139.177.225.227]) by smtp.gmail.com with ESMTPSA id v20-20020a170902ca9400b001708c4ebbaesm4339348pld.309.2022.12.17.21.03.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Dec 2022 21:03:53 -0800 (PST) From: wuqiang To: mhiramat@kernel.org, davem@davemloft.net, anil.s.keshavamurthy@intel.com, naveen.n.rao@linux.ibm.com, rostedt@goodmis.org, peterz@infradead.org, akpm@linux-foundation.org, sander@svanheule.net, ebiggers@google.com, dan.j.williams@intel.com, jpoimboe@kernel.org Cc: linux-kernel@vger.kernel.org, lkp@intel.com, mattwu@163.com, wuqiang Subject: [PATCH v8 2/5] lib: objpool test module added Date: Sun, 18 Dec 2022 13:03:07 +0800 Message-Id: <20221218050310.1338630-3-wuqiang.matt@bytedance.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> References: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1752527682164940219?= X-GMAIL-MSGID: =?utf-8?q?1752527682164940219?= The test_objpool module (test_objpool) will run several testcases for objpool stress and performance evaluation. Each testcase will have all available cpu cores involved to create a situation of high parallel and high contention. As of now there are 3 groups and 3 * 2 testcases in total: 1) group 1: synchronous mode objpool is managed synchronously, that is, all objects are to be reclaimed before objpool finalization and the objpool owner makes sure of it. All threads on different cores run in the same pace. 2) group 2: synchronous + miss mode This test group is mainly for performance evaluation of missing cases when pre-allocated objects are less than the requested. 3) group 3: asynchronous mode This case is just an emulation of kretprobe. The objpool owner has no control of the object after it's allocated. hrtimer irq is introduced to stress objpool with thread preemption. Signed-off-by: wuqiang --- lib/Kconfig.debug | 11 + lib/Makefile | 2 + lib/test_objpool.c | 682 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 695 insertions(+) create mode 100644 lib/test_objpool.c diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 3638b3424be5..840903b51434 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2750,6 +2750,17 @@ config TEST_CLOCKSOURCE_WATCHDOG If unsure, say N. +config TEST_OBJPOOL + tristate "Test module for correctness and stress of objpool" + default n + depends on m + help + This builds the "test_objpool" module that should be used for + correctness verification and concurrent testings of objects + allocation and reclamation. + + If unsure, say N. + endif # RUNTIME_TESTING_MENU config ARCH_USE_MEMTEST diff --git a/lib/Makefile b/lib/Makefile index f23d9c4fe639..c078dc5f64ac 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -100,6 +100,8 @@ obj-$(CONFIG_KPROBES_SANITY_TEST) += test_kprobes.o obj-$(CONFIG_TEST_REF_TRACKER) += test_ref_tracker.o CFLAGS_test_fprobe.o += $(CC_FLAGS_FTRACE) obj-$(CONFIG_FPROBE_SANITY_TEST) += test_fprobe.o +obj-$(CONFIG_TEST_OBJPOOL) += test_objpool.o + # # CFLAGS for compiling floating point code inside the kernel. x86/Makefile turns # off the generation of FPU/SSE* instructions for kernel proper but FPU_FLAGS diff --git a/lib/test_objpool.c b/lib/test_objpool.c new file mode 100644 index 000000000000..5c55d0b7aab0 --- /dev/null +++ b/lib/test_objpool.c @@ -0,0 +1,682 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* + * Test module for lockless object pool + * (C) 2022 Matt Wu + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define OT_NR_MAX_BULK (16) + +struct ot_ctrl { + int mode; /* test no */ + int objsz; /* object size */ + int duration; /* ms */ + int delay; /* ms */ + int bulk_normal; + int bulk_irq; + unsigned long hrtimer; /* ms */ + const char *name; +}; + +struct ot_stat { + unsigned long nhits; + unsigned long nmiss; +}; + +struct ot_item { + struct objpool_head *pool; /* pool head */ + struct ot_ctrl *ctrl; /* ctrl parameters */ + + void (*worker)(struct ot_item *item, int irq); + + /* hrtimer control */ + ktime_t hrtcycle; + struct hrtimer hrtimer; + + int bulk[2]; /* for thread and irq */ + int delay; + u32 niters; + + /* results summary */ + struct ot_stat stat[2]; /* thread and irq */ + + u64 duration; +}; + +struct ot_mem_stat { + atomic_long_t alloc; + atomic_long_t free; +}; + +struct ot_data { + struct rw_semaphore start; + struct completion wait; + struct completion rcu; + atomic_t nthreads ____cacheline_aligned_in_smp; + atomic_t stop ____cacheline_aligned_in_smp; + struct ot_mem_stat kmalloc; + struct ot_mem_stat vmalloc; +} g_ot_data; + +/* + * memory leakage checking + */ + +static void *ot_kzalloc(long size) +{ + void *ptr = kzalloc(size, GFP_KERNEL); + + if (ptr) + atomic_long_add(size, &g_ot_data.kmalloc.alloc); + return ptr; +} + +static void ot_kfree(void *ptr, long size) +{ + if (!ptr) + return; + atomic_long_add(size, &g_ot_data.kmalloc.free); + kfree(ptr); +} + +static void ot_mem_report(struct ot_ctrl *ctrl) +{ + long alloc, free; + + pr_info("memory allocation summary for %s\n", ctrl->name); + + alloc = atomic_long_read(&g_ot_data.kmalloc.alloc); + free = atomic_long_read(&g_ot_data.kmalloc.free); + pr_info(" kmalloc: %lu - %lu = %lu\n", alloc, free, alloc - free); + + alloc = atomic_long_read(&g_ot_data.vmalloc.alloc); + free = atomic_long_read(&g_ot_data.vmalloc.free); + pr_info(" vmalloc: %lu - %lu = %lu\n", alloc, free, alloc - free); +} + +/* + * general structs & routines + */ + +struct ot_node { + void *owner; + unsigned long data; + unsigned long refs; + unsigned long payload[32]; +}; + +struct ot_context { + struct objpool_head pool; /* objpool head */ + struct ot_ctrl *ctrl; /* ctrl parameters */ + void *ptr; /* user pool buffer */ + unsigned long size; /* buffer size */ + struct rcu_head rcu; +}; + +static DEFINE_PER_CPU(struct ot_item, ot_pcup_items); + +static int ot_init_data(struct ot_data *data) +{ + memset(data, 0, sizeof(*data)); + init_rwsem(&data->start); + init_completion(&data->wait); + init_completion(&data->rcu); + atomic_set(&data->nthreads, 1); + + return 0; +} + +static void ot_reset_data(struct ot_data *data) +{ + reinit_completion(&data->wait); + reinit_completion(&data->rcu); + atomic_set(&data->nthreads, 1); + atomic_set(&data->stop, 0); + memset(&data->kmalloc, 0, sizeof(data->kmalloc)); + memset(&data->vmalloc, 0, sizeof(data->vmalloc)); +} + +static int ot_init_node(void *nod, void *context) +{ + struct ot_context *sop = context; + struct ot_node *on = nod; + + on->owner = &sop->pool; + return 0; +} + +static enum hrtimer_restart ot_hrtimer_handler(struct hrtimer *hrt) +{ + struct ot_item *item = container_of(hrt, struct ot_item, hrtimer); + + if (atomic_read_acquire(&g_ot_data.stop)) + return HRTIMER_NORESTART; + + /* do bulk-testings for objects pop/push */ + item->worker(item, 1); + + hrtimer_forward(hrt, hrt->base->get_time(), item->hrtcycle); + return HRTIMER_RESTART; +} + +static void ot_start_hrtimer(struct ot_item *item) +{ + if (!item->ctrl->hrtimer) + return; + hrtimer_start(&item->hrtimer, item->hrtcycle, HRTIMER_MODE_REL); +} + +static void ot_stop_hrtimer(struct ot_item *item) +{ + if (!item->ctrl->hrtimer) + return; + hrtimer_cancel(&item->hrtimer); +} + +static int ot_init_hrtimer(struct ot_item *item, unsigned long hrtimer) +{ + struct hrtimer *hrt = &item->hrtimer; + + if (!hrtimer) + return -ENOENT; + + item->hrtcycle = ktime_set(0, hrtimer * 1000000UL); + hrtimer_init(hrt, CLOCK_MONOTONIC, HRTIMER_MODE_REL); + hrt->function = ot_hrtimer_handler; + return 0; +} + +static int ot_init_cpu_item(struct ot_item *item, + struct ot_ctrl *ctrl, + struct objpool_head *pool, + void (*worker)(struct ot_item *, int)) +{ + memset(item, 0, sizeof(*item)); + item->pool = pool; + item->ctrl = ctrl; + item->worker = worker; + + item->bulk[0] = ctrl->bulk_normal; + item->bulk[1] = ctrl->bulk_irq; + item->delay = ctrl->delay; + + /* initialize hrtimer */ + ot_init_hrtimer(item, item->ctrl->hrtimer); + return 0; +} + +static int ot_thread_worker(void *arg) +{ + struct ot_item *item = arg; + ktime_t start; + + sched_set_normal(current, 50); + + atomic_inc(&g_ot_data.nthreads); + down_read(&g_ot_data.start); + up_read(&g_ot_data.start); + start = ktime_get(); + ot_start_hrtimer(item); + do { + if (atomic_read_acquire(&g_ot_data.stop)) + break; + /* do bulk-testings for objects pop/push */ + item->worker(item, 0); + } while (!kthread_should_stop()); + ot_stop_hrtimer(item); + item->duration = (u64) ktime_us_delta(ktime_get(), start); + if (atomic_dec_and_test(&g_ot_data.nthreads)) + complete(&g_ot_data.wait); + + return 0; +} + +static void ot_perf_report(struct ot_ctrl *ctrl, u64 duration) +{ + struct ot_stat total, normal = {0}, irq = {0}; + int cpu, nthreads = 0; + + pr_info("\n"); + pr_info("Testing summary for %s\n", ctrl->name); + + for_each_possible_cpu(cpu) { + struct ot_item *item = per_cpu_ptr(&ot_pcup_items, cpu); + if (!item->duration) + continue; + normal.nhits += item->stat[0].nhits; + normal.nmiss += item->stat[0].nmiss; + irq.nhits += item->stat[1].nhits; + irq.nmiss += item->stat[1].nmiss; + pr_info("CPU: %d duration: %lluus\n", cpu, item->duration); + pr_info("\tthread:\t%16lu hits \t%16lu miss\n", + item->stat[0].nhits, item->stat[0].nmiss); + pr_info("\tirq: \t%16lu hits \t%16lu miss\n", + item->stat[1].nhits, item->stat[1].nmiss); + pr_info("\ttotal: \t%16lu hits \t%16lu miss\n", + item->stat[0].nhits + item->stat[1].nhits, + item->stat[0].nmiss + item->stat[1].nmiss); + nthreads++; + } + + total.nhits = normal.nhits + irq.nhits; + total.nmiss = normal.nmiss + irq.nmiss; + + pr_info("ALL: \tnthreads: %d duration: %lluus\n", nthreads, duration); + pr_info("SUM: \t%16lu hits \t%16lu miss\n", + total.nhits, total.nmiss); +} + +/* + * synchronous test cases for objpool manipulation + */ + +/* objpool manipulation for synchronous mode 0 (percpu objpool) */ +static struct ot_context *ot_init_sync_m0(struct ot_ctrl *ctrl) +{ + struct ot_context *sop = NULL; + int max = num_possible_cpus() << 3; + + sop = (struct ot_context *)ot_kzalloc(sizeof(*sop)); + if (!sop) + return NULL; + sop->ctrl = ctrl; + + if (objpool_init(&sop->pool, max, ctrl->objsz, + GFP_KERNEL, sop, ot_init_node, NULL)) { + ot_kfree(sop, sizeof(*sop)); + return NULL; + } + WARN_ON(max != sop->pool.nr_objs); + + return sop; +} + +static void ot_fini_sync_m0(struct ot_context *sop) +{ + objpool_fini(&sop->pool); + ot_kfree(sop, sizeof(*sop)); +} + +struct { + struct ot_context * (*init)(struct ot_ctrl *oc); + void (*fini)(struct ot_context *sop); +} g_ot_sync_ops[] = { + {.init = ot_init_sync_m0, .fini = ot_fini_sync_m0}, +}; + +/* + * synchronous test cases: performance mode + */ + +static void ot_bulk_sync(struct ot_item *item, int irq) +{ + struct ot_node *nods[OT_NR_MAX_BULK]; + int i; + + for (i = 0; i < item->bulk[irq]; i++) + nods[i] = objpool_pop(item->pool); + + if (!irq && (item->delay || !(++(item->niters) & 0x7FFF))) + msleep(item->delay); + + while (i-- > 0) { + struct ot_node *on = nods[i]; + if (on) { + on->refs++; + objpool_push(on, item->pool); + item->stat[irq].nhits++; + } else { + item->stat[irq].nmiss++; + } + } +} + +static int ot_start_sync(struct ot_ctrl *ctrl) +{ + struct ot_context *sop; + ktime_t start; + u64 duration; + unsigned long timeout; + int cpu, rc; + + /* initialize objpool for syncrhonous testcase */ + sop = g_ot_sync_ops[ctrl->mode].init(ctrl); + if (!sop) + return -ENOMEM; + + /* grab rwsem to block testing threads */ + down_write(&g_ot_data.start); + + for_each_possible_cpu(cpu) { + struct ot_item *item = per_cpu_ptr(&ot_pcup_items, cpu); + struct task_struct *work; + + ot_init_cpu_item(item, ctrl, &sop->pool, ot_bulk_sync); + + /* skip offline cpus */ + if (!cpu_online(cpu)) + continue; + + work = kthread_create_on_node(ot_thread_worker, item, + cpu_to_node(cpu), "ot_worker_%d", cpu); + if (IS_ERR(work)) { + pr_err("failed to create thread for cpu %d\n", cpu); + } else { + kthread_bind(work, cpu); + wake_up_process(work); + } + } + + /* wait a while to make sure all threads waiting at start line */ + msleep(20); + + /* in case no threads were created: memory insufficient ? */ + if (atomic_dec_and_test(&g_ot_data.nthreads)) + complete(&g_ot_data.wait); + + // sched_set_fifo_low(current); + + /* start objpool testing threads */ + start = ktime_get(); + up_write(&g_ot_data.start); + + /* yeild cpu to worker threads for duration ms */ + timeout = msecs_to_jiffies(ctrl->duration); + rc = schedule_timeout_interruptible(timeout); + + /* tell workers threads to quit */ + atomic_set_release(&g_ot_data.stop, 1); + + /* wait all workers threads finish and quit */ + wait_for_completion(&g_ot_data.wait); + duration = (u64) ktime_us_delta(ktime_get(), start); + + /* cleanup objpool */ + g_ot_sync_ops[ctrl->mode].fini(sop); + + /* report testing summary and performance results */ + ot_perf_report(ctrl, duration); + + /* report memory allocation summary */ + ot_mem_report(ctrl); + + return rc; +} + +/* + * asynchronous test cases: pool lifecycle controlled by refcount + */ + +static void ot_fini_async_rcu(struct rcu_head *rcu) +{ + struct ot_context *sop = container_of(rcu, struct ot_context, rcu); + + /* here all cpus are aware of the stop event: g_ot_data.stop = 1 */ + WARN_ON(!atomic_read_acquire(&g_ot_data.stop)); + + objpool_fini(&sop->pool); + complete(&g_ot_data.rcu); +} + +static void ot_fini_async(struct ot_context *sop) +{ + /* make sure the stop event is acknowledged by all cores */ + call_rcu(&sop->rcu, ot_fini_async_rcu); +} + +static int ot_objpool_release(struct objpool_head *head, void *context) +{ + struct ot_context *sop = context; + + WARN_ON(!head || !sop || head != &sop->pool); + + /* do context cleaning if needed */ + if (sop) + ot_kfree(sop, sizeof(*sop)); + + return 0; +} + +static struct ot_context *ot_init_async_m0(struct ot_ctrl *ctrl) +{ + struct ot_context *sop = NULL; + int max = num_possible_cpus() << 3; + + sop = (struct ot_context *)ot_kzalloc(sizeof(*sop)); + if (!sop) + return NULL; + sop->ctrl = ctrl; + + if (objpool_init(&sop->pool, max, ctrl->objsz, GFP_KERNEL, + sop, ot_init_node, ot_objpool_release)) { + ot_kfree(sop, sizeof(*sop)); + return NULL; + } + WARN_ON(max != sop->pool.nr_objs); + + return sop; +} + +struct { + struct ot_context * (*init)(struct ot_ctrl *oc); + void (*fini)(struct ot_context *sop); +} g_ot_async_ops[] = { + {.init = ot_init_async_m0, .fini = ot_fini_async}, +}; + +static void ot_nod_recycle(struct ot_node *on, struct objpool_head *pool, + int release) +{ + struct ot_context *sop; + + on->refs++; + + if (!release) { + /* push object back to opjpool for reuse */ + objpool_push(on, pool); + return; + } + + sop = container_of(pool, struct ot_context, pool); + WARN_ON(sop != pool->context); + + /* unref objpool with nod removed forever */ + objpool_drop(on, pool); +} + +static void ot_bulk_async(struct ot_item *item, int irq) +{ + struct ot_node *nods[OT_NR_MAX_BULK]; + int i, stop; + + for (i = 0; i < item->bulk[irq]; i++) + nods[i] = objpool_pop(item->pool); + + if (!irq) { + if (item->delay || !(++(item->niters) & 0x7FFF)) + msleep(item->delay); + get_cpu(); + } + + stop = atomic_read_acquire(&g_ot_data.stop); + + /* drop all objects and deref objpool */ + while (i-- > 0) { + struct ot_node *on = nods[i]; + + if (on) { + on->refs++; + ot_nod_recycle(on, item->pool, stop); + item->stat[irq].nhits++; + } else { + item->stat[irq].nmiss++; + } + } + + if (!irq) + put_cpu(); +} + +static int ot_start_async(struct ot_ctrl *ctrl) +{ + struct ot_context *sop; + ktime_t start; + u64 duration; + unsigned long timeout; + int cpu, rc; + + /* initialize objpool for syncrhonous testcase */ + sop = g_ot_async_ops[ctrl->mode].init(ctrl); + if (!sop) + return -ENOMEM; + + /* grab rwsem to block testing threads */ + down_write(&g_ot_data.start); + + for_each_possible_cpu(cpu) { + struct ot_item *item = per_cpu_ptr(&ot_pcup_items, cpu); + struct task_struct *work; + + ot_init_cpu_item(item, ctrl, &sop->pool, ot_bulk_async); + + /* skip offline cpus */ + if (!cpu_online(cpu)) + continue; + + work = kthread_create_on_node(ot_thread_worker, item, + cpu_to_node(cpu), "ot_worker_%d", cpu); + if (IS_ERR(work)) { + pr_err("failed to create thread for cpu %d\n", cpu); + } else { + kthread_bind(work, cpu); + wake_up_process(work); + } + } + + /* wait a while to make sure all threads waiting at start line */ + msleep(20); + + /* in case no threads were created: memory insufficient ? */ + if (atomic_dec_and_test(&g_ot_data.nthreads)) + complete(&g_ot_data.wait); + + /* start objpool testing threads */ + start = ktime_get(); + up_write(&g_ot_data.start); + + /* yeild cpu to worker threads for duration ms */ + timeout = msecs_to_jiffies(ctrl->duration); + rc = schedule_timeout_interruptible(timeout); + + /* tell workers threads to quit */ + atomic_set_release(&g_ot_data.stop, 1); + + /* do async-finalization */ + g_ot_async_ops[ctrl->mode].fini(sop); + + /* wait all workers threads finish and quit */ + wait_for_completion(&g_ot_data.wait); + duration = (u64) ktime_us_delta(ktime_get(), start); + + /* assure rcu callback is triggered */ + wait_for_completion(&g_ot_data.rcu); + + /* + * now we are sure that objpool is finalized either + * by rcu callback or by worker threads + */ + + /* report testing summary and performance results */ + ot_perf_report(ctrl, duration); + + /* report memory allocation summary */ + ot_mem_report(ctrl); + + return rc; +} + +/* + * predefined testing cases: + * synchronous case / overrun case / async case + * + * mode: int, currently only mode 0 is supoorted + * duration: int, total test time in ms + * delay: int, delay (in ms) between each iteration + * bulk_normal: int, repeat times for thread worker + * bulk_irq: int, repeat times for irq consumer + * hrtimer: unsigned long, hrtimer intervnal in ms + * name: char *, tag for current test ot_item + */ + +#define NODE_COMPACT sizeof(struct ot_node) +#define NODE_VMALLOC (512) + +struct ot_ctrl g_ot_sync[] = { + {0, NODE_COMPACT, 1000, 0, 1, 0, 0, "sync: percpu objpool"}, + {0, NODE_VMALLOC, 1000, 0, 1, 0, 0, "sync: percpu objpool from vmalloc"}, +}; + +struct ot_ctrl g_ot_miss[] = { + {0, NODE_COMPACT, 1000, 0, 16, 0, 0, "sync overrun: percpu objpool"}, + {0, NODE_VMALLOC, 1000, 0, 16, 0, 0, "sync overrun: percpu objpool from vmalloc"}, +}; + +struct ot_ctrl g_ot_async[] = { + {0, NODE_COMPACT, 1000, 4, 8, 8, 6, "async: percpu objpool"}, + {0, NODE_VMALLOC, 1000, 4, 8, 8, 6, "async: percpu objpool from vmalloc"}, +}; + +static int __init ot_mod_init(void) +{ + int i; + + ot_init_data(&g_ot_data); + + for (i = 0; i < ARRAY_SIZE(g_ot_sync); i++) { + if (ot_start_sync(&g_ot_sync[i])) + goto out; + ot_reset_data(&g_ot_data); + } + + for (i = 0; i < ARRAY_SIZE(g_ot_miss); i++) { + if (ot_start_sync(&g_ot_miss[i])) + goto out; + ot_reset_data(&g_ot_data); + } + + for (i = 0; i < ARRAY_SIZE(g_ot_async); i++) { + if (ot_start_async(&g_ot_async[i])) + goto out; + ot_reset_data(&g_ot_data); + } + +out: + return -EAGAIN; +} + +static void __exit ot_mod_exit(void) +{ +} + +module_init(ot_mod_init); +module_exit(ot_mod_exit); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Matt Wu"); From patchwork Sun Dec 18 05:03:08 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "wuqiang.matt" X-Patchwork-Id: 34285 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp1789573wrn; Sat, 17 Dec 2022 21:05:08 -0800 (PST) X-Google-Smtp-Source: AA0mqf4Q1UcxivkOvmAZEYvHIWt+qfDm1hrDSZZlycsDmaUTTHAMqFVq+mw1jT6p8RKFYZaX4WwZ X-Received: by 2002:a17:906:c014:b0:7ae:987d:d7f9 with SMTP id e20-20020a170906c01400b007ae987dd7f9mr33840626ejz.17.1671339907905; Sat, 17 Dec 2022 21:05:07 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1671339907; cv=none; d=google.com; s=arc-20160816; b=ix9GPGvvCmkdmB2sPjnAJJCUcuFpv14HlQqW0A5MckcBxsYig/7OIB//7I3QadEdCe Vf74Sc58Vb5l9p6S9QXXNE551H5pZJ/dLpqJ0AmLJg72FeiZhYD28Rg+dCiZxkyKrEwV H775EYygu8ktpjXE+oa2dp5/FU+tv4RZiF9gDNOZnMH62HPihQjC/mhkr/m2ZeA1SP34 B+l4Qdt6eUHRRDUBvA+fY3ATzs24fummDJarZkrLDTvPhGUp5KZhSBk+M2ISPjMAgaMF zTzgqD9+obQZeiSqxQc2mxCdzdAPjixJFF7btLu3FguNLgRYdcY1B0xzvVhvw0ErATqg fgPw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=qrOkKWPUXzcoHZUqv6wcsVbUmk6AKAdNuoB5NzSAgk8=; b=MrtsTr4+IEC0mw6DXmRT1OnmGD524JnLHW0IRwVfeXtwzHjQ0wiuA2M9t5VlPUYOOz 92zGxselWN0Jlet+BBNOPwt4Az3nmHhCjNCdpfrQvZZwvhsGRybTXULlGW9IQLsInjXP e6Tpx4rhKvGIr5jaZniWz/iOykSJRUkz6nP3ZW7uQSry8TmfK1DxXrxtKDOL297ozrLO B6xZQ29NzhyRLcTuorM0bicfehRVOETS6n9uytKdhhWXKKbtf5+XlkB+KpyTadsMRBCA zqM0aAnxr3kA4QrVW+p8v7b2NYzfEGdEab8Rn7QYLPEc4y952y0w7HnGJyxkVwBD7Jf2 dBjQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=tX3S7sOu; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id n11-20020a05640205cb00b00477e889f2a6si3123917edx.53.2022.12.17.21.04.39; Sat, 17 Dec 2022 21:05:07 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=tX3S7sOu; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229716AbiLRFEJ (ORCPT + 99 others); Sun, 18 Dec 2022 00:04:09 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50818 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230147AbiLRFEE (ORCPT ); Sun, 18 Dec 2022 00:04:04 -0500 Received: from mail-pl1-x630.google.com (mail-pl1-x630.google.com [IPv6:2607:f8b0:4864:20::630]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DD3E2DF54 for ; Sat, 17 Dec 2022 21:04:00 -0800 (PST) Received: by mail-pl1-x630.google.com with SMTP id x2so6031459plb.13 for ; Sat, 17 Dec 2022 21:04:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qrOkKWPUXzcoHZUqv6wcsVbUmk6AKAdNuoB5NzSAgk8=; b=tX3S7sOuJfnMU4xR7YlSnrVlH9o22FEQjU5zsr4Bhq5178LKLXvbZbFqUHgFeHIz7X G3BwuwsA9T72RmOJXqfJw8N6svostqquOLeFwMkaEoBGGgp8ZNEJ/XOHl/FymauagwXf zfYzm0musLSLk64Rw8qFlbGPyAra+jEFKhCIhilkU/Gr6efdqydLFHT0LEFabonqjr3o tJXKv2nnBP3q5hNWhbb2c+h7+/qplAIBM51fF60KMx3anLX4rk4hs02uWKj9B94pybIR H6NlaTgA96jvAdyMUMnID20/m/c2BLIBf0uO8hZdEoPqmZM/MjHiEH1hmuv/H3n//zYP /pXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qrOkKWPUXzcoHZUqv6wcsVbUmk6AKAdNuoB5NzSAgk8=; b=1IsPaZVj3H31o5GjOOErzX5RTASYcNe5y7azumisso2M+IpTF/1s7lfE0CH1YZgtH5 BSuC4sX2ngxdSbagQR/edgd+46NQlfjrLUfMzDsUK3A6ictOSHaIohR8GB4Lz1vOaRCJ GkNCnbeBULvqp09jOEyfIZN15b54YpRKv7jdGXc/nfFdnDL6woLg1XIIBusW5XN5j8E+ 0w/DIbqBDrEvHtKDJOOdDgtDZ2Gp62SclPGi3oaHC/BF8AuS/4Ki4+anF7ioAHuWKGX0 myxsR5Yk6NSIiwWeA1iQIsI6mZ5sDnohPR39Q9wnxWjWSSarfAyYbSP9Fq6zqA5DQslR cVdQ== X-Gm-Message-State: AFqh2kpD1q58eEY4v0/mLYzjrBBvp9uyN2zzthR92r/leKUF8DDUzPZK QOSthO024tbSzBSw2bS0H6v8EQ== X-Received: by 2002:a17:903:2154:b0:189:5a49:36c3 with SMTP id s20-20020a170903215400b001895a4936c3mr4151202ple.0.1671339840159; Sat, 17 Dec 2022 21:04:00 -0800 (PST) Received: from devtp.bytedance.net ([139.177.225.227]) by smtp.gmail.com with ESMTPSA id v20-20020a170902ca9400b001708c4ebbaesm4339348pld.309.2022.12.17.21.03.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Dec 2022 21:03:59 -0800 (PST) From: wuqiang To: mhiramat@kernel.org, davem@davemloft.net, anil.s.keshavamurthy@intel.com, naveen.n.rao@linux.ibm.com, rostedt@goodmis.org, peterz@infradead.org, akpm@linux-foundation.org, sander@svanheule.net, ebiggers@google.com, dan.j.williams@intel.com, jpoimboe@kernel.org Cc: linux-kernel@vger.kernel.org, lkp@intel.com, mattwu@163.com, wuqiang Subject: [PATCH v8 3/5] kprobes: kretprobe scalability improvement with objpool Date: Sun, 18 Dec 2022 13:03:08 +0800 Message-Id: <20221218050310.1338630-4-wuqiang.matt@bytedance.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> References: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1752526914962840885?= X-GMAIL-MSGID: =?utf-8?q?1752526914962840885?= kretprobe is using freelist to manage return-instances, but freelist, as LIFO queue based on singly linked list, scales badly and reduces the overall throughput of kretprobed routines, especially for high contention scenarios. Here's a typical throughput test of sys_flock (counts in 10 seconds, measured with perf stat -a -I 10000 -e syscalls:sys_enter_flock): OS: Debian 10 X86_64, Linux 6.1rc2 HW: XEON 8336C x 2, 64 cores/128 threads, DDR4 3200MT/s 1X 2X 4X 6X 8X 12X 16X 34762430 36546920 17949900 13101899 12569595 12646601 14729195 24X 32X 48X 64X 72X 96X 128X 19263546 10102064 8985418 11936495 11493980 7127789 9330985 This patch introduces objpool to kretprobe and rethook, with orginal freelist replaced and brings near-linear scalability to kretprobed routines. Tests of kretprobe throughput show the biggest ratio as 333.9x of the original freelist. Here's the comparison: 1X 2X 4X 8X 16X freelist: 34762430 36546920 17949900 12569595 14729195 objpool: 35627544 72182095 144068494 287564688 576903916 32X 48X 64X 96X 128X freelist: 10102064 8985418 11936495 7127789 9330985 objpool: 1158876372 1737828164 2324371724 2380310472 2463182819 Tests on 96-core ARM64 system output similarly, but with the biggest ratio up to 642.2x: OS: Debian 10 AARCH64, Linux 6.1rc2 HW: Kunpeng-920 96 cores/2 sockets/4 NUMA nodes, DDR4 2933 MT/s 1X 2X 4X 8X 16X freelist: 17498299 10887037 10224710 8499132 6421751 objpool: 18715726 35549845 71615884 144258971 283707220 24X 32X 48X 64X 96X freelist: 5339868 4819116 3593919 3121575 2687167 objpool: 419830913 571609748 877456139 1143316315 1725668029 Signed-off-by: wuqiang --- include/linux/kprobes.h | 11 ++--- include/linux/rethook.h | 16 ++----- kernel/kprobes.c | 93 +++++++++++++++++------------------------ kernel/trace/fprobe.c | 37 +++++++--------- kernel/trace/rethook.c | 91 ++++++++++++++++++---------------------- 5 files changed, 101 insertions(+), 147 deletions(-) diff --git a/include/linux/kprobes.h b/include/linux/kprobes.h index a0b92be98984..b1452a9734f7 100644 --- a/include/linux/kprobes.h +++ b/include/linux/kprobes.h @@ -26,8 +26,7 @@ #include #include #include -#include -#include +#include #include #include @@ -141,7 +140,7 @@ static inline bool kprobe_ftrace(struct kprobe *p) */ struct kretprobe_holder { struct kretprobe *rp; - refcount_t ref; + struct objpool_head pool; }; struct kretprobe { @@ -154,7 +153,6 @@ struct kretprobe { #ifdef CONFIG_KRETPROBE_ON_RETHOOK struct rethook *rh; #else - struct freelist_head freelist; struct kretprobe_holder *rph; #endif }; @@ -165,10 +163,7 @@ struct kretprobe_instance { #ifdef CONFIG_KRETPROBE_ON_RETHOOK struct rethook_node node; #else - union { - struct freelist_node freelist; - struct rcu_head rcu; - }; + struct rcu_head rcu; struct llist_node llist; struct kretprobe_holder *rph; kprobe_opcode_t *ret_addr; diff --git a/include/linux/rethook.h b/include/linux/rethook.h index c8ac1e5afcd1..ec5f186cf203 100644 --- a/include/linux/rethook.h +++ b/include/linux/rethook.h @@ -6,11 +6,10 @@ #define _LINUX_RETHOOK_H #include -#include +#include #include #include #include -#include struct rethook_node; @@ -30,14 +29,12 @@ typedef void (*rethook_handler_t) (struct rethook_node *, void *, struct pt_regs struct rethook { void *data; rethook_handler_t handler; - struct freelist_head pool; - refcount_t ref; + struct objpool_head pool; struct rcu_head rcu; }; /** * struct rethook_node - The rethook shadow-stack entry node. - * @freelist: The freelist, linked to struct rethook::pool. * @rcu: The rcu_head for deferred freeing. * @llist: The llist, linked to a struct task_struct::rethooks. * @rethook: The pointer to the struct rethook. @@ -48,19 +45,15 @@ struct rethook { * on each entry of the shadow stack. */ struct rethook_node { - union { - struct freelist_node freelist; - struct rcu_head rcu; - }; + struct rcu_head rcu; struct llist_node llist; struct rethook *rethook; unsigned long ret_addr; unsigned long frame; }; -struct rethook *rethook_alloc(void *data, rethook_handler_t handler); +struct rethook *rethook_alloc(void *data, rethook_handler_t handler, int size, int num); void rethook_free(struct rethook *rh); -void rethook_add_node(struct rethook *rh, struct rethook_node *node); struct rethook_node *rethook_try_get(struct rethook *rh); void rethook_recycle(struct rethook_node *node); void rethook_hook(struct rethook_node *node, struct pt_regs *regs, bool mcount); @@ -97,4 +90,3 @@ void rethook_flush_task(struct task_struct *tk); #endif #endif - diff --git a/kernel/kprobes.c b/kernel/kprobes.c index 3050631e528d..497fe18755d7 100644 --- a/kernel/kprobes.c +++ b/kernel/kprobes.c @@ -1868,13 +1868,27 @@ static struct notifier_block kprobe_exceptions_nb = { #ifdef CONFIG_KRETPROBES #if !defined(CONFIG_KRETPROBE_ON_RETHOOK) + +/* callbacks for objpool of kretprobe instances */ +static int kretprobe_init_inst(void *nod, void *context) +{ + struct kretprobe_instance *ri = nod; + + ri->rph = context; + return 0; +} +static int kretprobe_fini_pool(struct objpool_head *head, void *context) +{ + kfree(context); + return 0; +} + static void free_rp_inst_rcu(struct rcu_head *head) { struct kretprobe_instance *ri = container_of(head, struct kretprobe_instance, rcu); + struct kretprobe_holder *rph = ri->rph; - if (refcount_dec_and_test(&ri->rph->ref)) - kfree(ri->rph); - kfree(ri); + objpool_drop(ri, &rph->pool); } NOKPROBE_SYMBOL(free_rp_inst_rcu); @@ -1883,7 +1897,7 @@ static void recycle_rp_inst(struct kretprobe_instance *ri) struct kretprobe *rp = get_kretprobe(ri); if (likely(rp)) - freelist_add(&ri->freelist, &rp->freelist); + objpool_push(ri, &rp->rph->pool); else call_rcu(&ri->rcu, free_rp_inst_rcu); } @@ -1920,23 +1934,12 @@ NOKPROBE_SYMBOL(kprobe_flush_task); static inline void free_rp_inst(struct kretprobe *rp) { - struct kretprobe_instance *ri; - struct freelist_node *node; - int count = 0; - - node = rp->freelist.head; - while (node) { - ri = container_of(node, struct kretprobe_instance, freelist); - node = node->next; - - kfree(ri); - count++; - } + struct kretprobe_holder *rph = rp->rph; - if (refcount_sub_and_test(count, &rp->rph->ref)) { - kfree(rp->rph); - rp->rph = NULL; - } + if (!rph) + return; + rp->rph = NULL; + objpool_fini(&rph->pool); } /* This assumes the 'tsk' is the current task or the is not running. */ @@ -2078,19 +2081,17 @@ NOKPROBE_SYMBOL(__kretprobe_trampoline_handler) static int pre_handler_kretprobe(struct kprobe *p, struct pt_regs *regs) { struct kretprobe *rp = container_of(p, struct kretprobe, kp); + struct kretprobe_holder *rph = rp->rph; struct kretprobe_instance *ri; - struct freelist_node *fn; - fn = freelist_try_get(&rp->freelist); - if (!fn) { + ri = objpool_pop(&rph->pool); + if (!ri) { rp->nmissed++; return 0; } - ri = container_of(fn, struct kretprobe_instance, freelist); - if (rp->entry_handler && rp->entry_handler(ri, regs)) { - freelist_add(&ri->freelist, &rp->freelist); + objpool_push(ri, &rph->pool); return 0; } @@ -2183,7 +2184,6 @@ int kprobe_on_func_entry(kprobe_opcode_t *addr, const char *sym, unsigned long o int register_kretprobe(struct kretprobe *rp) { int ret; - struct kretprobe_instance *inst; int i; void *addr; @@ -2221,20 +2221,12 @@ int register_kretprobe(struct kretprobe *rp) #endif } #ifdef CONFIG_KRETPROBE_ON_RETHOOK - rp->rh = rethook_alloc((void *)rp, kretprobe_rethook_handler); - if (!rp->rh) - return -ENOMEM; + rp->rh = rethook_alloc((void *)rp, kretprobe_rethook_handler, + sizeof(struct kretprobe_instance) + + rp->data_size, rp->maxactive); + if (IS_ERR(rp->rh)) + return PTR_ERR(rp->rh); - for (i = 0; i < rp->maxactive; i++) { - inst = kzalloc(sizeof(struct kretprobe_instance) + - rp->data_size, GFP_KERNEL); - if (inst == NULL) { - rethook_free(rp->rh); - rp->rh = NULL; - return -ENOMEM; - } - rethook_add_node(rp->rh, &inst->node); - } rp->nmissed = 0; /* Establish function entry probe point */ ret = register_kprobe(&rp->kp); @@ -2243,25 +2235,18 @@ int register_kretprobe(struct kretprobe *rp) rp->rh = NULL; } #else /* !CONFIG_KRETPROBE_ON_RETHOOK */ - rp->freelist.head = NULL; rp->rph = kzalloc(sizeof(struct kretprobe_holder), GFP_KERNEL); if (!rp->rph) return -ENOMEM; - rp->rph->rp = rp; - for (i = 0; i < rp->maxactive; i++) { - inst = kzalloc(sizeof(struct kretprobe_instance) + - rp->data_size, GFP_KERNEL); - if (inst == NULL) { - refcount_set(&rp->rph->ref, i); - free_rp_inst(rp); - return -ENOMEM; - } - inst->rph = rp->rph; - freelist_add(&inst->freelist, &rp->freelist); + if (objpool_init(&rp->rph->pool, rp->maxactive, rp->data_size + + sizeof(struct kretprobe_instance), GFP_KERNEL, + rp->rph, kretprobe_init_inst, kretprobe_fini_pool)) { + kfree(rp->rph); + rp->rph = NULL; + return -ENOMEM; } - refcount_set(&rp->rph->ref, i); - + rp->rph->rp = rp; rp->nmissed = 0; /* Establish function entry probe point */ ret = register_kprobe(&rp->kp); diff --git a/kernel/trace/fprobe.c b/kernel/trace/fprobe.c index e8143e368074..9b685d6921d1 100644 --- a/kernel/trace/fprobe.c +++ b/kernel/trace/fprobe.c @@ -125,41 +125,32 @@ static void fprobe_init(struct fprobe *fp) static int fprobe_init_rethook(struct fprobe *fp, int num) { - int i, size; - - if (num < 0) - return -EINVAL; + int max; if (!fp->exit_handler) { fp->rethook = NULL; return 0; } - /* Initialize rethook if needed */ - size = num * num_possible_cpus() * 2; - if (size < 0) + if (num <= 0) + return -EINVAL; + max = num * num_possible_cpus() * 2; + /* Fail if max overflows */ + if (max <= 0) return -E2BIG; - fp->rethook = rethook_alloc((void *)fp, fprobe_exit_handler); - if (!fp->rethook) - return -ENOMEM; - for (i = 0; i < size; i++) { - struct fprobe_rethook_node *node; - - node = kzalloc(sizeof(*node), GFP_KERNEL); - if (!node) { - rethook_free(fp->rethook); - fp->rethook = NULL; - return -ENOMEM; - } - rethook_add_node(fp->rethook, &node->node); - } + /* Initialize rethook */ + fp->rethook = rethook_alloc((void *)fp, fprobe_exit_handler, + sizeof(struct fprobe_rethook_node), max); + if (IS_ERR(fp->rethook)) + return PTR_ERR(fp->rethook); + return 0; } static void fprobe_fail_cleanup(struct fprobe *fp) { - if (fp->rethook) { + if (!IS_ERR_OR_NULL(fp->rethook)) { /* Don't need to cleanup rethook->handler because this is not used. */ rethook_free(fp->rethook); fp->rethook = NULL; @@ -313,7 +304,7 @@ int unregister_fprobe(struct fprobe *fp) * current running handlers are finished, call unregister_ftrace_function() * after this. */ - if (fp->rethook) + if (!IS_ERR_OR_NULL(fp->rethook)) rethook_free(fp->rethook); ret = unregister_ftrace_function(&fp->ops); diff --git a/kernel/trace/rethook.c b/kernel/trace/rethook.c index 32c3dfdb4d6a..ba069bf9be75 100644 --- a/kernel/trace/rethook.c +++ b/kernel/trace/rethook.c @@ -9,6 +9,7 @@ #include #include #include +#include /* Return hook list (shadow stack by list) */ @@ -36,21 +37,7 @@ void rethook_flush_task(struct task_struct *tk) static void rethook_free_rcu(struct rcu_head *head) { struct rethook *rh = container_of(head, struct rethook, rcu); - struct rethook_node *rhn; - struct freelist_node *node; - int count = 1; - - node = rh->pool.head; - while (node) { - rhn = container_of(node, struct rethook_node, freelist); - node = node->next; - kfree(rhn); - count++; - } - - /* The rh->ref is the number of pooled node + 1 */ - if (refcount_sub_and_test(count, &rh->ref)) - kfree(rh); + objpool_fini(&rh->pool); } /** @@ -70,54 +57,63 @@ void rethook_free(struct rethook *rh) call_rcu(&rh->rcu, rethook_free_rcu); } +static int rethook_init_node(void *nod, void *context) +{ + struct rethook_node *node = nod; + + node->rethook = context; + return 0; +} + +static int rethook_fini_pool(struct objpool_head *head, void *context) +{ + kfree(context); + return 0; +} + /** * rethook_alloc() - Allocate struct rethook. * @data: a data to pass the @handler when hooking the return. - * @handler: the return hook callback function. + * @handler: the return hook callback function, must NOT be NULL + * @gfp: default gfp for objpool allocation + * @size: node size: rethook node and additional data + * @num: number of rethook nodes to be preallocated * * Allocate and initialize a new rethook with @data and @handler. - * Return NULL if memory allocation fails or @handler is NULL. + * Return pointer of new rethook, or error codes for failures. + * * Note that @handler == NULL means this rethook is going to be freed. */ -struct rethook *rethook_alloc(void *data, rethook_handler_t handler) +struct rethook *rethook_alloc(void *data, rethook_handler_t handler, + int size, int num) { - struct rethook *rh = kzalloc(sizeof(struct rethook), GFP_KERNEL); + struct rethook *rh; - if (!rh || !handler) { - kfree(rh); - return NULL; - } + if (!handler || num <= 0 || size < sizeof(struct rethook_node)) + return ERR_PTR(-EINVAL); + + rh = kzalloc(sizeof(struct rethook), GFP_KERNEL); + if (!rh) + return ERR_PTR(-ENOMEM); rh->data = data; rh->handler = handler; - rh->pool.head = NULL; - refcount_set(&rh->ref, 1); + /* initialize the objpool for rethook nodes */ + if (objpool_init(&rh->pool, num, size, GFP_KERNEL, rh, + rethook_init_node, rethook_fini_pool)) { + kfree(rh); + return ERR_PTR(-ENOMEM); + } return rh; } -/** - * rethook_add_node() - Add a new node to the rethook. - * @rh: the struct rethook. - * @node: the struct rethook_node to be added. - * - * Add @node to @rh. User must allocate @node (as a part of user's - * data structure.) The @node fields are initialized in this function. - */ -void rethook_add_node(struct rethook *rh, struct rethook_node *node) -{ - node->rethook = rh; - freelist_add(&node->freelist, &rh->pool); - refcount_inc(&rh->ref); -} - static void free_rethook_node_rcu(struct rcu_head *head) { struct rethook_node *node = container_of(head, struct rethook_node, rcu); + struct rethook *rh = node->rethook; - if (refcount_dec_and_test(&node->rethook->ref)) - kfree(node->rethook); - kfree(node); + objpool_drop(node, &rh->pool); } /** @@ -132,7 +128,7 @@ void rethook_recycle(struct rethook_node *node) lockdep_assert_preemption_disabled(); if (likely(READ_ONCE(node->rethook->handler))) - freelist_add(&node->freelist, &node->rethook->pool); + objpool_push(node, &node->rethook->pool); else call_rcu(&node->rcu, free_rethook_node_rcu); } @@ -148,7 +144,6 @@ NOKPROBE_SYMBOL(rethook_recycle); struct rethook_node *rethook_try_get(struct rethook *rh) { rethook_handler_t handler = READ_ONCE(rh->handler); - struct freelist_node *fn; lockdep_assert_preemption_disabled(); @@ -165,11 +160,7 @@ struct rethook_node *rethook_try_get(struct rethook *rh) if (unlikely(!rcu_is_watching())) return NULL; - fn = freelist_try_get(&rh->pool); - if (!fn) - return NULL; - - return container_of(fn, struct rethook_node, freelist); + return (struct rethook_node *)objpool_pop(&rh->pool); } NOKPROBE_SYMBOL(rethook_try_get); From patchwork Sun Dec 18 05:03:09 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "wuqiang.matt" X-Patchwork-Id: 34288 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp1791924wrn; Sat, 17 Dec 2022 21:16:36 -0800 (PST) X-Google-Smtp-Source: AA0mqf5JN743w+X8FaUyAfC9H+/Mm+7sInRPzx5zYLtSRHbHLO2txzDqO0HKvLlOjc/Ts1081KTw X-Received: by 2002:a62:19c6:0:b0:576:cd93:2b06 with SMTP id 189-20020a6219c6000000b00576cd932b06mr37915046pfz.6.1671340596316; Sat, 17 Dec 2022 21:16:36 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1671340596; cv=none; d=google.com; s=arc-20160816; b=0jiZQQ28qEyG+QKOM3okTZqVZV89v5CPd12gN11VXdEiqUwn8yUPGwMnAXqMowe2XU yHgNa8xxiD4D4uDkJWu4SCUiwGHP+IA5M58ACibiNW620nKhbAAnxDY1VJjHfz2zXAql sq3fLmnnqQrubuRO13BsuXo1Uj4OXJ3alMeoVfQTtrxYDLZRd4lgFB2nXLlafC+KrPvY lDnqKMrH1Y8yB5KCU+Uwe+wmFRpcV2yY+gE3JmOEavvM53Feo6oRcShBFQhYRNHy18Lg 5dnI7fPWESpdO+lyfq1hKNcE+qV8f2aUaXvVKNtByzbDaPnJJs2rmysOzcdZgYPoko3q Wudw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=OkVJDMV1dLbnY0a97cBJ8dALMRcKW3eBADQn81KDV+U=; b=WeJaKtPpNG95308H4hsIYo1nQeNYsmHccwYWgJIl7Du9TB1j3htbVS34AIeF2w5x17 QkphFmdPFUc4KlqKvlkw4Qc3baEbR1Yfc6g+xueUMsalNT9VKR3LH9xJKCcfCUxKP3bG M2Kf6m/XYn+ge0LxlQjMyyX63/ruouqBneYL2C5jWjLMsiyS25Nl+1DWbaSCFoG6R9yf iphMb12FmpYqmZd//qG5k095vriCO30C1peqWJq9LhRyfCrLExMYH20wmivzG8K4i66J VJkJ+eWQnE10Ny+j4nLhUTSbABWU2TqHLg8l271ff1OV7Lrqzh8EKTd0f/usVqH5TFwM 71Tw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=oyVXGSBf; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id o3-20020a056a001bc300b00572d3b2ed93si6350281pfw.139.2022.12.17.21.16.21; Sat, 17 Dec 2022 21:16:36 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=oyVXGSBf; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230316AbiLRFFJ (ORCPT + 99 others); Sun, 18 Dec 2022 00:05:09 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50890 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230230AbiLRFEc (ORCPT ); Sun, 18 Dec 2022 00:04:32 -0500 Received: from mail-pj1-x102a.google.com (mail-pj1-x102a.google.com [IPv6:2607:f8b0:4864:20::102a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 79A41DEAD for ; Sat, 17 Dec 2022 21:04:07 -0800 (PST) Received: by mail-pj1-x102a.google.com with SMTP id o12so6118316pjo.4 for ; Sat, 17 Dec 2022 21:04:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=OkVJDMV1dLbnY0a97cBJ8dALMRcKW3eBADQn81KDV+U=; b=oyVXGSBfQ66N/vpiNxVgFLg9BI1lff6swGj32icd6FZI8eLgtvfwoQFYVXSOtNpWNF PHooMjjc2xUCxPK03BcUhC6Dt194C7f1n0xbkBQHKu7QU4I56YMsKMsIcQQ1w1VawMtV ZOaavZta9+n5GOE9kM6HnqwYQ7SfOB/chu7QOvmCzX1gLTsDPI88vlqNFizyVQdRXMC9 JQh8AH1kUa7JFxQQ2XVszNAyLi0bAe5Mj6W0ZU3kfaoPgFa3lSA31VzUDNzldSylmXqm tfnDvH2Db+NaFmEpPA9Xlgv4TeHGZdNoM5iiCYQDcdzNM5uRfWgVUuCAz9U60vv9+UxV xvEg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=OkVJDMV1dLbnY0a97cBJ8dALMRcKW3eBADQn81KDV+U=; b=wQ7aHz2SfNywC20AuDmqyMPaF8bXmgNIZ25pTaCCXN5ZlNjEksxoUql4RG4SKDVNTW 2ixs0DxgifkjbXea65cQwPh3qHQ3L3/1b0LAsXjjS81ZBx9+FdHP8r1lpy47T7spN5IL pP1wpPW3rdqyLI1H/mysIz+wzKejdmmzcD02lKIcw5P5lKOMlp/Y0hYdZrpRxeREDJMn 4QrC6v7PEmkQpd7dZEHQ7LhV9VsQj8EeN6LIjoZiQsp6wpm4GFuFAmGr7Ty5gnlU4jNC 36S8Zy+c4FtOdNsc/oRsHC/NUtAquaGaLlu98w8QztRDpl0UTI4pD1BfWzuLx3f9aiac /sQg== X-Gm-Message-State: ANoB5pmX6wmA1Dg3L9Ge8TUAgqBOgNyqxWSQnDjMHoEufSZM5Bes974O M9UbJqwgtcSilL/TTqdACGCf3g== X-Received: by 2002:a17:902:d18c:b0:189:df3c:1ba1 with SMTP id m12-20020a170902d18c00b00189df3c1ba1mr34790233plb.38.1671339847179; Sat, 17 Dec 2022 21:04:07 -0800 (PST) Received: from devtp.bytedance.net ([139.177.225.227]) by smtp.gmail.com with ESMTPSA id v20-20020a170902ca9400b001708c4ebbaesm4339348pld.309.2022.12.17.21.04.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Dec 2022 21:04:06 -0800 (PST) From: wuqiang To: mhiramat@kernel.org, davem@davemloft.net, anil.s.keshavamurthy@intel.com, naveen.n.rao@linux.ibm.com, rostedt@goodmis.org, peterz@infradead.org, akpm@linux-foundation.org, sander@svanheule.net, ebiggers@google.com, dan.j.williams@intel.com, jpoimboe@kernel.org Cc: linux-kernel@vger.kernel.org, lkp@intel.com, mattwu@163.com, wuqiang Subject: [PATCH v8 4/5] kprobes: freelist.h removed Date: Sun, 18 Dec 2022 13:03:09 +0800 Message-Id: <20221218050310.1338630-5-wuqiang.matt@bytedance.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> References: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1752527637428196812?= X-GMAIL-MSGID: =?utf-8?q?1752527637428196812?= This patch will remove freelist.h from kernel source tree, since the only use cases (kretprobe and rethook) are converted to objpool. Signed-off-by: wuqiang --- include/linux/freelist.h | 129 --------------------------------------- 1 file changed, 129 deletions(-) delete mode 100644 include/linux/freelist.h diff --git a/include/linux/freelist.h b/include/linux/freelist.h deleted file mode 100644 index fc1842b96469..000000000000 --- a/include/linux/freelist.h +++ /dev/null @@ -1,129 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-only OR BSD-2-Clause */ -#ifndef FREELIST_H -#define FREELIST_H - -#include - -/* - * Copyright: cameron@moodycamel.com - * - * A simple CAS-based lock-free free list. Not the fastest thing in the world - * under heavy contention, but simple and correct (assuming nodes are never - * freed until after the free list is destroyed), and fairly speedy under low - * contention. - * - * Adapted from: https://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists - */ - -struct freelist_node { - atomic_t refs; - struct freelist_node *next; -}; - -struct freelist_head { - struct freelist_node *head; -}; - -#define REFS_ON_FREELIST 0x80000000 -#define REFS_MASK 0x7FFFFFFF - -static inline void __freelist_add(struct freelist_node *node, struct freelist_head *list) -{ - /* - * Since the refcount is zero, and nobody can increase it once it's - * zero (except us, and we run only one copy of this method per node at - * a time, i.e. the single thread case), then we know we can safely - * change the next pointer of the node; however, once the refcount is - * back above zero, then other threads could increase it (happens under - * heavy contention, when the refcount goes to zero in between a load - * and a refcount increment of a node in try_get, then back up to - * something non-zero, then the refcount increment is done by the other - * thread) -- so if the CAS to add the node to the actual list fails, - * decrese the refcount and leave the add operation to the next thread - * who puts the refcount back to zero (which could be us, hence the - * loop). - */ - struct freelist_node *head = READ_ONCE(list->head); - - for (;;) { - WRITE_ONCE(node->next, head); - atomic_set_release(&node->refs, 1); - - if (!try_cmpxchg_release(&list->head, &head, node)) { - /* - * Hmm, the add failed, but we can only try again when - * the refcount goes back to zero. - */ - if (atomic_fetch_add_release(REFS_ON_FREELIST - 1, &node->refs) == 1) - continue; - } - return; - } -} - -static inline void freelist_add(struct freelist_node *node, struct freelist_head *list) -{ - /* - * We know that the should-be-on-freelist bit is 0 at this point, so - * it's safe to set it using a fetch_add. - */ - if (!atomic_fetch_add_release(REFS_ON_FREELIST, &node->refs)) { - /* - * Oh look! We were the last ones referencing this node, and we - * know we want to add it to the free list, so let's do it! - */ - __freelist_add(node, list); - } -} - -static inline struct freelist_node *freelist_try_get(struct freelist_head *list) -{ - struct freelist_node *prev, *next, *head = smp_load_acquire(&list->head); - unsigned int refs; - - while (head) { - prev = head; - refs = atomic_read(&head->refs); - if ((refs & REFS_MASK) == 0 || - !atomic_try_cmpxchg_acquire(&head->refs, &refs, refs+1)) { - head = smp_load_acquire(&list->head); - continue; - } - - /* - * Good, reference count has been incremented (it wasn't at - * zero), which means we can read the next and not worry about - * it changing between now and the time we do the CAS. - */ - next = READ_ONCE(head->next); - if (try_cmpxchg_acquire(&list->head, &head, next)) { - /* - * Yay, got the node. This means it was on the list, - * which means should-be-on-freelist must be false no - * matter the refcount (because nobody else knows it's - * been taken off yet, it can't have been put back on). - */ - WARN_ON_ONCE(atomic_read(&head->refs) & REFS_ON_FREELIST); - - /* - * Decrease refcount twice, once for our ref, and once - * for the list's ref. - */ - atomic_fetch_add(-2, &head->refs); - - return head; - } - - /* - * OK, the head must have changed on us, but we still need to decrement - * the refcount we increased. - */ - refs = atomic_fetch_add(-1, &prev->refs); - if (refs == REFS_ON_FREELIST + 1) - __freelist_add(prev, list); - } - - return NULL; -} - -#endif /* FREELIST_H */ From patchwork Sun Dec 18 05:03:10 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "wuqiang.matt" X-Patchwork-Id: 34287 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:e747:0:0:0:0:0 with SMTP id c7csp1789869wrn; Sat, 17 Dec 2022 21:06:33 -0800 (PST) X-Google-Smtp-Source: AA0mqf5ESOwm9UElLHOEktzpaTHqDL9qsKSOjdIAdIaEzPAuH8PQvry5x4E8RSTfuiH03aTQzLls X-Received: by 2002:a17:906:804b:b0:7c1:67ca:56f5 with SMTP id x11-20020a170906804b00b007c167ca56f5mr22633500ejw.15.1671339992881; Sat, 17 Dec 2022 21:06:32 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1671339992; cv=none; d=google.com; s=arc-20160816; b=OkZ4560FbQehE7kD5IS4sAg+8h5CrgOA1MtVxuU/AjAoETHTlwIJIxRwlVu01QDbr/ NAfTAJ+eY8nWvjwZz05GMlg32Ek+W6ghxwPyob9JQ6h5SPBZS7pwOF2rSaTjcZA8wkj0 DClkM7G0wzYjG8ECZXcdNJo/apWezi4p1J1RRyPsPdUzwSY4KBNoj7gX+9WmP4Zn+ab3 dzweW6wHdfNU9WJqUczA5BgEp6NJfhSiS4isZzuvyqrYthRCfBjp2nbHY1YK08dtslqu xXneEy4xt/aqLGJGhqMXeHWzO9VvRcI0FIS4a9Z7snC3BE6U5y8Fx43S5lbI0VYffV37 9noQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=f+8uGGe5vOHJy+eJbczvZUafBVT7vGqMpKgjkjdLPuI=; b=y6sPCpfhsit6Oqpko8OE98a1PsOvU42DoXuZ0T/ZM80Hw21WnHwVyw+qtqYuIgY4V+ beE4QVssY35eKW/F2AWSppObEsFT+jC3kyr+dDWibF4xxf4kTr6rQnm+cWR9wL78x4rn BdebPm+JmFtdMamK75oDLNWbqZclIKTj+XO/HhkupvMlCux0FfENFZrGhKmTVsGOM1KH tuY1/WWCMXsmeh3uMNhqY6RYwjrWYAjwiIT0hgpukOFvV1rdkoYL5LTNnlstDjZyim+j ZH4ClB7VS5g9BV5DygjGPOuGSxxDx3xrBXN428FKMzE012U9ouJgT7gGC7h/TPhajs5Q 33Rg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=AUG89S3j; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id jg3-20020a170907970300b007f5e85a453asi3855339ejc.354.2022.12.17.21.06.10; Sat, 17 Dec 2022 21:06:32 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=AUG89S3j; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230089AbiLRFE3 (ORCPT + 99 others); Sun, 18 Dec 2022 00:04:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50956 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230170AbiLRFEP (ORCPT ); Sun, 18 Dec 2022 00:04:15 -0500 Received: from mail-pl1-x635.google.com (mail-pl1-x635.google.com [IPv6:2607:f8b0:4864:20::635]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 670BDDF54 for ; Sat, 17 Dec 2022 21:04:14 -0800 (PST) Received: by mail-pl1-x635.google.com with SMTP id m4so6083044pls.4 for ; Sat, 17 Dec 2022 21:04:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=f+8uGGe5vOHJy+eJbczvZUafBVT7vGqMpKgjkjdLPuI=; b=AUG89S3jopByrFoGln5MN2jF636XiStemIMcMCSuWk6oMNg9iO5UueelIFV1njqVHI 8xNZEK61XzIFE2aWXLg7XVYQC1MaKdi04PvGO8eEWf5i0agL+phx0a/uzwxqJ2TJTgwH AycuZtmDn3/WjVykXDC1dg5Mberq7kxe2g/BlX3iT/qih/EOb9StiFbVsITj++WLdqKi HJ/OQx8/vocQ0oOZqlOUc+f52B4lnLYMNRCSivjeLzqjt81UXIlt1PyO/OvGS6g157/0 toRr2GFIHeXC5KeT/KPDcr04xRb8r9YktQ5di2tIWEFfiODOoieEoMEsf6vTWIepEr8P /N9Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=f+8uGGe5vOHJy+eJbczvZUafBVT7vGqMpKgjkjdLPuI=; b=Gi7w3zHrf80xQk1bdTuMZ7anxOZ+QWBgT7cTj6HJh1VQYgPoIMoRw78VwmKLVXaUEN xtUu2tPEIRCBaKwc2m+DyU7WrlmyO1rDBGzkmXK/VxB/FoDC04hfkiyguKTLug0GRAla Py6oe+GgMnTdPELrNl2Yt+jbKbnBahbCKgHH/8hS1Qwt5Z4+BJBJy4T315pLH89lOxu1 NiODpZ2woXCW0khLuuCSPQrt+Su9qWuQeO8FDvDgVxXViqwU48AmqzLCSskN2/855N/Z BPWgu02h3wm4FCOcUjLri3BnkLN0Lbgz94nUioUhLHW4677/CNESdUMMnAjRSdxOuFkW hSYw== X-Gm-Message-State: ANoB5pmZFA9v4LD5PQM4YWuBK9sazh0AG0PPY1SzL6wI5oAohNNvUSjG zCVx2eXasyQQNBAhzbz3mwLekyzsueczuNbt X-Received: by 2002:a05:6a21:9212:b0:9f:2dd1:c2bc with SMTP id tl18-20020a056a21921200b0009f2dd1c2bcmr47116953pzb.49.1671339853827; Sat, 17 Dec 2022 21:04:13 -0800 (PST) Received: from devtp.bytedance.net ([139.177.225.227]) by smtp.gmail.com with ESMTPSA id v20-20020a170902ca9400b001708c4ebbaesm4339348pld.309.2022.12.17.21.04.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Dec 2022 21:04:13 -0800 (PST) From: wuqiang To: mhiramat@kernel.org, davem@davemloft.net, anil.s.keshavamurthy@intel.com, naveen.n.rao@linux.ibm.com, rostedt@goodmis.org, peterz@infradead.org, akpm@linux-foundation.org, sander@svanheule.net, ebiggers@google.com, dan.j.williams@intel.com, jpoimboe@kernel.org Cc: linux-kernel@vger.kernel.org, lkp@intel.com, mattwu@163.com, wuqiang Subject: [PATCH v8 5/5] MAINTAINERS: objpool added Date: Sun, 18 Dec 2022 13:03:10 +0800 Message-Id: <20221218050310.1338630-6-wuqiang.matt@bytedance.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> References: <20221218050310.1338630-1-wuqiang.matt@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1752527004537049132?= X-GMAIL-MSGID: =?utf-8?q?1752527004537049132?= ojbpool, a scalable and lockless ring-array based object pool, was introduced to replace the original freelist (a LIFO queue based on singly linked list) to improve kretprobe scalability. Signed-off-by: wuqiang --- MAINTAINERS | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index 886d3f69ee64..9584aa440eb9 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -14914,6 +14914,13 @@ F: include/linux/objagg.h F: lib/objagg.c F: lib/test_objagg.c +OBJPOOL +M: Matt Wu +S: Supported +F: include/linux/objpool.h +F: lib/objpool.c +F: lib/test_objpool.c + OBJTOOL M: Josh Poimboeuf M: Peter Zijlstra