Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 421838ff

History | View | Annotate | Download (7.89 KB)

1
/*
2
 *        BIRD -- Routing Table
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
#include <string.h>
10

    
11
#define LOCAL_DEBUG
12

    
13
#include "nest/bird.h"
14
#include "nest/route.h"
15
#include "nest/protocol.h"
16
#include "lib/resource.h"
17
#include "lib/event.h"
18
#include "filter/filter.h"
19

    
20
rtable master_table;
21
static slab *rte_slab;
22

    
23
#define RT_GC_MIN_TIME 5                /* FIXME: Make configurable */
24
#define RT_GC_MIN_COUNT 100
25

    
26
static pool *rt_table_pool;
27
static event *rt_gc_event;
28
static bird_clock_t rt_last_gc;
29
static int rt_gc_counter;
30

    
31
static void
32
rte_init(struct fib_node *N)
33
{
34
  net *n = (net *) N;
35

    
36
  N->flags = 0;
37
  n->routes = NULL;
38
}
39

    
40
void
41
rt_setup(rtable *t, char *name)
42
{
43
  bzero(t, sizeof(*t));
44
  fib_init(&t->fib, &root_pool, sizeof(rte), 0, rte_init);
45
  t->name = name;
46
}
47

    
48
net *
49
net_find(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
50
{
51
  while (tab && tab->tos != tos)
52
    tab = tab->sibling;
53
  if (!tab)
54
    return NULL;
55
  return (net *) fib_find(&tab->fib, &mask, len);
56
}
57

    
58
net *
59
net_get(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
60
{
61
  rtable *t = tab;
62

    
63
  while (t && t->tos != tos)
64
    t = t->sibling;
65
  if (!t)
66
    {
67
      while (tab->sibling)
68
        tab = tab->sibling;
69
      t = mb_alloc(&root_pool, sizeof(rtable));
70
      rt_setup(t, NULL);
71
      tab->sibling = t;
72
      t->tos = tos;
73
    }
74
  return (net *) fib_get(&t->fib, &mask, len);
75
}
76

    
77
rte *
78
rte_find(net *net, struct proto *p)
79
{
80
  rte *e = net->routes;
81

    
82
  while (e && e->attrs->proto != p)
83
    e = e->next;
84
  return e;
85
}
86

    
87
rte *
88
rte_get_temp(rta *a)
89
{
90
  rte *e = sl_alloc(rte_slab);
91

    
92
  e->attrs = a;
93
  e->flags = 0;
94
  e->pref = a->proto->preference;
95
  return e;
96
}
97

    
98
static int                                /* Actually better or at least as good as */
99
rte_better(rte *new, rte *old)
100
{
101
  int (*better)(rte *, rte *);
102

    
103
  if (!old)
104
    return 1;
105
  if (new->pref > old->pref)
106
    return 1;
107
  if (new->pref < old->pref)
108
    return 0;
109
  if (new->attrs->proto != old->attrs->proto)
110
    {
111
      /* FIXME!!! */
112
      bug("Different protocols, but identical preferences => oops");
113
    }
114
  if (better = new->attrs->proto->rte_better)
115
    return better(new, old);
116
  return 0;
117
}
118

    
119
static inline void
120
do_rte_announce(struct proto *p, net *net, rte *new, rte *old)
121
{
122
  if (p->out_filter)
123
    {
124
      if (old && f_run(p->out_filter, old, NULL) != F_ACCEPT)
125
        old = NULL;
126
      if (new && f_run(p->out_filter, new, NULL) != F_ACCEPT)
127
        new = NULL;
128
    }
129
  if (new || old)
130
    p->rt_notify(p, net, new, old);
131
}
132

    
133
void
134
rte_announce(net *net, rte *new, rte *old)
135
{
136
  struct proto *p;
137

    
138
  WALK_LIST(p, proto_list)
139
    {
140
      ASSERT(p->core_state == FS_HAPPY);
141
      if (p->rt_notify)
142
        do_rte_announce(p, net, new, old);
143
    }
144
}
145

    
146
void
147
rt_feed_baby(struct proto *p)
148
{
149
  rtable *t = &master_table;
150

    
151
  if (!p->rt_notify)
152
    return;
153
  debug("Announcing routes to new protocol %s\n", p->name);
154
  while (t)
155
    {
156
      FIB_WALK(&t->fib, fn)
157
        {
158
          net *n = (net *) fn;
159
          rte *e;
160
          for(e=n->routes; e; e=e->next)
161
            do_rte_announce(p, n, e, NULL);
162
        }
163
      FIB_WALK_END;
164
      t = t->sibling;
165
    }
166
}
167

    
168
static inline int
169
rte_validate(rte *e)
170
{
171
  int c;
172
  net *n = e->net;
173

    
174
  ASSERT(!ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))));
