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

Martin Mareš's avatar
Martin Mareš committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22
/**
 * DOC: Neighbor cache
 *
 * Most routing protocols need to associate their internal state data with
 * neighboring routers, check whether an address given as the next hop
 * attribute of a route is really an address of a directly connected host
 * and which interface is it connected through. Also, they often need to
 * be notified when a neighbor ceases to exist or when their long awaited
 * neighbor becomes connected. The neighbor cache is there to solve all
 * these problems.
 *
 * The neighbor cache maintains a collection of neighbor entries. Each
 * entry represents one IP address corresponding to either our directly
 * connected neighbor or our own end of the link (when the scope of the
Martin Mareš's avatar
Martin Mareš committed
23
 * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a
Martin Mareš's avatar
Martin Mareš committed
24 25 26
 * single protocol.
 *
 * Active entries represent known neighbors and are stored in a hash
Martin Mareš's avatar
Martin Mareš committed
27
 * table (to allow fast retrieval based on the IP address of the node) and
Martin Mareš's avatar
Martin Mareš committed
28 29 30 31 32
 * two linked lists: one global and one per-interface (allowing quick
 * processing of interface change events). Inactive entries exist only
 * when the protocol has explicitly requested it via the %NEF_STICKY
 * flag because it wishes to be notified when the node will again become
 * a neighbor. Such entries are enqueued in a special list which is walked
Martin Mareš's avatar
Martin Mareš committed
33
 * whenever an interface changes its state to up.
Martin Mareš's avatar
Martin Mareš committed
34 35 36 37 38 39
 *
 * When a neighbor event occurs (a neighbor gets disconnected or a sticky
 * inactive neighbor becomes connected), the protocol hook neigh_notify()
 * is called to advertise the change.
 */

40
#undef LOCAL_DEBUG
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

#include "nest/bird.h"
#include "nest/iface.h"
#include "nest/protocol.h"
#include "lib/resource.h"

#define NEIGH_HASH_SIZE 256

static slab *neigh_slab;
static list sticky_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];

static inline unsigned int
neigh_hash(struct proto *p, ip_addr *a)
{
  return (p->hash_key ^ ipa_hash(*a)) & (NEIGH_HASH_SIZE-1);
}

58
static int
59 60 61 62 63
if_connected(ip_addr *a, struct iface *i) /* -1=error, 1=match, 0=no match */
{
  struct ifa *b;

  if (!(i->flags & IF_UP))
64
    return -1;
65 66 67
  WALK_LIST(b, i->addrs)
    {
      if (ipa_equal(*a, b->ip))
68
	return SCOPE_HOST;
69 70 71
      if (b->flags & IA_UNNUMBERED)
	{
	  if (ipa_equal(*a, b->opposite))
72
	    return b->scope;
73 74 75 76 77 78 79 80
	}
      else
	{
	  if (ipa_in_net(*a, b->prefix, b->pxlen))
	    {
	      if (ipa_equal(*a, b->prefix) ||	/* Network address */
		  ipa_equal(*a, b->brd))	/* Broadcast */
		return -1;
81
	      return b->scope;
82 83 84
	    }
	}
      }
85
  return -1;
86 87
}

Martin Mareš's avatar
Martin Mareš committed
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
/**
 * neigh_find - find or create a neighbor entry.
 * @p: protocol which asks for the entry.
 * @a: pointer to IP address of the node to be searched for.
 * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
 *
 * Search the neighbor cache for a node with given IP address. If
 * it's found, a pointer to the neighbor entry is returned. If no
 * such entry exists and the node is directly connected on
 * one of our active interfaces, a new entry is created and returned
 * to the caller with protocol-dependent fields initialized to zero.
 * If the node is not connected directly or *@a is not a valid unicast
 * IP address, neigh_find() returns %NULL.
 */

103 104
neighbor *
neigh_find(struct proto *p, ip_addr *a, unsigned flags)
105 106 107 108 109 110
{
  return neigh_find2(p, a, NULL, flags);
}

neighbor *
neigh_find2(struct proto *p, ip_addr *a, unsigned flags)
111 112
{
  neighbor *n;
113
  int class, scope = SCOPE_HOST;
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
  unsigned int h = neigh_hash(p, a);
  struct iface *i, *j;

  WALK_LIST(n, neigh_hash_table[h])	/* Search the cache */
    if (n->proto == p && ipa_equal(*a, n->addr))
      return n;

  class = ipa_classify(*a);
  if (class < 0)			/* Invalid address */
    return NULL;
  if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
      !(class & IADDR_HOST))
    return NULL;			/* Bad scope or a somecast */

  j = NULL;
  WALK_LIST(i, iface_list)
130
    if ((scope = if_connected(a, i)) >= 0)
131
      {
132 133
	j = i;
	break;
134 135 136 137 138 139 140 141 142 143 144 145 146
      }
  if (!j && !(flags & NEF_STICKY))
    return NULL;

  n = sl_alloc(neigh_slab);
  n->addr = *a;
  n->iface = j;
  if (j)
    {
      add_tail(&neigh_hash_table[h], &n->n);
      add_tail(&j->neighbors, &n->if_n);
    }
  else
