[thirdparty/bird.git] / nest / rt-table.c

/*
 *	BIRD -- Routing Table
 *
 *	(c) 1998--1999 Martin Mares <mj@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include <string.h>

#define LOCAL_DEBUG

#include "nest/bird.h"
#include "nest/route.h"
#include "nest/protocol.h"
#include "nest/cli.h"
#include "nest/iface.h"
#include "lib/resource.h"
#include "lib/event.h"
#include "lib/string.h"
#include "conf/conf.h"
#include "filter/filter.h"

static slab *rte_slab;
static linpool *rte_update_pool;

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

static pool *rt_table_pool;
static list routing_tables;
static event *rt_gc_event;
static bird_clock_t rt_last_gc;
static int rt_gc_counter;

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

  N->flags = 0;
  n->routes = NULL;
}

void
rt_setup(pool *p, rtable *t, char *name)
{
  bzero(t, sizeof(*t));
  fib_init(&t->fib, p, sizeof(net), 0, rte_init);
  t->name = name;
  init_list(&t->hooks);
}

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;
  e->flags = 0;
  e->pref = a->proto->preference;
  return e;
}

rte *
rte_do_cow(rte *r)
{
  rte *e = sl_alloc(rte_slab);

  memcpy(e, r, sizeof(rte));
  e->attrs = rta_clone(r->attrs);
  e->flags = 0;
  return e;
}

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

  if (!old)
    return 1;
  if (new->pref > old->pref)
    return 1;
  if (new->pref < old->pref)
    return 0;
  if (new->attrs->proto->proto != old->attrs->proto->proto)
    bug("Different protocols, but identical preferences => oops");	/* FIXME */
  if (better = new->attrs->proto->rte_better)
    return better(new, old);
  return 0;
}

static inline void
do_rte_announce(struct announce_hook *a, net *net, rte *new, rte *old, ea_list *tmpa)
{
  struct proto *p = a->proto;
  rte *new0 = new;
  rte *old0 = old;

  if (new)
    {
      int ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0;
      if (ok < 0 ||
	  (!ok && (p->out_filter == FILTER_REJECT ||
		   p->out_filter && f_run(p->out_filter, &new, &tmpa, rte_update_pool) > F_MODIFY)
	  )
	 )
	new = NULL;
    }
  if (old && p->out_filter)
    {
      /* FIXME: Do we really need to filter old routes? */
      if (p->out_filter == FILTER_REJECT)
	old = NULL;
      else
	{
	  ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
	  if (f_run(p->out_filter, &old, &tmpb, rte_update_pool) > F_MODIFY)
	    old = NULL;
	}
    }
  if (new || old)
    p->rt_notify(p, net, new, old, tmpa);
  if (new && new != new0)	/* Discard temporary rte's */
    rte_free(new);
  if (old && old != old0)
    rte_free(old);
}

static void
rte_announce(rtable *tab, net *net, rte *new, rte *old, ea_list *tmpa)
{
  struct announce_hook *a;

  WALK_LIST(a, tab->hooks)
    {
      ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
      do_rte_announce(a, net, new, old, tmpa);
    }
}

void
rt_feed_baby(struct proto *p)
{
  struct announce_hook *h;

  if (!p->ahooks)
    return;
  debug("Announcing routes to new protocol %s\n", p->name);
  for(h=p->ahooks; h; h=h->next)
    {
      rtable *t = h->table;
      FIB_WALK(&t->fib, fn)
	{
	  net *n = (net *) fn;
	  rte *e;
	  for(e=n->routes; e; e=e->next)
	    {
	      struct proto *q = e->attrs->proto;
	      ea_list *tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
	      do_rte_announce(h, n, e, NULL, tmpa);
	      lp_flush(rte_update_pool);
	    }
	}
      FIB_WALK_END;
    }
}

