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