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
36struct ospf6_lsdb *
37ospf6_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
54void
55ospf6_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
65static void
66ospf6_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
77static 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
104void
105ospf6_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
169void
170ospf6_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
197struct ospf6_lsa *
198ospf6_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
220struct ospf6_lsa *
221ospf6_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 */
281struct ospf6_lsa *
282ospf6_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
301struct ospf6_lsa *
302ospf6_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
321struct ospf6_lsa *
322ospf6_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
357struct ospf6_lsa *
358ospf6_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
377struct ospf6_lsa *
378ospf6_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
410struct ospf6_lsa *
411ospf6_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
428void
429ospf6_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
440void
441ospf6_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
451int
452ospf6_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
487void
488ospf6_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 */
550u_int32_t
551ospf6_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 */
575u_int32_t
576ospf6_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
593