diff options
| -rw-r--r-- | bgpd/bgp_route.c | 117 | ||||
| -rw-r--r-- | bgpd/bgp_table.h | 3 | ||||
| -rw-r--r-- | bgpd/bgpd.c | 19 | ||||
| -rw-r--r-- | bgpd/bgpd.h | 23 | ||||
| -rw-r--r-- | bgpd/rfapi/rfapi_import.c | 4 | ||||
| -rw-r--r-- | eigrpd/eigrp_packet.c | 2 | ||||
| -rw-r--r-- | ldpd/control.h | 2 | ||||
| -rw-r--r-- | ldpd/lde.h | 2 | ||||
| -rw-r--r-- | ldpd/ldpd.h | 2 | ||||
| -rw-r--r-- | ldpd/ldpe.h | 2 | ||||
| -rw-r--r-- | lib/freebsd-queue.h | 679 | ||||
| -rw-r--r-- | lib/imsg-buffer.c | 2 | ||||
| -rw-r--r-- | lib/imsg.c | 2 | ||||
| -rw-r--r-- | lib/prefix.c | 3 | ||||
| -rw-r--r-- | lib/prefix.h | 16 | ||||
| -rw-r--r-- | lib/queue.h | 707 | ||||
| -rw-r--r-- | lib/subdir.am | 3 | ||||
| -rw-r--r-- | lib/table.c | 20 | ||||
| -rw-r--r-- | lib/table.h | 20 | ||||
| -rw-r--r-- | lib/workqueue.c | 54 | ||||
| -rw-r--r-- | lib/workqueue.h | 36 | ||||
| -rw-r--r-- | ospfd/ospf_packet.c | 2 | ||||
| -rw-r--r-- | zebra/zebra_rib.c | 4 | ||||
| -rw-r--r-- | zebra/zebra_static.c | 4 |
24 files changed, 937 insertions, 791 deletions
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 35f793f861..bb204b01f1 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -2001,18 +2001,15 @@ int bgp_zebra_has_route_changed(struct bgp_node *rn, struct bgp_info *selected) struct bgp_process_queue { struct bgp *bgp; - struct bgp_node *rn; - afi_t afi; - safi_t safi; + STAILQ_HEAD(, bgp_node)pqueue; +#define BGP_PROCESS_QUEUE_EOIU_MARKER (1 << 0) + unsigned int flags; + unsigned int queued; }; -static wq_item_status bgp_process_main(struct work_queue *wq, void *data) +static void bgp_process_main_one(struct bgp *bgp, struct bgp_node *rn, + afi_t afi, safi_t safi) { - struct bgp_process_queue *pq = data; - struct bgp *bgp = pq->bgp; - struct bgp_node *rn = pq->rn; - afi_t afi = pq->afi; - safi_t safi = pq->safi; struct prefix *p = &rn->p; struct bgp_info *new_select; struct bgp_info *old_select; @@ -2033,7 +2030,7 @@ static wq_item_status bgp_process_main(struct work_queue *wq, void *data) bgp->main_peers_update_hold = 0; bgp_start_routeadv(bgp); - return WQ_SUCCESS; + return; } /* Best path selection. */ @@ -2114,7 +2111,7 @@ static wq_item_status bgp_process_main(struct work_queue *wq, void *data) } UNSET_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED); - return WQ_SUCCESS; + return; } /* If the user did "clear ip bgp prefix x.x.x.x" this flag will be set @@ -2192,21 +2189,42 @@ static wq_item_status bgp_process_main(struct work_queue *wq, void *data) bgp_info_reap(rn, old_select); UNSET_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED); - return WQ_SUCCESS; + return; } -static void bgp_processq_del(struct work_queue *wq, void *data) +static wq_item_status bgp_process_wq(struct work_queue *wq, void *data) { - struct bgp_process_queue *pq = data; + struct bgp_process_queue *pqnode = data; + struct bgp *bgp = pqnode->bgp; struct bgp_table *table; + struct bgp_node *rn, *nrn; + + /* eoiu marker */ + if (CHECK_FLAG(pqnode->flags, BGP_PROCESS_QUEUE_EOIU_MARKER)) { + bgp_process_main_one(bgp, NULL, 0, 0); - bgp_unlock(pq->bgp); - if (pq->rn) { - table = bgp_node_table(pq->rn); - bgp_unlock_node(pq->rn); + return WQ_SUCCESS; + } + + STAILQ_FOREACH_SAFE(rn, &pqnode->pqueue, pq, nrn) { + table = bgp_node_table(rn); + + bgp_process_main_one(bgp, rn, table->afi, table->safi); + + bgp_unlock_node(rn); bgp_table_unlock(table); } - XFREE(MTYPE_BGP_PROCESS_QUEUE, pq); + + return WQ_SUCCESS; +} + +static void bgp_processq_del(struct work_queue *wq, void *data) +{ + struct bgp_process_queue *pqnode = data; + + bgp_unlock(pqnode->bgp); + + XFREE(MTYPE_BGP_PROCESS_QUEUE, pqnode); } void bgp_process_queue_init(void) @@ -2221,7 +2239,7 @@ void bgp_process_queue_init(void) } } - bm->process_main_queue->spec.workfunc = &bgp_process_main; + bm->process_main_queue->spec.workfunc = &bgp_process_wq; bm->process_main_queue->spec.del_item_data = &bgp_processq_del; bm->process_main_queue->spec.max_retries = 0; bm->process_main_queue->spec.hold = 50; @@ -2229,31 +2247,56 @@ void bgp_process_queue_init(void) bm->process_main_queue->spec.yield = 50 * 1000L; } +static struct bgp_process_queue *bgp_process_queue_work(struct work_queue *wq, + struct bgp *bgp) +{ + struct bgp_process_queue *pqnode; + + pqnode = XCALLOC(MTYPE_BGP_PROCESS_QUEUE, sizeof(struct bgp_process_queue)); + + /* unlocked in bgp_processq_del */ + pqnode->bgp = bgp_lock(bgp); + STAILQ_INIT(&pqnode->pqueue); + + work_queue_add(wq, pqnode); + + return pqnode; +} + void bgp_process(struct bgp *bgp, struct bgp_node *rn, afi_t afi, safi_t safi) { +#define ARBITRARY_PROCESS_QLEN 10000 + struct work_queue *wq = bm->process_main_queue; struct bgp_process_queue *pqnode; /* already scheduled for processing? */ if (CHECK_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED)) return; - if (bm->process_main_queue == NULL) + if (wq == NULL) return; - pqnode = XCALLOC(MTYPE_BGP_PROCESS_QUEUE, - sizeof(struct bgp_process_queue)); - if (!pqnode) - return; + /* Add route nodes to an existing work queue item until reaching the + limit only if is from the same BGP view and it's not an EOIU marker */ + if (work_queue_item_count(wq)) { + struct work_queue_item *item = work_queue_last_item(wq); + pqnode = item->data; + + if (CHECK_FLAG(pqnode->flags, BGP_PROCESS_QUEUE_EOIU_MARKER) || + pqnode->bgp != bgp || pqnode->queued >= ARBITRARY_PROCESS_QLEN) + pqnode = bgp_process_queue_work(wq, bgp); + } else + pqnode = bgp_process_queue_work(wq, bgp); - /* all unlocked in bgp_processq_del */ + /* all unlocked in bgp_process_wq */ bgp_table_lock(bgp_node_table(rn)); - pqnode->rn = bgp_lock_node(rn); - pqnode->bgp = bgp; - bgp_lock(bgp); - pqnode->afi = afi; - pqnode->safi = safi; - work_queue_add(bm->process_main_queue, pqnode); + SET_FLAG(rn->flags, BGP_NODE_PROCESS_SCHEDULED); + bgp_lock_node(rn); + + STAILQ_INSERT_TAIL(&pqnode->pqueue, rn, pq); + pqnode->queued++; + return; } @@ -2264,15 +2307,9 @@ void bgp_add_eoiu_mark(struct bgp *bgp) if (bm->process_main_queue == NULL) return; - pqnode = XCALLOC(MTYPE_BGP_PROCESS_QUEUE, - sizeof(struct bgp_process_queue)); - if (!pqnode) - return; + pqnode = bgp_process_queue_work(bm->process_main_queue, bgp); - pqnode->rn = NULL; - pqnode->bgp = bgp; - bgp_lock(bgp); - work_queue_add(bm->process_main_queue, pqnode); + SET_FLAG(pqnode->flags, BGP_PROCESS_QUEUE_EOIU_MARKER); } static int bgp_maximum_prefix_restart_timer(struct thread *thread) diff --git a/bgpd/bgp_table.h b/bgpd/bgp_table.h index 0d5706f7cb..a4f3b604c2 100644 --- a/bgpd/bgp_table.h +++ b/bgpd/bgp_table.h @@ -23,6 +23,7 @@ #include "mpls.h" #include "table.h" +#include "queue.h" struct bgp_table { /* afi/safi of this table */ @@ -52,6 +53,8 @@ struct bgp_node { struct bgp_node *prn; + STAILQ_ENTRY(bgp_node) pq; + mpls_label_t local_label; uint64_t version; diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c index d7733fbacd..9d7c38c871 100644 --- a/bgpd/bgpd.c +++ b/bgpd/bgpd.c @@ -1116,9 +1116,8 @@ struct peer *peer_new(struct bgp *bgp) peer->status = Idle; peer->ostatus = Idle; peer->cur_event = peer->last_event = peer->last_major_event = 0; - peer->bgp = bgp; + peer->bgp = bgp_lock(bgp); peer = peer_lock(peer); /* initial reference */ - bgp_lock(bgp); peer->password = NULL; /* Set default flags. */ @@ -3106,21 +3105,7 @@ int bgp_delete(struct bgp *bgp) return 0; } -static void bgp_free(struct bgp *); - -void bgp_lock(struct bgp *bgp) -{ - ++bgp->lock; -} - -void bgp_unlock(struct bgp *bgp) -{ - assert(bgp->lock > 0); - if (--bgp->lock == 0) - bgp_free(bgp); -} - -static void bgp_free(struct bgp *bgp) +void bgp_free(struct bgp *bgp) { afi_t afi; safi_t safi; diff --git a/bgpd/bgpd.h b/bgpd/bgpd.h index bfdddc69b1..f6e7b2277f 100644 --- a/bgpd/bgpd.h +++ b/bgpd/bgpd.h @@ -1252,9 +1252,6 @@ extern int bgp_flag_set(struct bgp *, int); extern int bgp_flag_unset(struct bgp *, int); extern int bgp_flag_check(struct bgp *, int); -extern void bgp_lock(struct bgp *); -extern void bgp_unlock(struct bgp *); - extern void bgp_router_id_zebra_bump(vrf_id_t, const struct prefix *); extern int bgp_router_id_static_set(struct bgp *, struct in_addr); @@ -1395,6 +1392,20 @@ extern struct peer_af *peer_af_find(struct peer *, afi_t, safi_t); extern int peer_af_delete(struct peer *, afi_t, safi_t); extern void bgp_close(void); +extern void bgp_free(struct bgp *); + +static inline struct bgp *bgp_lock(struct bgp *bgp) +{ + bgp->lock++; + return bgp; +} + +static inline void bgp_unlock(struct bgp *bgp) +{ + assert(bgp->lock > 0); + if (--bgp->lock == 0) + bgp_free(bgp); +} static inline int afindex(afi_t afi, safi_t safi) { @@ -1540,10 +1551,8 @@ static inline struct vrf *bgp_vrf_lookup_by_instance_type(struct bgp *bgp) static inline void bgp_vrf_link(struct bgp *bgp, struct vrf *vrf) { bgp->vrf_id = vrf->vrf_id; - if (vrf->info != (void *)bgp) { - bgp_lock(bgp); - vrf->info = (void *)bgp; - } + if (vrf->info != (void *)bgp) + vrf->info = (void *)bgp_lock(bgp); } /* Unlink BGP instance from VRF. */ diff --git a/bgpd/rfapi/rfapi_import.c b/bgpd/rfapi/rfapi_import.c index 7e0ed9150b..d63975a22b 100644 --- a/bgpd/rfapi/rfapi_import.c +++ b/bgpd/rfapi/rfapi_import.c @@ -1224,8 +1224,8 @@ static int rfapiVpnBiSamePtUn(struct bgp_info *bi1, struct bgp_info *bi2) switch (pfx_un1.family) { case AF_INET: - if (!IPV4_ADDR_SAME(&pfx_un1.u.prefix4.s_addr, - &pfx_un2.u.prefix4.s_addr)) + if (!IPV4_ADDR_SAME(&pfx_un1.u.prefix4, + &pfx_un2.u.prefix4)) return 0; break; case AF_INET6: diff --git a/eigrpd/eigrp_packet.c b/eigrpd/eigrp_packet.c index 3b4a57ed54..72aaef1b37 100644 --- a/eigrpd/eigrp_packet.c +++ b/eigrpd/eigrp_packet.c @@ -527,7 +527,7 @@ int eigrp_read(struct thread *thread) /* Self-originated packet should be discarded silently. */ if (eigrp_if_lookup_by_local_addr(eigrp, NULL, iph->ip_src) - || (IPV4_ADDR_SAME(&iph->ip_src.s_addr, &ei->address->u.prefix4))) { + || (IPV4_ADDR_SAME(&iph->ip_src, &ei->address->u.prefix4))) { if (IS_DEBUG_EIGRP_TRANSMIT(0, RECV)) zlog_debug( "eigrp_read[%s]: Dropping self-originated packet", diff --git a/ldpd/control.h b/ldpd/control.h index 0e66a1636a..23edb5f24d 100644 --- a/ldpd/control.h +++ b/ldpd/control.h @@ -19,7 +19,7 @@ #ifndef _CONTROL_H_ #define _CONTROL_H_ -#include "openbsd-queue.h" +#include "queue.h" struct ctl_conn { TAILQ_ENTRY(ctl_conn) entry; diff --git a/ldpd/lde.h b/ldpd/lde.h index 43f1d36481..94077d1631 100644 --- a/ldpd/lde.h +++ b/ldpd/lde.h @@ -21,7 +21,7 @@ #ifndef _LDE_H_ #define _LDE_H_ -#include "openbsd-queue.h" +#include "queue.h" #include "openbsd-tree.h" #include "if.h" diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 31d0bc69b1..5580ea5d67 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -22,7 +22,7 @@ #ifndef _LDPD_H_ #define _LDPD_H_ -#include "openbsd-queue.h" +#include "queue.h" #include "openbsd-tree.h" #include "imsg.h" #include "thread.h" diff --git a/ldpd/ldpe.h b/ldpd/ldpe.h index 74f6b852b0..ccff1e803d 100644 --- a/ldpd/ldpe.h +++ b/ldpd/ldpe.h @@ -21,7 +21,7 @@ #ifndef _LDPE_H_ #define _LDPE_H_ -#include "openbsd-queue.h" +#include "queue.h" #include "openbsd-tree.h" #ifdef __OpenBSD__ #include <net/pfkeyv2.h> diff --git a/lib/freebsd-queue.h b/lib/freebsd-queue.h new file mode 100644 index 0000000000..d198f5674f --- /dev/null +++ b/lib/freebsd-queue.h @@ -0,0 +1,679 @@ +/*- + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + * $FreeBSD$ + */ + +#ifndef _SYS_QUEUE_H_ +#define _SYS_QUEUE_H_ + +/* + * This file defines four types of data structures: singly-linked lists, + * singly-linked tail queues, lists and tail queues. + * + * A singly-linked list is headed by a single forward pointer. The elements + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary elements. New elements can be + * added to the list after an existing element or at the head of the list. + * Elements being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + * + * A singly-linked tail queue is headed by a pair of pointers, one to the + * head of the list and the other to the tail of the list. The elements are + * singly linked for minimum space and pointer manipulation overhead at the + * expense of O(n) removal for arbitrary elements. New elements can be added + * to the list after an existing element, at the head of the list, or at the + * end of the list. Elements being removed from the head of the tail queue + * should use the explicit macro for this purpose for optimum efficiency. + * A singly-linked tail queue may only be traversed in the forward direction. + * Singly-linked tail queues are ideal for applications with large datasets + * and few or no removals or for implementing a FIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * For details on the use of these macros, see the queue(3) manual page. + * + * + * SLIST LIST STAILQ TAILQ + * _HEAD + + + + + * _HEAD_INITIALIZER + + + + + * _ENTRY + + + + + * _INIT + + + + + * _EMPTY + + + + + * _FIRST + + + + + * _NEXT + + + + + * _PREV - - - + + * _LAST - - + + + * _FOREACH + + + + + * _FOREACH_SAFE + + + + + * _FOREACH_REVERSE - - - + + * _FOREACH_REVERSE_SAFE - - - + + * _INSERT_HEAD + + + + + * _INSERT_BEFORE - + - + + * _INSERT_AFTER + + + + + * _INSERT_TAIL - - + + + * _CONCAT - - + + + * _REMOVE_AFTER + - + - + * _REMOVE_HEAD + - + - + * _REMOVE + + + + + * _SWAP + + + + + * + */ +#ifdef QUEUE_MACRO_DEBUG +/* Store the last 2 places the queue element or head was altered */ +struct qm_trace { + char *lastfile; + int lastline; + char *prevfile; + int prevline; +}; + +#define TRACEBUF struct qm_trace trace; +#define TRASHIT(x) do {(x) = (void *)-1;} while (0) +#define QMD_SAVELINK(name, link) void **name = (void *)&(link) + +#define QMD_TRACE_HEAD(head) \ + do { \ + (head)->trace.prevline = (head)->trace.lastline; \ + (head)->trace.prevfile = (head)->trace.lastfile; \ + (head)->trace.lastline = __LINE__; \ + (head)->trace.lastfile = __FILE__; \ + } while (0) + +#define QMD_TRACE_ELEM(elem) \ + do { \ + (elem)->trace.prevline = (elem)->trace.lastline; \ + (elem)->trace.prevfile = (elem)->trace.lastfile; \ + (elem)->trace.lastline = __LINE__; \ + (elem)->trace.lastfile = __FILE__; \ + } while (0) + +#else +#define QMD_TRACE_ELEM(elem) +#define QMD_TRACE_HEAD(head) +#define QMD_SAVELINK(name, link) +#define TRACEBUF +#define TRASHIT(x) +#endif /* QUEUE_MACRO_DEBUG */ + +/* + * Singly-linked List declarations. + */ +#define SLIST_HEAD(name, type) \ + struct name { \ + struct type *slh_first; /* first element */ \ + } + +#define SLIST_HEAD_INITIALIZER(head) \ + { \ + NULL \ + } + +#define SLIST_ENTRY(type) \ + struct { \ + struct type *sle_next; /* next element */ \ + } + +/* + * Singly-linked List functions. + */ +#define SLIST_EMPTY(head) ((head)->slh_first == NULL) + +#define SLIST_FIRST(head) ((head)->slh_first) + +#define SLIST_FOREACH(var, head, field) \ + for ((var) = SLIST_FIRST((head)); (var); \ + (var) = SLIST_NEXT((var), field)) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST((head)); \ + (var) && ((tvar) = SLIST_NEXT((var), field), 1); (var) = (tvar)) + +#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ + for ((varp) = &SLIST_FIRST((head)); ((var) = *(varp)) != NULL; \ + (varp) = &SLIST_NEXT((var), field)) + +#define SLIST_INIT(head) \ + do { \ + SLIST_FIRST((head)) = NULL; \ + } while (0) + +#define SLIST_INSERT_AFTER(slistelm, elm, field) \ + do { \ + SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ + SLIST_NEXT((slistelm), field) = (elm); \ + } while (0) + +#define SLIST_INSERT_HEAD(head, elm, field) \ + do { \ + SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ + SLIST_FIRST((head)) = (elm); \ + } while (0) + +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_REMOVE(head, elm, type, field) \ + do { \ + QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ + if (SLIST_FIRST((head)) == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = SLIST_FIRST((head)); \ + while (SLIST_NEXT(curelm, field) != (elm)) \ + curelm = SLIST_NEXT(curelm, field); \ + SLIST_REMOVE_AFTER(curelm, field); \ + } \ + TRASHIT(*oldnext); \ + } while (0) + +#define SLIST_REMOVE_AFTER(elm, field) \ + do { \ + SLIST_NEXT(elm, field) = \ + SLIST_NEXT(SLIST_NEXT(elm, field), field); \ + } while (0) + +#define SLIST_REMOVE_HEAD(head, field) \ + do { \ + SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ + } while (0) + +#define SLIST_SWAP(head1, head2, type) \ + do { \ + struct type *swap_first = SLIST_FIRST(head1); \ + SLIST_FIRST(head1) = SLIST_FIRST(head2); \ + SLIST_FIRST(head2) = swap_first; \ + } while (0) + +/* + * Singly-linked Tail queue declarations. + */ +#define STAILQ_HEAD(name, type) \ + struct name { \ + struct type *stqh_first; /* first element */ \ + struct type **stqh_last; /* addr of last next element */ \ + } + +#define STAILQ_HEAD_INITIALIZER(head) \ + { \ + NULL, &(head).stqh_first \ + } + +#define STAILQ_ENTRY(type) \ + struct { \ + struct type *stqe_next; /* next element */ \ + } + +/* + * Singly-linked Tail queue functions. + */ +#define STAILQ_CONCAT(head1, head2) \ + do { \ + if (!STAILQ_EMPTY((head2))) { \ + *(head1)->stqh_last = (head2)->stqh_first; \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_INIT((head2)); \ + } \ + } while (0) + +#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) + +#define STAILQ_FIRST(head) ((head)->stqh_first) + +#define STAILQ_FOREACH(var, head, field) \ + for ((var) = STAILQ_FIRST((head)); (var); \ + (var) = STAILQ_NEXT((var), field)) + + +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = STAILQ_FIRST((head)); \ + (var) && ((tvar) = STAILQ_NEXT((var), field), 1); (var) = (tvar)) + +#define STAILQ_INIT(head) \ + do { \ + STAILQ_FIRST((head)) = NULL; \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ + } while (0) + +#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) \ + do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) \ + == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_NEXT((tqelm), field) = (elm); \ + } while (0) + +#define STAILQ_INSERT_HEAD(head, elm, field) \ + do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) \ + == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_FIRST((head)) = (elm); \ + } while (0) + +#define STAILQ_INSERT_TAIL(head, elm, field) \ + do { \ + STAILQ_NEXT((elm), field) = NULL; \ + *(head)->stqh_last = (elm); \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + } while (0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) \ + ? NULL \ + : ((struct type *)(void *)((char *)((head)->stqh_last) \ + - offsetof(struct type, \ + field)))) + +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) + +#define STAILQ_REMOVE(head, elm, type, field) \ + do { \ + QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ + if (STAILQ_FIRST((head)) == (elm)) { \ + STAILQ_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = STAILQ_FIRST((head)); \ + while (STAILQ_NEXT(curelm, field) != (elm)) \ + curelm = STAILQ_NEXT(curelm, field); \ + STAILQ_REMOVE_AFTER(head, curelm, field); \ + } \ + TRASHIT(*oldnext); \ + } while (0) + +#define STAILQ_REMOVE_AFTER(head, elm, field) \ + do { \ + if ((STAILQ_NEXT(elm, field) = \ + STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) \ + == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + } while (0) + +#define STAILQ_REMOVE_HEAD(head, field) \ + do { \ + if ((STAILQ_FIRST((head)) = \ + STAILQ_NEXT(STAILQ_FIRST((head)), field)) \ + == NULL) \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ + } while (0) + +#define STAILQ_SWAP(head1, head2, type) \ + do { \ + struct type *swap_first = STAILQ_FIRST(head1); \ + struct type **swap_last = (head1)->stqh_last; \ + STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_FIRST(head2) = swap_first; \ + (head2)->stqh_last = swap_last; \ + if (STAILQ_EMPTY(head1)) \ + (head1)->stqh_last = &STAILQ_FIRST(head1); \ + if (STAILQ_EMPTY(head2)) \ + (head2)->stqh_last = &STAILQ_FIRST(head2); \ + } while (0) + + +/* + * List declarations. + */ +#define LIST_HEAD(name, type) \ + struct name { \ + struct type *lh_first; /* first element */ \ + } + +#define LIST_HEAD_INITIALIZER(head) \ + { \ + NULL \ + } + +#define LIST_ENTRY(type) \ + struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ + } + +/* + * List functions. + */ + +#if (defined(_KERNEL) && defined(INVARIANTS)) +#define QMD_LIST_CHECK_HEAD(head, field) \ + do { \ + if (LIST_FIRST((head)) != NULL \ + && LIST_FIRST((head))->field.le_prev \ + != &LIST_FIRST((head))) \ + panic("Bad list head %p first->prev != head", (head)); \ + } while (0) + +#define QMD_LIST_CHECK_NEXT(elm, field) \ + do { \ + if (LIST_NEXT((elm), field) != NULL \ + && LIST_NEXT((elm), field)->field.le_prev \ + != &((elm)->field.le_next)) \ + panic("Bad link elm %p next->prev != elm", (elm)); \ + } while (0) + +#define QMD_LIST_CHECK_PREV(elm, field) \ + do { \ + if (*(elm)->field.le_prev != (elm)) \ + panic("Bad link elm %p prev->next != elm", (elm)); \ + } while (0) +#else +#define QMD_LIST_CHECK_HEAD(head, field) +#define QMD_LIST_CHECK_NEXT(elm, field) +#define QMD_LIST_CHECK_PREV(elm, field) +#endif /* (_KERNEL && INVARIANTS) */ + +#define LIST_EMPTY(head) ((head)->lh_first == NULL) + +#define LIST_FIRST(head) ((head)->lh_first) + +#define LIST_FOREACH(var, head, field) \ + for ((var) = LIST_FIRST((head)); (var); (var) = LIST_NEXT((var), field)) + +#define LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST((head)); \ + (var) && ((tvar) = LIST_NEXT((var), field), 1); (var) = (tvar)) + +#define LIST_INIT(head) \ + do { \ + LIST_FIRST((head)) = NULL; \ + } while (0) + +#define LIST_INSERT_AFTER(listelm, elm, field) \ + do { \ + QMD_LIST_CHECK_NEXT(listelm, field); \ + if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) \ + != NULL) \ + LIST_NEXT((listelm), field)->field.le_prev = \ + &LIST_NEXT((elm), field); \ + LIST_NEXT((listelm), field) = (elm); \ + (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ + } while (0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) \ + do { \ + QMD_LIST_CHECK_PREV(listelm, field); \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + LIST_NEXT((elm), field) = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ + } while (0) + +#define LIST_INSERT_HEAD(head, elm, field) \ + do { \ + QMD_LIST_CHECK_HEAD((head), field); \ + if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ + LIST_FIRST((head))->field.le_prev = \ + &LIST_NEXT((elm), field); \ + LIST_FIRST((head)) = (elm); \ + (elm)->field.le_prev = &LIST_FIRST((head)); \ + } while (0) + +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_REMOVE(elm, field) \ + do { \ + QMD_SAVELINK(oldnext, (elm)->field.le_next); \ + QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ + QMD_LIST_CHECK_NEXT(elm, field); \ + QMD_LIST_CHECK_PREV(elm, field); \ + if (LIST_NEXT((elm), field) != NULL) \ + LIST_NEXT((elm), field)->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = LIST_NEXT((elm), field); \ + TRASHIT(*oldnext); \ + TRASHIT(*oldprev); \ + } while (0) + +#define LIST_SWAP(head1, head2, type, field) \ + do { \ + struct type *swap_tmp = LIST_FIRST((head1)); \ + LIST_FIRST((head1)) = LIST_FIRST((head2)); \ + LIST_FIRST((head2)) = swap_tmp; \ + if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ + swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ + if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ + swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ + } while (0) + +/* + * Tail queue declarations. + */ +#define TAILQ_HEAD(name, type) \ + struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ + TRACEBUF \ + } + +#define TAILQ_HEAD_INITIALIZER(head) \ + { \ + NULL, &(head).tqh_first \ + } + +#define TAILQ_ENTRY(type) \ + struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ + TRACEBUF \ + } + +/* + * Tail queue functions. + */ +#if (defined(_KERNEL) && defined(INVARIANTS)) +#define QMD_TAILQ_CHECK_HEAD(head, field) \ + do { \ + if (!TAILQ_EMPTY(head) \ + && TAILQ_FIRST((head))->field.tqe_prev \ + != &TAILQ_FIRST((head))) \ + panic("Bad tailq head %p first->prev != head", \ + (head)); \ + } while (0) + +#define QMD_TAILQ_CHECK_TAIL(head, field) \ + do { \ + if (*(head)->tqh_last != NULL) \ + panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ + } while (0) + +#define QMD_TAILQ_CHECK_NEXT(elm, field) \ + do { \ + if (TAILQ_NEXT((elm), field) != NULL \ + && TAILQ_NEXT((elm), field)->field.tqe_prev \ + != &((elm)->field.tqe_next)) \ + panic("Bad link elm %p next->prev != elm", (elm)); \ + } while (0) + +#define QMD_TAILQ_CHECK_PREV(elm, field) \ + do { \ + if (*(elm)->field.tqe_prev != (elm)) \ + panic("Bad link elm %p prev->next != elm", (elm)); \ + } while (0) +#else +#define QMD_TAILQ_CHECK_HEAD(head, field) +#define QMD_TAILQ_CHECK_TAIL(head, headname) +#define QMD_TAILQ_CHECK_NEXT(elm, field) +#define QMD_TAILQ_CHECK_PREV(elm, field) +#endif /* (_KERNEL && INVARIANTS) */ + +#define TAILQ_CONCAT(head1, head2, field) \ + do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = \ + (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + QMD_TRACE_HEAD(head1); \ + QMD_TRACE_HEAD(head2); \ + } \ + } while (0) + +#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) + +#define TAILQ_FIRST(head) ((head)->tqh_first) + +#define TAILQ_FOREACH(var, head, field) \ + for ((var) = TAILQ_FIRST((head)); (var); \ + (var) = TAILQ_NEXT((var), field)) + +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST((head)); \ + (var) && ((tvar) = TAILQ_NEXT((var), field), 1); (var) = (tvar)) + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for ((var) = TAILQ_LAST((head), headname); (var); \ + (var) = TAILQ_PREV((var), headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ + (var) = (tvar)) + +#define TAILQ_INIT(head) \ + do { \ + TAILQ_FIRST((head)) = NULL; \ + (head)->tqh_last = &TAILQ_FIRST((head)); \ + QMD_TRACE_HEAD(head); \ + } while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + QMD_TAILQ_CHECK_NEXT(listelm, field); \ + if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) \ + != NULL) \ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ + &TAILQ_NEXT((elm), field); \ + else { \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + QMD_TRACE_HEAD(head); \ + } \ + TAILQ_NEXT((listelm), field) = (elm); \ + (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ + QMD_TRACE_ELEM(&(elm)->field); \ + QMD_TRACE_ELEM(&listelm->field); \ + } while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) \ + do { \ + QMD_TAILQ_CHECK_PREV(listelm, field); \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + TAILQ_NEXT((elm), field) = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ + QMD_TRACE_ELEM(&(elm)->field); \ + QMD_TRACE_ELEM(&listelm->field); \ + } while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) \ + do { \ + QMD_TAILQ_CHECK_HEAD(head, field); \ + if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ + TAILQ_FIRST((head))->field.tqe_prev = \ + &TAILQ_NEXT((elm), field); \ + else \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + TAILQ_FIRST((head)) = (elm); \ + (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ + QMD_TRACE_HEAD(head); \ + QMD_TRACE_ELEM(&(elm)->field); \ + } while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) \ + do { \ + QMD_TAILQ_CHECK_TAIL(head, field); \ + TAILQ_NEXT((elm), field) = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + QMD_TRACE_HEAD(head); \ + QMD_TRACE_ELEM(&(elm)->field); \ + } while (0) + +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) + +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) + +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) + +#define TAILQ_REMOVE(head, elm, field) \ + do { \ + QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ + QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ + QMD_TAILQ_CHECK_NEXT(elm, field); \ + QMD_TAILQ_CHECK_PREV(elm, field); \ + if ((TAILQ_NEXT((elm), field)) != NULL) \ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else { \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + QMD_TRACE_HEAD(head); \ + } \ + *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ + TRASHIT(*oldnext); \ + TRASHIT(*oldprev); \ + QMD_TRACE_ELEM(&(elm)->field); \ + } while (0) + +#define TAILQ_SWAP(head1, head2, type, field) \ + do { \ + struct type *swap_first = (head1)->tqh_first; \ + struct type **swap_last = (head1)->tqh_last; \ + (head1)->tqh_first = (head2)->tqh_first; \ + (head1)->tqh_last = (head2)->tqh_last; \ + (head2)->tqh_first = swap_first; \ + (head2)->tqh_last = swap_last; \ + if ((swap_first = (head1)->tqh_first) != NULL) \ + swap_first->field.tqe_prev = &(head1)->tqh_first; \ + else \ + (head1)->tqh_last = &(head1)->tqh_first; \ + if ((swap_first = (head2)->tqh_first) != NULL) \ + swap_first->field.tqe_prev = &(head2)->tqh_first; \ + else \ + (head2)->tqh_last = &(head2)->tqh_first; \ + } while (0) + +#endif /* !_SYS_QUEUE_H_ */ diff --git a/lib/imsg-buffer.c b/lib/imsg-buffer.c index a486fc17c1..ae660504e4 100644 --- a/lib/imsg-buffer.c +++ b/lib/imsg-buffer.c @@ -18,7 +18,7 @@ #include <zebra.h> -#include "openbsd-queue.h" +#include "queue.h" #include "imsg.h" int ibuf_realloc(struct ibuf *, size_t); diff --git a/lib/imsg.c b/lib/imsg.c index fc62c13734..999ab679b8 100644 --- a/lib/imsg.c +++ b/lib/imsg.c @@ -18,7 +18,7 @@ #include <zebra.h> -#include "openbsd-queue.h" +#include "queue.h" #include "imsg.h" int imsg_fd_overhead = 0; diff --git a/lib/prefix.c b/lib/prefix.c index de521b2e3e..2f61eb6e8b 100644 --- a/lib/prefix.c +++ b/lib/prefix.c @@ -497,8 +497,7 @@ int prefix_same(const struct prefix *p1, const struct prefix *p2) if (p1->family == p2->family && p1->prefixlen == p2->prefixlen) { if (p1->family == AF_INET) - if (IPV4_ADDR_SAME(&p1->u.prefix4.s_addr, - &p2->u.prefix4.s_addr)) + if (IPV4_ADDR_SAME(&p1->u.prefix4, &p2->u.prefix4)) return 1; if (p1->family == AF_INET6) if (IPV6_ADDR_SAME(&p1->u.prefix6.s6_addr, diff --git a/lib/prefix.h b/lib/prefix.h index f0644ea88e..bc4abb492a 100644 --- a/lib/prefix.h +++ b/lib/prefix.h @@ -241,8 +241,20 @@ union prefixconstptr { #define IPV4_MAX_BITLEN 32 #define IPV4_MAX_PREFIXLEN 32 #define IPV4_ADDR_CMP(D,S) memcmp ((D), (S), IPV4_MAX_BYTELEN) -#define IPV4_ADDR_SAME(D,S) (memcmp ((D), (S), IPV4_MAX_BYTELEN) == 0) -#define IPV4_ADDR_COPY(D,S) memcpy ((D), (S), IPV4_MAX_BYTELEN) + +static inline bool ipv4_addr_same(const struct in_addr *a, + const struct in_addr *b) +{ + return (a->s_addr == b->s_addr); +} +#define IPV4_ADDR_SAME(A,B) ipv4_addr_same((A), (B)) + +static inline void ipv4_addr_copy(struct in_addr *dst, + const struct in_addr *src) +{ + dst->s_addr = src->s_addr; +} +#define IPV4_ADDR_COPY(D,S) ipv4_addr_copy((D), (S)) #define IPV4_NET0(a) ((((u_int32_t) (a)) & 0xff000000) == 0x00000000) #define IPV4_NET127(a) ((((u_int32_t) (a)) & 0xff000000) == 0x7f000000) diff --git a/lib/queue.h b/lib/queue.h index 658b602ba3..29b67a26e6 100644 --- a/lib/queue.h +++ b/lib/queue.h @@ -1,679 +1,76 @@ -/*- - * Copyright (c) 1991, 1993 - * The Regents of the University of California. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * @(#)queue.h 8.5 (Berkeley) 8/20/94 - * $FreeBSD$ - */ - -#ifndef _SYS_QUEUE_H_ -#define _SYS_QUEUE_H_ - /* - * This file defines four types of data structures: singly-linked lists, - * singly-linked tail queues, lists and tail queues. + * lists and queues implementations * - * A singly-linked list is headed by a single forward pointer. The elements - * are singly linked for minimum space and pointer manipulation overhead at - * the expense of O(n) removal for arbitrary elements. New elements can be - * added to the list after an existing element or at the head of the list. - * Elements being removed from the head of the list should use the explicit - * macro for this purpose for optimum efficiency. A singly-linked list may - * only be traversed in the forward direction. Singly-linked lists are ideal - * for applications with large datasets and few or no removals or for - * implementing a LIFO queue. + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. * - * A singly-linked tail queue is headed by a pair of pointers, one to the - * head of the list and the other to the tail of the list. The elements are - * singly linked for minimum space and pointer manipulation overhead at the - * expense of O(n) removal for arbitrary elements. New elements can be added - * to the list after an existing element, at the head of the list, or at the - * end of the list. Elements being removed from the head of the tail queue - * should use the explicit macro for this purpose for optimum efficiency. - * A singly-linked tail queue may only be traversed in the forward direction. - * Singly-linked tail queues are ideal for applications with large datasets - * and few or no removals or for implementing a FIFO queue. + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. * - * A list is headed by a single forward pointer (or an array of forward - * pointers for a hash table header). The elements are doubly linked - * so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before - * or after an existing element or at the head of the list. A list - * may only be traversed in the forward direction. - * - * A tail queue is headed by a pair of pointers, one to the head of the - * list and the other to the tail of the list. The elements are doubly - * linked so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before or - * after an existing element, at the head of the list, or at the end of - * the list. A tail queue may be traversed in either direction. - * - * For details on the use of these macros, see the queue(3) manual page. - * - * - * SLIST LIST STAILQ TAILQ - * _HEAD + + + + - * _HEAD_INITIALIZER + + + + - * _ENTRY + + + + - * _INIT + + + + - * _EMPTY + + + + - * _FIRST + + + + - * _NEXT + + + + - * _PREV - - - + - * _LAST - - + + - * _FOREACH + + + + - * _FOREACH_SAFE + + + + - * _FOREACH_REVERSE - - - + - * _FOREACH_REVERSE_SAFE - - - + - * _INSERT_HEAD + + + + - * _INSERT_BEFORE - + - + - * _INSERT_AFTER + + + + - * _INSERT_TAIL - - + + - * _CONCAT - - + + - * _REMOVE_AFTER + - + - - * _REMOVE_HEAD + - + - - * _REMOVE + + + + - * _SWAP + + + + - * - */ -#ifdef QUEUE_MACRO_DEBUG -/* Store the last 2 places the queue element or head was altered */ -struct qm_trace { - char *lastfile; - int lastline; - char *prevfile; - int prevline; -}; - -#define TRACEBUF struct qm_trace trace; -#define TRASHIT(x) do {(x) = (void *)-1;} while (0) -#define QMD_SAVELINK(name, link) void **name = (void *)&(link) - -#define QMD_TRACE_HEAD(head) \ - do { \ - (head)->trace.prevline = (head)->trace.lastline; \ - (head)->trace.prevfile = (head)->trace.lastfile; \ - (head)->trace.lastline = __LINE__; \ - (head)->trace.lastfile = __FILE__; \ - } while (0) - -#define QMD_TRACE_ELEM(elem) \ - do { \ - (elem)->trace.prevline = (elem)->trace.lastline; \ - (elem)->trace.prevfile = (elem)->trace.lastfile; \ - (elem)->trace.lastline = __LINE__; \ - (elem)->trace.lastfile = __FILE__; \ - } while (0) - -#else -#define QMD_TRACE_ELEM(elem) -#define QMD_TRACE_HEAD(head) -#define QMD_SAVELINK(name, link) -#define TRACEBUF -#define TRASHIT(x) -#endif /* QUEUE_MACRO_DEBUG */ - -/* - * Singly-linked List declarations. - */ -#define SLIST_HEAD(name, type) \ - struct name { \ - struct type *slh_first; /* first element */ \ - } - -#define SLIST_HEAD_INITIALIZER(head) \ - { \ - NULL \ - } - -#define SLIST_ENTRY(type) \ - struct { \ - struct type *sle_next; /* next element */ \ - } - -/* - * Singly-linked List functions. + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ -#define SLIST_EMPTY(head) ((head)->slh_first == NULL) - -#define SLIST_FIRST(head) ((head)->slh_first) - -#define SLIST_FOREACH(var, head, field) \ - for ((var) = SLIST_FIRST((head)); (var); \ - (var) = SLIST_NEXT((var), field)) - -#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = SLIST_FIRST((head)); \ - (var) && ((tvar) = SLIST_NEXT((var), field), 1); (var) = (tvar)) - -#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ - for ((varp) = &SLIST_FIRST((head)); ((var) = *(varp)) != NULL; \ - (varp) = &SLIST_NEXT((var), field)) - -#define SLIST_INIT(head) \ - do { \ - SLIST_FIRST((head)) = NULL; \ - } while (0) - -#define SLIST_INSERT_AFTER(slistelm, elm, field) \ - do { \ - SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ - SLIST_NEXT((slistelm), field) = (elm); \ - } while (0) - -#define SLIST_INSERT_HEAD(head, elm, field) \ - do { \ - SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ - SLIST_FIRST((head)) = (elm); \ - } while (0) - -#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) - -#define SLIST_REMOVE(head, elm, type, field) \ - do { \ - QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ - if (SLIST_FIRST((head)) == (elm)) { \ - SLIST_REMOVE_HEAD((head), field); \ - } else { \ - struct type *curelm = SLIST_FIRST((head)); \ - while (SLIST_NEXT(curelm, field) != (elm)) \ - curelm = SLIST_NEXT(curelm, field); \ - SLIST_REMOVE_AFTER(curelm, field); \ - } \ - TRASHIT(*oldnext); \ - } while (0) - -#define SLIST_REMOVE_AFTER(elm, field) \ - do { \ - SLIST_NEXT(elm, field) = \ - SLIST_NEXT(SLIST_NEXT(elm, field), field); \ - } while (0) - -#define SLIST_REMOVE_HEAD(head, field) \ - do { \ - SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ - } while (0) - -#define SLIST_SWAP(head1, head2, type) \ - do { \ - struct type *swap_first = SLIST_FIRST(head1); \ - SLIST_FIRST(head1) = SLIST_FIRST(head2); \ - SLIST_FIRST(head2) = swap_first; \ - } while (0) - -/* - * Singly-linked Tail queue declarations. - */ -#define STAILQ_HEAD(name, type) \ - struct name { \ - struct type *stqh_first; /* first element */ \ - struct type **stqh_last; /* addr of last next element */ \ - } - -#define STAILQ_HEAD_INITIALIZER(head) \ - { \ - NULL, &(head).stqh_first \ - } - -#define STAILQ_ENTRY(type) \ - struct { \ - struct type *stqe_next; /* next element */ \ - } - -/* - * Singly-linked Tail queue functions. - */ -#define STAILQ_CONCAT(head1, head2) \ - do { \ - if (!STAILQ_EMPTY((head2))) { \ - *(head1)->stqh_last = (head2)->stqh_first; \ - (head1)->stqh_last = (head2)->stqh_last; \ - STAILQ_INIT((head2)); \ - } \ - } while (0) - -#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) - -#define STAILQ_FIRST(head) ((head)->stqh_first) - -#define STAILQ_FOREACH(var, head, field) \ - for ((var) = STAILQ_FIRST((head)); (var); \ - (var) = STAILQ_NEXT((var), field)) - - -#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = STAILQ_FIRST((head)); \ - (var) && ((tvar) = STAILQ_NEXT((var), field), 1); (var) = (tvar)) - -#define STAILQ_INIT(head) \ - do { \ - STAILQ_FIRST((head)) = NULL; \ - (head)->stqh_last = &STAILQ_FIRST((head)); \ - } while (0) - -#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) \ - do { \ - if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) \ - == NULL) \ - (head)->stqh_last = &STAILQ_NEXT((elm), field); \ - STAILQ_NEXT((tqelm), field) = (elm); \ - } while (0) - -#define STAILQ_INSERT_HEAD(head, elm, field) \ - do { \ - if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) \ - == NULL) \ - (head)->stqh_last = &STAILQ_NEXT((elm), field); \ - STAILQ_FIRST((head)) = (elm); \ - } while (0) - -#define STAILQ_INSERT_TAIL(head, elm, field) \ - do { \ - STAILQ_NEXT((elm), field) = NULL; \ - *(head)->stqh_last = (elm); \ - (head)->stqh_last = &STAILQ_NEXT((elm), field); \ - } while (0) +#ifndef _FRR_QUEUE_H +#define _FRR_QUEUE_H + +#if defined(__OpenBSD__) && !defined(STAILQ_HEAD) +#include "openbsd-queue.h" + +/* Try to map FreeBSD implementation to OpenBSD one. */ +#define STAILQ_HEAD(name, type) SIMPLEQ_HEAD(name, type) +#define STAILQ_HEAD_INITIALIZER(head) SIMPLEQ_HEAD_INITIALIZER(head) +#define STAILQ_ENTRY(entry) SIMPLEQ_ENTRY(entry) + +#define STAILQ_CONCAT(head1, head2) SIMPLEQ_CONCAT(head1, head2) +#define STAILQ_EMPTY(head) SIMPLEQ_EMPTY(head) +#define STAILQ_FIRST(head) SIMPLEQ_FIRST(head) +#define STAILQ_FOREACH(var, head, field) SIMPLEQ_FOREACH(var, head, field) +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) +#define STAILQ_INIT(head) SIMPLEQ_INIT(head) +#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) SIMPLEQ_INSERT_AFTER(head, tqelm, elm, field) +#define STAILQ_INSERT_HEAD(head, elm, field) SIMPLEQ_INSERT_HEAD(head, elm, field) +#define STAILQ_INSERT_TAIL(head, elm, field) SIMPLEQ_INSERT_TAIL(head, elm, field) #define STAILQ_LAST(head, type, field) \ - (STAILQ_EMPTY((head)) \ + (SIMPLEQ_EMPTY((head)) \ ? NULL \ - : ((struct type *)(void *)((char *)((head)->stqh_last) \ - - __offsetof(struct type, \ + : ((struct type *)(void *)((char *)((head)->sqh_last) \ + - offsetof(struct type, \ field)))) - -#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) - +#define STAILQ_NEXT(elm, field) SIMPLEQ_NEXT(elm, field) #define STAILQ_REMOVE(head, elm, type, field) \ do { \ - QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ - if (STAILQ_FIRST((head)) == (elm)) { \ - STAILQ_REMOVE_HEAD((head), field); \ + if (SIMPLEQ_FIRST((head)) == (elm)) { \ + SIMPLEQ_REMOVE_HEAD((head), field); \ } else { \ - struct type *curelm = STAILQ_FIRST((head)); \ - while (STAILQ_NEXT(curelm, field) != (elm)) \ - curelm = STAILQ_NEXT(curelm, field); \ - STAILQ_REMOVE_AFTER(head, curelm, field); \ + struct type *curelm = SIMPLEQ_FIRST((head)); \ + while (SIMPLEQ_NEXT(curelm, field) != (elm)) \ + curelm = SIMPLEQ_NEXT(curelm, field); \ + SIMPLEQ_REMOVE_AFTER(head, curelm, field); \ } \ - TRASHIT(*oldnext); \ - } while (0) - -#define STAILQ_REMOVE_AFTER(head, elm, field) \ - do { \ - if ((STAILQ_NEXT(elm, field) = \ - STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) \ - == NULL) \ - (head)->stqh_last = &STAILQ_NEXT((elm), field); \ } while (0) - -#define STAILQ_REMOVE_HEAD(head, field) \ - do { \ - if ((STAILQ_FIRST((head)) = \ - STAILQ_NEXT(STAILQ_FIRST((head)), field)) \ - == NULL) \ - (head)->stqh_last = &STAILQ_FIRST((head)); \ - } while (0) - +#define STAILQ_REMOVE_AFTER(head, elm, field) SIMPLEQ_REMOVE_AFTER(head, elm, field) +#define STAILQ_REMOVE_HEAD(head, field) SIMPLEQ_REMOVE_HEAD(head, field) #define STAILQ_SWAP(head1, head2, type) \ do { \ struct type *swap_first = STAILQ_FIRST(head1); \ - struct type **swap_last = (head1)->stqh_last; \ + struct type **swap_last = (head1)->sqh_last; \ STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ - (head1)->stqh_last = (head2)->stqh_last; \ + (head1)->sqh_last = (head2)->sqh_last; \ STAILQ_FIRST(head2) = swap_first; \ - (head2)->stqh_last = swap_last; \ + (head2)->sqh_last = swap_last; \ if (STAILQ_EMPTY(head1)) \ - (head1)->stqh_last = &STAILQ_FIRST(head1); \ + (head1)->sqh_last = &STAILQ_FIRST(head1); \ if (STAILQ_EMPTY(head2)) \ - (head2)->stqh_last = &STAILQ_FIRST(head2); \ - } while (0) - - -/* - * List declarations. - */ -#define LIST_HEAD(name, type) \ - struct name { \ - struct type *lh_first; /* first element */ \ - } - -#define LIST_HEAD_INITIALIZER(head) \ - { \ - NULL \ - } - -#define LIST_ENTRY(type) \ - struct { \ - struct type *le_next; /* next element */ \ - struct type **le_prev; /* address of previous next element */ \ - } - -/* - * List functions. - */ - -#if (defined(_KERNEL) && defined(INVARIANTS)) -#define QMD_LIST_CHECK_HEAD(head, field) \ - do { \ - if (LIST_FIRST((head)) != NULL \ - && LIST_FIRST((head))->field.le_prev \ - != &LIST_FIRST((head))) \ - panic("Bad list head %p first->prev != head", (head)); \ - } while (0) - -#define QMD_LIST_CHECK_NEXT(elm, field) \ - do { \ - if (LIST_NEXT((elm), field) != NULL \ - && LIST_NEXT((elm), field)->field.le_prev \ - != &((elm)->field.le_next)) \ - panic("Bad link elm %p next->prev != elm", (elm)); \ - } while (0) - -#define QMD_LIST_CHECK_PREV(elm, field) \ - do { \ - if (*(elm)->field.le_prev != (elm)) \ - panic("Bad link elm %p prev->next != elm", (elm)); \ + (head2)->sqh_last = &STAILQ_FIRST(head2); \ } while (0) #else -#define QMD_LIST_CHECK_HEAD(head, field) -#define QMD_LIST_CHECK_NEXT(elm, field) -#define QMD_LIST_CHECK_PREV(elm, field) -#endif /* (_KERNEL && INVARIANTS) */ - -#define LIST_EMPTY(head) ((head)->lh_first == NULL) - -#define LIST_FIRST(head) ((head)->lh_first) - -#define LIST_FOREACH(var, head, field) \ - for ((var) = LIST_FIRST((head)); (var); (var) = LIST_NEXT((var), field)) - -#define LIST_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = LIST_FIRST((head)); \ - (var) && ((tvar) = LIST_NEXT((var), field), 1); (var) = (tvar)) - -#define LIST_INIT(head) \ - do { \ - LIST_FIRST((head)) = NULL; \ - } while (0) - -#define LIST_INSERT_AFTER(listelm, elm, field) \ - do { \ - QMD_LIST_CHECK_NEXT(listelm, field); \ - if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) \ - != NULL) \ - LIST_NEXT((listelm), field)->field.le_prev = \ - &LIST_NEXT((elm), field); \ - LIST_NEXT((listelm), field) = (elm); \ - (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ - } while (0) - -#define LIST_INSERT_BEFORE(listelm, elm, field) \ - do { \ - QMD_LIST_CHECK_PREV(listelm, field); \ - (elm)->field.le_prev = (listelm)->field.le_prev; \ - LIST_NEXT((elm), field) = (listelm); \ - *(listelm)->field.le_prev = (elm); \ - (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ - } while (0) - -#define LIST_INSERT_HEAD(head, elm, field) \ - do { \ - QMD_LIST_CHECK_HEAD((head), field); \ - if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ - LIST_FIRST((head))->field.le_prev = \ - &LIST_NEXT((elm), field); \ - LIST_FIRST((head)) = (elm); \ - (elm)->field.le_prev = &LIST_FIRST((head)); \ - } while (0) - -#define LIST_NEXT(elm, field) ((elm)->field.le_next) - -#define LIST_REMOVE(elm, field) \ - do { \ - QMD_SAVELINK(oldnext, (elm)->field.le_next); \ - QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ - QMD_LIST_CHECK_NEXT(elm, field); \ - QMD_LIST_CHECK_PREV(elm, field); \ - if (LIST_NEXT((elm), field) != NULL) \ - LIST_NEXT((elm), field)->field.le_prev = \ - (elm)->field.le_prev; \ - *(elm)->field.le_prev = LIST_NEXT((elm), field); \ - TRASHIT(*oldnext); \ - TRASHIT(*oldprev); \ - } while (0) - -#define LIST_SWAP(head1, head2, type, field) \ - do { \ - struct type *swap_tmp = LIST_FIRST((head1)); \ - LIST_FIRST((head1)) = LIST_FIRST((head2)); \ - LIST_FIRST((head2)) = swap_tmp; \ - if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ - swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ - if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ - swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ - } while (0) - -/* - * Tail queue declarations. - */ -#define TAILQ_HEAD(name, type) \ - struct name { \ - struct type *tqh_first; /* first element */ \ - struct type **tqh_last; /* addr of last next element */ \ - TRACEBUF \ - } - -#define TAILQ_HEAD_INITIALIZER(head) \ - { \ - NULL, &(head).tqh_first \ - } - -#define TAILQ_ENTRY(type) \ - struct { \ - struct type *tqe_next; /* next element */ \ - struct type **tqe_prev; /* address of previous next element */ \ - TRACEBUF \ - } - -/* - * Tail queue functions. - */ -#if (defined(_KERNEL) && defined(INVARIANTS)) -#define QMD_TAILQ_CHECK_HEAD(head, field) \ - do { \ - if (!TAILQ_EMPTY(head) \ - && TAILQ_FIRST((head))->field.tqe_prev \ - != &TAILQ_FIRST((head))) \ - panic("Bad tailq head %p first->prev != head", \ - (head)); \ - } while (0) - -#define QMD_TAILQ_CHECK_TAIL(head, field) \ - do { \ - if (*(head)->tqh_last != NULL) \ - panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ - } while (0) - -#define QMD_TAILQ_CHECK_NEXT(elm, field) \ - do { \ - if (TAILQ_NEXT((elm), field) != NULL \ - && TAILQ_NEXT((elm), field)->field.tqe_prev \ - != &((elm)->field.tqe_next)) \ - panic("Bad link elm %p next->prev != elm", (elm)); \ - } while (0) - -#define QMD_TAILQ_CHECK_PREV(elm, field) \ - do { \ - if (*(elm)->field.tqe_prev != (elm)) \ - panic("Bad link elm %p prev->next != elm", (elm)); \ - } while (0) -#else -#define QMD_TAILQ_CHECK_HEAD(head, field) -#define QMD_TAILQ_CHECK_TAIL(head, headname) -#define QMD_TAILQ_CHECK_NEXT(elm, field) -#define QMD_TAILQ_CHECK_PREV(elm, field) -#endif /* (_KERNEL && INVARIANTS) */ - -#define TAILQ_CONCAT(head1, head2, field) \ - do { \ - if (!TAILQ_EMPTY(head2)) { \ - *(head1)->tqh_last = (head2)->tqh_first; \ - (head2)->tqh_first->field.tqe_prev = \ - (head1)->tqh_last; \ - (head1)->tqh_last = (head2)->tqh_last; \ - TAILQ_INIT((head2)); \ - QMD_TRACE_HEAD(head1); \ - QMD_TRACE_HEAD(head2); \ - } \ - } while (0) - -#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) - -#define TAILQ_FIRST(head) ((head)->tqh_first) - -#define TAILQ_FOREACH(var, head, field) \ - for ((var) = TAILQ_FIRST((head)); (var); \ - (var) = TAILQ_NEXT((var), field)) - -#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = TAILQ_FIRST((head)); \ - (var) && ((tvar) = TAILQ_NEXT((var), field), 1); (var) = (tvar)) - -#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ - for ((var) = TAILQ_LAST((head), headname); (var); \ - (var) = TAILQ_PREV((var), headname, field)) - -#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ - for ((var) = TAILQ_LAST((head), headname); \ - (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ - (var) = (tvar)) - -#define TAILQ_INIT(head) \ - do { \ - TAILQ_FIRST((head)) = NULL; \ - (head)->tqh_last = &TAILQ_FIRST((head)); \ - QMD_TRACE_HEAD(head); \ - } while (0) - -#define TAILQ_INSERT_AFTER(head, listelm, elm, field) \ - do { \ - QMD_TAILQ_CHECK_NEXT(listelm, field); \ - if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) \ - != NULL) \ - TAILQ_NEXT((elm), field)->field.tqe_prev = \ - &TAILQ_NEXT((elm), field); \ - else { \ - (head)->tqh_last = &TAILQ_NEXT((elm), field); \ - QMD_TRACE_HEAD(head); \ - } \ - TAILQ_NEXT((listelm), field) = (elm); \ - (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ - QMD_TRACE_ELEM(&(elm)->field); \ - QMD_TRACE_ELEM(&listelm->field); \ - } while (0) - -#define TAILQ_INSERT_BEFORE(listelm, elm, field) \ - do { \ - QMD_TAILQ_CHECK_PREV(listelm, field); \ - (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ - TAILQ_NEXT((elm), field) = (listelm); \ - *(listelm)->field.tqe_prev = (elm); \ - (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ - QMD_TRACE_ELEM(&(elm)->field); \ - QMD_TRACE_ELEM(&listelm->field); \ - } while (0) - -#define TAILQ_INSERT_HEAD(head, elm, field) \ - do { \ - QMD_TAILQ_CHECK_HEAD(head, field); \ - if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ - TAILQ_FIRST((head))->field.tqe_prev = \ - &TAILQ_NEXT((elm), field); \ - else \ - (head)->tqh_last = &TAILQ_NEXT((elm), field); \ - TAILQ_FIRST((head)) = (elm); \ - (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ - QMD_TRACE_HEAD(head); \ - QMD_TRACE_ELEM(&(elm)->field); \ - } while (0) - -#define TAILQ_INSERT_TAIL(head, elm, field) \ - do { \ - QMD_TAILQ_CHECK_TAIL(head, field); \ - TAILQ_NEXT((elm), field) = NULL; \ - (elm)->field.tqe_prev = (head)->tqh_last; \ - *(head)->tqh_last = (elm); \ - (head)->tqh_last = &TAILQ_NEXT((elm), field); \ - QMD_TRACE_HEAD(head); \ - QMD_TRACE_ELEM(&(elm)->field); \ - } while (0) - -#define TAILQ_LAST(head, headname) \ - (*(((struct headname *)((head)->tqh_last))->tqh_last)) - -#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) - -#define TAILQ_PREV(elm, headname, field) \ - (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) - -#define TAILQ_REMOVE(head, elm, field) \ - do { \ - QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ - QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ - QMD_TAILQ_CHECK_NEXT(elm, field); \ - QMD_TAILQ_CHECK_PREV(elm, field); \ - if ((TAILQ_NEXT((elm), field)) != NULL) \ - TAILQ_NEXT((elm), field)->field.tqe_prev = \ - (elm)->field.tqe_prev; \ - else { \ - (head)->tqh_last = (elm)->field.tqe_prev; \ - QMD_TRACE_HEAD(head); \ - } \ - *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ - TRASHIT(*oldnext); \ - TRASHIT(*oldprev); \ - QMD_TRACE_ELEM(&(elm)->field); \ - } while (0) - -#define TAILQ_SWAP(head1, head2, type, field) \ - do { \ - struct type *swap_first = (head1)->tqh_first; \ - struct type **swap_last = (head1)->tqh_last; \ - (head1)->tqh_first = (head2)->tqh_first; \ - (head1)->tqh_last = (head2)->tqh_last; \ - (head2)->tqh_first = swap_first; \ - (head2)->tqh_last = swap_last; \ - if ((swap_first = (head1)->tqh_first) != NULL) \ - swap_first->field.tqe_prev = &(head1)->tqh_first; \ - else \ - (head1)->tqh_last = &(head1)->tqh_first; \ - if ((swap_first = (head2)->tqh_first) != NULL) \ - swap_first->field.tqe_prev = &(head2)->tqh_first; \ - else \ - (head2)->tqh_last = &(head2)->tqh_first; \ - } while (0) +#include "freebsd-queue.h" +#endif /* defined(__OpenBSD__) && !defined(STAILQ_HEAD) */ -#endif /* !_SYS_QUEUE_H_ */ +#endif /* _FRR_QUEUE_H */ diff --git a/lib/subdir.am b/lib/subdir.am index 6a62cbb678..8545184228 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -90,6 +90,7 @@ pkginclude_HEADERS += \ lib/event_counter.h \ lib/fifo.h \ lib/filter.h \ + lib/freebsd-queue.h \ lib/frr_pthread.h \ lib/frratomic.h \ lib/getopt.h \ @@ -125,6 +126,7 @@ pkginclude_HEADERS += \ lib/ptm_lib.h \ lib/pw.h \ lib/qobj.h \ + lib/queue.h \ lib/routemap.h \ lib/sbuf.h \ lib/sha256.h \ @@ -222,7 +224,6 @@ EXTRA_DIST += \ lib/command_lex.h \ lib/command_parse.h \ lib/gitversion.pl \ - lib/queue.h \ lib/route_types.pl \ lib/route_types.txt \ # end diff --git a/lib/table.c b/lib/table.c index 833adb9a37..67cf6aeec3 100644 --- a/lib/table.c +++ b/lib/table.c @@ -31,7 +31,6 @@ DEFINE_MTYPE(LIB, ROUTE_TABLE, "Route table") DEFINE_MTYPE(LIB, ROUTE_NODE, "Route node") -static void route_node_delete(struct route_node *); static void route_table_free(struct route_table *); static int route_table_hash_cmp(const void *a, const void *b) @@ -187,23 +186,6 @@ static void set_link(struct route_node *node, struct route_node *new) new->parent = node; } -/* Lock node. */ -struct route_node *route_lock_node(struct route_node *node) -{ - node->lock++; - return node; -} - -/* Unlock node. */ -void route_unlock_node(struct route_node *node) -{ - assert(node->lock > 0); - node->lock--; - - if (node->lock == 0) - route_node_delete(node); -} - /* Find matched prefix. */ struct route_node *route_node_match(const struct route_table *table, union prefixconstptr pu) @@ -348,7 +330,7 @@ struct route_node *route_node_get(struct route_table *const table, } /* Delete node from the routing table. */ -static void route_node_delete(struct route_node *node) +void route_node_delete(struct route_node *node) { struct route_node *child; struct route_node *parent; diff --git a/lib/table.h b/lib/table.h index b7b402a591..ece40d86b3 100644 --- a/lib/table.h +++ b/lib/table.h @@ -182,7 +182,6 @@ route_table_init_with_delegate(route_table_delegate_t *); extern route_table_delegate_t *route_table_get_default_delegate(void); extern void route_table_finish(struct route_table *); -extern void route_unlock_node(struct route_node *node); extern struct route_node *route_top(struct route_table *); extern struct route_node *route_next(struct route_node *); extern struct route_node *route_next_until(struct route_node *, @@ -193,7 +192,6 @@ extern struct route_node *route_node_lookup(const struct route_table *, union prefixconstptr); extern struct route_node *route_node_lookup_maynull(const struct route_table *, union prefixconstptr); -extern struct route_node *route_lock_node(struct route_node *node); extern struct route_node *route_node_match(const struct route_table *, union prefixconstptr); extern struct route_node *route_node_match_ipv4(const struct route_table *, @@ -205,6 +203,7 @@ extern unsigned long route_table_count(const struct route_table *); extern struct route_node *route_node_create(route_table_delegate_t *, struct route_table *); +extern void route_node_delete(struct route_node *); extern void route_node_destroy(route_table_delegate_t *, struct route_table *, struct route_node *); @@ -225,6 +224,23 @@ extern void route_table_iter_cleanup(route_table_iter_t *iter); * Inline functions. */ +/* Lock node. */ +static inline struct route_node *route_lock_node(struct route_node *node) +{ + node->lock++; + return node; +} + +/* Unlock node. */ +static inline void route_unlock_node(struct route_node *node) +{ + assert(node->lock > 0); + node->lock--; + + if (node->lock == 0) + route_node_delete(node); +} + /* * route_table_iter_next * diff --git a/lib/workqueue.c b/lib/workqueue.c index 612421c80b..b76b73b367 100644 --- a/lib/workqueue.c +++ b/lib/workqueue.c @@ -72,14 +72,7 @@ struct work_queue *work_queue_new(struct thread_master *m, new->master = m; SET_FLAG(new->flags, WQ_UNPLUGGED); - if ((new->items = list_new()) == NULL) { - XFREE(MTYPE_WORK_QUEUE_NAME, new->name); - XFREE(MTYPE_WORK_QUEUE, new); - - return NULL; - } - - new->items->del = (void (*)(void *))work_queue_item_free; + STAILQ_INIT(&new->items); listnode_add(work_queues, new); @@ -97,8 +90,6 @@ void work_queue_free(struct work_queue *wq) if (wq->thread != NULL) thread_cancel(wq->thread); - /* list_delete frees items via callback */ - list_delete(wq->items); listnode_delete(work_queues, wq); XFREE(MTYPE_WORK_QUEUE_NAME, wq->name); @@ -114,8 +105,8 @@ bool work_queue_is_scheduled(struct work_queue *wq) static int work_queue_schedule(struct work_queue *wq, unsigned int delay) { /* if appropriate, schedule work queue thread */ - if (CHECK_FLAG(wq->flags, WQ_UNPLUGGED) && (wq->thread == NULL) - && (listcount(wq->items) > 0)) { + if (CHECK_FLAG(wq->flags, WQ_UNPLUGGED) && (wq->thread == NULL) && + !work_queue_empty(wq)) { wq->thread = NULL; thread_add_timer_msec(wq->master, work_queue_run, wq, delay, &wq->thread); @@ -139,33 +130,35 @@ void work_queue_add(struct work_queue *wq, void *data) } item->data = data; - listnode_add(wq->items, item); + work_queue_item_enqueue(wq, item); work_queue_schedule(wq, wq->spec.hold); return; } -static void work_queue_item_remove(struct work_queue *wq, struct listnode *ln) +static void work_queue_item_remove(struct work_queue *wq, + struct work_queue_item *item) { - struct work_queue_item *item = listgetdata(ln); - assert(item && item->data); /* call private data deletion callback if needed */ if (wq->spec.del_item_data) wq->spec.del_item_data(wq, item->data); - list_delete_node(wq->items, ln); + work_queue_item_dequeue(wq, item); + work_queue_item_free(item); return; } -static void work_queue_item_requeue(struct work_queue *wq, struct listnode *ln) +static void work_queue_item_requeue(struct work_queue *wq, struct work_queue_item *item) { - LISTNODE_DETACH(wq->items, ln); - LISTNODE_ATTACH(wq->items, ln); /* attach to end of list */ + work_queue_item_dequeue(wq, item); + + /* attach to end of list */ + work_queue_item_enqueue(wq, item); } DEFUN (show_work_queues, @@ -186,7 +179,7 @@ DEFUN (show_work_queues, for (ALL_LIST_ELEMENTS_RO(work_queues, node, wq)) { vty_out(vty, "%c %8d %5d %8ld %8ld %7d %6d %8ld %6u %s\n", (CHECK_FLAG(wq->flags, WQ_UNPLUGGED) ? ' ' : 'P'), - listcount(wq->items), wq->spec.hold, wq->runs, + work_queue_item_count(wq), wq->spec.hold, wq->runs, wq->yields, wq->cycles.best, wq->cycles.granularity, wq->cycles.total, (wq->runs) ? (unsigned int)(wq->cycles.total / wq->runs) @@ -233,16 +226,15 @@ void work_queue_unplug(struct work_queue *wq) int work_queue_run(struct thread *thread) { struct work_queue *wq; - struct work_queue_item *item; + struct work_queue_item *item, *titem; wq_item_status ret; unsigned int cycles = 0; - struct listnode *node, *nnode; char yielded = 0; wq = THREAD_ARG(thread); wq->thread = NULL; - assert(wq && wq->items); + assert(wq); /* calculate cycle granularity: * list iteration == 1 run @@ -266,7 +258,7 @@ int work_queue_run(struct thread *thread) if (wq->cycles.granularity == 0) wq->cycles.granularity = WORK_QUEUE_MIN_GRANULARITY; - for (ALL_LIST_ELEMENTS(wq->items, node, nnode, item)) { + STAILQ_FOREACH_SAFE(item, &wq->items, wq, titem) { assert(item && item->data); /* dont run items which are past their allowed retries */ @@ -274,7 +266,7 @@ int work_queue_run(struct thread *thread) /* run error handler, if any */ if (wq->spec.errorfunc) wq->spec.errorfunc(wq, item->data); - work_queue_item_remove(wq, node); + work_queue_item_remove(wq, item); continue; } @@ -298,7 +290,7 @@ int work_queue_run(struct thread *thread) } case WQ_REQUEUE: { item->ran--; - work_queue_item_requeue(wq, node); + work_queue_item_requeue(wq, item); /* If a single node is being used with a meta-queue * (e.g., zebra), * update the next node as we don't want to exit the @@ -309,8 +301,8 @@ int work_queue_run(struct thread *thread) * will kick in * to terminate the thread when time has exceeded. */ - if (nnode == NULL) - nnode = node; + if (titem == NULL) + titem = item; break; } case WQ_RETRY_NOW: @@ -323,7 +315,7 @@ int work_queue_run(struct thread *thread) /* fallthru */ case WQ_SUCCESS: default: { - work_queue_item_remove(wq, node); + work_queue_item_remove(wq, item); break; } } @@ -376,7 +368,7 @@ stats: #endif /* Is the queue done yet? If it is, call the completion callback. */ - if (listcount(wq->items) > 0) + if (!work_queue_empty(wq)) work_queue_schedule(wq, 0); else if (wq->spec.completion_func) wq->spec.completion_func(wq); diff --git a/lib/workqueue.h b/lib/workqueue.h index ff7f57690d..df35d44fbc 100644 --- a/lib/workqueue.h +++ b/lib/workqueue.h @@ -24,6 +24,7 @@ #define _QUAGGA_WORK_QUEUE_H #include "memory.h" +#include "queue.h" DECLARE_MTYPE(WORK_QUEUE) /* Hold time for the initial schedule of a queue run, in millisec */ @@ -43,6 +44,7 @@ typedef enum { /* A single work queue item, unsurprisingly */ struct work_queue_item { + STAILQ_ENTRY(work_queue_item) wq; void *data; /* opaque data */ unsigned short ran; /* # of times item has been run */ }; @@ -91,7 +93,8 @@ struct work_queue { } spec; /* remaining fields should be opaque to users */ - struct list *items; /* queue item list */ + STAILQ_HEAD(work_queue_items, work_queue_item) items; /* queue item list */ + int item_count; /* queued items */ unsigned long runs; /* runs count */ unsigned long yields; /* yields count */ @@ -107,6 +110,37 @@ struct work_queue { /* User API */ +static inline int work_queue_item_count(struct work_queue *wq) +{ + return wq->item_count; +} + +static inline bool work_queue_empty(struct work_queue *wq) +{ + return (wq->item_count == 0) ? true : false; +} + +static inline struct work_queue_item *work_queue_last_item(struct work_queue *wq) +{ + return STAILQ_LAST(&wq->items, work_queue_item, wq); +} + +static inline void work_queue_item_enqueue(struct work_queue *wq, + struct work_queue_item *item) +{ + STAILQ_INSERT_TAIL(&wq->items, item, wq); + wq->item_count++; +} + +static inline void work_queue_item_dequeue(struct work_queue *wq, + struct work_queue_item *item) +{ + assert(wq->item_count > 0); + + wq->item_count--; + STAILQ_REMOVE(&wq->items, item, work_queue_item, wq); +} + /* create a new work queue, of given name. * user must fill in the spec of the returned work queue before adding * anything to it diff --git a/ospfd/ospf_packet.c b/ospfd/ospf_packet.c index ac2406ec2d..36f9a6757a 100644 --- a/ospfd/ospf_packet.c +++ b/ospfd/ospf_packet.c @@ -3938,7 +3938,7 @@ void ospf_ls_upd_send(struct ospf_neighbor *nbr, struct list *update, int flag) if (flag == OSPF_SEND_PACKET_INDIRECT) zlog_warn( "* LS-Update is directly sent on NBMA network."); - if (IPV4_ADDR_SAME(&oi->address->u.prefix4, &p.prefix.s_addr)) + if (IPV4_ADDR_SAME(&oi->address->u.prefix4, &p.prefix)) zlog_warn("* LS-Update is sent to myself."); } diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c index ed53554265..dc61ea5e40 100644 --- a/zebra/zebra_rib.c +++ b/zebra/zebra_rib.c @@ -1820,7 +1820,7 @@ void rib_queue_add(struct route_node *rn) * holder, if necessary, then push the work into it in any case. * This semantics was introduced after 0.99.9 release. */ - if (!zebrad.ribq->items->count) + if (work_queue_empty(zebrad.ribq)) work_queue_add(zebrad.ribq, zebrad.mq); rib_meta_queue_add(zebrad.mq, rn); @@ -2352,7 +2352,7 @@ void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type, break; } for (ALL_NEXTHOPS(re->nexthop, nexthop)) - if (IPV4_ADDR_SAME(&nexthop->gate.ipv4, gate) + if (IPV4_ADDR_SAME(&nexthop->gate.ipv4, &gate->ipv4) || IPV6_ADDR_SAME(&nexthop->gate.ipv6, gate)) { same = re; diff --git a/zebra/zebra_static.c b/zebra/zebra_static.c index dba228ea35..6815916faf 100644 --- a/zebra/zebra_static.c +++ b/zebra/zebra_static.c @@ -398,7 +398,7 @@ int static_add_route(afi_t afi, safi_t safi, u_char type, struct prefix *p, for (si = rn->info; si; si = si->next) { if (type == si->type && (!gate || ((afi == AFI_IP - && IPV4_ADDR_SAME(gate, &si->addr.ipv4)) + && IPV4_ADDR_SAME(&gate->ipv4, &si->addr.ipv4)) || (afi == AFI_IP6 && IPV6_ADDR_SAME(gate, &si->addr.ipv6)))) && (!strcmp (ifname ? ifname : "", si->ifname))) { @@ -515,7 +515,7 @@ int static_delete_route(afi_t afi, safi_t safi, u_char type, struct prefix *p, for (si = rn->info; si; si = si->next) if (type == si->type && (!gate || ((afi == AFI_IP - && IPV4_ADDR_SAME(gate, &si->addr.ipv4)) + && IPV4_ADDR_SAME(&gate->ipv4, &si->addr.ipv4)) || (afi == AFI_IP6 && IPV6_ADDR_SAME(gate, &si->addr.ipv6)))) && (!strcmp(ifname ? ifname : "", si->ifname)) |