Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 51ad41f2

History | View | Annotate | Download (6.55 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

    
19
rtable master_table;
20
static slab *rte_slab;
21

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    
118
void
119
rte_announce(net *net, rte *new, rte *old)
120
{
121
  struct proto *p;
122

    
123
  WALK_LIST(p, proto_list)
124
    {
125
      ASSERT(p->core_state == FS_HAPPY);
126
      if (p->rt_notify)
127
        p->rt_notify(p, net, new, old);
128
    }
129
}
130

    
131
void
132
rt_feed_baby(struct proto *p)
133
{
134
  rtable *t = &master_table;
135

    
136
  if (!p->rt_notify)
137
    return;
138
  debug("Announcing routes to new protocol %s\n", p->name);
139
  while (t)
140
    {
141
      FIB_WALK(&t->fib, fn)
142
        {
143
          net *n = (net *) fn;
144
          rte *e;
145
          for(e=n->routes; e; e=e->next)
146
            p->rt_notify(p, n, e, NULL);
147
        }
148
      FIB_WALK_END;
149
      t = t->sibling;
150
    }
151
}
152

    
153
void
154
rte_free(rte *e)
155
{
156
  if (e->attrs->aflags & RTAF_CACHED)
157
    rta_free(e->attrs);
158
  sl_free(rte_slab, e);
159
}
160

    
161
static inline void
162
rte_free_quick(rte *e)
163
{
164
  rta_free(e->attrs);
165
  sl_free(rte_slab, e);
166
}
167

    
168
void
169
rte_update(net *net, struct proto *p, rte *new)
170
{
171
  rte *old_best = net->routes;
172
  rte *old = NULL;
173
  rte **k, *r, *s;
174

    
175
  if (new && !(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
176
    new->attrs = rta_lookup(new->attrs);
177

    
178
  k = &net->routes;                        /* Find and remove original route from the same protocol */
179
  while (old = *k)
180
    {
181
      if (old->attrs->proto == p)
182
        {
183
          *k = old->next;
184
          break;
185
        }
186
      k = &old->next;
187
    }
188

    
189
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
190
    {
191
      rte_announce(net, new, old_best);
192
      new->next = net->routes;
193
      net->routes = new;
194
    }
195
  else
196
    {
197
      if (old == old_best)                /* It has _replaced_ the old optimal route */
198
        {
199
          r = new;                        /* Find new optimal route and announce it */
200
          for(s=net->routes; s; s=s->next)
201
            if (rte_better(s, r))
202
              r = s;
203
          rte_announce(net, r, old_best);
204
          if (r)                        /* Re-link the new optimal route */
205
            {
206
              k = &net->routes;
207
              while (s = *k)
208
                {
209
                  if (s == r)
210
                    {
211
                      *k = r->next;
212
                      break;
213
                    }
214
                  k = &s->next;
215
                }
216
              r->next = net->routes;
217
              net->routes = r;
218
              if (!r && rt_gc_counter++ >= RT_GC_MIN_COUNT && rt_last_gc + RT_GC_MIN_TIME <= now)
219
                ev_schedule(rt_gc_event);
220
            }
221
        }
222
      if (new)                                /* Link in the new non-optimal route */
223
        {
224
          new->next = old_best->next;
225
          old_best->next = new;
226
        }
227
    }
228
  if (old)
229
    {
230
      if (p->rte_remove)
231
        p->rte_remove(net, old);
232
      rte_free_quick(old);
233
    }
234
  if (new)
235
    {
236
      new->lastmod = now;
237
      if (p->rte_insert)
238
        p->rte_insert(net, new);
239
    }
240
}
241

    
242
void
243
rte_discard(rte *old)                        /* Non-filtered route deletion, used during garbage collection */
244
{
245
  rte_update(old->net, old->attrs->proto, NULL);
246
}
247

    
248
void
249
rte_dump(rte *e)
250
{
251
  net *n = e->net;
252
  if (n)
253
    debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
254
  else
255
    debug("??? ");
256
  debug("PF=%02x pref=%d lm=%d ", e->pflags, e->pref, now-e->lastmod);
257
  rta_dump(e->attrs);
258
  if (e->flags & REF_CHOSEN)
259
    debug(" [*]");
260
  debug("\n");
261
}
262

    
263
void
264
rt_dump(rtable *t)
265
{
266
  rte *e;
267
  net *n;
268

    
269
  debug("Dump of routing table <%s>\n", t->name);
270
  while (t)
271
    {
272
      debug("Routes for TOS %02x:\n", t->tos);
273
#ifdef DEBUGGING
274
      fib_check(&t->fib);
275
#endif
276
      FIB_WALK(&t->fib, fn)
277
        {
278
          n = (net *) fn;
279
          for(e=n->routes; e; e=e->next)
280
            rte_dump(e);
281
        }
282
      FIB_WALK_END;
283
      t = t->sibling;
284
    }
285
  debug("\n");
286
}
287

    
288
void
289
rt_dump_all(void)
290
{
291
  rt_dump(&master_table);
292
}
293

    
294
static void
295
rt_gc(void *unused)
296
{
297
  DBG("Entered routing table garbage collector after %d seconds and %d deletes\n", (int)(now - rt_last_gc), rt_gc_counter);
298
  rt_prune(&master_table);
299
  rt_last_gc = now;
300
  rt_gc_counter = 0;
301
}
302

    
303
void
304
rt_init(void)
305
{
306
  rta_init();
307
  rt_table_pool = rp_new(&root_pool, "Routing tables");
308
  rt_setup(&master_table, "master");
309
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
310
  rt_last_gc = now;
311
  rt_gc_event = ev_new(rt_table_pool);
312
  rt_gc_event->hook = rt_gc;
313
}
314

    
315
void
316
rt_prune(rtable *tab)
317
{
318
  struct fib_iterator fit;
319
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
320

    
321
  DBG("Pruning route table %s\n", tab->name);
322
  while (tab)
323
    {
324
      FIB_ITERATE_INIT(&fit, &tab->fib);
325
    again:
326
      FIB_ITERATE_START(&tab->fib, &fit, f)
327
        {
328
          net *n = (net *) f;
329
          rte *e;
330
          ncnt++;
331
        rescan:
332
          for (e=n->routes; e; e=e->next, rcnt++)
333
            if (e->attrs->proto->core_state != FS_HAPPY)
334
              {
335
                rte_discard(e);
336
                rdel++;
337
                goto rescan;
338
              }
339
          if (!n->routes)                /* Orphaned FIB entry? */
340
            {
341
              FIB_ITERATE_PUT(&fit, f);
342
              fib_delete(&tab->fib, f);
343
              ndel++;
344
              goto again;
345
            }
346
        }
347
      FIB_ITERATE_END(f);
348
      tab = tab->sibling;
349
    }
350
  DBG("Pruned %d of %d routes and %d of %d networks\n", rcnt, rdel, ncnt, ndel);
351
}