]>
git.ipfire.org Git - thirdparty/bird.git/blob - nest/rt-attr.c
2 * BIRD -- Route Attribute Cache
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
12 #include "nest/bird.h"
13 #include "nest/route.h"
14 #include "nest/protocol.h"
15 #include "nest/iface.h"
17 #include "lib/resource.h"
19 static slab
*rta_slab
;
20 static pool
*rta_pool
;
27 ea__find(ea_list
*e
, unsigned id
)
34 if (e
->flags
& EALF_BISECT
)
51 for(m
=0; m
<e
->count
; m
++)
52 if (e
->attrs
[m
].id
== id
)
60 ea_find(ea_list
*e
, unsigned id
)
62 eattr
*a
= ea__find(e
, id
& EA_CODE_MASK
);
64 if (a
&& (a
->type
& EAF_TYPE_MASK
) == EAF_TYPE_UNDEF
&&
65 !(id
& EA_ALLOW_UNDEF
))
71 ea_do_sort(ea_list
*e
)
73 unsigned n
= e
->count
;
75 eattr
*b
= alloca(n
* sizeof(eattr
));
78 /* We need to use a stable sorting algorithm, hence mergesort */
84 eattr
*p
, *q
, *lo
, *hi
;
88 while (s
< n
&& p
[-1].id
<= a
[s
].id
)
94 while (s
< n
&& p
[-1].id
<= a
[s
].id
)
99 while (lo
< q
&& hi
< p
)
100 if (lo
->id
<= hi
->id
)
115 ea_do_prune(ea_list
*e
)
120 /* Discard duplicates and undefs. Do you remember sorting was stable? */
122 l
= e
->attrs
+ e
->count
;
125 if ((s
->type
& EAF_TYPE_MASK
) != EAF_TYPE_UNDEF
)
131 while (s
< l
&& s
->id
== s
[-1].id
)
142 if (!(e
->flags
& EALF_SORTED
))
146 e
->flags
|= EALF_SORTED
;
149 e
->flags
|= EALF_BISECT
;
164 return sizeof(ea_list
) + sizeof(eattr
)*cnt
;
168 ea_merge(ea_list
*e
, ea_list
*t
)
177 memcpy(d
, e
->attrs
, sizeof(eattr
)*e
->count
);
178 t
->count
+= e
->count
;
185 ea_same(ea_list
*x
, ea_list
*y
)
191 ASSERT(!x
->next
&& !y
->next
);
192 if (x
->count
!= y
->count
)
194 for(c
=0; c
<x
->count
; c
++)
196 eattr
*a
= &x
->attrs
[c
];
197 eattr
*b
= &y
->attrs
[c
];
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
))))
209 static inline ea_list
*
210 ea_list_copy(ea_list
*o
)
218 len
= sizeof(ea_list
) + sizeof(eattr
) * o
->count
;
219 n
= mb_alloc(rta_pool
, len
);
221 n
->flags
|= EALF_CACHED
;
222 for(i
=0; i
<o
->count
; i
++)
224 eattr
*a
= &n
->attrs
[i
];
225 if (!(a
->flags
& EAF_EMBEDDED
))
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
);
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
++)
254 eattr
*a
= &e
->attrs
[i
];
255 debug(" %02x:%02x.%02x", EA_PROTO(a
->id
), EA_ID(a
->id
), a
->flags
);
256 if (a
->type
& EAF_TEMP
)
258 debug("=%c", "?iO?I?P???S?????" [a
->type
& EAF_TYPE_MASK
]);
259 if (a
->type
& EAF_EMBEDDED
)
260 debug(":%08x", a
->u
.data
);
263 int j
, len
= a
->u
.ptr
->length
;
266 debug("%02x", a
->u
.ptr
->data
[j
]);
274 static inline unsigned int
280 if (e
) /* Assuming chain of length 1 */
282 for(i
=0; i
<e
->count
; i
++)
284 struct eattr
*a
= &e
->attrs
[i
];
286 if (a
->type
& EAF_EMBEDDED
)
290 struct adata
*d
= a
->u
.ptr
;
291 int size
= d
->length
;
300 h
= (h
>> 24) ^ (h
<< 8) ^ *z
++;
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
;
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;
328 rta_cache_limit
= ~0;
329 rta_cache_mask
= rta_cache_size
- 1;
332 static inline unsigned int
335 return a
->proto
->hash_key
^ ipa_hash(a
->gw
) ^ ea_hash(a
->eattrs
);
339 rta_same(rta
*x
, rta
*y
)
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
&&
346 x
->flags
== y
->flags
&&
347 ipa_equal(x
->gw
, y
->gw
) &&
348 ipa_equal(x
->from
, y
->from
) &&
349 x
->iface
== y
->iface
&&
350 ea_same(x
->eattrs
, y
->eattrs
));
356 rta
*r
= sl_alloc(rta_slab
);
358 memcpy(r
, o
, sizeof(rta
));
360 r
->eattrs
= ea_list_copy(o
->eattrs
);
367 unsigned int h
= r
->hash_key
& rta_cache_mask
;
368 r
->next
= rta_hash_table
[h
];
370 r
->next
->pprev
= &r
->next
;
371 r
->pprev
= &rta_hash_table
[h
];
372 rta_hash_table
[h
] = r
;
378 unsigned int ohs
= rta_cache_size
;
381 rta
**oht
= rta_hash_table
;
383 rta_cache_size
= 2*rta_cache_size
;
384 DBG("Rehashing rta cache from %d to %d entries.\n", ohs
, rta_cache_size
);
387 for(r
=oht
[h
]; r
; r
=n
)
401 ASSERT(!(o
->aflags
& RTAF_CACHED
));
404 if (o
->eattrs
->next
) /* Multiple ea_list's, need to merge them */
406 ea_list
*ml
= alloca(ea_scan(o
->eattrs
));
407 ea_merge(o
->eattrs
, ml
);
414 for(r
=rta_hash_table
[h
& rta_cache_mask
]; r
; r
=r
->next
)
415 if (r
->hash_key
== h
&& rta_same(r
, o
))
420 r
->aflags
= RTAF_CACHED
;
423 if (++rta_cache_count
> rta_cache_limit
)
432 ASSERT(rta_cache_count
&& (a
->aflags
& RTAF_CACHED
));
439 static char *rts
[] = { "RTS_DUMMY", "RTS_STATIC", "RTS_INHERIT", "RTS_DEVICE",
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" };
443 static char *rtc
[] = { "", " BC", " MC", " AC" };
444 static char *rtd
[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
446 debug("p=%s uc=%d %s %s%s%s h=%04x",
447 a
->proto
->name
, a
->uc
, rts
[a
->source
], ip_scope_text(a
->scope
), rtc
[a
->cast
],
448 rtd
[a
->dest
], a
->hash_key
);
449 if (!(a
->aflags
& RTAF_CACHED
))
451 debug(" <-%I", a
->from
);
452 if (a
->dest
== RTD_ROUTER
)
453 debug(" ->%I", a
->gw
);
454 if (a
->dest
== RTD_DEVICE
|| a
->dest
== RTD_ROUTER
)
455 debug(" [%s]", a
->iface
? a
->iface
->name
: "???" );
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
)
481 rta_show(struct cli
*c
, rta
*a
)
483 static char *src_names
[] = { "dummy", "static", "inherit", "device", "static-device", "redirect",
484 "RIP", "RIP-ext", "OSPF", "OSPF-ext", "OSPF-IA", "OSPF-boundary",
486 static char *cast_names
[] = { "unicast", "broadcast", "multicast", "anycast" };
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... */
495 rta_pool
= rp_new(&root_pool
, "Attributes");
496 rta_slab
= sl_new(rta_pool
, sizeof(rta
));