1 /* $NetBSD: label.c,v 1.11 2013/07/31 06:58:23 kefren Exp $ */
2
3 /*-
4 * Copyright (c) 2010 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Mihai Chelaru <kefren@NetBSD.org>
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include <netmpls/mpls.h>
33
34 #include <assert.h>
35 #include <stddef.h>
36 #include <stdlib.h>
37 #include <string.h>
38
39 #include "ldp.h"
40 #include "tlv_stack.h"
41 #include "mpls_routes.h"
42 #include "label.h"
43 #include "ldp_errors.h"
44
45 static int labels_compare(void*, const void*, const void*);
46
47 int min_label = MIN_LABEL, max_label = MAX_LABEL;
48
49 static rb_tree_t labels_tree;
50 static const rb_tree_ops_t tree_ops = {
51 .rbto_compare_nodes = labels_compare,
52 .rbto_compare_key = labels_compare,
53 .rbto_node_offset = offsetof(struct label, lbtree),
54 .rbto_context = NULL
55 };
56
57 void
label_init()58 label_init()
59 {
60
61 rb_tree_init(&labels_tree, &tree_ops);
62 }
63
64 static int
labels_compare(void * context,const void * node1,const void * node2)65 labels_compare(void *context, const void *node1, const void *node2)
66 {
67 const struct label *l1 = node1, *l2 = node2;
68 int ret;
69
70 if (__predict_false(l1->so_dest.sa.sa_family !=
71 l2->so_dest.sa.sa_family))
72 return l1->so_dest.sa.sa_family > l2->so_dest.sa.sa_family ?
73 1 : -1;
74
75 assert(l1->so_dest.sa.sa_len == l2->so_dest.sa.sa_len);
76 assert(l1->so_pref.sa.sa_len == l2->so_pref.sa.sa_len);
77
78 if ((ret = memcmp(&l1->so_dest.sa, &l2->so_dest.sa,
79 l1->so_dest.sa.sa_len)) != 0)
80 return ret;
81 else
82 return memcmp(&l1->so_pref.sa, &l2->so_pref.sa,
83 l1->so_pref.sa.sa_len);
84 }
85
86 /*
87 * if binding == 0 it receives a free one
88 */
89 struct label *
label_add(const union sockunion * so_dest,const union sockunion * so_pref,const union sockunion * so_gate,uint32_t binding,const struct ldp_peer * p,uint32_t label,bool host)90 label_add(const union sockunion * so_dest, const union sockunion * so_pref,
91 const union sockunion * so_gate, uint32_t binding,
92 const struct ldp_peer * p, uint32_t label, bool host)
93 {
94 struct label *l;
95 char spreftmp[INET_ADDRSTRLEN];
96
97 l = calloc(1, sizeof(*l));
98
99 if (!l) {
100 fatalp("label_add: malloc problem\n");
101 return NULL;
102 }
103
104 assert(so_dest);
105 assert(so_pref);
106 assert(so_dest->sa.sa_family == so_pref->sa.sa_family);
107 assert(label_get(so_dest, so_pref) == NULL);
108
109 memcpy(&l->so_dest, so_dest, so_dest->sa.sa_len);
110 memcpy(&l->so_pref, so_pref, so_pref->sa.sa_len);
111
112 if (so_gate)
113 memcpy(&l->so_gate, so_gate, so_gate->sa.sa_len);
114 if (binding)
115 l->binding = binding;
116 else
117 l->binding = get_free_local_label();
118 l->p = p;
119 l->label = label;
120 l->host = host;
121
122 if (rb_tree_insert_node(&labels_tree, l) != l)
123 fatalp("label already in tree");
124
125 strlcpy(spreftmp, satos(&so_pref->sa), INET_ADDRSTRLEN);
126 warnp("[label_add] added binding %d for %s/%s\n", l->binding,
127 satos(&so_dest->sa), spreftmp);
128
129 send_label_tlv_to_all(&(so_dest->sa),
130 from_union_to_cidr(so_pref), l->binding);
131 return l;
132 }
133
134 /* Unlink a label */
135 void
label_del(struct label * l)136 label_del(struct label * l)
137 {
138 warnp("[label_del] deleted binding %d for %s\n", l->binding,
139 satos(&l->so_dest.sa));
140 rb_tree_remove_node(&labels_tree, l);
141 free(l);
142 }
143
144 /*
145 * Delete or Reuse the old IPv4 route, delete MPLS route
146 * readd = REATT_INET_CHANGE -> delete and recreate the INET route
147 * readd = REATT_INET_DEL -> deletes INET route
148 * readd = REATT_INET_NODEL -> doesn't touch the INET route
149 */
150 void
label_reattach_route(struct label * l,int readd)151 label_reattach_route(struct label *l, int readd)
152 {
153
154 warnp("[label_reattach_route] binding %d deleted\n",
155 l->binding);
156
157 /* No gateway ? */
158 if (l->so_gate.sa.sa_len == 0)
159 return;
160
161 if (readd == REATT_INET_CHANGE) {
162 /* Delete the tagged route and re-add IPv4 route */
163 delete_route(&l->so_dest,
164 l->host ? NULL : &l->so_pref, NO_FREESO);
165 add_route(&l->so_dest,
166 l->host ? NULL : &l->so_pref, &l->so_gate,
167 NULL, NULL, NO_FREESO, RTM_READD);
168 } else if (readd == REATT_INET_DEL)
169 delete_route(&l->so_dest, l->host ? NULL : &l->so_pref,
170 NO_FREESO);
171
172 /* Deletes the MPLS route */
173 if (l->binding >= min_label)
174 delete_route(make_mpls_union(l->binding), NULL, FREESO);
175
176 l->binding = MPLS_LABEL_IMPLNULL;
177 l->p = NULL;
178 l->label = 0;
179 }
180 /*
181 * Get a label by dst and pref
182 */
183 struct label*
label_get(const union sockunion * sodest,const union sockunion * sopref)184 label_get(const union sockunion *sodest, const union sockunion *sopref)
185 {
186 struct label l;
187
188 memset(&l, 0, sizeof(l));
189 memcpy(&l.so_dest, sodest, sodest->sa.sa_len);
190 memcpy(&l.so_pref, sopref, sopref->sa.sa_len);
191
192 return rb_tree_find_node(&labels_tree, &l);
193 }
194
195 /*
196 * Find all labels that points to a peer
197 * and reattach them to IPv4
198 */
199 void
label_reattach_all_peer_labels(const struct ldp_peer * p,int readd)200 label_reattach_all_peer_labels(const struct ldp_peer *p, int readd)
201 {
202 struct label *l;
203
204 RB_TREE_FOREACH(l, &labels_tree)
205 if (l->p == p)
206 label_reattach_route(l, readd);
207 }
208
209 /*
210 * Find all labels that points to a peer
211 * and delete them
212 */
213 void
del_all_peer_labels(const struct ldp_peer * p,int readd)214 del_all_peer_labels(const struct ldp_peer * p, int readd)
215 {
216 struct label *l, *lnext;
217
218 RB_TREE_FOREACH(l, &labels_tree) {
219 back_delete:
220 if(l->p != p)
221 continue;
222 label_reattach_route(l, readd);
223 lnext = rb_tree_iterate(&labels_tree, l, RB_DIR_RIGHT);
224 label_del(l);
225 if (lnext == NULL)
226 break;
227 l = lnext;
228 goto back_delete;
229 }
230 }
231
232 /*
233 * Finds a label by its binding and deletes it
234 */
235 void
label_del_by_binding(uint32_t binding,int readd)236 label_del_by_binding(uint32_t binding, int readd)
237 {
238 struct label *l;
239
240 RB_TREE_FOREACH(l, &labels_tree)
241 if ((uint32_t)l->binding == binding) {
242 label_reattach_route(l, readd);
243 label_del(l);
244 break;
245 }
246 }
247
248 /*
249 * For Compatibility with old bindinds code
250 */
251 struct label*
label_get_by_prefix(const struct sockaddr * a,int prefixlen)252 label_get_by_prefix(const struct sockaddr *a, int prefixlen)
253 {
254 const union sockunion *so_dest;
255 union sockunion *so_pref;
256 struct label *l;
257
258 so_dest = (const union sockunion *)a;
259 so_pref = from_cidr_to_union(prefixlen);
260
261 l = label_get(so_dest, so_pref);
262
263 free(so_pref);
264
265 return l;
266 }
267
268 /*
269 * Get a free binding
270 */
271 uint32_t
get_free_local_label()272 get_free_local_label()
273 {
274 struct label *l;
275 int lbl;
276
277 for (lbl = min_label; lbl <= max_label; lbl++) {
278 RB_TREE_FOREACH(l, &labels_tree)
279 if (l->binding == lbl)
280 break;
281 if (l == NULL)
282 return lbl;
283 }
284 return 0;
285 }
286
287 /*
288 * Announce peers that a label has changed its binding
289 * by withdrawing it and reannouncing it
290 */
291 void
announce_label_change(struct label * l)292 announce_label_change(struct label *l)
293 {
294 send_withdraw_tlv_to_all(&(l->so_dest.sa),
295 from_union_to_cidr(&(l->so_pref)));
296 send_label_tlv_to_all(&(l->so_dest.sa),
297 from_union_to_cidr(&(l->so_pref)),
298 l->binding);
299 }
300
301 void
label_check_assoc(struct ldp_peer * p)302 label_check_assoc(struct ldp_peer *p)
303 {
304 struct label *l;
305 struct ldp_peer_address *wp;
306
307 RB_TREE_FOREACH(l, &labels_tree)
308 if (l->p == NULL && l->so_gate.sa.sa_family != 0)
309 SLIST_FOREACH(wp, &p->ldp_peer_address_head, addresses)
310 if (sockaddr_cmp(&l->so_gate.sa,
311 &wp->address.sa) == 0) {
312 l->p = p;
313 l->label = MPLS_LABEL_IMPLNULL;
314 break;
315 }
316 }
317
318 struct label *
label_get_right(struct label * l)319 label_get_right(struct label *l)
320 {
321 if (l == NULL)
322 return RB_TREE_MIN(&labels_tree);
323 else
324 return rb_tree_iterate(&labels_tree, l, RB_DIR_RIGHT);
325 }
326