From 160e87eadca07690fcf995aeaccca775a5e68337 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 15 Jan 2019 11:17:00 -0500 Subject: [PATCH] maple_tree: Rearrange _ma_insert for appends. Reorder and make _ma_insert append safe and prepare for split. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 202 +++++++++++++++++++++++++----------------- lib/test_maple_tree.c | 1 - 2 files changed, 119 insertions(+), 84 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 198ef705a71d..d0a8f127a8ee 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -324,9 +324,55 @@ unsigned char ma_data_end_r64(const struct ma_state *ms) return data_end; } + +/* Private + * + * Splitting is done in a lazy-fashion. As such, the parent may not have room + * for two entries and will require splitting itself. Rinse & repeat. + */ +static int ma_split(struct ma_state *mas, unsigned char slot, + unsigned char num) +{ + return 0; +} +/* Private + * + * This copies from the start to the specified end of a node into a new node. + * Returns a pointer to the node, encoded node is in mas->node. + * Note: mas->node is overwritten. + * This isn't safe to use to copy the last slot as it doesn't check the + * pivot. + */ +static struct maple_range_64 *mas_partial_copy(struct ma_state *mas, + unsigned char end) +{ + struct maple_node *smn = mt_to_node(mas->node); + struct maple_range_64 *src = &smn->mr64; + struct maple_range_64 *dst = NULL; + struct maple_node *dmn; + int i = 0; + /* Allocate a new node */ + mas_node_cnt(mas, 1); + if (mas_is_err(mas)) + return NULL; + + dmn = ma_next_alloc(mas); + dst = &dmn->mr64; + dmn->parent = smn->parent; + for (i = 0; i < end;i++) + { + RCU_INIT_POINTER(dst->slot[i], + src->slot[i]); + dst->pivot[i] = src->pivot[i]; + } + mas->node = mt_mk_node(dmn, maple_leaf_64); + return dst; +} /* Private * - * Insert entry into a node that is not visible to readers. + * Insert entry into a node. + * If this is not an append, a new node will be generated. + * If this node is full, split the node & insert. * * This is done by: * 1. Calculating the range of slot. @@ -338,10 +384,12 @@ unsigned char ma_data_end_r64(const struct ma_state *ms) static int _ma_insert(struct ma_state *ms, void *entry, unsigned char slot) { struct maple_range_64 *mr64 = &mt_to_node(ms->node)->mr64; + struct maple_range_64 *p_mr64; int o_end = ma_data_end_r64(ms); // Old end int n_end = o_end; // New end unsigned long max = ms->max; unsigned long min = ms->min; + int ret = 1; /* Calculate the range of the slot */ if (slot < MAPLE_RANGE64_SLOTS - 1 && mr64->pivot[slot] != 0) @@ -360,39 +408,63 @@ static int _ma_insert(struct ma_state *ms, void *entry, unsigned char slot) if (min != ms->index - 1) n_end++; - /* Copy the data over */ - while (o_end >= slot) { - RCU_INIT_POINTER(mr64->slot[n_end], - mr64->slot[o_end]); - if (n_end < MAPLE_RANGE64_SLOTS - 1) - mr64->pivot[n_end] = mr64->pivot[o_end]; - n_end--; - o_end--; + if (n_end > MAPLE_RANGE64_SLOTS -1) { + return ma_split(ms, slot, n_end); } - // Overwrite the last pivot value - if (mr64->pivot[slot] == ms->index) - n_end++; - - /* Write the entry */ + /* Save the node in case we are not appending. */ + p_mr64 = mr64; - RCU_INIT_POINTER(mr64->slot[n_end], entry); + /* Creates a new node and copies until slot (inclusively) */ + if (slot == o_end) { + /* Appending */ + o_end = n_end; + } else { + /* Not appending */ + mr64 = mas_partial_copy(ms, slot); + o_end = slot; + if (mas_is_err(ms)) + return 0; + } if (min != ms->index - 1) { - mr64->pivot[n_end--] = ms->last; - RCU_INIT_POINTER(mr64->slot[n_end], NULL); - wmb(); /* slot needs to be written before readers can see. */ - mr64->pivot[n_end] = ms->index - 1; - return 2; + /* When writing a NULL entry, the order must be reversed to + * ensure readers don't get incorrect data on appends + */ + /* Write the entry */ + RCU_INIT_POINTER(mr64->slot[++slot], entry); + mr64->pivot[slot] = ms->last; + /* Write NULL entry */ + RCU_INIT_POINTER(mr64->slot[--slot], NULL); + if (o_end == n_end) // Append. + wmb(); + + mr64->pivot[slot] = ms->index - 1; + slot+=2; + ret = 2; + } else { + /* Write the entry */ + RCU_INIT_POINTER(mr64->slot[slot], entry); + if (o_end == n_end) // Append. + wmb(); + + mr64->pivot[slot++] = ms->last; } - wmb(); /* slot needs to be written before readers can see. */ - mr64->pivot[n_end] = ms->last; - return 1; -} -static unsigned char ma_append(struct ma_state *ms, void *entry) -{ - return _ma_insert(ms, entry, ma_data_end_r64(ms)); + /* Skip possible duplicate entry that contains a NULL */ + if (p_mr64->pivot[o_end] == ms->last) + o_end++; + + /* Copy remainder of node if this isn't an append */ + for ( ; o_end < n_end; slot++, o_end++) { + if(p_mr64->pivot[o_end] == 0) + break; + RCU_INIT_POINTER(mr64->slot[slot], + p_mr64->slot[o_end]); + if (slot < MAPLE_RANGE64_SLOTS - 1) + mr64->pivot[slot] = p_mr64->pivot[o_end]; + } + return ret; } static void ma_root_expand(struct ma_state *ms, void *entry) @@ -414,7 +486,7 @@ static void ma_root_expand(struct ma_state *ms, void *entry) if (!r_entry) mn->mr64.pivot[0] = ms->index - 1; - ma_append(ms, entry); + _ma_insert(ms, entry, 1); /* swap the new root into the tree */ rcu_assign_pointer(ms->tree->ma_root, mt_mk_root(ms->node)); } @@ -437,37 +509,6 @@ static void mas_update_limits(struct ma_state *ms, unsigned char slot) if (slot < MAPLE_RANGE64_SLOTS - 1) ms->max = mr64->pivot[slot]; } -/* Private - * - * This copies from the start to the specified end of a node into a new node. - * Returns a pointer to the node, encoded node is in mas->node. - * Node: mas->node is overwritten. - */ -static struct maple_range_64 *mas_partial_copy(struct ma_state *mas, - unsigned char end) -{ - struct maple_node *smn = mt_to_node(mas->node); - struct maple_range_64 *src = &smn->mr64; - struct maple_range_64 *dst = NULL; - struct maple_node *dmn; - int i = 0; - /* Allocate a new node */ - mas_node_cnt(mas, 1); - if (mas_is_err(mas)) - return NULL; - - dmn = ma_next_alloc(mas); - dst = &dmn->mr64; - dmn->parent = smn->parent; - for (i = 0; i < end;i++) - { - RCU_INIT_POINTER(dst->slot[i], - src->slot[i]); - dst->pivot[i] = src->pivot[i]; - } - mas->node = mt_mk_node(dmn, maple_leaf_64); - return dst; -} /* Private * Combine nulls with the same pivot value * Note: The mas->node will most likely be changed, so keep track of the old @@ -605,15 +646,22 @@ bool ma_reserved(void *entry) /* Private * Replace mn with mas->node in the tree */ -void mt_replace(struct ma_state *mas, void *p_entry, bool leaf) +void mt_may_replace(struct ma_state *mas, void *p_entry, bool leaf) { struct maple_node *mn; + struct maple_node *pmn = mt_to_node(p_entry); + /* There is no new node to replace */ if (mas->node == p_entry) return; mn = mt_to_node(mas->node); - mn->parent = mt_to_node(p_entry)->parent; + + /* The targeted node was split and is already in the tree */ + if (mn == mt_parent(pmn)) + goto in_tree; + + mn->parent = pmn->parent; if (!leaf) ma_adopt_children(mn); @@ -628,17 +676,15 @@ void mt_replace(struct ma_state *mas, void *p_entry, bool leaf) RCU_INIT_POINTER(parent->slot[slot], mas->node); } - mt_free(mt_to_node(p_entry)); +in_tree: + mt_free(pmn); } void *ma_insert(struct ma_state *mas, void *entry) { void *p_entry; // Previous entry. unsigned char slot = MAPLE_NODE_SLOTS; - unsigned long last = mas->max; struct maple_range_64 *src; - bool coalesce = false; - unsigned char s_slot; bool leaf; @@ -661,7 +707,7 @@ void *ma_insert(struct ma_state *mas, void *entry) leaf = _mas_walk(mas); slot = ma_get_slot(mas); - src = mt_to_node(mas->node); + src = &mt_to_node(mas->node)->mr64; if (leaf == true && slot != MAPLE_NODE_SLOTS) { if (src->slot[slot]) { mas_set_err(mas, -EEXIST); @@ -670,27 +716,17 @@ void *ma_insert(struct ma_state *mas, void *entry) } p_entry = mas->node; - for (s_slot = 0; s_slot < MAPLE_RANGE64_SLOTS - 1; s_slot++) { - if (last == src->pivot[s_slot]) { - coalesce = true; - break; - } - last = src->pivot[s_slot]; - } - - if (coalesce) { - mas_coalesce(mas); - if (mas_is_err(mas)) - goto error; - } + mas_coalesce(mas); + if (mas_is_err(mas)) + goto error; /* Do the insert */ _ma_insert(mas, entry, slot); if (mas_is_err(mas)) goto error; - /* Replace the node in the tree */ - mt_replace(mas, p_entry, leaf); + /* Replace the node in the tree, if necessary. */ + mt_may_replace(mas, p_entry, leaf); return NULL; error: @@ -776,7 +812,7 @@ int ma_erase(struct ma_state *mas) if (mas_is_err(mas)) goto error; - mt_replace(mas, p_entry, leaf); + mt_may_replace(mas, p_entry, leaf); error: return cnt; @@ -1005,7 +1041,7 @@ void mt_dump(const struct maple_tree *mt) else mt_dump_node(entry, 0, mt_max[mt_node_type(entry)], 0); } - +extern void kmem_cache_set_non_kernel(struct kmem_cache *, unsigned int); void mt_set_non_kernel(unsigned int val) { kmem_cache_set_non_kernel(maple_node_cache, val); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 922cf0b0b2ad..4da1e1d36180 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -325,7 +325,6 @@ static int maple_tree_seed(void) mt_set_non_kernel(1); check_erase(&tree, set[1]); check_load(&tree, set[1], NULL); - return 0; check_insert(&tree, set[4], ptr); // 1000 < Should split. check_load(&tree, set[0], ptr); -- 2.50.1