Especially the rde_aspath hash function is horrible.
Fix this by adding more bits to the SipHash which results in a better
spread. Also switch the stored hases to 64bit and save the one for
rde_aspath as well since it the compare a lot quicker.

-- 
:wq Claudio

Index: rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.177
diff -u -p -r1.177 rde.h
--- rde.h       11 Jul 2018 16:34:36 -0000      1.177
+++ rde.h       11 Jul 2018 17:35:27 -0000
@@ -140,8 +140,8 @@ enum attrtypes {
 struct attr {
        LIST_ENTRY(attr)                 entry;
        u_char                          *data;
+       u_int64_t                        hash;
        int                              refcnt;
-       u_int32_t                        hash;
        u_int16_t                        len;
        u_int8_t                         flags;
        u_int8_t                         type;
@@ -154,11 +154,6 @@ struct mpattr {
        u_int16_t        unreach_len;
 };
 
-struct path_table {
-       struct aspath_head      *path_hashtbl;
-       u_int32_t                path_hashmask;
-};
-
 #define        F_ATTR_ORIGIN           0x00001
 #define        F_ATTR_ASPATH           0x00002
 #define        F_ATTR_NEXTHOP          0x00004
@@ -195,10 +190,11 @@ struct rde_aspath {
        struct rde_peer                 *peer;
        struct aspath                   *aspath;
        struct nexthop                  *nexthop;       /* may be NULL */
+       u_int64_t                        hash;
+       u_int32_t                        flags;         /* internally used */
        u_int32_t                        med;           /* multi exit disc */
        u_int32_t                        lpref;         /* local pref */
        u_int32_t                        weight;        /* low prio lpref */
-       u_int32_t                        flags;         /* internally used */
        u_int16_t                        rtlabelid;     /* route label id */
        u_int16_t                        pftableid;     /* pf table id */
        u_int8_t                         origin;
@@ -358,6 +354,7 @@ int          attr_optadd(struct rde_aspath *, u
 struct attr    *attr_optget(const struct rde_aspath *, u_int8_t);
 void            attr_copy(struct rde_aspath *, const struct rde_aspath *);
 int             attr_compare(struct rde_aspath *, struct rde_aspath *);
+u_int64_t       attr_hash(struct rde_aspath *);
 void            attr_freeall(struct rde_aspath *);
 void            attr_free(struct rde_aspath *, struct attr *);
 #define                 attr_optlen(x) \
Index: rde_attr.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_attr.c,v
retrieving revision 1.103
diff -u -p -r1.103 rde_attr.c
--- rde_attr.c  11 Jul 2018 16:34:36 -0000      1.103
+++ rde_attr.c  11 Jul 2018 17:35:27 -0000
@@ -99,7 +99,7 @@ void           attr_put(struct attr *);
 
 struct attr_table {
        struct attr_list        *hashtbl;
-       u_int32_t                hashmask;
+       u_int64_t                hashmask;
 } attrtable;
 
 SIPHASH_KEY attrtablekey;
@@ -287,7 +287,6 @@ attr_diff(struct attr *oa, struct attr *
                return (-1);
 
        fatalx("attr_diff: equal attributes encountered");
-       return (0);
 }
 
 int
@@ -313,6 +312,18 @@ attr_compare(struct rde_aspath *a, struc
        return (0);
 }
 
+u_int64_t
+attr_hash(struct rde_aspath *a)
+{
+       u_int64_t       hash = 0;
+       u_int8_t        l;
+
+       for (l = 0; l < a->others_len; l++)
+               if (a->others[l] != NULL)
+                       hash ^= a->others[l]->hash;
+       return (hash);
+}
+
 void
 attr_free(struct rde_aspath *asp, struct attr *attr)
 {
@@ -384,7 +395,7 @@ attr_lookup(u_int8_t flags, u_int8_t typ
 {
        struct attr_list        *head;
        struct attr             *a;
-       u_int32_t                hash;
+       u_int64_t                hash;
        SIPHASH_CTX             ctx;
 
        flags &= ~ATTR_DEFMASK; /* normalize mask */
Index: rde_rib.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
retrieving revision 1.169
diff -u -p -r1.169 rde_rib.c
--- rde_rib.c   11 Jul 2018 16:34:36 -0000      1.169
+++ rde_rib.c   11 Jul 2018 17:35:28 -0000
@@ -348,17 +348,17 @@ rib_restart(struct rib_context *ctx)
 /* path specific functions */
 
 static struct rde_aspath *path_lookup(struct rde_aspath *, struct rde_peer *);
-static void    path_link(struct rde_aspath *, struct rde_peer *);
+static u_int64_t path_hash(struct rde_aspath *);
+static void path_link(struct rde_aspath *, struct rde_peer *);
 
-struct path_table pathtable;
+struct path_table {
+       struct aspath_head      *path_hashtbl;
+       u_int64_t                path_hashmask;
+} pathtable;
 
 SIPHASH_KEY pathtablekey;
 
-/* XXX the hash should also include communities and the other attrs */
-#define PATH_HASH(x)                                           \
-       &pathtable.path_hashtbl[x == NULL ? 0 :                 \
-           SipHash24(&pathtablekey, (x)->data, (x)->len) &     \
-           pathtable.path_hashmask]
+#define PATH_HASH(x)   &pathtable.path_hashtbl[x & pathtable.path_hashmask]
 
 void
 path_init(u_int32_t hashsize)
@@ -511,16 +511,42 @@ path_compare(struct rde_aspath *a, struc
        return (attr_compare(a, b));
 }
 
+static u_int64_t
+path_hash(struct rde_aspath *asp)
+{
+       SIPHASH_CTX     ctx;
+       u_int64_t       hash;
+
+       SipHash24_Init(&ctx, &pathtablekey);
+       SipHash24_Update(&ctx, &asp->origin, sizeof(asp->origin));
+       SipHash24_Update(&ctx, &asp->med, sizeof(asp->med));
+       SipHash24_Update(&ctx, &asp->lpref, sizeof(asp->lpref));
+       SipHash24_Update(&ctx, &asp->weight, sizeof(asp->weight));
+       SipHash24_Update(&ctx, &asp->rtlabelid, sizeof(asp->rtlabelid));
+       SipHash24_Update(&ctx, &asp->pftableid, sizeof(asp->pftableid));
+
+       if (asp->aspath)
+               SipHash24_Update(&ctx, asp->aspath->data, asp->aspath->len);
+
+       hash = attr_hash(asp);
+       SipHash24_Update(&ctx, &hash, sizeof(hash));
+
+       return (SipHash24_End(&ctx));
+}
+
 static struct rde_aspath *
 path_lookup(struct rde_aspath *aspath, struct rde_peer *peer)
 {
        struct aspath_head      *head;
        struct rde_aspath       *asp;
+       u_int64_t                hash;
 
-       head = PATH_HASH(aspath->aspath);
+       hash = path_hash(aspath);
+       head = PATH_HASH(hash);
 
        LIST_FOREACH(asp, head, path_l) {
-               if (peer == asp->peer && path_compare(aspath, asp) == 0)
+               if (asp->hash == hash && peer == asp->peer &&
+                   path_compare(aspath, asp) == 0)
                        return (asp);
        }
        return (NULL);
@@ -654,11 +680,13 @@ path_link(struct rde_aspath *asp, struct
 {
        struct aspath_head      *head;
 
-       head = PATH_HASH(asp->aspath);
+       asp->peer = peer;
+
+       asp->hash = path_hash(asp);
+       head = PATH_HASH(asp->hash);
 
        LIST_INSERT_HEAD(head, asp, path_l);
-       TAILQ_INSERT_TAIL(&peer->path_h, asp, peer_l);
-       asp->peer = peer;
+       TAILQ_INSERT_HEAD(&peer->path_h, asp, peer_l);
        nexthop_link(asp);
        asp->flags |= F_ATTR_LINKED;
 }
@@ -676,6 +704,7 @@ path_copy(struct rde_aspath *dst, const 
                rdemem.aspath_refs++;
        }
        dst->nexthop = nexthop_ref(src->nexthop);
+       dst->hash = 0;
        dst->med = src->med;
        dst->lpref = src->lpref;
        dst->weight = src->weight;
@@ -698,9 +727,6 @@ path_prep(struct rde_aspath *asp)
        TAILQ_INIT(&asp->updates);
        asp->origin = ORIGIN_INCOMPLETE;
        asp->lpref = DEFAULT_LPREF;
-       /* med = 0 */
-       /* weight = 0 */
-       /* rtlabel = 0 */
 
        return (asp);
 }

Reply via email to