Module Name: src
Committed By: kefren
Date: Wed Jul 31 06:58:23 UTC 2013
Modified Files:
src/usr.sbin/ldpd: label.c label.h ldp_command.c main.c mpls_routes.c
tlv_stack.c
Log Message:
Store local bindings in a rbtree
To generate a diff of this commit:
cvs rdiff -u -r1.10 -r1.11 src/usr.sbin/ldpd/label.c
cvs rdiff -u -r1.7 -r1.8 src/usr.sbin/ldpd/label.h
cvs rdiff -u -r1.12 -r1.13 src/usr.sbin/ldpd/ldp_command.c \
src/usr.sbin/ldpd/tlv_stack.c
cvs rdiff -u -r1.8 -r1.9 src/usr.sbin/ldpd/main.c
cvs rdiff -u -r1.21 -r1.22 src/usr.sbin/ldpd/mpls_routes.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.sbin/ldpd/label.c
diff -u src/usr.sbin/ldpd/label.c:1.10 src/usr.sbin/ldpd/label.c:1.11
--- src/usr.sbin/ldpd/label.c:1.10 Wed Jul 24 09:05:53 2013
+++ src/usr.sbin/ldpd/label.c Wed Jul 31 06:58:23 2013
@@ -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 @@ label_add(const union sockunion * so_des
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 @@ label_del(struct label * l)
{
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 @@ label_reattach_route(struct label *l, in
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 @@ label_reattach_all_peer_labels(const str
{
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 @@ del_all_peer_labels(const struct ldp_pee
{
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 @@ label_del_by_binding(uint32_t binding, i
{
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 @@ get_free_local_label()
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 @@ label_check_assoc(struct ldp_peer *p)
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);
+}
Index: src/usr.sbin/ldpd/label.h
diff -u src/usr.sbin/ldpd/label.h:1.7 src/usr.sbin/ldpd/label.h:1.8
--- src/usr.sbin/ldpd/label.h:1.7 Wed Jul 24 09:05:53 2013
+++ src/usr.sbin/ldpd/label.h Wed Jul 31 06:58:23 2013
@@ -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 @@ struct label {
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 @@ uint32_t get_free_local_label(void);
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_ */
Index: src/usr.sbin/ldpd/ldp_command.c
diff -u src/usr.sbin/ldpd/ldp_command.c:1.12 src/usr.sbin/ldpd/ldp_command.c:1.13
--- src/usr.sbin/ldpd/ldp_command.c:1.12 Thu Jul 18 06:07:45 2013
+++ src/usr.sbin/ldpd/ldp_command.c Wed Jul 31 06:58:23 2013
@@ -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 @@ show_labels(int s, char *recvspace)
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);
Index: src/usr.sbin/ldpd/tlv_stack.c
diff -u src/usr.sbin/ldpd/tlv_stack.c:1.12 src/usr.sbin/ldpd/tlv_stack.c:1.13
--- src/usr.sbin/ldpd/tlv_stack.c:1.12 Sat Jul 20 05:16:08 2013
+++ src/usr.sbin/ldpd/tlv_stack.c Wed Jul 31 06:58:23 2013
@@ -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 @@ withdraw_label(struct ldp_peer * p, stru
* 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 @@ send_label_tlv_to_all(const struct socka
void
send_all_bindings(const struct ldp_peer * peer)
{
- struct label *l;
+ struct label *l = NULL;
- SLIST_FOREACH(l, &label_head, labels)
+ while((l = label_get_right(l)) != NULL)
send_label_tlv(peer, &l->so_dest.sa,
from_union_to_cidr(&l->so_pref), l->binding, NULL);
Index: src/usr.sbin/ldpd/main.c
diff -u src/usr.sbin/ldpd/main.c:1.8 src/usr.sbin/ldpd/main.c:1.9
--- src/usr.sbin/ldpd/main.c:1.8 Thu Jul 25 08:40:30 2013
+++ src/usr.sbin/ldpd/main.c Wed Jul 31 06:58:23 2013
@@ -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>
Index: src/usr.sbin/ldpd/mpls_routes.c
diff -u src/usr.sbin/ldpd/mpls_routes.c:1.21 src/usr.sbin/ldpd/mpls_routes.c:1.22
--- src/usr.sbin/ldpd/mpls_routes.c:1.21 Sat Jul 27 14:35:41 2013
+++ src/usr.sbin/ldpd/mpls_routes.c Wed Jul 31 06:58:23 2013
@@ -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 @@ bind_current_routes()
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) &&
