As mentioned I need a TAILQ for the list of prefixes that belong to a rib
entry. Mainly because I need TAILQ_PREV. This diff does this replacement.
I did not change the nexhtop LIST of prefixes to a TAILQ. Maybe something
to consider but there is no real need for that.
This is mostly a mechanical change. The only thing that had to change is
rde_softreconfig_sync_reeval() where before the LIST_HEAD was copied which
is not possible with TAILQ (there is a pointer to the TAILQ_HEAD struct
from inside the TAILQ). Instead use TAILQ_CONCAT() to move the queue from
the rib_entry to the local tailq head. I checked the rest of the code and
did not find any other case where the rib_entry prefix_h was copied
around.
I also have a fix for the unittest regress ready for this change. I left
that one out since it is just a trivial mechanical change.
--
:wq Claudio
Index: mrt.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/mrt.c,v
retrieving revision 1.106
diff -u -p -r1.106 mrt.c
--- mrt.c 6 Feb 2022 09:51:19 -0000 1.106
+++ mrt.c 21 Mar 2022 17:51:09 -0000
@@ -620,7 +620,7 @@ mrt_dump_entry_v2_rib(struct rib_entry *
*np = 0;
*app = 0;
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib) {
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib) {
struct nexthop *nexthop;
struct bgpd_addr *nh;
struct ibuf *tbuf;
@@ -895,7 +895,7 @@ mrt_dump_upcall(struct rib_entry *re, vo
* dumps the table so we do the same. If only the active route should
* be dumped p should be set to p = pt->active.
*/
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib) {
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib) {
if (mrtbuf->type == MRT_TABLE_DUMP)
mrt_dump_entry(mrtbuf, p, mrtbuf->seqnum++,
prefix_peer(p));
Index: rde.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.c,v
retrieving revision 1.543
diff -u -p -r1.543 rde.c
--- rde.c 21 Mar 2022 17:35:56 -0000 1.543
+++ rde.c 21 Mar 2022 17:41:29 -0000
@@ -2536,7 +2536,7 @@ rde_dump_upcall(struct rib_entry *re, vo
struct rde_dump_ctx *ctx = ptr;
struct prefix *p;
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib)
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib)
rde_dump_filter(p, &ctx->req, 0);
}
@@ -2557,14 +2557,14 @@ rde_dump_prefix_upcall(struct rib_entry
return;
if (!prefix_compare(&ctx->req.prefix, &addr,
ctx->req.prefixlen))
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib)
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib)
rde_dump_filter(p, &ctx->req, 0);
} else {
if (ctx->req.prefixlen < pt->prefixlen)
return;
if (!prefix_compare(&addr, &ctx->req.prefix,
pt->prefixlen))
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib)
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib)
rde_dump_filter(p, &ctx->req, 0);
}
}
@@ -3673,7 +3673,7 @@ rde_softreconfig_in(struct rib_entry *re
pt = re->prefix;
pt_getaddr(pt, &prefix);
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib) {
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib) {
asp = prefix_aspath(p);
peer = prefix_peer(p);
@@ -3736,7 +3736,7 @@ rde_softreconfig_out(struct rib_entry *r
static void
rde_softreconfig_sync_reeval(struct rib_entry *re, void *arg)
{
- struct prefix_list prefixes;
+ struct prefix_queue prefixes = TAILQ_HEAD_INITIALIZER(prefixes);
struct prefix *p, *next;
struct rib *rib = arg;
@@ -3746,7 +3746,7 @@ rde_softreconfig_sync_reeval(struct rib_
* all dependent adj-rib-out were already flushed
* unlink nexthop if it was linked
*/
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib) {
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib) {
if (p->flags & PREFIX_NEXTHOP_LINKED)
nexthop_unlink(p);
}
@@ -3754,8 +3754,7 @@ rde_softreconfig_sync_reeval(struct rib_
}
/* evaluation process is turned on, so evaluate all prefixes again */
- prefixes = re->prefix_h;
- LIST_INIT(&re->prefix_h);
+ TAILQ_CONCAT(&prefixes, &re->prefix_h, entry.list.rib);
/*
* TODO: this code works but is not optimal. prefix_evaluate()
@@ -3763,9 +3762,9 @@ rde_softreconfig_sync_reeval(struct rib_
* to resort the list once and then call rde_generate_updates()
* and rde_send_kroute() once.
*/
- LIST_FOREACH_SAFE(p, &prefixes, entry.list.rib, next) {
+ TAILQ_FOREACH_SAFE(p, &prefixes, entry.list.rib, next) {
/* need to re-link the nexthop if not already linked */
- LIST_REMOVE(p, entry.list.rib);
+ TAILQ_REMOVE(&prefixes, p, entry.list.rib);
if ((p->flags & PREFIX_NEXTHOP_LINKED) == 0)
nexthop_link(p);
prefix_evaluate(re, p, NULL);
@@ -3818,7 +3817,7 @@ rde_roa_softreload(struct rib_entry *re,
pt = re->prefix;
pt_getaddr(pt, &prefix);
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib) {
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib) {
asp = prefix_aspath(p);
peer = prefix_peer(p);
@@ -4163,7 +4162,7 @@ network_dump_upcall(struct rib_entry *re
struct bgpd_addr addr;
struct rde_dump_ctx *ctx = ptr;
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib) {
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib) {
asp = prefix_aspath(p);
if (!(asp->flags & F_PREFIX_ANNOUNCED))
continue;
Index: rde.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
retrieving revision 1.250
diff -u -p -r1.250 rde.h
--- rde.h 21 Mar 2022 17:35:56 -0000 1.250
+++ rde.h 21 Mar 2022 17:40:10 -0000
@@ -38,11 +38,12 @@ enum peer_state {
};
LIST_HEAD(prefix_list, prefix);
+TAILQ_HEAD(prefix_queue, prefix);
RB_HEAD(rib_tree, rib_entry);
struct rib_entry {
RB_ENTRY(rib_entry) rib_e;
- struct prefix_list prefix_h;
+ struct prefix_queue prefix_h;
struct pt_entry *prefix;
uint16_t rib_id;
uint16_t lock;
@@ -315,7 +316,8 @@ struct pt_entry_vpn6 {
struct prefix {
union {
struct {
- LIST_ENTRY(prefix) rib, nexthop;
+ TAILQ_ENTRY(prefix) rib;
+ LIST_ENTRY(prefix) nexthop;
struct rib_entry *re;
} list;
struct {
Index: rde_decide.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_decide.c,v
retrieving revision 1.90
diff -u -p -r1.90 rde_decide.c
--- rde_decide.c 21 Mar 2022 17:35:56 -0000 1.90
+++ rde_decide.c 21 Mar 2022 17:50:37 -0000
@@ -301,16 +301,16 @@ prefix_cmp(struct prefix *p1, struct pre
void
prefix_insert(struct prefix *new, struct prefix *ep, struct rib_entry *re)
{
- struct prefix_list redo = LIST_HEAD_INITIALIZER(redo);
- struct prefix *xp, *np, *tailp = NULL, *insertp = ep;
+ struct prefix_queue redo = TAILQ_HEAD_INITIALIZER(redo);
+ struct prefix *xp, *np, *insertp = ep;
int testall, selected = 0;
/* start scan at the entry point (ep) or the head if ep == NULL */
if (ep == NULL)
- ep = LIST_FIRST(&re->prefix_h);
+ ep = TAILQ_FIRST(&re->prefix_h);
for (xp = ep; xp != NULL; xp = np) {
- np = LIST_NEXT(xp, entry.list.rib);
+ np = TAILQ_NEXT(xp, entry.list.rib);
if (prefix_cmp(new, xp, &testall) > 0) {
/* new is preferred over xp */
@@ -321,14 +321,8 @@ prefix_insert(struct prefix *new, struct
* MED inversion, take out prefix and
* put it onto redo queue.
*/
- LIST_REMOVE(xp, entry.list.rib);
- if (tailp == NULL)
- LIST_INSERT_HEAD(&redo, xp,
- entry.list.rib);
- else
- LIST_INSERT_AFTER(tailp, xp,
- entry.list.rib);
- tailp = xp;
+ TAILQ_REMOVE(&re->prefix_h, xp, entry.list.rib);
+ TAILQ_INSERT_TAIL(&redo, xp, entry.list.rib);
} else {
/*
* lock insertion point and
@@ -355,14 +349,14 @@ prefix_insert(struct prefix *new, struct
}
if (insertp == NULL)
- LIST_INSERT_HEAD(&re->prefix_h, new, entry.list.rib);
+ TAILQ_INSERT_HEAD(&re->prefix_h, new, entry.list.rib);
else
- LIST_INSERT_AFTER(insertp, new, entry.list.rib);
+ TAILQ_INSERT_AFTER(&re->prefix_h, insertp, new, entry.list.rib);
/* Fixup MED order again. All elements are < new */
- while (!LIST_EMPTY(&redo)) {
- xp = LIST_FIRST(&redo);
- LIST_REMOVE(xp, entry.list.rib);
+ while (!TAILQ_EMPTY(&redo)) {
+ xp = TAILQ_FIRST(&redo);
+ TAILQ_REMOVE(&redo, xp, entry.list.rib);
prefix_insert(xp, new, re);
}
@@ -380,18 +374,18 @@ prefix_insert(struct prefix *new, struct
void
prefix_remove(struct prefix *old, struct rib_entry *re)
{
- struct prefix_list redo = LIST_HEAD_INITIALIZER(redo);
- struct prefix *xp, *np, *tailp = NULL;
+ struct prefix_queue redo = TAILQ_HEAD_INITIALIZER(redo);
+ struct prefix *xp, *np;
int testall;
- xp = LIST_NEXT(old, entry.list.rib);
- LIST_REMOVE(old, entry.list.rib);
+ xp = TAILQ_NEXT(old, entry.list.rib);
+ TAILQ_REMOVE(&re->prefix_h, old, entry.list.rib);
/* check if a MED inversion could be possible */
prefix_cmp(old, xp, &testall);
if (testall > 0) {
/* maybe MED route, scan tail for other possible routes */
for (; xp != NULL; xp = np) {
- np = LIST_NEXT(xp, entry.list.rib);
+ np = TAILQ_NEXT(xp, entry.list.rib);
/* only interested in the testall result */
prefix_cmp(old, xp, &testall);
@@ -402,22 +396,16 @@ prefix_remove(struct prefix *old, struct
* possible MED inversion, take out prefix and
* put it onto redo queue.
*/
- LIST_REMOVE(xp, entry.list.rib);
- if (tailp == NULL)
- LIST_INSERT_HEAD(&redo, xp,
- entry.list.rib);
- else
- LIST_INSERT_AFTER(tailp, xp,
- entry.list.rib);
- tailp = xp;
+ TAILQ_REMOVE(&re->prefix_h, xp, entry.list.rib);
+ TAILQ_INSERT_HEAD(&redo, xp, entry.list.rib);
}
}
}
/* Fixup MED order again, reinsert prefixes from the start */
- while (!LIST_EMPTY(&redo)) {
- xp = LIST_FIRST(&redo);
- LIST_REMOVE(xp, entry.list.rib);
+ while (!TAILQ_EMPTY(&redo)) {
+ xp = TAILQ_FIRST(&redo);
+ TAILQ_REMOVE(&redo, xp, entry.list.rib);
prefix_insert(xp, NULL, re);
}
@@ -454,7 +442,7 @@ prefix_best(struct rib_entry *re)
/* decision process is turned off */
return NULL;
- xp = LIST_FIRST(&re->prefix_h);
+ xp = TAILQ_FIRST(&re->prefix_h);
if (xp != NULL && !prefix_eligible(xp))
xp = NULL;
return xp;
@@ -477,9 +465,9 @@ prefix_evaluate(struct rib_entry *re, st
if (rib->flags & F_RIB_NOEVALUATE) {
/* decision process is turned off */
if (old != NULL)
- LIST_REMOVE(old, entry.list.rib);
+ TAILQ_REMOVE(&re->prefix_h, old, entry.list.rib);
if (new != NULL)
- LIST_INSERT_HEAD(&re->prefix_h, new, entry.list.rib);
+ TAILQ_INSERT_HEAD(&re->prefix_h, new, entry.list.rib);
return;
}
@@ -491,7 +479,7 @@ prefix_evaluate(struct rib_entry *re, st
if (new != NULL)
prefix_insert(new, NULL, re);
- xp = LIST_FIRST(&re->prefix_h);
+ xp = TAILQ_FIRST(&re->prefix_h);
if (xp != NULL && !prefix_eligible(xp))
xp = NULL;
Index: rde_peer.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_peer.c,v
retrieving revision 1.14
diff -u -p -r1.14 rde_peer.c
--- rde_peer.c 21 Mar 2022 17:35:56 -0000 1.14
+++ rde_peer.c 21 Mar 2022 17:52:23 -0000
@@ -248,7 +248,7 @@ peer_flush_upcall(struct rib_entry *re,
pt_getaddr(re->prefix, &addr);
prefixlen = re->prefix->prefixlen;
- LIST_FOREACH_SAFE(p, &re->prefix_h, entry.list.rib, np) {
+ TAILQ_FOREACH_SAFE(p, &re->prefix_h, entry.list.rib, np) {
if (peer != prefix_peer(p))
continue;
if (staletime && p->lastchange > staletime)
Index: rde_rib.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
retrieving revision 1.236
diff -u -p -r1.236 rde_rib.c
--- rde_rib.c 21 Mar 2022 17:35:56 -0000 1.236
+++ rde_rib.c 21 Mar 2022 17:43:17 -0000
@@ -252,7 +252,7 @@ rib_free(struct rib *rib)
* an empty check in prefix_destroy() it is not possible to
* use the default for loop.
*/
- while ((p = LIST_FIRST(&re->prefix_h))) {
+ while ((p = TAILQ_FIRST(&re->prefix_h))) {
struct rde_aspath *asp = prefix_aspath(p);
if (asp && asp->pftableid)
rde_pftable_del(asp->pftableid, p);
@@ -353,7 +353,7 @@ rib_add(struct rib *rib, struct bgpd_add
if ((re = calloc(1, sizeof(*re))) == NULL)
fatal("rib_add");
- LIST_INIT(&re->prefix_h);
+ TAILQ_INIT(&re->prefix_h);
re->prefix = pt_ref(pte);
re->rib_id = rib->id;
@@ -391,7 +391,7 @@ rib_remove(struct rib_entry *re)
int
rib_empty(struct rib_entry *re)
{
- return LIST_EMPTY(&re->prefix_h);
+ return TAILQ_EMPTY(&re->prefix_h);
}
static struct rib_entry *
@@ -1496,7 +1496,7 @@ prefix_bypeer(struct rib_entry *re, stru
{
struct prefix *p;
- LIST_FOREACH(p, &re->prefix_h, entry.list.rib)
+ TAILQ_FOREACH(p, &re->prefix_h, entry.list.rib)
if (prefix_peer(p) == peer && p->path_id == path_id)
return (p);
return (NULL);
Index: rde_update.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/rde_update.c,v
retrieving revision 1.137
diff -u -p -r1.137 rde_update.c
--- rde_update.c 15 Mar 2022 16:50:29 -0000 1.137
+++ rde_update.c 21 Mar 2022 17:51:39 -0000
@@ -154,7 +154,7 @@ again:
prefixlen, prefix_vstate(new), &state) == ACTION_DENY) {
rde_filterstate_clean(&state);
if (peer->flags & PEERFLAG_EVALUATE_ALL)
- new = LIST_NEXT(new, entry.list.rib);
+ new = TAILQ_NEXT(new, entry.list.rib);
else
new = NULL;
if (new != NULL && !prefix_eligible(new))
