Statistics
| Branch: | Revision:

iof-bird-daemon / nest / neighbor.c @ 8e433d6a

History | View | Annotate | Download (10.2 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.
34
 *
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
#undef LOCAL_DEBUG
41

    
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

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

    
52
static inline uint
53
neigh_hash(struct proto *p, ip_addr *a)
54
{
55
  return (p->hash_key ^ ipa_hash(*a)) & (NEIGH_HASH_SIZE-1);
56
}
57

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

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

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

    
73
      if (ipa_equal(*a, b->ip))
74
        return SCOPE_HOST;
75
      if (b->flags & IA_PEER)
76
        {
77
          if (ipa_equal(*a, b->opposite))
78
            return b->scope;
79
        }
80
      else
81
        {
82
          if (ipa_in_net(*a, b->prefix, b->pxlen))
83
            {
84
#ifndef IPV6
85
              if ((b->pxlen < (BITS_PER_IP_ADDRESS - 1)) &&
86
                  (ipa_equal(*a, b->prefix) ||        /* Network address */
87
                   ipa_equal(*a, b->brd)))        /* Broadcast */
88
              {
89
                *ap = NULL;
90
                return -1;
91
              }
92
#endif
93

    
94
              return b->scope;
95
            }
96
        }
97
      }
98

    
99
  *ap = NULL;
100
  return -1;
101
}
102

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

    
123

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

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

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

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

    
150
      if ((scope < 0) && (flags & NEF_ONLINK))
151
        scope = class & IADDR_SCOPE_MASK;
152
    }
153
  else
154
    WALK_LIST(i, iface_list)
155
      if ((scope = if_connected(a, i, &addr)) >= 0)
156
        {
157
          ifa = i;
158
          break;
159
        }
160

    
161
  /* scope < 0 means i don't know neighbor */
162
  /* scope >= 0 implies ifa != NULL */
163

    
164
  if ((scope < 0) && !(flags & NEF_STICKY))
165
    return NULL;
166

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

    
189
/**
190
 * neigh_dump - dump specified neighbor entry.
191
 * @n: the entry to dump
192
 *
193
 * This functions dumps the contents of a given neighbor entry
194
 * to debug output.
195
 */
196
void
197
neigh_dump(neighbor *n)
198
{
199
  debug("%p %I ", n, n->addr);
200
  if (n->iface)
201
    debug("%s ", n->iface->name);
202
  else
203
    debug("[] ");
204
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
205
  if (n->flags & NEF_STICKY)
206
    debug(" STICKY");
207
  debug("\n");
208
}
209

    
210
/**
211
 * neigh_dump_all - dump all neighbor entries.
212
 *
213
 * This function dumps the contents of the neighbor cache to
214
 * debug output.
215
 */
216
void
217
neigh_dump_all(void)
218
{
219
  neighbor *n;
220
  int i;
221

    
222
  debug("Known neighbors:\n");
223
  WALK_LIST(n, sticky_neigh_list)
224
    neigh_dump(n);
225
  for(i=0; i<NEIGH_HASH_SIZE; i++)
226
    WALK_LIST(n, neigh_hash_table[i])
227
      neigh_dump(n);
228
  debug("\n");
229
}
230

    
231
static void
232
neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
233
{
234
  n->iface = i;
235
  n->ifa = a;
236
  n->scope = scope;
237
  add_tail(&i->neighbors, &n->if_n);
238
  rem_node(&n->n);
239
  add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
240
  DBG("Waking up sticky neighbor %I\n", n->addr);
241
  if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
242
    n->proto->neigh_notify(n);
243
}
244

    
245
static void
246
neigh_down(neighbor *n)
247
{
248
  DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
249
  rem_node(&n->if_n);
250
  if (! (n->flags & NEF_BIND))
251
    n->iface = NULL;
252
  n->ifa = NULL;
253
  n->scope = -1;
254
  if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
255
    n->proto->neigh_notify(n);
256
  rem_node(&n->n);
257
  if (n->flags & NEF_STICKY)
258
    {
259
      add_tail(&sticky_neigh_list, &n->n);
260

    
261
      /* Respawn neighbor if there is another matching prefix */
262
      struct iface *i;
263
      struct ifa *a;
264
      int scope;
265

    
266
      if (!n->iface)
267
        WALK_LIST(i, iface_list)
268
          if ((scope = if_connected(&n->addr, i, &a)) >= 0)
269
            {
270
              neigh_up(n, i, scope, a);
271
              return;
272
            }
273
    }
274
  else
275
    sl_free(neigh_slab, n);
276
}
277

    
278

    
279
/**
280
 * neigh_if_up: notify neighbor cache about interface up event
281
 * @i: interface in question
282
 *
283
 * Tell the neighbor cache that a new interface became up.
284
 *
285
 * The neighbor cache wakes up all inactive sticky neighbors with
286
 * addresses belonging to prefixes of the interface @i.
287
 */
