From b0451d157dd149c68214327572e72c6b8c06764d Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 7 Jan 2019 12:46:05 -0500 Subject: [PATCH] maple_tree: Add insert/append operation. Check for NULL runs by looking for duplicate pivots and coalesce them into a single entry. Append and insert into a new node, then replace the old node and adopt the children. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 283 ++++++++++++++++++++++++++++++++++++------ lib/test_maple_tree.c | 12 +- 2 files changed, 248 insertions(+), 47 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 56980807b967..28643f8aba5d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -73,6 +73,56 @@ static inline bool mas_is_err(struct ma_state *mas) return xa_is_err(mas->node); } +static inline unsigned int mt_slot_mask(struct maple_node *node) +{ + unsigned int bitmask = 0x78; // Bits 3-6 + + if (mt_node_type(node) == MAPLE_RANGE16_SLOTS) + bitmask |= 0x04; // Set bit 2. + return bitmask; +} +static inline unsigned int mt_slot_shift(struct maple_node *node) +{ + if (mt_node_type(node) == MAPLE_RANGE16_SLOTS) + return 2; + return 3; +} +/* Private + * + * Slot number is encoded in the node->parent + * range_16, slot number is encoded in bits 2-6 + * range_32, slot number is encoded in bits 3-6 + * range_64, slot number is encoded in bits 3-6 + */ +static inline void mt_set_parent(struct maple_node *node, + struct maple_node *parent, short slot) +{ + unsigned int bitmask = mt_slot_mask(node); + unsigned int slot_shift = mt_slot_shift(node); + unsigned long val = (unsigned long) parent; + + BUG_ON(slot > MAPLE_NODE_SLOTS); // Only 4 bits to use. + val &= ~bitmask; // Remove any old slot number. + val |= (slot << slot_shift); // Set the slot. + node->parent = (struct maple_node *)val; +} + +static inline unsigned int mt_parent_slot(struct maple_node *node) +{ + unsigned int bitmask = mt_slot_mask(node); + unsigned int slot_shift = mt_slot_shift(node); + unsigned long val = (unsigned long) node->parent; + + return (val & bitmask) >> slot_shift; +} + +static inline void *mt_parent(struct maple_node *node) +{ + unsigned int bitmask = mt_slot_mask(node) | 7; + + return (void *)((unsigned long)(node->parent) & ~bitmask); + +} static inline struct maple_node *ma_get_alloc(const struct ma_state *ms) { return (struct maple_node *)((unsigned long)ms->alloc & ~0x7F); @@ -144,7 +194,6 @@ static void ma_new_node(struct ma_state *ms, gfp_t gfp) mn = mt_alloc_one(gfp); if (!mn) goto list_failed; - printk("Node = %p\n", mn); req--; allocated++; } @@ -251,31 +300,54 @@ unsigned char ma_data_end_r64(const struct ma_state *ms) return data_end; } - -static void ma_append(struct ma_state *ms, void *entry) +static int _ma_insert(struct ma_state *ms, void *entry, unsigned char slot) { - short idx = ma_data_end_r64(ms) + 1; + unsigned char added = 1; + unsigned char o_end = ma_data_end_r64(ms); + unsigned char n_end = o_end; + unsigned long max = ms->max; struct maple_range_64 *mr64 = &ms->node->mr64; - if ((ms->index - 1 != mr64->pivot[idx - 2]) || - (ms->index != ms->last)) - idx++; + if (o_end < MAPLE_RANGE64_SLOTS - 1) + max = mr64->pivot[o_end - 1]; - if (idx >= MAPLE_RANGE64_SLOTS - 1) - printk("Split this node\n"); + if ((ms->index - 1 != max) || + (ms->index != ms->last)) { + added++; + n_end++; + } + + if (n_end >= MAPLE_RANGE64_SLOTS && ms->max != ms->last) + pr_info("\n\nSplit this node\n"); + + if (o_end == slot) { // Appending + /* zero the new end if the pivot exists. */ + if (n_end < MAPLE_RANGE64_SLOTS - 2) + mr64->pivot[n_end+1] = 0; + } else { + while (o_end > slot) { + if (n_end < MAPLE_RANGE64_SLOTS - 2) + mr64->pivot[n_end] = mr64->pivot[o_end]; + RCU_INIT_POINTER(mr64->slot[n_end--], + mr64->slot[o_end--]); + } + } - /* zero the new end */ - mr64->pivot[idx--] = 0; /* Set the entry value */ - RCU_INIT_POINTER(mr64->slot[idx], entry); - mr64->pivot[idx--] = ms->last; + mr64->pivot[n_end] = ms->last; + RCU_INIT_POINTER(mr64->slot[n_end--], entry); /* Create a NULL gap, if necessary */ - if ((ms->index - 1 != mr64->pivot[idx - 1]) || - (ms->index != ms->last)) { - RCU_INIT_POINTER(mr64->slot[idx], NULL); - mr64->pivot[idx] = ms->index - 1; + if ((ms->index - 1 != mr64->pivot[n_end]) || + (ms->index != ms->last)) { + RCU_INIT_POINTER(mr64->slot[n_end], NULL); + mr64->pivot[n_end] = ms->index - 1; } + return added; +} +static unsigned char ma_append(struct ma_state *ms, void *entry) +{ + return _ma_insert(ms, entry, ma_data_end_r64(ms)); } static void ma_root_expand(struct ma_state *ms, void *entry) @@ -302,7 +374,7 @@ static void ma_root_expand(struct ma_state *ms, void *entry) rcu_assign_pointer(ms->tree->ma_root, mt_mk_node(mn, maple_leaf_64)); } -static void ms_update_limits(struct ma_state *ms, unsigned char slot) +static void mas_update_limits(struct ma_state *ms, unsigned char slot) { struct maple_range_64 *mr64; if (slot >= MAPLE_NODE_SLOTS) @@ -319,56 +391,189 @@ static void ms_update_limits(struct ma_state *ms, unsigned char slot) if (slot < MAPLE_RANGE64_SLOTS - 1) ms->max = mr64->pivot[slot]; } + +/* Private + * Combine nulls with the same pivot value + */ +static void *mas_coalesce(struct ma_state *mas) +{ + struct maple_range_64 *src = &mas->node->mr64; + unsigned long last = mas->max; + struct maple_range_64 *dst; + struct maple_node *mn; + unsigned char s_slot, d_slot = 0; + + /* Allocate a new node */ + mas_node_cnt(mas, 1); + if (mas_is_err(mas)) + return NULL; + + mn = ma_next_alloc(mas); + dst = &mn->mr64; + + for (s_slot = 0; s_slot < MAPLE_RANGE64_SLOTS; s_slot++) { + if (last == src->pivot[s_slot]) + continue; + + if (s_slot < MAPLE_RANGE64_SLOTS - 1) { + if (s_slot != 0 && src->pivot[s_slot] == 0) + break; + + dst->pivot[d_slot] = src->pivot[s_slot]; + } + + RCU_INIT_POINTER(dst->slot[d_slot], src->slot[s_slot]); + last = dst->pivot[d_slot++]; + } + return mn; +} + +static void ma_adopt_children(struct maple_node *parent) +{ + + struct maple_range_64 *p64 = &parent->mr64; + struct maple_node *child; + unsigned char slot; + + for (slot = 0; slot < MAPLE_RANGE64_SLOTS; slot++) { + if (slot < MAPLE_RANGE64_SLOTS - 1 && + slot != 0 && p64->pivot[slot] == 0) + break; + child = p64->slot[slot]; + mt_set_parent(child, parent, slot); + } +} + +static unsigned char mt_copy_mr64(struct maple_range_64 *dst, + unsigned char d_slot, struct maple_range_64 *src, + unsigned char s_slot, unsigned char cnt) +{ + BUG_ON(cnt >= MAPLE_RANGE64_SLOTS); + for (; s_slot < cnt; s_slot++) { + if (d_slot > 0 && + dst->pivot[d_slot - 1] == src->pivot[s_slot]) { + s_slot++; + } + dst->pivot[d_slot] = src->pivot[s_slot]; + + if (s_slot != 0 && src->pivot[s_slot] == 0) + return d_slot; + + if (s_slot > 0 && + src->slot[s_slot] == NULL && + src->slot[s_slot - 1] == NULL) { + dst->pivot[--d_slot] = src->pivot[s_slot]; + continue; + } + RCU_INIT_POINTER(dst->slot[d_slot], src->slot[s_slot]); + d_slot++; + } + return d_slot; +} static unsigned char mas_walk_r64(struct ma_state *ms, unsigned long val) { struct maple_range_64 *mr64 = &ms->node->mr64; int i = 0; - do { - if (i >= MAPLE_RANGE64_SLOTS - 1) - break; // Right-most child. + + for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) { + if (i != 0 && mr64->pivot[i] == 0) + goto not_found; + if (val <= mr64->pivot[i]) break; - } while (i++ < MAPLE_RANGE64_SLOTS - 1); + } + if (i == MAPLE_RANGE64_SLOTS - 2) { + // Right-most child. + if (ms->max != val) + goto not_found; + + ms->node = rcu_dereference(mr64->slot[++i]); + if (!ms->node) + goto not_found; + return i; + } ms->node = rcu_dereference(mr64->slot[i]); return i; + +not_found: + mas_set_err(ms, -EBADSLT); + return i; + } -void *ma_insert(struct ma_state *ms, void *entry) +void mt_dump_node(void *entry, unsigned long min, unsigned long max, + unsigned int depth); + +void *ma_insert(struct ma_state *mas, void *entry) { - void *e_entry = mas_start(ms); // existing entry; + void *e_entry = mas_start(mas); // existing entry; void *p_entry; // Previous entry. - char slot = MAPLE_NODE_SLOTS; + unsigned char slot = MAPLE_NODE_SLOTS; + struct maple_node *mn; + bool leaf; if (!xa_is_node(e_entry)) { - if (ms->last == 0) { + if (mas->last == 0) { if (e_entry != NULL) goto exists; - rcu_assign_pointer(ms->tree->ma_root, entry); + rcu_assign_pointer(mas->tree->ma_root, entry); return NULL; } - ma_root_expand(ms, entry); + ma_root_expand(mas, entry); return NULL; } /* Find the correct node */ do { - ms->node = mt_to_node(e_entry); - p_entry = ms->node; - ms_update_limits(ms, slot); - slot = mas_walk_r64(ms, ms->index); - e_entry = ms->node; + mas->node = mt_to_node(e_entry); + leaf = mt_is_leaf(e_entry); + p_entry = mas->node; + mas_update_limits(mas, slot); + slot = mas_walk_r64(mas, mas->index); + if (mas_is_err(mas)) { + /* Ran off the end of the node. */ + mas->node = p_entry; + ma_append(mas, entry); + return NULL; + } + e_entry = mas->node; } while (xa_is_node(e_entry)); + if (e_entry) goto exists; - /* Do the Insert */ - printk("Inserting %lu\n", ms->index); + mas->node = p_entry; + mn = mas_coalesce(mas); + if (mas_is_err(mas)) + return NULL; + + mas->node = mn; + /* Do the insert */ + _ma_insert(mas, entry, slot); + if (mas_is_err(mas)) + return NULL; + + /* Insert into tree */ + mn->parent = mas->node->parent; + if (!leaf) + ma_adopt_children(mn); + if (ma_is_root(p_entry)) { + rcu_assign_pointer(mas->tree->ma_root, + mt_mk_node(mn, maple_leaf_64)); + } else { + struct maple_node *parent = mt_parent(mn->parent); + + slot = mt_parent_slot(mn); + RCU_INIT_POINTER(parent->slot[slot], + mt_mk_node(mn, maple_leaf_64)); + } + mt_free(p_entry); return NULL; exists: - mas_set_err(ms, -EEXIST); + mas_set_err(mas, -EEXIST); return NULL; } @@ -395,8 +600,10 @@ void *mas_walk(struct ma_state *ms) while (xa_is_node(entry)) { ms->node = mt_to_node(entry); - ms_update_limits(ms, slot); + mas_update_limits(ms, slot); slot = mas_walk_r64(ms, ms->index); + if (mas_is_err(ms)) + return NULL; entry = ms->node; } return entry; @@ -524,8 +731,6 @@ void mt_dump_entry(void *entry, unsigned long min, unsigned long max) pr_cont("%p\n", entry); } -void mt_dump_node(void *entry, unsigned long min, unsigned long max, - unsigned int depth); void mt_dump_range64(void *entry, unsigned long min, unsigned long max, unsigned int depth) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 6b7471e283db..d364a41fb4b4 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -229,6 +229,7 @@ static int maple_tree_seed(void) unsigned long r[] = {10, 15, 20, 25, 22}; // For range testing void *ptr = &set; + pr_info("\nTEST STARTING\n\n"); mtree_init(&tree); //check_new_node(&tree); @@ -244,6 +245,7 @@ static int maple_tree_seed(void) check_load(&tree, set[11], NULL); // See if 2 -> NULL + check_load(&tree, set[10], ptr); // See if 3 -> ptr /* Clear out the tree */ @@ -259,16 +261,9 @@ static int maple_tree_seed(void) * a second value, then loads the value again */ check_load(&tree, set[1], NULL); // See if 14 -> NULL - printk("%s: %d\n", __func__, __LINE__); - mt_dump(&tree); check_insert(&tree, set[1], ptr); // insert 14 -> ptr - mt_dump(&tree); - printk("%s: %d\n", __func__, __LINE__); check_load(&tree, set[1], ptr); // See if 14 -> ptr - printk("%s: %d\n", __func__, __LINE__); check_load(&tree, set[0], &tree); // See if 15 -> &tree - printk("%s: %d\n", __func__, __LINE__); - /* Tree currently contains: * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil) */ @@ -313,7 +308,8 @@ static int maple_tree_seed(void) check_insert(&tree, set[0], ptr); // 15 check_insert(&tree, set[1], &tree); // 14 check_insert(&tree, set[2], ptr); // 17 - check_insert(&tree, set[3], &tree); // 25. + check_insert(&tree, set[3], &tree); // 25 + return 0; check_insert(&tree, set[4], ptr); // 1000 < Should split. check_load(&tree, set[0], ptr); check_load(&tree, set[1], &tree); -- 2.50.1