Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (7.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.
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
  neighbor *n;
107
  int class, scope = SCOPE_HOST;
108
  unsigned int h = neigh_hash(p, a);
109
  struct iface *i, *j;
110

    
111
  WALK_LIST(n, neigh_hash_table[h])        /* Search the cache */
112
    if (n->proto == p && ipa_equal(*a, n->addr))
113
      return n;
114

    
115
  class = ipa_classify(*a);
116
  if (class < 0)                        /* Invalid address */
117
    return NULL;
118
  if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
119
      !(class & IADDR_HOST))
120
    return NULL;                        /* Bad scope or a somecast */
121

    
122
  j = NULL;
123
  WALK_LIST(i, iface_list)
124
    if ((scope = if_connected(a, i)) >= 0)
125
      {
126
        j = i;
127
        break;
128
      }
129
  if (!j && !(flags & NEF_STICKY))
130
    return NULL;
131

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

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

    
174
/**
175
 * neigh_dump_all - dump all neighbor entries.
176
 *
177
 * This function dumps the contents of the neighbor cache to
178
 * debug output.
179
 */
180
void
181
neigh_dump_all(void)
182
{
183
  neighbor *n;
184
  int i;
185

    
186
  debug("Known neighbors:\n");
187
  WALK_LIST(n, sticky_neigh_list)
188
    neigh_dump(n);
189
  for(i=0; i<NEIGH_HASH_SIZE; i++)
190
    WALK_LIST(n, neigh_hash_table[i])
191
      neigh_dump(n);
192
  debug("\n");
193
}
194

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

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

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

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

    
254
static inline void
255
neigh_prune_one(neighbor *n)
256
{
257
  if (n->proto->proto_state != PS_DOWN)
258
    return;
259
  rem_node(&n->n);
260
  if (n->iface)
261
    rem_node(&n->if_n);
262
  sl_free(neigh_slab, n);
263
}
264

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

    
279
  DBG("Pruning neighbors\n");
280
  for(i=0; i<NEIGH_HASH_SIZE; i++)
281
    WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
282
      neigh_prune_one(n);
283
  WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
284
    neigh_prune_one(n);
285
}
286

    
287
/**
288
 * neigh_init - initialize the neighbor cache.
289
 * @if_pool: resource pool to be used for neighbor entries.
290
 *
291
 * This function is called during BIRD startup to initialize
292
 * the neighbor cache module.
293
 */
294
void
295
neigh_init(pool *if_pool)
296
{
297
  int i;
298

    
299
  neigh_slab = sl_new(if_pool, sizeof(neighbor));
300
  init_list(&sticky_neigh_list);
301
  for(i=0; i<NEIGH_HASH_SIZE; i++)
302
    init_list(&neigh_hash_table[i]);
303
}