[src/trunk]: src/usr.sbin/ldpd Store local bindings in a rbtree

[kefren <kefren%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/fe3bd6890cb1
branches:  trunk
changeset: 788957:fe3bd6890cb1
user:      kefren <kefren%NetBSD.org@localhost>
date:      Wed Jul 31 06:58:23 2013 +0000

description:
Store local bindings in a rbtree

diffstat:

 usr.sbin/ldpd/label.c       |  88 ++++++++++++++++++++++++++++++++++----------
 usr.sbin/ldpd/label.h       |   8 ++--
 usr.sbin/ldpd/ldp_command.c |   6 +-
 usr.sbin/ldpd/main.c        |   3 +-
 usr.sbin/ldpd/mpls_routes.c |   4 +-
 usr.sbin/ldpd/tlv_stack.c   |   8 ++--
 6 files changed, 82 insertions(+), 35 deletions(-)

diffs (truncated from 306 to 300 lines):

diff -r db5d0af4e878 -r fe3bd6890cb1 usr.sbin/ldpd/label.c
--- a/usr.sbin/ldpd/label.c     Tue Jul 30 22:23:45 2013 +0000
+++ b/usr.sbin/ldpd/label.c     Wed Jul 31 06:58:23 2013 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: label.c,v 1.10 2013/07/24 09:05:53 kefren Exp $ */
+/* $NetBSD: label.c,v 1.11 2013/07/31 06:58:23 kefren Exp $ */
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -32,6 +32,7 @@
 #include <netmpls/mpls.h>
 
 #include <assert.h>
+#include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -41,12 +42,45 @@
 #include "label.h"
 #include "ldp_errors.h"
 
-int    min_label = MIN_LABEL, max_label = MAX_LABEL;
+static int labels_compare(void*, const void*, const void*);
+
+int min_label = MIN_LABEL, max_label = MAX_LABEL;
+
+static rb_tree_t labels_tree;
+static const rb_tree_ops_t tree_ops = {
+       .rbto_compare_nodes = labels_compare,
+       .rbto_compare_key = labels_compare,
+       .rbto_node_offset = offsetof(struct label, lbtree),
+       .rbto_context = NULL
+};
 
 void 
 label_init()
 {
-       SLIST_INIT(&label_head);
+
+       rb_tree_init(&labels_tree, &tree_ops);
+}
+
+static int
+labels_compare(void *context, const void *node1, const void *node2)
+{
+       const struct label *l1 = node1, *l2 = node2;
+       int ret;
+
+       if (__predict_false(l1->so_dest.sa.sa_family !=
+           l2->so_dest.sa.sa_family))
+               return l1->so_dest.sa.sa_family > l2->so_dest.sa.sa_family ?
+                   1 : -1;
+
+       assert(l1->so_dest.sa.sa_len == l2->so_dest.sa.sa_len);
+       assert(l1->so_pref.sa.sa_len == l2->so_pref.sa.sa_len);
+
+       if ((ret = memcmp(&l1->so_dest.sa, &l2->so_dest.sa,
+           l1->so_dest.sa.sa_len)) != 0)
+               return ret;
+       else
+               return memcmp(&l1->so_pref.sa, &l2->so_pref.sa,
+                   l1->so_pref.sa.sa_len);
 }
 
 /*
@@ -85,7 +119,8 @@
        l->label = label;
        l->host = host;
 
-       SLIST_INSERT_HEAD(&label_head, l, labels);
+       if (rb_tree_insert_node(&labels_tree, l) != l)
+               fatalp("label already in tree");
 
        strlcpy(spreftmp, satos(&so_pref->sa), INET_ADDRSTRLEN);
        warnp("[label_add] added binding %d for %s/%s\n", l->binding,
@@ -102,7 +137,7 @@
 {
        warnp("[label_del] deleted binding %d for %s\n", l->binding,
           satos(&l->so_dest.sa));
-       SLIST_REMOVE(&label_head, l, label, labels);
+       rb_tree_remove_node(&labels_tree, l);
        free(l);
 }
 
@@ -148,15 +183,13 @@
 struct label*
 label_get(const union sockunion *sodest, const union sockunion *sopref)
 {
-       struct label *l;
+       struct label l;
 
-       SLIST_FOREACH (l, &label_head, labels)
-           if (sodest->sin.sin_addr.s_addr ==
-                   l->so_dest.sin.sin_addr.s_addr &&
-               sopref->sin.sin_addr.s_addr ==
-                   l->so_pref.sin.sin_addr.s_addr)
-                       return l;
-       return NULL;
+       memset(&l, 0, sizeof(l));
+       memcpy(&l.so_dest, sodest, sodest->sa.sa_len);
+       memcpy(&l.so_pref, sopref, sopref->sa.sa_len);
+
+       return rb_tree_find_node(&labels_tree, &l);
 }
 
 /*
@@ -168,7 +201,7 @@
 {
        struct label   *l;
 
-       SLIST_FOREACH(l, &label_head, labels)
+       RB_TREE_FOREACH(l, &labels_tree)
                if (l->p == p)
                        label_reattach_route(l, readd);
 }
@@ -182,12 +215,17 @@
 {
        struct label   *l, *lnext;
 
-       SLIST_FOREACH_SAFE(l, &label_head, labels, lnext) {
+       RB_TREE_FOREACH(l, &labels_tree) {
+back_delete:
                if(l->p != p)
                        continue;
                label_reattach_route(l, readd);
+               lnext = rb_tree_iterate(&labels_tree, l, RB_DIR_RIGHT);
                label_del(l);
-               SLIST_REMOVE(&label_head, l, label, labels);
+               if (lnext == NULL)
+                       break;
+               l = lnext;
+               goto back_delete;
        }
 }
 
@@ -199,11 +237,10 @@
 {
        struct label   *l;
 
-       SLIST_FOREACH(l, &label_head, labels)
+       RB_TREE_FOREACH(l, &labels_tree)
                if ((uint32_t)l->binding == binding) {
                        label_reattach_route(l, readd);
                        label_del(l);
-                       SLIST_REMOVE(&label_head, l, label, labels);
                        break;
                }
 }
@@ -238,7 +275,7 @@
        int lbl;
  
        for (lbl = min_label; lbl <= max_label; lbl++) {
-               SLIST_FOREACH(l, &label_head, labels)
+               RB_TREE_FOREACH(l, &labels_tree)
                        if (l->binding == lbl)
                                break;
                if (l == NULL)
@@ -267,13 +304,22 @@
        struct label *l;
        struct ldp_peer_address *wp;
 
-       SLIST_FOREACH (l, &label_head, labels)
+       RB_TREE_FOREACH(l, &labels_tree)
                if (l->p == NULL && l->so_gate.sa.sa_family != 0)
                        SLIST_FOREACH(wp, &p->ldp_peer_address_head, addresses)
                                if (sockaddr_cmp(&l->so_gate.sa,
-                                   &wp->address.sa) == 0){
+                                   &wp->address.sa) == 0) {
                                        l->p = p;
                                        l->label = MPLS_LABEL_IMPLNULL;
                                        break;
                                }
 }
+
+struct label *
+label_get_right(struct label *l)
+{
+       if (l == NULL)
+               return RB_TREE_MIN(&labels_tree);
+       else
+               return rb_tree_iterate(&labels_tree, l, RB_DIR_RIGHT);
+}
diff -r db5d0af4e878 -r fe3bd6890cb1 usr.sbin/ldpd/label.h
--- a/usr.sbin/ldpd/label.h     Tue Jul 30 22:23:45 2013 +0000
+++ b/usr.sbin/ldpd/label.h     Wed Jul 31 06:58:23 2013 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: label.h,v 1.7 2013/07/24 09:05:53 kefren Exp $ */
+/* $NetBSD: label.h,v 1.8 2013/07/31 06:58:23 kefren Exp $ */
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -32,7 +32,7 @@
 #ifndef _LABEL_H_
 #define _LABEL_H_
 
-#include <sys/queue.h>
+#include <sys/rbtree.h>
 
 #include "mpls_routes.h"
 #include "ldp_peer.h"
@@ -53,9 +53,8 @@
        int binding, label;
        bool host;      /* change routes using RTF_HOST */
        const struct ldp_peer *p;
-       SLIST_ENTRY(label) labels;
+       rb_node_t lbtree;
 };
