iofbirddaemon / nest / rtfib.c @ 08c69a77
History  View  Annotate  Download (8.27 KB)
1 
/*


2 
* BIRD  Forwarding Information Base  Data Structures

3 
*

4 
* (c) 1998 Martin Mares <mj@ucw.cz>

5 
*

6 
* Can be freely distributed and used under the terms of the GNU GPL.

7 
*/

8  
9 
#define LOCAL_DEBUG

10  
11 
#include <string.h> 
12  
13 
#include "nest/bird.h" 
14 
#include "nest/route.h" 
15  
16 
#define HASH_DEF_ORDER 10 
17 
#define HASH_HI_MARK *4 
18 
#define HASH_HI_STEP 2 
19 
#define HASH_HI_MAX 16 /* Must be at most 16 */ 
20 
#define HASH_LO_MARK /5 
21 
#define HASH_LO_STEP 2 
22 
#define HASH_LO_MIN 10 
23  
24 
static void 
25 
fib_ht_alloc(struct fib *f)

26 
{ 
27 
f>hash_size = 1 << f>hash_order;

28 
f>hash_shift = 16  f>hash_order;

29 
if (f>hash_order > HASH_HI_MAX  HASH_HI_STEP)

30 
f>entries_max = ~0;

31 
else

32 
f>entries_max = f>hash_size HASH_HI_MARK; 
33 
if (f>hash_order < HASH_LO_MIN + HASH_LO_STEP)

34 
f>entries_min = 0;

35 
else

36 
f>entries_min = f>hash_size HASH_LO_MARK; 
37 
DBG("Allocating FIB hash of order %d: %d entries, %d low, %d high\n",

38 
f>hash_order, f>hash_size, f>entries_min, f>entries_max); 
39 
f>hash_table = mb_alloc(f>fib_pool, f>hash_size * sizeof(struct fib_node *)); 
40 
} 
41  
42 
static inline void 
43 
fib_ht_free(struct fib_node **h)

44 
{ 
45 
mb_free(h); 
46 
} 
47  
48 
static inline unsigned 
49 
fib_hash(struct fib *f, ip_addr *a)

50 
{ 
51 
return ipa_hash(*a) >> f>hash_shift;

52 
} 
53  
54 
void

55 
fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, void (*init)(struct fib_node *)) 
56 
{ 
57 
if (!hash_order)

58 
hash_order = HASH_DEF_ORDER; 
59 
f>fib_pool = p; 
60 
f>fib_slab = sl_new(p, node_size); 
61 
f>hash_order = hash_order; 
62 
fib_ht_alloc(f); 
63 
bzero(f>hash_table, f>hash_size * sizeof(struct fib_node *)); 
64 
f>entries = 0;

65 
f>entries_min = 0;

66 
f>init = init; 
67 
} 
68  
69 
static void 
70 
fib_rehash(struct fib *f, int step) 
71 
{ 
72 
unsigned old, new, oldn, newn, ni, nh;

73 
struct fib_node **n, *e, *x, **t, **m, **h;

74  
75 
old = f>hash_order; 
76 
oldn = f>hash_size; 
77 
new = old + step; 
78 
m = h = f>hash_table; 
79 
DBG("Rehashing FIB from order %d to %d\n", old, new);

80 
f>hash_order = new; 
81 
fib_ht_alloc(f); 
82 
t = n = f>hash_table; 
83 
newn = f>hash_size; 
84 
ni = 0;

85  
86 
while (old)

87 
{ 
88 
x = *h++; 
89 
while (e = x)

90 
{ 
91 
x = e>next; 
92 
nh = fib_hash(f, &e>prefix); 
93 
while (nh > ni)

94 
{ 
95 
*t = NULL;

96 
ni++; 
97 
t = ++n; 
98 
} 
99 
*t = e; 
100 
t = &e>next; 
101 
} 
102 
} 
103 
while (ni < newn)

104 
{ 
105 
*t = NULL;

106 
ni++; 
107 
t = ++n; 
108 
} 
109 
fib_ht_free(m); 
110 
} 
111  
112 
void *

113 
fib_find(struct fib *f, ip_addr *a, int len) 
114 
{ 
115 
struct fib_node *e = f>hash_table[fib_hash(f, a)];

116  
117 
while (e && (e>pxlen != len  !ipa_equal(*a, e>prefix)))

118 
e = e>next; 
119 
return e;

120 
} 
121  
122 
void *