static inline int
rte_validate(rte *e)
{
  int c;
  net *n = e->net;

  ASSERT(!ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))));
  if (n->n.pxlen)
    {
      c = ipa_classify(n->n.prefix);
      if (c < 0 || !(c & IADDR_HOST))
	{
	  if (!ipa_nonzero(n->n.prefix) && n->n.pxlen <= 1)
	    return 1;		/* Default route and half-default route is OK */
	  log(L_WARN "Ignoring bogus route %I/%d received from %I via %s",
	      n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
	  return 0;
	}
      if ((c & IADDR_SCOPE_MASK) == SCOPE_HOST)
	{
	  int s = e->attrs->source;
	  if (s != RTS_STATIC && s != RTS_DEVICE && s != RTS_STATIC_DEVICE)
	    {
	      log(L_WARN "Ignoring host scope route %I/%d received from %I via %s",
		  n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
	      return 0;
	    }
	}
    }
  return 1;
}

void
rte_free(rte *e)
{
  if (e->attrs->aflags & RTAF_CACHED)
    rta_free(e->attrs);
  sl_free(rte_slab, e);
}

static inline void
rte_free_quick(rte *e)
{
  rta_free(e->attrs);
  sl_free(rte_slab, e);
}

static void
rte_recalculate(rtable *table, net *net, struct proto *p, rte *new, ea_list *tmpa)
{
  rte *old_best = net->routes;
  rte *old = NULL;
  rte **k, *r, *s;

  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;
    }

  if (new && rte_better(new, old_best))	/* It's a new optimal route => announce and relink it */
    {
      rte_announce(table, net, new, old_best, tmpa);
      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;
	  rte_announce(table, net, r, old_best, tmpa);
	  if (r)			/* Re-link the new optimal route */
	    {
	      k = &net->routes;
	      while (s = *k)
		{
		  if (s == r)
		    {
		      *k = r->next;
		      break;
		    }
		  k = &s->next;
		}
	      r->next = net->routes;
	      net->routes = r;
	      if (!r && rt_gc_counter++ >= RT_GC_MIN_COUNT && rt_last_gc + RT_GC_MIN_TIME <= now)
		ev_schedule(rt_gc_event);
	    }
	}
      if (new)				/* Link in the new non-optimal route */
	{
	  new->next = old_best->next;
	  old_best->next = new;
	}
    }
  if (old)
    {
      if (p->rte_remove)
	p->rte_remove(net, old);
      rte_free_quick(old);
    }
  if (new)
    {
      new->lastmod = now;
      if (p->rte_insert)
	p->rte_insert(net, new);
    }
}

static int rte_update_nest_cnt;		/* Nesting counter to allow recursive updates */

static inline void
rte_update_lock(void)
{
  rte_update_nest_cnt++;
}

static inline void
rte_update_unlock(void)
{
  if (!--rte_update_nest_cnt)
    lp_flush(rte_update_pool);
}

void
rte_update(rtable *table, net *net, struct proto *p, rte *new)
{
  ea_list *tmpa = NULL;

  rte_update_lock();
  if (new)
    {
      if (!rte_validate(new) || p->in_filter == FILTER_REJECT)
	goto drop;
      if (p->make_tmp_attrs)
	tmpa = p->make_tmp_attrs(new, rte_update_pool);
      if (p->in_filter)
	{
	  int fr = f_run(p->in_filter, &new, &tmpa, rte_update_pool);
	  if (fr > F_MODIFY)
	    goto drop;
	  if (fr == F_MODIFY && p->store_tmp_attrs)
	    p->store_tmp_attrs(new, tmpa);
	}
      if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
	new->attrs = rta_lookup(new->attrs);
      new->flags |= REF_COW;
    }
  rte_recalculate(table, net, p, new, tmpa);
  rte_update_unlock();
  return;

drop:
  rte_free(new);
  rte_update_unlock();
}

void
rte_discard(rtable *t, rte *old)	/* Non-filtered route deletion, used during garbage collection */
{
  rte_update_lock();
  rte_recalculate(t, old->net, old->attrs->proto, NULL, NULL);
  rte_update_unlock();
}

void
rte_dump(rte *e)
{
  net *n = e->net;
  if (n)
    debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
  else
    debug("??? ");
  debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
  rta_dump(e->attrs);
  if (e->attrs->proto->proto->dump_attrs)
    e->attrs->proto->proto->dump_attrs(e);
  debug("\n");
}

void
rt_dump(rtable *t)
{
  rte *e;
  net *n;
  struct announce_hook *a;

  debug("Dump of routing table <%s>\n", t->name);
#ifdef DEBUGGING
  fib_check(&t->fib);
#endif
  FIB_WALK(&t->fib, fn)
    {
      n = (net *) fn;
      for(e=n->routes; e; e=e->next)
	rte_dump(e);
    }
  FIB_WALK_END;
  WALK_LIST(a, t->hooks)
    debug("\tAnnounces routes to protocol %s\n", a->proto->name);
  debug("\n");
}

void
rt_dump_all(void)
{
  rtable *t;

  WALK_LIST(t, routing_tables)
    rt_dump(t);
}

static int
rt_gc(void *unused)
{
  rtable *t;

  DBG("Entered routing table garbage collector after %d seconds and %d deletes\n", (int)(now - rt_last_gc), rt_gc_counter);
  rt_prune_all();
  rt_last_gc = now;
  rt_gc_counter = 0;
  return 0;
}

