Revision fe9f1a6d nest/rt-fib.c

View differences:

nest/rt-fib.c
48 48
#define HASH_LO_STEP 2
49 49
#define HASH_LO_MIN 10
50 50

  
51

  
52
static inline void * fib_node_to_user(struct fib *f, struct fib_node *e)
53
{ return (void *) ((char *) e - f->node_offset); }
54

  
55
static inline struct fib_node * fib_user_to_node(struct fib *f, void *e)
56
{ return (void *) ((char *) e + f->node_offset); }
57

  
51 58
static void
52 59
fib_ht_alloc(struct fib *f)
53 60
{
......
72 79
  mb_free(h);
73 80
}
74 81

  
75
static inline unsigned
76
fib_hash(struct fib *f, ip_addr *a)
77
{
78
  return ipa_hash(*a) >> f->hash_shift;
79
}
80 82

  
81
static void
82
fib_dummy_init(struct fib_node *dummy UNUSED)
83
{
84
}
83
static u32
84
fib_hash(struct fib *f, net_addr *a);
85 85

  
86 86
/**
87 87
 * fib_init - initialize a new FIB
......
96 96
 * This function initializes a newly allocated FIB and prepares it for use.
97 97
 */
98 98
void
99
fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_order, fib_init_func init)
99
fib_init(struct fib *f, pool *p, uint addr_type, uint node_size, uint node_offset, uint hash_order, fib_init_fn init)
100 100
{
101
  uint addr_length = net_addr_length[addr_type];
102

  
101 103
  if (!hash_order)
102 104
    hash_order = HASH_DEF_ORDER;
103 105
  f->fib_pool = p;
104
  f->fib_slab = sl_new(p, node_size);
106
  f->fib_slab = addr_length ? sl_new(p, node_size + addr_length) : NULL;
107
  f->addr_type = addr_type;
108
  f->node_size = node_size;
109
  f->node_offset = node_offset;
105 110
  f->hash_order = hash_order;
106 111
  fib_ht_alloc(f);
107 112
  bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *));
108 113
  f->entries = 0;
109 114
  f->entries_min = 0;
110
  f->init = init ? : fib_dummy_init;
115
  f->init = init;
111 116
}
112 117

  
113 118
static void
......
133 138
      while (e = x)
134 139
	{
135 140
	  x = e->next;
136
	  nh = fib_hash(f, &e->prefix);
141
	  nh = fib_hash(f, e->addr);
137 142
	  while (nh > ni)
138 143
	    {
139 144
	      *t = NULL;
......
153 158
  fib_ht_free(m);
154 159
}
155 160

  
161
#define CAST(t) (net_addr_##t *)
162

  
163
#define FIB_HASH(f,a,t) (net_hash_##t(CAST(t) a) >> f->hash_shift)
164

  
165
#define FIB_FIND(f,a,t)							\
166
  ({									\
167
    struct fib_node *e = f->hash_table[FIB_HASH(f, a, t)];		\
168
    while (e && !net_equal_##t(CAST(t) e->addr, CAST(t) a))		\
169
      e = e->next;							\
170
    fib_node_to_user(f, e);						\
171
  })
172

  
173
#define FIB_INSERT(f,a,e,t)						\
174
  ({									\
175
  u32 h = net_hash_##t(CAST(t) a);					\
176
  struct fib_node **ee = f->hash_table + (h >> f->hash_shift);		\
177
  struct fib_node *g;							\
178
									\
179
  while ((g = *ee) && (net_hash_##t(CAST(t) g->addr) < h))		\
180
    ee = &g->next;							\
181
									\
182
  net_copy_##t(CAST(t) e->addr, CAST(t) a);				\
183
  e->next = *ee;							\
184
  *ee = e;								\
185
  })
186

  
187

  
188
static u32
189
fib_hash(struct fib *f, net_addr *a)
190
{
191
  switch (f->addr_type)
192
  {
193
  case NET_IP4: return FIB_HASH(f, a, ip4);
194
  case NET_IP6: return FIB_HASH(f, a, ip6);
195
  case NET_VPN4: return FIB_HASH(f, a, vpn4);
196
  case NET_VPN6: return FIB_HASH(f, a, vpn6);
197
  default: bug("invalid type");
198
  }
199
}
200

  
201
void *
202
fib_find(struct fib *f, net_addr *a)
203
{
204
  ASSERT(f->addr_type == a->type);
205

  
206
  switch (f->addr_type)
207
  {
208
  case NET_IP4: return FIB_FIND(f, a, ip4);
209
  case NET_IP6: return FIB_FIND(f, a, ip6);
210
  case NET_VPN4: return FIB_FIND(f, a, vpn4);
211
  case NET_VPN6: return FIB_FIND(f, a, vpn6);
212
  default: bug("invalid type");
213
  }
214
}
215

  
216
static void
217
fib_insert(struct fib *f, net_addr *a, struct fib_node *e)
218
{
219
  switch (f->addr_type)
220
  {
221
  case NET_IP4: FIB_INSERT(f, a, e, ip4); return;
222
  case NET_IP6: FIB_INSERT(f, a, e, ip6); return;
223
  case NET_VPN4: FIB_INSERT(f, a, e, vpn4); return;
224
  case NET_VPN6: FIB_INSERT(f, a, e, vpn6); return;
225
  default: bug("invalid type");
226
  }
227
}
228

  
229

  
230

  
156 231
/**
157 232
 * fib_find - search for FIB node by prefix
158 233
 * @f: FIB to search in
......
162 237
 * Search for a FIB node corresponding to the given prefix, return
163 238
 * a pointer to it or %NULL if no such node exists.
164 239
 */
240
/*
165 241
void *
166
fib_find(struct fib *f, ip_addr *a, int len)
242
fib_find(struct fib *f, net_addr *a)
167 243
{
168 244
  struct fib_node *e = f->hash_table[fib_hash(f, a)];
169 245

  
......
171 247
    e = e->next;
172 248
  return e;
173 249
}
174

  
175
/*
176
int
177
fib_histogram(struct fib *f)
178
{
179
  log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
180

  
181
  int i, j;
182
  struct fib_node *e;
183

  
184
  for (i = 0; i < f->hash_size; i++)
185
    {
186
      j = 0;
187
      for (e = f->hash_table[i]; e != NULL; e = e->next)
188
	j++;
189
      if (j > 0)
190
        log(L_WARN "Histogram line %d: %d", i, j);
191
    }
192

  
193
  log(L_WARN "Histogram dump end");
194
}
195 250
*/
196 251

  
197 252
/**
......
204 259
 * return a pointer to it. If no such node exists, create it.
205 260
 */
206 261
void *
207
fib_get(struct fib *f, ip_addr *a, int len)
262
fib_get(struct fib *f, net_addr *a)
208 263
{
209
  uint h = ipa_hash(*a);
210
  struct fib_node **ee = f->hash_table + (h >> f->hash_shift);
211
  struct fib_node *g, *e = *ee;
212
  u32 uid = h << 16;
213

  
214
  while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix)))
215
    e = e->next;
216
  if (e)
217
    return e;
218
#ifdef DEBUGGING
219
  if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len))
