rt-table.c 5.56 KB
Newer Older
1 2 3 4 5 6 7 8
/*
 *	BIRD -- Routing Table
 *
 *	(c) 1998 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

9 10
#include <string.h>

11 12
#define LOCAL_DEBUG

13 14
#include "nest/bird.h"
#include "nest/route.h"
15 16 17 18 19 20 21 22 23 24 25
#include "nest/protocol.h"
#include "lib/resource.h"

rtable master_table;
static slab *rte_slab;

void
rte_init(struct fib_node *N)
{
  net *n = (net *) N;

26
  N->flags = 0;
27 28 29 30 31 32 33 34
  n->routes = NULL;
}

void
rt_setup(rtable *t, char *name)
{
  bzero(t, sizeof(*t));
  fib_init(&t->fib, &root_pool, sizeof(rte), 0, rte_init);
35
  t->name = name;
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
}

net *
net_find(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
{
  while (tab && tab->tos != tos)
    tab = tab->sibling;
  if (!tab)
    return NULL;
  return (net *) fib_find(&tab->fib, &mask, len);
}

net *
net_get(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
{
  rtable *t = tab;

  while (t && t->tos != tos)
    t = t->sibling;
  if (!t)
    {
      while (tab->sibling)
	tab = tab->sibling;
      t = mb_alloc(&root_pool, sizeof(rtable));
      rt_setup(t, NULL);
      tab->sibling = t;
      t->tos = tos;
    }
  return (net *) fib_get(&t->fib, &mask, len);
}

rte *
rte_find(net *net, struct proto *p)
{
  rte *e = net->routes;

  while (e && e->attrs->proto != p)
    e = e->next;
  return e;
}

rte *
rte_get_temp(rta *a)
{
  rte *e = sl_alloc(rte_slab);

  e->attrs = a;
83
  e->flags = 0;
84 85 86 87 88 89 90
  e->pref = a->proto->preference;
  return e;
}

static int				/* Actually better or at least as good as */
rte_better(rte *new, rte *old)
{
91 92
  int (*better)(rte *, rte *);

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

void
110
rte_announce(net *net, rte *new, rte *old)
111 112 113 114
{
  struct proto *p;

  WALK_LIST(p, proto_list)
115 116
    if (p->rt_notify)
      p->rt_notify(p, net, new, old);
117 118
}

119 120 121 122 123 124 125
void
rt_feed_baby(struct proto *p)
{
  rtable *t = &master_table;

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

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

static inline void
rte_free_quick(rte *e)
151 152 153 154 155 156
{
  rta_free(e->attrs);
  sl_free(rte_slab, e);
}

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

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

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

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

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

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

249 250 251
void
rt_dump(rtable *t)
{
252 253 254 255 256 257 258
  rte *e;
  net *n;

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

274 275 276
void
rt_dump_all(void)
{
277
  rt_dump(&master_table);
278 279
}

280 281 282 283 284 285 286
void
rt_init(void)
{
  rta_init();
  rt_setup(&master_table, "master");
  rte_slab = sl_new(&root_pool, sizeof(rte));
}
287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316

void
rt_prune(rtable *tab)
{
  struct fib_iterator fit;
  int cnt = 0;

  DBG("Pruning route table %s\n", tab->name);
  while (tab)
    {
      FIB_ITERATE_INIT(&fit, &tab->fib);
    again:
      FIB_ITERATE_START(&tab->fib, &fit, f)
	{
	  net *n = (net *) f;
	  rte *e;
	  for (e=n->routes; e; e=e->next)
	    if (e->attrs->proto->core_state != FS_HAPPY)
	      {
		FIB_ITERATE_PUT(&fit, f);
		rte_discard(e);
		cnt++;
		goto again;
	      }
	}
      FIB_ITERATE_END(f);
      tab = tab->sibling;
    }
  DBG("Pruned %d routes\n", cnt);
}