summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRichard Braun <rbraun@sceen.net>2013-06-09 16:47:19 +0200
committerRichard Braun <rbraun@sceen.net>2013-06-09 16:47:19 +0200
commit07d2beb0a65ef843f4ba12af7235069b14d6714c (patch)
tree04423af2861a8a1426ac1e0c8d2d40ec80f7ac57
parent9f52145cb6862582e97d3efa1b7ff9903a900b35 (diff)
kern/rdxtree: use a constructor for internal nodes
A tree node is larger than 512 bytes on a 64-bit machine. Initializing it on each allocation can get noticeably slow in case there is hysteresis.
-rw-r--r--kern/rdxtree.c41
1 files changed, 37 insertions, 4 deletions
diff --git a/kern/rdxtree.c b/kern/rdxtree.c
index ef822ac2..2944f775 100644
--- a/kern/rdxtree.c
+++ b/kern/rdxtree.c
@@ -131,6 +131,17 @@ rdxtree_node_to_entry(struct rdxtree_node *node)
return (void *)((unsigned long)node | 1);
}
+static void
+rdxtree_node_ctor(void *buf)
+{
+ struct rdxtree_node *node;
+
+ node = buf;
+ node->nr_entries = 0;
+ node->alloc_bm = RDXTREE_BM_FULL;
+ memset(node->entries, 0, sizeof(node->entries));
+}
+
static int
rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height)
{
@@ -144,9 +155,6 @@ rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height)
assert(rdxtree_check_alignment(node));
node->parent = NULL;
node->height = height;
- node->nr_entries = 0;
- node->alloc_bm = RDXTREE_BM_FULL;
- memset(node->entries, 0, sizeof(node->entries));
*nodep = node;
return 0;
}
@@ -157,6 +165,16 @@ rdxtree_node_destroy(struct work *work)
struct rdxtree_node *node;
node = structof(work, struct rdxtree_node, work);
+
+ /* See rdxtree_shrink() */
+ if (node->nr_entries != 0) {
+ assert(node->nr_entries == 1);
+ assert(node->entries[0] != NULL);
+ node->entries[0] = NULL;
+ node->nr_entries = 0;
+ node->alloc_bm = RDXTREE_BM_FULL;
+ }
+
kmem_cache_free(&rdxtree_node_cache, node);
}
@@ -307,6 +325,13 @@ rdxtree_shrink(struct rdxtree *tree)
rdxtree_node_unlink(rdxtree_entry_addr(entry));
llsync_assign_ptr(tree->root, entry);
+
+ /*
+ * There is still one valid entry (the first one) in this node. It
+ * must remain valid as long as read-side references can exist so
+ * that concurrent lookups can find the rest of the tree. Therefore,
+ * this entry isn't reset before node destruction.
+ */
rdxtree_node_schedule_destruction(node);
}
}
@@ -765,6 +790,13 @@ rdxtree_remove_all(struct rdxtree *tree)
do {
next = rdxtree_walk(tree, node);
+ /* Version of rdxtree_node_ctor() with proper pointer assignment */
+ node->nr_entries = 0;
+ node->alloc_bm = RDXTREE_BM_FULL;
+
+ for (index = 0; index < ARRAY_SIZE(node->entries); index++)
+ llsync_assign_ptr(node->entries[index], NULL);
+
parent = node->parent;
if (parent != NULL) {
@@ -785,5 +817,6 @@ void
rdxtree_setup(void)
{
kmem_cache_init(&rdxtree_node_cache, "rdxtree_node",
- sizeof(struct rdxtree_node), 0, NULL, NULL, NULL, 0);
+ sizeof(struct rdxtree_node), 0,
+ rdxtree_node_ctor, NULL, NULL, 0);
}