220
    bug("fib_get() called for invalid address");
221
#endif
264
  char *b = fib_find(f, a);
265
  if (b)
266
    return b;
222 267

  
223
  while ((g = *ee) && g->uid < uid)
224
    ee = &g->next;
225
  while ((g = *ee) && g->uid == uid)
226
    {
227
      ee = &g->next;
228
      uid++;
229
    }
268
  if (f->fib_slab)
269
    b = sl_alloc(f->fib_slab);
270
  else
271
    b = mb_alloc(f->fib_pool, f->node_size + a->length);
230 272

  
231
  if ((uid >> 16) != h)
232
    log(L_ERR "FIB hash table chains are too long");
273
  struct fib_node *e = (void *) (b + f->node_offset);
274
  e->readers = NULL;
275
  e->flags = 0;
276
  e->uid = 0;
277
  fib_insert(f, a, e);
233 278

  
234
  // log (L_WARN "FIB_GET %I %x %x", *a, h, uid);
279
  memset(b, 0, f->node_offset);
280
  if (f->init)
281
    f->init(b);
235 282

  
236
  e = sl_alloc(f->fib_slab);
237
  e->prefix = *a;
238
  e->pxlen = len;
239
  e->next = *ee;
240
  e->uid = uid;
241
  *ee = e;
242
  e->readers = NULL;
243
  f->init(e);
244 283
  if (f->entries++ > f->entries_max)
245 284
    fib_rehash(f, HASH_HI_STEP);
246 285

  
247
  return e;
286
  return b;
248 287
}
249 288

  
250 289
/**
......
257 296
 * network, that is a node which a CIDR router would use for routing
258 297
 * that network.
259 298
 */
299
/*
260 300
void *
261 301
fib_route(struct fib *f, ip_addr a, int len)
262 302
{
......
273 313
    }
274 314
  return NULL;
275 315
}
316
*/
276 317

  
277 318
static inline void
278 319
fib_merge_readers(struct fib_iterator *i, struct fib_node *to)
......
320 361
void
321 362
fib_delete(struct fib *f, void *E)
322 363
{
323
  struct fib_node *e = E;
324
  uint h = fib_hash(f, &e->prefix);
364
  struct fib_node *e = fib_user_to_node(f, E);
365
  uint h = fib_hash(f, e->addr);
325 366
  struct fib_node **ee = f->hash_table + h;
326 367
  struct fib_iterator *it;
327 368

  
......
413 454
  if (k = i->next)
414 455
    k->prev = j;
415 456
  j->next = k;
416
  i->hash = fib_hash(f, &n->prefix);
457
  i->hash = fib_hash(f, n->addr);
417 458
  return n;
418 459
}
419 460

  
......
498 539
    bug("fib_check: invalid entry count (%d != %d)", ec, f->entries);
499 540
}
500 541

  
542
/*
543
int
544
fib_histogram(struct fib *f)
545
{
546
  log(L_WARN "Histogram dump start %d %d", f->hash_size, f->entries);
547

  
548
  int i, j;
549
  struct fib_node *e;
550

  
551
  for (i = 0; i < f->hash_size; i++)
552
    {
553
      j = 0;
554
      for (e = f->hash_table[i]; e != NULL; e = e->next)
555
	j++;
556
      if (j > 0)
557
        log(L_WARN "Histogram line %d: %d", i, j);
558
    }
559

  
560
  log(L_WARN "Histogram dump end");
561
}
562
*/
563

  
501 564
#endif
502 565

  
503 566
#ifdef TEST
......
517 580
      struct fib_iterator *j;
518 581
      for(n=f.hash_table[i]; n; n=n->next)
519 582
	{
520
	  debug("%04x %04x %p %I/%2d", i, ipa_hash(n->prefix), n, n->prefix, n->pxlen);
583
	  debug("%04x %08x %p %N", i, ipa_hash(n->prefix), n, n->addr);
521 584
	  for(j=n->readers; j; j=j->next)
522 585
	    debug(" %p[%p]", j, j->node);
523 586
	  debug("\n");

Also available in: Unified diff