Module Name: src
Committed By: kefren
Date: Fri Aug 2 07:29:56 UTC 2013
Modified Files:
src/usr.sbin/ldpd: ldp_command.c ldp_peer.c ldp_peer.h mpls_interface.c
Log Message:
Use rbtree for storing peers FEC label bindings
To generate a diff of this commit:
cvs rdiff -u -r1.13 -r1.14 src/usr.sbin/ldpd/ldp_command.c
cvs rdiff -u -r1.15 -r1.16 src/usr.sbin/ldpd/ldp_peer.c
cvs rdiff -u -r1.7 -r1.8 src/usr.sbin/ldpd/ldp_peer.h
cvs rdiff -u -r1.12 -r1.13 src/usr.sbin/ldpd/mpls_interface.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/ldp_command.c
diff -u src/usr.sbin/ldpd/ldp_command.c:1.13 src/usr.sbin/ldpd/ldp_command.c:1.14
--- src/usr.sbin/ldpd/ldp_command.c:1.13 Wed Jul 31 06:58:23 2013
+++ src/usr.sbin/ldpd/ldp_command.c Fri Aug 2 07:29:56 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: ldp_command.c,v 1.13 2013/07/31 06:58:23 kefren Exp $ */
+/* $NetBSD: ldp_command.c,v 1.14 2013/08/02 07:29:56 kefren Exp $ */
/*-
* Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -481,12 +481,12 @@ int
show_labels(int s, char *recvspace)
{
struct ldp_peer *p;
- struct label_mapping *lm;
+ struct label_mapping *lm = NULL;
SLIST_FOREACH(p, &ldp_peer_head, peers) {
if (p->state != LDP_PEER_ESTABLISHED)
continue;
- SLIST_FOREACH(lm, &p->label_mapping_head, mappings) {
+ while ((lm = ldp_peer_lm_right(p, lm)) != NULL) {
char lma[256];
/* XXX: TODO */
if (lm->address.sa.sa_family != AF_INET)
Index: src/usr.sbin/ldpd/ldp_peer.c
diff -u src/usr.sbin/ldpd/ldp_peer.c:1.15 src/usr.sbin/ldpd/ldp_peer.c:1.16
--- src/usr.sbin/ldpd/ldp_peer.c:1.15 Sat Jul 20 05:16:08 2013
+++ src/usr.sbin/ldpd/ldp_peer.c Fri Aug 2 07:29:56 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: ldp_peer.c,v 1.15 2013/07/20 05:16:08 kefren Exp $ */
+/* $NetBSD: ldp_peer.c,v 1.16 2013/08/02 07:29:56 kefren Exp $ */
/*
* Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -41,6 +41,7 @@
#include <fcntl.h>
#include <stdlib.h>
#include <strings.h>
+#include <stddef.h>
#include <stdio.h>
#include <unistd.h>
@@ -55,6 +56,17 @@
extern int ldp_holddown_time;
+static struct label_mapping *ldp_peer_get_lm(struct ldp_peer *,
+ const struct sockaddr *, uint);
+
+static int mappings_compare(void *, const void *, const void *);
+static rb_tree_ops_t mappings_tree_ops = {
+ .rbto_compare_nodes = mappings_compare,
+ .rbto_compare_key = mappings_compare,
+ .rbto_node_offset = offsetof(struct label_mapping, mappings_node),
+ .rbto_context = NULL
+};
+
void
ldp_peer_init(void)
{
@@ -69,6 +81,28 @@ sockaddr_cmp(const struct sockaddr *a, c
return -1;
return memcmp(a, b, a->sa_len);
}
+
+static int
+mappings_compare(void *context, const void *node1, const void *node2)
+{
+ const struct label_mapping *l1 = node1, *l2 = node2;
+ int ret;
+
+ if (__predict_false(l1->address.sa.sa_family !=
+ l2->address.sa.sa_family))
+ return l1->address.sa.sa_family > l2->address.sa.sa_family ?
+ 1 : -1;
+
+ assert(l1->address.sa.sa_len == l2->address.sa.sa_len);
+ if ((ret = memcmp(&l1->address.sa, &l2->address.sa, l1->address.sa.sa_len)) != 0)
+ return ret;
+
+ if (__predict_false(l1->prefix != l2->prefix))
+ return l1->prefix > l2->prefix ? 1 : -1;
+
+ return 0;
+}
+
/*
* soc should be > 1 if there is already a TCP socket for this else we'll
* initiate a new one
@@ -150,7 +184,7 @@ ldp_peer_new(const struct in_addr * ldp_
set_ttl(p->socket);
}
SLIST_INIT(&p->ldp_peer_address_head);
- SLIST_INIT(&p->label_mapping_head);
+ rb_tree_init(&p->label_mapping_tree, &mappings_tree_ops);
p->timeout = p->holdtime;
sopts = fcntl(p->socket, F_GETFL);
@@ -449,7 +483,7 @@ ldp_peer_add_mapping(struct ldp_peer * p
lma->prefix = prefix;
lma->label = label;
- SLIST_INSERT_HEAD(&p->label_mapping_head, lma, mappings);
+ rb_tree_insert_node(&p->label_mapping_tree, lma);
return LDP_E_OK;
}
@@ -460,34 +494,28 @@ ldp_peer_delete_mapping(struct ldp_peer
{
struct label_mapping *lma;
- if (!a)
+ if (a == NULL || (lma = ldp_peer_get_lm(p, a, prefix)) == NULL)
return LDP_E_NOENT;
- lma = ldp_peer_get_lm(p, a, prefix);
- if (!lma)
- return LDP_E_NOENT;
-
- SLIST_REMOVE(&p->label_mapping_head, lma, label_mapping, mappings);
+ rb_tree_remove_node(&p->label_mapping_tree, lma);
free(lma);
return LDP_E_OK;
}
-struct label_mapping *
-ldp_peer_get_lm(const struct ldp_peer * p, const struct sockaddr * a,
+static struct label_mapping *
+ldp_peer_get_lm(struct ldp_peer * p, const struct sockaddr * a,
uint prefix)
{
- struct label_mapping *rv;
+ struct label_mapping rv;
- if (!p)
- return NULL;
-
- SLIST_FOREACH(rv, &p->label_mapping_head, mappings)
- if (rv->prefix == prefix && sockaddr_cmp(a, &rv->address.sa)==0)
- break;
+ assert(a->sa_len <= sizeof(union sockunion));
- return rv;
+ memset(&rv, 0, sizeof(rv));
+ memcpy(&rv.address.sa, a, a->sa_len);
+ rv.prefix = prefix;
+ return rb_tree_find_node(&p->label_mapping_tree, &rv);
}
void
@@ -495,9 +523,8 @@ ldp_peer_delete_all_mappings(struct ldp_
{
struct label_mapping *lma;
- while(!SLIST_EMPTY(&p->label_mapping_head)) {
- lma = SLIST_FIRST(&p->label_mapping_head);
- SLIST_REMOVE_HEAD(&p->label_mapping_head, mappings);
+ while((lma = RB_TREE_MIN(&p->label_mapping_tree)) != NULL) {
+ rb_tree_remove_node(&p->label_mapping_tree, lma);
free(lma);
}
}
@@ -542,6 +569,16 @@ ldp_test_mapping(const struct sockaddr *
return rv;
}
+struct label_mapping * ldp_peer_lm_right(struct ldp_peer *p,
+ struct label_mapping * map)
+{
+ if (map == NULL)
+ return RB_TREE_MIN(&p->label_mapping_tree);
+ else
+ return rb_tree_iterate(&p->label_mapping_tree, map,
+ RB_DIR_RIGHT);
+}
+
/* Name from state */
const char * ldp_state_to_name(int state)
{
Index: src/usr.sbin/ldpd/ldp_peer.h
diff -u src/usr.sbin/ldpd/ldp_peer.h:1.7 src/usr.sbin/ldpd/ldp_peer.h:1.8
--- src/usr.sbin/ldpd/ldp_peer.h:1.7 Sat Jul 20 05:16:08 2013
+++ src/usr.sbin/ldpd/ldp_peer.h Fri Aug 2 07:29:56 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: ldp_peer.h,v 1.7 2013/07/20 05:16:08 kefren Exp $ */
+/* $NetBSD: ldp_peer.h,v 1.8 2013/08/02 07:29:56 kefren Exp $ */
/*-
* Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -33,6 +33,7 @@
#define _LDP_PEER_H_
#include "sys/types.h"
+#include "sys/rbtree.h"
#include "sys/queue.h"
#include "netinet/in.h"
@@ -48,7 +49,7 @@ struct label_mapping {
union sockunion address;
uint prefix;
uint label;
- SLIST_ENTRY(label_mapping) mappings;
+ rb_node_t mappings_node;
};
struct ldp_peer {
@@ -69,7 +70,7 @@ struct ldp_peer {
time_t established_t; /* time when it did connect */
/* Here I maintain all the addresses announced by a peer */
SLIST_HEAD(,ldp_peer_address) ldp_peer_address_head;
- SLIST_HEAD(,label_mapping) label_mapping_head;
+ rb_tree_t label_mapping_tree;
SLIST_ENTRY(ldp_peer) peers;
};
@@ -106,13 +107,13 @@ int del_ifaddresses(struct ldp_peer *, c
int ldp_peer_add_mapping(struct ldp_peer *, const struct sockaddr *, int, int);
int ldp_peer_delete_mapping(struct ldp_peer *, const struct sockaddr *, int);
-struct label_mapping * ldp_peer_get_lm(const struct ldp_peer *,
- const struct sockaddr *, uint);
void ldp_peer_delete_all_mappings(struct ldp_peer *);
void ldp_peer_holddown_all(void);
struct peer_map * ldp_test_mapping(const struct sockaddr *, int,
const struct sockaddr *);
+struct label_mapping * ldp_peer_lm_right(struct ldp_peer *,
+ struct label_mapping *);
const char * ldp_state_to_name(int);
Index: src/usr.sbin/ldpd/mpls_interface.c
diff -u src/usr.sbin/ldpd/mpls_interface.c:1.12 src/usr.sbin/ldpd/mpls_interface.c:1.13
--- src/usr.sbin/ldpd/mpls_interface.c:1.12 Wed Jul 24 09:05:53 2013
+++ src/usr.sbin/ldpd/mpls_interface.c Fri Aug 2 07:29:56 2013
@@ -1,4 +1,4 @@
-/* $NetBSD: mpls_interface.c,v 1.12 2013/07/24 09:05:53 kefren Exp $ */
+/* $NetBSD: mpls_interface.c,v 1.13 2013/08/02 07:29:56 kefren Exp $ */
/*-
* Copyright (c) 2010 The NetBSD Foundation, Inc.
@@ -59,6 +59,7 @@ mpls_add_label(struct label *lab)
union sockunion *so_dest, *so_nexthop, *so_tag, so_ifa;
uint8_t prefixlen;
uint32_t oldbinding;
+ struct peer_map *pm;
assert(lab != NULL);
@@ -74,8 +75,13 @@ mpls_add_label(struct label *lab)
return LDP_E_BAD_AF;
/* double check if there is a label mapping for this */
- if (ldp_peer_get_lm(lab->p, &lab->so_dest.sa, prefixlen) == NULL)
+ if ((pm = ldp_test_mapping(&lab->so_dest.sa, prefixlen,
+ &lab->so_gate.sa)) == NULL || pm->peer != lab->p) {
+ if (pm != NULL)
+ free(pm);
return LDP_E_NOENT;
+ }
+ free(pm);
if (lab->so_gate.sa.sa_family != AF_INET &&
lab->so_gate.sa.sa_family != AF_INET6) {