void
rt_init(void)
{
  rta_init();
  rt_table_pool = rp_new(&root_pool, "Routing tables");
  rte_update_pool = lp_new(rt_table_pool, 4080);
  rte_slab = sl_new(rt_table_pool, sizeof(rte));
  rt_last_gc = now;
  rt_gc_event = ev_new(rt_table_pool);
  rt_gc_event->hook = rt_gc;
  init_list(&routing_tables);
}

void
rt_prune(rtable *tab)
{
  struct fib_iterator fit;
  int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;

  DBG("Pruning route table %s\n", tab->name);
  FIB_ITERATE_INIT(&fit, &tab->fib);
again:
  FIB_ITERATE_START(&tab->fib, &fit, f)
    {
      net *n = (net *) f;
      rte *e;
      ncnt++;
    rescan:
      for (e=n->routes; e; e=e->next, rcnt++)
	if (e->attrs->proto->core_state != FS_HAPPY)
	  {
	    rte_discard(tab, e);
	    rdel++;
	    goto rescan;
	  }
      if (!n->routes)		/* Orphaned FIB entry? */
	{
	  FIB_ITERATE_PUT(&fit, f);
	  fib_delete(&tab->fib, f);
	  ndel++;
	  goto again;
	}
    }
  FIB_ITERATE_END(f);
  DBG("Pruned %d of %d routes and %d of %d networks\n", rcnt, rdel, ncnt, ndel);
}

void
rt_prune_all(void)
{
  rtable *t;

  WALK_LIST(t, routing_tables)
    rt_prune(t);
}

void
rt_preconfig(struct config *c)
{
  struct symbol *s = cf_find_symbol("master");
  struct rtable_config *r = cfg_allocz(sizeof(struct rtable_config));

  cf_define_symbol(s, SYM_TABLE, r);
  r->name = s->name;
  init_list(&c->tables);
  add_tail(&c->tables, &r->n);
  c->master_rtc = r;
}

void
rt_commit(struct config *c)
{
  struct rtable_config *r;

  WALK_LIST(r, c->tables)
    {
      rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
      rt_setup(rt_table_pool, t, r->name);
      add_tail(&routing_tables, &t->n);
      r->table = t;
    }
}

/*
 *  CLI commands
 */

static void
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d)
{
  byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH];
  byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
  rta *a = e->attrs;

  switch (a->dest)
    {
    case RTD_ROUTER:	bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
    case RTD_DEVICE:	bsprintf(via, "dev %s", a->iface->name); break;
    case RTD_BLACKHOLE:	bsprintf(via, "blackhole"); break;
    case RTD_UNREACHABLE:	bsprintf(via, "unreachable"); break;
    case RTD_PROHIBIT:	bsprintf(via, "prohibited"); break;
    default:		bsprintf(via, "???");
    }
  tm_format_reltime(tm, e->lastmod);
  if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
    bsprintf(from, " from %I", a->from);
  else
    from[0] = 0;
  if (a->proto->proto->get_route_info)
    a->proto->proto->get_route_info(e, info);
  else
    bsprintf(info, " (%d)", e->pref);
  cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
  if (d->verbose)
    {
      rta_show(c, a);
      if (a->proto->proto->show_route_data)
	a->proto->proto->show_route_data(e);
    }
}

static void
rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
{
  rte *e, *ee;
  byte ia[STD_ADDRESS_P_LENGTH+8];

  bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
  for(e=n->routes; e; e=e->next)
    {
      struct ea_list *tmpa = NULL;
      ee = e;
      rte_update_lock();		/* We use the update buffer for filtering */
      if (d->filter == FILTER_ACCEPT || f_run(d->filter, &ee, &tmpa, rte_update_pool) <= F_MODIFY)
	{
	  rt_show_rte(c, ia, e, d);
	  ia[0] = 0;
	}
      if (e != ee)
	rte_free(ee);
      rte_update_unlock();
    }
}

static void
rt_show_cont(struct cli *c)
{
  struct rt_show_data *d = c->rover;
  unsigned max = 1;			/* FIXME: After some debugging, increase to reasonable amount */
  struct fib *fib = &d->table->fib;
  struct fib_iterator *it = &d->fit;

  FIB_ITERATE_START(fib, it, f)
    {
      net *n = (net *) f;
      if (!max--)
	{
	  FIB_ITERATE_PUT(it, f);
	  return;
	}
      rt_show_net(c, n, d);
    }
  FIB_ITERATE_END(f);
  cli_printf(c, 0, "");
  c->cont = c->cleanup = NULL;
}

static void
rt_show_cleanup(struct cli *c)
{
  struct rt_show_data *d = c->rover;

  /* Unlink the iterator */
  fit_get(&d->table->fib, &d->fit);
}

