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: if (lsdb != NULL)
58: {
59: ospf6_lsdb_remove_all (lsdb);
60: route_table_finish (lsdb->table);
61: XFREE (MTYPE_OSPF6_LSDB, lsdb);
62: }
63: }
64:
65: static void
66: ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len)
67: {
68: assert (key->prefixlen % 8 == 0);
69:
70: memcpy ((caddr_t) &key->prefix + key->prefixlen / 8,
71: (caddr_t) value, len);
72: key->family = AF_INET6;
73: key->prefixlen += len * 8;
74: }
75:
76: #ifdef DEBUG
77: static void
78: _lsdb_count_assert (struct ospf6_lsdb *lsdb)
79: {
80: struct ospf6_lsa *debug;
81: unsigned int num = 0;
82: for (debug = ospf6_lsdb_head (lsdb); debug;
83: debug = ospf6_lsdb_next (debug))
84: num++;
85:
86: if (num == lsdb->count)
87: return;
88:
89: zlog_debug ("PANIC !! lsdb[%p]->count = %d, real = %d",
90: lsdb, lsdb->count, num);
91: for (debug = ospf6_lsdb_head (lsdb); debug;
92: debug = ospf6_lsdb_next (debug))
93: zlog_debug ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name,
94: debug->lsdb);
95: zlog_debug ("DUMP END");
96:
97: assert (num == lsdb->count);
98: }
99: #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
100: #else /*DEBUG*/
101: #define ospf6_lsdb_count_assert(t) ((void) 0)
102: #endif /*DEBUG*/
103:
104: void
105: ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
106: {
107: struct prefix_ipv6 key;
108: struct route_node *current;
109: struct ospf6_lsa *old = NULL;
110:
111: memset (&key, 0, sizeof (key));
112: ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
113: ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
114: sizeof (lsa->header->adv_router));
115: ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
116:
117: current = route_node_get (lsdb->table, (struct prefix *) &key);
118: old = current->info;
119: current->info = lsa;
120: lsa->rn = current;
121: ospf6_lsa_lock (lsa);
122:
123: if (!old)
124: {
125: lsdb->count++;
126:
127: if (OSPF6_LSA_IS_MAXAGE (lsa))
128: {
129: if (lsdb->hook_remove)
130: (*lsdb->hook_remove) (lsa);
131: }
132: else
133: {
134: if (lsdb->hook_add)
135: (*lsdb->hook_add) (lsa);
136: }
137: }
138: else
139: {
140: if (OSPF6_LSA_IS_CHANGED (old, lsa))
141: {
142: if (OSPF6_LSA_IS_MAXAGE (lsa))
143: {
144: if (lsdb->hook_remove)
145: {
146: (*lsdb->hook_remove) (old);
147: (*lsdb->hook_remove) (lsa);
148: }
149: }
150: else if (OSPF6_LSA_IS_MAXAGE (old))
151: {
152: if (lsdb->hook_add)
153: (*lsdb->hook_add) (lsa);
154: }
155: else
156: {
157: if (lsdb->hook_remove)
158: (*lsdb->hook_remove) (old);
159: if (lsdb->hook_add)
160: (*lsdb->hook_add) (lsa);
161: }
162: }
163: ospf6_lsa_unlock (old);
164: }
165:
166: ospf6_lsdb_count_assert (lsdb);
167: }
168:
169: void
170: ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
171: {
172: struct route_node *node;
173: struct prefix_ipv6 key;
174:
175: memset (&key, 0, sizeof (key));
176: ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
177: ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
178: sizeof (lsa->header->adv_router));
179: ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
180:
181: node = route_node_lookup (lsdb->table, (struct prefix *) &key);
182: assert (node && node->info == lsa);
183:
184: node->info = NULL;
185: lsdb->count--;
186:
187: if (lsdb->hook_remove)
188: (*lsdb->hook_remove) (lsa);
189:
190: route_unlock_node (node); /* to free the lookup lock */
191: route_unlock_node (node); /* to free the original lock */
192: ospf6_lsa_unlock (lsa);
193:
194: ospf6_lsdb_count_assert (lsdb);
195: }
196:
197: struct ospf6_lsa *
198: ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
199: struct ospf6_lsdb *lsdb)
200: {
201: struct route_node *node;
202: struct prefix_ipv6 key;
203:
204: if (lsdb == NULL)
205: return NULL;
206:
207: memset (&key, 0, sizeof (key));
208: ospf6_lsdb_set_key (&key, &type, sizeof (type));
209: ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
210: ospf6_lsdb_set_key (&key, &id, sizeof (id));
211:
212: node = route_node_lookup (lsdb->table, (struct prefix *) &key);
213: if (node == NULL || node->info == NULL)
214: return NULL;
215:
216: route_unlock_node (node);
217: return (struct ospf6_lsa *) node->info;
218: }
219:
220: struct ospf6_lsa *
221: ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
222: struct ospf6_lsdb *lsdb)
223: {
224: struct route_node *node;
225: struct route_node *matched = NULL;
226: struct prefix_ipv6 key;
227: struct prefix *p;
228:
229: if (lsdb == NULL)
230: return NULL;
231:
232: memset (&key, 0, sizeof (key));
233: ospf6_lsdb_set_key (&key, &type, sizeof (type));
234: ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
235: ospf6_lsdb_set_key (&key, &id, sizeof (id));
236: p = (struct prefix *) &key;
237:
238: {
239: char buf[64];
240: prefix2str (p, buf, sizeof (buf));
241: zlog_debug ("lsdb_lookup_next: key: %s", buf);
242: }
243:
244: node = lsdb->table->top;
245: /* walk down tree. */
246: while (node && node->p.prefixlen <= p->prefixlen &&
247: prefix_match (&node->p, p))
248: {
249: matched = node;
250: node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
251: }
252:
253: if (matched)
254: node = matched;
255: else
256: node = lsdb->table->top;
257: route_lock_node (node);
258:
259: /* skip to real existing entry */
260: while (node && node->info == NULL)
261: node = route_next (node);
262:
263: if (! node)
264: return NULL;
265:
266: if (prefix_same (&node->p, p))
267: {
268: node = route_next (node);
269: while (node && node->info == NULL)
270: node = route_next (node);
271: }
272:
273: if (! node)
274: return NULL;
275:
276: route_unlock_node (node);
277: return (struct ospf6_lsa *) node->info;
278: }
279:
280: /* Iteration function */
281: struct ospf6_lsa *
282: ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
283: {
284: struct route_node *node;
285:
286: node = route_top (lsdb->table);
287: if (node == NULL)
288: return NULL;
289:
290: /* skip to the existing lsdb entry */
291: while (node && node->info == NULL)
292: node = route_next (node);
293: if (node == NULL)
294: return NULL;
295:
296: if (node->info)
297: ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
298: return (struct ospf6_lsa *) node->info;
299: }
300:
301: struct ospf6_lsa *
302: ospf6_lsdb_next (struct ospf6_lsa *lsa)
303: {
304: struct route_node *node = lsa->rn;
305: struct ospf6_lsa *next = NULL;
306:
307: do {
308: node = route_next (node);
309: } while (node && node->info == NULL);
310:
311: if ((node != NULL) && (node->info != NULL))
312: {
313: next = node->info;
314: ospf6_lsa_lock (next);
315: }
316:
317: ospf6_lsa_unlock (lsa);
318: return next;
319: }
320:
321: struct ospf6_lsa *
322: ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
323: struct ospf6_lsdb *lsdb)
324: {
325: struct route_node *node;
326: struct prefix_ipv6 key;
327: struct ospf6_lsa *lsa;
328:
329: memset (&key, 0, sizeof (key));
330: ospf6_lsdb_set_key (&key, &type, sizeof (type));
331: ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
332:
333: node = lsdb->table->top;
334:
335: /* Walk down tree. */
336: while (node && node->p.prefixlen <= key.prefixlen &&
337: prefix_match (&node->p, (struct prefix *) &key))
338: node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)];
339:
340: if (node)
341: route_lock_node (node);
342: while (node && node->info == NULL)
343: node = route_next (node);
344:
345: if (node == NULL)
346: return NULL;
347:
348: if (! prefix_match ((struct prefix *) &key, &node->p))
349: return NULL;
350:
351: lsa = node->info;
352: ospf6_lsa_lock (lsa);
353:
354: return lsa;
355: }
356:
357: struct ospf6_lsa *
358: ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
359: struct ospf6_lsa *lsa)
360: {
361: struct ospf6_lsa *next = ospf6_lsdb_next(lsa);
362:
363: if (next)
364: {
365: if (next->header->type != type ||
366: next->header->adv_router != adv_router)
367: {
368: route_unlock_node (next->rn);
369: ospf6_lsa_unlock (next);
370: next = NULL;
371: }
372: }
373:
374: return next;
375: }
376:
377: struct ospf6_lsa *
378: ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
379: {
380: struct route_node *node;
381: struct prefix_ipv6 key;
382: struct ospf6_lsa *lsa;
383:
384: memset (&key, 0, sizeof (key));
385: ospf6_lsdb_set_key (&key, &type, sizeof (type));
386:
387: /* Walk down tree. */
388: node = lsdb->table->top;
389: while (node && node->p.prefixlen <= key.prefixlen &&
390: prefix_match (&node->p, (struct prefix *) &key))
391: node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)];
392:
393: if (node)
394: route_lock_node (node);
395: while (node && node->info == NULL)
396: node = route_next (node);
397:
398: if (node == NULL)
399: return NULL;
400:
401: if (! prefix_match ((struct prefix *) &key, &node->p))
402: return NULL;
403:
404: lsa = node->info;
405: ospf6_lsa_lock (lsa);
406:
407: return lsa;
408: }
409:
410: struct ospf6_lsa *
411: ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
412: {
413: struct ospf6_lsa *next = ospf6_lsdb_next (lsa);
414:
415: if (next)
416: {
417: if (next->header->type != type)
418: {
419: route_unlock_node (next->rn);
420: ospf6_lsa_unlock (next);
421: next = NULL;
422: }
423: }
424:
425: return next;
426: }
427:
428: void
429: ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
430: {
431: struct ospf6_lsa *lsa;
432:
433: if (lsdb == NULL)
434: return;
435:
436: for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
437: ospf6_lsdb_remove (lsa, lsdb);
438: }
439:
440: void
441: ospf6_lsdb_lsa_unlock (struct ospf6_lsa *lsa)
442: {
443: if (lsa != NULL)
444: {
445: if (lsa->rn != NULL)
446: route_unlock_node (lsa->rn);
447: ospf6_lsa_unlock (lsa);
448: }
449: }
450:
451: int
452: ospf6_lsdb_maxage_remover (struct ospf6_lsdb *lsdb)
453: {
454: int reschedule = 0;
455: struct ospf6_lsa *lsa;
456:
457: for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
458: {
459: if (! OSPF6_LSA_IS_MAXAGE (lsa))
460: continue;
461: if (lsa->retrans_count != 0)
462: {
463: reschedule = 1;
464: continue;
465: }
466: if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type))
467: zlog_debug ("Remove MaxAge %s", lsa->name);
468: if (CHECK_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED))
469: {
470: UNSET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED);
471: /*
472: * lsa->header->age = 0;
473: */
474: lsa->header->seqnum = htonl(OSPF_MAX_SEQUENCE_NUMBER + 1);
475: ospf6_lsa_checksum (lsa->header);
476:
477: THREAD_OFF(lsa->refresh);
478: thread_execute (master, ospf6_lsa_refresh, lsa, 0);
479: } else {
480: ospf6_lsdb_remove (lsa, lsdb);
481: }
482: }
483:
484: return (reschedule);
485: }
486:
487: void
488: ospf6_lsdb_show (struct vty *vty, enum ospf_lsdb_show_level level,
489: u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
490: struct ospf6_lsdb *lsdb)
491: {
492: struct ospf6_lsa *lsa;
493: void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
494:
495: switch (level)
496: {
497: case OSPF6_LSDB_SHOW_LEVEL_DETAIL:
498: showfunc = ospf6_lsa_show;
499: break;
500: case OSPF6_LSDB_SHOW_LEVEL_INTERNAL:
501: showfunc = ospf6_lsa_show_internal;
502: break;
503: case OSPF6_LSDB_SHOW_LEVEL_DUMP:
504: showfunc = ospf6_lsa_show_dump;
505: break;
506: case OSPF6_LSDB_SHOW_LEVEL_NORMAL:
507: default:
508: showfunc = ospf6_lsa_show_summary;
509: }
510:
511: if (type && id && adv_router)
512: {
513: lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
514: if (lsa)
515: {
516: if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
517: ospf6_lsa_show (vty, lsa);
518: else
519: (*showfunc) (vty, lsa);
520: }
521: return;
522: }
523:
524: if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
525: ospf6_lsa_show_summary_header (vty);
526:
527: if (type && adv_router)
528: lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
529: else if (type)
530: lsa = ospf6_lsdb_type_head (*type, lsdb);
531: else
532: lsa = ospf6_lsdb_head (lsdb);
533: while (lsa)
534: {
535: if ((! adv_router || lsa->header->adv_router == *adv_router) &&
536: (! id || lsa->header->id == *id))
537: (*showfunc) (vty, lsa);
538:
539: if (type && adv_router)
540: lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
541: else if (type)
542: lsa = ospf6_lsdb_type_next (*type, lsa);
543: else
544: lsa = ospf6_lsdb_next (lsa);
545: }
546: }
547:
548: /* Decide new Link State ID to originate.
549: note return value is network byte order */
550: u_int32_t
551: ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
552: struct ospf6_lsdb *lsdb)
553: {
554: struct ospf6_lsa *lsa;
555: u_int32_t id = 1;
556:
557: for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
558: lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
559: {
560: if (ntohl (lsa->header->id) < id)
561: continue;
562: if (ntohl (lsa->header->id) > id)
563: {
564: ospf6_lsdb_lsa_unlock (lsa);
565: break;
566: }
567: id++;
568: }
569:
570: return ((u_int32_t) htonl (id));
571: }
572:
573: /* Decide new LS sequence number to originate.
574: note return value is network byte order */
575: u_int32_t
576: ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
577: struct ospf6_lsdb *lsdb)
578: {
579: struct ospf6_lsa *lsa;
580: signed long seqnum = 0;
581:
582: /* if current database copy not found, return InitialSequenceNumber */
583: lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
584: if (lsa == NULL)
585: seqnum = OSPF_INITIAL_SEQUENCE_NUMBER;
586: else
587: seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
588:
589: return ((u_int32_t) htonl (seqnum));
590: }
591:
592:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>