From 5ecfb8b6de15ffa4fe79abbbac7e82aa20ec1e55 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 7 Aug 2020 14:29:45 -0400 Subject: [PATCH] maple_tree: Make allocations node size agnostic Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 16 ++++++++-------- lib/test_maple_tree.c | 36 ++++++++++++------------------------ 2 files changed, 20 insertions(+), 32 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 7451cc319d6e..4abaf15c3ee4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -892,16 +892,16 @@ static inline struct maple_node *mas_next_alloc(struct ma_state *ms) mn = mas_get_alloc(ms); if (cnt == 1) { ms->alloc = NULL; - } else if (cnt <= 16) { + } else if (cnt <= MAPLE_NODE_SLOTS + 1) { cnt -= 2; smn = mn->slot[cnt]; mn->slot[cnt] = NULL; mn = smn; - } else if (cnt > 16) { + } else if (cnt > MAPLE_NODE_SLOTS + 1) { cnt -= 2; - smn = mn->slot[(cnt / 15) - 1]; - mn = smn->slot[(cnt % 15)]; - smn->slot[cnt % 15] = NULL; + smn = mn->slot[(cnt / MAPLE_NODE_SLOTS) - 1]; + mn = smn->slot[(cnt % MAPLE_NODE_SLOTS)]; + smn->slot[cnt % MAPLE_NODE_SLOTS] = NULL; } return mn; @@ -916,15 +916,15 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) cnt = mas_get_alloc_cnt(mas); if (cnt == 0) { mas->alloc = reuse; - } else if (cnt <= 15) { + } else if (cnt <= MAPLE_NODE_SLOTS) { cnt--; node->slot[cnt] = reuse; } else { struct maple_node *smn; cnt--; - smn = node->slot[(cnt/15) - 1]; - smn->slot[cnt % 15] = reuse; + smn = node->slot[(cnt/MAPLE_NODE_SLOTS) - 1]; + smn->slot[cnt % MAPLE_NODE_SLOTS] = reuse; } cnt = mas_get_alloc_cnt(mas); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 389da4399f2b..1c9d8a1c5331 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -190,7 +190,7 @@ static noinline void check_new_node(struct maple_tree *mt) { struct maple_node *mn, *smn; - int cnt = 0; + int i, j, total, full_slots, cnt = 0; MA_STATE(mas, mt, 0, 0); @@ -250,41 +250,30 @@ static noinline void check_new_node(struct maple_tree *mt) mas_nomem(&mas, GFP_KERNEL); // Set allocation request to 127. - mas_node_cnt(&mas, 127); - // Drop the lock and allocate 3 nodes. + total = 127; + full_slots = (total - MAPLE_NODE_SLOTS) / MAPLE_NODE_SLOTS; + mas_node_cnt(&mas, total); + // Drop the lock and allocate 127 nodes. mas_nomem(&mas, GFP_KERNEL); mn = mas_get_alloc(&mas); MT_BUG_ON(mt, mn == NULL); cnt++; - for (int i = 0; i < 7; i++) { + for (i = 0; i < MAPLE_NODE_SLOTS; i++) { + j = 0; smn = mn->slot[i]; MT_BUG_ON(mt, smn == NULL); cnt++; - for (int j = 0; j < 15; j++) { + while ((i < full_slots) && (j < MAPLE_NODE_SLOTS)) { MT_BUG_ON(mt, smn->slot[j] == NULL); cnt++; + j++; } } - - smn = mn->slot[7]; - cnt++; - MT_BUG_ON(mt, smn == NULL); - for (int j = 0; j < 6; j++) { - MT_BUG_ON(mt, smn->slot[j] == NULL); - cnt++; - } - - for (int i = 8; i < 15; i++) { - MT_BUG_ON(mt, mn->slot[i] == NULL); - cnt++; - } - MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 127); mas_nomem(&mas, GFP_KERNEL); // Free. - MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 0); - for (int i = 1; i < 128; i++) { - int j; + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 0); + for (i = 1; i < 128; i++) { mas_node_cnt(&mas, i); // Request mas_nomem(&mas, GFP_KERNEL); // Fill request MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != i); // check request filled @@ -295,9 +284,8 @@ static noinline void check_new_node(struct maple_tree *mt) } MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 0); } - for (int i = 1; i < 128; i++) { - int j; + for (i = 1; i < 128; i++) { MA_STATE(mas2, mt, 0, 0); mas_node_cnt(&mas, i); // Request mas_nomem(&mas, GFP_KERNEL); // Fill request -- 2.50.1