summaryrefslogtreecommitdiff
path: root/lib/assoc_array.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/assoc_array.c')
-rw-r--r--lib/assoc_array.c47
1 files changed, 26 insertions, 21 deletions
diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index c6659cb37033..388e656ac974 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -1,14 +1,10 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
/* Generic associative array implementation.
*
* See Documentation/core-api/assoc_array.rst for information.
*
* Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
* Written by David Howells (dhowells@redhat.com)
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public Licence
- * as published by the Free Software Foundation; either version
- * 2 of the Licence, or (at your option) any later version.
*/
//#define DEBUG
#include <linux/rcupdate.h>
@@ -745,8 +741,7 @@ all_leaves_cluster_together:
keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
- new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
- keylen * sizeof(unsigned long), GFP_KERNEL);
+ new_s0 = kzalloc(struct_size(new_s0, index_key, keylen), GFP_KERNEL);
if (!new_s0)
return false;
edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
@@ -768,9 +763,11 @@ all_leaves_cluster_together:
new_s0->index_key[i] =
ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
- 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;
+ 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.
@@ -851,8 +848,8 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
- new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
- keylen * sizeof(unsigned long), GFP_KERNEL);
+ new_s0 = kzalloc(struct_size(new_s0, index_key, keylen),
+ GFP_KERNEL);
if (!new_s0)
return false;
edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
@@ -866,7 +863,7 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
new_n0->parent_slot = 0;
memcpy(new_s0->index_key, shortcut->index_key,
- keylen * sizeof(unsigned long));
+ flex_array_size(new_s0, index_key, keylen));
blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
@@ -901,8 +898,8 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
- new_s1 = kzalloc(sizeof(struct assoc_array_shortcut) +
- keylen * sizeof(unsigned long), GFP_KERNEL);
+ new_s1 = kzalloc(struct_size(new_s1, index_key, keylen),
+ GFP_KERNEL);
if (!new_s1)
return false;
edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
@@ -915,7 +912,7 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
memcpy(new_s1->index_key, shortcut->index_key,
- keylen * sizeof(unsigned long));
+ flex_array_size(new_s1, index_key, keylen));
edit->set[1].ptr = &side->back_pointer;
edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
@@ -941,7 +938,7 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
edit->leaf_p = &new_n0->slots[0];
pr_devel("<--%s() = ok [split shortcut]\n", __func__);
- return edit;
+ return true;
}
/**
@@ -1115,6 +1112,7 @@ struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
index_key))
goto found_leaf;
}
+ fallthrough;
case assoc_array_walk_tree_empty:
case assoc_array_walk_found_wrong_shortcut:
default:
@@ -1463,6 +1461,7 @@ int assoc_array_gc(struct assoc_array *array,
struct assoc_array_ptr *cursor, *ptr;
struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
unsigned long nr_leaves_on_tree;
+ bool retained;
int keylen, slot, nr_free, next_slot, i;
pr_devel("-->%s()\n", __func__);
@@ -1491,13 +1490,12 @@ descend:
shortcut = assoc_array_ptr_to_shortcut(cursor);
keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
- new_s = kmalloc(sizeof(struct assoc_array_shortcut) +
- keylen * sizeof(unsigned long), GFP_KERNEL);
+ new_s = kmalloc(struct_size(new_s, index_key, keylen),
+ GFP_KERNEL);
if (!new_s)
goto enomem;
pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
- memcpy(new_s, shortcut, (sizeof(struct assoc_array_shortcut) +
- keylen * sizeof(unsigned long)));
+ memcpy(new_s, shortcut, struct_size(new_s, index_key, keylen));
new_s->back_pointer = new_parent;
new_s->parent_slot = shortcut->parent_slot;
*new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s);
@@ -1539,6 +1537,7 @@ continue_node:
goto descend;
}
+retry_compress:
pr_devel("-- compress node %p --\n", new_n);
/* Count up the number of empty slots in this node and work out the
@@ -1556,6 +1555,7 @@ continue_node:
pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
/* See what we can fold in */
+ retained = false;
next_slot = 0;
for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
struct assoc_array_shortcut *s;
@@ -1605,9 +1605,14 @@ continue_node:
pr_devel("[%d] retain node %lu/%d [nx %d]\n",
slot, child->nr_leaves_on_branch, nr_free + 1,
next_slot);
+ retained = true;
}
}
+ if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
+ pr_devel("internal nodes remain despite enough space, retrying\n");
+ goto retry_compress;
+ }
pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
nr_leaves_on_tree = new_n->nr_leaves_on_branch;
generated by cgit (git 2.34.1) at 2025-12-22 09:00:34 +0000