Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys/kern thmap(9): merge changes from the upstream -- primar...
details: https://anonhg.NetBSD.org/src/rev/71ce3e87889e
branches: trunk
changeset: 933273:71ce3e87889e
user: rmind <rmind%NetBSD.org@localhost>
date: Sat May 23 19:52:12 2020 +0000
description:
thmap(9): merge changes from the upstream -- primarily, switch to the
C11-style memory fences and atomic primitives; in NetBSD, this translates
to using the atomic_loadstore(9) primitives.
To be pulled up (just in case).
diffstat:
sys/kern/subr_thmap.c | 228 ++++++++++++++++++++++++++++++-------------------
1 files changed, 139 insertions(+), 89 deletions(-)
diffs (truncated from 525 to 300 lines):
diff -r b64dd67c849b -r 71ce3e87889e sys/kern/subr_thmap.c
--- a/sys/kern/subr_thmap.c Sat May 23 18:42:17 2020 +0000
+++ b/sys/kern/subr_thmap.c Sat May 23 19:52:12 2020 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: subr_thmap.c,v 1.5 2019/02/04 08:00:27 mrg Exp $ */
+/* $NetBSD: subr_thmap.c,v 1.6 2020/05/23 19:52:12 rmind Exp $ */
/*-
* Copyright (c) 2018 Mindaugas Rasiukevicius <rmind at noxt eu>
@@ -53,7 +53,7 @@
* re-try from the root; this is a case for deletions and is achieved
* using the NODE_DELETED flag.
*
- * iii) the node destruction must be synchronised with the readers,
+ * iii) the node destruction must be synchronized with the readers,
* e.g. by using the Epoch-based reclamation or other techniques.
*
* - WRITERS AND LOCKING: Each intermediate node has a spin-lock (which
@@ -87,7 +87,6 @@
* https://www.csd.uoc.gr/~hy460/pdf/p650-lehman.pdf
*/
-
#ifdef _KERNEL
#include <sys/cdefs.h>
#include <sys/param.h>
@@ -112,20 +111,19 @@
#include "utils.h"
#endif
-THMAP_RCSID("$NetBSD: subr_thmap.c,v 1.5 2019/02/04 08:00:27 mrg Exp $");
+THMAP_RCSID("$NetBSD: subr_thmap.c,v 1.6 2020/05/23 19:52:12 rmind Exp $");
/*
* NetBSD kernel wrappers
*/
#ifdef _KERNEL
#define ASSERT KASSERT
-#define atomic_thread_fence(x) x
-#define memory_order_stores membar_producer()
-#define memory_order_loads membar_consumer()
-#define atomic_cas_32_p(p, e, n) (atomic_cas_32((p), (e), (n)) == (e))
-#define atomic_cas_ptr_p(p, e, n) \
- (atomic_cas_ptr((p), (void *)(e), (void *)(n)) == (e))
-#define atomic_exchange atomic_swap_ptr
+#define atomic_thread_fence(x) membar_sync()
+#define atomic_compare_exchange_weak_explicit_32(p, e, n, m1, m2) \
+ (atomic_cas_32((p), *(e), (n)) == *(e))
+#define atomic_compare_exchange_weak_explicit_ptr(p, e, n, m1, m2) \
+ (atomic_cas_ptr((p), *(void **)(e), (void *)(n)) == *(void **)(e))
+#define atomic_exchange_explicit(o, n, m1) atomic_swap_ptr((o), (n))
#define murmurhash3 murmurhash2
#endif
@@ -160,6 +158,7 @@
* least significant bit.
*/
typedef uintptr_t thmap_ptr_t;
+typedef uintptr_t atomic_thmap_ptr_t; // C11 _Atomic
#define THMAP_NULL ((thmap_ptr_t)0)
@@ -188,9 +187,9 @@
*/
typedef struct {
- uint32_t state;
- thmap_ptr_t parent;
- thmap_ptr_t slots[LEVEL_SIZE];
+ uint32_t state; // C11 _Atomic
+ thmap_ptr_t parent;
+ atomic_thmap_ptr_t slots[LEVEL_SIZE];
} thmap_inode_t;
#define THMAP_INODE_LEN sizeof(thmap_inode_t)
@@ -217,11 +216,11 @@
#define THMAP_ROOT_LEN (sizeof(thmap_ptr_t) * ROOT_SIZE)
struct thmap {
- uintptr_t baseptr;
- thmap_ptr_t * root;
- unsigned flags;
- const thmap_ops_t *ops;
- thmap_gc_t * gc_list;
+ uintptr_t baseptr;
+ atomic_thmap_ptr_t * root;
+ unsigned flags;
+ const thmap_ops_t * ops;
+ thmap_gc_t * gc_list; // C11 _Atomic
};
static void stage_mem_gc(thmap_t *, uintptr_t, size_t);
@@ -253,9 +252,9 @@
#ifdef DIAGNOSTIC
static inline bool
-node_locked_p(const thmap_inode_t *node)
+node_locked_p(thmap_inode_t *node)
{
- return (node->state & NODE_LOCKED) != 0;
+ return (atomic_load_relaxed(&node->state) & NODE_LOCKED) != 0;
}
#endif
@@ -265,18 +264,14 @@
unsigned bcount = SPINLOCK_BACKOFF_MIN;
uint32_t s;
again:
- s = node->state;
+ s = atomic_load_relaxed(&node->state);
if (s & NODE_LOCKED) {
SPINLOCK_BACKOFF(bcount);
goto again;
}
- /*
- * CAS will issue a full memory fence for us.
- *
- * WARNING: for optimisations purposes, callers rely on us
- * issuing load and store fence
- */
- if (!atomic_cas_32_p(&node->state, s, s | NODE_LOCKED)) {
+ /* Acquire from prior release in unlock_node.() */
+ if (!atomic_compare_exchange_weak_explicit_32(&node->state,
+ &s, s | NODE_LOCKED, memory_order_acquire, memory_order_relaxed)) {
bcount = SPINLOCK_BACKOFF_MIN;
goto again;
}
@@ -285,11 +280,11 @@
static void
unlock_node(thmap_inode_t *node)
{
- uint32_t s = node->state & ~NODE_LOCKED;
+ uint32_t s = atomic_load_relaxed(&node->state) & ~NODE_LOCKED;
ASSERT(node_locked_p(node));
- atomic_thread_fence(memory_order_stores);
- node->state = s; // atomic store
+ /* Release to subsequent acquire in lock_node(). */
+ atomic_store_release(&node->state, s);
}
/*
@@ -375,7 +370,8 @@
memset(node, 0, THMAP_INODE_LEN);
if (parent) {
- node->state = NODE_LOCKED;
+ /* Not yet published, no need for ordering. */
+ atomic_store_relaxed(&node->state, NODE_LOCKED);
node->parent = THMAP_GETOFF(thmap, parent);
}
return node;
@@ -385,27 +381,35 @@
node_insert(thmap_inode_t *node, unsigned slot, thmap_ptr_t child)
{
ASSERT(node_locked_p(node) || node->parent == THMAP_NULL);
- ASSERT((node->state & NODE_DELETED) == 0);
- ASSERT(node->slots[slot] == THMAP_NULL);
+ ASSERT((atomic_load_relaxed(&node->state) & NODE_DELETED) == 0);
+ ASSERT(atomic_load_relaxed(&node->slots[slot]) == THMAP_NULL);
+
+ ASSERT(NODE_COUNT(atomic_load_relaxed(&node->state)) < LEVEL_SIZE);
- ASSERT(NODE_COUNT(node->state) < LEVEL_SIZE);
-
- node->slots[slot] = child;
- node->state++;
+ /*
+ * If node is public already, caller is responsible for issuing
+ * release fence; if node is not public, no ordering is needed.
+ * Hence relaxed ordering.
+ */
+ atomic_store_relaxed(&node->slots[slot], child);
+ atomic_store_relaxed(&node->state,
+ atomic_load_relaxed(&node->state) + 1);
}
static void
node_remove(thmap_inode_t *node, unsigned slot)
{
ASSERT(node_locked_p(node));
- ASSERT((node->state & NODE_DELETED) == 0);
- ASSERT(node->slots[slot] != THMAP_NULL);
+ ASSERT((atomic_load_relaxed(&node->state) & NODE_DELETED) == 0);
+ ASSERT(atomic_load_relaxed(&node->slots[slot]) != THMAP_NULL);
- ASSERT(NODE_COUNT(node->state) > 0);
- ASSERT(NODE_COUNT(node->state) <= LEVEL_SIZE);
+ ASSERT(NODE_COUNT(atomic_load_relaxed(&node->state)) > 0);
+ ASSERT(NODE_COUNT(atomic_load_relaxed(&node->state)) <= LEVEL_SIZE);
- node->slots[slot] = THMAP_NULL;
- node->state--;
+ /* Element will be GC-ed later; no need for ordering here. */
+ atomic_store_relaxed(&node->slots[slot], THMAP_NULL);
+ atomic_store_relaxed(&node->state,
+ atomic_load_relaxed(&node->state) - 1);
}
/*
@@ -459,7 +463,8 @@
{
thmap_ptr_t node;
- node = parent->slots[slot];
+ /* Consume from prior release in thmap_put(). */
+ node = atomic_load_consume(&parent->slots[slot]);
if (THMAP_INODE_P(node)) {
return NULL;
}
@@ -470,36 +475,48 @@
* ROOT OPERATIONS.
*/
+/*
+ * root_try_put: Try to set a root pointer at query->rslot.
+ *
+ * => Implies release operation on success.
+ * => Implies no ordering on failure.
+ */
static inline bool
root_try_put(thmap_t *thmap, const thmap_query_t *query, thmap_leaf_t *leaf)
{
+ thmap_ptr_t expected;
const unsigned i = query->rslot;
thmap_inode_t *node;
thmap_ptr_t nptr;
unsigned slot;
/*
- * Must pre-check first.
+ * Must pre-check first. No ordering required because we will
+ * check again before taking any actions, and start over if
+ * this changes from null.
*/
- if (thmap->root[i]) {
+ if (atomic_load_relaxed(&thmap->root[i])) {
return false;
}
/*
* Create an intermediate node. Since there is no parent set,
- * it will be created unlocked and the CAS operation will issue
- * the store memory fence for us.
+ * it will be created unlocked and the CAS operation will
+ * release it to readers.
*/
node = node_create(thmap, NULL);
slot = hashval_getl0slot(thmap, query, leaf);
node_insert(node, slot, THMAP_GETOFF(thmap, leaf) | THMAP_LEAF_BIT);
nptr = THMAP_GETOFF(thmap, node);
again:
- if (thmap->root[i]) {
+ if (atomic_load_relaxed(&thmap->root[i])) {
thmap->ops->free(nptr, THMAP_INODE_LEN);
return false;
}
- if (!atomic_cas_ptr_p(&thmap->root[i], NULL, nptr)) {
+ /* Release to subsequent consume in find_edge_node(). */
+ expected = THMAP_NULL;
+ if (!atomic_compare_exchange_weak_explicit_ptr(&thmap->root[i], &expected,
+ nptr, memory_order_release, memory_order_relaxed)) {
goto again;
}
return true;
@@ -515,23 +532,23 @@
find_edge_node(const thmap_t *thmap, thmap_query_t *query,
const void * restrict key, size_t len, unsigned *slot)
{
- thmap_ptr_t root_slot = thmap->root[query->rslot];
+ thmap_ptr_t root_slot;
thmap_inode_t *parent;
thmap_ptr_t node;
unsigned off;
ASSERT(query->level == 0);
+ /* Consume from prior release in root_try_put(). */
+ root_slot = atomic_load_consume(&thmap->root[query->rslot]);
parent = THMAP_NODE(thmap, root_slot);
if (!parent) {
return NULL;
}
descend:
off = hashval_getslot(query, key, len);
- node = parent->slots[off];
-
- /* Ensure the parent load happens before the child load. */
- atomic_thread_fence(memory_order_loads);
+ /* Consume from prior release in thmap_put(). */
+ node = atomic_load_consume(&parent->slots[off]);
/* Descend the tree until we find a leaf or empty slot. */
if (node && THMAP_INODE_P(node)) {
@@ -539,7 +556,12 @@
query->level++;
goto descend;
}
- if (parent->state & NODE_DELETED) {
+ /*
Home |
Main Index |
Thread Index |
Old Index