Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / nest / neighbor.c @ 6b3f1a54

History | View | Annotate | Download (11.7 KB)

1
/*
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
/**
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
 * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a
24
 * single protocol.
25
 *
26
 * Active entries represent known neighbors and are stored in a hash
27
 * table (to allow fast retrieval based on the IP address of the node) and
28
 * 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
 * whenever an interface changes its state to up. Neighbor entry VRF
34
 * association is implied by respective protocol.
35
 *
36
 * When a neighbor event occurs (a neighbor gets disconnected or a sticky
37
 * inactive neighbor becomes connected), the protocol hook neigh_notify()
38
 * is called to advertise the change.
39
 */
40

    
41
#undef LOCAL_DEBUG
42

    
43
#include "nest/bird.h"
44
#include "nest/iface.h"
45
#include "nest/protocol.h"
46
#include "lib/resource.h"
47

    
48
#define NEIGH_HASH_SIZE 256
49
#define NEIGH_HASH_OFFSET 24
50

    
51
static slab *neigh_slab;
52
static list sticky_neigh_list, iface_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];
53

    
54
static inline uint
55
neigh_hash(struct proto *p, ip_addr *a)
56
{
57
  return (p->hash_key ^ ipa_hash(*a)) >> NEIGH_HASH_OFFSET;
58
}
59

    
60
static int
61
if_connected(ip_addr *a, struct iface *i, struct ifa **ap)
62
{
63
  struct ifa *b;
64

    
65
  if (!(i->flags & IF_UP))
66
  {
67
    *ap = NULL;
68
    return -1;
69
  }
70

    
71
  WALK_LIST(b, i->addrs)
72
    {
73
      *ap = b;
74

    
75
      if (ipa_equal(*a, b->ip))
76
        return SCOPE_HOST;
77
      if (b->flags & IA_PEER)
78
        {
79
          if (ipa_equal(*a, b->opposite))
80
            return b->scope;
81
        }
82
      else
83
        {
84
          if (ipa_in_netX(*a, &b->prefix))
85
            {
86
              /* Do not allow IPv4 network and broadcast addresses */
87
              if (ipa_is_ip4(*a) &&
88
                  (net_pxlen(&b->prefix) < (IP4_MAX_PREFIX_LENGTH - 1)) &&
89
                  (ipa_equal(*a, net_prefix(&b->prefix)) ||        /* Network address */
90
                   ipa_equal(*a, b->brd)))        /* Broadcast */
91
              {
92
                *ap = NULL;
93
                return -1;
94
              }
95

    
96
              return b->scope;
97
            }
98
        }
99
      }
100

    
101
  *ap = NULL;
102
  return -1;
103
}
104

    
105
/**
106
 * neigh_find - find or create a neighbor entry.
107
 * @p: protocol which asks for the entry.
108
 * @a: pointer to IP address of the node to be searched for.
109
 * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
110
 *
111
 * Search the neighbor cache for a node with given IP address. If
112
 * it's found, a pointer to the neighbor entry is returned. If no
113
 * such entry exists and the node is directly connected on
114
 * one of our active interfaces, a new entry is created and returned
115
 * to the caller with protocol-dependent fields initialized to zero.
116
 * If the node is not connected directly or *@a is not a valid unicast
117
 * IP address, neigh_find() returns %NULL.
118
 */