void
rt_show(struct rt_show_data *d)
{
  struct rtable_config *tc;
  net *n;

  if (d->pxlen == 256)
    {
      FIB_ITERATE_INIT(&d->fit, &d->table->fib);
      this_cli->cont = rt_show_cont;
      this_cli->cleanup = rt_show_cleanup;
      this_cli->rover = d;
    }
  else
    {
      n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
      if (n)
	{
	  rt_show_net(this_cli, n, d);
	  cli_msg(0, "");
	}
      else
	cli_msg(8001, "Network not in table");
    }
}
Commit	Line	Data
62aa008a MM	1	/*
	2	* BIRD -- Routing Table
	3	*
730f2e2c	4	* (c) 1998--1999 Martin Mares <mj@ucw.cz>
62aa008a MM	5	*
	6	* Can be freely distributed and used under the terms of the GNU GPL.
	7	*/
	8
2326b001 MM	9	#include <string.h>
2326b001 MM	10
1a54b1c6 MM	11	#define LOCAL_DEBUG
1a54b1c6 MM	12
62aa008a MM	13	#include "nest/bird.h"
62aa008a MM	14	#include "nest/route.h"
2326b001	15	#include "nest/protocol.h"
730f2e2c MM	16	#include "nest/cli.h"
730f2e2c MM	17	#include "nest/iface.h"
2326b001	18	#include "lib/resource.h"
5996da6a	19	#include "lib/event.h"
730f2e2c	20	#include "lib/string.h"
0e02abfd	21	#include "conf/conf.h"
529c4149	22	#include "filter/filter.h"
2326b001	23
2326b001	24	static slab *rte_slab;
e2dc2f30	25	static linpool *rte_update_pool;
2326b001	26
5996da6a MM	27	#define RT_GC_MIN_TIME 5 /* FIXME: Make configurable */
	28	#define RT_GC_MIN_COUNT 100
	29
	30	static pool *rt_table_pool;
0e02abfd	31	static list routing_tables;
5996da6a MM	32	static event *rt_gc_event;
	33	static bird_clock_t rt_last_gc;
	34	static int rt_gc_counter;
	35
	36	static void
2326b001 MM	37	rte_init(struct fib_node *N)
	38	{
	39	net n = (net ) N;
	40
4c45595e	41	N->flags = 0;
2326b001 MM	42	n->routes = NULL;
	43	}
	44
	45	void
c10421d3	46	rt_setup(pool p, rtable t, char *name)
2326b001 MM	47	{
2326b001 MM	48	bzero(t, sizeof(*t));
d7975d26	49	fib_init(&t->fib, p, sizeof(net), 0, rte_init);
0cdbd397	50	t->name = name;
0e02abfd	51	init_list(&t->hooks);
2326b001 MM	52	}
2326b001 MM	53
2326b001 MM	54	rte *
	55	rte_find(net net, struct proto p)
	56	{
	57	rte *e = net->routes;
	58
	59	while (e && e->attrs->proto != p)
	60	e = e->next;
	61	return e;
	62	}
	63
	64	rte *
	65	rte_get_temp(rta *a)
	66	{
	67	rte *e = sl_alloc(rte_slab);
	68
	69	e->attrs = a;
0cdbd397	70	e->flags = 0;
2326b001	71	e->pref = a->proto->preference;
2326b001 MM	72	return e;
	73	}
	74
e2dc2f30 MM	75	rte *
	76	rte_do_cow(rte *r)
	77	{
	78	rte *e = sl_alloc(rte_slab);
	79
	80	memcpy(e, r, sizeof(rte));
	81	e->attrs = rta_clone(r->attrs);
	82	e->flags = 0;
	83	return e;
	84	}
	85
