]>
Commit | Line | Data |
---|---|---|
85053fce MM |
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 | ||
1f495723 MM |
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 | |
58f7d004 | 23 | * address is set to %SCOPE_HOST) together with per-neighbor data belonging to a |
1f495723 MM |
24 | * single protocol. |
25 | * | |
26 | * Active entries represent known neighbors and are stored in a hash | |
58f7d004 | 27 | * table (to allow fast retrieval based on the IP address of the node) and |
1f495723 MM |
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 | |
58f7d004 | 33 | * whenever an interface changes its state to up. |
1f495723 MM |
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 | ||
6b9fa320 | 40 | #undef LOCAL_DEBUG |
85053fce MM |
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 | ||
200accf3 | 58 | static int |
2d0b7e24 | 59 | if_connected(ip_addr *a, struct iface *i, struct ifa **ap) |
85053fce MM |
60 | { |
61 | struct ifa *b; | |
62 | ||
63 | if (!(i->flags & IF_UP)) | |
2d0b7e24 OZ |
64 | { |
65 | *ap = NULL; | |
0f32f2a6 | 66 | return -1; |
2d0b7e24 OZ |
67 | } |
68 | ||
85053fce MM |
69 | WALK_LIST(b, i->addrs) |
70 | { | |
2d0b7e24 OZ |
71 | *ap = b; |
72 | ||
85053fce | 73 | if (ipa_equal(*a, b->ip)) |
0f32f2a6 | 74 | return SCOPE_HOST; |
52a43ae3 | 75 | if (b->flags & IA_PEER) |
85053fce MM |
76 | { |
77 | if (ipa_equal(*a, b->opposite)) | |
0f32f2a6 | 78 | return b->scope; |
85053fce MM |
79 | } |
80 | else | |
81 | { | |
82 | if (ipa_in_net(*a, b->prefix, b->pxlen)) | |
83 | { | |
ba321706 OZ |
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 */ | |
2d0b7e24 OZ |
88 | { |
89 | *ap = NULL; | |
85053fce | 90 | return -1; |
2d0b7e24 | 91 | } |
ba321706 OZ |
92 | #endif |
93 | ||
0f32f2a6 | 94 | return b->scope; |
85053fce MM |
95 | } |
96 | } | |
97 | } | |
2d0b7e24 OZ |
98 | |
99 | *ap = NULL; | |
0f32f2a6 | 100 | return -1; |
85053fce MM |
101 | } |
102 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
117 | neighbor * |
118 | neigh_find(struct proto *p, ip_addr *a, unsigned flags) | |
061ab802 OZ |
119 | { |
120 | return neigh_find2(p, a, NULL, flags); | |
121 | } | |
be862406 | 122 | |
061ab802 OZ |
123 | |
124 | neighbor * | |
be862406 | 125 | neigh_find2(struct proto *p, ip_addr *a, struct iface *ifa, unsigned flags) |
85053fce MM |
126 | { |
127 | neighbor *n; | |
8ecbaf9c | 128 | int class, scope = -1; |
85053fce | 129 | unsigned int h = neigh_hash(p, a); |
be862406 | 130 | struct iface *i; |
2d0b7e24 | 131 | struct ifa *addr; |
85053fce MM |
132 | |
133 | WALK_LIST(n, neigh_hash_table[h]) /* Search the cache */ | |
ff2857b0 | 134 | if (n->proto == p && ipa_equal(*a, n->addr) && (!ifa || (ifa == n->iface))) |
85053fce MM |
135 | return n; |
136 | ||
137 | class = ipa_classify(*a); | |
138 | if (class < 0) /* Invalid address */ | |
139 | return NULL; | |
be862406 OZ |
140 | if (((class & IADDR_SCOPE_MASK) == SCOPE_HOST) || |
141 | (((class & IADDR_SCOPE_MASK) == SCOPE_LINK) && (ifa == NULL)) || | |
85053fce MM |
142 | !(class & IADDR_HOST)) |
143 | return NULL; /* Bad scope or a somecast */ | |
144 | ||
be862406 | 145 | if (ifa) |
ff2857b0 | 146 | { |
2d0b7e24 | 147 | scope = if_connected(a, ifa, &addr); |
69a8259c | 148 | flags |= NEF_BIND; |
ff2857b0 OZ |
149 | |
150 | if ((scope < 0) && (flags & NEF_ONLINK)) | |
151 | scope = class & IADDR_SCOPE_MASK; | |
152 | } | |
be862406 OZ |
153 | else |
154 | WALK_LIST(i, iface_list) | |
2d0b7e24 | 155 | if ((scope = if_connected(a, i, &addr)) >= 0) |
be862406 OZ |
156 | { |
157 | ifa = i; | |
158 | break; | |
159 | } | |
160 | ||
ff2857b0 OZ |
161 | /* scope < 0 means i don't know neighbor */ |
162 | /* scope >= 0 implies ifa != NULL */ | |
163 | ||
164 | if ((scope < 0) && !(flags & NEF_STICKY)) | |
85053fce MM |
165 | return NULL; |
166 | ||
167 | n = sl_alloc(neigh_slab); | |
168 | n->addr = *a; | |
ff2857b0 | 169 | if (scope >= 0) |
85053fce MM |
170 | { |
171 | add_tail(&neigh_hash_table[h], &n->n); | |
be862406 | 172 | add_tail(&ifa->neighbors, &n->if_n); |
85053fce MM |
173 | } |
174 | else | |
a9aa4c1e MM |
175 | { |
176 | add_tail(&sticky_neigh_list, &n->n); | |
9d67ffb0 | 177 | scope = -1; |
a9aa4c1e | 178 | } |
ff2857b0 | 179 | n->iface = ifa; |
2d0b7e24 | 180 | n->ifa = addr; |
85053fce MM |
181 | n->proto = p; |
182 | n->data = NULL; | |
183 | n->aux = 0; | |
184 | n->flags = flags; | |
0f32f2a6 | 185 | n->scope = scope; |
85053fce MM |
186 | return n; |
187 | } | |
188 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
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("[] "); | |
0f32f2a6 | 204 | debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope)); |
85053fce MM |
205 | if (n->flags & NEF_STICKY) |
206 | debug(" STICKY"); | |
207 | debug("\n"); | |
208 | } | |
209 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
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++) | |
18c031fa MM |
226 | WALK_LIST(n, neigh_hash_table[i]) |
227 | neigh_dump(n); | |
85053fce MM |
228 | debug("\n"); |
229 | } | |
230 | ||
cf7f0645 | 231 | static void |
2d0b7e24 | 232 | neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a) |
cf7f0645 OZ |
233 | { |
234 | n->iface = i; | |
2d0b7e24 | 235 | n->ifa = a; |
cf7f0645 OZ |
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 | { | |
f83ce94d | 248 | DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name); |
cf7f0645 | 249 | rem_node(&n->if_n); |
69a8259c OZ |
250 | if (! (n->flags & NEF_BIND)) |
251 | n->iface = NULL; | |
2d0b7e24 | 252 | n->ifa = NULL; |
69a8259c | 253 | n->scope = -1; |
cf7f0645 OZ |
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) | |
8ecbaf9c OZ |
258 | { |
259 | add_tail(&sticky_neigh_list, &n->n); | |
260 | ||
261 | /* Respawn neighbor if there is another matching prefix */ | |
262 | struct iface *i; | |
2d0b7e24 | 263 | struct ifa *a; |
8ecbaf9c OZ |
264 | int scope; |
265 | ||
266 | if (!n->iface) | |
267 | WALK_LIST(i, iface_list) | |
2d0b7e24 | 268 | if ((scope = if_connected(&n->addr, i, &a)) >= 0) |
8ecbaf9c | 269 | { |
2d0b7e24 | 270 | neigh_up(n, i, scope, a); |
8ecbaf9c OZ |
271 | return; |
272 | } | |
273 | } | |
cf7f0645 OZ |
274 | else |
275 | sl_free(neigh_slab, n); | |
276 | } | |
277 | ||
278 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
288 | void |
289 | neigh_if_up(struct iface *i) | |
290 | { | |
2d0b7e24 | 291 | struct ifa *a; |
85053fce | 292 | neighbor *n, *next; |
0f32f2a6 | 293 | int scope; |
85053fce MM |
294 | |
295 | WALK_LIST_DELSAFE(n, next, sticky_neigh_list) | |
69a8259c | 296 | if ((!n->iface || n->iface == i) && |
2d0b7e24 OZ |
297 | ((scope = if_connected(&n->addr, i, &a)) >= 0)) |
298 | neigh_up(n, i, scope, a); | |
85053fce MM |
299 | } |
300 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
310 | void |
311 | neigh_if_down(struct iface *i) | |
312 | { | |
313 | node *x, *y; | |
314 | ||
315 | WALK_LIST_DELSAFE(x, y, i->neighbors) | |
cf7f0645 | 316 | neigh_down(SKIP_BACK(neighbor, if_n, x)); |
85053fce MM |
317 | } |
318 | ||
fe181e7c OZ |
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 | */ | |
fe181e7c OZ |
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 | ||
cf7f0645 OZ |
340 | /** |
341 | * neigh_ifa_update: notify neighbor cache about interface address add or remove event | |
342 | * @ifa: 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 | { | |
2d0b7e24 | 359 | struct ifa *aa; |
cf7f0645 | 360 | neighbor *n = SKIP_BACK(neighbor, if_n, x); |
2d0b7e24 | 361 | if (if_connected(&n->addr, i, &aa) != n->scope) |
cf7f0645 OZ |
362 | neigh_down(n); |
363 | } | |
364 | ||
365 | /* Wake up all sticky neighbors that are reachable now */ | |
366 | neigh_if_up(i); | |
367 | } | |
368 | ||
18c031fa MM |
369 | static inline void |
370 | neigh_prune_one(neighbor *n) | |
371 | { | |
d6a836f8 | 372 | if (n->proto->proto_state != PS_DOWN) |
18c031fa MM |
373 | return; |
374 | rem_node(&n->n); | |
69a8259c | 375 | if (n->scope >= 0) |
18c031fa MM |
376 | rem_node(&n->if_n); |
377 | sl_free(neigh_slab, n); | |
378 | } | |
379 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
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]) | |
18c031fa MM |
397 | neigh_prune_one(n); |
398 | WALK_LIST_DELSAFE(n, m, sticky_neigh_list) | |
399 | neigh_prune_one(n); | |
85053fce MM |
400 | } |
401 | ||
1f495723 MM |
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 | */ | |
85053fce MM |
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 | } |