123 
fib_get(struct fib *f, ip_addr *a, int len) 
124 
{ 
125 
unsigned int h = ipa_hash(*a); 
126 
struct fib_node **ee = f>hash_table + (h >> f>hash_shift);

127 
struct fib_node *g, *e = *ee;

128  
129 
while (e && (e>pxlen != len  !ipa_equal(*a, e>prefix)))

130 
e = e>next; 
131 
if (e)

132 
return e;

133 
#ifdef DEBUGGING

134 
if (len < 0  len > BITS_PER_IP_ADDRESS  !ip_is_prefix(*a,len)) 
135 
bug("fib_get() called for invalid address");

136 
#endif

137 
e = sl_alloc(f>fib_slab); 
138 
e>prefix = *a; 
139 
e>pxlen = len; 
140 
while ((g = *ee) && ipa_hash(g>prefix) < h)

141 
ee = &g>next; 
142 
e>next = *ee; 
143 
*ee = e; 
144 
e>readers = NULL;

145 
f>init(e); 
146 
if (f>entries++ > f>entries_max)

147 
fib_rehash(f, HASH_HI_STEP); 
148 
return e;

149 
} 
150  
151 
static inline void 
152 
fib_merge_readers(struct fib_iterator *i, struct fib_node *to) 
153 
{ 
154 
if (to)

155 
{ 
156 
struct fib_iterator *j = to>readers;

157 
if (!j)

158 
{ 
159 
/* Fast path */

160 
to>readers = i; 
161 
i>prev = (struct fib_iterator *) to;

162 
fixup:

163 
while (i && i>node)

164 
{ 
165 
i>node = NULL;

166 
i = i>next; 
167 
} 
168 
return;

169 
} 
170 
/* Really merging */

171 
while (j>next)

172 
j = j>next; 
173 
j>next = i; 
174 
i>prev = j; 
175 
goto fixup;

176 
} 
177 
else /* No more nodes */ 
178 
while (i)

179 
{ 
180 
i>prev = NULL;

181 
i = i>next; 
182 
} 
183 
} 
184  
185 
void

186 
fib_delete(struct fib *f, void *E) 
187 
{ 
188 
struct fib_node *e = E;

189 
unsigned int h = fib_hash(f, &e>prefix); 
190 
struct fib_node **ee = f>hash_table + h;

191 
struct fib_iterator *it;

192  
193 
while (*ee)

194 
{ 
195 
if (*ee == e)

196 
{ 
197 
*ee = e>next; 
198 
if (it = e>readers)

199 
{ 
200 
struct fib_node *l = e>next;

201 
while (!l)

202 
{ 
203 
h++; 
204 
if (h >= f>hash_size)

205 
break;

206 
else

207 
l = f>hash_table[h]; 
208 
} 
209 
fib_merge_readers(it, l); 
210 
} 
211 
sl_free(f>fib_slab, e); 
212 
if (f>entries < f>entries_min)

213 
fib_rehash(f, HASH_LO_STEP); 
214 
return;

215 
} 
216 
ee = &((*ee)>next); 
217 
} 
218 
bug("fib_delete() called for invalid node");

219 
} 
220  
221 
void

222 
fib_free(struct fib *f)

223 
{ 
224 
fib_ht_free(f>hash_table); 
225 
rfree(f>fib_slab); 
226 
} 
227  
228 
void

229 
fit_init(struct fib_iterator *i, struct fib *f) 
230 
{ 
231 
unsigned h;

232 
struct fib_node *n;

233  
234 
i>efef = 0xff;

235 
for(h=0; h<f>hash_size; h++) 
236 
if (n = f>hash_table[h])

237 
{ 
238 
i>prev = (struct fib_iterator *) n;

239 
if (i>next = n>readers)

240 
i>next>prev = i; 
241 
n>readers = i; 
242 
i>node = n; 
243 
return;

244 
} 
245 
/* The fib is empty, nothing to do */

246 
i>prev = i>next = NULL;

247 
i>node = NULL;

248 
} 
249  
250 
struct fib_node *

251 
fit_get(struct fib *f, struct fib_iterator *i) 
252 
{ 
253 
struct fib_node *n;

254 
struct fib_iterator *j, *k;

255  
256 
if (!i>prev)

257 
{ 
258 
/* We are at the end */

259 
i>hash = f>hash_size; 
260 
return NULL; 
261 
} 
262 
if (!(n = i>node))

263 
{ 
264 
/* No node info available, we are a victim of merging. Try harder. */

265 
j = i; 
266 
while (j>efef == 0xff) 
267 
j = j>prev; 
268 
n = (struct fib_node *) j;

269 
} 
270 
j = i>prev; 
271 
if (k = i>next)

272 
k>prev = j; 
273 
j>next = k; 
274 
i>hash = fib_hash(f, &n>prefix); 
275 
return n;

276 
} 
277  
278 
void

279 
fit_put(struct fib_iterator *i, struct fib_node *n) 
280 
{ 
281 
struct fib_iterator *j;

282  
283 
i>node = n; 
284 
if (j = n>readers)

285 
j>prev = i; 
286 
i>next = j; 
287 
n>readers = i; 
288 
i>prev = (struct fib_iterator *) n;

289 
} 
290  
291 
#ifdef DEBUGGING

