From patchwork Mon Nov 20 17:47:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: andrey.konovalov@linux.dev X-Patchwork-Id: 167325 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:612c:2b07:b0:403:3b70:6f57 with SMTP id io7csp106978vqb; Mon, 20 Nov 2023 09:50:19 -0800 (PST) X-Google-Smtp-Source: AGHT+IEpYBsERedkgfgj65NV/09FvRzucG5TYJIk5oyYELQyhUlf2HwrfQNr52HAvE8/vcjDAQvH X-Received: by 2002:a05:6a20:9589:b0:189:f8bc:71a3 with SMTP id iu9-20020a056a20958900b00189f8bc71a3mr4827283pzb.37.1700502619366; Mon, 20 Nov 2023 09:50:19 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1700502619; cv=none; d=google.com; s=arc-20160816; b=EYjI1Kj9E5qWo4OEDP5OoP1h1Ukvwp/bV2vTVbHu4QeJvgfBPHNUIUcSpFwhjwlMQg Jcq6W6Tr7ddyPYljvk8Nhp3XDJaBAU1A5WgIWSvhj4RzvvvK+sfVAXKvR3kEB8ghuHe9 n9EJFNzcNWW6XRVyl7d2o+fMJDaZSP6wTdSp1w0QUYnQM/OeY5ytRW7Q1ReCTq+3GVb2 fzeN3xRqI0HeyarZVMHxfccitczU+xewuxypkrzEInGtPh6Ip3ELtzuNX93rshaVYa5P MUl+NEnHTDS90zTI249WFklHujn7oue2RMDuucoIpdwkhpa5dwz4Fp42V2fwU1NYFld7 hkzA== 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=JJPmOktxCpdhFxDsq8sCddRT3Qn7jxR2DhkERqO3NMk=; fh=qWoxmPN1zRqnLSoCWGpfFsDtzJsx/SGdqx98lbP+Uho=; b=YxLFUvKhAnLno6iqiJ34UYLNPstmk3BVCWN/q/Gg0iASA7Y1pm+mT9J5mNxB9DY260 VMmMJETacjp3lVA3AXIxMeWqzMtB2a1OUhRylJfkLU86Fx24nM+ucRaixBMurrfh6Bqm iUQ+f91Q7mdxTw7rAM1k92KybBBTT9eehTQceBNcxSCIyPQlYHLBkbEMr5pwkNcQu4DZ dZEL3zesNcEjcpQrHezmQE3vip6THFj14qKlwYBSjn8U+zS3hxdPxoAXRhwez7x2G7m2 WUlNVVNNeq6S4C3rwXSJpKIJY1XdPDxqQK5jPWDeu5RzUSLW4T3aDY28SSsDrNdndh/W jDrQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=Ru67pJEW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: from snail.vger.email (snail.vger.email. [2620:137:e000::3:7]) by mx.google.com with ESMTPS id d10-20020a056a00244a00b006c4d1f10b8asi8670760pfj.99.2023.11.20.09.50.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Nov 2023 09:50:19 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7; Authentication-Results: mx.google.com; dkim=pass header.i=@linux.dev header.s=key1 header.b=Ru67pJEW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linux.dev Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id 71F9180FA85B; Mon, 20 Nov 2023 09:50:18 -0800 (PST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.11 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234545AbjKTRuN (ORCPT + 27 others); Mon, 20 Nov 2023 12:50:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49320 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234599AbjKTRtt (ORCPT ); Mon, 20 Nov 2023 12:49:49 -0500 Received: from out-189.mta0.migadu.com (out-189.mta0.migadu.com [IPv6:2001:41d0:1004:224b::bd]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8E2E610D5 for ; Mon, 20 Nov 2023 09:49:39 -0800 (PST) X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1700502578; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=JJPmOktxCpdhFxDsq8sCddRT3Qn7jxR2DhkERqO3NMk=; b=Ru67pJEW7nzqb9rpO9yuZYxURTiycM1daQ55M4avqe1G86/dIuZUOw3dlKb408oXGg6x5O JLJSygolUyzo1EhZYq8z5/W03AxWgm/1aMH2K0UPV7/E3PTSKcGiP2gUzwgoDhjawwRIqO osUPMvkhvTwmI4K9sg+oiHZAmIKPW1E= From: andrey.konovalov@linux.dev To: Andrew Morton Cc: Andrey Konovalov , Marco Elver , Alexander Potapenko , Dmitry Vyukov , Vlastimil Babka , kasan-dev@googlegroups.com, Evgenii Stepanov , Oscar Salvador , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Andrey Konovalov Subject: [PATCH v4 13/22] lib/stackdepot: use list_head for stack record links Date: Mon, 20 Nov 2023 18:47:11 +0100 Message-Id: <4787d9a584cd33433d9ee1846b17fa3d3e1987ad.1700502145.git.andreyknvl@google.com> In-Reply-To: References: MIME-Version: 1.0 X-Migadu-Flow: FLOW_OUT X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE 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-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Mon, 20 Nov 2023 09:50:18 -0800 (PST) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1783106234606128386 X-GMAIL-MSGID: 1783106234606128386 From: Andrey Konovalov Switch stack_record to use list_head for links in the hash table and in the freelist. This will allow removing entries from the hash table buckets. This is preparatory patch for implementing the eviction of stack records from the stack depot. Signed-off-by: Andrey Konovalov --- Changes v2->v3: - Use the proper number of entries for initializing the stack table when alloc_large_system_hash() auto-calculates the number. Changes v1->v2: - Use list_head instead of open-coding backward links. --- lib/stackdepot.c | 87 ++++++++++++++++++++++++++++-------------------- 1 file changed, 50 insertions(+), 37 deletions(-) diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 8378b32b5310..4bb0af423f82 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -18,6 +18,7 @@ #include #include #include +#include #include #include #include @@ -55,7 +56,7 @@ union handle_parts { }; struct stack_record { - struct stack_record *next; /* Link in hash table or freelist */ + struct list_head list; /* Links in hash table or freelist */ u32 hash; /* Hash in hash table */ u32 size; /* Number of stored frames */ union handle_parts handle; @@ -77,21 +78,21 @@ static bool __stack_depot_early_init_passed __initdata; /* Initial seed for jhash2. */ #define STACK_HASH_SEED 0x9747b28c -/* Hash table of pointers to stored stack traces. */ -static struct stack_record **stack_table; +/* Hash table of stored stack records. */ +static struct list_head *stack_table; /* Fixed order of the number of table buckets. Used when KASAN is enabled. */ static unsigned int stack_bucket_number_order; /* Hash mask for indexing the table. */ static unsigned int stack_hash_mask; -/* Array of memory regions that store stack traces. */ +/* Array of memory regions that store stack records. */ static void *stack_pools[DEPOT_MAX_POOLS]; /* Newly allocated pool that is not yet added to stack_pools. */ static void *new_pool; /* Number of pools in stack_pools. */ static int pools_num; -/* Next stack in the freelist of stack records within stack_pools. */ -static struct stack_record *next_stack; +/* Freelist of stack records within stack_pools. */ +static LIST_HEAD(free_stacks); /* * Stack depot tries to keep an extra pool allocated even before it runs out * of space in the currently used pool. This flag marks whether this extra pool @@ -116,6 +117,15 @@ void __init stack_depot_request_early_init(void) __stack_depot_early_init_requested = true; } +/* Initialize list_head's within the hash table. */ +static void init_stack_table(unsigned long entries) +{ + unsigned long i; + + for (i = 0; i < entries; i++) + INIT_LIST_HEAD(&stack_table[i]); +} + /* Allocates a hash table via memblock. Can only be used during early boot. */ int __init stack_depot_early_init(void) { @@ -152,16 +162,16 @@ int __init stack_depot_early_init(void) /* * If stack_bucket_number_order is not set, leave entries as 0 to rely - * on the automatic calculations performed by alloc_large_system_hash. + * on the automatic calculations performed by alloc_large_system_hash(). */ if (stack_bucket_number_order) entries = 1UL << stack_bucket_number_order; pr_info("allocating hash table via alloc_large_system_hash\n"); stack_table = alloc_large_system_hash("stackdepot", - sizeof(struct stack_record *), + sizeof(struct list_head), entries, STACK_HASH_TABLE_SCALE, - HASH_EARLY | HASH_ZERO, + HASH_EARLY, NULL, &stack_hash_mask, 1UL << STACK_BUCKET_NUMBER_ORDER_MIN, @@ -171,6 +181,14 @@ int __init stack_depot_early_init(void) stack_depot_disabled = true; return -ENOMEM; } + if (!entries) { + /* + * Obtain the number of entries that was calculated by + * alloc_large_system_hash(). + */ + entries = stack_hash_mask + 1; + } + init_stack_table(entries); return 0; } @@ -211,7 +229,7 @@ int stack_depot_init(void) entries = 1UL << STACK_BUCKET_NUMBER_ORDER_MAX; pr_info("allocating hash table of %lu entries via kvcalloc\n", entries); - stack_table = kvcalloc(entries, sizeof(struct stack_record *), GFP_KERNEL); + stack_table = kvcalloc(entries, sizeof(struct list_head), GFP_KERNEL); if (!stack_table) { pr_err("hash table allocation failed, disabling\n"); stack_depot_disabled = true; @@ -219,6 +237,7 @@ int stack_depot_init(void) goto out_unlock; } stack_hash_mask = entries - 1; + init_stack_table(entries); out_unlock: mutex_unlock(&stack_depot_init_mutex); @@ -230,31 +249,24 @@ EXPORT_SYMBOL_GPL(stack_depot_init); /* Initializes a stack depol pool. */ static void depot_init_pool(void *pool) { - const int records_in_pool = DEPOT_POOL_SIZE / DEPOT_STACK_RECORD_SIZE; - int i, offset; + int offset; lockdep_assert_held_write(&pool_rwlock); - /* Initialize handles and link stack records to each other. */ - for (i = 0, offset = 0; - offset <= DEPOT_POOL_SIZE - DEPOT_STACK_RECORD_SIZE; - i++, offset += DEPOT_STACK_RECORD_SIZE) { + WARN_ON(!list_empty(&free_stacks)); + + /* Initialize handles and link stack records into the freelist. */ + for (offset = 0; offset <= DEPOT_POOL_SIZE - DEPOT_STACK_RECORD_SIZE; + offset += DEPOT_STACK_RECORD_SIZE) { struct stack_record *stack = pool + offset; stack->handle.pool_index = pools_num; stack->handle.offset = offset >> DEPOT_STACK_ALIGN; stack->handle.extra = 0; - if (i < records_in_pool - 1) - stack->next = (void *)stack + DEPOT_STACK_RECORD_SIZE; - else - stack->next = NULL; + list_add(&stack->list, &free_stacks); } - /* Link stack records into the freelist. */ - WARN_ON(next_stack); - next_stack = pool; - /* Save reference to the pool to be used by depot_fetch_stack(). */ stack_pools[pools_num] = pool; pools_num++; @@ -295,7 +307,7 @@ static bool depot_update_pools(void **prealloc) lockdep_assert_held_write(&pool_rwlock); /* Check if we still have objects in the freelist. */ - if (next_stack) + if (!list_empty(&free_stacks)) goto out_keep_prealloc; /* Check if we have a new pool saved and use it. */ @@ -346,19 +358,18 @@ depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) return NULL; /* Check if we have a stack record to save the stack trace. */ - stack = next_stack; - if (!stack) + if (list_empty(&free_stacks)) return NULL; - /* Advance the freelist. */ - next_stack = stack->next; + /* Get and unlink the first entry from the freelist. */ + stack = list_first_entry(&free_stacks, struct stack_record, list); + list_del(&stack->list); /* Limit number of saved frames to CONFIG_STACKDEPOT_MAX_FRAMES. */ if (size > CONFIG_STACKDEPOT_MAX_FRAMES) size = CONFIG_STACKDEPOT_MAX_FRAMES; /* Save the stack trace. */ - stack->next = NULL; stack->hash = hash; stack->size = size; /* stack->handle is already filled in by depot_init_pool(). */ @@ -420,15 +431,17 @@ int stackdepot_memcmp(const unsigned long *u1, const unsigned long *u2, } /* Finds a stack in a bucket of the hash table. */ -static inline struct stack_record *find_stack(struct stack_record *bucket, +static inline struct stack_record *find_stack(struct list_head *bucket, unsigned long *entries, int size, u32 hash) { + struct list_head *pos; struct stack_record *found; lockdep_assert_held(&pool_rwlock); - for (found = bucket; found; found = found->next) { + list_for_each(pos, bucket) { + found = list_entry(pos, struct stack_record, list); if (found->hash == hash && found->size == size && !stackdepot_memcmp(entries, found->entries, size)) @@ -441,7 +454,8 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, unsigned int nr_entries, gfp_t alloc_flags, bool can_alloc) { - struct stack_record *found = NULL, **bucket; + struct list_head *bucket; + struct stack_record *found = NULL; depot_stack_handle_t handle = 0; struct page *page = NULL; void *prealloc = NULL; @@ -468,7 +482,7 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, read_lock_irqsave(&pool_rwlock, flags); /* Fast path: look the stack trace up without full locking. */ - found = find_stack(*bucket, entries, nr_entries, hash); + found = find_stack(bucket, entries, nr_entries, hash); if (found) { read_unlock_irqrestore(&pool_rwlock, flags); goto exit; @@ -500,14 +514,13 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, write_lock_irqsave(&pool_rwlock, flags); - found = find_stack(*bucket, entries, nr_entries, hash); + found = find_stack(bucket, entries, nr_entries, hash); if (!found) { struct stack_record *new = depot_alloc_stack(entries, nr_entries, hash, &prealloc); if (new) { - new->next = *bucket; - *bucket = new; + list_add(&new->list, bucket); found = new; } } else if (prealloc) {