Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.3 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
#define NEIGH_HASH_OFFSET 24
49

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

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

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

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

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

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

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

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

    
104
/**
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
neighbor *
119
neigh_find(struct proto *p, ip_addr *a, unsigned flags)
120
{
121
  return neigh_find2(p, a, NULL, flags);
122
}
123

    
124

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

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

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

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

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

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

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

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

    
190
/**
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
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
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
206
  if (n->flags & NEF_STICKY)
207
    debug(" STICKY");
208
  debug("\n");
209
}
210

    
211
/**
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
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
    WALK_LIST(n, neigh_hash_table[i])
228
      neigh_dump(n);
229
  debug("\n");
230
}
231

    
232
static void
233
neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
234
{
235
  n->iface = i;
236
  n->ifa = a;
237
  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
  if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
243
    n->proto->neigh_notify(n);
244
}
245

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

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

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

    
279

    
280
/**
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
void
290
neigh_if_up(struct iface *i)
291
{
292
  struct ifa *a;
293
  neighbor *n, *next;
294
  int scope;
295

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

    
302
/**
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
void
312
neigh_if_down(struct iface *i)
313
{
314
  node *x, *y;
315

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

    
320
/**
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
      if (n->proto->neigh_notify && (n->proto->proto_state != PS_STOP))
337
        n->proto->neigh_notify(n);
338
    }
339
}
340

    
341
/**
342
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
343
 * @a: interface address in question
344
 *
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
      struct ifa *aa;
361
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
362
      if (if_connected(&n->addr, i, &aa) != n->scope)
363
        neigh_down(n);
364
    }
365

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

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

    
381
/**
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
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
      neigh_prune_one(n);
399
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
400
    neigh_prune_one(n);
401
}
402

    
403
/**
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
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
}