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