From 5c577598bc1f667333c97dca70155df6d296c251 Mon Sep 17 00:00:00 2001 From: John Naylor Date: Sun, 22 Jan 2023 13:29:18 +0700 Subject: [PATCH v21 17/22] Remove some maintenance hazards in growing nodes Arrange so that kinds with only one size class have no "full" suffix. This ensures that splitting such a class into multiple classes will force compilation errors if the dev has not thought through which new class should apply in each case. For node32, make growing into a new size class a bit more general. It's not clear we would ever need more than 2 classes, but let's not put up additional road blocks. Change partial/full to min/max. It's a bit shorter this way, matches some newer coding, and allows for the possibility of a "mid" class. Also remove RT_KIND_MIN_SIZE_CLASS, since it doesn't reduce the need for future changes, only makes such a change further away from the effect. In passing, move a declaration the block where it's used. --- src/include/lib/radixtree.h | 66 +++++++++++-------------- src/include/lib/radixtree_insert_impl.h | 16 +++--- 2 files changed, 37 insertions(+), 45 deletions(-) diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index cd8b8d1c22..7c3f3dcf4f 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -196,12 +196,11 @@ #define RT_SIZE_CLASS RT_MAKE_NAME(size_class) #define RT_SIZE_CLASS_ELEM RT_MAKE_NAME(size_class_elem) #define RT_SIZE_CLASS_INFO RT_MAKE_NAME(size_class_info) -#define RT_CLASS_3_FULL RT_MAKE_NAME(class_3_full) -#define RT_CLASS_32_PARTIAL RT_MAKE_NAME(class_32_partial) -#define RT_CLASS_32_FULL RT_MAKE_NAME(class_32_full) -#define RT_CLASS_125_FULL RT_MAKE_NAME(class_125_full) +#define RT_CLASS_3 RT_MAKE_NAME(class_3) +#define RT_CLASS_32_MIN RT_MAKE_NAME(class_32_min) +#define RT_CLASS_32_MAX RT_MAKE_NAME(class_32_max) +#define RT_CLASS_125 RT_MAKE_NAME(class_125) #define RT_CLASS_256 RT_MAKE_NAME(class_256) -#define RT_KIND_MIN_SIZE_CLASS RT_MAKE_NAME(kind_min_size_class) /* generate forward declarations necessary to use the radix tree */ #ifdef RT_DECLARE @@ -523,10 +522,10 @@ typedef struct RT_NODE_LEAF_256 */ typedef enum RT_SIZE_CLASS { - RT_CLASS_3_FULL = 0, - RT_CLASS_32_PARTIAL, - RT_CLASS_32_FULL, - RT_CLASS_125_FULL, + RT_CLASS_3 = 0, + RT_CLASS_32_MIN, + RT_CLASS_32_MAX, + RT_CLASS_125, RT_CLASS_256 } RT_SIZE_CLASS; @@ -542,25 +541,25 @@ typedef struct RT_SIZE_CLASS_ELEM } RT_SIZE_CLASS_ELEM; static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = { - [RT_CLASS_3_FULL] = { + [RT_CLASS_3] = { .name = "radix tree node 3", .fanout = 3, .inner_size = sizeof(RT_NODE_INNER_3) + 3 * sizeof(RT_PTR_ALLOC), .leaf_size = sizeof(RT_NODE_LEAF_3) + 3 * sizeof(RT_VALUE_TYPE), }, - [RT_CLASS_32_PARTIAL] = { + [RT_CLASS_32_MIN] = { .name = "radix tree node 15", .fanout = 15, .inner_size = sizeof(RT_NODE_INNER_32) + 15 * sizeof(RT_PTR_ALLOC), .leaf_size = sizeof(RT_NODE_LEAF_32) + 15 * sizeof(RT_VALUE_TYPE), }, - [RT_CLASS_32_FULL] = { + [RT_CLASS_32_MAX] = { .name = "radix tree node 32", .fanout = 32, .inner_size = sizeof(RT_NODE_INNER_32) + 32 * sizeof(RT_PTR_ALLOC), .leaf_size = sizeof(RT_NODE_LEAF_32) + 32 * sizeof(RT_VALUE_TYPE), }, - [RT_CLASS_125_FULL] = { + [RT_CLASS_125] = { .name = "radix tree node 125", .fanout = 125, .inner_size = sizeof(RT_NODE_INNER_125) + 125 * sizeof(RT_PTR_ALLOC), @@ -576,14 +575,6 @@ static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = { #define RT_SIZE_CLASS_COUNT lengthof(RT_SIZE_CLASS_INFO) -/* Map from the node kind to its minimum size class */ -static const RT_SIZE_CLASS RT_KIND_MIN_SIZE_CLASS[RT_NODE_KIND_COUNT] = { - [RT_NODE_KIND_3] = RT_CLASS_3_FULL, - [RT_NODE_KIND_32] = RT_CLASS_32_PARTIAL, - [RT_NODE_KIND_125] = RT_CLASS_125_FULL, - [RT_NODE_KIND_256] = RT_CLASS_256, -}; - #ifdef RT_SHMEM /* A magic value used to identify our radix tree */ #define RT_RADIX_TREE_MAGIC 0x54A48167 @@ -893,7 +884,7 @@ static inline void RT_CHUNK_CHILDREN_ARRAY_COPY(uint8 *src_chunks, RT_PTR_ALLOC *src_children, uint8 *dst_chunks, RT_PTR_ALLOC *dst_children) { - const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_FULL].fanout; + const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3].fanout; const Size chunk_size = sizeof(uint8) * fanout; const Size children_size = sizeof(RT_PTR_ALLOC) * fanout; @@ -905,7 +896,7 @@ static inline void RT_CHUNK_VALUES_ARRAY_COPY(uint8 *src_chunks, RT_VALUE_TYPE *src_values, uint8 *dst_chunks, RT_VALUE_TYPE *dst_values) { - const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_FULL].fanout; + const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3].fanout; const Size chunk_size = sizeof(uint8) * fanout; const Size values_size = sizeof(RT_VALUE_TYPE) * fanout; @@ -1105,9 +1096,9 @@ RT_NEW_ROOT(RT_RADIX_TREE *tree, uint64 key) RT_PTR_ALLOC allocnode; RT_PTR_LOCAL newnode; - allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, inner); + allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3, inner); newnode = RT_PTR_GET_LOCAL(tree, allocnode); - RT_INIT_NODE(newnode, RT_NODE_KIND_3, RT_CLASS_3_FULL, inner); + RT_INIT_NODE(newnode, RT_NODE_KIND_3, RT_CLASS_3, inner); newnode->shift = shift; tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(shift); tree->ctl->root = allocnode; @@ -1230,9 +1221,9 @@ RT_EXTEND(RT_RADIX_TREE *tree, uint64 key) RT_PTR_LOCAL node; RT_NODE_INNER_3 *n3; - allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, true); + allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3, true); node = RT_PTR_GET_LOCAL(tree, allocnode); - RT_INIT_NODE(node, RT_NODE_KIND_3, RT_CLASS_3_FULL, true); + RT_INIT_NODE(node, RT_NODE_KIND_3, RT_CLASS_3, true); node->shift = shift; node->count = 1; @@ -1268,9 +1259,9 @@ RT_SET_EXTEND(RT_RADIX_TREE *tree, uint64 key, RT_VALUE_TYPE value, RT_PTR_LOCAL int newshift = shift - RT_NODE_SPAN; bool inner = newshift > 0; - allocchild = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, inner); + allocchild = RT_ALLOC_NODE(tree, RT_CLASS_3, inner); newchild = RT_PTR_GET_LOCAL(tree, allocchild); - RT_INIT_NODE(newchild, RT_NODE_KIND_3, RT_CLASS_3_FULL, inner); + RT_INIT_NODE(newchild, RT_NODE_KIND_3, RT_CLASS_3, inner); newchild->shift = newshift; RT_NODE_INSERT_INNER(tree, parent, stored_node, node, key, allocchild); @@ -2007,10 +1998,10 @@ RT_STATS(RT_RADIX_TREE *tree) ereport(NOTICE, (errmsg("num_keys = " UINT64_FORMAT ", height = %d, n3 = %u, n15 = %u, n32 = %u, n125 = %u, n256 = %u", tree->ctl->num_keys, tree->ctl->root->shift / RT_NODE_SPAN, - tree->ctl->cnt[RT_CLASS_3_FULL], - tree->ctl->cnt[RT_CLASS_32_PARTIAL], - tree->ctl->cnt[RT_CLASS_32_FULL], - tree->ctl->cnt[RT_CLASS_125_FULL], + tree->ctl->cnt[RT_CLASS_3], + tree->ctl->cnt[RT_CLASS_32_MIN], + tree->ctl->cnt[RT_CLASS_32_MAX], + tree->ctl->cnt[RT_CLASS_125], tree->ctl->cnt[RT_CLASS_256]))); } @@ -2292,12 +2283,11 @@ RT_DUMP(RT_RADIX_TREE *tree) #undef RT_SIZE_CLASS #undef RT_SIZE_CLASS_ELEM #undef RT_SIZE_CLASS_INFO -#undef RT_CLASS_3_FULL -#undef RT_CLASS_32_PARTIAL -#undef RT_CLASS_32_FULL -#undef RT_CLASS_125_FULL +#undef RT_CLASS_3 +#undef RT_CLASS_32_MIN +#undef RT_CLASS_32_MAX +#undef RT_CLASS_125 #undef RT_CLASS_256 -#undef RT_KIND_MIN_SIZE_CLASS /* function declarations */ #undef RT_CREATE diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h index a0f46b37d3..e3c3f7a69d 100644 --- a/src/include/lib/radixtree_insert_impl.h +++ b/src/include/lib/radixtree_insert_impl.h @@ -49,7 +49,7 @@ RT_PTR_LOCAL newnode; RT_NODE32_TYPE *new32; const uint8 new_kind = RT_NODE_KIND_32; - const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind]; + const RT_SIZE_CLASS new_class = RT_CLASS_32_MIN; /* grow node from 3 to 32 */ allocnode = RT_ALLOC_NODE(tree, new_class, inner); @@ -96,8 +96,7 @@ /* FALLTHROUGH */ case RT_NODE_KIND_32: { - const RT_SIZE_CLASS_ELEM class32_min = RT_SIZE_CLASS_INFO[RT_CLASS_32_PARTIAL]; - const RT_SIZE_CLASS_ELEM class32_max = RT_SIZE_CLASS_INFO[RT_CLASS_32_FULL]; + const RT_SIZE_CLASS_ELEM class32_max = RT_SIZE_CLASS_INFO[RT_CLASS_32_MAX]; RT_NODE32_TYPE *n32 = (RT_NODE32_TYPE *) node; int idx; @@ -115,11 +114,14 @@ } if (unlikely(RT_NODE_MUST_GROW(n32)) && - n32->base.n.fanout == class32_min.fanout) + n32->base.n.fanout < class32_max.fanout) { RT_PTR_ALLOC allocnode; RT_PTR_LOCAL newnode; - const RT_SIZE_CLASS new_class = RT_CLASS_32_FULL; + const RT_SIZE_CLASS_ELEM class32_min = RT_SIZE_CLASS_INFO[RT_CLASS_32_MIN]; + const RT_SIZE_CLASS new_class = RT_CLASS_32_MAX; + + Assert(n32->base.n.fanout == class32_min.fanout); /* grow to the next size class of this kind */ allocnode = RT_ALLOC_NODE(tree, new_class, inner); @@ -143,7 +145,7 @@ RT_PTR_LOCAL newnode; RT_NODE125_TYPE *new125; const uint8 new_kind = RT_NODE_KIND_125; - const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind]; + const RT_SIZE_CLASS new_class = RT_CLASS_125; Assert(n32->base.n.fanout == class32_max.fanout); @@ -224,7 +226,7 @@ RT_PTR_LOCAL newnode; RT_NODE256_TYPE *new256; const uint8 new_kind = RT_NODE_KIND_256; - const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind]; + const RT_SIZE_CLASS new_class = RT_CLASS_256; /* grow node from 125 to 256 */ allocnode = RT_ALLOC_NODE(tree, new_class, inner); -- 2.39.0