1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
/*
* BIRD -- Forwarding Information Base -- Data Structures
*
* (c) 1998 Martin Mares <mj@ucw.cz>
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
#define LOCAL_DEBUG
#include <string.h>
#include "nest/bird.h"
#include "nest/route.h"
#define HASH_DEF_SIZE 1024
#define HASH_HI_MARK *16
#define HASH_LO_MARK *0
#define HASH_LO_MIN 128
#define HASH_HI_RESIZE *16
#define HASH_LO_RESIZE *0
static void
fib_ht_alloc(struct fib *f)
{
f->hash_mask = f->hash_size - 1;
f->entries_max = f->hash_size HASH_HI_MARK;
f->entries_min = f->hash_size HASH_LO_MARK;
if (f->entries_min < HASH_LO_MIN)
f->entries_min = 0;
DBG("Allocating FIB: %d entries, %d low, %d high\n", f->hash_size, f->entries_min, f->entries_max);
f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *));
bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
}
static inline void
fib_ht_free(struct fib_node **h)
{
mb_free(h);
}
static inline unsigned
fib_hash(struct fib *f, ip_addr *a)
{
return ipa_hash(*a) & f->hash_mask;
}
void
fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *))
{
if (!hash_size)
hash_size = HASH_DEF_SIZE;
f->fib_pool = p;
f->fib_slab = sl_new(p, node_size);
f->hash_size = hash_size;
fib_ht_alloc(f);
f->entries = 0;
f->entries_min = 0;
f->init = init;
}
static void
fib_rehash(struct fib *f, unsigned new)
{
unsigned old;
struct fib_node **n, *e, *x, **t, **m, **h;
old = f->hash_size;
m = h = f->hash_table;
DBG("Re-hashing FIB from %d to %d\n", old, new);
f->hash_size = new;
fib_ht_alloc(f);
n = f->hash_table;
while (old--)
{
x = *h++;
while (e = x)
{
x = e->next;
t = n + fib_hash(f, &e->prefix);
e->next = *t;
*t = e;
}
}
fib_ht_free(m);
}
void *
fib_find(struct fib *f, ip_addr *a, int len)
{
struct fib_node *e = f->hash_table[fib_hash(f, a)];
while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
e = e->next;
return e;
}
void *
fib_get(struct fib *f, ip_addr *a, int len)
{
struct fib_node **ee = f->hash_table + fib_hash(f, a);
struct fib_node *e = *ee;
while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
e = e->next;
if (e)
return e;
#ifdef DEBUG
if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
die("fib_get() called for invalid address");
#endif
e = sl_alloc(f->fib_slab);
e->prefix = *a;
e->pxlen = len;
e->flags = 0;
e->next = *ee;
*ee = e;
f->init(e);
if (f->entries++ > f->entries_max)
fib_rehash(f, f->hash_size HASH_HI_RESIZE);
return e;
}
void
fib_delete(struct fib *f, void *E)
{
struct fib_node *e = E;
struct fib_node **ee = f->hash_table + fib_hash(f, &e->prefix);
while (*ee)
{
if (*ee == e)
{
*ee = e->next;
sl_free(f->fib_slab, e);
if (f->entries-- < f->entries_min)
fib_rehash(f, f->hash_size HASH_LO_RESIZE);
return;
}
ee = &((*ee)->next);
}
die("fib_delete() called for invalid node");
}
void
fib_free(struct fib *f)
{
fib_ht_free(f->hash_table);
rfree(f->fib_slab);
}
|
