Statistics
| Branch: | Revision:

iof-bird-daemon / nest / neighbor.c @ d47c3d64

History | View | Annotate | Download (10.3 KB)

1 85053fce Martin Mares
/*
2
 *        BIRD -- Neighbor Cache
3
 *
4
 *        (c) 1998--2000 Martin Mares <mj@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8
9 1f495723 Martin Mares
/**
10
 * DOC: Neighbor cache
11
 *
12
 * Most routing protocols need to associate their internal state data with
13
 * neighboring routers, check whether an address given as the next hop
14
 * attribute of a route is really an address of a directly connected host
15
 * and which interface is it connected through. Also, they often need to
16
 * be notified when a neighbor ceases to exist or when their long awaited
17
 * neighbor becomes connected. The neighbor cache is there to solve all
18
 * these problems.
19
 *
20
 * The neighbor cache maintains a collection of neighbor entries. Each
21
 * entry represents one IP address corresponding to either our directly
22
 * connected neighbor or our own end of the link (when the scope of the
23 58f7d004 Martin Mares
 * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a
24 1f495723 Martin Mares
 * single protocol.
25
 *
26
 * Active entries represent known neighbors and are stored in a hash
27 58f7d004 Martin Mares
 * table (to allow fast retrieval based on the IP address of the node) and
28 1f495723 Martin Mares
 * two linked lists: one global and one per-interface (allowing quick
29
 * processing of interface change events). Inactive entries exist only
30
 * when the protocol has explicitly requested it via the %NEF_STICKY
31
 * flag because it wishes to be notified when the node will again become
32
 * a neighbor. Such entries are enqueued in a special list which is walked
33 58f7d004 Martin Mares
 * whenever an interface changes its state to up.
34 1f495723 Martin Mares
 *
35
 * When a neighbor event occurs (a neighbor gets disconnected or a sticky
36
 * inactive neighbor becomes connected), the protocol hook neigh_notify()
37
 * is called to advertise the change.
38
 */
39
40 6b9fa320 Martin Mares
#undef LOCAL_DEBUG
41 85053fce Martin Mares
42
#include "nest/bird.h"
43
#include "nest/iface.h"
44
#include "nest/protocol.h"
45
#include "lib/resource.h"
46
47
#define NEIGH_HASH_SIZE 256
48 04632fd7 Ondrej Zajicek (work)
#define NEIGH_HASH_OFFSET 24
49 85053fce Martin Mares
50
static slab *neigh_slab;
51
static list sticky_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];
52
53 ae80a2de Pavel Tvrdík
static inline uint
54 85053fce Martin Mares
neigh_hash(struct proto *p, ip_addr *a)
55
{
56 04632fd7 Ondrej Zajicek (work)
  return (p->hash_key ^ ipa_hash(*a)) >> NEIGH_HASH_OFFSET;
57 85053fce Martin Mares
}
58
59 200accf3 Martin Mares
static int
60 2d0b7e24 Ondrej Zajicek
if_connected(ip_addr *a, struct iface *i, struct ifa **ap)
61 85053fce Martin Mares
{
62
  struct ifa *b;
63
64
  if (!(i->flags & IF_UP))
65 2d0b7e24 Ondrej Zajicek
  {
66
    *ap = NULL;
67 0f32f2a6 Martin Mares
    return -1;
68 2d0b7e24 Ondrej Zajicek
  }
69
70 85053fce Martin Mares
  WALK_LIST(b, i->addrs)
71
    {
72 2d0b7e24 Ondrej Zajicek
      *ap = b;
73
74 85053fce Martin Mares
      if (ipa_equal(*a, b->ip))
75 0f32f2a6 Martin Mares
        return SCOPE_HOST;
76 52a43ae3 Ondrej Zajicek
      if (b->flags & IA_PEER)
77 85053fce Martin Mares
        {
78
          if (ipa_equal(*a, b->opposite))
79 0f32f2a6 Martin Mares
            return b->scope;
80 85053fce Martin Mares
        }
81
      else
82
        {
83 d44e686e Ondrej Zajicek (work)
          if (ipa_in_netX(*a, &b->prefix))
84 85053fce Martin Mares
            {
85 9b136840 Jan Moskyto Matejka
              /* Do not allow IPv4 network and broadcast addresses */
86
              if (ipa_is_ip4(*a) &&
87 d7661fbe Jan Moskyto Matejka
                  (net_pxlen(&b->prefix) < (IP4_MAX_PREFIX_LENGTH - 1)) &&
88 9b136840 Jan Moskyto Matejka
                  (ipa_equal(*a, net_prefix(&b->prefix)) ||        /* Network address */
89 ba321706 Ondrej Zajicek
                   ipa_equal(*a, b->brd)))        /* Broadcast */
90 2d0b7e24 Ondrej Zajicek
              {
91
                *ap = NULL;
92 85053fce Martin Mares
                return -1;
93 2d0b7e24 Ondrej Zajicek
              }
94 ba321706 Ondrej Zajicek
95 0f32f2a6 Martin Mares
              return b->scope;
96 85053fce Martin Mares
            }
97
        }
98
      }
99 2d0b7e24 Ondrej Zajicek
100
  *ap = NULL;
101 0f32f2a6 Martin Mares
  return -1;
102 85053fce Martin Mares
}
103
104 1f495723 Martin Mares
/**
105
 * neigh_find - find or create a neighbor entry.
106
 * @p: protocol which asks for the entry.
107
 * @a: pointer to IP address of the node to be searched for.
108
 * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
109
 *
110
 * Search the neighbor cache for a node with given IP address. If
111
 * it's found, a pointer to the neighbor entry is returned. If no
112
 * such entry exists and the node is directly connected on
113
 * one of our active interfaces, a new entry is created and returned
114
 * to the caller with protocol-dependent fields initialized to zero.
115
 * If the node is not connected directly or *@a is not a valid unicast
116
 * IP address, neigh_find() returns %NULL.
117
 */
