Index: art.c =================================================================== RCS file: /cvs/src/sys/net/art.c,v retrieving revision 1.29 diff -u -p -r1.29 art.c --- art.c 12 Nov 2020 15:25:28 -0000 1.29 +++ art.c 9 Mar 2021 11:58:58 -0000 @@ -33,6 +33,7 @@ #include #include #include +#include #endif #include @@ -42,32 +43,25 @@ void art_allot(struct art_table *at, struct art_node *); struct art_table *art_table_get(struct art_root *, struct art_table *, int); -struct art_table *art_table_put(struct art_root *, struct art_table *); +struct art_table *art_table_put(struct art_root *, struct art_table *, + struct art_garbage *); struct art_node *art_table_insert(struct art_root *, struct art_table *, int, struct art_node *); struct art_node *art_table_delete(struct art_root *, struct art_table *, - int, struct art_node *); + int, struct art_node *, struct art_garbage *); struct art_table *art_table_ref(struct art_root *, struct art_table *); -int art_table_free(struct art_root *, struct art_table *); +int art_table_free(struct art_root *, struct art_table *, + struct art_garbage *); int art_table_walk(struct art_root *, struct art_table *, + struct art_garbage *, int (*f)(struct art_node *, void *), void *); int art_walk_apply(struct art_root *, struct art_node *, struct art_node *, int (*f)(struct art_node *, void *), void *); -void art_table_gc(void *); -void art_gc(void *); +void art_table_gc(struct art_table *); struct pool an_pool, at_pool, at_heap_4_pool, at_heap_8_pool; -struct art_table *art_table_gc_list = NULL; -struct mutex art_table_gc_mtx = MUTEX_INITIALIZER(IPL_SOFTNET); -struct task art_table_gc_task = - TASK_INITIALIZER(art_table_gc, NULL); - -struct art_node *art_node_gc_list = NULL; -struct mutex art_node_gc_mtx = MUTEX_INITIALIZER(IPL_SOFTNET); -struct task art_node_gc_task = TASK_INITIALIZER(art_gc, NULL); - void art_init(void) { @@ -215,60 +209,35 @@ art_findex(struct art_table *at, uint8_t * Return the best existing match for a destination. */ struct art_node * -art_match(struct art_root *ar, void *addr, struct srp_ref *nsr) +art_match(struct art_root *ar, void *addr) { - struct srp_ref dsr, ndsr; - void *entry; + struct art_node *node; struct art_table *at; - struct art_node *dflt, *ndflt; + struct art_node *dflt = NULL, *ndflt; int j; - - entry = srp_enter(nsr, &ar->ar_root); - at = entry; - - if (at == NULL) - goto done; - - /* - * Remember the default route of each table we visit in case - * we do not find a better matching route. - */ - dflt = srp_enter(&dsr, &at->at_default); - + /* * Iterate until we find a leaf. */ - while (1) { + for (at = SMR_PTR_GET(&ar->ar_root); at != NULL; at = SUBTABLE(node)) { /* Do a single level route lookup. */ j = art_findex(at, addr); - entry = srp_follow(nsr, &at->at_heap[j].node); + node = SMR_PTR_GET(&at->at_heap[j].node); /* If this is a leaf (NULL is a leaf) we're done. */ - if (ISLEAF(entry)) - break; - - at = SUBTABLE(entry); - - ndflt = srp_enter(&ndsr, &at->at_default); - if (ndflt != NULL) { - srp_leave(&dsr); - dsr = ndsr; + if (ISLEAF(node)) + return (node); + + /* + * Rember the default route of this table in case + * we do not find a better matching route. + */ + ndflt = SMR_PTR_GET(&at->at_default); + if (ndflt != NULL) dflt = ndflt; - } else - srp_leave(&ndsr); } - - if (entry == NULL) { - srp_leave(nsr); - *nsr = dsr; - KASSERT(ISLEAF(dflt)); - return (dflt); - } - - srp_leave(&dsr); -done: - KASSERT(ISLEAF(entry)); - return (entry); + + return (dflt); } /* @@ -278,25 +247,21 @@ done: * it does not exist. */ struct art_node * -art_lookup(struct art_root *ar, void *addr, int plen, struct srp_ref *nsr) +art_lookup(struct art_root *ar, void *addr, int plen) { - void *entry; + struct art_node *node; struct art_table *at; int i, j; - + KASSERT(plen >= 0 && plen <= ar->ar_alen); - entry = srp_enter(nsr, &ar->ar_root); - at = entry; - + at = SMR_PTR_GET(&ar->ar_root); if (at == NULL) - goto done; - + return (NULL); + /* Default route */ - if (plen == 0) { - entry = srp_follow(nsr, &at->at_default); - goto done; - } + if (plen == 0) + return (SMR_PTR_GET(&at->at_default)); /* * If the prefix length is smaller than the sum of @@ -306,26 +271,26 @@ art_lookup(struct art_root *ar, void *ad while (plen > (at->at_offset + at->at_bits)) { /* Do a single level route lookup. */ j = art_findex(at, addr); - entry = srp_follow(nsr, &at->at_heap[j].node); + node = SMR_PTR_GET(&at->at_heap[j].node); /* A leaf is a match, but not a perfect one, or NULL */ - if (ISLEAF(entry)) + if (ISLEAF(node)) return (NULL); - at = SUBTABLE(entry); + at = SUBTABLE(node); } i = art_bindex(at, addr, plen); if (i == -1) return (NULL); - entry = srp_follow(nsr, &at->at_heap[i].node); - if (!ISLEAF(entry)) - entry = srp_follow(nsr, &SUBTABLE(entry)->at_default); - -done: - KASSERT(ISLEAF(entry)); - return (entry); + node = SMR_PTR_GET(&at->at_heap[i].node); + if (!ISLEAF(node)) { + at = SUBTABLE(node); + node = SMR_PTR_GET(&at->at_default); + } + + return (node); } @@ -345,23 +310,23 @@ art_insert(struct art_root *ar, struct a rw_assert_wrlock(&ar->ar_lock); KASSERT(plen >= 0 && plen <= ar->ar_alen); - at = srp_get_locked(&ar->ar_root); + at = SMR_PTR_GET_LOCKED(&ar->ar_root); if (at == NULL) { at = art_table_get(ar, NULL, -1); if (at == NULL) return (NULL); - srp_swap_locked(&ar->ar_root, at); + SMR_PTR_SET_LOCKED(&ar->ar_root, at); } /* Default route */ if (plen == 0) { - node = srp_get_locked(&at->at_default); + node = SMR_PTR_GET_LOCKED(&at->at_default); if (node != NULL) return (node); art_table_ref(ar, at); - srp_swap_locked(&at->at_default, an); + SMR_PTR_SET_LOCKED(&at->at_default, an); return (an); } @@ -373,7 +338,7 @@ art_insert(struct art_root *ar, struct a while (plen > (at->at_offset + at->at_bits)) { /* Do a single level route lookup. */ j = art_findex(at, addr); - node = srp_get_locked(&at->at_heap[j].node); + node = SMR_PTR_GET_LOCKED(&at->at_heap[j].node); /* * If the node corresponding to the fringe index is @@ -387,7 +352,7 @@ art_insert(struct art_root *ar, struct a return (NULL); art_table_ref(ar, at); - srp_swap_locked(&at->at_heap[j].node, ASNODE(child)); + SMR_PTR_SET_LOCKED(&at->at_heap[j].node, ASNODE(child)); at = child; } else at = SUBTABLE(node); @@ -407,16 +372,18 @@ struct art_node * art_table_insert(struct art_root *ar, struct art_table *at, int i, struct art_node *an) { - struct art_node *prev, *node; + struct art_node **slot; + struct art_node *node; - node = srp_get_locked(&at->at_heap[i].node); - if (!ISLEAF(node)) - prev = srp_get_locked(&SUBTABLE(node)->at_default); - else - prev = node; + slot = &at->at_heap[i].node; + node = SMR_PTR_GET_LOCKED(slot); + if (!ISLEAF(node)) { + slot = &SUBTABLE(node)->at_default; + node = SMR_PTR_GET_LOCKED(slot); + } - if (art_check_duplicate(ar, prev, an)) - return (prev); + if (art_check_duplicate(ar, node, an)) + return (node); art_table_ref(ar, at); @@ -426,11 +393,9 @@ art_table_insert(struct art_root *ar, st * all the corresponding fringe indices. */ if (i < at->at_minfringe) - art_allot(at, i, prev, an); - else if (!ISLEAF(node)) - srp_swap_locked(&SUBTABLE(node)->at_default, an); + art_allot(at, i, node, an); else - srp_swap_locked(&at->at_heap[i].node, an); + SMR_PTR_SET_LOCKED(slot, an); return (an); } @@ -440,7 +405,8 @@ art_table_insert(struct art_root *ar, st * Deletion API function. */ struct art_node * -art_delete(struct art_root *ar, struct art_node *an, void *addr, int plen) +art_delete(struct art_root *ar, struct art_node *an, void *addr, int plen, + struct art_garbage *ag) { struct art_table *at; struct art_node *node; @@ -449,15 +415,15 @@ art_delete(struct art_root *ar, struct a rw_assert_wrlock(&ar->ar_lock); KASSERT(plen >= 0 && plen <= ar->ar_alen); - at = srp_get_locked(&ar->ar_root); + at = SMR_PTR_GET_LOCKED(&ar->ar_root); if (at == NULL) return (NULL); /* Default route */ if (plen == 0) { - node = srp_get_locked(&at->at_default); - srp_swap_locked(&at->at_default, NULL); - art_table_free(ar, at); + node = SMR_PTR_GET_LOCKED(&at->at_default); + SMR_PTR_SET_LOCKED(&at->at_default, NULL); + art_table_free(ar, at, ag); return (node); } @@ -469,7 +435,7 @@ art_delete(struct art_root *ar, struct a while (plen > (at->at_offset + at->at_bits)) { /* Do a single level route lookup. */ j = art_findex(at, addr); - node = srp_get_locked(&at->at_heap[j].node); + node = SMR_PTR_GET_LOCKED(&at->at_heap[j].node); /* If this is a leaf, there is no route to delete. */ if (ISLEAF(node)) @@ -482,7 +448,7 @@ art_delete(struct art_root *ar, struct a if (i == -1) return (NULL); - return (art_table_delete(ar, at, i, an)); + return (art_table_delete(ar, at, i, an, ag)); } /* @@ -490,29 +456,26 @@ art_delete(struct art_root *ar, struct a */ struct art_node * art_table_delete(struct art_root *ar, struct art_table *at, int i, - struct art_node *an) + struct art_node *an, struct art_garbage *ag) { - struct art_node *next, *node; + struct art_node **slot; + struct art_node *node; + int j; -#ifdef DIAGNOSTIC - struct art_node *prev; -#endif - - node = srp_get_locked(&at->at_heap[i].node); -#ifdef DIAGNOSTIC - if (!ISLEAF(node)) - prev = srp_get_locked(&SUBTABLE(node)->at_default); - else - prev = node; - - KASSERT(prev == an); -#endif + slot = &at->at_heap[i].node; + node = SMR_PTR_GET_LOCKED(slot); + if (!ISLEAF(node)) { + slot = &SUBTABLE(node)->at_default; + node = SMR_PTR_GET_LOCKED(slot); + } + KASSERT(node == an); + j = (i >> 1); /* Get the next most specific route for the index `i'. */ - if ((i >> 1) > 1) - next = srp_get_locked(&at->at_heap[i >> 1].node); + if (j > 1) + node = SMR_PTR_GET_LOCKED(&at->at_heap[j].node); else - next = NULL; + node = NULL; /* * If the index `i' of the route that we are removing is not @@ -520,14 +483,15 @@ art_table_delete(struct art_root *ar, st * route pointer to all the corresponding fringe indices. */ if (i < at->at_minfringe) - art_allot(at, i, an, next); - else if (!ISLEAF(node)) - srp_swap_locked(&SUBTABLE(node)->at_default, next); + art_allot(at, i, an, node); else - srp_swap_locked(&at->at_heap[i].node, next); + SMR_PTR_SET_LOCKED(slot, node); /* We have removed an entry from this table. */ - art_table_free(ar, at); + art_table_free(ar, at, ag); + + an->an_gc_entry = ag->ag_list; + ag->ag_list = an; return (an); } @@ -549,7 +513,8 @@ art_table_rele(struct art_table *at) } int -art_table_free(struct art_root *ar, struct art_table *at) +art_table_free(struct art_root *ar, struct art_table *at, + struct art_garbage *ag) { if (art_table_rele(at)) { /* @@ -557,7 +522,7 @@ art_table_free(struct art_root *ar, stru * that are empty. */ do { - at = art_table_put(ar, at); + at = art_table_put(ar, at, ag); } while (art_table_rele(at)); return (1); @@ -572,13 +537,13 @@ art_table_free(struct art_root *ar, stru int art_walk(struct art_root *ar, int (*f)(struct art_node *, void *), void *arg) { - struct srp_ref sr; struct art_table *at; struct art_node *node; int error = 0; + struct art_garbage ag = ART_GARBAGE_INITIALIZER(); rw_enter_write(&ar->ar_lock); - at = srp_get_locked(&ar->ar_root); + at = SMR_PTR_GET_LOCKED(&ar->ar_root); if (at != NULL) { art_table_ref(ar, at); @@ -586,25 +551,28 @@ art_walk(struct art_root *ar, int (*f)(s * The default route should be processed here because the root * table does not have a parent. */ - node = srp_enter(&sr, &at->at_default); + node = SMR_PTR_GET_LOCKED(&at->at_default); error = art_walk_apply(ar, node, NULL, f, arg); - srp_leave(&sr); - if (error == 0) - error = art_table_walk(ar, at, f, arg); + error = art_table_walk(ar, at, &ag, f, arg); - art_table_free(ar, at); + art_table_free(ar, at, &ag); } rw_exit_write(&ar->ar_lock); + if (ag.ag_list != NULL) { + smr_barrier(); + art_gc(&ag); + } + return (error); } int art_table_walk(struct art_root *ar, struct art_table *at, + struct art_garbage *ag, int (*f)(struct art_node *, void *), void *arg) { - struct srp_ref sr; struct art_node *node, *next; struct art_table *nat; int i, j, error = 0; @@ -620,12 +588,9 @@ art_table_walk(struct art_root *ar, stru * be processed more than once. */ for (i = max(j, 2); i < at->at_minfringe; i <<= 1) { - next = srp_get_locked(&at->at_heap[i >> 1].node); - - node = srp_enter(&sr, &at->at_heap[i].node); + next = SMR_PTR_GET_LOCKED(&at->at_heap[i >> 1].node); + node = SMR_PTR_GET_LOCKED(&at->at_heap[i].node); error = art_walk_apply(ar, node, next, f, arg); - srp_leave(&sr); - if (error != 0) return (error); } @@ -635,26 +600,23 @@ art_table_walk(struct art_root *ar, stru * Iterate fringe nodes. */ for (i = at->at_minfringe; i < maxfringe; i++) { - next = srp_get_locked(&at->at_heap[i >> 1].node); - - node = srp_enter(&sr, &at->at_heap[i].node); + next = SMR_PTR_GET_LOCKED(&at->at_heap[i >> 1].node); + node = SMR_PTR_GET_LOCKED(&at->at_heap[i].node); if (!ISLEAF(node)) { nat = art_table_ref(ar, SUBTABLE(node)); - node = srp_follow(&sr, &nat->at_default); + node = SMR_PTR_GET_LOCKED(&nat->at_default); } else nat = NULL; error = art_walk_apply(ar, node, next, f, arg); - srp_leave(&sr); - if (error != 0) { - art_table_free(ar, nat); + art_table_free(ar, nat, ag); return (error); } if (nat != NULL) { - error = art_table_walk(ar, nat, f, arg); - art_table_free(ar, nat); + error = art_table_walk(ar, nat, ag, f, arg); + art_table_free(ar, nat, ag); if (error != 0) return (error); } @@ -671,15 +633,16 @@ art_walk_apply(struct art_root *ar, int error = 0; if ((an != NULL) && (an != next)) { + smr_read_enter(); /* this is pretty magical */ rw_exit_write(&ar->ar_lock); error = (*f)(an, arg); + smr_read_leave(); rw_enter_write(&ar->ar_lock); } return (error); } - /* * Create a table and use the given index to set its default route. * @@ -732,9 +695,9 @@ art_table_get(struct art_root *ar, struc at->at_refcnt = 0; if (parent != NULL) { - node = srp_get_locked(&parent->at_heap[j].node); - /* node isn't being deleted, no srp_finalize needed */ - srp_swap_locked(&at->at_default, node); + node = SMR_PTR_GET_LOCKED(&parent->at_heap[j].node); + /* move reference */ + SMR_PTR_SET_LOCKED(&at->at_default, node); at->at_offset = (parent->at_offset + parent->at_bits); } @@ -748,7 +711,8 @@ art_table_get(struct art_root *ar, struc * Note: Modify its parent to unlink the table from it. */ struct art_table * -art_table_put(struct art_root *ar, struct art_table *at) +art_table_put(struct art_root *ar, struct art_table *at, + struct art_garbage *ag) { struct art_table *parent = at->at_parent; struct art_node *node; @@ -763,57 +727,36 @@ art_table_put(struct art_root *ar, struc KASSERT(parent->at_refcnt >= 1); /* Give the route back to its parent. */ - node = srp_get_locked(&at->at_default); - srp_swap_locked(&parent->at_heap[j].node, node); + node = SMR_PTR_GET_LOCKED(&at->at_default); + /* move reference */ + SMR_PTR_SET_LOCKED(&parent->at_heap[j].node, node); } else { KASSERT(j == -1); KASSERT(at->at_level == 0); - srp_swap_locked(&ar->ar_root, NULL); + SMR_PTR_SET_LOCKED(&ar->ar_root, NULL); } - mtx_enter(&art_table_gc_mtx); - at->at_parent = art_table_gc_list; - art_table_gc_list = at; - mtx_leave(&art_table_gc_mtx); - - task_add(systqmp, &art_table_gc_task); + at->at_gc_entry = ag->ag_list; + ag->ag_list = ASNODE(at); return (parent); } void -art_table_gc(void *null) +art_table_gc(struct art_table *at) { - struct art_table *at, *next; - - mtx_enter(&art_table_gc_mtx); - at = art_table_gc_list; - art_table_gc_list = NULL; - mtx_leave(&art_table_gc_mtx); - - while (at != NULL) { - next = at->at_parent; - - if (at->at_level == 0) - srp_finalize(at, "arttfini"); - else - srp_finalize(ASNODE(at), "arttfini"); - - switch (AT_HEAPSIZE(at->at_bits)) { - case AT_HEAPSIZE(4): - pool_put(&at_heap_4_pool, at->at_heap); - break; - case AT_HEAPSIZE(8): - pool_put(&at_heap_8_pool, at->at_heap); - break; - default: - panic("incorrect stride length %u", at->at_bits); - } - - pool_put(&at_pool, at); - - at = next; + switch (AT_HEAPSIZE(at->at_bits)) { + case AT_HEAPSIZE(4): + pool_put(&at_heap_4_pool, at->at_heap); + break; + case AT_HEAPSIZE(8): + pool_put(&at_heap_8_pool, at->at_heap); + break; + default: + panic("incorrect stride length %u", at->at_bits); } + + pool_put(&at_pool, at); } /* @@ -855,15 +798,15 @@ again: /* Change fringe nodes. */ while (1) { - node = srp_get_locked(&at->at_heap[k].node); + node = SMR_PTR_GET_LOCKED(&at->at_heap[k].node); if (!ISLEAF(node)) { - dflt = srp_get_locked(&SUBTABLE(node)->at_default); + dflt = SMR_PTR_GET_LOCKED(&SUBTABLE(node)->at_default); if (dflt == old) { - srp_swap_locked(&SUBTABLE(node)->at_default, + SMR_PTR_SET_LOCKED(&SUBTABLE(node)->at_default, new); } } else if (node == old) { - srp_swap_locked(&at->at_heap[k].node, new); + SMR_PTR_SET_LOCKED(&at->at_heap[k].node, new); } if (k % 2) goto moveup; @@ -871,7 +814,7 @@ again: } nonfringe: - node = srp_get_locked(&at->at_heap[k].node); + node = SMR_PTR_GET_LOCKED(&at->at_heap[k].node); if (node == old) goto again; moveon: @@ -881,7 +824,7 @@ moveon: goto nonfringe; moveup: k >>= 1; - srp_swap_locked(&at->at_heap[k].node, new); + SMR_PTR_SET_LOCKED(&at->at_heap[k].node, new); /* Change non-fringe node. */ if (k != i) @@ -889,7 +832,7 @@ moveup: } struct art_node * -art_get(void *dst, uint8_t plen) +art_get(uint8_t plen) { struct art_node *an; @@ -898,7 +841,6 @@ art_get(void *dst, uint8_t plen) return (NULL); an->an_plen = plen; - SRPL_INIT(&an->an_rtlist); return (an); } @@ -906,33 +848,22 @@ art_get(void *dst, uint8_t plen) void art_put(struct art_node *an) { - KASSERT(SRPL_EMPTY_LOCKED(&an->an_rtlist)); - - mtx_enter(&art_node_gc_mtx); - an->an_gc = art_node_gc_list; - art_node_gc_list = an; - mtx_leave(&art_node_gc_mtx); - - task_add(systqmp, &art_node_gc_task); + pool_put(&an_pool, an); } void -art_gc(void *null) +art_gc(struct art_garbage *ag) { - struct art_node *an, *next; - - mtx_enter(&art_node_gc_mtx); - an = art_node_gc_list; - art_node_gc_list = NULL; - mtx_leave(&art_node_gc_mtx); - - while (an != NULL) { - next = an->an_gc; - - srp_finalize(an, "artnfini"); - - pool_put(&an_pool, an); - - an = next; + struct art_node *node, *next; + + for (node = ag->ag_list; node != NULL; node = next) { + if (ISLEAF(node)) { + next = node->an_gc_entry; + art_put(node); + } else { + struct art_table *at = SUBTABLE(node); + next = at->at_gc_entry; + art_table_gc(at); + } } } Index: art.h =================================================================== RCS file: /cvs/src/sys/net/art.h,v retrieving revision 1.21 diff -u -p -r1.21 art.h --- art.h 2 Mar 2021 17:50:41 -0000 1.21 +++ art.h 9 Mar 2021 11:58:58 -0000 @@ -20,7 +20,6 @@ #define _NET_ART_H_ #include -#include #define ART_MAXLVL 32 /* We currently use 32 levels for IPv6. */ @@ -35,7 +34,7 @@ * is indicated below. */ struct art_root { - struct srp ar_root; /* [l] First table */ + struct art_table *ar_root; /* [l] First table */ struct rwlock ar_lock; /* [] Serialise modifications */ uint8_t ar_bits[ART_MAXLVL]; /* [I] Per level stride */ uint8_t ar_nlvl; /* [I] Number of levels */ @@ -52,7 +51,15 @@ struct art_root { * Allotment Table. */ struct art_table { - struct art_table *at_parent; /* Parent table */ + union { + struct art_table * + at_u_parent; /* Parent table */ + struct art_node * + at_u_gc_entry; + } at_u; +#define at_parent at_u.at_u_parent +#define at_gc_entry at_u.at_u_gc_entry + uint32_t at_index; /* Index in the parent table */ uint32_t at_minfringe; /* Index that fringe begins */ uint32_t at_level; /* Level of the table */ @@ -65,7 +72,7 @@ struct art_table { * is a route counter. */ union { - struct srp node; + struct art_node *node; unsigned long count; } *at_heap; /* Array of 2^(slen+1) items */ }; @@ -76,37 +83,32 @@ struct art_table { #define AT_HEAPSIZE(slen) ((1 << ((slen) + 1)) * sizeof(void *)) /* - * Forward declaration needed for the list of mpath routes - * attached to a single ART node. - */ -struct rtentry; - -/* * A node is the internal representation of a route entry. */ struct art_node { - union { - SRPL_HEAD(, rtentry) an__rtlist; /* Route related to this node */ - struct art_node *an__gc; /* Entry on GC list */ - } an_pointer; + void *an_entry; /* Routes on this node */ + struct art_node *an_gc_entry; uint8_t an_plen; /* Prefix length */ }; -#define an_rtlist an_pointer.an__rtlist -#define an_gc an_pointer.an__gc + +struct art_garbage { + struct art_node *ag_list; +}; +#define ART_GARBAGE_INITIALIZER() { .ag_list = NULL } void art_init(void); struct art_root *art_alloc(unsigned int, unsigned int, unsigned int); -struct art_node *art_insert(struct art_root *, struct art_node *, void *, - int); -struct art_node *art_delete(struct art_root *, struct art_node *, void *, - int); -struct art_node *art_match(struct art_root *, void *, struct srp_ref *); -struct art_node *art_lookup(struct art_root *, void *, int, - struct srp_ref *); +struct art_node *art_insert(struct art_root *, struct art_node *, void *, int); +struct art_node *art_delete(struct art_root *, struct art_node *, void *, int, + struct art_garbage *); +struct art_node *art_match(struct art_root *, void *); +struct art_node *art_lookup(struct art_root *, void *, int); int art_walk(struct art_root *, int (*)(struct art_node *, void *), void *); -struct art_node *art_get(void *, uint8_t); +struct art_node *art_get(uint8_t); void art_put(struct art_node *); + +void art_gc(struct art_garbage *); #endif /* _NET_ART_H_ */ Index: rtable.c =================================================================== RCS file: /cvs/src/sys/net/rtable.c,v retrieving revision 1.72 diff -u -p -r1.72 rtable.c --- rtable.c 7 Nov 2020 09:51:40 -0000 1.72 +++ rtable.c 9 Mar 2021 11:58:58 -0000 @@ -26,6 +26,7 @@ #include #include #include +#include #endif #include @@ -87,6 +88,46 @@ void rtable_init_backend(void); void *rtable_alloc(unsigned int, unsigned int, unsigned int); void *rtable_get(unsigned int, sa_family_t); +static inline int +sockaddr_eq(const struct sockaddr *a, const struct sockaddr *b) +{ + return (a->sa_len == b->sa_len && memcmp(a, b, a->sa_len) == 0); +} + +static inline struct rtentry * +rtlist_first_locked(struct art_node *an) +{ + return (SMR_PTR_GET_LOCKED(&an->an_entry)); +} + +static inline struct rtentry * +rtlist_next_locked(struct rtentry *rt) +{ + return (SMR_PTR_GET_LOCKED(&rt->rt_next)); +} + +#define RTLIST_FOREACH_LOCKED(_rt, _an) \ + for ((_rt) = rtlist_first_locked(_an); \ + (_rt) != NULL; \ + (_rt) = rtlist_next_locked(_rt)) + +static inline struct rtentry * +rtlist_first(struct art_node *an) +{ + return (SMR_PTR_GET(&an->an_entry)); +} + +static inline struct rtentry * +rtlist_next(struct rtentry *rt) +{ + return (SMR_PTR_GET(&rt->rt_next)); +} + +#define RTLIST_FOREACH(_rt, _an) \ + for ((_rt) = rtlist_first(_an); \ + (_rt) != NULL; \ + (_rt) = rtlist_next(_rt)) + void rtmap_init(void) { @@ -288,7 +329,7 @@ rtable_empty(unsigned int rtableid) tbl = rtable_get(rtableid, dp->dom_family); if (tbl == NULL) continue; - if (tbl->ar_root.ref != NULL) + if (tbl->ar_root != NULL) return (0); } @@ -410,7 +451,7 @@ rtable_lookup(unsigned int rtableid, str struct art_root *ar; struct art_node *an; struct rtentry *rt = NULL; - struct srp_ref sr, nsr; + struct rtentry **nrtp; uint8_t *addr; int plen; @@ -420,41 +461,41 @@ rtable_lookup(unsigned int rtableid, str addr = satoaddr(ar, dst); + smr_read_enter(); /* No need for a perfect match. */ if (mask == NULL) { - an = art_match(ar, addr, &nsr); - if (an == NULL) + an = art_match(ar, addr); + if (an == NULL) { +printf("%s[%u]\n", __func__, __LINE__); goto out; + } } else { plen = rtable_satoplen(dst->sa_family, mask); if (plen == -1) return (NULL); - an = art_lookup(ar, addr, plen, &nsr); + an = art_lookup(ar, addr, plen); /* Make sure we've got a perfect match. */ if (!an_match(an, dst, plen)) goto out; } - SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) { + nrtp = (struct rtentry **)&an->an_entry; + while ((rt = SMR_PTR_GET(nrtp)) != NULL) { + nrtp = &rt->rt_next; + if (prio != RTP_ANY && (rt->rt_priority & RTP_MASK) != (prio & RTP_MASK)) continue; - if (gateway == NULL) - break; - - if (rt->rt_gateway->sa_len == gateway->sa_len && - memcmp(rt->rt_gateway, gateway, gateway->sa_len) == 0) + if (gateway == NULL || sockaddr_eq(rt->rt_gateway, gateway)) { + rtref(rt); break; + } } - if (rt != NULL) - rtref(rt); - - SRPL_LEAVE(&sr); out: - srp_leave(&nsr); + smr_read_leave(); return (rt); } @@ -465,7 +506,6 @@ rtable_match(unsigned int rtableid, stru struct art_root *ar; struct art_node *an; struct rtentry *rt = NULL; - struct srp_ref sr, nsr; uint8_t *addr; int hash; @@ -475,28 +515,29 @@ rtable_match(unsigned int rtableid, stru addr = satoaddr(ar, dst); - an = art_match(ar, addr, &nsr); - if (an == NULL) + smr_read_enter(); + an = art_match(ar, addr); + if (an == NULL) { +printf("%s[%u]\n", __func__, __LINE__); goto out; + } - rt = SRPL_FIRST(&sr, &an->an_rtlist); - rtref(rt); - SRPL_LEAVE(&sr); + rt = SMR_PTR_GET(&an->an_entry); /* Gateway selection by Hash-Threshold (RFC 2992) */ if ((hash = rt_hash(rt, dst, src)) != -1) { struct rtentry *mrt; - int threshold, npaths = 0; + int threshold, npaths = 1; KASSERT(hash <= 0xffff); - SRPL_FOREACH(mrt, &sr, &an->an_rtlist, rt_next) { + mrt = rt; + while ((mrt = SMR_PTR_GET(&mrt->rt_next)) != NULL) { /* Only count nexthops with the same priority. */ - if (mrt->rt_priority == rt->rt_priority) - npaths++; + if (mrt->rt_priority != rt->rt_priority) + break; + npaths++; } - SRPL_LEAVE(&sr); - threshold = (0xffff / npaths) + 1; /* @@ -509,22 +550,21 @@ rtable_match(unsigned int rtableid, stru * the end of the list and then pick the first route. */ - mrt = SRPL_FIRST(&sr, &an->an_rtlist); - while (hash > threshold && mrt != NULL) { - if (mrt->rt_priority == rt->rt_priority) - hash -= threshold; - mrt = SRPL_FOLLOW(&sr, mrt, rt_next); - } - - if (mrt != NULL) { - rtref(mrt); - rtfree(rt); - rt = mrt; + mrt = rt; + while ((mrt = SMR_PTR_GET(&mrt->rt_next)) != NULL) { + /* Only count nexthops with the same priority. */ + if (mrt->rt_priority != rt->rt_priority) + break; + hash -= threshold; + if (hash <= threshold) { + rt = mrt; + break; + } } - SRPL_LEAVE(&sr); } + rtref(rt); out: - srp_leave(&nsr); + smr_read_leave(); return (rt); } @@ -534,7 +574,6 @@ rtable_insert(unsigned int rtableid, str struct rtentry *rt) { struct rtentry *mrt; - struct srp_ref sr; struct art_root *ar; struct art_node *an, *prev; uint8_t *addr; @@ -555,28 +594,27 @@ rtable_insert(unsigned int rtableid, str rw_enter_write(&ar->ar_lock); /* Do not permit exactly the same dst/mask/gw pair. */ - an = art_lookup(ar, addr, plen, &sr); - srp_leave(&sr); /* an can't go away while we have the lock */ + an = art_lookup(ar, addr, plen); if (an_match(an, dst, plen)) { - struct rtentry *mrt; - int mpathok = ISSET(rt->rt_flags, RTF_MPATH); + int mpathok = ISSET(rt->rt_flags, RTF_MPATH); - SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) { + RTLIST_FOREACH_LOCKED(mrt, an) { if (prio != RTP_ANY && (mrt->rt_priority & RTP_MASK) != (prio & RTP_MASK)) continue; if (!mpathok || - (mrt->rt_gateway->sa_len == gateway->sa_len && - !memcmp(mrt->rt_gateway, gateway, gateway->sa_len))){ + sockaddr_eq(mrt->rt_gateway, gateway)) { +printf("%s[%u]\n", __func__, __LINE__); error = EEXIST; goto leave; } } } - an = art_get(dst, plen); + an = art_get(plen); if (an == NULL) { +printf("%s[%u]\n", __func__, __LINE__); error = ENOBUFS; goto leave; } @@ -586,23 +624,24 @@ rtable_insert(unsigned int rtableid, str rt->rt_flags &= ~RTF_MPATH; rt->rt_dest = dst; rt->rt_plen = plen; - SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); + rtref(rt); + SMR_PTR_SET_LOCKED(&an->an_entry, rt); prev = art_insert(ar, an, addr, plen); if (prev != an) { - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, - rt_next); + rtfree(rt); rt->rt_flags = rt_flags; art_put(an); if (prev == NULL) { +printf("%s[%u]\n", __func__, __LINE__); error = ESRCH; goto leave; } an = prev; - mrt = SRPL_FIRST_LOCKED(&an->an_rtlist); + mrt = rtlist_first_locked(an); KASSERT(mrt != NULL); KASSERT((rt->rt_flags & RTF_MPATH) || mrt->rt_priority != prio); @@ -616,15 +655,16 @@ rtable_insert(unsigned int rtableid, str * the same gateway. */ rt->rt_flags &= ~RTF_MPATH; - SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) { + do { if (mrt->rt_priority == prio) { mrt->rt_flags |= RTF_MPATH; rt->rt_flags |= RTF_MPATH; } - } + } while ((mrt = rtlist_next_locked(mrt)) != NULL); } /* Put newly inserted entry at the right place. */ + rtref(rt); rtable_mpath_insert(an, rt); } leave: @@ -639,10 +679,11 @@ rtable_delete(unsigned int rtableid, str { struct art_root *ar; struct art_node *an; - struct srp_ref sr; + struct art_garbage ag = ART_GARBAGE_INITIALIZER(); uint8_t *addr; int plen; struct rtentry *mrt; + struct rtentry **rtp; int npaths = 0; int error = 0; @@ -657,8 +698,7 @@ rtable_delete(unsigned int rtableid, str rtref(rt); /* guarantee rtfree won't do anything under ar_lock */ rw_enter_write(&ar->ar_lock); - an = art_lookup(ar, addr, plen, &sr); - srp_leave(&sr); /* an can't go away while we have the lock */ + an = art_lookup(ar, addr, plen); /* Make sure we've got a perfect match. */ if (!an_match(an, dst, plen)) { @@ -670,30 +710,35 @@ rtable_delete(unsigned int rtableid, str * If other multipath route entries are still attached to * this ART node we only have to unlink it. */ - SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) + RTLIST_FOREACH_LOCKED(mrt, an) npaths++; if (npaths > 1) { KASSERT(rt->rt_refcnt >= 1); - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, - rt_next); + rtp = (struct rtentry **)&an->an_entry; + while ((mrt = SMR_PTR_GET_LOCKED(rtp)) != rt) + rtp = &mrt->rt_next; + SMR_PTR_SET_LOCKED(rtp, rt->rt_next); - mrt = SRPL_FIRST_LOCKED(&an->an_rtlist); - if (npaths == 2) + if (npaths == 2) { + mrt = rtlist_first_locked(an); mrt->rt_flags &= ~RTF_MPATH; - - goto leave; + } + } else { + if (art_delete(ar, an, addr, plen, &ag) == NULL) + panic("art_delete failed to find node %p", an); } - if (art_delete(ar, an, addr, plen) == NULL) - panic("art_delete failed to find node %p", an); - KASSERT(rt->rt_refcnt >= 1); - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, rt_next); - art_put(an); + rtfree(rt); leave: rw_exit_write(&ar->ar_lock); + + if (error == 0) { + smr_barrier(); + art_gc(&ag); + } rtfree(rt); return (error); @@ -712,12 +757,12 @@ struct rtable_walk_cookie { int rtable_walk_helper(struct art_node *an, void *xrwc) { - struct srp_ref sr; struct rtable_walk_cookie *rwc = xrwc; struct rtentry *rt; int error = 0; - SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) { + smr_read_enter(); + RTLIST_FOREACH(rt, an) { error = (*rwc->rwc_func)(rt, rwc->rwc_arg, rwc->rwc_rid); if (error != 0) break; @@ -726,7 +771,7 @@ rtable_walk_helper(struct art_node *an, rtref(rt); *rwc->rwc_prt = rt; } - SRPL_LEAVE(&sr); + smr_read_leave(); return (error); } @@ -756,13 +801,13 @@ rtable_walk(unsigned int rtableid, sa_fa struct rtentry * rtable_iterate(struct rtentry *rt0) { - struct rtentry *rt = NULL; - struct srp_ref sr; + struct rtentry *rt; - rt = SRPL_NEXT(&sr, rt0, rt_next); + smr_read_enter(); + rt = rtlist_next(rt); if (rt != NULL) rtref(rt); - SRPL_LEAVE(&sr); + smr_read_leave(); rtfree(rt0); return (rt); } @@ -779,7 +824,6 @@ rtable_mpath_reprio(unsigned int rtablei { struct art_root *ar; struct art_node *an; - struct srp_ref sr; uint8_t *addr; int error = 0; @@ -790,14 +834,13 @@ rtable_mpath_reprio(unsigned int rtablei addr = satoaddr(ar, dst); rw_enter_write(&ar->ar_lock); - an = art_lookup(ar, addr, plen, &sr); - srp_leave(&sr); /* an can't go away while we have the lock */ + an = art_lookup(ar, addr, plen); /* Make sure we've got a perfect match. */ if (!an_match(an, dst, plen)) { error = ESRCH; - } else if (SRPL_FIRST_LOCKED(&an->an_rtlist) == rt && - SRPL_NEXT_LOCKED(rt, rt_next) == NULL) { + } else if (rtlist_first_locked(an) == rt && + rtlist_next_locked(rt) == NULL) { /* * If there's only one entry on the list do not go * through an insert/remove cycle. This is done to @@ -806,12 +849,16 @@ rtable_mpath_reprio(unsigned int rtablei */ rt->rt_priority = prio; } else { - rtref(rt); /* keep rt alive in between remove and insert */ - SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, - rt, rtentry, rt_next); + struct rtentry **rtp; + struct rtentry *mrt; + + rtp = (struct rtentry **)&an->an_entry; + while ((mrt = SMR_PTR_GET_LOCKED(rtp)) != rt) + rtp = &mrt->rt_next; + + SMR_PTR_SET_LOCKED(rtp, rt->rt_next); rt->rt_priority = prio; rtable_mpath_insert(an, rt); - rtfree(rt); error = EAGAIN; } rw_exit_write(&ar->ar_lock); @@ -822,27 +869,17 @@ rtable_mpath_reprio(unsigned int rtablei void rtable_mpath_insert(struct art_node *an, struct rtentry *rt) { - struct rtentry *mrt, *prt = NULL; + struct rtentry **rtp; + struct rtentry *mrt; uint8_t prio = rt->rt_priority; - if ((mrt = SRPL_FIRST_LOCKED(&an->an_rtlist)) == NULL) { - SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); - return; - } - - /* Iterate until we find the route to be placed after ``rt''. */ - while (mrt->rt_priority <= prio && SRPL_NEXT_LOCKED(mrt, rt_next)) { - prt = mrt; - mrt = SRPL_NEXT_LOCKED(mrt, rt_next); - } + rtp = (struct rtentry **)&an->an_entry; + do { + mrt = SMR_PTR_GET_LOCKED(rtp); + } while (mrt != NULL && mrt->rt_priority <= prio); - if (mrt->rt_priority <= prio) { - SRPL_INSERT_AFTER_LOCKED(&rt_rc, mrt, rt, rt_next); - } else if (prt != NULL) { - SRPL_INSERT_AFTER_LOCKED(&rt_rc, prt, rt, rt_next); - } else { - SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); - } + SMR_PTR_SET_LOCKED(&rt->rt_next, mrt); + SMR_PTR_SET_LOCKED(rtp, rt); } /* @@ -852,17 +889,12 @@ int an_match(struct art_node *an, struct sockaddr *dst, int plen) { struct rtentry *rt; - struct srp_ref sr; - int match; if (an == NULL || an->an_plen != plen) return (0); - rt = SRPL_FIRST(&sr, &an->an_rtlist); - match = (memcmp(rt->rt_dest, dst, dst->sa_len) == 0); - SRPL_LEAVE(&sr); - - return (match); + rt = rtlist_first(an); + return (memcmp(rt->rt_dest, dst, dst->sa_len) == 0); } void