v21-0017-Remove-some-maintenance-hazards-in-growing-nodes.patch

From 5c577598bc1f667333c97dca70155df6d296c251 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
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