175
  if (n->n.pxlen)
176
    {
177
      c = ipa_classify(n->n.prefix);
178
      if (c < 0 || !(c & IADDR_HOST))
179
        {
180
          if (!ipa_nonzero(n->n.prefix) && n->n.pxlen <= 1)
181
            return 1;                /* Default route and half-default route is OK */
182
          log(L_WARN "Ignoring bogus route %I/%d received from %I via %s",
183
              n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
184
          return 0;
185
        }
186
      if ((c & IADDR_SCOPE_MASK) == SCOPE_HOST)
187
        {
188
          int s = e->attrs->source;
189
          if (s != RTS_STATIC && s != RTS_DEVICE && s != RTS_STATIC_DEVICE)
190
            {
191
              log(L_WARN "Ignoring host scope route %I/%d received from %I via %s",
192
                  n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
193
              return 0;
194
            }
195
        }
196
    }
197
  return 1;
198
}
199

    
200
void
201
rte_free(rte *e)
202
{
203
  if (e->attrs->aflags & RTAF_CACHED)
204
    rta_free(e->attrs);
205
  sl_free(rte_slab, e);
206
}
207

    
208
static inline void
209
rte_free_quick(rte *e)
210
{
211
  rta_free(e->attrs);
212
  sl_free(rte_slab, e);
213
}
214

    
215
void
216
rte_update(net *net, struct proto *p, rte *new)
217
{
218
  rte *old_best = net->routes;
219
  rte *old = NULL;
220
  rte **k, *r, *s;
221

    
222
  if (new)
223
    {
224
      if (!rte_validate(new) || p->in_filter && f_run(p->in_filter, new, NULL) != F_ACCEPT)
225
        {
226
          rte_free(new);
227
          return;
228
        }
229
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
230
        new->attrs = rta_lookup(new->attrs);
231
    }
232

    
233
  k = &net->routes;                        /* Find and remove original route from the same protocol */
234
  while (old = *k)
235
    {
236
      if (old->attrs->proto == p)
237
        {
238
          *k = old->next;
239
          break;
240
        }
241
      k = &old->next;
242
    }
243

    
244
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
245
    {
246
      rte_announce(net, new, old_best);
247
      new->next = net->routes;
248
      net->routes = new;
249
    }
250
  else
251
    {
252
      if (old == old_best)                /* It has _replaced_ the old optimal route */
253
        {
254
          r = new;                        /* Find new optimal route and announce it */
255
          for(s=net->routes; s; s=s->next)
256
            if (rte_better(s, r))
257
              r = s;
258
          rte_announce(net, r, old_best);
259
          if (r)                        /* Re-link the new optimal route */
260
            {
261
              k = &net->routes;
262
              while (s = *k)
263
                {
264
                  if (s == r)
265
                    {
266
                      *k = r->next;
267
                      break;
268
                    }
269
                  k = &s->next;
270
                }
271
              r->next = net->routes;
272
              net->routes = r;
273
              if (!r && rt_gc_counter++ >= RT_GC_MIN_COUNT && rt_last_gc + RT_GC_MIN_TIME <= now)
274
                ev_schedule(rt_gc_event);
275
            }
276
        }
277
      if (new)                                /* Link in the new non-optimal route */
278
        {
279
          new->next = old_best->next;
280
          old_best->next = new;
281
        }
282
    }
283
  if (old)
284
    {
285
      if (p->rte_remove)
286
        p->rte_remove(net, old);
287
      rte_free_quick(old);
288
    }
289
  if (new)
290
    {
291
      new->lastmod = now;
292
      if (p->rte_insert)
293
        p->rte_insert(net, new);
294
    }
295
}
296

    
297
void
298
rte_discard(rte *old)                        /* Non-filtered route deletion, used during garbage collection */
299
{
300
  rte_update(old->net, old->attrs->proto, NULL);
301
}
302

    
303
void
304
rte_dump(rte *e)
305
{
306
  net *n = e->net;
307
  if (n)
308
    debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
309
  else
310
    debug("??? ");
311
  debug("PF=%02x pref=%d lm=%d ", e->pflags, e->pref, now-e->lastmod);
312
  rta_dump(e->attrs);
313
  if (e->flags & REF_CHOSEN)
314
    debug(" [*]");
315
  debug("\n");
316
}
317

    
318
void
319
rt_dump(rtable *t)
320
{
321
  rte *e;
322
  net *n;
323

    
324
  debug("Dump of routing table <%s>\n", t->name);
325
  while (t)
326
    {
327
      debug("Routes for TOS %02x:\n", t->tos);
328
#ifdef DEBUGGING
329
      fib_check(&t->fib);
330
#endif
331
      FIB_WALK(&t->fib, fn)
332
        {
333
          n = (net *) fn;
334
          for(e=n->routes; e; e=e->next)
335
            rte_dump(e);
336
        }
337
      FIB_WALK_END;
338
      t = t->sibling;
339
    }
340
  debug("\n");
341
}
342

    
343
void
344
rt_dump_all(void)
345
{
346
  rt_dump(&master_table);
347
}
348

    
349
static void
350
rt_gc(void *unused)
351
{
352
  DBG("Entered routing table garbage collector after %d seconds and %d deletes\n", (int)(now - rt_last_gc), rt_gc_counter);
353
  rt_prune(&master_table);
354
  rt_last_gc = now;
355
  rt_gc_counter = 0;
356
}
357

    
358
void
359
rt_init(void)
360
{
361
  rta_init();
362
  rt_table_pool = rp_new(&root_pool, "Routing tables");
363
  rt_setup(&master_table, "master");
364
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
365
  rt_last_gc = now;
366
  rt_gc_event = ev_new(rt_table_pool);
367
  rt_gc_event->hook = rt_gc;
368
}
369

    
370
void
371
rt_prune(rtable *tab)
372
{
373
  struct fib_iterator fit;
374
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
375

    
376
  DBG("Pruning route table %s\n", tab->name);
377
  while (tab)
378
    {
379
      FIB_ITERATE_INIT(&fit, &tab->fib);
380
    again:
381
      FIB_ITERATE_START(&tab->fib, &fit, f)
382
        {
383
          net *n = (net *) f;
384
          rte *e;
385
          ncnt++;
386
        rescan:
387
          for (e=n->routes; e; e=e->next, rcnt++)
388
            if (e->attrs->proto->core_state != FS_HAPPY)
389
              {
390
                rte_discard(e);
391
                rdel++;
392
                goto rescan;
393
              }
394
          if (!n->routes)                /* Orphaned FIB entry? */
395
            {
396
              FIB_ITERATE_PUT(&fit, f);
397
              fib_delete(&tab->fib, f);
398
              ndel++;
399
              goto again;
400
            }
401
        }
402
      FIB_ITERATE_END(f);
403
      tab = tab->sibling;
404
    }
405
  DBG("Pruned %d of %d routes and %d of %d networks\n", rcnt, rdel, ncnt, ndel);
406
}