From 4ab88f68b08edd2bbf0e39daeb5536801380433b Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 31 Jan 2019 11:11:13 -0500 Subject: [PATCH] maple_tree: Fix parent definitions & fallout from ULONG_MAX ending. coalesce needed to be updated for ULONG_MAX endings. ma_copy needed to check for ULONG_MAX ending. ma_encoded_parent no longer updates the ma_state limits. adopt_children needed the encoded node passed in for the node type to encode in the parent of the children. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 134 +++++++++++++++++++++++++++++++++-------------- 1 file changed, 94 insertions(+), 40 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 267fb2c659d5..94db306ca760 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -96,14 +96,19 @@ static inline unsigned int mt_slot_mask(struct maple_node *node) bitmask |= 0x04; // Set bit 2. return bitmask; } - -static inline unsigned int mt_slot_shift(struct maple_node *node) +static inline bool ma_is_root(struct maple_node *node) { - if (mt_node_type(node) == MAPLE_RANGE16_SLOTS) - return 2; - return 3; + if (((unsigned long)mt_to_node(node)->parent & MA_ROOT_PARENT) == 1) + return true; + return false; } + /* Private + * + * Type is encoded in the node->parent + * bit 0: 1 = root, 0 otherwise + * bit 1: 0 = range 16, 1 otherwise + * bit 2: 0 = range 32, 1 = range 64 | lowest bit of range_16's slot. * * Slot number is encoded in the node->parent * range_16, slot number is encoded in bits 2-6 @@ -111,30 +116,74 @@ static inline unsigned int mt_slot_shift(struct maple_node *node) * 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) + struct maple_node *parent, unsigned char slot) { - unsigned long bitmask = mt_slot_mask(node); - unsigned long slot_shift = mt_slot_shift(node); + unsigned long bitmask = 0x78; + unsigned long slot_shift = 3; unsigned long val = (unsigned long) parent; + unsigned long type = 0; + + switch (mt_node_type(parent)) { + case maple_range_64: + type |= 4; + /* fallthrough */ + case maple_range_32: + type |= 2; + break; + case maple_range_16: + slot_shift = 2; + break; + default: + break; + } 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. + val |= type; mt_to_node(node)->parent = (struct maple_node *)val; } +static inline unsigned int mt_parent_shift(unsigned long parent) +{ + if (parent & 1) + return 0; // Root. + if (!(parent & 2)) + return 2; // maple_range_16 + return 3; +} 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 bitmask = 0x7C; unsigned long val = (unsigned long) mt_to_node(node)->parent; + unsigned long slot_shift = mt_parent_shift(val); + + if (!slot_shift) + return 0; return (val & bitmask) >> slot_shift; } +static inline enum maple_type mt_parent_type(struct maple_node *node) +{ + unsigned long parent = (unsigned long) mt_to_node(node)->parent; + unsigned long slot_shift = mt_parent_shift(parent); + + parent &= ~(ULONG_MAX << slot_shift); + switch (parent) { + case 6: + return maple_range_64; + case 4: + return maple_range_32; + case 0: + return maple_range_16; + } + return maple_dense; +} + static inline void *mt_parent(struct maple_node *node) { - unsigned long bitmask = mt_slot_mask(node) | 7; + unsigned long bitmask = 0x7F; return (void *)((unsigned long)(mt_to_node(node)->parent) & ~bitmask); @@ -178,12 +227,6 @@ static inline void ma_set_slot(struct ma_state *ms, int slot) { ma_set_alloc_req(ms, slot); } -static inline bool ma_is_root(struct maple_node *node) -{ - if (((unsigned long)mt_to_node(node)->parent & 1) == 1) - return true; - return false; -} static void mas_update_limits(struct ma_state *ms, unsigned char slot) { @@ -195,6 +238,11 @@ static void mas_update_limits(struct ma_state *ms, unsigned char slot) if (mas_is_start(ms)) return; + if (ma_is_root(ms->node)) { + ms->max = ULONG_MAX; + ms->min = 0; + } + mr64 = &mt_to_node(ms->node)->mr64; if (slot > 0) ms->min = mr64->pivot[slot - 1] + 1; @@ -209,8 +257,6 @@ static inline void ma_encoded_parent(struct ma_state *mas) if (ma_is_root(mt_to_node(mas->node)->parent)) { mas->node = mt_safe_root(rcu_dereference(mas->tree->ma_root)); - mas->max = ULONG_MAX; - mas->min = 0; return; } @@ -222,7 +268,6 @@ static inline void ma_encoded_parent(struct ma_state *mas) mas->node = rcu_dereference(gparent->mr64.slot[slot]); return; } - static inline struct maple_node *ma_next_alloc(struct ma_state *ms) { int cnt; @@ -394,6 +439,7 @@ void ma_copy(struct ma_state *mas, struct ma_cp *cp) if (!cp->dst) { /* Allocate a new node */ + mas_node_cnt(mas, 1); if (mas_is_err(mas)) return; @@ -408,11 +454,12 @@ void ma_copy(struct ma_state *mas, struct ma_cp *cp) src64->pivot[sloc] == 0) break; - if (sloc < MAPLE_RANGE64_SLOTS - 1 && - dloc < MAPLE_RANGE64_SLOTS - 1) - dst64->pivot[dloc] = src64->pivot[sloc]; - else if (dloc < MAPLE_RANGE64_SLOTS - 1) - dst64->pivot[dloc] = mas->max; + if (dloc < MAPLE_RANGE64_SLOTS - 1) { + if (sloc < MAPLE_RANGE64_SLOTS - 1) + dst64->pivot[dloc] = src64->pivot[sloc]; + else if (dloc > 0 && dst64->pivot[dloc - 1] != mas->max) + dst64->pivot[dloc] = mas->max; + } RCU_INIT_POINTER(dst64->slot[dloc], src64->slot[sloc]); @@ -441,7 +488,7 @@ static int ma_cp_data_64(struct ma_state *mas, struct maple_node *left, static void ma_adopt_children(struct maple_node *parent) { - struct maple_range_64 *p64 = &parent->mr64; + struct maple_range_64 *p64 = &mt_to_node(parent)->mr64; struct maple_node *child; unsigned char slot; @@ -464,7 +511,7 @@ void mt_replace(struct ma_state *mas) struct maple_node *mn = mt_to_node(mas->node); struct maple_node *parent; struct maple_range_64 *p64; - unsigned char slot = mt_parent_slot(mas->node); + unsigned char slot = 0; struct maple_node *prev; if (ma_is_root(mas->node)) { @@ -472,6 +519,7 @@ void mt_replace(struct ma_state *mas) } else { parent = mt_parent(mas->node); p64 = &parent->mr64; + slot = mt_parent_slot(mas->node); prev = p64->slot[slot]; } @@ -479,7 +527,7 @@ void mt_replace(struct ma_state *mas) return; if (!mt_is_leaf(mas->node)) - ma_adopt_children(mn); + ma_adopt_children(mas->node); if (ma_is_root(mas->node)) { mn->parent = (struct maple_node *) @@ -506,6 +554,7 @@ static struct maple_range_64 *mas_partial_copy(struct ma_state *mas, ma_copy(mas, &cp); if (mas_is_err(mas)) return NULL; + mas->node = mt_mk_node(cp.dst, mt_node_type(mas->node)); cp.dst->parent = cp.src->parent; return &cp.dst->mr64; @@ -522,7 +571,7 @@ static void ma_link(struct maple_node *new, struct maple_node *parent, p64->pivot[slot] = pivot; RCU_INIT_POINTER(p64->slot[slot], new_enc); if (!mt_is_leaf(new_enc)) - ma_adopt_children(new); + ma_adopt_children(new_enc); } static int ma_split(struct ma_state *mas, unsigned char slot, @@ -538,23 +587,29 @@ static int ma_split(struct ma_state *mas, unsigned char slot, if (ma_is_root(full)) { old_parent = full; ptype = maple_range_64; + p_slot = 0; + mas->max = ULONG_MAX; } else { old_parent = mt_parent(mas->node); p_slot = mt_parent_slot(mas->node); p_end = ma_data_end_r64(&old_parent->mr64, UINT_MAX); - ma_encoded_parent(mas); // sets mas->node to encoded parent and updates limits. + ptype = mt_parent_type(mas->node); if (p_end >= MAPLE_RANGE64_SLOTS - 1) { /* Must split the parent */ + ma_encoded_parent(mas); + mas_update_limits(mas, p_slot); split = ma_split(mas, p_slot, p_end, 1); if (mas_is_err(mas)) return 0; - if (split <= p_slot) - p_slot -= split; + if (split < p_slot) + p_slot -= split + 1; // Split will return the parent. old_parent = mt_to_node(mas->node); + ptype = mt_node_type(mas->node); + p_slot = mt_parent_slot(mas->node); + mas_update_limits(mas, p_slot); + mas->node = old_parent->mr64.slot[p_slot]; } - ptype = mt_node_type(mas->node); - mas->node = old_parent->mr64.slot[p_slot]; } mas_node_cnt(mas, 3); @@ -573,7 +628,6 @@ static int ma_split(struct ma_state *mas, unsigned char slot, // Copy the parents information if (!ma_is_root(full)) { // Copy the parent data and leave a hole. - p_slot = mt_parent_slot(mas->node); MA_CP(cp, old_parent, new_parent, 0, p_slot); ma_copy(mas, &cp); cp.dst_start += 1; @@ -665,7 +719,6 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot) if (mas_is_err(mas)) return 0; - if (split <= slot) slot -= split; @@ -769,17 +822,18 @@ static int mas_coalesce(struct ma_state *mas) struct maple_node *src_mn = mt_to_node(mas->node); struct maple_range_64 *src = &src_mn->mr64; unsigned char s_slot, d_slot = 0; - unsigned long last = UINT_MAX; + unsigned long last = 0; struct maple_range_64 *dst = NULL; int ret = 0; for (s_slot = 0; s_slot < MAPLE_RANGE64_SLOTS; s_slot++) { if (s_slot < MAPLE_RANGE64_SLOTS - 1) { - if (last == src->pivot[s_slot]) { + if (s_slot != 0 && last == src->pivot[s_slot]) { if (!dst) { + // Skip this duplicate slot d_slot = s_slot; - dst = mas_partial_copy(mas, s_slot); + dst = mas_partial_copy(mas, s_slot - 1); if (mas_is_err(mas)) return 0; } @@ -1183,7 +1237,7 @@ void mt_dump_node(void *entry, unsigned long min, unsigned long max, mt_dump_range(min, max); pr_cont("node %p depth %d type %d parent %p", node, depth, type, - node->parent); + node ? node->parent : NULL); switch (type) { case maple_dense: pr_cont("\n"); -- 2.50.1