Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/netbsd-9]: src/sys/kern Pull up following revision(s) (requested by rmin...



details:   https://anonhg.NetBSD.org/src/rev/d3bca1f00583
branches:  netbsd-9
changeset: 963911:d3bca1f00583
user:      martin <martin%NetBSD.org@localhost>
date:      Mon May 25 17:19:37 2020 +0000

description:
Pull up following revision(s) (requested by rmind in ticket #929):

        sys/kern/subr_thmap.c: revision 1.6

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 5a135afbfddd -r d3bca1f00583 sys/kern/subr_thmap.c
--- a/sys/kern/subr_thmap.c     Mon May 25 17:12:26 2020 +0000
+++ b/sys/kern/subr_thmap.c     Mon May 25 17:19:37 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.5.6.1 2020/05/25 17:19:37 martin 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.5.6.1 2020/05/25 17:19:37 martin 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