-SLIST_HEAD(,label) label_head;
 
 void            label_init(void);
 struct label * label_add(const union sockunion *, const union sockunion *,
@@ -72,5 +71,6 @@
 void           announce_label_change(struct label *);
 void           label_reattach_route(struct label*, int);
 void           label_check_assoc(struct ldp_peer *p);
+struct label * label_get_right(struct label *);
 
 #endif /* !_LABEL_H_ */
diff -r db5d0af4e878 -r fe3bd6890cb1 usr.sbin/ldpd/ldp_command.c
--- a/usr.sbin/ldpd/ldp_command.c       Tue Jul 30 22:23:45 2013 +0000
+++ b/usr.sbin/ldpd/ldp_command.c       Wed Jul 31 06:58:23 2013 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: ldp_command.c,v 1.12 2013/07/18 06:07:45 kefren Exp $ */
+/* $NetBSD: ldp_command.c,v 1.13 2013/07/31 06:58:23 kefren Exp $ */
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -504,11 +504,11 @@
 int
 show_bindings(int s, char *recvspace)
 {
-       struct label *l;
+       struct label *l = NULL;
 
        snprintf(sendspace, MAXSEND, "Local label\tNetwork\t\t\t\tNexthop\n");
        writestr(s, sendspace);
-       SLIST_FOREACH (l, &label_head, labels) {
+       while((l = label_get_right(l)) != NULL) {
                snprintf(sendspace, MAXSEND, "%d\t\t%s/", l->binding,
                    satos(&l->so_dest.sa));
                writestr(s, sendspace);
diff -r db5d0af4e878 -r fe3bd6890cb1 usr.sbin/ldpd/main.c
--- a/usr.sbin/ldpd/main.c      Tue Jul 30 22:23:45 2013 +0000
+++ b/usr.sbin/ldpd/main.c      Wed Jul 31 06:58:23 2013 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: main.c,v 1.8 2013/07/25 08:40:30 kefren Exp $ */
+/* $NetBSD: main.c,v 1.9 2013/07/31 06:58:23 kefren Exp $ */
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -32,7 +32,6 @@
 #include <netinet/in.h>
 #include <sys/stat.h>
 #include <sys/socket.h>
-#include <sys/select.h>
 #include <arpa/inet.h>
 
 #include <stdio.h>
diff -r db5d0af4e878 -r fe3bd6890cb1 usr.sbin/ldpd/mpls_routes.c
--- a/usr.sbin/ldpd/mpls_routes.c       Tue Jul 30 22:23:45 2013 +0000
+++ b/usr.sbin/ldpd/mpls_routes.c       Wed Jul 31 06:58:23 2013 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: mpls_routes.c,v 1.21 2013/07/27 14:35:41 kefren Exp $ */
+/* $NetBSD: mpls_routes.c,v 1.22 2013/07/31 06:58:23 kefren Exp $ */
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -900,6 +900,8 @@
 
                so_pref->sa.sa_family = AF_INET;
                so_pref->sa.sa_len = sizeof(struct sockaddr_in);
+               so_pref->sin.sin_port = 0;
+               memset(&so_pref->sin.sin_zero, 0, 8);
 
                /* Also deletes when dest is IPv4 and gateway MPLS */
                if ((rtmes->rtm_addrs & RTA_GATEWAY) &&
diff -r db5d0af4e878 -r fe3bd6890cb1 usr.sbin/ldpd/tlv_stack.c
--- a/usr.sbin/ldpd/tlv_stack.c Tue Jul 30 22:23:45 2013 +0000
+++ b/usr.sbin/ldpd/tlv_stack.c Wed Jul 31 06:58:23 2013 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: tlv_stack.c,v 1.12 2013/07/20 05:16:08 kefren Exp $ */
+/* $NetBSD: tlv_stack.c,v 1.13 2013/07/31 06:58:23 kefren Exp $ */
 
 /*-
  * Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -201,7 +201,7 @@
                 * POP Label
                 */
                lab = label_get_by_prefix(&socktmp.sa, pref->prelen);
-               if ((lab) && (lab->p == p)) {
+               if (lab && lab->p == p) {
                        label_reattach_route(lab, REATT_INET_CHANGE);
                        announce_label_change(lab); /* binding has changed */
                }
@@ -332,9 +332,9 @@
 void 
 send_all_bindings(const struct ldp_peer * peer)
 {
-       struct label *l;
+       struct label *l = NULL;