Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (9.72 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 unsigned int
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) /* -1=error, 1=match, 0=no match */
60
{
61
  struct ifa *b;
62

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

    
85
              return b->scope;
86
            }
87
        }
88
      }
89
  return -1;
90
}
91

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

    
112

    
113
neighbor *
114
neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags)
115
{
116
  neighbor *n;
117
  int class, scope = -1;       ;
118
  unsigned int h = neigh_hash(p, a);
119
  struct iface *i;
120

    
121
  WALK_LIST(n, neigh_hash_table[h])        /* Search the cache */
122
    if (n->proto == p && ipa_equal(*a, n->addr) && (!ifa || (ifa == n->iface)))
123
      return n;
124

    
125
  class = ipa_classify(*a);
126
  if (class < 0)                        /* Invalid address */
127
    return NULL;
128
  if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) ||
129
      (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) ||
130
      !(class & IADDR_HOST))
131
    return NULL;                        /* Bad scope or a somecast */
132

    
133
  if (ifa)
134
    {
135
      scope = if_connected(a, ifa);
136

    
137
      if ((scope < 0) && (flags & NEF_ONLINK))
138
        scope = class & IADDR_SCOPE_MASK;
139
    }
140
  else
141
    WALK_LIST(i, iface_list)
142
      if ((scope = if_connected(a, i)) >= 0)
143
        {
144
          ifa = i;
145
          break;
146
        }
147

    
148
  /* scope < 0 means i don't know neighbor */
149
  /* scope >= 0 implies ifa != NULL */
150

    
151
  if ((scope < 0) && !(flags & NEF_STICKY))
152
    return NULL;
153

    
154
  n = sl_alloc(neigh_slab);
155
  n->addr = *a;
156
  if (scope >= 0)
157
    {
158
      add_tail(&neigh_hash_table[h], &n->n);
159
      add_tail(&ifa->neighbors, &n->if_n);
160
    }
161
  else
162
    {
163
      /* sticky flag does not work for link-local neighbors;
164
         fortunately, we don't use this combination */
165
      add_tail(&sticky_neigh_list, &n->n);
166
      ifa = NULL;
167
      scope = -1;
168
    }
169
  n->iface = ifa;
170
  n->proto = p;
171
  n->data = NULL;
172
  n->aux = 0;
173
  n->flags = flags;
174
  n->scope = scope;
175
  return n;
176
}
177

    
178
/**
179
 * neigh_dump - dump specified neighbor entry.
180
 * @n: the entry to dump
181
 *
182
 * This functions dumps the contents of a given neighbor entry
183
 * to debug output.
184
 */
185
void
186
neigh_dump(neighbor *n)
187
{
188
  debug("%p %I ", n, n->addr);
189
  if (n->iface)
190
    debug("%s ", n->iface->name);
191
  else
192
    debug("[] ");
193
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
194
  if (n->flags & NEF_STICKY)
195
    debug(" STICKY");
196
  debug("\n");
197
}
198

    
199
/**
200
 * neigh_dump_all - dump all neighbor entries.
201
 *
202
 * This function dumps the contents of the neighbor cache to
203
 * debug output.
204
 */
205
void
206
neigh_dump_all(void)
207
{
208
  neighbor *n;
209
  int i;
210

    
211
  debug("Known neighbors:\n");
212
  WALK_LIST(n, sticky_neigh_list)
213
    neigh_dump(n);
214
  for(i=0; i<NEIGH_HASH_SIZE; i++)
215
    WALK_LIST(n, neigh_hash_table[i])
216
      neigh_dump(n);
217
  debug("\n");
218
}
219

    
220
static void
221
neigh_up(neighbor *n, struct iface *i, int scope)
222
{
223
  n->iface = i;
224
  n->scope = scope;
225
  add_tail(&i->neighbors, &n->if_n);
226
  rem_node(&n->n);
227
  add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
228
  DBG("Waking up sticky neighbor %I\n", n->addr);
229
  if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
230
    n->proto->neigh_notify(n);
231
}
232

    
233
static void
234
neigh_down(neighbor *n)
235
{
236
  DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
237
  rem_node(&n->if_n);
238
  n->iface = NULL;
239
  if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
240
    n->proto->neigh_notify(n);
241
  rem_node(&n->n);
242
  if (n->flags & NEF_STICKY)
243
    add_tail(&sticky_neigh_list, &n->n);
244
  else
245
    sl_free(neigh_slab, n);
246
}
247

    
248

    
249
/**
250
 * neigh_if_up: notify neighbor cache about interface up event
251
 * @i: interface in question
252
 *
253
 * Tell the neighbor cache that a new interface became up.
254
 *
255
 * The neighbor cache wakes up all inactive sticky neighbors with
256
 * addresses belonging to prefixes of the interface @i.
257
 */