118 85053fce Martin Mares
neighbor *
119
neigh_find(struct proto *p, ip_addr *a, unsigned flags)
120
{
121 061ab802 Ondrej Zajicek
  return neigh_find2(p, a, NULL, flags);
122
}
123 be862406 Ondrej Zajicek
124 061ab802 Ondrej Zajicek
125
neighbor *
126 be862406 Ondrej Zajicek
neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
127 061ab802 Ondrej Zajicek
{
128 85053fce Martin Mares
  neighbor *n;
129 8ecbaf9c Ondrej Zajicek
  int class, scope = -1;
130 ae80a2de Pavel Tvrdík
  uint h = neigh_hash(p, a);
131 be862406 Ondrej Zajicek
  struct iface *i;
132 2d0b7e24 Ondrej Zajicek
  struct ifa *addr;
133 85053fce Martin Mares
134
  WALK_LIST(n, neigh_hash_table[h])        /* Search the cache */
135 ff2857b0 Ondrej Zajicek
    if (n->proto == p && ipa_equal(*a, n->addr) && (!ifa || (ifa == n->iface)))
136 85053fce Martin Mares
      return n;
137
138
  class = ipa_classify(*a);
139
  if (class < 0)                        /* Invalid address */
140
    return NULL;
141 be862406 Ondrej Zajicek
  if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
142
      (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
143 85053fce Martin Mares
      !(class & IADDR_HOST))
144
    return NULL;                        /* Bad scope or a somecast */
145
146 be862406 Ondrej Zajicek
  if (ifa)
147 ff2857b0 Ondrej Zajicek
    {
148 2d0b7e24 Ondrej Zajicek
      scope = if_connected(a, ifa, &addr);
149 69a8259c Ondrej Zajicek
      flags |= NEF_BIND;
150 ff2857b0 Ondrej Zajicek
151
      if ((scope < 0) && (flags & NEF_ONLINK))
152
        scope = class & IADDR_SCOPE_MASK;
153
    }
154 be862406 Ondrej Zajicek
  else
155
    WALK_LIST(i, iface_list)
156 2d0b7e24 Ondrej Zajicek
      if ((scope = if_connected(a, i, &addr)) >= 0)
157 be862406 Ondrej Zajicek
        {
158
          ifa = i;
159
          break;
160
        }
161
162 ff2857b0 Ondrej Zajicek
  /* scope < 0 means i don't know neighbor */
163
  /* scope >= 0 implies ifa != NULL */
164
165
  if ((scope < 0) && !(flags & NEF_STICKY))
166 85053fce Martin Mares
    return NULL;
167
168
  n = sl_alloc(neigh_slab);
169
  n->addr = *a;
170 ff2857b0 Ondrej Zajicek
  if (scope >= 0)
171 85053fce Martin Mares
    {
172
      add_tail(&neigh_hash_table[h], &n->n);
173 be862406 Ondrej Zajicek
      add_tail(&ifa->neighbors, &n->if_n);
174 85053fce Martin Mares
    }
175
  else
176 a9aa4c1e Martin Mares
    {
177
      add_tail(&sticky_neigh_list, &n->n);
178 9d67ffb0 Ondrej Zajicek
      scope = -1;
179 a9aa4c1e Martin Mares
    }
180 ff2857b0 Ondrej Zajicek
  n->iface = ifa;
181 2d0b7e24 Ondrej Zajicek
  n->ifa = addr;
182 85053fce Martin Mares
  n->proto = p;
183
  n->data = NULL;
184
  n->aux = 0;
185
  n->flags = flags;
186 0f32f2a6 Martin Mares
  n->scope = scope;
187 85053fce Martin Mares
  return n;
188
}
189
190 1f495723 Martin Mares
/**
191
 * neigh_dump - dump specified neighbor entry.
192
 * @n: the entry to dump
193
 *
194
 * This functions dumps the contents of a given neighbor entry
195
 * to debug output.
196
 */
