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. Neighbor entry VRF
34: * association is implied by respective protocol.
35: *
36: * When a neighbor event occurs (a neighbor gets disconnected or a sticky
37: * inactive neighbor becomes connected), the protocol hook neigh_notify()
38: * is called to advertise the change.
39: */
40:
41: #undef LOCAL_DEBUG
42:
43: #include "nest/bird.h"
44: #include "nest/iface.h"
45: #include "nest/protocol.h"
46: #include "lib/resource.h"
47:
48: #define NEIGH_HASH_SIZE 256
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_SIZE-1);
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_net(*a, b->prefix, b->pxlen))
84: {
85: #ifndef IPV6
86: if ((b->pxlen < (BITS_PER_IP_ADDRESS - 1)) &&
87: (ipa_equal(*a, b->prefix) || /* Network address */
88: ipa_equal(*a, b->brd))) /* Broadcast */
89: {
90: *ap = NULL;
91: return -1;
92: }
93: #endif
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 ((!p->vrf_set || p->vrf == i->master) &&
157: ((scope = if_connected(a, i, &addr)) >= 0))
158: {
159: ifa = i;
160: break;
161: }
162:
163: /* scope < 0 means i don't know neighbor */
164: /* scope >= 0 implies ifa != NULL */
165:
166: if ((scope < 0) && !(flags & NEF_STICKY))
167: return NULL;
168:
169: n = sl_alloc(neigh_slab);
170: n->addr = *a;
171: if (scope >= 0)
172: {
173: add_tail(&neigh_hash_table[h], &n->n);
174: add_tail(&ifa->neighbors, &n->if_n);
175: }
176: else
177: {
178: add_tail(&sticky_neigh_list, &n->n);
179: scope = -1;
180: }
181: n->iface = ifa;
182: n->ifa = addr;
183: n->proto = p;
184: n->data = NULL;
185: n->aux = 0;
186: n->flags = flags;
187: n->scope = scope;
188: return n;
189: }
190:
191: /**
192: * neigh_dump - dump specified neighbor entry.
193: * @n: the entry to dump
194: *
195: * This functions dumps the contents of a given neighbor entry
196: * to debug output.
197: */
198: void
199: neigh_dump(neighbor *n)
200: {
201: debug("%p %I ", n, n->addr);
202: if (n->iface)
203: debug("%s ", n->iface->name);
204: else
205: debug("[] ");
206: debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
207: if (n->flags & NEF_STICKY)
208: debug(" STICKY");
209: debug("\n");
210: }
211:
212: /**
213: * neigh_dump_all - dump all neighbor entries.
214: *
215: * This function dumps the contents of the neighbor cache to
216: * debug output.
217: */
218: void
219: neigh_dump_all(void)
220: {
221: neighbor *n;
222: int i;
223:
224: debug("Known neighbors:\n");
225: WALK_LIST(n, sticky_neigh_list)
226: neigh_dump(n);
227: for(i=0; i<NEIGH_HASH_SIZE; i++)
228: WALK_LIST(n, neigh_hash_table[i])
229: neigh_dump(n);
230: debug("\n");
231: }
232:
233: static void
234: neigh_up(neighbor *n, struct iface *i, int scope, struct ifa *a)
235: {
236: n->iface = i;
237: n->ifa = a;
238: n->scope = scope;
239: add_tail(&i->neighbors, &n->if_n);
240: rem_node(&n->n);
241: add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
242: DBG("Waking up sticky neighbor %I\n", n->addr);
243: if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
244: n->proto->neigh_notify(n);
245: }
246:
247: static void
248: neigh_down(neighbor *n)
249: {
250: DBG("Flushing neighbor %I on %s\n", n->addr, n->iface->name);
251: rem_node(&n->if_n);
252: if (! (n->flags & NEF_BIND))
253: n->iface = NULL;
254: n->ifa = NULL;
255: n->scope = -1;
256: if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
257: n->proto->neigh_notify(n);
258: rem_node(&n->n);
259: if (n->flags & NEF_STICKY)
260: {
261: add_tail(&sticky_neigh_list, &n->n);
262:
263: /* Respawn neighbor if there is another matching prefix */
264: struct iface *i;
265: struct ifa *a;
266: int scope;
267:
268: if (!n->iface)
269: WALK_LIST(i, iface_list)
270: if ((scope = if_connected(&n->addr, i, &a)) >= 0)
271: {
272: neigh_up(n, i, scope, a);
273: return;
274: }
275: }
276: else
277: sl_free(neigh_slab, n);
278: }
279:
280:
281: /**
282: * neigh_if_up: notify neighbor cache about interface up event
283: * @i: interface in question
284: *
285: * Tell the neighbor cache that a new interface became up.
286: *
287: * The neighbor cache wakes up all inactive sticky neighbors with
288: * addresses belonging to prefixes of the interface @i.
289: */
290: void
291: neigh_if_up(struct iface *i)
292: {
293: struct ifa *a;
294: neighbor *n, *next;
295: int scope;
296:
297: WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
298: if ((!n->iface || n->iface == i) &&
299: ((scope = if_connected(&n->addr, i, &a)) >= 0))
300: neigh_up(n, i, scope, a);
301: }
302:
303: /**
304: * neigh_if_down - notify neighbor cache about interface down event
305: * @i: the interface in question
306: *
307: * Notify the neighbor cache that an interface has ceased to exist.
308: *
309: * It causes all entries belonging to neighbors connected to this interface
310: * to be flushed.
311: */
312: void
313: neigh_if_down(struct iface *i)
314: {
315: node *x, *y;
316:
317: WALK_LIST_DELSAFE(x, y, i->neighbors)
318: neigh_down(SKIP_BACK(neighbor, if_n, x));
319: }
320:
321: /**
322: * neigh_if_link - notify neighbor cache about interface link change
323: * @i: the interface in question
324: *
325: * Notify the neighbor cache that an interface changed link state.
326: * All owners of neighbor entries connected to this interface are
327: * notified.
328: */
329: void
330: neigh_if_link(struct iface *i)
331: {
332: node *x, *y;
333:
334: WALK_LIST_DELSAFE(x, y, i->neighbors)
335: {
336: neighbor *n = SKIP_BACK(neighbor, if_n, x);
337: if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
338: n->proto->neigh_notify(n);
339: }
340: }
341:
342: /**
343: * neigh_ifa_update: notify neighbor cache about interface address add or remove event
344: * @a: interface address in question
345: *
346: * Tell the neighbor cache that an address was added or removed.
347: *
348: * The neighbor cache wakes up all inactive sticky neighbors with
349: * addresses belonging to prefixes of the interface belonging to @ifa
350: * and causes all unreachable neighbors to be flushed.
351: */
352: void
353: neigh_ifa_update(struct ifa *a)
354: {
355: struct iface *i = a->iface;
356: node *x, *y;
357:
358: /* Remove all neighbors whose scope has changed */
359: WALK_LIST_DELSAFE(x, y, i->neighbors)
360: {
361: struct ifa *aa;
362: neighbor *n = SKIP_BACK(neighbor, if_n, x);
363: if (if_connected(&n->addr, i, &aa) != n->scope)
364: neigh_down(n);
365: }
366:
367: /* Wake up all sticky neighbors that are reachable now */
368: neigh_if_up(i);
369: }
370:
371: static inline void
372: neigh_prune_one(neighbor *n)
373: {
374: if (n->proto->proto_state != PS_DOWN)
375: return;
376: rem_node(&n->n);
377: if (n->scope >= 0)
378: rem_node(&n->if_n);
379: sl_free(neigh_slab, n);
380: }
381:
382: /**
383: * neigh_prune - prune neighbor cache
384: *
385: * neigh_prune() examines all neighbor entries cached and removes those
386: * corresponding to inactive protocols. It's called whenever a protocol
387: * is shut down to get rid of all its heritage.
388: */
389: void
390: neigh_prune(void)
391: {
392: neighbor *n;
393: node *m;
394: int i;
395:
396: DBG("Pruning neighbors\n");
397: for(i=0; i<NEIGH_HASH_SIZE; i++)
398: WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
399: neigh_prune_one(n);
400: WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
401: neigh_prune_one(n);
402: }
403:
404: /**
405: * neigh_init - initialize the neighbor cache.
406: * @if_pool: resource pool to be used for neighbor entries.
407: *
408: * This function is called during BIRD startup to initialize
409: * the neighbor cache module.
410: */
411: void
412: neigh_init(pool *if_pool)
413: {
414: int i;
415:
416: neigh_slab = sl_new(if_pool, sizeof(neighbor));
417: init_list(&sticky_neigh_list);
418: for(i=0; i<NEIGH_HASH_SIZE; i++)
419: init_list(&neigh_hash_table[i]);
420: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to neighbor.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / nest