Module Name: src
Committed By: riastradh
Date: Tue Oct 17 11:57:20 UTC 2023
Modified Files:
src/sys/kern: subr_thmap.c
Log Message:
thmap(9): Preallocate GC list storage for thmap_del.
thmap_del can't fail, and it is used in places in npf where sleeping
is forbidden, so it can't rely on allocating memory either.
Instead of having thmap_del allocate memory on the fly for each
object to defer freeing until thmap_gc, arrange to have thmap(9)
preallocate the same storage when allocating all the objects in the
first place, with a GC header.
This is suboptimal for memory usage, especially on insertion- and
lookup-heavy but deletion-light workloads, but it's not clear rmind's
alternative (https://github.com/rmind/thmap/tree/thmap_del_mem_fail)
is ready to use yet, so we'll go with this for correctness.
PR kern/57208
https://github.com/rmind/npf/issues/129
XXX pullup-10
XXX pullup-9
To generate a diff of this commit:
cvs rdiff -u -r1.14 -r1.15 src/sys/kern/subr_thmap.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/kern/subr_thmap.c
diff -u src/sys/kern/subr_thmap.c:1.14 src/sys/kern/subr_thmap.c:1.15
--- src/sys/kern/subr_thmap.c:1.14 Tue Oct 17 11:55:28 2023
+++ src/sys/kern/subr_thmap.c Tue Oct 17 11:57:20 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: subr_thmap.c,v 1.14 2023/10/17 11:55:28 riastradh Exp $ */
+/* $NetBSD: subr_thmap.c,v 1.15 2023/10/17 11:57:20 riastradh Exp $ */
/*-
* Copyright (c) 2018 Mindaugas Rasiukevicius <rmind at noxt eu>
@@ -112,7 +112,7 @@
#include "utils.h"
#endif
-THMAP_RCSID("$NetBSD: subr_thmap.c,v 1.14 2023/10/17 11:55:28 riastradh Exp $");
+THMAP_RCSID("$NetBSD: subr_thmap.c,v 1.15 2023/10/17 11:57:20 riastradh Exp $");
#include <crypto/blake2/blake2s.h>
@@ -212,11 +212,17 @@ typedef struct {
uint32_t hashval; // current hash value
} thmap_query_t;
-typedef struct {
- uintptr_t addr;
+union thmap_align {
+ void * p;
+ uint64_t v;
+};
+
+typedef struct thmap_gc thmap_gc_t;
+struct thmap_gc {
size_t len;
- void * next;
-} thmap_gc_t;
+ thmap_gc_t * next;
+ char data[] __aligned(sizeof(union thmap_align));
+};
#define THMAP_ROOT_LEN (sizeof(thmap_ptr_t) * ROOT_SIZE)
@@ -252,6 +258,34 @@ static const thmap_ops_t thmap_default_o
.free = free_wrapper
};
+static uintptr_t
+gc_alloc(const thmap_t *thmap, size_t len)
+{
+ const size_t alloclen = offsetof(struct thmap_gc, data[len]);
+ const uintptr_t gcaddr = thmap->ops->alloc(alloclen);
+
+ if (!gcaddr)
+ return 0;
+
+ thmap_gc_t *const gc = THMAP_GETPTR(thmap, gcaddr);
+ gc->len = len;
+ return THMAP_GETOFF(thmap, &gc->data[0]);
+}
+
+static void
+gc_free(const thmap_t *thmap, uintptr_t addr, size_t len)
+{
+ const size_t alloclen = offsetof(struct thmap_gc, data[len]);
+ char *const ptr = THMAP_GETPTR(thmap, addr);
+ thmap_gc_t *const gc = container_of(ptr, struct thmap_gc, data[0]);
+ const uintptr_t gcaddr = THMAP_GETOFF(thmap, gc);
+
+ KASSERTMSG(gc->len == len, "thmap=%p ops=%p addr=%p len=%zu"
+ " gc=%p gc->len=%zu",
+ thmap, thmap->ops, (void *)addr, len, gc, gc->len);
+ thmap->ops->free(gcaddr, alloclen);
+}
+
/*
* NODE LOCKING.
*/
@@ -395,7 +429,7 @@ node_create(thmap_t *thmap, thmap_inode_
thmap_inode_t *node;
uintptr_t p;
- p = thmap->ops->alloc(THMAP_INODE_LEN);
+ p = gc_alloc(thmap, THMAP_INODE_LEN);
if (!p) {
return NULL;
}
@@ -456,7 +490,7 @@ leaf_create(const thmap_t *thmap, const
thmap_leaf_t *leaf;
uintptr_t leaf_off, key_off;
- leaf_off = thmap->ops->alloc(sizeof(thmap_leaf_t));
+ leaf_off = gc_alloc(thmap, sizeof(thmap_leaf_t));
if (!leaf_off) {
return NULL;
}
@@ -467,9 +501,9 @@ leaf_create(const thmap_t *thmap, const
/*
* Copy the key.
*/
- key_off = thmap->ops->alloc(len);
+ key_off = gc_alloc(thmap, len);
if (!key_off) {
- thmap->ops->free(leaf_off, sizeof(thmap_leaf_t));
+ gc_free(thmap, leaf_off, sizeof(thmap_leaf_t));
return NULL;
}
memcpy(THMAP_GETPTR(thmap, key_off), key, len);
@@ -487,9 +521,9 @@ static void
leaf_free(const thmap_t *thmap, thmap_leaf_t *leaf)
{
if ((thmap->flags & THMAP_NOCOPY) == 0) {
- thmap->ops->free(leaf->key, leaf->len);
+ gc_free(thmap, leaf->key, leaf->len);
}
- thmap->ops->free(THMAP_GETOFF(thmap, leaf), sizeof(thmap_leaf_t));
+ gc_free(thmap, THMAP_GETOFF(thmap, leaf), sizeof(thmap_leaf_t));
}
static thmap_leaf_t *
@@ -547,7 +581,7 @@ root_try_put(thmap_t *thmap, const thmap
nptr = THMAP_GETOFF(thmap, node);
again:
if (atomic_load_relaxed(&thmap->root[i])) {
- thmap->ops->free(nptr, THMAP_INODE_LEN);
+ gc_free(thmap, nptr, THMAP_INODE_LEN);
return EEXIST;
}
/* Release to subsequent consume in find_edge_node(). */
@@ -927,11 +961,13 @@ thmap_del(thmap_t *thmap, const void *ke
static void
stage_mem_gc(thmap_t *thmap, uintptr_t addr, size_t len)
{
+ char *const ptr = THMAP_GETPTR(thmap, addr);
thmap_gc_t *head, *gc;
- gc = kmem_intr_alloc(sizeof(thmap_gc_t), KM_NOSLEEP);
- gc->addr = addr;
- gc->len = len;
+ gc = container_of(ptr, struct thmap_gc, data[0]);
+ KASSERTMSG(gc->len == len,
+ "thmap=%p ops=%p ptr=%p len=%zu gc=%p gc->len=%zu",
+ thmap, thmap->ops, (char *)addr, len, gc, gc->len);
retry:
head = atomic_load_relaxed(&thmap->gc_list);
gc->next = head; // not yet published
@@ -958,8 +994,7 @@ thmap_gc(thmap_t *thmap, void *ref)
while (gc) {
thmap_gc_t *next = gc->next;
- thmap->ops->free(gc->addr, gc->len);
- kmem_intr_free(gc, sizeof(thmap_gc_t));
+ gc_free(thmap, THMAP_GETOFF(thmap, &gc->data[0]), gc->len);
gc = next;
}
}
@@ -986,7 +1021,7 @@ thmap_create(uintptr_t baseptr, const th
if ((thmap->flags & THMAP_SETROOT) == 0) {
/* Allocate the root level. */
- root = thmap->ops->alloc(THMAP_ROOT_LEN);
+ root = gc_alloc(thmap, THMAP_ROOT_LEN);
if (!root) {
kmem_free(thmap, sizeof(thmap_t));
return NULL;
@@ -1026,7 +1061,7 @@ thmap_destroy(thmap_t *thmap)
thmap_gc(thmap, ref);
if ((thmap->flags & THMAP_SETROOT) == 0) {
- thmap->ops->free(root, THMAP_ROOT_LEN);
+ gc_free(thmap, root, THMAP_ROOT_LEN);
}
kmem_free(thmap, sizeof(thmap_t));
}