197 85053fce Martin Mares
void
198
neigh_dump(neighbor *n)
199
{
200
  debug("%p %I ", n, n->addr);
201
  if (n->iface)
202
    debug("%s ", n->iface->name);
203
  else
204
    debug("[] ");
205 0f32f2a6 Martin Mares
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
206 85053fce Martin Mares
  if (n->flags & NEF_STICKY)
207
    debug(" STICKY");
208
  debug("\n");
209
}
210
211 1f495723 Martin Mares
/**
212
 * neigh_dump_all - dump all neighbor entries.
213
 *
214
 * This function dumps the contents of the neighbor cache to
215
 * debug output.
216
 */
217 85053fce Martin Mares
void
218
neigh_dump_all(void)
219
{
220
  neighbor *n;
221
  int i;
222
223
  debug("Known neighbors:\n");
224
  WALK_LIST(n, sticky_neigh_list)
225
    neigh_dump(n);
226
  for(i=0; i<NEIGH_HASH_SIZE; i++)
227 18c031fa Martin Mares
    WALK_LIST(n, neigh_hash_table[i])
228
      neigh_dump(n);
229 85053fce Martin Mares
  debug("\n");
230
}
231
232 cf7f0645 Ondrej Zajicek
static void
233 2d0b7e24 Ondrej Zajicek
neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
234 cf7f0645 Ondrej Zajicek
{
235
  n->iface = i;
236 2d0b7e24 Ondrej Zajicek
  n->ifa = a;
237 cf7f0645 Ondrej Zajicek
  n->scope = scope;
238
  add_tail(&i->neighbors, &n->if_n);
239
  rem_node(&n->n);
240
  add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
241
  DBG("Waking up sticky neighbor %I\n", n->addr);
242 f4a60a9b Ondrej Zajicek (work)
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
243 cf7f0645 Ondrej Zajicek
    n->proto->neigh_notify(n);
244
}
245
246
static void
247
neigh_down(neighbor *n)
248
{
249 f83ce94d Ondrej Zajicek
  DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
250 cf7f0645 Ondrej Zajicek
  rem_node(&n->if_n);
251 69a8259c Ondrej Zajicek
  if (! (n->flags & NEF_BIND))
252
    n->iface = NULL;
253 2d0b7e24 Ondrej Zajicek
  n->ifa = NULL;
254 69a8259c Ondrej Zajicek
  n->scope = -1;
255 f4a60a9b Ondrej Zajicek (work)
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
256 cf7f0645 Ondrej Zajicek
    n->proto->neigh_notify(n);
257
  rem_node(&n->n);
258
  if (n->flags & NEF_STICKY)
259 8ecbaf9c Ondrej Zajicek
    {
260
      add_tail(&sticky_neigh_list, &n->n);
261
262
      /* Respawn neighbor if there is another matching prefix */
263
      struct iface *i;
264 2d0b7e24 Ondrej Zajicek
      struct ifa *a;
265 8ecbaf9c Ondrej Zajicek
      int scope;
266
267
      if (!n->iface)
268
        WALK_LIST(i, iface_list)
269 2d0b7e24 Ondrej Zajicek
          if ((scope = if_connected(&n->addr, i, &a)) >= 0)
270 8ecbaf9c Ondrej Zajicek
            {
271 2d0b7e24 Ondrej Zajicek
              neigh_up(n, i, scope, a);
272 8ecbaf9c Ondrej Zajicek
              return;
273
            }
274
    }
275 cf7f0645 Ondrej Zajicek
  else
276
    sl_free(neigh_slab, n);
277
}
278
279
280 1f495723 Martin Mares
/**
281
 * neigh_if_up: notify neighbor cache about interface up event
282
 * @i: interface in question
283
 *
284
 * Tell the neighbor cache that a new interface became up.
285
 *
286
 * The neighbor cache wakes up all inactive sticky neighbors with
287
 * addresses belonging to prefixes of the interface @i.
288
 */