292  
293 
void

294 
fib_check(struct fib *f)

295 
{ 
296 
unsigned int i, ec, lo, nulls; 
297  
298 
ec = 0;

299 
for(i=0; i<f>hash_size; i++) 
300 
{ 
301 
struct fib_node *n;

302 
lo = 0;

303 
for(n=f>hash_table[i]; n; n=n>next)

304 
{ 
305 
struct fib_iterator *j, *j0;

306 
unsigned int h0 = ipa_hash(n>prefix); 
307 
if (h0 < lo)

308 
bug("fib_check: discord in hash chains");

309 
lo = h0; 
310 
if ((h0 >> f>hash_shift) != i)

311 
bug("fib_check: mishashed %x>%x (order %d)", h0, i, f>hash_order);

312 
j0 = (struct fib_iterator *) n;

313 
nulls = 0;

314 
for(j=n>readers; j; j=j>next)

315 
{ 
316 
if (j>prev != j0)

317 
bug("fib_check: iterator>prev mismatch");

318 
j0 = j; 
319 
if (!j>node)

320 
nulls++; 
321 
else if (nulls) 
322 
bug("fib_check: iterator nullified");

323 
else if (j>node != n) 
324 
bug("fib_check: iterator>node mismatch");

325 
} 
326 
ec++; 
327 
} 
328 
} 
329 
if (ec != f>entries)

330 
bug("fib_check: invalid entry count (%d != %d)", ec, f>entries);

331 
} 
332  
333 
#endif

334  
335 
#ifdef TEST

336  
337 
#include "lib/resource.h" 
338  
339 
struct fib f;

340  
341 
void dump(char *m) 
342 
{ 
343 
unsigned int i; 
344  
345 
debug("%s ... order=%d, size=%d, entries=%d\n", m, f.hash_order, f.hash_size, f.hash_size);

346 
for(i=0; i<f.hash_size; i++) 
347 
{ 
348 
struct fib_node *n;

349 
struct fib_iterator *j;

350 
for(n=f.hash_table[i]; n; n=n>next)

351 
{ 
352 
debug("%04x %04x %p %I/%2d", i, ipa_hash(n>prefix), n, n>prefix, n>pxlen);

353 
for(j=n>readers; j; j=j>next)

354 
debug(" %p[%p]", j, j>node);

355 
debug("\n");

356 
} 
357 
} 
358 
fib_check(&f); 
359 
debug("\n");

360 
} 
361  
362 
void init(struct fib_node *n) 
363 
{ 
364 
} 
365  
366 
int main(void) 
367 
{ 
368 
struct fib_node *n;

369 
struct fib_iterator i, j;

370 
ip_addr a; 
371 
int c;

372  
373 
log_init_debug(NULL);

374 
resource_init(); 
375 
fib_init(&f, &root_pool, sizeof(struct fib_node), 4, init); 
376 
dump("init");

377  
378 
a = ipa_from_u32(0x01020304); n = fib_get(&f, &a, 32); 
379 
a = ipa_from_u32(0x02030405); n = fib_get(&f, &a, 32); 
380 
a = ipa_from_u32(0x03040506); n = fib_get(&f, &a, 32); 
381 
a = ipa_from_u32(0x00000000); n = fib_get(&f, &a, 32); 
382 
a = ipa_from_u32(0x00000c01); n = fib_get(&f, &a, 32); 
383 
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); 
384 
dump("fill");

385  
386 
fit_init(&i, &f); 
387 
dump("iter init");

388  
389 
fib_rehash(&f, 1);

390 
dump("rehash up");

391  
392 
fib_rehash(&f, 1);

393 
dump("rehash down");

394  
395 
next:

396 
c = 0;

397 
FIB_ITERATE_START(&f, &i, z) 
398 
{ 
399 
if (c)

400 
{ 
401 
FIB_ITERATE_PUT(&i, z); 
402 
dump("iter");

403 
goto next;

404 
} 
405 
c = 1;

406 
debug("got %p\n", z);

407 
} 
408 
FIB_ITERATE_END; 
409 
dump("iter end");

410  
411 
fit_init(&i, &f); 
412 
fit_init(&j, &f); 
413 
dump("iter init 2");

414  
415 
n = fit_get(&f, &i); 
416 
dump("iter step 2");

417  
418 
fit_put(&i, n>next); 
419 
dump("iter step 3");

420  
421 
a = ipa_from_u32(0xffffffff); n = fib_get(&f, &a, 32); 
422 
fib_delete(&f, n); 
423 
dump("iter step 3");

424  
425 
return 0; 
426 
} 
427  
428 
#endif
