]> git.sommitrealweird.co.uk Git - quagga-debian.git/blob - ospf6d/ospf6_lsdb.c
New upstream version 1.2.4
[quagga-debian.git] / ospf6d / ospf6_lsdb.c
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