2326b001 MM	86	static int /* Actually better or at least as good as */
	87	rte_better(rte new, rte old)
	88	{
d9f330c5 MM	89	int (better)(rte , rte *);
d9f330c5 MM	90
2326b001 MM	91	if (!old)
	92	return 1;
	93	if (new->pref > old->pref)
	94	return 1;
	95	if (new->pref < old->pref)
	96	return 0;
739ebd8e MM	97	if (new->attrs->proto->proto != old->attrs->proto->proto)
739ebd8e MM	98	bug("Different protocols, but identical preferences => oops"); /* FIXME */
d9f330c5 MM	99	if (better = new->attrs->proto->rte_better)
	100	return better(new, old);
	101	return 0;
2326b001 MM	102	}
2326b001 MM	103
529c4149	104	static inline void
0e02abfd	105	do_rte_announce(struct announce_hook a, net net, rte new, rte old, ea_list *tmpa)
529c4149	106	{
0e02abfd	107	struct proto *p = a->proto;
e2dc2f30 MM	108	rte *new0 = new;
e2dc2f30 MM	109	rte *old0 = old;
7de45ba4	110
e2dc2f30	111	if (new)
529c4149	112	{
e2dc2f30 MM	113	int ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0;
	114	if (ok < 0 \|\|
	115	(!ok && (p->out_filter == FILTER_REJECT \|\|
	116	p->out_filter && f_run(p->out_filter, &new, &tmpa, rte_update_pool) > F_MODIFY)
	117	)
	118	)
529c4149 MM	119	new = NULL;
529c4149 MM	120	}
e2dc2f30 MM	121	if (old && p->out_filter)
	122	{
	123	/* FIXME: Do we really need to filter old routes? */
	124	if (p->out_filter == FILTER_REJECT)
	125	old = NULL;
	126	else
	127	{
	128	ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
	129	if (f_run(p->out_filter, &old, &tmpb, rte_update_pool) > F_MODIFY)
	130	old = NULL;
	131	}
	132	}
529c4149	133	if (new \|\| old)
bb027be1	134	p->rt_notify(p, net, new, old, tmpa);
e2dc2f30 MM	135	if (new && new != new0) /* Discard temporary rte's */
	136	rte_free(new);
	137	if (old && old != old0)
	138	rte_free(old);
529c4149 MM	139	}
529c4149 MM	140
e2dc2f30	141	static void
0e02abfd	142	rte_announce(rtable tab, net net, rte new, rte old, ea_list *tmpa)
2326b001	143	{
0e02abfd	144	struct announce_hook *a;
2326b001	145
0e02abfd	146	WALK_LIST(a, tab->hooks)
0a2e9d9f	147	{
8c943173	148	ASSERT(a->proto->core_state == FS_HAPPY \|\| a->proto->core_state == FS_FEEDING);
0e02abfd	149	do_rte_announce(a, net, new, old, tmpa);
0a2e9d9f	150	}
2326b001 MM	151	}
2326b001 MM	152
47b79306 MM	153	void
	154	rt_feed_baby(struct proto *p)
	155	{
0e02abfd	156	struct announce_hook *h;
47b79306	157
0e02abfd	158	if (!p->ahooks)
47b79306	159	return;
64011f89	160	debug("Announcing routes to new protocol %s\n", p->name);
0e02abfd	161	for(h=p->ahooks; h; h=h->next)
47b79306	162	{
0e02abfd MM	163	rtable *t = h->table;
0e02abfd MM	164	FIB_WALK(&t->fib, fn)
47b79306	165	{
0e02abfd MM	166	net n = (net ) fn;
	167	rte *e;
	168	for(e=n->routes; e; e=e->next)
	169	{
	170	struct proto *q = e->attrs->proto;
	171	ea_list *tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
	172	do_rte_announce(h, n, e, NULL, tmpa);
	173	lp_flush(rte_update_pool);
	174	}
47b79306	175	}
0e02abfd	176	FIB_WALK_END;
47b79306 MM	177	}
	178	}
	179