289 85053fce Martin Mares
void
290
neigh_if_up(struct iface *i)
291
{
292 2d0b7e24 Ondrej Zajicek
  struct ifa *a;
293 85053fce Martin Mares
  neighbor *n, *next;
294 0f32f2a6 Martin Mares
  int scope;
295 85053fce Martin Mares
296
  WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
297 69a8259c Ondrej Zajicek
    if ((!n->iface || n->iface == i) &&
298 2d0b7e24 Ondrej Zajicek
        ((scope = if_connected(&n->addr, i, &a)) >= 0))
299
      neigh_up(n, i, scope, a);
300 85053fce Martin Mares
}
301
302 1f495723 Martin Mares
/**
303
 * neigh_if_down - notify neighbor cache about interface down event
304
 * @i: the interface in question
305
 *
306
 * Notify the neighbor cache that an interface has ceased to exist.
307
 *
308
 * It causes all entries belonging to neighbors connected to this interface
309
 * to be flushed.
310
 */
311 85053fce Martin Mares
void
312
neigh_if_down(struct iface *i)
313
{
314
  node *x, *y;
315
316
  WALK_LIST_DELSAFE(x, y, i->neighbors)
317 cf7f0645 Ondrej Zajicek
    neigh_down(SKIP_BACK(neighbor, if_n, x));
318 85053fce Martin Mares
}
319
320 fe181e7c Ondrej Zajicek
/**
321
 * neigh_if_link - notify neighbor cache about interface link change
322
 * @i: the interface in question
323
 *
324
 * Notify the neighbor cache that an interface changed link state.
325
 * All owners of neighbor entries connected to this interface are
326
 * notified.
327
 */
328
void
329
neigh_if_link(struct iface *i)
330
{
331
  node *x, *y;
332
333
  WALK_LIST_DELSAFE(x, y, i->neighbors)
334
    {
335
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
336 f4a60a9b Ondrej Zajicek (work)
      if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
337 fe181e7c Ondrej Zajicek
        n->proto->neigh_notify(n);
338
    }
339
}
340
341 cf7f0645 Ondrej Zajicek
/**
342
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
343 8e433d6a Pavel Tvrdik
 * @a: interface address in question
344 cf7f0645 Ondrej Zajicek
 *
345
 * Tell the neighbor cache that an address was added or removed.
346
 *
347
 * The neighbor cache wakes up all inactive sticky neighbors with
348
 * addresses belonging to prefixes of the interface belonging to @ifa
349
 * and causes all unreachable neighbors to be flushed.
350
 */
351
void
352
neigh_ifa_update(struct ifa *a)
353
{
354
  struct iface *i = a->iface;
355
  node *x, *y;
356
 
357
  /* Remove all neighbors whose scope has changed */
358
  WALK_LIST_DELSAFE(x, y, i->neighbors)
359
    {
360 2d0b7e24 Ondrej Zajicek
      struct ifa *aa;
361 cf7f0645 Ondrej Zajicek
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
362 2d0b7e24 Ondrej Zajicek
      if (if_connected(&n->addr, i, &aa) != n->scope)
363 cf7f0645 Ondrej Zajicek
        neigh_down(n);
364
    }
365
366
  /* Wake up all sticky neighbors that are reachable now */
367
  neigh_if_up(i);
368
}
369
370 18c031fa Martin Mares
static inline void
371
neigh_prune_one(neighbor *n)
372
{
373 d6a836f8 Ondrej Zajicek
  if (n->proto->proto_state != PS_DOWN)
374 18c031fa Martin Mares
    return;
375
  rem_node(&n->n);
376 69a8259c Ondrej Zajicek
  if (n->scope >= 0)
377 18c031fa Martin Mares
    rem_node(&n->if_n);
378
  sl_free(neigh_slab, n);
379
}
380
381 1f495723 Martin Mares
/**
382
 * neigh_prune - prune neighbor cache
383
 *
384
 * neigh_prune() examines all neighbor entries cached and removes those
385
 * corresponding to inactive protocols. It's called whenever a protocol
386
 * is shut down to get rid of all its heritage.
387
 */
388 85053fce Martin Mares
void
389
neigh_prune(void)
390
{
391
  neighbor *n;
392
  node *m;
393
  int i;
394
395
  DBG("Pruning neighbors\n");
396
  for(i=0; i<NEIGH_HASH_SIZE; i++)
397
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
398 18c031fa Martin Mares
      neigh_prune_one(n);
399
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
400
    neigh_prune_one(n);
401 85053fce Martin Mares
}
402
403 1f495723 Martin Mares
/**
404
 * neigh_init - initialize the neighbor cache.
405
 * @if_pool: resource pool to be used for neighbor entries.
406
 *
407
 * This function is called during BIRD startup to initialize
408
 * the neighbor cache module.
409
 */
410 85053fce Martin Mares
void
411
neigh_init(pool *if_pool)
412
{
413
  int i;
414
415
  neigh_slab = sl_new(if_pool, sizeof(neighbor));
416
  init_list(&sticky_neigh_list);
417
  for(i=0; i<NEIGH_HASH_SIZE; i++)
418
    init_list(&neigh_hash_table[i]);
419
}