From e54b04397b9c17a90c5e9a59c44f2d8b842d8cce Mon Sep 17 00:00:00 2001 From: claudio Date: Mon, 5 Feb 2018 23:29:59 +0000 Subject: [PATCH] Switch a few lists to tailqs. Mainly the prefix list per aspath needs to be a queue so that we can use it in the Adj-RIB-Out case. OK benno@ --- usr.sbin/bgpd/rde.c | 14 +++---- usr.sbin/bgpd/rde.h | 26 ++++++------ usr.sbin/bgpd/rde_rib.c | 91 ++++++++++++++++++++++++++++++----------- 3 files changed, 88 insertions(+), 43 deletions(-) diff --git a/usr.sbin/bgpd/rde.c b/usr.sbin/bgpd/rde.c index 072bcd630c9..7ec8171bc18 100644 --- a/usr.sbin/bgpd/rde.c +++ b/usr.sbin/bgpd/rde.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.c,v 1.375 2018/02/05 03:55:54 claudio Exp $ */ +/* $OpenBSD: rde.c,v 1.376 2018/02/05 23:29:59 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Henning Brauer @@ -3251,7 +3251,7 @@ peer_add(u_int32_t id, struct peer_config *p_conf) if (peer == NULL) fatal("peer_add"); - LIST_INIT(&peer->path_h); + TAILQ_INIT(&peer->path_h); memcpy(&peer->conf, p_conf, sizeof(struct peer_config)); peer->remote_bgpid = 0; peer->rib = rib_find(peer->conf.rib); @@ -3391,11 +3391,11 @@ peer_down(u_int32_t id) up_down(peer); /* walk through per peer RIB list and remove all prefixes. */ - for (asp = LIST_FIRST(&peer->path_h); asp != NULL; asp = nasp) { - nasp = LIST_NEXT(asp, peer_l); + for (asp = TAILQ_FIRST(&peer->path_h); asp != NULL; asp = nasp) { + nasp = TAILQ_NEXT(asp, peer_l); path_remove(asp); } - LIST_INIT(&peer->path_h); + TAILQ_INIT(&peer->path_h); peer->prefix_cnt = 0; /* Deletions are performed in path_remove() */ @@ -3418,8 +3418,8 @@ peer_flush(struct rde_peer *peer, u_int8_t aid) rprefixes = 0; /* walk through per peer RIB list and remove all stale prefixes. */ - for (asp = LIST_FIRST(&peer->path_h); asp != NULL; asp = nasp) { - nasp = LIST_NEXT(asp, peer_l); + for (asp = TAILQ_FIRST(&peer->path_h); asp != NULL; asp = nasp) { + nasp = TAILQ_NEXT(asp, peer_l); rprefixes += path_remove_stale(asp, aid); } diff --git a/usr.sbin/bgpd/rde.h b/usr.sbin/bgpd/rde.h index 2684d5e3120..84bdb0b7ad2 100644 --- a/usr.sbin/bgpd/rde.h +++ b/usr.sbin/bgpd/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.164 2018/02/05 03:55:54 claudio Exp $ */ +/* $OpenBSD: rde.h,v 1.165 2018/02/05 23:29:59 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker and @@ -41,9 +41,15 @@ enum peer_state { * Currently I assume that we can do that with the neighbor_ip... */ LIST_HEAD(rde_peer_head, rde_peer); +LIST_HEAD(aspath_list, aspath); +LIST_HEAD(attr_list, attr); +LIST_HEAD(prefix_list, prefix); +TAILQ_HEAD(prefix_queue, prefix); LIST_HEAD(aspath_head, rde_aspath); +TAILQ_HEAD(aspath_queue, rde_aspath); RB_HEAD(uptree_prefix, update_prefix); RB_HEAD(uptree_attr, update_attr); + struct rib_desc; struct rib; RB_HEAD(rib_tree, rib_entry); @@ -53,7 +59,7 @@ TAILQ_HEAD(uplist_attr, update_attr); struct rde_peer { LIST_ENTRY(rde_peer) hash_l; /* hash list over all peers */ LIST_ENTRY(rde_peer) peer_l; /* list of all peers */ - struct aspath_head path_h; /* list of all as paths */ + struct aspath_queue path_h; /* list of all as paths */ struct peer_config conf; struct bgpd_addr remote_addr; struct bgpd_addr local_v4_addr; @@ -91,8 +97,6 @@ struct rde_peer { #define AS_CONFED_SET 4 #define ASPATH_HEADER_SIZE (sizeof(struct aspath) - sizeof(u_char)) -LIST_HEAD(aspath_list, aspath); - struct aspath { LIST_ENTRY(aspath) entry; int refcnt; /* reference count */ @@ -150,15 +154,11 @@ struct mpattr { u_int16_t unreach_len; }; -LIST_HEAD(attr_list, attr); - struct path_table { struct aspath_head *path_hashtbl; u_int32_t path_hashmask; }; -LIST_HEAD(prefix_head, prefix); - #define F_ATTR_ORIGIN 0x00001 #define F_ATTR_ASPATH 0x00002 #define F_ATTR_NEXTHOP 0x00004 @@ -187,8 +187,9 @@ LIST_HEAD(prefix_head, prefix); #define DEFAULT_LPREF 100 struct rde_aspath { - LIST_ENTRY(rde_aspath) path_l, peer_l, nexthop_l; - struct prefix_head prefix_h; + LIST_ENTRY(rde_aspath) path_l, nexthop_l; + TAILQ_ENTRY(rde_aspath) peer_l, update_l; + struct prefix_queue prefixes, updates; struct attr **others; struct rde_peer *peer; struct aspath *aspath; @@ -281,7 +282,7 @@ struct rib_context { struct rib_entry { RB_ENTRY(rib_entry) rib_e; - struct prefix_head prefix_h; + struct prefix_list prefix_h; struct prefix *active; /* for fast access */ struct pt_entry *prefix; struct rib *__rib; /* mangled pointer with flags */ @@ -307,7 +308,8 @@ struct rib_desc { #define RIB_LOC_START 2 struct prefix { - LIST_ENTRY(prefix) rib_l, path_l; + LIST_ENTRY(prefix) rib_l; + TAILQ_ENTRY(prefix) path_l; struct rib_entry *re; union { struct rde_aspath *_aspath; diff --git a/usr.sbin/bgpd/rde_rib.c b/usr.sbin/bgpd/rde_rib.c index 349c66bd990..8959bbd8a04 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.156 2018/02/05 03:55:54 claudio Exp $ */ +/* $OpenBSD: rde_rib.c,v 1.157 2018/02/05 23:29:59 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker @@ -367,7 +367,7 @@ path_init(u_int32_t hashsize) for (hs = 1; hs < hashsize; hs <<= 1) ; - pathtable.path_hashtbl = calloc(hs, sizeof(struct aspath_head)); + pathtable.path_hashtbl = calloc(hs, sizeof(struct aspath_queue)); if (pathtable.path_hashtbl == NULL) fatal("path_init"); @@ -496,9 +496,17 @@ void path_remove(struct rde_aspath *asp) { struct prefix *p, *np; + int has_updates; - for (p = LIST_FIRST(&asp->prefix_h); p != NULL; p = np) { - np = LIST_NEXT(p, path_l); + /* + * Must check if we actually have updates before removing prefixes + * because if this is the case than the last prefix on prefixes will + * free the asp and so the access to updates is a use after free. + */ + has_updates = !TAILQ_EMPTY(&asp->updates); + + for (p = TAILQ_FIRST(&asp->prefixes); p != NULL; p = np) { + np = TAILQ_NEXT(p, path_l); if (asp->pftableid) { struct bgpd_addr addr; @@ -509,6 +517,12 @@ path_remove(struct rde_aspath *asp) } prefix_destroy(p); } + if (has_updates) + for (p = TAILQ_FIRST(&asp->updates); p != NULL; p = np) { + np = TAILQ_NEXT(p, path_l); + /* no need to worry about pftable on Adj-RIB-Out */ + prefix_destroy(p); + } } /* remove all stale routes or if staletime is 0 remove all routes for @@ -519,11 +533,18 @@ path_remove_stale(struct rde_aspath *asp, u_int8_t aid) struct prefix *p, *np; time_t staletime; u_int32_t rprefixes; + int has_updates; rprefixes=0; staletime = asp->peer->staletime[aid]; - for (p = LIST_FIRST(&asp->prefix_h); p != NULL; p = np) { - np = LIST_NEXT(p, path_l); + /* + * Same magic as in path_remove() but probably not needed here. + * This is called when a session flapped and during that time + * the pending updates for that peer are getting reset. + */ + has_updates = !TAILQ_EMPTY(&asp->updates); + for (p = TAILQ_FIRST(&asp->prefixes); p != NULL; p = np) { + np = TAILQ_NEXT(p, path_l); if (p->re->prefix->aid != aid) continue; @@ -545,11 +566,26 @@ path_remove_stale(struct rde_aspath *asp, u_int8_t aid) prefix_destroy(p); } + if (has_updates) + for (p = TAILQ_FIRST(&asp->updates); p != NULL; p = np) { + np = TAILQ_NEXT(p, path_l); + if (p->re->prefix->aid != aid) + continue; + + if (staletime && p->lastchange > staletime) + continue; + + /* no need to worry about pftable on Adj-RIB-Out */ + prefix_destroy(p); + } return (rprefixes); } -/* this function is only called by prefix_remove and path_remove */ +/* + * This function can only called when all prefix have been removed first. + * Normally this happens directly out of the prefix removal functions. + */ void path_destroy(struct rde_aspath *asp) { @@ -559,7 +595,7 @@ path_destroy(struct rde_aspath *asp) nexthop_unlink(asp); LIST_REMOVE(asp, path_l); - LIST_REMOVE(asp, peer_l); + TAILQ_REMOVE(&asp->peer->path_h, asp, peer_l); asp->peer = NULL; asp->nexthop = NULL; asp->flags &= ~F_ATTR_LINKED; @@ -570,7 +606,7 @@ path_destroy(struct rde_aspath *asp) int path_empty(struct rde_aspath *asp) { - return LIST_EMPTY(&asp->prefix_h); + return TAILQ_EMPTY(&asp->prefixes) && TAILQ_EMPTY(&asp->updates); } /* @@ -588,7 +624,7 @@ path_link(struct rde_aspath *asp, struct rde_peer *peer) head = PATH_HASH(asp->aspath); LIST_INSERT_HEAD(head, asp, path_l); - LIST_INSERT_HEAD(&peer->path_h, asp, peer_l); + TAILQ_INSERT_TAIL(&peer->path_h, asp, peer_l); asp->peer = peer; nexthop_link(asp); asp->flags |= F_ATTR_LINKED; @@ -635,7 +671,8 @@ path_get(void) fatal("path_alloc"); rdemem.path_cnt++; - LIST_INIT(&asp->prefix_h); + TAILQ_INIT(&asp->prefixes); + TAILQ_INIT(&asp->updates); asp->origin = ORIGIN_INCOMPLETE; asp->lpref = DEFAULT_LPREF; /* med = 0 */ @@ -736,7 +773,7 @@ prefix_move(struct rde_aspath *asp, struct prefix *p) np->lastchange = time(NULL); /* add to new as path */ - LIST_INSERT_HEAD(&asp->prefix_h, np, path_l); + TAILQ_INSERT_HEAD(&asp->prefixes, np, path_l); PREFIX_COUNT(asp, 1); /* * no need to update the peer prefix count because we are only moving @@ -756,7 +793,7 @@ prefix_move(struct rde_aspath *asp, struct prefix *p) /* remove old prefix node */ oasp = prefix_aspath(p); - LIST_REMOVE(p, path_l); + TAILQ_REMOVE(&oasp->prefixes, p, path_l); PREFIX_COUNT(oasp, -1); /* as before peer count needs no update because of move */ @@ -890,9 +927,11 @@ prefix_updateall(struct rde_aspath *asp, enum nexthop_state state, { struct prefix *p; - LIST_FOREACH(p, &asp->prefix_h, path_l) { + TAILQ_FOREACH(p, &asp->prefixes, path_l) { /* - * skip non local-RIBs or RIBs that are flagged as noeval. + * Skip non local-RIBs or RIBs that are flagged as noeval. + * There is no need to run over updates since that is only + * used on the Adj-RIB-Out. */ if (re_rib(p->re)->flags & F_RIB_NOEVALUATE) continue; @@ -933,6 +972,8 @@ prefix_destroy(struct prefix *p) struct rde_aspath *asp; asp = prefix_aspath(p); + PREFIX_COUNT(asp, -1); + prefix_unlink(p); prefix_free(p); @@ -949,13 +990,14 @@ prefix_network_clean(struct rde_peer *peer, time_t reloadtime, u_int32_t flags) struct rde_aspath *asp, *xasp; struct prefix *p, *xp; - for (asp = LIST_FIRST(&peer->path_h); asp != NULL; asp = xasp) { - xasp = LIST_NEXT(asp, peer_l); + for (asp = TAILQ_FIRST(&peer->path_h); asp != NULL; asp = xasp) { + xasp = TAILQ_NEXT(asp, peer_l); if ((asp->flags & F_ANN_DYNAMIC) != flags) continue; - for (p = LIST_FIRST(&asp->prefix_h); p != NULL; p = xp) { - xp = LIST_NEXT(p, path_l); + for (p = TAILQ_FIRST(&asp->prefixes); p != NULL; p = xp) { + xp = TAILQ_NEXT(p, path_l); if (reloadtime > p->lastchange) { + PREFIX_COUNT(asp, -1); prefix_unlink(p); prefix_free(p); } @@ -971,7 +1013,7 @@ prefix_network_clean(struct rde_peer *peer, time_t reloadtime, u_int32_t flags) static void prefix_link(struct prefix *pref, struct rib_entry *re, struct rde_aspath *asp) { - LIST_INSERT_HEAD(&asp->prefix_h, pref, path_l); + TAILQ_INSERT_HEAD(&asp->prefixes, pref, path_l); PREFIX_COUNT(asp, 1); pref->_p._aspath = asp; @@ -989,13 +1031,14 @@ static void prefix_unlink(struct prefix *pref) { struct rib_entry *re = pref->re; + struct prefix_queue *pq; /* make route decision */ LIST_REMOVE(pref, rib_l); prefix_evaluate(NULL, re); - LIST_REMOVE(pref, path_l); - PREFIX_COUNT(prefix_aspath(pref), -1); + pq = &prefix_aspath(pref)->prefixes; + TAILQ_REMOVE(pq, pref, path_l); if (rib_empty(re)) rib_remove(re); @@ -1005,8 +1048,8 @@ prefix_unlink(struct prefix *pref) pref->re = NULL; /* - * It's the caller's duty to remove empty aspath structures. - * Also freeing the unlinked prefix is the caller's duty. + * It's the caller's duty to do accounting and remove empty aspath + * structures. Also freeing the unlinked prefix is the caller's duty. */ } -- 2.20.1