119
neighbor *
120
neigh_find(struct proto *p, ip_addr *a, unsigned flags)
121
{
122
  return neigh_find2(p, a, NULL, flags);
123
}
124

    
125

    
126
neighbor *
127
neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
128
{
129
  neighbor *n;
130
  int class, scope = -1;
131
  uint h = neigh_hash(p, a);
132
  struct iface *i;
133
  struct ifa *addr;
134

    
135
  WALK_LIST(n, neigh_hash_table[h])        /* Search the cache */
136
    if (n->proto == p && ipa_equal(*a, n->addr) && (!ifa || (ifa == n->iface)))
137
      return n;
138

    
139
  class = ipa_classify(*a);
140
  if (class < 0)                        /* Invalid address */
141
    return NULL;
142
  if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
143
      (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
144
      !(class & IADDR_HOST))
145
    return NULL;                        /* Bad scope or a somecast */
146

    
147
  if (ifa)
148
    {
149
      scope = if_connected(a, ifa, &addr);
150
      flags |= NEF_BIND;
151

    
152
      if ((scope < 0) && (flags & NEF_ONLINK))
153
        scope = class & IADDR_SCOPE_MASK;
154
    }
155
  else
156
    WALK_LIST(i, iface_list)
157
      if ((!p->vrf || p->vrf == i->master) &&
158
          ((scope = if_connected(a, i, &addr)) >= 0))
159
        {
160
          ifa = i;
161
          break;
162
        }
163

    
164
  /* scope < 0 means i don't know neighbor */
165
  /* scope >= 0 implies ifa != NULL */
166

    
167
  if ((scope < 0) && !(flags & NEF_STICKY))
168
    return NULL;
169

    
170
  n = sl_alloc(neigh_slab);
171
  memset(n, 0, sizeof(neighbor));
172

    
173
  n->addr = *a;
174
  if (scope >= 0)
175
    {
176
      add_tail(&neigh_hash_table[h], &n->n);
177
      add_tail(&ifa->neighbors, &n->if_n);
178
    }
179
  else
180
    {
181
      add_tail(&sticky_neigh_list, &n->n);
182
      scope = -1;
183
    }
184
  n->iface = ifa;
185
  n->ifa = addr;
186
  n->proto = p;
187
  n->data = NULL;
188
  n->aux = 0;
189
  n->flags = flags;
190
  n->scope = scope;
191
  return n;
192
}
193

    
194
neighbor *
195
neigh_find_iface(struct proto *p, struct iface *ifa)
196
{
197
  neighbor *n;
198
  node *nn;
199

    
200
  /* We keep neighbors with NEF_IFACE foremost in ifa->neighbors list */
201
  WALK_LIST2(n, nn, ifa->neighbors, if_n)
202
  {
203
    if (! (n->flags & NEF_IFACE))
204
      break;
205

    
206
    if (n->proto == p)
207
      return n;
208
  }
209

    
210
  n = sl_alloc(neigh_slab);
211
  memset(n, 0, sizeof(neighbor));
212

    
213
  add_tail(&iface_neigh_list, &n->n);
214
  add_head(&ifa->neighbors, &n->if_n);
215
  n->iface = ifa;
216
  n->proto = p;
217
  n->flags = NEF_IFACE;
218
  n->scope = (ifa->flags & IF_UP) ? SCOPE_HOST : -1;
219

    
220
  return n;
221
}
222

    
223
/**
224
 * neigh_dump - dump specified neighbor entry.
225
 * @n: the entry to dump
226
 *
227
 * This functions dumps the contents of a given neighbor entry
228
 * to debug output.
229
 */
230
void
231
neigh_dump(neighbor *n)
232
{
233
  debug("%p %I ", n, n->addr);
234
  if (n->iface)
235
    debug("%s ", n->iface->name);
236
  else
237
    debug("[] ");
238
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
239
  if (n->flags & NEF_STICKY)
240
    debug(" STICKY");
241
  if (n->flags & NEF_IFACE)
242
    debug(" IFACE");
243
  debug("\n");
244
}
245

    
246
/**
247
 * neigh_dump_all - dump all neighbor entries.
248
 *
249
 * This function dumps the contents of the neighbor cache to
250
 * debug output.
251
 */
252
void
253
neigh_dump_all(void)
254
{
255
  neighbor *n;
256
  int i;
257

    
258
  debug("Known neighbors:\n");
259
  WALK_LIST(n, sticky_neigh_list)
260
    neigh_dump(n);
261
  WALK_LIST(n, iface_neigh_list)
262
    neigh_dump(n);
263
  for(i=0; i<NEIGH_HASH_SIZE; i++)
264
    WALK_LIST(n, neigh_hash_table[i])
265
      neigh_dump(n);
266
  debug("\n");
267
}
268

    
269
static void
270
neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
271
{
272
  DBG("Waking up sticky neighbor %I\n", n->addr);
273
  n->iface = i;
274
  n->ifa = a;
275
  n->scope = scope;
276

    
277
  if (! (n->flags & NEF_IFACE))
278
  {
279
    add_tail(&i->neighbors, &n->if_n);
280
    rem_node(&n->n);
281
    add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
282
  }
283

    
284
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
285
    n->proto->neigh_notify(n);
286
}
287

    
288
static void
289
neigh_down(neighbor *n)
290
{
291
  DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
292
  if (! (n->flags & (NEF_BIND | NEF_IFACE)))
293
    n->iface = NULL;
294
  n->ifa = NULL;
295
  n->scope = -1;
296

    
297
  if (! (n->flags & NEF_IFACE))
298
    {
299
      rem_node(&n->if_n);
300
      rem_node(&n->n);
301
    }
302

    
303
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
304
    n->proto->neigh_notify(n);
305

    
306
  if (n->flags & NEF_STICKY)
307
    {
308
      add_tail(&sticky_neigh_list, &n->n);
309

    
310
      /* Respawn neighbor if there is another matching prefix */
311
      struct iface *i;
312
      struct ifa *a;
313
      int scope;
314

    
315
      if (!n->iface)
316
        WALK_LIST(i, iface_list)
317
          if ((scope = if_connected(&n->addr, i, &a)) >= 0)
318
            {
319
              neigh_up(n, i, scope, a);
320
              return;
321
            }
322
    }
323

    
324
  if (! (n->flags & (NEF_STICKY | NEF_IFACE)))
325
    sl_free(neigh_slab, n);
326
}
327

    
328

    
329
/**
330
 * neigh_if_up: notify neighbor cache about interface up event
331
 * @i: interface in question
332
 *
333
 * Tell the neighbor cache that a new interface became up.
334
 *
335
 * The neighbor cache wakes up all inactive sticky neighbors with
336
 * addresses belonging to prefixes of the interface @i.
337
 */
