Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.sbin/ldpd Use rbtree for storing peers FEC label bindings
details: https://anonhg.NetBSD.org/src/rev/a804725583a0
branches: trunk
changeset: 788990:a804725583a0
user: kefren <kefren%NetBSD.org@localhost>
date: Fri Aug 02 07:29:56 2013 +0000
description:
Use rbtree for storing peers FEC label bindings
diffstat:
usr.sbin/ldpd/ldp_command.c | 6 +-
usr.sbin/ldpd/ldp_peer.c | 81 ++++++++++++++++++++++++++++++-----------
usr.sbin/ldpd/ldp_peer.h | 11 +++--
usr.sbin/ldpd/mpls_interface.c | 10 ++++-
4 files changed, 76 insertions(+), 32 deletions(-)
diffs (263 lines):
diff -r b51bd77e1696 -r a804725583a0 usr.sbin/ldpd/ldp_command.c
--- a/usr.sbin/ldpd/ldp_command.c Fri Aug 02 03:52:50 2013 +0000
+++ b/usr.sbin/ldpd/ldp_command.c Fri Aug 02 07:29:56 2013 +0000
@@ -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 @@
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)
diff -r b51bd77e1696 -r a804725583a0 usr.sbin/ldpd/ldp_peer.c
--- a/usr.sbin/ldpd/ldp_peer.c Fri Aug 02 03:52:50 2013 +0000
+++ b/usr.sbin/ldpd/ldp_peer.c Fri Aug 02 07:29:56 2013 +0000
@@ -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 @@
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 @@
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 @@
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 @@
{
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;
+ assert(a->sa_len <= sizeof(union sockunion));
- SLIST_FOREACH(rv, &p->label_mapping_head, mappings)
- if (rv->prefix == prefix && sockaddr_cmp(a, &rv->address.sa)==0)
- break;
+ memset(&rv, 0, sizeof(rv));
+ memcpy(&rv.address.sa, a, a->sa_len);
+ rv.prefix = prefix;
- return rv;
-
+ return rb_tree_find_node(&p->label_mapping_tree, &rv);
}
void
@@ -495,9 +523,8 @@
{
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 @@
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)
{
diff -r b51bd77e1696 -r a804725583a0 usr.sbin/ldpd/ldp_peer.h
--- a/usr.sbin/ldpd/ldp_peer.h Fri Aug 02 03:52:50 2013 +0000
+++ b/usr.sbin/ldpd/ldp_peer.h Fri Aug 02 07:29:56 2013 +0000
@@ -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 @@
union sockunion address;
uint prefix;
uint label;
- SLIST_ENTRY(label_mapping) mappings;
+ rb_node_t mappings_node;
};
struct ldp_peer {
@@ -69,7 +70,7 @@
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 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);
diff -r b51bd77e1696 -r a804725583a0 usr.sbin/ldpd/mpls_interface.c
--- a/usr.sbin/ldpd/mpls_interface.c Fri Aug 02 03:52:50 2013 +0000
+++ b/usr.sbin/ldpd/mpls_interface.c Fri Aug 02 07:29:56 2013 +0000
@@ -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 @@
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 @@
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) {
Home |
Main Index |
Thread Index |
Old Index