Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ 64011f89

History | View | Annotate | Download (5.01 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
#include "nest/bird.h"
12
#include "nest/route.h"
13
#include "nest/protocol.h"
14
#include "lib/resource.h"
15

    
16
rtable master_table;
17
static slab *rte_slab;
18

    
19
void
20
rte_init(struct fib_node *N)
21
{
22
  net *n = (net *) N;
23

    
24
  N->flags = 0;
25
  n->routes = NULL;
26
}
27

    
28
void
29
rt_setup(rtable *t, char *name)
30
{
31
  bzero(t, sizeof(*t));
32
  fib_init(&t->fib, &root_pool, sizeof(rte), 0, rte_init);
33
  t->name = name;
34
}
35

    
36
net *
37
net_find(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
38
{
39
  while (tab && tab->tos != tos)
40
    tab = tab->sibling;
41
  if (!tab)
42
    return NULL;
43
  return (net *) fib_find(&tab->fib, &mask, len);
44
}
45

    
46
net *
47
net_get(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
48
{
49
  rtable *t = tab;
50

    
51
  while (t && t->tos != tos)
52
    t = t->sibling;
53
  if (!t)
54
    {
55
      while (tab->sibling)
56
        tab = tab->sibling;
57
      t = mb_alloc(&root_pool, sizeof(rtable));
58
      rt_setup(t, NULL);
59
      tab->sibling = t;
60
      t->tos = tos;
61
    }
62
  return (net *) fib_get(&t->fib, &mask, len);
63
}
64

    
65
rte *
66
rte_find(net *net, struct proto *p)
67
{
68
  rte *e = net->routes;
69

    
70
  while (e && e->attrs->proto != p)
71
    e = e->next;
72
  return e;
73
}
74

    
75
rte *
76
rte_get_temp(rta *a)
77
{
78
  rte *e = sl_alloc(rte_slab);
79

    
80
  e->attrs = a;
81
  e->flags = 0;
82
  e->pref = a->proto->preference;
83
  return e;
84
}
85

    
86
static int                                /* Actually better or at least as good as */
87
rte_better(rte *new, rte *old)
88
{
89
  int (*better)(rte *, rte *);
90

    
91
  if (!old)
92
    return 1;
93
  if (new->pref > old->pref)
94
    return 1;
95
  if (new->pref < old->pref)
96
    return 0;
97
  if (new->attrs->proto != old->attrs->proto)
98
    {
99
      /* FIXME!!! */
100
      bug("Different protocols, but identical preferences => oops");
101
    }
102
  if (better = new->attrs->proto->rte_better)
103
    return better(new, old);
104
  return 0;
105
}
106

    
107
void
108
rte_announce(net *net, rte *new, rte *old)
109
{
110
  struct proto *p;
111

    
112
  WALK_LIST(p, proto_list)
113
    if (p->rt_notify)
114
      p->rt_notify(p, net, new, old);
115
}
116

    
117
void
118
rt_feed_baby(struct proto *p)
119
{
120
  rtable *t = &master_table;
121

    
122
  if (!p->rt_notify)
123
    return;
124
  debug("Announcing routes to new protocol %s\n", p->name);
125
  while (t)
126
    {
127
      FIB_WALK(&t->fib, fn)
128
        {
129
          net *n = (net *) fn;
130
          rte *e;
131
          for(e=n->routes; e; e=e->next)
132
            p->rt_notify(p, n, e, NULL);
133
        }
134
      FIB_WALK_END;
135
      t = t->sibling;
136
    }
137
}
138

    
139
void
140
rte_free(rte *e)
141
{
142
  if (e->attrs->aflags & RTAF_CACHED)
143
    rta_free(e->attrs);
144
  sl_free(rte_slab, e);
145
}
146

    
147
static inline void
148
rte_free_quick(rte *e)
149
{
150
  rta_free(e->attrs);
151
  sl_free(rte_slab, e);
152
}
153

    
154
void
155
rte_update(net *net, struct proto *p, rte *new)
156
{
157
  rte *old_best = net->routes;
158
  rte *old = NULL;
159
  rte **k, *r, *s;
160

    
161
  if (new && !(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
162
    new->attrs = rta_lookup(new->attrs);
163

    
164
  k = &net->routes;                        /* Find and remove original route from the same protocol */
165
  while (old = *k)
166
    {
167
      if (old->attrs->proto == p)
168
        {
169
          *k = old->next;
170
          break;
171
        }
172
      k = &old->next;
173
    }
174

    
175
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
176
    {
177
      rte_announce(net, new, old_best);
178
      new->next = net->routes;
179
      net->routes = new;
180
    }
181
  else
182
    {
183
      if (old == old_best)                /* It has _replaced_ the old optimal route */
184
        {
185
          r = new;                        /* Find new optimal route and announce it */
186
          for(s=net->routes; s; s=s->next)
187
            if (rte_better(s, r))
188
              r = s;
189
          rte_announce(net, r, old_best);
190
          if (r)                        /* Re-link the new optimal route */
191
            {
192
              k = &net->routes;
193
              while (s = *k)
194
                {
195
                  if (s == r)
196
                    {
197
                      *k = r->next;
198
                      break;
199
                    }
200
                  k = &s->next;
201
                }
202
              r->next = net->routes;
203
              net->routes = r;
204
            }
205
        }
206
      if (new)                                /* Link in the new non-optimal route */
207
        {
208
          new->next = old_best->next;
209
          old_best->next = new;
210
        }
211
    }
212
  if (old)
213
    {
214
      if (p->rte_remove)
215
        p->rte_remove(net, old);
216
      rte_free_quick(old);
217
    }
218
  if (new)
219
    {
220
      new->lastmod = now;
221
      if (p->rte_insert)
222
        p->rte_insert(net, new);
223
    }
224
}
225

    
226
void
227
rte_discard(rte *old)                        /* Non-filtered route deletion, used during garbage collection */
228
{
229
  rte_update(old->net, old->attrs->proto, NULL);
230
}
231

    
232
void
233
rte_dump(rte *e)
234
{
235
  net *n = e->net;
236
  if (n)
237
    debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
238
  else
239
    debug("??? ");
240
  debug("PF=%02x pref=%d lm=%d ", e->pflags, e->pref, now-e->lastmod);
241
  rta_dump(e->attrs);
242
  if (e->flags & REF_CHOSEN)
243
    debug(" [*]");
244
  debug("\n");
245
}
246

    
247
void
248
rt_dump(rtable *t)
249
{
250
  rte *e;
251
  net *n;
252

    
253
  debug("Dump of routing table <%s>\n", t->name);
254
  while (t)
255
    {
256
      debug("Routes for TOS %02x:\n", t->tos);
257
#ifdef DEBUGGING
258
      fib_check(&t->fib);
259
#endif
260
      FIB_WALK(&t->fib, fn)
261
        {
262
          n = (net *) fn;
263
          for(e=n->routes; e; e=e->next)
264
            rte_dump(e);
265
        }
266
      FIB_WALK_END;
267
      t = t->sibling;
268
    }
269
  debug("\n");
270
}
271

    
272
void
273
rt_dump_all(void)
274
{
275
  rt_dump(&master_table);
276
}
277

    
278
void
279
rt_init(void)
280
{
281
  rta_init();
282
  rt_setup(&master_table, "master");
283
  rte_slab = sl_new(&root_pool, sizeof(rte));
284
}