Revision ce4aca09

View differences:

nest/route.h
48 48
  unsigned int hash;
49 49
};
50 50

  
51
typedef void (*fib_init_func)(struct fib_node *);
52

  
51 53
struct fib {
52 54
  pool *fib_pool;			/* Pool holding all our data */
53 55
  slab *fib_slab;			/* Slab holding all fib nodes */
......
57 59
  unsigned int hash_shift;		/* 16 - hash_log */
58 60
  unsigned int entries;			/* Number of entries */
59 61
  unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */
60
  void (*init)(struct fib_node *);	/* Constructor */
62
  fib_init_func init;			/* Constructor */
61 63
};
62 64

  
63
void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_order, void (*init)(struct fib_node *));
65
void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_order, fib_init_func init);
64 66
void *fib_find(struct fib *, ip_addr *, int);	/* Find or return NULL if doesn't exist */
65 67
void *fib_get(struct fib *, ip_addr *, int); 	/* Find or create new if nonexistent */
66 68
void *fib_route(struct fib *, ip_addr, int);	/* Longest-match routing lookup */
nest/rt-fib.c
6 6
 *	Can be freely distributed and used under the terms of the GNU GPL.
7 7
 */
8 8

  
9
/**
10
 * DOC: Forwarding Information Base
11
 *
12
 * FIB is a data structure designed for storage of routes indexed by their
13
 * network prefixes. It supports insertion, deletion, searching by prefix,
14
 * `routing' (in CIDR sense, that is searching for a longest prefix matching
15
 * a given IP address) and (which makes the structure very tricky to implement)
16
 * asynchronous reading, that is enumerating the contents of a FIB while other
17
 * modules add, modify or remove entries.
18
 *
19
 * Internally, each FIB is represented as a collection of nodes of type &fib_node
20
 * indexed using a sophisticated hashing mechanism.
21
 * We use two-stage hashing where we calculate a 16-bit primary hash key independent
22
 * on hash table size and then we just divide the primary keys modulo table size
23
 * to get a real hash key used for determining the bucket containing the node.
24
 * The lists of nodes in each buckets are sorted according to the primary hash
25
 * key, hence if we keep the total number of buckets to be a power of two,
26
 * re-hashing of the structure keeps the relative order of the nodes.
27
 *
28
 * To get the asynchronous reading consistent over node deletions, we need to
29
 * keep a list of readers for each node. When a node gets deleted, its readers
30
 * are automatically moved to the next node in the table.
31
 *
32
 * Basic FIB operations are performed by functions defined by this module,
33
 * enumerating of FIB contents is accomplished by using the FIB_WALK() macro
34
 * or FIB_ITERATE_START() if you want to do it asynchronously.
35
 */
36

  
9 37
#undef LOCAL_DEBUG
10 38

  
11 39
#include "nest/bird.h"
......
55 83
{
56 84
}
57 85

  
86
/**
87
 * fib_init - initialize a new FIB
88
 * @f: the FIB to be initialized (the structure itself being allocated by the caller)
89
 * @p: pool to allocate the nodes in
90
 * @node_size: node size to be used (each node consists of a standard header &fib_node
91
 * followed by user data)
92
 * @hash_order: initial hash order (a binary logarithm of hash table size), 0 to use default order
93
 * (recommended)
94
 * @init: pointer a function to be called to initialize a newly created node
95
 *
96
 * This function initializes a newly allocated FIB and prepares it for use.
97
 */
58 98
void
59
fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, void (*init)(struct fib_node *))
99
fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, fib_init_func init)
60 100
{
61 101
  if (!hash_order)
62 102
    hash_order = HASH_DEF_ORDER;
......
113 153
  fib_ht_free(m);
114 154
}
115 155

  
156
/**
157
 * fib_find - search for FIB node by prefix
158
 * @f: FIB to search in
159
 * @a: pointer to IP address of the prefix
160
 * @len: prefix length
161
 *
162
 * Search for a FIB node corresponding to the given prefix, return
163
 * a pointer to it or %NULL if no such node exists.
164
 */
116 165
void *
117 166
fib_find(struct fib *f, ip_addr *a, int len)
118 167
{
......
123 172
  return e;
124 173
}
125 174

  
175
/**
176
 * fib_get - find or create a FIB node
177
 * @f: FIB to work with
178
 * @a: pointer to IP address of the prefix
179
 * @len: prefix length
180
 *
181
 * Search for a FIB node corresponding to the given prefix and
182
 * return a pointer to it. If no such node exists, create it.
183
 */
126 184
void *
127 185
fib_get(struct fib *f, ip_addr *a, int len)
128 186
{
......
152 210
  return e;
153 211
}
154 212

  
213
/**
214
 * fib_route - CIDR routing lookup
215
 * @f: FIB to search in
216
 * @a: pointer to IP address of the prefix
217
 * @len: prefix length
218
 *
219
 * Search for a FIB node with longest prefix matching the given
220
 * network, that is a node which a CIDR router would use for routing
221
 * that network.
222
 */
155 223
void *
156 224
fib_route(struct fib *f, ip_addr a, int len)
157 225
{
......
203 271
      }
204 272
}
205 273

  
274
/**
275
 * fib_delete - delete a FIB node
276
 * @f: FIB to delete from
277
 * @E: entry to delete
278
 *
279
 * This function removes the given entry from the FIB,
280
 * taking care of all the asynchronous readers by shifting
281
 * them to the next node in the canonical reading order.
282
 */
206 283
void
207 284
fib_delete(struct fib *f, void *E)
208 285
{
......
239 316
  bug("fib_delete() called for invalid node");
240 317
}
241 318

  
319
/**
320
 * fib_free - delete a FIB
321
 * @f: FIB to be deleted
322
 *
323
 * This function deletes a FIB -- it frees all memory associated
324
 * with it and all its entries.
325
 */
242 326
void
243 327
fib_free(struct fib *f)
244 328
{
......
311 395

  
312 396
#ifdef DEBUGGING
313 397

  
398
/**
399
 * fib_check - audit a FIB
400
 * @f: FIB to be checked
401
 *
402
 * This debugging function audits a FIB by checking its internal consistency.
403
 * Use when you suspect somebody from corrupting innocent data structures.
404
 */
314 405
void
315 406
fib_check(struct fib *f)
316 407
{

Also available in: Unified diff