258
void
259
neigh_if_up(struct iface *i)
260
{
261
  neighbor *n, *next;
262
  int scope;
263

    
264
  WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
265
    if ((scope = if_connected(&n->addr, i)) >= 0)
266
      neigh_up(n, i, scope);
267
}
268

    
269
/**
270
 * neigh_if_down - notify neighbor cache about interface down event
271
 * @i: the interface in question
272
 *
273
 * Notify the neighbor cache that an interface has ceased to exist.
274
 *
275
 * It causes all entries belonging to neighbors connected to this interface
276
 * to be flushed.
277
 */
278
void
279
neigh_if_down(struct iface *i)
280
{
281
  node *x, *y;
282

    
283
  WALK_LIST_DELSAFE(x, y, i->neighbors)
284
    neigh_down(SKIP_BACK(neighbor, if_n, x));
285
}
286

    
287
/**
288
 * neigh_if_link - notify neighbor cache about interface link change
289
 * @i: the interface in question
290
 *
291
 * Notify the neighbor cache that an interface changed link state.
292
 * All owners of neighbor entries connected to this interface are
293
 * notified.
294
 */
295
void
296
neigh_if_link(struct iface *i)
297
{
298
  node *x, *y;
299

    
300
  WALK_LIST_DELSAFE(x, y, i->neighbors)
301
    {
302
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
303
      if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
304
        n->proto->neigh_notify(n);
305
    }
306
}
307

    
308
/**
309
 * neigh_ifa_update: notify neighbor cache about interface address add or remove event
310
 * @ifa: interface address in question
311
 *
312
 * Tell the neighbor cache that an address was added or removed.
313
 *
314
 * The neighbor cache wakes up all inactive sticky neighbors with
315
 * addresses belonging to prefixes of the interface belonging to @ifa
316
 * and causes all unreachable neighbors to be flushed.
317
 */
318
void
319
neigh_ifa_update(struct ifa *a)
320
{
321
  struct iface *i = a->iface;
322
  node *x, *y;
323
 
324
  /* Remove all neighbors whose scope has changed */
325
  WALK_LIST_DELSAFE(x, y, i->neighbors)
326
    {
327
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
328
      if (if_connected(&n->addr, i) != n->scope)
329
        neigh_down(n);
330
    }
331

    
332
  /* Wake up all sticky neighbors that are reachable now */
333
  neigh_if_up(i);
334
}
335

    
336
static inline void
337
neigh_prune_one(neighbor *n)
338
{
339
  if (n->proto->proto_state != PS_DOWN)
340
    return;
341
  rem_node(&n->n);
342
  if (n->iface)
343
    rem_node(&n->if_n);
344
  sl_free(neigh_slab, n);
345
}
346

    
347
/**
348
 * neigh_prune - prune neighbor cache
349
 *
350
 * neigh_prune() examines all neighbor entries cached and removes those
351
 * corresponding to inactive protocols. It's called whenever a protocol
352
 * is shut down to get rid of all its heritage.
353
 */
354
void
355
neigh_prune(void)
356
{
357
  neighbor *n;
358
  node *m;
359
  int i;
360

    
361
  DBG("Pruning neighbors\n");
362
  for(i=0; i<NEIGH_HASH_SIZE; i++)
363
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
364
      neigh_prune_one(n);
365
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
366
    neigh_prune_one(n);
367
}
368

    
369
/**
370
 * neigh_init - initialize the neighbor cache.
371
 * @if_pool: resource pool to be used for neighbor entries.
372
 *
373
 * This function is called during BIRD startup to initialize
374
 * the neighbor cache module.
375
 */
376
void
377
neigh_init(pool *if_pool)
378
{
379
  int i;
380

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