Statistics
| Branch: | Revision:

iof-bird-daemon / nest / rt-table.c @ db6984c4

History | View | Annotate | Download (4.72 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
      die("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
static inline void
140
rte_free(rte *e)
141
{
142
  rta_free(e->attrs);
143
  sl_free(rte_slab, e);
144
}
145

    
146
void
147
rte_update(net *net, struct proto *p, rte *new)
148
{
149
  rte *old_best = net->routes;
150
  rte *old = NULL;
151
  rte **k, *r, *s;
152

    
153
  k = &net->routes;                        /* Find and remove original route from the same protocol */
154
  while (old = *k)
155
    {
156
      if (old->attrs->proto == p)
157
        {
158
          *k = old->next;
159
          break;
160
        }
161
      k = &old->next;
162
    }
163

    
164
  if (new && rte_better(new, old_best))        /* It's a new optimal route => announce and relink it */
165
    {
166
      rte_announce(net, new, old_best);
167
      new->next = net->routes;
168
      net->routes = new;
169
    }
170
  else
171
    {
172
      if (old == old_best)                /* It has _replaced_ the old optimal route */
173
        {
174
          r = new;                        /* Find new optimal route and announce it */
175
          for(s=net->routes; s; s=s->next)
176
            if (rte_better(s, r))
177
              r = s;
178
          rte_announce(net, r, old_best);
179
          if (r)                        /* Re-link the new optimal route */
180
            {
181
              k = &net->routes;
182
              while (s = *k)
183
                {
184
                  if (s == r)
185
                    {
186
                      *k = r->next;
187
                      break;
188
                    }
189
                  k = &r->next;
190
                }
191
              r->next = net->routes;
192
              net->routes = r;
193
            }
194
        }
195
      if (new)                                /* Link in the new non-optimal route */
196
        {
197
          new->next = old_best->next;
198
          old_best->next = new;
199
        }
200
    }
201
  if (old)
202
    {
203
      if (p->rte_remove)
204
        p->rte_remove(net, old);
205
      rte_free(old);
206
    }
207
  if (new)
208
    {
209
      new->lastmod = now;
210
      if (p->rte_insert)
211
        p->rte_insert(net, new);
212
    }
213
}
214

    
215
void
216
rte_discard(rte *old)                        /* Non-filtered route deletion, used during garbage collection */
217
{
218
  rte_update(old->net, old->attrs->proto, NULL);
219
}
220

    
221
void
222
rte_dump(rte *e)
223
{
224
  net *n = e->net;
225
  if (n)
226
    debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
227
  else
228
    debug("??? ");
229
  debug("PF=%02x pref=%d lm=%d ", e->pflags, e->pref, now-e->lastmod);
230
  rta_dump(e->attrs);
231
  if (e->flags & REF_CHOSEN)
232
    debug(" [*]");
233
  debug("\n");
234
}
235

    
236
void
237
rt_dump(rtable *t)
238
{
239
  rte *e;
240
  net *n;
241

    
242
  debug("Dump of routing table <%s>\n", t->name);
243
  while (t)
244
    {
245
      debug("Routes for TOS %02x:\n", t->tos);
246
      FIB_WALK(&t->fib, fn)
247
        {
248
          n = (net *) fn;
249
          for(e=n->routes; e; e=e->next)
250
            rte_dump(e);
251
        }
252
      FIB_WALK_END;
253
      t = t->sibling;
254
    }
255
  debug("\n");
256
}
257

    
258
void
259
rt_dump_all(void)
260
{
261
  rt_dump(&master_table);
262
}
263

    
264
void
265
rt_init(void)
266
{
267
  rta_init();
268
  rt_setup(&master_table, "master");
269
  rte_slab = sl_new(&root_pool, sizeof(rte));
270
}