From d72084bc6da32ed275d5c9e46e79567990550422 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 7 Dec 2018 10:33:12 -0500 Subject: [PATCH] maple_tree: Add anon struct to maple_node Add an anon struct for parent access & for allocations. Drop unnecessary encoding of parent. Remove unnecessary brackets Rename some variables for readability and add some comments. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 5 ++ lib/maple_tree.c | 102 +++++++++++++++++-------------------- 2 files changed, 53 insertions(+), 54 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 99e8725adf48..31df0fe1ad8c 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -80,6 +80,11 @@ struct maple_node { struct maple_node_4m map4m; struct maple_node_64 map64; struct maple_node_4 map4; + struct { + struct maple_node __rcu *parent; + void *slot[2]; /* Used for allocations. */ + unsigned long _pad[13]; + }; }; }; /* diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 2fc3811d57e8..33ebbb0ddbb8 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -81,8 +81,8 @@ static inline struct maple_node *ma_next_alloc(struct maple_state *ms) if (cnt == 0) { ms->alloc = NULL; } else { - smn = (struct maple_node*)mn->map64.slot[cnt - 1]; - mn->map64.slot[cnt - 1] = NULL; + smn = (struct maple_node*)mn->slot[cnt - 1]; + mn->slot[cnt - 1] = NULL; ma_set_alloc_cnt(ms, cnt); mn = smn; } @@ -131,8 +131,8 @@ static void maple_new_node(struct maple_state *ms, int count, gfp_t gfp) smn = kzalloc(sizeof(*mn), gfp); if (!smn) goto kzalloc_failed; - smn->map64.parent = NULL; - mn->map64.slot[i] = smn; + smn->parent = NULL; + mn->slot[i] = smn; } ms->alloc = mn; ma_set_alloc_cnt(ms, count); @@ -140,7 +140,7 @@ static void maple_new_node(struct maple_state *ms, int count, gfp_t gfp) kzalloc_failed: while (--i >= 0) - kfree(mn->map64.slot[i]); + kfree(mn->slot[i]); kfree(mn); list_failed: return; @@ -351,13 +351,13 @@ static int _maple_root_expand(struct maple_state *ms) * Copy 1/2 the data from ms->node to new_mn. */ static void maple_split_data_64(struct maple_state *ms, - struct maple_node *lmn, - struct maple_node *rmn, + struct maple_node *left, + struct maple_node *right, int off) { - struct maple_node_64 *full_mn = &(ms->node->map64); - struct maple_node_64 *target = &(lmn->map64); + struct maple_node_64 *full64 = &ms->node->map64; + struct maple_node_64 *target = &left->map64; int i, j; /* Copy 0-4 to left_mn 1-5 @@ -365,14 +365,14 @@ static void maple_split_data_64(struct maple_state *ms, */ for (i = 0, j = off; j < MAPLE_NODE64_MAX_SLOT; i++, j++) { if (i == MAPLE_NODE64_MAX_SLOT / 2) { - target = &(rmn->map64); + target = &right->map64; i = 0; } if (j < MAPLE_NODE64_MAX_SLOT - 1) - target->pivot[i] = full_mn->pivot[j]; + target->pivot[i] = full64->pivot[j]; else if (j == MAPLE_NODE64_MAX_SLOT - 1 && ms->max != ULONG_MAX) target->pivot[i] = ms->max; - target->slot[i] = full_mn->slot[j]; + target->slot[i] = full64->slot[j]; } } @@ -385,16 +385,16 @@ static void maple_split_data_64(struct maple_state *ms, */ int maple_data_end_64(const struct maple_node_64 *mn64) { - int p_end; + int data_end; - for (p_end = 0; p_end < MAPLE_NODE64_MAX_PIVOT; p_end++) { - if (mn64->pivot[p_end] == 0) + for (data_end = 0; data_end < MAPLE_NODE64_MAX_PIVOT; data_end++) { + if (mn64->pivot[data_end] == 0) break; } - if ((p_end == MAPLE_NODE64_MAX_PIVOT - 1) && - (mn64->slot[p_end + 1] != NULL)) - p_end++; - return p_end; + if ((data_end == MAPLE_NODE64_MAX_PIVOT - 1) && + (mn64->slot[data_end + 1] != NULL)) + data_end++; + return data_end; } /* * Private @@ -403,10 +403,10 @@ int maple_data_end_64(const struct maple_node_64 *mn64) */ void maple_shift_64(struct maple_node_64 *mn64, int p_here) { - int p_end = maple_data_end_64(mn64); + int data_end = maple_data_end_64(mn64); int idx; - for (idx = p_end; idx >= p_here; idx--) { + for (idx = data_end; idx >= p_here; idx--) { if (idx < 6) mn64->pivot[idx + 1] = mn64->pivot[idx]; rcu_assign_pointer(mn64->slot[idx + 1], mn64->slot[idx]); @@ -420,45 +420,39 @@ void maple_shift_64(struct maple_node_64 *mn64, int p_here) * */ void maple_link_node(struct maple_state *ms, - struct maple_node *lmn, - struct maple_node *rmn) + struct maple_node *left, + struct maple_node *right) { - struct maple_node *full_mn = ms->node; - struct maple_node_64 *fmn64 = &(full_mn->map64); - struct maple_node_64 *lmn64 = &(lmn->map64); - struct maple_node_64 *rmn64 = &(rmn->map64); + struct maple_node *full = ms->node; + struct maple_node_64 *left64 = &left->map64; if (maple_is_root(ms, ms->node)) { - struct maple_node *root_mn = ma_next_alloc(ms); - int l_end = maple_data_end_64(lmn64) - 1; - int r_end = maple_data_end_64(rmn64) - 1; - int idx = 0; + struct maple_node *new_root = ma_next_alloc(ms); + int l_end = maple_data_end_64(left64) - 1; + int r_end = maple_data_end_64(&right->map64) - 1; /* The full node is the root. * We have to throw out the old root due to pesky readers. * left and right have the data already, so link them in the * correct place in the root. */ - lmn64->parent = ma_mk_node(root_mn); - rmn64->parent = ma_mk_node(root_mn); - /* Root will have two entries: lmn, rmn. + left->parent = new_root; + right->parent = new_root; + /* Root will have two entries: left, right. * The pivot will be the maximum pivot of each. - * pivot 0 will be the lowest pivot of lmn. + * pivot 0 will be the lowest pivot of left. */ - root_mn->map64.pivot[idx] = fmn64->pivot[0]; - idx++; + new_root->map64.pivot[0] = full->map64.pivot[0]; /* Left child */ - root_mn->map64.pivot[idx] = lmn64->pivot[l_end]; - RCU_INIT_POINTER(root_mn->map64.slot[idx], ma_mk_node(lmn)); - idx++; + new_root->map64.pivot[1] = left64->pivot[l_end]; + RCU_INIT_POINTER(new_root->map64.slot[1], ma_mk_node(left)); /* Right child */ - root_mn->map64.pivot[idx] = rmn64->pivot[r_end]; - RCU_INIT_POINTER(root_mn->map64.slot[idx], ma_mk_node(rmn)); + new_root->map64.pivot[2] = right->map64.pivot[r_end]; + RCU_INIT_POINTER(new_root->map64.slot[2], ma_mk_node(right)); /* Swap root of tree */ - rcu_assign_pointer(ms->tree->root, ma_mk_node(root_mn)); - ms->node = root_mn; + rcu_assign_pointer(ms->tree->root, ma_mk_node(new_root)); + ms->node = new_root; } else { - struct maple_node_64 *target = - &(ma_to_node(fmn64->parent)->map64); + struct maple_node_64 *target = &full->parent->map64; /* * Shift in the parent, making room for the right node. * @@ -471,22 +465,22 @@ void maple_link_node(struct maple_state *ms, * target. */ - lmn64->parent = fmn64->parent; - rmn64->parent = fmn64->parent; + left->parent = full->parent; + right->parent = full->parent; /* Shift the data over */ maple_shift_64(target, ms->slot_idx); /* Overwrite the duplicate slot data with the new right node */ - target->slot[ms->slot_idx + 1] = ma_mk_node(rmn); + target->slot[ms->slot_idx + 1] = ma_mk_node(right); /* Overwrite the first pivot with the new value. This is fine * as the current slot has valid entries for this pivot */ - target->pivot[ms->slot_idx] = lmn64->pivot[3]; + target->pivot[ms->slot_idx] = left64->pivot[3]; /* Set the first slot to the node with less pivots */ - target->slot[ms->slot_idx] = ma_mk_node(lmn); + target->slot[ms->slot_idx] = ma_mk_node(left); } /* Orphan & free the full node */ - fmn64->parent = full_mn; - _maple_free_node(full_mn); + full->parent = full; + _maple_free_node(full); } /* * Private @@ -537,7 +531,7 @@ static inline int _maple_insert_4(struct maple_state *ms, void *entry) static inline int _maple_insert_64(struct maple_state *ms, void *entry) { struct maple_node_64 *mn64 = &ms->node->map64; - int p_here = ms->slot_idx; /* Location to place data */ + int p_here = ms->slot_idx; /* Place data here */ int shift = 0; int idx = 0; -- 2.50.1