diff options
| -rw-r--r-- | usr.sbin/bgpd/bgpd.h | 3 | ||||
| -rw-r--r-- | usr.sbin/bgpd/mrt.c | 17 | ||||
| -rw-r--r-- | usr.sbin/bgpd/rde.c | 5 | ||||
| -rw-r--r-- | usr.sbin/bgpd/rde.h | 18 | ||||
| -rw-r--r-- | usr.sbin/bgpd/rde_attr.c | 277 | ||||
| -rw-r--r-- | usr.sbin/bgpd/rde_rib.c | 33 | ||||
| -rw-r--r-- | usr.sbin/bgpd/rde_update.c | 7 |
7 files changed, 264 insertions, 96 deletions
diff --git a/usr.sbin/bgpd/bgpd.h b/usr.sbin/bgpd/bgpd.h index 11e3d002929..4c046676b65 100644 --- a/usr.sbin/bgpd/bgpd.h +++ b/usr.sbin/bgpd/bgpd.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bgpd.h,v 1.184 2006/01/04 12:45:53 claudio Exp $ */ +/* $OpenBSD: bgpd.h,v 1.185 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org> @@ -640,6 +640,7 @@ struct rde_memstats { int64_t aspath_size; int64_t aspath_refs; int64_t attr_cnt; + int64_t attr_refs; int64_t attr_data; int64_t attr_dcnt; }; diff --git a/usr.sbin/bgpd/mrt.c b/usr.sbin/bgpd/mrt.c index f06aff60a36..d7cb0eb1c96 100644 --- a/usr.sbin/bgpd/mrt.c +++ b/usr.sbin/bgpd/mrt.c @@ -1,4 +1,4 @@ -/* $OpenBSD: mrt.c,v 1.48 2005/11/29 21:11:07 claudio Exp $ */ +/* $OpenBSD: mrt.c,v 1.49 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> @@ -219,8 +219,8 @@ mrt_dump_state(struct mrt *mrt, u_int16_t old_state, u_int16_t new_state, static u_int16_t mrt_attr_length(struct rde_aspath *a, int oldform) { - struct attr *oa; u_int16_t alen, plen; + u_int8_t l; alen = 4 /* origin */ + 7 /* lpref */; if (oldform) @@ -230,8 +230,12 @@ mrt_attr_length(struct rde_aspath *a, int oldform) if (a->med != 0) alen += 7; - TAILQ_FOREACH(oa, &a->others, entry) - alen += 2 + oa->len + (oa->len > 255 ? 2 : 1); + for (l = 0; l < a->others_len; l++) + if (a->others[l] != NULL) + alen += 2 + a->others[l]->len + + (a->others[l]->len > 255 ? 2 : 1); + else + break; return alen; } @@ -245,6 +249,7 @@ mrt_attr_dump(void *p, u_int16_t len, struct rde_aspath *a, u_int32_t tmp32; int r; u_int16_t aslen, wlen = 0; + u_int8_t l; /* origin */ if ((r = attr_write(buf + wlen, len, ATTR_WELL_KNOWN, ATTR_ORIGIN, @@ -284,7 +289,9 @@ mrt_attr_dump(void *p, u_int16_t len, struct rde_aspath *a, wlen += r; len -= r; /* dump all other path attributes without modification */ - TAILQ_FOREACH(oa, &a->others, entry) { + for (l = 0; l < a->others_len; l++) { + if ((oa = a->others[l]) == NULL) + break; if ((r = attr_write(buf + wlen, len, oa->flags, oa->type, oa->data, oa->len)) == -1) return (-1); diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c index 785e51b4152..6f7cc7017ae 100644 --- a/usr.sbin/bgpd/rde.c +++ b/usr.sbin/bgpd/rde.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.c,v 1.189 2006/01/04 12:53:31 claudio Exp $ */ +/* $OpenBSD: rde.c,v 1.190 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org> @@ -112,6 +112,7 @@ rde_sighdlr(int sig) u_int32_t peerhashsize = 64; u_int32_t pathhashsize = 1024; +u_int32_t attrhashsize = 512; u_int32_t nexthophashsize = 64; pid_t @@ -191,6 +192,7 @@ rde_main(struct bgpd_config *config, struct peer *peer_l, pt_init(); path_init(pathhashsize); aspath_init(pathhashsize); + attr_init(pathhashsize); nexthop_init(nexthophashsize); peer_init(peerhashsize); rules_l = rules; @@ -2270,6 +2272,7 @@ rde_shutdown(void) nexthop_shutdown(); path_shutdown(); aspath_shutdown(); + attr_shutdown(); pt_shutdown(); peer_shutdown(); free(mrt); diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index 0ad9c60550c..8e4a67dfcb8 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.79 2006/01/03 22:49:17 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.80 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> and @@ -110,8 +110,10 @@ enum attrtypes { #define ATTR_WELL_KNOWN ATTR_TRANSITIVE struct attr { - TAILQ_ENTRY(attr) entry; + LIST_ENTRY(attr) entry; u_char *data; + int refcnt; + u_int32_t hash; u_int16_t len; u_int8_t flags; u_int8_t type; @@ -124,7 +126,7 @@ struct mpattr { u_int16_t unreach_len; }; -TAILQ_HEAD(attr_list, attr); +LIST_HEAD(attr_list, attr); struct path_table { struct aspath_head *path_hashtbl; @@ -156,7 +158,7 @@ LIST_HEAD(prefix_head, prefix); struct rde_aspath { LIST_ENTRY(rde_aspath) path_l, peer_l, nexthop_l; struct prefix_head prefix_h; - struct attr_list others; + struct attr **others; struct rde_peer *peer; struct aspath *aspath; struct nexthop *nexthop; /* may be NULL */ @@ -169,6 +171,7 @@ struct rde_aspath { u_int16_t prefix_cnt; /* # of prefixes */ u_int16_t active_cnt; /* # of active prefixes */ u_int8_t origin; + u_int8_t others_len; }; enum nexthop_state { @@ -254,11 +257,14 @@ int rde_decisionflags(void); /* rde_attr.c */ int attr_write(void *, u_int16_t, u_int8_t, u_int8_t, void *, u_int16_t); -void attr_optcopy(struct rde_aspath *, struct rde_aspath *); +void attr_init(u_int32_t); +void attr_shutdown(void); int attr_optadd(struct rde_aspath *, u_int8_t, u_int8_t, void *, u_int16_t); struct attr *attr_optget(const struct rde_aspath *, u_int8_t); -void attr_optfree(struct rde_aspath *); +void attr_copy(struct rde_aspath *, struct rde_aspath *); +int attr_compare(struct rde_aspath *, struct rde_aspath *); +void attr_freeall(struct rde_aspath *); int aspath_verify(void *, u_int16_t); #define AS_ERR_LEN -1 diff --git a/usr.sbin/bgpd/rde_attr.c b/usr.sbin/bgpd/rde_attr.c index bbc19da8f7d..37b3be82247 100644 --- a/usr.sbin/bgpd/rde_attr.c +++ b/usr.sbin/bgpd/rde_attr.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_attr.c,v 1.55 2006/01/04 12:45:53 claudio Exp $ */ +/* $OpenBSD: rde_attr.c,v 1.56 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org> @@ -29,8 +29,6 @@ #include "bgpd.h" #include "rde.h" -/* attribute specific functions */ - int attr_write(void *p, u_int16_t p_len, u_int8_t flags, u_int8_t type, void *data, u_int16_t data_len) @@ -64,24 +62,209 @@ attr_write(void *p, u_int16_t p_len, u_int8_t flags, u_int8_t type, return (tot_len); } +/* optional attribute specific functions */ +int attr_diff(struct attr *, struct attr *); +struct attr *attr_alloc(u_int8_t, u_int8_t, const void *, u_int16_t); +struct attr *attr_lookup(u_int8_t, u_int8_t, const void *, u_int16_t); +void attr_put(struct attr *); + +struct attr_table { + struct attr_list *hashtbl; + u_int32_t hashmask; +} attrtable; + +#define ATTR_HASH(x) \ + &attrtable.hashtbl[(x) & attrtable.hashmask] + +void +attr_init(u_int32_t hashsize) +{ + u_int32_t hs, i; + + for (hs = 1; hs < hashsize; hs <<= 1) + ; + attrtable.hashtbl = calloc(hs, sizeof(struct attr_list)); + if (attrtable.hashtbl == NULL) + fatal("attr_init"); + + for (i = 0; i < hs; i++) + LIST_INIT(&attrtable.hashtbl[i]); + + attrtable.hashmask = hs - 1; +} + +void +attr_shutdown(void) +{ + u_int32_t i; + + for (i = 0; i <= attrtable.hashmask; i++) + if (!LIST_EMPTY(&attrtable.hashtbl[i])) + log_warnx("attr_shutdown: free non-free table"); + + free(attrtable.hashtbl); +} + int attr_optadd(struct rde_aspath *asp, u_int8_t flags, u_int8_t type, void *data, u_int16_t len) { - struct attr *a, *p; + u_int8_t l; + struct attr *a, *t; /* known optional attributes were validated previously */ + if ((a = attr_lookup(flags, type, data, len)) == 0) + a = attr_alloc(flags, type, data, len); + + /* attribute allowed only once */ + for (l = 0; l < asp->others_len; l++) { + if (asp->others[l] == NULL) + break; + if (type == asp->others[l]->type) + return (-1); + } + + /* add attribute to the table but first bump refcnt */ + a->refcnt++; + rdemem.attr_refs++; + + for (l = 0; l < asp->others_len; l++) { + if (asp->others[l] == NULL) { + asp->others[l] = a; + return (0); + } + /* list is sorted */ + if (a->type < asp->others[l]->type) { + t = asp->others[l]; + asp->others[l] = a; + a = t; + } + } + + /* no empty slot found, need to realloc */ + asp->others_len++; + if ((asp->others = realloc(asp->others, + asp->others_len * sizeof(struct attr *))) == NULL) + fatal("attr_optadd"); + + /* l stores the size of others before resize */ + asp->others[l] = a; + return (0); +} + +struct attr * +attr_optget(const struct rde_aspath *asp, u_int8_t type) +{ + u_int8_t l; + + for (l = 0; l < asp->others_len; l++) { + if (asp->others[l] == NULL) + break; + if (type == asp->others[l]->type) + return (asp->others[l]); + if (type < asp->others[l]->type) + break; + } + return (NULL); +} + +void +attr_copy(struct rde_aspath *t, struct rde_aspath *s) +{ + u_int8_t l; + + if (t->others != NULL) + attr_freeall(t); + + if ((t->others = calloc(s->others_len, sizeof(struct attr *))) == 0) + fatal("attr_copy"); + t->others_len = s->others_len; + + for (l = 0; l < t->others_len; l++) { + if (s->others[l] == NULL) + break; + s->others[l]->refcnt++; + rdemem.attr_refs++; + t->others[l] = s->others[l]; + } +} + +int +attr_diff(struct attr *oa, struct attr *ob) +{ + int r; + + if (oa->type > ob->type) + return (1); + if (oa->type < ob->type) + return (-1); + if (oa->len > ob->len) + return (1); + if (oa->len < ob->len) + return (-1); + r = memcmp(oa->data, ob->data, oa->len); + if (r > 0) + return (1); + if (r < 0) + return (-1); + + fatalx("attr_diff: equal attributes encountered"); + return (0); +} + +int +attr_compare(struct rde_aspath *a, struct rde_aspath *b) +{ + u_int8_t l, min; + + min = a->others_len < b->others_len ? a->others_len : b->others_len; + for (l = 0; l < min; l++) + if (a->others[l] != b->others[l]) + return (attr_diff(a->others[l], b->others[l])); + + if (a->others_len < b->others_len) { + for (; l < b->others_len; l++) + if (b->others[l] != NULL) + return (-1); + } else if (a->others_len < b->others_len) { + for (; l < a->others_len; l++) + if (a->others[l] != NULL) + return (1); + } + + return (0); +} + +void +attr_freeall(struct rde_aspath *asp) +{ + u_int8_t l; + + for (l = 0; l < asp->others_len; l++) + attr_put(asp->others[l]); + + free(asp->others); + asp->others = NULL; + asp->others_len = 0; +} + +struct attr * +attr_alloc(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len) +{ + struct attr *a; + a = calloc(1, sizeof(struct attr)); if (a == NULL) fatal("attr_optadd"); rdemem.attr_cnt++; a->flags = flags; + a->hash = hash32_buf(&flags, sizeof(flags), HASHINIT); a->type = type; + a->hash = hash32_buf(&type, sizeof(type), a->hash); a->len = len; if (len != 0) { - a->data = malloc(len); - if (a->data == NULL) + if ((a->data = malloc(len)) == NULL) fatal("attr_optadd"); rdemem.attr_dcnt++; @@ -90,65 +273,55 @@ attr_optadd(struct rde_aspath *asp, u_int8_t flags, u_int8_t type, } else a->data = NULL; - /* keep a sorted list */ - TAILQ_FOREACH_REVERSE(p, &asp->others, attr_list, entry) { - if (type == p->type) { - /* attribute allowed only once */ - if (len != 0) - rdemem.attr_dcnt--; - rdemem.attr_data -= len; - rdemem.attr_cnt--; - free(a->data); - free(a); - return (-1); - } - if (type > p->type) { - TAILQ_INSERT_AFTER(&asp->others, p, a, entry); - return (0); - } - } - TAILQ_INSERT_HEAD(&asp->others, a, entry); - return (0); + a->hash = hash32_buf(&len, sizeof(len), a->hash); + a->hash = hash32_buf(a->data, a->len, a->hash); + LIST_INSERT_HEAD(ATTR_HASH(a->hash), a, entry); + + return (a); } struct attr * -attr_optget(const struct rde_aspath *asp, u_int8_t type) +attr_lookup(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len) { - struct attr *a; + struct attr_list *head; + struct attr *a; + u_int32_t hash; + + hash = hash32_buf(&flags, sizeof(flags), HASHINIT); + hash = hash32_buf(&type, sizeof(type), hash); + hash = hash32_buf(&len, sizeof(len), hash); + hash = hash32_buf(data, len, hash); + head = ATTR_HASH(hash); - TAILQ_FOREACH(a, &asp->others, entry) { - if (type == a->type) + LIST_FOREACH(a, head, entry) { + if (hash == a->hash && type == a->type && + flags == a->flags && len == a->len && + memcmp(data, a->data, len) == 0) return (a); - if (type < a->type) - /* list is sorted */ - break; } return (NULL); } void -attr_optcopy(struct rde_aspath *t, struct rde_aspath *s) +attr_put(struct attr *a) { - struct attr *os; - - TAILQ_FOREACH(os, &s->others, entry) - attr_optadd(t, os->flags, os->type, os->data, os->len); -} + if (a == NULL) + return; -void -attr_optfree(struct rde_aspath *asp) -{ - struct attr *a; + rdemem.attr_refs--; + if (--a->refcnt > 0) + /* somebody still holds a reference */ + return; - while ((a = TAILQ_FIRST(&asp->others)) != NULL) { - TAILQ_REMOVE(&asp->others, a, entry); - if (a->len != 0) - rdemem.attr_dcnt--; - rdemem.attr_data -= a->len; - rdemem.attr_cnt--; - free(a->data); - free(a); - } + /* unlink */ + LIST_REMOVE(a, entry); + + if (a->len != 0) + rdemem.attr_dcnt--; + rdemem.attr_data -= a->len; + rdemem.attr_cnt--; + free(a->data); + free(a); } /* aspath specific functions */ @@ -219,7 +392,7 @@ aspath_shutdown(void) for (i = 0; i <= astable.hashmask; i++) if (!LIST_EMPTY(&astable.hashtbl[i])) - log_warnx("path_free: free non-free table"); + log_warnx("aspath_shutdown: free non-free table"); free(astable.hashtbl); } diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c index 58fb145f72a..7c371d372de 100644 --- a/usr.sbin/bgpd/rde_rib.c +++ b/usr.sbin/bgpd/rde_rib.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_rib.c,v 1.73 2006/01/04 16:13:07 claudio Exp $ */ +/* $OpenBSD: rde_rib.c,v 1.74 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org> @@ -118,7 +118,6 @@ path_update(struct rde_peer *peer, struct rde_aspath *nasp, int path_compare(struct rde_aspath *a, struct rde_aspath *b) { - struct attr *oa, *ob; int r; if (a->origin > b->origin) @@ -158,28 +157,7 @@ path_compare(struct rde_aspath *a, struct rde_aspath *b) if (r < 0) return (-1); - for (oa = TAILQ_FIRST(&a->others), ob = TAILQ_FIRST(&b->others); - oa != NULL && ob != NULL; - oa = TAILQ_NEXT(oa, entry), ob = TAILQ_NEXT(ob, entry)) { - if (oa->type > ob->type) - return (1); - if (oa->type < ob->type) - return (-1); - if (oa->len > ob->len) - return (1); - if (oa->len < ob->len) - return (-1); - r = memcmp(oa->data, ob->data, oa->len); - if (r > 0) - return (1); - if (r < 0) - return (-1); - } - if (oa != NULL) - return (1); - if (ob != NULL) - return (-1); - return (0); + return (attr_compare(a, b)); } struct rde_aspath * @@ -292,9 +270,7 @@ path_copy(struct rde_aspath *asp) rtlabel_ref(nasp->rtlabelid); nasp->flags = asp->flags & ~F_ATTR_LINKED; - - TAILQ_INIT(&nasp->others); - attr_optcopy(nasp, asp); + attr_copy(nasp, asp); return (nasp); } @@ -311,7 +287,6 @@ path_get(void) rdemem.path_cnt++; LIST_INIT(&asp->prefix_h); - TAILQ_INIT(&asp->others); asp->origin = ORIGIN_INCOMPLETE; asp->lpref = DEFAULT_LPREF; /* med = 0 */ @@ -330,7 +305,7 @@ path_put(struct rde_aspath *asp) rtlabel_unref(asp->rtlabelid); aspath_put(asp->aspath); - attr_optfree(asp); + attr_freeall(asp); rdemem.path_cnt--; free(asp); } diff --git a/usr.sbin/bgpd/rde_update.c b/usr.sbin/bgpd/rde_update.c index 04fef3b5df9..e9606c96803 100644 --- a/usr.sbin/bgpd/rde_update.c +++ b/usr.sbin/bgpd/rde_update.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_update.c,v 1.46 2005/12/30 14:07:40 claudio Exp $ */ +/* $OpenBSD: rde_update.c,v 1.47 2006/01/05 16:00:07 claudio Exp $ */ /* * Copyright (c) 2004 Claudio Jeker <claudio@openbsd.org> @@ -625,6 +625,7 @@ up_generate_attr(struct rde_peer *peer, struct update_attr *upa, in_addr_t nexthop; int r, ismp = 0; u_int16_t len = sizeof(up_attr_buf), wlen = 0; + u_int8_t l; /* origin */ if ((r = attr_write(up_attr_buf + wlen, len, ATTR_WELL_KNOWN, @@ -688,7 +689,9 @@ up_generate_attr(struct rde_peer *peer, struct update_attr *upa, * 3. transitive known attrs: announce unmodified * 4. transitive unknown attrs: set partial bit and re-announce */ - TAILQ_FOREACH(oa, &a->others, entry) { + for (l = 0; l < a->others_len; l++) { + if ((oa = a->others[l]) == NULL) + break; switch (oa->type) { case ATTR_ATOMIC_AGGREGATE: if ((r = attr_write(up_attr_buf + wlen, len, |