]>
Commit | Line | Data |
---|---|---|
2326b001 MM |
1 | /* |
2 | * BIRD -- Route Attribute Cache | |
3 | * | |
b77ae37d | 4 | * (c) 1998--1999 Martin Mares <mj@ucw.cz> |
2326b001 MM |
5 | * |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
9 | #include <string.h> | |
b77ae37d | 10 | #include <alloca.h> |
2326b001 MM |
11 | |
12 | #include "nest/bird.h" | |
13 | #include "nest/route.h" | |
14 | #include "nest/protocol.h" | |
66e53309 | 15 | #include "nest/iface.h" |
730f2e2c | 16 | #include "nest/cli.h" |
2326b001 MM |
17 | #include "lib/resource.h" |
18 | ||
19 | /* | |
20 | * FIXME: Implement hash tables and garbage collection! | |
21 | */ | |
22 | ||
23 | static rta *first_rta; | |
24 | static slab *rta_slab; | |
25 | static pool *rta_pool; | |
26 | ||
b77ae37d MM |
27 | /* |
28 | * Extended Attributes | |
29 | */ | |
30 | ||
8d24b689 MM |
31 | static inline eattr * |
32 | ea__find(ea_list *e, unsigned id) | |
b77ae37d MM |
33 | { |
34 | eattr *a; | |
35 | int l, r, m; | |
36 | ||
37 | while (e) | |
38 | { | |
39 | if (e->flags & EALF_BISECT) | |
40 | { | |
41 | l = 0; | |
42 | r = e->count + 1; | |
43 | while (l <= r) | |
44 | { | |
45 | m = (l+r) / 2; | |
46 | a = &e->attrs[m]; | |
47 | if (a->id == id) | |
48 | return a; | |
49 | else if (a->id < id) | |
50 | l = m+1; | |
51 | else | |
52 | r = m-1; | |
53 | } | |
54 | } | |
55 | else | |
56 | for(m=0; m<e->count; m++) | |
57 | if (e->attrs[m].id == id) | |
58 | return &e->attrs[m]; | |
59 | e = e->next; | |
60 | } | |
61 | return NULL; | |
62 | } | |
63 | ||
8d24b689 MM |
64 | eattr * |
65 | ea_find(ea_list *e, unsigned id) | |
66 | { | |
67 | eattr *a = ea__find(e, id & EA_CODE_MASK); | |
68 | ||
69 | if (a && (a->type & EAF_TYPE_MASK) == EAF_TYPE_UNDEF && | |
70 | !(id & EA_ALLOW_UNDEF)) | |
71 | return NULL; | |
72 | return a; | |
73 | } | |
74 | ||
b77ae37d MM |
75 | static inline void |
76 | ea_do_sort(ea_list *e) | |
77 | { | |
78 | unsigned n = e->count; | |
79 | eattr *a = e->attrs; | |
80 | eattr *b = alloca(n * sizeof(eattr)); | |
81 | unsigned s, ss; | |
82 | ||
83 | /* We need to use a stable sorting algorithm, hence mergesort */ | |
84 | do | |
85 | { | |
86 | s = ss = 0; | |
87 | while (s < n) | |
88 | { | |
89 | eattr *p, *q, *lo, *hi; | |
90 | p = b; | |
91 | ss = s; | |
92 | *p++ = a[s++]; | |
93 | while (s < n && p[-1].id <= a[s].id) | |
94 | *p++ = a[s++]; | |
95 | if (s < n) | |
96 | { | |
97 | q = p; | |
98 | *p++ = a[s++]; | |
99 | while (s < n && p[-1].id <= a[s].id) | |
100 | *p++ = a[s++]; | |
101 | lo = b; | |
102 | hi = q; | |
103 | s = ss; | |
104 | while (lo < q && hi < p) | |
105 | if (lo->id <= hi->id) | |
106 | a[s++] = *lo++; | |
107 | else | |
108 | a[s++] = *hi++; | |
109 | while (lo < q) | |
110 | a[s++] = *lo++; | |
111 | while (hi < p) | |
112 | a[s++] = *hi++; | |
113 | } | |
114 | } | |
115 | } | |
116 | while (ss); | |
117 | } | |
118 | ||
119 | static inline void | |
120 | ea_do_prune(ea_list *e) | |
121 | { | |
8d24b689 MM |
122 | eattr *s, *d, *l; |
123 | int i = 0; | |
124 | ||
125 | /* Discard duplicates and undefs. Do you remember sorting was stable? */ | |
126 | s = d = e->attrs; | |
127 | l = e->attrs + e->count; | |
128 | while (s < l) | |
129 | { | |
130 | if ((s->type & EAF_TYPE_MASK) != EAF_TYPE_UNDEF) | |
131 | { | |
132 | *d++ = *s; | |
133 | i++; | |
134 | } | |
b77ae37d | 135 | s++; |
8d24b689 MM |
136 | while (s < l && s->id == s[-1].id) |
137 | s++; | |
138 | } | |
139 | e->count = i; | |
b77ae37d MM |
140 | } |
141 | ||
142 | void | |
143 | ea_sort(ea_list *e) | |
144 | { | |
145 | while (e) | |
146 | { | |
147 | if (!(e->flags & EALF_SORTED)) | |
148 | { | |
149 | ea_do_sort(e); | |
150 | ea_do_prune(e); | |
151 | e->flags |= EALF_SORTED; | |
152 | } | |
153 | #if 0 /* FIXME: Remove this after some testing */ | |
154 | if (e->count > 5) | |
155 | #endif | |
156 | e->flags |= EALF_BISECT; | |
157 | e = e->next; | |
158 | } | |
159 | } | |
160 | ||
161 | unsigned | |
162 | ea_scan(ea_list *e) | |
163 | { | |
164 | unsigned cnt = 0; | |
165 | ||
166 | while (e) | |
167 | { | |
168 | cnt += e->count; | |
169 | e = e->next; | |
170 | } | |
171 | return sizeof(ea_list) + sizeof(eattr)*cnt; | |
172 | } | |
173 | ||
174 | void | |
175 | ea_merge(ea_list *e, ea_list *t) | |
176 | { | |
177 | eattr *d = t->attrs; | |
178 | ||
179 | t->flags = 0; | |
180 | t->count = 0; | |
181 | t->next = NULL; | |
182 | while (e) | |
183 | { | |
184 | memcpy(d, e->attrs, sizeof(eattr)*e->count); | |
185 | t->count += e->count; | |
186 | d += e->count; | |
187 | e = e->next; | |
188 | } | |
189 | } | |
190 | ||
2326b001 MM |
191 | static inline int |
192 | ea_same(ea_list *x, ea_list *y) | |
193 | { | |
194 | int c; | |
195 | ||
b77ae37d MM |
196 | if (!x || !y) |
197 | return x == y; | |
198 | ASSERT(!x->next && !y->next); | |
199 | if (x->count != y->count) | |
200 | return 0; | |
201 | for(c=0; c<x->count; c++) | |
2326b001 | 202 | { |
b77ae37d MM |
203 | eattr *a = &x->attrs[c]; |
204 | eattr *b = &y->attrs[c]; | |
205 | ||
206 | if (a->id != b->id || | |
207 | a->flags != b->flags || | |
208 | a->type != b->type || | |
209 | ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data : | |
210 | (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr, b->u.ptr, a->u.ptr->length)))) | |
2326b001 | 211 | return 0; |
b77ae37d MM |
212 | } |
213 | return 1; | |
214 | } | |
215 | ||
216 | static inline ea_list * | |
217 | ea_list_copy(ea_list *o) | |
218 | { | |
219 | ea_list *n; | |
220 | unsigned i, len; | |
221 | ||
222 | if (!o) | |
223 | return NULL; | |
224 | ASSERT(!o->next); | |
225 | len = sizeof(ea_list) + sizeof(eattr) * o->count; | |
226 | n = mb_alloc(rta_pool, len); | |
227 | memcpy(n, o, len); | |
228 | n->flags |= EALF_CACHED; | |
229 | for(i=0; i<o->count; i++) | |
230 | { | |
231 | eattr *a = &n->attrs[i]; | |
232 | if (!(a->flags & EAF_EMBEDDED)) | |
233 | { | |
234 | unsigned size = sizeof(struct adata) + a->u.ptr->length; | |
235 | struct adata *d = mb_alloc(rta_pool, size); | |
236 | memcpy(d, a->u.ptr, size); | |
237 | a->u.ptr = d; | |
238 | } | |
239 | } | |
240 | return n; | |
241 | } | |
242 | ||
243 | void | |
244 | ea_dump(ea_list *e) | |
245 | { | |
246 | int i; | |
247 | ||
248 | if (!e) | |
249 | { | |
250 | debug("NONE"); | |
251 | return; | |
252 | } | |
253 | while (e) | |
254 | { | |
255 | debug("[%c%c%c]", | |
256 | (e->flags & EALF_SORTED) ? 'S' : 's', | |
257 | (e->flags & EALF_BISECT) ? 'B' : 'b', | |
258 | (e->flags & EALF_CACHED) ? 'C' : 'c'); | |
259 | for(i=0; i<e->count; i++) | |
2326b001 | 260 | { |
b77ae37d MM |
261 | eattr *a = &e->attrs[i]; |
262 | debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags); | |
263 | if (a->type & EAF_INLINE) | |
264 | debug("*"); | |
265 | debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]); | |
266 | if (a->type & EAF_EMBEDDED) | |
267 | debug(":%08x", a->u.data); | |
268 | else | |
269 | { | |
270 | int j, len = a->u.ptr->length; | |
271 | debug("[%d]:", len); | |
272 | for(j=0; j<len; j++) | |
273 | debug("%02x", a->u.ptr->data[j]); | |
274 | } | |
2326b001 | 275 | } |
b77ae37d MM |
276 | if (e = e->next) |
277 | debug(" | "); | |
2326b001 | 278 | } |
2326b001 MM |
279 | } |
280 | ||
b77ae37d MM |
281 | /* |
282 | * rta's | |
283 | */ | |
284 | ||
2326b001 MM |
285 | static inline int |
286 | rta_same(rta *x, rta *y) | |
287 | { | |
288 | return (x->proto == y->proto && | |
289 | x->source == y->source && | |
290 | x->scope == y->scope && | |
291 | x->cast == y->cast && | |
292 | x->dest == y->dest && | |
2326b001 MM |
293 | x->flags == y->flags && |
294 | ipa_equal(x->gw, y->gw) && | |
295 | ipa_equal(x->from, y->from) && | |
296 | x->iface == y->iface && | |
2727bb7c | 297 | ea_same(x->eattrs, y->eattrs)); |
2326b001 MM |
298 | } |
299 | ||
300 | static rta * | |
301 | rta_copy(rta *o) | |
302 | { | |
303 | rta *r = sl_alloc(rta_slab); | |
304 | ||
305 | memcpy(r, o, sizeof(rta)); | |
306 | r->uc = 1; | |
2727bb7c | 307 | r->eattrs = ea_list_copy(o->eattrs); |
2326b001 MM |
308 | return r; |
309 | } | |
310 | ||
311 | rta * | |
312 | rta_lookup(rta *o) | |
313 | { | |
314 | rta *r; | |
315 | ||
b77ae37d | 316 | ASSERT(!(o->aflags & RTAF_CACHED)); |
2727bb7c | 317 | if (o->eattrs) |
b77ae37d | 318 | { |
2727bb7c | 319 | if (o->eattrs->next) /* Multiple ea_list's, need to merge them */ |
b77ae37d | 320 | { |
2727bb7c MM |
321 | ea_list *ml = alloca(ea_scan(o->eattrs)); |
322 | ea_merge(o->eattrs, ml); | |
323 | o->eattrs = ml; | |
b77ae37d | 324 | } |
2727bb7c | 325 | ea_sort(o->eattrs); |
b77ae37d MM |
326 | } |
327 | ||
2326b001 MM |
328 | for(r=first_rta; r; r=r->next) |
329 | if (rta_same(r, o)) | |
330 | return rta_clone(r); | |
b77ae37d | 331 | |
2326b001 | 332 | r = rta_copy(o); |
04925e90 | 333 | r->aflags = RTAF_CACHED; |
2326b001 MM |
334 | r->next = first_rta; |
335 | first_rta = r; | |
336 | return r; | |
337 | } | |
338 | ||
339 | void | |
b77ae37d | 340 | rta__free(rta *a) |
2326b001 MM |
341 | { |
342 | } | |
343 | ||
344 | void | |
66e53309 | 345 | rta_dump(rta *a) |
2326b001 | 346 | { |
618533af | 347 | static char *rts[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE", |
66e53309 MM |
348 | "RTS_STAT_DEV", "RTS_REDIR", "RTS_RIP", "RTS_RIP_EXT", |
349 | "RTS_OSPF", "RTS_OSPF_EXT", "RTS_OSPF_IA", | |
350 | "RTS_OSPF_BOUNDARY", "RTS_BGP" }; | |
66e53309 MM |
351 | static char *rtc[] = { "", " BC", " MC", " AC" }; |
352 | static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" }; | |
353 | ||
08e2d625 | 354 | debug("p=%s uc=%d %s %s%s%s", |
730f2e2c | 355 | a->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast], |
08e2d625 | 356 | rtd[a->dest]); |
66e53309 MM |
357 | if (a->flags & RTF_EXTERIOR) |
358 | debug(" EXT"); | |
359 | if (a->flags & RTF_TAGGED) | |
360 | debug(" TAG"); | |
04925e90 MM |
361 | if (!(a->aflags & RTAF_CACHED)) |
362 | debug(" !CACHED"); | |
962ba482 | 363 | debug(" <-%I", a->from); |
66e53309 | 364 | if (a->dest == RTD_ROUTER) |
962ba482 | 365 | debug(" ->%I", a->gw); |
66e53309 | 366 | if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER) |
48b41d58 | 367 | debug(" [%s]", a->iface ? a->iface->name : "???" ); |
2727bb7c | 368 | if (a->eattrs) |
b77ae37d MM |
369 | { |
370 | debug(" EA: "); | |
2727bb7c | 371 | ea_dump(a->eattrs); |
b77ae37d | 372 | } |
2326b001 MM |
373 | } |
374 | ||
375 | void | |
376 | rta_dump_all(void) | |
377 | { | |
66e53309 MM |
378 | rta *a; |
379 | ||
380 | debug("Route attribute cache:\n"); | |
381 | for(a=first_rta; a; a=a->next) | |
382 | { | |
383 | debug("%p ", a); | |
384 | rta_dump(a); | |
385 | debug("\n"); | |
386 | } | |
387 | debug("\n"); | |
2326b001 MM |
388 | } |
389 | ||
730f2e2c MM |
390 | void |
391 | rta_show(struct cli *c, rta *a) | |
392 | { | |
393 | static char *src_names[] = { "dummy", "static", "inherit", "device", "static-device", "redirect", | |
394 | "RIP", "RIP-ext", "OSPF", "OSPF-ext", "OSPF-IA", "OSPF-boundary", | |
395 | "BGP" }; | |
396 | static char *cast_names[] = { "unicast", "broadcast", "multicast", "anycast" }; | |
397 | ||
398 | cli_printf(c, -1008, "\tType: %s %s %s", src_names[a->source], cast_names[a->cast], ip_scope_text(a->scope)); | |
399 | /* FIXME: Here we probably should print the dynamic attributes... */ | |
400 | } | |
401 | ||
2326b001 MM |
402 | void |
403 | rta_init(void) | |
404 | { | |
ed68a5c6 | 405 | rta_pool = rp_new(&root_pool, "Attributes"); |
2326b001 MM |
406 | rta_slab = sl_new(rta_pool, sizeof(rta)); |
407 | } |