147 148 149 150
    {
      add_tail(&sticky_neigh_list, &n->n);
      scope = 0;
    }
151 152 153 154
  n->proto = p;
  n->data = NULL;
  n->aux = 0;
  n->flags = flags;
155
  n->scope = scope;
156 157 158
  return n;
}

Martin Mareš's avatar
Martin Mareš committed
159 160 161 162 163 164 165
/**
 * neigh_dump - dump specified neighbor entry.
 * @n: the entry to dump
 *
 * This functions dumps the contents of a given neighbor entry
 * to debug output.
 */
166 167 168 169 170 171 172 173
void
neigh_dump(neighbor *n)
{
  debug("%p %I ", n, n->addr);
  if (n->iface)
    debug("%s ", n->iface->name);
  else
    debug("[] ");
174
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
175 176 177 178 179
  if (n->flags & NEF_STICKY)
    debug(" STICKY");
  debug("\n");
}

Martin Mareš's avatar
Martin Mareš committed
180 181 182 183 184 185
/**
 * neigh_dump_all - dump all neighbor entries.
 *
 * This function dumps the contents of the neighbor cache to
 * debug output.
 */
186 187 188 189 190 191 192 193 194 195
void
neigh_dump_all(void)
{
  neighbor *n;
  int i;

  debug("Known neighbors:\n");
  WALK_LIST(n, sticky_neigh_list)
    neigh_dump(n);
  for(i=0; i<NEIGH_HASH_SIZE; i++)
196 197
    WALK_LIST(n, neigh_hash_table[i])
      neigh_dump(n);
198 199 200
  debug("\n");
}

Martin Mareš's avatar
Martin Mareš committed
201 202 203 204 205 206 207 208 209
/**
 * neigh_if_up: notify neighbor cache about interface up event
 * @i: interface in question
 *
 * Tell the neighbor cache that a new interface became up.
 *
 * The neighbor cache wakes up all inactive sticky neighbors with
 * addresses belonging to prefixes of the interface @i.
 */
210 211 212 213
void
neigh_if_up(struct iface *i)
{
  neighbor *n, *next;
214
  int scope;
215 216

  WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
217
    if ((scope = if_connected(&n->addr, i)) >= 0)
218 219
      {
	n->iface = i;
220
	n->scope = scope;
221 222 223 224 225 226 227 228 229
	add_tail(&i->neighbors, &n->if_n);
	rem_node(&n->n);
	add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
	DBG("Waking up sticky neighbor %I\n", n->addr);
	if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
	  n->proto->neigh_notify(n);
      }
}

Martin Mareš's avatar
Martin Mareš committed
230 231 232 233 234 235 236 237 238
/**
 * neigh_if_down - notify neighbor cache about interface down event
 * @i: the interface in question
 *
 * Notify the neighbor cache that an interface has ceased to exist.
 *
 * It causes all entries belonging to neighbors connected to this interface
 * to be flushed.
 */
239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
void
neigh_if_down(struct iface *i)
{
  node *x, *y;

  WALK_LIST_DELSAFE(x, y, i->neighbors)
    {
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
      DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
      rem_node(&n->if_n);
      n->iface = NULL;
      if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
	n->proto->neigh_notify(n);
      rem_node(&n->n);
      if (n->flags & NEF_STICKY)
	add_tail(&sticky_neigh_list, &n->n);
      else
	sl_free(neigh_slab, n);
    }
}

260 261 262
static inline void
neigh_prune_one(neighbor *n)
{
263
  if (n->proto->proto_state != PS_DOWN)
264 265 266 267 268 269 270
    return;
  rem_node(&n->n);
  if (n->iface)
    rem_node(&n->if_n);
  sl_free(neigh_slab, n);
}

Martin Mareš's avatar
Martin Mareš committed
271 272 273 274 275 276 277
/**
 * neigh_prune - prune neighbor cache
 *
 * neigh_prune() examines all neighbor entries cached and removes those
 * corresponding to inactive protocols. It's called whenever a protocol
 * is shut down to get rid of all its heritage.
 */
278 279 280 281 282 283 284 285 286 287
void
neigh_prune(void)
{
  neighbor *n;
  node *m;
  int i;

  DBG("Pruning neighbors\n");
  for(i=0; i<NEIGH_HASH_SIZE; i++)
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
288 289 290
      neigh_prune_one(n);
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
    neigh_prune_one(n);
291 292
}

Martin Mareš's avatar
Martin Mareš committed
293 294 295 296 297 298 299
/**
 * neigh_init - initialize the neighbor cache.
 * @if_pool: resource pool to be used for neighbor entries.
 *
 * This function is called during BIRD startup to initialize
 * the neighbor cache module.
 */
300 301 302 303 304 305 306 307 308 309
void
neigh_init(pool *if_pool)
{
  int i;

  neigh_slab = sl_new(if_pool, sizeof(neighbor));
  init_list(&sticky_neigh_list);
  for(i=0; i<NEIGH_HASH_SIZE; i++)
    init_list(&neigh_hash_table[i]);
}