 @@ -1,14 +1,14 @@
-/*	$NetBSD: radixtree.c,v 1.23 2020/01/28 22:20:45 ad Exp $	*/
+/*	$NetBSD: radixtree.c,v 1.24 2020/04/10 21:56:41 ad Exp $	*/
 /*-
  * Copyright (c)2011,2012,2013 YAMAMOTO Takashi,
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
 @@ -102,37 +102,37 @@
  * leaf nodes with the given tag.  To reduce amount of nodes to visit for
  * these functions, this implementation keeps tagging information in internal
  * intermediate nodes and quickly skips uninterested parts of a tree.
+ *
  * A tree has RADIX_TREE_TAG_ID_MAX independent tag spaces, each of which are
  * identified by an zero-origin numbers, tagid.  For the current implementation,
  * RADIX_TREE_TAG_ID_MAX is 2.  A set of tags is described as a bitmask tagmask,
  * which is a bitwise OR of (1 << tagid).
  */
 #include <sys/cdefs.h>
 #if defined(_KERNEL) || defined(_STANDALONE)
-__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.23 2020/01/28 22:20:45 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.24 2020/04/10 21:56:41 ad Exp $");
 #include <sys/param.h>
 #include <sys/errno.h>
 #include <sys/pool.h>
 #include <sys/radixtree.h>
 #include <lib/libkern/libkern.h>
 #if defined(_STANDALONE)
 #include <lib/libsa/stand.h>
 #endif /* defined(_STANDALONE) */
 #else /* defined(_KERNEL) || defined(_STANDALONE) */
