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