Statistics
| Branch: | Revision:

iof-bird-daemon / nest / neighbor.c @ 061ab802

History | View | Annotate | Download (7.81 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_UNNUMBERED)
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
              if (ipa_equal(*a, b->prefix) ||        /* Network address */
79
                  ipa_equal(*a, b->brd))        /* Broadcast */
80
                return -1;
81
              return b->scope;
82
            }
83
        }
84
      }
85
  return -1;
86
}
87

    
88
/**
89
 * neigh_find - find or create a neighbor entry.
90
 * @p: protocol which asks for the entry.
91
 * @a: pointer to IP address of the node to be searched for.
92
 * @flags: 0 or %NEF_STICKY if you want to create a sticky entry.
93
 *
94
 * Search the neighbor cache for a node with given IP address. If
95
 * it's found, a pointer to the neighbor entry is returned. If no
96
 * such entry exists and the node is directly connected on
97
 * one of our active interfaces, a new entry is created and returned
98
 * to the caller with protocol-dependent fields initialized to zero.
99
 * If the node is not connected directly or *@a is not a valid unicast
100
 * IP address, neigh_find() returns %NULL.
101
 */
102

    
103
neighbor *
104
neigh_find(struct proto *p, ip_addr *a, unsigned flags)
105
{
106
  return neigh_find2(p, a, NULL, flags);
107
}
108

    
109
neighbor *
110
neigh_find2(struct proto *p, ip_addr *a, unsigned flags)
111
{
112
  neighbor *n;
113
  int class, scope = SCOPE_HOST;
114
  unsigned int h = neigh_hash(p, a);
115
  struct iface *i, *j;
116

    
117
  WALK_LIST(n, neigh_hash_table[h])        /* Search the cache */
118
    if (n->proto == p && ipa_equal(*a, n->addr))
119
      return n;
120

    
121
  class = ipa_classify(*a);
122
  if (class < 0)                        /* Invalid address */
123
    return NULL;
124
  if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
125
      !(class & IADDR_HOST))
126
    return NULL;                        /* Bad scope or a somecast */
127

    
128
  j = NULL;
129
  WALK_LIST(i, iface_list)
130
    if ((scope = if_connected(a, i)) >= 0)
131
      {
132
        j = i;
133
        break;
134
      }
135
  if (!j && !(flags & NEF_STICKY))
136
    return NULL;
137

    
138
  n = sl_alloc(neigh_slab);
139
  n->addr = *a;
140
  n->iface = j;
141
  if (j)
142
    {
143
      add_tail(&neigh_hash_table[h], &n->n);
144
      add_tail(&j->neighbors, &n->if_n);
145
    }
146
  else
147
    {
148
      add_tail(&sticky_neigh_list, &n->n);
149
      scope = 0;
150
    }
151
  n->proto = p;
152
  n->data = NULL;
153
  n->aux = 0;
154
  n->flags = flags;
155
  n->scope = scope;
156
  return n;
157
}
158

    
159
/**
160
 * neigh_dump - dump specified neighbor entry.
161
 * @n: the entry to dump
162
 *
163
 * This functions dumps the contents of a given neighbor entry
164
 * to debug output.
165
 */
166
void
167
neigh_dump(neighbor *n)
168
{
169
  debug("%p %I ", n, n->addr);
170
  if (n->iface)
171
    debug("%s ", n->iface->name);
172
  else
173
    debug("[] ");
174
  debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
175
  if (n->flags & NEF_STICKY)
176
    debug(" STICKY");
177
  debug("\n");
178
}
179

    
180
/**
181
 * neigh_dump_all - dump all neighbor entries.
182
 *
183
 * This function dumps the contents of the neighbor cache to
184
 * debug output.
185
 */
186
void
187
neigh_dump_all(void)
188
{
189
  neighbor *n;
190
  int i;
191

    
192
  debug("Known neighbors:\n");
193
  WALK_LIST(n, sticky_neigh_list)
194
    neigh_dump(n);
195
  for(i=0; i<NEIGH_HASH_SIZE; i++)
196
    WALK_LIST(n, neigh_hash_table[i])
197
      neigh_dump(n);
198
  debug("\n");
199
}
200

    
201
/**
202
 * neigh_if_up: notify neighbor cache about interface up event
203
 * @i: interface in question
204
 *
205
 * Tell the neighbor cache that a new interface became up.
206
 *
207
 * The neighbor cache wakes up all inactive sticky neighbors with
208
 * addresses belonging to prefixes of the interface @i.
209
 */
210
void
211
neigh_if_up(struct iface *i)
212
{
213
  neighbor *n, *next;
214
  int scope;
215

    
216
  WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
217
    if ((scope = if_connected(&n->addr, i)) >= 0)
218
      {
219
        n->iface = i;
220
        n->scope = scope;
221
        add_tail(&i->neighbors, &n->if_n);
222
        rem_node(&n->n);
223
        add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
224
        DBG("Waking up sticky neighbor %I\n", n->addr);
225
        if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
226
          n->proto->neigh_notify(n);
227
      }
228
}
229

    
230
/**
231
 * neigh_if_down - notify neighbor cache about interface down event
232
 * @i: the interface in question
233
 *
234
 * Notify the neighbor cache that an interface has ceased to exist.
235
 *
236
 * It causes all entries belonging to neighbors connected to this interface
237
 * to be flushed.
238
 */
239
void
240
neigh_if_down(struct iface *i)
241
{
242
  node *x, *y;
243

    
244
  WALK_LIST_DELSAFE(x, y, i->neighbors)
245
    {
246
      neighbor *n = SKIP_BACK(neighbor, if_n, x);
247
      DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
248
      rem_node(&n->if_n);
249
      n->iface = NULL;
250
      if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
251
        n->proto->neigh_notify(n);
252
      rem_node(&n->n);
253
      if (n->flags & NEF_STICKY)
254
        add_tail(&sticky_neigh_list, &n->n);
255
      else
256
        sl_free(neigh_slab, n);
257
    }
258
}
259

    
260
static inline void
261
neigh_prune_one(neighbor *n)
262
{
263
  if (n->proto->proto_state != PS_DOWN)
264
    return;
265
  rem_node(&n->n);
266
  if (n->iface)
267
    rem_node(&n->if_n);
268
  sl_free(neigh_slab, n);
269
}
270

    
271
/**
272
 * neigh_prune - prune neighbor cache
273
 *
274
 * neigh_prune() examines all neighbor entries cached and removes those
275
 * corresponding to inactive protocols. It's called whenever a protocol
276
 * is shut down to get rid of all its heritage.
277
 */
278
void
279
neigh_prune(void)
280
{
281
  neighbor *n;
282
  node *m;
283
  int i;
284

    
285
  DBG("Pruning neighbors\n");
286
  for(i=0; i<NEIGH_HASH_SIZE; i++)
287
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
288
      neigh_prune_one(n);
289
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
290
    neigh_prune_one(n);
291
}
292

    
293
/**
294
 * neigh_init - initialize the neighbor cache.
295
 * @if_pool: resource pool to be used for neighbor entries.
296
 *
297
 * This function is called during BIRD startup to initialize
298
 * the neighbor cache module.
299
 */
300
void
301
neigh_init(pool *if_pool)
302
{
303
  int i;
304

    
305
  neigh_slab = sl_new(if_pool, sizeof(neighbor));
306
  init_list(&sticky_neigh_list);
307
  for(i=0; i<NEIGH_HASH_SIZE; i++)
308
    init_list(&neigh_hash_table[i]);
309
}