421838ff MM	180	static inline int
	181	rte_validate(rte *e)
	182	{
	183	int c;
	184	net *n = e->net;
	185
	186	ASSERT(!ipa_nonzero(ipa_and(n->n.prefix, ipa_not(ipa_mkmask(n->n.pxlen)))));
	187	if (n->n.pxlen)
	188	{
	189	c = ipa_classify(n->n.prefix);
	190	if (c < 0 \|\| !(c & IADDR_HOST))
	191	{
	192	if (!ipa_nonzero(n->n.prefix) && n->n.pxlen <= 1)
	193	return 1; /* Default route and half-default route is OK */
	194	log(L_WARN "Ignoring bogus route %I/%d received from %I via %s",
	195	n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
	196	return 0;
	197	}
	198	if ((c & IADDR_SCOPE_MASK) == SCOPE_HOST)
	199	{
	200	int s = e->attrs->source;
	201	if (s != RTS_STATIC && s != RTS_DEVICE && s != RTS_STATIC_DEVICE)
	202	{
	203	log(L_WARN "Ignoring host scope route %I/%d received from %I via %s",
	204	n->n.prefix, n->n.pxlen, e->attrs->from, e->attrs->proto->name);
	205	return 0;
	206	}
	207	}
	208	}
	209	return 1;
	210	}
	211
04925e90	212	void
2326b001	213	rte_free(rte *e)
04925e90 MM	214	{
	215	if (e->attrs->aflags & RTAF_CACHED)
	216	rta_free(e->attrs);
	217	sl_free(rte_slab, e);
	218	}
	219
	220	static inline void
	221	rte_free_quick(rte *e)
2326b001 MM	222	{
	223	rta_free(e->attrs);
	224	sl_free(rte_slab, e);
	225	}
	226
e2dc2f30	227	static void
0e02abfd	228	rte_recalculate(rtable table, net net, struct proto p, rte new, ea_list *tmpa)
2326b001 MM	229	{
	230	rte *old_best = net->routes;
	231	rte *old = NULL;
	232	rte *k, r, *s;
2326b001 MM	233
	234	k = &net->routes; /* Find and remove original route from the same protocol */
	235	while (old = *k)
	236	{
	237	if (old->attrs->proto == p)
	238	{
	239	*k = old->next;
	240	break;
	241	}
	242	k = &old->next;
	243	}
	244
0cdbd397	245	if (new && rte_better(new, old_best)) /* It's a new optimal route => announce and relink it */
2326b001	246	{
0e02abfd	247	rte_announce(table, net, new, old_best, tmpa);
2326b001 MM	248	new->next = net->routes;
	249	net->routes = new;
	250	}
	251	else
	252	{
	253	if (old == old_best) /* It has _replaced_ the old optimal route */
	254	{
	255	r = new; /* Find new optimal route and announce it */
	256	for(s=net->routes; s; s=s->next)
	257	if (rte_better(s, r))
	258	r = s;
0e02abfd	259	rte_announce(table, net, r, old_best, tmpa);
2326b001 MM	260	if (r) /* Re-link the new optimal route */
	261	{
	262	k = &net->routes;
	263	while (s = *k)
	264	{
	265	if (s == r)
	266	{
	267	*k = r->next;
	268	break;
	269	}
dafd580e	270	k = &s->next;
2326b001 MM	271	}
	272	r->next = net->routes;
	273	net->routes = r;
5996da6a MM	274	if (!r && rt_gc_counter++ >= RT_GC_MIN_COUNT && rt_last_gc + RT_GC_MIN_TIME <= now)
5996da6a MM	275	ev_schedule(rt_gc_event);
2326b001 MM	276	}
	277	}
	278	if (new) /* Link in the new non-optimal route */
	279	{
	280	new->next = old_best->next;
	281	old_best->next = new;
	282	}
	283	}
	284	if (old)
5b22683d MM	285	{
	286	if (p->rte_remove)
	287	p->rte_remove(net, old);
04925e90	288	rte_free_quick(old);
5b22683d	289	}
8ca8683c MM	290	if (new)
	291	{
	292	new->lastmod = now;
	293	if (p->rte_insert)
	294	p->rte_insert(net, new);
	295	}
5b22683d MM	296	}
5b22683d MM	297
e2dc2f30 MM	298	static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */
	299
	300	static inline void
	301	rte_update_lock(void)
	302	{
	303	rte_update_nest_cnt++;
	304	}
	305
	306	static inline void
	307	rte_update_unlock(void)
	308	{
	309	if (!--rte_update_nest_cnt)
	310	lp_flush(rte_update_pool);
	311	}
	312
	313	void
0e02abfd	314	rte_update(rtable table, net net, struct proto p, rte new)
e2dc2f30 MM	315	{
	316	ea_list *tmpa = NULL;
	317
	318	rte_update_lock();
	319	if (new)
	320	{
	321	if (!rte_validate(new) \|\| p->in_filter == FILTER_REJECT)
	322	goto drop;
	323	if (p->make_tmp_attrs)
	324	tmpa = p->make_tmp_attrs(new, rte_update_pool);
	325	if (p->in_filter)
	326	{
	327	int fr = f_run(p->in_filter, &new, &tmpa, rte_update_pool);
	328	if (fr > F_MODIFY)
	329	goto drop;
	330	if (fr == F_MODIFY && p->store_tmp_attrs)
	331	p->store_tmp_attrs(new, tmpa);
	332	}
	333	if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
	334	new->attrs = rta_lookup(new->attrs);
	335	new->flags \|= REF_COW;
	336	}
0e02abfd	337	rte_recalculate(table, net, p, new, tmpa);
e2dc2f30 MM	338	rte_update_unlock();
	339	return;
	340
	341	drop:
	342	rte_free(new);
	343	rte_update_unlock();
	344	}
	345
5b22683d	346	void
0e02abfd	347	rte_discard(rtable t, rte old) /* Non-filtered route deletion, used during garbage collection */
5b22683d	348	{
e2dc2f30	349	rte_update_lock();
0e02abfd	350	rte_recalculate(t, old->net, old->attrs->proto, NULL, NULL);
e2dc2f30	351	rte_update_unlock();
2326b001 MM	352	}
	353
	354	void
a0762910	355	rte_dump(rte *e)
2326b001	356	{
a0762910	357	net *n = e->net;
0cdbd397	358	if (n)
962ba482	359	debug("%1I/%2d ", n->n.prefix, n->n.pxlen);
a0762910 MM	360	else
a0762910 MM	361	debug("??? ");
c10421d3	362	debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
0cdbd397	363	rta_dump(e->attrs);
c10421d3 MM	364	if (e->attrs->proto->proto->dump_attrs)
c10421d3 MM	365	e->attrs->proto->proto->dump_attrs(e);
0cdbd397	366	debug("\n");
2326b001	367	}
62aa008a	368
2326b001 MM	369	void
	370	rt_dump(rtable *t)
	371	{
0cdbd397 MM	372	rte *e;
0cdbd397 MM	373	net *n;
0e02abfd	374	struct announce_hook *a;
0cdbd397 MM	375
0cdbd397 MM	376	debug("Dump of routing table <%s>\n", t->name);
e440395d	377	#ifdef DEBUGGING
08e2d625	378	fib_check(&t->fib);
e440395d	379	#endif
08e2d625 MM	380	FIB_WALK(&t->fib, fn)
	381	{
	382	n = (net *) fn;
	383	for(e=n->routes; e; e=e->next)
	384	rte_dump(e);
0cdbd397	385	}
08e2d625	386	FIB_WALK_END;
0e02abfd MM	387	WALK_LIST(a, t->hooks)
0e02abfd MM	388	debug("\tAnnounces routes to protocol %s\n", a->proto->name);
0cdbd397	389	debug("\n");
2326b001	390	}
62aa008a	391
6d45cf21 MM	392	void
	393	rt_dump_all(void)
	394	{
0e02abfd MM	395	rtable *t;
	396
	397	WALK_LIST(t, routing_tables)
	398	rt_dump(t);
6d45cf21 MM	399	}
6d45cf21 MM	400
0d70292d	401	static int
5996da6a MM	402	rt_gc(void *unused)
5996da6a MM	403	{
0e02abfd MM	404	rtable *t;
0e02abfd MM	405
5996da6a	406	DBG("Entered routing table garbage collector after %d seconds and %d deletes\n", (int)(now - rt_last_gc), rt_gc_counter);
0e02abfd	407	rt_prune_all();
5996da6a MM	408	rt_last_gc = now;
5996da6a MM	409	rt_gc_counter = 0;
0d70292d	410	return 0;
5996da6a MM	411	}
5996da6a MM	412
2326b001 MM	413	void
	414	rt_init(void)
	415	{
	416	rta_init();
5996da6a	417	rt_table_pool = rp_new(&root_pool, "Routing tables");
e2dc2f30	418	rte_update_pool = lp_new(rt_table_pool, 4080);
5996da6a MM	419	rte_slab = sl_new(rt_table_pool, sizeof(rte));
	420	rt_last_gc = now;
	421	rt_gc_event = ev_new(rt_table_pool);
	422	rt_gc_event->hook = rt_gc;
0e02abfd	423	init_list(&routing_tables);
2326b001	424	}
1a54b1c6 MM	425
	426	void
	427	rt_prune(rtable *tab)
	428	{
	429	struct fib_iterator fit;
5996da6a	430	int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
1a54b1c6 MM	431
1a54b1c6 MM	432	DBG("Pruning route table %s\n", tab->name);
08e2d625 MM	433	FIB_ITERATE_INIT(&fit, &tab->fib);
	434	again:
	435	FIB_ITERATE_START(&tab->fib, &fit, f)
1a54b1c6	436	{
08e2d625 MM	437	net n = (net ) f;
	438	rte *e;
	439	ncnt++;
	440	rescan:
	441	for (e=n->routes; e; e=e->next, rcnt++)
	442	if (e->attrs->proto->core_state != FS_HAPPY)
	443	{
0e02abfd	444	rte_discard(tab, e);
08e2d625 MM	445	rdel++;
	446	goto rescan;
	447	}
	448	if (!n->routes) /* Orphaned FIB entry? */
1a54b1c6	449	{
08e2d625 MM	450	FIB_ITERATE_PUT(&fit, f);
	451	fib_delete(&tab->fib, f);
	452	ndel++;
	453	goto again;
1a54b1c6	454	}
1a54b1c6	455	}
08e2d625	456	FIB_ITERATE_END(f);
5996da6a	457	DBG("Pruned %d of %d routes and %d of %d networks\n", rcnt, rdel, ncnt, ndel);
1a54b1c6	458	}
0e02abfd MM	459
	460	void
	461	rt_prune_all(void)
	462	{
	463	rtable *t;
	464
	465	WALK_LIST(t, routing_tables)
	466	rt_prune(t);
	467	}
	468
	469	void
	470	rt_preconfig(struct config *c)
	471	{
	472	struct symbol *s = cf_find_symbol("master");
	473	struct rtable_config *r = cfg_allocz(sizeof(struct rtable_config));
	474
	475	cf_define_symbol(s, SYM_TABLE, r);
	476	r->name = s->name;
	477	init_list(&c->tables);
	478	add_tail(&c->tables, &r->n);
	479	c->master_rtc = r;
	480	}
	481
	482	void
	483	rt_commit(struct config *c)
	484	{
	485	struct rtable_config *r;
	486
	487	WALK_LIST(r, c->tables)
	488	{
	489	rtable *t = mb_alloc(rt_table_pool, sizeof(struct rtable));
	490	rt_setup(rt_table_pool, t, r->name);
	491	add_tail(&routing_tables, &t->n);
	492	r->table = t;
	493	}
	494	}
730f2e2c MM	495
	496	/*
	497	* CLI commands
	498	*/
	499
	500	static void
	501	rt_show_rte(struct cli c, byte ia, rte e, struct rt_show_data d)
	502	{
	503	byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH];
	504	byte tm[TM_RELTIME_BUFFER_SIZE], info[256];
	505	rta *a = e->attrs;
	506
	507	switch (a->dest)
	508	{
	509	case RTD_ROUTER: bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
	510	case RTD_DEVICE: bsprintf(via, "dev %s", a->iface->name); break;
	511	case RTD_BLACKHOLE: bsprintf(via, "blackhole"); break;
	512	case RTD_UNREACHABLE: bsprintf(via, "unreachable"); break;
	513	case RTD_PROHIBIT: bsprintf(via, "prohibited"); break;
	514	default: bsprintf(via, "???");
	515	}
	516	tm_format_reltime(tm, e->lastmod);
	517	if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
	518	bsprintf(from, " from %I", a->from);
	519	else
	520	from[0] = 0;
	521	if (a->proto->proto->get_route_info)
	522	a->proto->proto->get_route_info(e, info);
	523	else
	524	bsprintf(info, " (%d)", e->pref);
	525	cli_printf(c, -1007, "%-18s %s [%s %s%s]%s", ia, via, a->proto->name, tm, from, info);
	526	if (d->verbose)
	527	{
	528	rta_show(c, a);
	529	if (a->proto->proto->show_route_data)
	530	a->proto->proto->show_route_data(e);
	531	}
	532	}
	533
	534	static void
	535	rt_show_net(struct cli c, net n, struct rt_show_data *d)
	536	{
	537	rte e, ee;
	538	byte ia[STD_ADDRESS_P_LENGTH+8];
	539
	540	bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
	541	for(e=n->routes; e; e=e->next)
	542	{
	543	struct ea_list *tmpa = NULL;
	544	ee = e;
	545	rte_update_lock(); /* We use the update buffer for filtering */
	546	if (d->filter == FILTER_ACCEPT \|\| f_run(d->filter, &ee, &tmpa, rte_update_pool) <= F_MODIFY)
	547	{
	548	rt_show_rte(c, ia, e, d);
	549	ia[0] = 0;
	550	}
	551	if (e != ee)
	552	rte_free(ee);
	553	rte_update_unlock();
	554	}
	555	}
	556
	557	static void
	558	rt_show_cont(struct cli *c)