338
void
339
neigh_if_up(struct iface *i)
340
{
341
  struct ifa *a;
342
  neighbor *n;
343
  node *x, *y;
344
  int scope;
345

    
346
  /* Wake up all iface neighbors */
347
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
348
    if ((n->scope < 0) && (n->flags & NEF_IFACE))
349
      neigh_up(n, i, SCOPE_HOST, NULL);
350

    
351
  /* Wake up appropriate sticky neighbors */
352
  WALK_LIST_DELSAFE(n, x, sticky_neigh_list)
353
    if ((!n->iface || n->iface == i) &&
354
        ((scope = if_connected(&n->addr, i, &a)) >= 0))
355
      neigh_up(n, i, scope, a);
356
}
357

    
358
/**
359
 * neigh_if_down - notify neighbor cache about interface down event
360
 * @i: the interface in question
361
 *
362
 * Notify the neighbor cache that an interface has ceased to exist.
363
 *
364
 * It causes all entries belonging to neighbors connected to this interface
365
 * to be flushed.
366
 */
367
void
368
neigh_if_down(struct iface *i)
369
{
370
  neighbor *n;
371
  node *x, *y;
372

    
373
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
374
    neigh_down(n);
375
}
376

    
377
/**
378
 * neigh_if_link - notify neighbor cache about interface link change
379
 * @i: the interface in question
380
 *
381
 * Notify the neighbor cache that an interface changed link state.
382
 * All owners of neighbor entries connected to this interface are
383
 * notified.
384
 */
385
void
386
neigh_if_link(struct iface *i)
387
{
388
  neighbor *n;
389
  node *x, *y;
390

    
391
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
392
    if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
393
      n->proto->neigh_notify(n);
394
}
395

    
396
/**
397
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
398
 * @a: interface address in question
399
 *
400
 * Tell the neighbor cache that an address was added or removed.
401
 *
402
 * The neighbor cache wakes up all inactive sticky neighbors with
403
 * addresses belonging to prefixes of the interface belonging to @ifa
404
 * and causes all unreachable neighbors to be flushed.
405
 */
406
void
407
neigh_ifa_update(struct ifa *a)
408
{
409
  struct iface *i = a->iface;
410
  struct ifa *aa;
411
  node *x, *y;
412
  neighbor *n;
413
  int scope;
414

    
415
  /* Remove all neighbors whose scope has changed */
416
  WALK_LIST2_DELSAFE(n, x, y, i->neighbors, if_n)
417
    if (n->ifa && (if_connected(&n->addr, i, &aa) != n->scope))
418
      neigh_down(n);
419

    
420
  /* Wake up all sticky neighbors that are reachable now */
421
  WALK_LIST_DELSAFE(n, x, sticky_neigh_list)
422
    if ((!n->iface || n->iface == i) &&
423
        ((scope = if_connected(&n->addr, i, &aa)) >= 0))
424
      neigh_up(n, i, scope, aa);
425
}
426

    
427
static inline void
428
neigh_prune_one(neighbor *n)
429
{
430
  if (n->proto->proto_state != PS_DOWN)
431
    return;
432
  rem_node(&n->n);
433
  if (n->if_n.next)
434
    rem_node(&n->if_n);
435
  sl_free(neigh_slab, n);
436
}
437

    
438
/**
439
 * neigh_prune - prune neighbor cache
440
 *
441
 * neigh_prune() examines all neighbor entries cached and removes those
442
 * corresponding to inactive protocols. It's called whenever a protocol
443
 * is shut down to get rid of all its heritage.
444
 */
445
void
446
neigh_prune(void)
447
{
448
  neighbor *n;
449
  node *m;
450
  int i;
451

    
452
  DBG("Pruning neighbors\n");
453
  for(i=0; i<NEIGH_HASH_SIZE; i++)
454
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
455
      neigh_prune_one(n);
456
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
457
    neigh_prune_one(n);
458
  WALK_LIST_DELSAFE(n, m, iface_neigh_list)
459
    neigh_prune_one(n);
460
}
461

    
462
/**
463
 * neigh_init - initialize the neighbor cache.
464
 * @if_pool: resource pool to be used for neighbor entries.
465
 *
466
 * This function is called during BIRD startup to initialize
467
 * the neighbor cache module.
468
 */
469
void
470
neigh_init(pool *if_pool)
471
{
472
  neigh_slab = sl_new(if_pool, sizeof(neighbor));
473

    
474
  init_list(&sticky_neigh_list);
475
  init_list(&iface_neigh_list);
476

    
477
  for(int i = 0; i < NEIGH_HASH_SIZE; i++)
478
    init_list(&neigh_hash_table[i]);
479
}