-__RCSID("$NetBSD: radixtree.c,v 1.23 2020/01/28 22:20:45 ad Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.24 2020/04/10 21:56:41 ad Exp $");
 #include <assert.h>
 #include <errno.h>
 #include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #if 1
 #define KASSERT assert
 #else
 #define KASSERT(a)	/* nothing */
 #endif
 #endif /* defined(_KERNEL) || defined(_STANDALONE) */
 #include <sys/radixtree.h>
 @@ -188,45 +188,26 @@ entry_match_p(void *p, unsigned int tagm
+ *
  * we used to maintain a count of non-NULL nodes in this structure, but it
  * prevented it from being aligned to a cache line boundary; the performance
  * benefit from being cache friendly is greater than the benefit of having
  * a dedicated count value, especially in multi-processor situations where
  * we need to avoid intra-pool-page false sharing.
  */
 struct radix_tree_node {
 	void *n_ptrs[RADIX_TREE_PTR_PER_NODE];
 };
 /*
  * any_children_tagmask:
  * return OR'ed tagmask of the given node's children.
  */
 static unsigned int
 any_children_tagmask(const struct radix_tree_node *n)
 	unsigned int mask;
 	int i;
 	mask = 0;
 	for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
 		mask |= (unsigned int)(uintptr_t)n->n_ptrs[i];
 	return mask & RADIX_TREE_TAG_MASK;
 /*
  * p_refs[0].pptr == &t->t_root
  *	:
  * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x]
  *	:
  *	:
  * p_refs[t->t_height].pptr == &leaf_pointer
  */
 struct radix_tree_path {
 	struct radix_tree_node_ref {
 		void **pptr;
 	} p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */
 	/*
 @@ -358,38 +339,44 @@ radix_tree_init(void)
  */
 void
 radix_tree_await_memory(void)
+{
 	struct radix_tree_node *n;
 	n = pool_cache_get(radix_tree_node_cache, PR_WAITOK);
 	pool_cache_put(radix_tree_node_cache, n);
+}
 #endif /* defined(_KERNEL) */
-static bool __unused
+/*
-radix_tree_node_clean_p(const struct radix_tree_node *n)
+ * radix_tree_node_sum:
+ *
  * return the logical sum of all entries in the given node.  used to quickly
  * check for tag masks or empty nodes.
  */
 static uintptr_t
 radix_tree_node_sum(const struct radix_tree_node *n)
+{
 #if RADIX_TREE_PTR_PER_NODE > 16
-	unsigned int i;
+	uintptr_t sum;
 	unsigned i;
-	for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
+	for (i = 0, sum = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
-		if (n->n_ptrs[i] != NULL) {
+		sum |= (uintptr_t)n->n_ptrs[i];
 			return false;
+	}
-	return true;
+	return sum;
 #else /* RADIX_TREE_PTR_PER_NODE > 16 */
 	uintptr_t sum;
 	/*
 	 * Unrolling the above is much better than a tight loop with two
 	 * test+branch pairs.  On x86 with gcc 5.5.0 this compiles into 19
 	 * deterministic instructions including the "return" and prologue &
 	 * epilogue.
 	 */
 	sum = (uintptr_t)n->n_ptrs[0];
 	sum |= (uintptr_t)n->n_ptrs[1];
 	sum |= (uintptr_t)n->n_ptrs[2];
 	sum |= (uintptr_t)n->n_ptrs[3];
 @@ -399,27 +386,27 @@ radix_tree_node_clean_p(const struct rad
 	sum |= (uintptr_t)n->n_ptrs[6];
 	sum |= (uintptr_t)n->n_ptrs[7];
 #endif
 #if RADIX_TREE_PTR_PER_NODE > 8
 	sum |= (uintptr_t)n->n_ptrs[8];
 	sum |= (uintptr_t)n->n_ptrs[9];
 	sum |= (uintptr_t)n->n_ptrs[10];
 	sum |= (uintptr_t)n->n_ptrs[11];
 	sum |= (uintptr_t)n->n_ptrs[12];
 	sum |= (uintptr_t)n->n_ptrs[13];
 	sum |= (uintptr_t)n->n_ptrs[14];
 	sum |= (uintptr_t)n->n_ptrs[15];
 #endif
-	return sum == 0;
+	return sum;
 #endif /* RADIX_TREE_PTR_PER_NODE > 16 */
+}
 static int __unused
 radix_tree_node_count_ptrs(const struct radix_tree_node *n)
+{
 	unsigned int i, c;
 	for (i = c = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
 		c += (n->n_ptrs[i] != NULL);
+	}
 	return c;
+}
 @@ -434,35 +421,35 @@ radix_tree_alloc_node(void)
 	 * note that pool_cache_get can block.
 	 */
 	n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT);
 #else /* defined(_KERNEL) */
 #if defined(_STANDALONE)
 	n = alloc(sizeof(*n));
 #else /* defined(_STANDALONE) */
 	n = malloc(sizeof(*n));
 #endif /* defined(_STANDALONE) */
 	if (n != NULL) {
 		radix_tree_node_init(n);
+	}
 #endif /* defined(_KERNEL) */
-	KASSERT(n == NULL || radix_tree_node_clean_p(n));
+	KASSERT(n == NULL || radix_tree_node_sum(n) == 0);
 	return n;
+}
 static void
 radix_tree_free_node(struct radix_tree_node *n)
+{
-	KASSERT(radix_tree_node_clean_p(n));
+	KASSERT(radix_tree_node_sum(n) == 0);
 #if defined(_KERNEL)
 	pool_cache_put(radix_tree_node_cache, n);
 #elif defined(_STANDALONE)
 	dealloc(n, sizeof(*n));
 #else
 	free(n);
 #endif
+}
 static int
 radix_tree_grow(struct radix_tree *t, unsigned int newheight)
+{
 	const unsigned int tagmask = entry_tagmask(t->t_root);
 @@ -677,55 +664,55 @@ radix_tree_remove_node(struct radix_tree
 	KASSERT(path.p_lastidx == t->t_height);
 	KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
 	*vpp = NULL;
 	for (i = t->t_height - 1; i >= 0; i--) {
 		void *entry;
 		struct radix_tree_node ** const pptr =
 		    (struct radix_tree_node **)path_pptr(t, &path, i);
 		struct radix_tree_node *n;
 		KASSERT(pptr != NULL);
 		entry = *pptr;
 		n = entry_ptr(entry);
 		KASSERT(n != NULL);
-		if (!radix_tree_node_clean_p(n)) {
+		if (radix_tree_node_sum(n) != 0) {
 			break;
+		}
 		radix_tree_free_node(n);
 		*pptr = NULL;
+	}
 	/*
 	 * fix up height
 	 */
 	if (i < 0) {
 		KASSERT(t->t_root == NULL);
 		t->t_height = 0;
+	}
 	/*
 	 * update tags
 	 */
 	for (; i >= 0; i--) {
 		void *entry;
 		struct radix_tree_node ** const pptr =
 		    (struct radix_tree_node **)path_pptr(t, &path, i);
 		struct radix_tree_node *n;
 		unsigned int newmask;
 		KASSERT(pptr != NULL);
 		entry = *pptr;
 		n = entry_ptr(entry);
 		KASSERT(n != NULL);
-		KASSERT(!radix_tree_node_clean_p(n));
+		KASSERT(radix_tree_node_sum(n) != 0);
-		newmask = any_children_tagmask(n);
+		newmask = radix_tree_node_sum(n) & RADIX_TREE_TAG_MASK;
 		if (newmask == entry_tagmask(entry)) {
 			break;
+		}
 		*pptr = entry_compose(n, newmask);
+	}
 	/*
 	 * XXX is it worth to try to reduce height?
 	 * if we do that, make radix_tree_grow rollback its change as well.
 	 */
 	return entry_ptr(oldp);
+}
 /*
 @@ -1081,27 +1068,27 @@ radix_tree_clear_tag(struct radix_tree *
 		void *entry;
 		KASSERT(pptr != NULL);
 		entry = *pptr;
 		KASSERT((entry_tagmask(entry) & tagmask) != 0);
 		*pptr = entry_compose(entry_ptr(entry),
 		    entry_tagmask(entry) & ~tagmask);
 		/*
 		 * check if we should proceed to process the next level.
 		 */
 		if (0 < i) {
 			struct radix_tree_node *n = path_node(t, &path, i - 1);
-			if ((any_children_tagmask(n) & tagmask) != 0) {
+			if ((radix_tree_node_sum(n) & tagmask) != 0) {
 				break;
+			}
+		}
+	}
+}
 #if defined(UNITTEST)
 #include <inttypes.h>
 #include <stdio.h>
 static void
 radix_tree_dump_node(const struct radix_tree *t, void *vp,
 @@ -1114,27 +1101,28 @@ radix_tree_dump_node(const struct radix_
 		printf(" ");
+	}
 	if (entry_tagmask(vp) == 0) {
 		printf("[%" PRIu64 "] %p", offset, entry_ptr(vp));
 	} else {
 		printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp),
 		    entry_tagmask(vp));
+	}
 	if (height == 0) {
 		printf(" (leaf)\n");
 		return;
+	}
 	n = entry_ptr(vp);
-	assert(any_children_tagmask(n) == entry_tagmask(vp));
+	assert((radix_tree_node_sum(n) & RADIX_TREE_TAG_MASK) ==
 	    entry_tagmask(vp));
 	printf(" (%u children)\n", radix_tree_node_count_ptrs(n));
 	for (i = 0; i < __arraycount(n->n_ptrs); i++) {
 		void *c;
 		c = n->n_ptrs[i];
 		if (c == NULL) {
 			continue;
+		}
 		radix_tree_dump_node(t, c,
 		    offset + i * (UINT64_C(1) <<
 		    (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1);
+	}
+}