559	{
560	struct rt_show_data *d = c->rover;
561	unsigned max = 1; /* FIXME: After some debugging, increase to reasonable amount */
562	struct fib *fib = &d->table->fib;
563	struct fib_iterator *it = &d->fit;
564
565	FIB_ITERATE_START(fib, it, f)
566	{
567	net n = (net ) f;
568	if (!max--)
569	{
570	FIB_ITERATE_PUT(it, f);
571	return;
572	}
573	rt_show_net(c, n, d);
574	}
575	FIB_ITERATE_END(f);
576	cli_printf(c, 0, "");
577	c->cont = c->cleanup = NULL;
578	}
579
580	static void
581	rt_show_cleanup(struct cli *c)
582	{
583	struct rt_show_data *d = c->rover;
584
585	/* Unlink the iterator */
586	fit_get(&d->table->fib, &d->fit);
587	}
588
589	void
590	rt_show(struct rt_show_data *d)
591	{
592	struct rtable_config *tc;
593	net *n;
594
595	if (d->pxlen == 256)
596	{
597	FIB_ITERATE_INIT(&d->fit, &d->table->fib);
598	this_cli->cont = rt_show_cont;
599	this_cli->cleanup = rt_show_cleanup;
600	this_cli->rover = d;
601	}
602	else
603	{
604	n = fib_find(&d->table->fib, &d->prefix, d->pxlen);
605	if (n)
606	{
607	rt_show_net(this_cli, n, d);
608	cli_msg(0, "");
609	}
610	else
611	cli_msg(8001, "Network not in table");
612	}
613	}