Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=100.103.45.18 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1795059924; b=PDfun9BqKAr42B72uLk3pmyILZHx9dJOXLYWFuFidrTBfsdJ7CDwTlbNh0eNs0AjfoAQ OOC5kxMOeCexH2w7nUWH0gD1/AaYULd25RKsru/Jf7VRjVdZCMugjtQSbiBhKsmexYfhb O/+MdxPm3QSOuxx32rzxU7Zo8DTTgEiNiKJCa1ydayUJD6yu7cxLNk8OwhBaZcD9lO7gf uKWFbcFltj+cll+tCtydAHOmyaUyMaIoNxkW2Vs+lz3va+wC3hPuYbAFskfbo7qR+zmgI 4IWqjMNuXycVg4Rz/UEE2qyO3H0vN2pbDca7+HGpxGyq8H+OvJeIPsMIe88/J7l6rfQ== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1795059924; h=Received:DKIM-Signature:From:To:Cc:Subject:Date:Message-ID:X-Mailer: In-Reply-To:References:User-Agent:X-stable:X-Patchwork-Hint: MIME-Version:Content-Transfer-Encoding; bh=i7nM3ondmac8NpI7UnQ2k8guOda7zwXGfNBm5c54h08=; b=nZtrvUPx089w6IZPUnd1hkFKmCO4cOcs7fi7dVrwALKaqwQv22C0ggC+OAZRkwgT0uc7 Nst6xqlUwcBVRkmGFDaeGR2TNbUVQ5icDVgGOJd/wHkesE8M1uy8hS9v2xxXAMJgJJU/8 18sU6mDcPkTixBd/F+n7BX2k0+ZTDJ0WatFb9vYiQ/gAiNW4ur4FcJryZvC1atDR0lofC HYzDjwG2fds8iv4fYKYGTkmmDu4u0DRul56aB/mT0kt6oU410viYsdQPF6Wo3wm/PvpvO 2pKmj3qqIKgw/dnBl/4bj2SGbjp2D8eHosV3EY3tFBhK0s19pLr25YgAysuTX/OHu3A== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass header.d=linuxfoundation.org header.i=@linuxfoundation.org header.a=rsa-sha256 header.s=korg header.b=UdvdxrD0; arc=none smtp.remote-ip=100.103.45.18 Received: from smtp.kernel.org (quasi.space.kernel.org [100.103.45.18]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D6BCA606A320; Thu, 19 Nov 2026 03:45:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linuxfoundation.org header.i=@linuxfoundation.org header.a=rsa-sha256 header.s=korg header.b=UdvdxrD0 Received: by smtp.kernel.org (Postfix) with ESMTPSA id 313DE1F000C5; Thu, 19 Nov 2026 03:45:24 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linuxfoundation.org; s=korg; t=1795059924; bh=i7nM3ondmac8NpI7UnQ2k8guOda7zwXGfNBm5c54h08=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=UdvdxrD0UD+TU2DjSCwWZQHcB4s3Kv1rnkHEe0MtxgOhVe5D2KGfXrhyh1jaRa/bx ggEJacbrjchh+9IUATy7tXgKmxySP1ZYW95IWYstTieieTql6nNIdGmsGwR3F2YC7A cY7rC2cp4xmQ6NilGlKdJLSPsppqt/dGwvg8F614= From: Greg Kroah-Hartman To: stable@vger.kernel.org Cc: Greg Kroah-Hartman , patches@lists.linux.dev, Linus Torvalds , David Howells , Sasha Levin Subject: [PATCH 5.10 1013/1848] assoc_array: move shortcut creation into a function of its own Date: Wed, 18 Nov 2026 15:50:51 +0100 Message-ID: <20261118145959.306887308@linuxfoundation.org> X-Mailer: git-send-email 2.56.0 In-Reply-To: <20261118145911.150052362@linuxfoundation.org> References: <20261118145911.150052362@linuxfoundation.org> User-Agent: quilt/0.69 X-stable: review X-Patchwork-Hint: ignore X-Mailing-List: patches@lists.linux.dev List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 5.10-stable review patch. If anyone has any objections, please let me know. ------------------ From: Linus Torvalds [ Upstream commit fdc6124c55dd0c5aa8e3ec30e6425b4d423ada24 ] Move the code after the all_leaves_cluster_together label into assoc_array_insert_shortcut(), which returns the new shortcut, or NULL when it cannot allocate one. The caller installs it and jumps to do_split_node as before. No functional change. Assisted-by: LLM Signed-off-by: Linus Torvalds Tested-by: David Howells Reviewed-by: David Howells [ sashal: used kzalloc(struct_size()) instead of kzalloc_flex() ] Stable-dep-of: 48691075b0ad ("assoc_array: don't chain a new shortcut onto an existing one") Signed-off-by: Sasha Levin --- lib/assoc_array.c | 146 ++++++++++++++++++++++++++-------------------- 1 file changed, 82 insertions(+), 64 deletions(-) diff --git a/lib/assoc_array.c b/lib/assoc_array.c index 17dc15d123913..74946e7ec1c60 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -647,6 +647,84 @@ static void assoc_array_split_node(struct assoc_array_edit *edit, } } +/* + * All the leaves, new and old, want to cluster together in this node in the + * same slot, so we have to replace this node with a shortcut to skip over + * the identical parts of the key, leading to new_n0. The caller then splits + * the leaves between new_n0 and new_n1 at the shortcut's far end, for which + * this fills in the segment cache. + */ +static struct assoc_array_shortcut * +assoc_array_insert_shortcut(struct assoc_array_edit *edit, + const struct assoc_array_ops *ops, + const void *index_key, + struct assoc_array_node *node, int level, + struct assoc_array_node *new_n0) +{ + struct assoc_array_shortcut *new_s0; + unsigned long base_seg, blank; + size_t keylen; + int diff, i; + + /* Firstly we need to work out where the leaves start diverging as a + * bit position into their keys so that we know how big the shortcut + * needs to be. + * + * We only need to make a single pass of N of the N+1 leaves because if + * any keys differ between themselves at bit X then at least one of + * them must also differ with the base key at bit X or before. + */ + pr_devel("all leaves cluster together\n"); + diff = INT_MAX; + for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) { + int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]), + index_key); + if (x < diff) { + BUG_ON(x < 0); + diff = x; + } + } + BUG_ON(diff == INT_MAX); + BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP); + + keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE); + keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT; + + new_s0 = kzalloc(struct_size(new_s0, index_key, keylen), GFP_KERNEL); + if (!new_s0) + return NULL; + edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0); + + new_s0->back_pointer = node->back_pointer; + new_s0->parent_slot = node->parent_slot; + new_s0->next_node = assoc_array_node_to_ptr(new_n0); + new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0); + new_n0->parent_slot = 0; + + new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK; + pr_devel("skip_to_level = %d [diff %d]\n", level, diff); + BUG_ON(level <= 0); + + for (i = 0; i < keylen; i++) + new_s0->index_key[i] = + ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE); + + if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) { + blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK); + pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank); + new_s0->index_key[keylen - 1] &= ~blank; + } + + /* This now reduces to a node splitting exercise for which we'll need + * to regenerate the disparity table. + */ + assoc_array_fill_segment_cache(edit, ops, node, level); + base_seg = ops->get_key_chunk(index_key, level); + base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK; + edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK; + return new_s0; +} + /* * Handle insertion into a terminal node. */ @@ -658,10 +736,9 @@ static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit, struct assoc_array_shortcut *new_s0; struct assoc_array_node *node, *new_n0, *new_n1; struct assoc_array_ptr *ptr; - unsigned long dissimilarity, base_seg, blank; - size_t keylen; + unsigned long dissimilarity, base_seg; bool have_meta; - int level, diff; + int level; int i; node = result->terminal_node.node; @@ -766,70 +843,11 @@ static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit, return true; all_leaves_cluster_together: - /* All the leaves, new and old, want to cluster together in this node - * in the same slot, so we have to replace this node with a shortcut to - * skip over the identical parts of the key and then place a pair of - * nodes, one inside the other, at the end of the shortcut and - * distribute the keys between them. - * - * Firstly we need to work out where the leaves start diverging as a - * bit position into their keys so that we know how big the shortcut - * needs to be. - * - * We only need to make a single pass of N of the N+1 leaves because if - * any keys differ between themselves at bit X then at least one of - * them must also differ with the base key at bit X or before. - */ - pr_devel("all leaves cluster together\n"); - diff = INT_MAX; - for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]), - index_key); - if (x < diff) { - BUG_ON(x < 0); - diff = x; - } - } - BUG_ON(diff == INT_MAX); - BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP); - - keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE); - keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT; - - new_s0 = kzalloc(struct_size(new_s0, index_key, keylen), GFP_KERNEL); + new_s0 = assoc_array_insert_shortcut(edit, ops, index_key, + node, level, new_n0); if (!new_s0) return false; - edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0); - edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0); - new_s0->back_pointer = node->back_pointer; - new_s0->parent_slot = node->parent_slot; - new_s0->next_node = assoc_array_node_to_ptr(new_n0); - new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0); - new_n0->parent_slot = 0; - - new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK; - pr_devel("skip_to_level = %d [diff %d]\n", level, diff); - BUG_ON(level <= 0); - - for (i = 0; i < keylen; i++) - new_s0->index_key[i] = - ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE); - - if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) { - blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK); - pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank); - new_s0->index_key[keylen - 1] &= ~blank; - } - - /* This now reduces to a node splitting exercise for which we'll need - * to regenerate the disparity table. - */ - assoc_array_fill_segment_cache(edit, ops, node, level); - - base_seg = ops->get_key_chunk(index_key, level); - base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK; - edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK; goto do_split_node; } -- 2.53.0