Annotation of embedaddon/quagga/ospf6d/ospf6_lsdb.c, revision 1.1.1.1
1.1 misho 1: /*
2: * Copyright (C) 2003 Yasuhiro Ohara
3: *
4: * This file is part of GNU Zebra.
5: *
6: * GNU Zebra is free software; you can redistribute it and/or modify it
7: * under the terms of the GNU General Public License as published by the
8: * Free Software Foundation; either version 2, or (at your option) any
9: * later version.
10: *
11: * GNU Zebra is distributed in the hope that it will be useful, but
12: * WITHOUT ANY WARRANTY; without even the implied warranty of
13: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: * General Public License for more details.
15: *
16: * You should have received a copy of the GNU General Public License
17: * along with GNU Zebra; see the file COPYING. If not, write to the
18: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19: * Boston, MA 02111-1307, USA.
20: */
21:
22: #include <zebra.h>
23:
24: #include "memory.h"
25: #include "log.h"
26: #include "command.h"
27: #include "prefix.h"
28: #include "table.h"
29: #include "vty.h"
30:
31: #include "ospf6_proto.h"
32: #include "ospf6_lsa.h"
33: #include "ospf6_lsdb.h"
34: #include "ospf6d.h"
35:
36: struct ospf6_lsdb *
37: ospf6_lsdb_create (void *data)
38: {
39: struct ospf6_lsdb *lsdb;
40:
41: lsdb = XCALLOC (MTYPE_OSPF6_LSDB, sizeof (struct ospf6_lsdb));
42: if (lsdb == NULL)
43: {
44: zlog_warn ("Can't malloc lsdb");
45: return NULL;
46: }
47: memset (lsdb, 0, sizeof (struct ospf6_lsdb));
48:
49: lsdb->data = data;
50: lsdb->table = route_table_init ();
51: return lsdb;
52: }
53:
54: void
55: ospf6_lsdb_delete (struct ospf6_lsdb *lsdb)
56: {
57: ospf6_lsdb_remove_all (lsdb);
58: route_table_finish (lsdb->table);
59: XFREE (MTYPE_OSPF6_LSDB, lsdb);
60: }
61:
62: static void
63: ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len)
64: {
65: assert (key->prefixlen % 8 == 0);
66:
67: memcpy ((caddr_t) &key->prefix + key->prefixlen / 8,
68: (caddr_t) value, len);
69: key->family = AF_INET6;
70: key->prefixlen += len * 8;
71: }
72:
73: #ifndef NDEBUG
74: static void
75: _lsdb_count_assert (struct ospf6_lsdb *lsdb)
76: {
77: struct ospf6_lsa *debug;
78: unsigned int num = 0;
79: for (debug = ospf6_lsdb_head (lsdb); debug;
80: debug = ospf6_lsdb_next (debug))
81: num++;
82:
83: if (num == lsdb->count)
84: return;
85:
86: zlog_debug ("PANIC !! lsdb[%p]->count = %d, real = %d",
87: lsdb, lsdb->count, num);
88: for (debug = ospf6_lsdb_head (lsdb); debug;
89: debug = ospf6_lsdb_next (debug))
90: zlog_debug ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name,
91: debug->lsdb);
92: zlog_debug ("DUMP END");
93:
94: assert (num == lsdb->count);
95: }
96: #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
97: #else /*NDEBUG*/
98: #define ospf6_lsdb_count_assert(t) ((void) 0)
99: #endif /*NDEBUG*/
100:
101: void
102: ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
103: {
104: struct prefix_ipv6 key;
105: struct route_node *current, *nextnode, *prevnode;
106: struct ospf6_lsa *next, *prev, *old = NULL;
107:
108: memset (&key, 0, sizeof (key));
109: ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
110: ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
111: sizeof (lsa->header->adv_router));
112: ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
113:
114: current = route_node_get (lsdb->table, (struct prefix *) &key);
115: old = current->info;
116: current->info = lsa;
117: ospf6_lsa_lock (lsa);
118:
119: if (old)
120: {
121: if (old->prev)
122: old->prev->next = lsa;
123: if (old->next)
124: old->next->prev = lsa;
125: lsa->next = old->next;
126: lsa->prev = old->prev;
127: }
128: else
129: {
130: /* next link */
131: nextnode = current;
132: route_lock_node (nextnode);
133: do {
134: nextnode = route_next (nextnode);
135: } while (nextnode && nextnode->info == NULL);
136: if (nextnode == NULL)
137: lsa->next = NULL;
138: else
139: {
140: next = nextnode->info;
141: lsa->next = next;
142: next->prev = lsa;
143: route_unlock_node (nextnode);
144: }
145:
146: /* prev link */
147: prevnode = current;
148: route_lock_node (prevnode);
149: do {
150: prevnode = route_prev (prevnode);
151: } while (prevnode && prevnode->info == NULL);
152: if (prevnode == NULL)
153: lsa->prev = NULL;
154: else
155: {
156: prev = prevnode->info;
157: lsa->prev = prev;
158: prev->next = lsa;
159: route_unlock_node (prevnode);
160: }
161:
162: lsdb->count++;
163: }
164:
165: if (old)
166: {
167: if (OSPF6_LSA_IS_CHANGED (old, lsa))
168: {
169: if (OSPF6_LSA_IS_MAXAGE (lsa))
170: {
171: if (lsdb->hook_remove)
172: {
173: (*lsdb->hook_remove) (old);
174: (*lsdb->hook_remove) (lsa);
175: }
176: }
177: else if (OSPF6_LSA_IS_MAXAGE (old))
178: {
179: if (lsdb->hook_add)
180: (*lsdb->hook_add) (lsa);
181: }
182: else
183: {
184: if (lsdb->hook_remove)
185: (*lsdb->hook_remove) (old);
186: if (lsdb->hook_add)
187: (*lsdb->hook_add) (lsa);
188: }
189: }
190: }
191: else if (OSPF6_LSA_IS_MAXAGE (lsa))
192: {
193: if (lsdb->hook_remove)
194: (*lsdb->hook_remove) (lsa);
195: }
196: else
197: {
198: if (lsdb->hook_add)
199: (*lsdb->hook_add) (lsa);
200: }
201:
202: if (old)
203: ospf6_lsa_unlock (old);
204:
205: ospf6_lsdb_count_assert (lsdb);
206: }
207:
208: void
209: ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
210: {
211: struct route_node *node;
212: struct prefix_ipv6 key;
213:
214: memset (&key, 0, sizeof (key));
215: ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
216: ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
217: sizeof (lsa->header->adv_router));
218: ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
219:
220: node = route_node_lookup (lsdb->table, (struct prefix *) &key);
221: assert (node && node->info == lsa);
222:
223: if (lsa->prev)
224: lsa->prev->next = lsa->next;
225: if (lsa->next)
226: lsa->next->prev = lsa->prev;
227:
228: node->info = NULL;
229: lsdb->count--;
230:
231: if (lsdb->hook_remove)
232: (*lsdb->hook_remove) (lsa);
233:
234: ospf6_lsa_unlock (lsa);
235: route_unlock_node (node);
236:
237: ospf6_lsdb_count_assert (lsdb);
238: }
239:
240: struct ospf6_lsa *
241: ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
242: struct ospf6_lsdb *lsdb)
243: {
244: struct route_node *node;
245: struct prefix_ipv6 key;
246:
247: if (lsdb == NULL)
248: return NULL;
249:
250: memset (&key, 0, sizeof (key));
251: ospf6_lsdb_set_key (&key, &type, sizeof (type));
252: ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
253: ospf6_lsdb_set_key (&key, &id, sizeof (id));
254:
255: node = route_node_lookup (lsdb->table, (struct prefix *) &key);
256: if (node == NULL || node->info == NULL)
257: return NULL;
258: return (struct ospf6_lsa *) node->info;
259: }
260:
261: struct ospf6_lsa *
262: ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
263: struct ospf6_lsdb *lsdb)
264: {
265: struct route_node *node;
266: struct route_node *matched = NULL;
267: struct prefix_ipv6 key;
268: struct prefix *p;
269:
270: if (lsdb == NULL)
271: return NULL;
272:
273: memset (&key, 0, sizeof (key));
274: ospf6_lsdb_set_key (&key, &type, sizeof (type));
275: ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
276: ospf6_lsdb_set_key (&key, &id, sizeof (id));
277: p = (struct prefix *) &key;
278:
279: {
280: char buf[64];
281: prefix2str (p, buf, sizeof (buf));
282: zlog_debug ("lsdb_lookup_next: key: %s", buf);
283: }
284:
285: node = lsdb->table->top;
286: /* walk down tree. */
287: while (node && node->p.prefixlen <= p->prefixlen &&
288: prefix_match (&node->p, p))
289: {
290: matched = node;
291: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
292: }
293:
294: if (matched)
295: node = matched;
296: else
297: node = lsdb->table->top;
298: route_lock_node (node);
299:
300: /* skip to real existing entry */
301: while (node && node->info == NULL)
302: node = route_next (node);
303:
304: if (! node)
305: return NULL;
306:
307: if (prefix_same (&node->p, p))
308: {
309: struct route_node *prev = node;
310: struct ospf6_lsa *lsa_prev;
311: struct ospf6_lsa *lsa_next;
312:
313: node = route_next (node);
314: while (node && node->info == NULL)
315: node = route_next (node);
316:
317: lsa_prev = prev->info;
318: lsa_next = (node ? node->info : NULL);
319: assert (lsa_prev);
320: assert (lsa_prev->next == lsa_next);
321: if (lsa_next)
322: assert (lsa_next->prev == lsa_prev);
323: zlog_debug ("lsdb_lookup_next: assert OK with previous LSA");
324: }
325:
326: if (! node)
327: return NULL;
328:
329: route_unlock_node (node);
330: return (struct ospf6_lsa *) node->info;
331: }
332:
333: /* Iteration function */
334: struct ospf6_lsa *
335: ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
336: {
337: struct route_node *node;
338:
339: node = route_top (lsdb->table);
340: if (node == NULL)
341: return NULL;
342:
343: /* skip to the existing lsdb entry */
344: while (node && node->info == NULL)
345: node = route_next (node);
346: if (node == NULL)
347: return NULL;
348:
349: route_unlock_node (node);
350: if (node->info)
351: ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
352: return (struct ospf6_lsa *) node->info;
353: }
354:
355: struct ospf6_lsa *
356: ospf6_lsdb_next (struct ospf6_lsa *lsa)
357: {
358: struct ospf6_lsa *next = lsa->next;
359:
360: ospf6_lsa_unlock (lsa);
361: if (next)
362: ospf6_lsa_lock (next);
363:
364: return next;
365: }
366:
367: struct ospf6_lsa *
368: ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
369: struct ospf6_lsdb *lsdb)
370: {
371: struct route_node *node;
372: struct prefix_ipv6 key;
373: struct ospf6_lsa *lsa;
374:
375: memset (&key, 0, sizeof (key));
376: ospf6_lsdb_set_key (&key, &type, sizeof (type));
377: ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
378:
379: node = lsdb->table->top;
380:
381: /* Walk down tree. */
382: while (node && node->p.prefixlen <= key.prefixlen &&
383: prefix_match (&node->p, (struct prefix *) &key))
384: node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)];
385:
386: if (node)
387: route_lock_node (node);
388: while (node && node->info == NULL)
389: node = route_next (node);
390:
391: if (node == NULL)
392: return NULL;
393: else
394: route_unlock_node (node);
395:
396: if (! prefix_match ((struct prefix *) &key, &node->p))
397: return NULL;
398:
399: lsa = node->info;
400: ospf6_lsa_lock (lsa);
401:
402: return lsa;
403: }
404:
405: struct ospf6_lsa *
406: ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
407: struct ospf6_lsa *lsa)
408: {
409: struct ospf6_lsa *next = lsa->next;
410:
411: if (next)
412: {
413: if (next->header->type != type ||
414: next->header->adv_router != adv_router)
415: next = NULL;
416: }
417:
418: if (next)
419: ospf6_lsa_lock (next);
420: ospf6_lsa_unlock (lsa);
421: return next;
422: }
423:
424: struct ospf6_lsa *
425: ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
426: {
427: struct route_node *node;
428: struct prefix_ipv6 key;
429: struct ospf6_lsa *lsa;
430:
431: memset (&key, 0, sizeof (key));
432: ospf6_lsdb_set_key (&key, &type, sizeof (type));
433:
434: /* Walk down tree. */
435: node = lsdb->table->top;
436: while (node && node->p.prefixlen <= key.prefixlen &&
437: prefix_match (&node->p, (struct prefix *) &key))
438: node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)];
439:
440: if (node)
441: route_lock_node (node);
442: while (node && node->info == NULL)
443: node = route_next (node);
444:
445: if (node == NULL)
446: return NULL;
447: else
448: route_unlock_node (node);
449:
450: if (! prefix_match ((struct prefix *) &key, &node->p))
451: return NULL;
452:
453: lsa = node->info;
454: ospf6_lsa_lock (lsa);
455:
456: return lsa;
457: }
458:
459: struct ospf6_lsa *
460: ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
461: {
462: struct ospf6_lsa *next = lsa->next;
463:
464: if (next)
465: {
466: if (next->header->type != type)
467: next = NULL;
468: }
469:
470: if (next)
471: ospf6_lsa_lock (next);
472: ospf6_lsa_unlock (lsa);
473: return next;
474: }
475:
476: void
477: ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
478: {
479: struct ospf6_lsa *lsa;
480: for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
481: ospf6_lsdb_remove (lsa, lsdb);
482: }
483:
484: void
485: ospf6_lsdb_show (struct vty *vty, int level,
486: u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
487: struct ospf6_lsdb *lsdb)
488: {
489: struct ospf6_lsa *lsa;
490: void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
491:
492: if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
493: showfunc = ospf6_lsa_show_summary;
494: else if (level == OSPF6_LSDB_SHOW_LEVEL_DETAIL)
495: showfunc = ospf6_lsa_show;
496: else if (level == OSPF6_LSDB_SHOW_LEVEL_INTERNAL)
497: showfunc = ospf6_lsa_show_internal;
498: else if (level == OSPF6_LSDB_SHOW_LEVEL_DUMP)
499: showfunc = ospf6_lsa_show_dump;
500:
501: if (type && id && adv_router)
502: {
503: lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
504: if (lsa)
505: {
506: if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
507: ospf6_lsa_show (vty, lsa);
508: else
509: (*showfunc) (vty, lsa);
510: }
511: return;
512: }
513:
514: if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
515: ospf6_lsa_show_summary_header (vty);
516:
517: if (type && adv_router)
518: lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
519: else if (type)
520: lsa = ospf6_lsdb_type_head (*type, lsdb);
521: else
522: lsa = ospf6_lsdb_head (lsdb);
523: while (lsa)
524: {
525: if ((! adv_router || lsa->header->adv_router == *adv_router) &&
526: (! id || lsa->header->id == *id))
527: (*showfunc) (vty, lsa);
528:
529: if (type && adv_router)
530: lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
531: else if (type)
532: lsa = ospf6_lsdb_type_next (*type, lsa);
533: else
534: lsa = ospf6_lsdb_next (lsa);
535: }
536: }
537:
538: /* Decide new Link State ID to originate.
539: note return value is network byte order */
540: u_int32_t
541: ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
542: struct ospf6_lsdb *lsdb)
543: {
544: struct ospf6_lsa *lsa;
545: u_int32_t id = 1;
546:
547: for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
548: lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
549: {
550: if (ntohl (lsa->header->id) < id)
551: continue;
552: if (ntohl (lsa->header->id) > id)
553: {
554: ospf6_lsa_unlock (lsa);
555: break;
556: }
557: id++;
558: }
559:
560: return ((u_int32_t) htonl (id));
561: }
562:
563: /* Decide new LS sequence number to originate.
564: note return value is network byte order */
565: u_int32_t
566: ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
567: struct ospf6_lsdb *lsdb)
568: {
569: struct ospf6_lsa *lsa;
570: signed long seqnum = 0;
571:
572: /* if current database copy not found, return InitialSequenceNumber */
573: lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
574: if (lsa == NULL)
575: seqnum = INITIAL_SEQUENCE_NUMBER;
576: else
577: seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
578:
579: return ((u_int32_t) htonl (seqnum));
580: }
581:
582:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to ospf6_lsdb.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / ospf6d