Index: art.c =================================================================== RCS file: /cvs/src/sys/net/art.c,v retrieving revision 1.8 diff -u -p -r1.8 art.c --- art.c 12 Nov 2015 14:29:04 -0000 1.8 +++ art.c 1 Dec 2015 10:21:54 -0000 @@ -36,8 +36,8 @@ #include -#define ISLEAF(e) (((unsigned long)(e).node & 1) == 0) -#define SUBTABLE(e) (((struct art_table *)((unsigned long)(e).child & ~1))) +#define ISLEAF(e) (((unsigned long)(e) & 1) == 0) +#define SUBTABLE(e) ((struct art_table *)((unsigned long)(e) & ~1)) #define ASNODE(t) ((struct art_node *)((unsigned long)(t) | 1)) /* @@ -57,13 +57,12 @@ struct art_table { * is a route counter. */ union { - struct art_node *node; - struct art_table *child; - unsigned long count; + struct srp next; /* node or child */ + unsigned long count; /* at_refcnt */ } *at_heap; /* Array of 2^(slen+1) items */ }; #define at_refcnt at_heap[0].count/* Refcounter (1 per different route) */ -#define at_default at_heap[1].node /* Default route (was in parent heap) */ +#define at_default at_heap[1].next /* Default route (was in parent heap) */ /* Heap size for an ART table of stride length ``slen''. */ #define AT_HEAPSIZE(slen) ((1 << ((slen) + 1)) * sizeof(void *)) @@ -237,11 +236,80 @@ art_findex(struct art_table *at, uint8_t struct art_node * art_match(struct art_root *ar, uint8_t *addr) { + struct srp *p, *np, *defp; + void *entry; + struct art_table *at; - struct art_node *dflt = NULL; + struct art_node *dflt, *node; int j; - at = ar->ar_root; + splassert(IPL_SOFTNET); /* srp_enters for at_default overlap */ + + p = &ar->ar_root; + entry = srp_enter(p); + at = entry; + + if (at == NULL) { + srp_leave(p, entry) + return (NULL); + } + + defp = &at->at_default; + node = srp_enter(defp); + + /* + * Iterate until we find a leaf. + */ + for (;;) { + /* Do a single level route lookup. */ + j = art_findex(at, addr); + np = &at->at_heap[j].next; + + entry = srp_follow(p, entry, np); + p = np; + + /* If this is a leaf we're done. */ + if (ISLEAF(entry)) + break; + + at = SUBTABLE(entry); + + /* + * Rember the default route of this table in case + * we do not find a better matching route. + */ + node = srp_enter(&at->at_default); + if (node != NULL) { + srp_leave(defp, dflt); + + dflt = node; + defp = &at->at_default; + } else + srp_leave(&at->at_default, node); + } + + node = entry; + + if (node != NULL) + REF(node); + else + node = REF(dflt); + + srp_leave(defp, dflt); + srp_leave(p, entry); + + return (node); +} + +struct art_node * +art_match_locked(struct art_root *ar, uint8_t *addr) +{ + void *entry; + struct art_table *at; + struct art_node *dflt = NULL, *ndflt; + int j; + + at = srp_get_locked(&ar->ar_root); if (at == NULL) return (NULL); @@ -253,21 +321,23 @@ art_match(struct art_root *ar, uint8_t * * Rember the default route of this table in case * we do not find a better matching route. */ - if (at->at_default != NULL) - dflt = at->at_default; + ndflt = srp_get_locked(&at->at_default); + if (ndflt != NULL) + dflt = ndflt; /* Do a single level route lookup. */ j = art_findex(at, addr); + entry = srp_get_locked(&at->at_heap[j]); /* If this is a leaf we're done. */ - if (ISLEAF(at->at_heap[j])) + if (ISLEAF(entry)) break; - at = SUBTABLE(at->at_heap[j]); + at = SUBTABLE(entry); } - if (at->at_heap[j].node != NULL) - return (at->at_heap[j].node); + if (entry) + return (entry); return (dflt); } @@ -281,19 +351,93 @@ art_match(struct art_root *ar, uint8_t * struct art_node * art_lookup(struct art_root *ar, uint8_t *addr, int plen) { + struct srp *p, *np; + + struct art_table *at; + struct art_node *an, *dflt; + int i, j; + + KASSERT(plen >= 0 && plen <= ar->ar_alen); + + p = &ar->ar_root; + entry = srp_enter(p); + at = entry; + + if (at == NULL) { + srp_leave(p, entry); + return (NULL); + } + + /* Default route */ + if (plen == 0) { + dflt = srp_follow(p, entry, &at->at_default); + if (dflt != NULL) + REF(dflt); + srp_leave(&at->at_default, dflt); + return (dflt); + } + + /* + * If the prefix length is smaller than the sum of + * the stride length at this level the entry must + * be in the current table. + */ + while (plen > (at->at_offset + at->at_bits)) { + /* Do a single level route lookup. */ + j = art_findex(at, addr); + np = &at->at_heap[j].next; + + entry = srp_follow(p, entry, np); + p = np; + + /* A leaf is a match, but not a perfect one. */ + if (ISLEAF(entry)) { + srp_leave(p, entry); + return (NULL); + } + + at = SUBTABLE(entry); + } + + i = art_bindex(at, addr, plen); + if (i == -1) { + srp_leave(p, entry); + return (NULL); + } + + np = &at->at_heap[i].next; + entry = srp_follow(p, entry, np); + p = np; + + if (!ISLEAF(entry)) { + np = &SUBTABLE(entry)->at_default; + entry = srp_follow(p, entry, np); + p = np; + } + + an = REF(entry); + srp_leave(p, entry); + + return (an); +} + +struct art_node * +art_lookup_locked(struct art_root *ar, uint8_t *addr, int plen) +{ + void *entry; struct art_table *at; struct art_node *an; int i, j; KASSERT(plen >= 0 && plen <= ar->ar_alen); - at = ar->ar_root; + at = srp_get_locked(ar->ar_root); if (at == NULL) return (NULL); /* Default route */ if (plen == 0) - return (at->at_default); + return (srp_get_locked(at->at_default)); /* * If the prefix length is smaller than the sum of @@ -303,22 +447,24 @@ art_lookup(struct art_root *ar, uint8_t while (plen > (at->at_offset + at->at_bits)) { /* Do a single level route lookup. */ j = art_findex(at, addr); + entry = srp_get_locked(&at->at_heap[j].next); /* A leaf is a match, but not a perfect one. */ - if (ISLEAF(at->at_heap[j])) + if (ISLEAF(entry)) return (NULL); - at = SUBTABLE(at->at_heap[j]); + at = SUBTABLE(entry); } i = art_bindex(at, addr, plen); if (i == -1) return (NULL); - if (!ISLEAF(at->at_heap[i])) - an = SUBTABLE(at->at_heap[i])->at_default; + entry = srp_get_locked(&at->at_heap[i].next); + if (!ISLEAF(entry)) + an = srp_get_locked(&SUBTABLE(entry))->at_default); else - an = at->at_heap[i].node; + an = entry; return (an); } Index: art.h =================================================================== RCS file: /cvs/src/sys/net/art.h,v retrieving revision 1.5 diff -u -p -r1.5 art.h --- art.h 6 Nov 2015 17:44:45 -0000 1.5 +++ art.h 1 Dec 2015 10:21:54 -0000 @@ -25,7 +25,7 @@ * Root of the ART tables, equivalent to the radix head. */ struct art_root { - struct art_table *ar_root; /* First table */ + struct srp ar_root; /* First struct art_table */ uint8_t ar_bits[ART_MAXLVL]; /* Per level stride */ uint8_t ar_nlvl; /* Number of levels */ uint8_t ar_alen; /* Address length in bits */ @@ -45,7 +45,6 @@ struct rtentry; struct art_node { struct sockaddr *an_dst; /* Destination address (key) */ int an_plen; /* Prefix length */ - SLIST_HEAD(, rtentry) an_rtlist; /* Route related to this node */ };