288
void
289
neigh_if_up(struct iface *i)
290
{
291
  struct ifa *a;
292
  neighbor *n, *next;
293
  int scope;
294

    
295
  WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
296
    if ((!n->iface || n->iface == i) &&
297
        ((scope = if_connected(&n->addr, i, &a)) >= 0))
298
      neigh_up(n, i, scope, a);
299
}
300

    
301
/**
302
 * neigh_if_down - notify neighbor cache about interface down event
303
 * @i: the interface in question
304
 *
305
 * Notify the neighbor cache that an interface has ceased to exist.
306
 *
307
 * It causes all entries belonging to neighbors connected to this interface
308
 * to be flushed.
309
 */
310
void
311
neigh_if_down(struct iface *i)
312
{
313
  node *x, *y;
314

    
315
  WALK_LIST_DELSAFE(x, y, i->neighbors)
316
    neigh_down(SKIP_BACK(neighbor, if_n, x));
317
}
318

    
319
/**
320
 * neigh_if_link - notify neighbor cache about interface link change
321
 * @i: the interface in question
322
 *
323
 * Notify the neighbor cache that an interface changed link state.
324
 * All owners of neighbor entries connected to this interface are
325
 * notified.
326
 */
327
void
328
neigh_if_link(struct iface *i)
329
{
330
  node *x, *y;
331

    
332
  WALK_LIST_DELSAFE(x, y, i->neighbors)
333
    {
334
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
335
      if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
336
        n->proto->neigh_notify(n);
337
    }
338
}
339

    
340
/**
341
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
342
 * @a: interface address in question
343
 *
344
 * Tell the neighbor cache that an address was added or removed.
345
 *
346
 * The neighbor cache wakes up all inactive sticky neighbors with
347
 * addresses belonging to prefixes of the interface belonging to @ifa
348
 * and causes all unreachable neighbors to be flushed.
349
 */
350
void
351
neigh_ifa_update(struct ifa *a)
352
{
353
  struct iface *i = a->iface;
354
  node *x, *y;
355
 
356
  /* Remove all neighbors whose scope has changed */
357
  WALK_LIST_DELSAFE(x, y, i->neighbors)
358
    {
359
      struct ifa *aa;
360
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
361
      if (if_connected(&n->addr, i, &aa) != n->scope)
362
        neigh_down(n);
363
    }
364

    
365
  /* Wake up all sticky neighbors that are reachable now */
366
  neigh_if_up(i);
367
}
368

    
369
static inline void
370
neigh_prune_one(neighbor *n)
371
{
372
  if (n->proto->proto_state != PS_DOWN)
373
    return;
374
  rem_node(&n->n);
375
  if (n->scope >= 0)
376
    rem_node(&n->if_n);
377
  sl_free(neigh_slab, n);
378
}
379

    
380
/**
381
 * neigh_prune - prune neighbor cache
382
 *
383
 * neigh_prune() examines all neighbor entries cached and removes those
384
 * corresponding to inactive protocols. It's called whenever a protocol
385
 * is shut down to get rid of all its heritage.
386
 */
387
void
388
neigh_prune(void)
389
{
390
  neighbor *n;
391
  node *m;
392
  int i;
393

    
394
  DBG("Pruning neighbors\n");
395
  for(i=0; i<NEIGH_HASH_SIZE; i++)
396
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
397
      neigh_prune_one(n);
398
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
399
    neigh_prune_one(n);
400
}
401

    
402
/**
403
 * neigh_init - initialize the neighbor cache.
404
 * @if_pool: resource pool to be used for neighbor entries.
405
 *
406
 * This function is called during BIRD startup to initialize
407
 * the neighbor cache module.
408
 */
409
void
410
neigh_init(pool *if_pool)
411
{
412
  int i;
413

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