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 along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22
  23 #include "memory.h"
  24 #include "log.h"
  25 #include "command.h"
  26 #include "prefix.h"
  27 #include "table.h"
  28 #include "vty.h"
  29
  30 #include "ospf6_proto.h"
  31 #include "ospf6_lsa.h"
  32 #include "ospf6_lsdb.h"
  33 #include "ospf6_route.h"
  34 #include "ospf6d.h"
  35 #include "bitfield.h"
  36
  37 struct ospf6_lsdb *
  38 ospf6_lsdb_create (void *data)
  39 {
  40   struct ospf6_lsdb *lsdb;
  41
  42   lsdb = XCALLOC (MTYPE_OSPF6_LSDB, sizeof (struct ospf6_lsdb));
  43   if (lsdb == NULL)
  44     {
  45       zlog_warn ("Can't malloc lsdb");
  46       return NULL;
  47     }
  48   memset (lsdb, 0, sizeof (struct ospf6_lsdb));
  49
  50   lsdb->data = data;
  51   lsdb->table = route_table_init ();
  52   return lsdb;
  53 }
  54
  55 void
  56 ospf6_lsdb_delete (struct ospf6_lsdb *lsdb)
  57 {
  58   if (lsdb != NULL)
  59     {
  60       ospf6_lsdb_remove_all (lsdb);
  61       route_table_finish (lsdb->table);
  62       XFREE (MTYPE_OSPF6_LSDB, lsdb);
  63     }
  64 }
  65
  66 static void
  67 ospf6_lsdb_set_key (struct prefix_ipv6 *key, const void *value, int len)
  68 {
  69   assert (key->prefixlen % 8 == 0);
  70
  71   memcpy ((caddr_t) &key->prefix + key->prefixlen / 8,
  72           (caddr_t) value, len);
  73   key->family = AF_INET6;
  74   key->prefixlen += len * 8;
  75 }
  76
  77 #ifdef DEBUG
  78 static void
  79 _lsdb_count_assert (struct ospf6_lsdb *lsdb)
  80 {
  81   struct ospf6_lsa *debug;
  82   unsigned int num = 0;
  83   for (ALL_LSDB(lsdb, 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 (ALL_LSDB(lsdb, debug))
  92     zlog_debug ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name,
  93                debug->lsdb);
  94   zlog_debug ("DUMP END");
  95
  96   assert (num == lsdb->count);
  97 }
  98 #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
  99 #else /*DEBUG*/
 100 #define ospf6_lsdb_count_assert(t) ((void) 0)
 101 #endif /*DEBUG*/
 102
 103 void
 104 ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
 105 {
 106   struct prefix_ipv6 key;
 107   struct route_node *current;
 108   struct ospf6_lsa *old = NULL;
 109
 110   memset (&key, 0, sizeof (key));
 111   ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
 112   ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
 113                       sizeof (lsa->header->adv_router));
 114   ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
 115
 116   current = route_node_get (lsdb->table, (struct prefix *) &key);
 117   old = current->info;
 118   current->info = lsa;
 119   lsa->rn = current;
 120   ospf6_lsa_lock (lsa);
 121
 122   if (!old)
 123     {
 124       lsdb->count++;
 125
 126       if (OSPF6_LSA_IS_MAXAGE (lsa))
 127         {
 128           if (lsdb->hook_remove)
 129             (*lsdb->hook_remove) (lsa);
 130         }
 131       else
 132         {
 133           if (lsdb->hook_add)
 134             (*lsdb->hook_add) (lsa);
 135         }
 136     }
 137   else
 138     {
 139       if (OSPF6_LSA_IS_CHANGED (old, lsa))
 140         {
 141           if (OSPF6_LSA_IS_MAXAGE (lsa))
 142             {
 143               if (lsdb->hook_remove)
 144                 {
 145                   (*lsdb->hook_remove) (old);
 146                   (*lsdb->hook_remove) (lsa);
 147                 }
 148             }
 149           else if (OSPF6_LSA_IS_MAXAGE (old))
 150             {
 151               if (lsdb->hook_add)
 152                 (*lsdb->hook_add) (lsa);
 153             }
 154           else
 155             {
 156               if (lsdb->hook_remove)
 157                 (*lsdb->hook_remove) (old);
 158               if (lsdb->hook_add)
 159                 (*lsdb->hook_add) (lsa);
 160             }
 161         }
 162       ospf6_lsa_unlock (old);
 163     }
 164
 165   ospf6_lsdb_count_assert (lsdb);
 166 }
 167
 168 void
 169 ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
 170 {
 171   struct route_node *node;
 172   struct prefix_ipv6 key;
 173
 174   memset (&key, 0, sizeof (key));
 175   ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
 176   ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
 177                       sizeof (lsa->header->adv_router));
 178   ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
 179
 180   node = route_node_lookup (lsdb->table, (struct prefix *) &key);
 181   assert (node && node->info == lsa);
 182
 183   node->info = NULL;
 184   lsdb->count--;
 185
 186   if (lsdb->hook_remove)
 187     (*lsdb->hook_remove) (lsa);
 188
 189   route_unlock_node (node);     /* to free the lookup lock */
 190   route_unlock_node (node);     /* to free the original lock */
 191   ospf6_lsa_unlock (lsa);
 192
 193   ospf6_lsdb_count_assert (lsdb);
 194 }
 195
 196 struct ospf6_lsa *
 197 ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 198                    struct ospf6_lsdb *lsdb)
 199 {
 200   struct route_node *node;
 201   struct prefix_ipv6 key;
 202
 203   if (lsdb == NULL)
 204     return NULL;
 205
 206   memset (&key, 0, sizeof (key));
 207   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 208   ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 209   ospf6_lsdb_set_key (&key, &id, sizeof (id));
 210
 211   node = route_node_lookup (lsdb->table, (struct prefix *) &key);
 212   if (node == NULL || node->info == NULL)
 213     return NULL;
 214
 215   route_unlock_node (node);
 216   return (struct ospf6_lsa *) node->info;
 217 }
 218
 219 struct ospf6_lsa *
 220 ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 221                         struct ospf6_lsdb *lsdb)
 222 {
 223   struct route_node *node;
 224   struct prefix_ipv6 key;
 225
 226   if (lsdb == NULL)
 227     return NULL;
 228
 229   memset (&key, 0, sizeof (key));
 230   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 231   ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 232   ospf6_lsdb_set_key (&key, &id, sizeof (id));
 233
 234   {
 235     char buf[PREFIX2STR_BUFFER];
 236     prefix2str (&key, buf, sizeof (buf));
 237     zlog_debug ("lsdb_lookup_next: key: %s", buf);
 238   }
 239
 240   node = route_table_get_next (lsdb->table, &key);
 241
 242   /* skip to real existing entry */
 243   while (node && node->info == NULL)
 244     node = route_next (node);
 245
 246   if (! node)
 247     return NULL;
 248
 249   route_unlock_node (node);
 250   if (! node->info)
 251     return NULL;
 252
 253   return (struct ospf6_lsa *) node->info;
 254 }
 255
 256 const struct route_node *
 257 ospf6_lsdb_head (struct ospf6_lsdb *lsdb,
 258                  int argmode, uint16_t type, uint32_t adv_router,
 259                  struct ospf6_lsa **lsa)
 260 {
 261   struct route_node *node, *end;
 262
 263   *lsa = NULL;
 264
 265   if (argmode > 0)
 266     {
 267       struct prefix_ipv6 key = { .family = AF_INET6, .prefixlen = 0 };
 268
 269       ospf6_lsdb_set_key (&key, &type, sizeof (type));
 270       if (argmode > 1)
 271         ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 272
 273       node = route_table_get_next (lsdb->table, &key);
 274       if (!node || !prefix_match((struct prefix *)&key, &node->p))
 275         return NULL;
 276
 277       for (end = node;
 278            end && end->parent && end->parent->p.prefixlen >= key.prefixlen;
 279            end = end->parent)
 280         ;
 281     }
 282   else
 283     {
 284       node = route_top (lsdb->table);
 285       end = NULL;
 286     }
 287
 288   while (node && !node->info)
 289     node = route_next_until(node, end);
 290
 291   if (!node)
 292     return NULL;
 293   if (!node->info)
 294     {
 295       route_unlock_node(node);
 296       return NULL;
 297     }
 298
 299   *lsa = node->info;
 300   ospf6_lsa_lock (*lsa);
 301
 302   return end;
 303 }
 304
 305 struct ospf6_lsa *
 306 ospf6_lsdb_next (const struct route_node *iterend,
 307                  struct ospf6_lsa *lsa)
 308 {
 309   struct route_node *node = lsa->rn;
 310
 311   ospf6_lsa_unlock(lsa);
 312
 313   do
 314     node = route_next_until(node, iterend);
 315   while (node && !node->info);
 316
 317   if (node && node->info)
 318     {
 319       struct ospf6_lsa *next = node->info;
 320       ospf6_lsa_lock (next);
 321       return next;
 322     }
 323
 324   if (node)
 325     route_unlock_node (node);
 326   return NULL;
 327 }
 328
 329 void
 330 ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
 331 {
 332   struct ospf6_lsa *lsa;
 333
 334   if (lsdb == NULL)
 335     return;
 336
 337   for (ALL_LSDB(lsdb, lsa))
 338     ospf6_lsdb_remove (lsa, lsdb);
 339 }
 340
 341 void
 342 ospf6_lsdb_lsa_unlock (struct ospf6_lsa *lsa)
 343 {
 344   if (lsa != NULL)
 345     {
 346       if (lsa->rn != NULL)
 347         route_unlock_node (lsa->rn);
 348       ospf6_lsa_unlock (lsa);
 349     }
 350 }
 351
 352 int
 353 ospf6_lsdb_maxage_remover (struct ospf6_lsdb *lsdb)
 354 {
 355   int reschedule = 0;
 356   struct ospf6_lsa *lsa;
 357
 358   for (ALL_LSDB(lsdb, lsa))
 359     {
 360       if (! OSPF6_LSA_IS_MAXAGE (lsa))
 361         continue;
 362       if (lsa->retrans_count != 0)
 363         {
 364           reschedule = 1;
 365           continue;
 366         }
 367       if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type))
 368         zlog_debug ("Remove MaxAge %s", lsa->name);
 369       if (CHECK_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED))
 370       {
 371         UNSET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED);
 372         /*
 373          * lsa->header->age = 0;
 374          */
 375         lsa->header->seqnum = htonl(OSPF_MAX_SEQUENCE_NUMBER + 1);
 376         ospf6_lsa_checksum (lsa->header);
 377
 378         THREAD_OFF(lsa->refresh);
 379         thread_execute (master, ospf6_lsa_refresh, lsa, 0);
 380       } else {
 381         ospf6_lsdb_remove (lsa, lsdb);
 382       }
 383     }
 384
 385   return (reschedule);
 386 }
 387
 388 void
 389 ospf6_lsdb_show (struct vty *vty, enum ospf_lsdb_show_level level,
 390                  u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
 391                  struct ospf6_lsdb *lsdb)
 392 {
 393   struct ospf6_lsa *lsa;
 394   const struct route_node *end = NULL;
 395   void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
 396
 397   switch (level)
 398   {
 399     case OSPF6_LSDB_SHOW_LEVEL_DETAIL:
 400       showfunc = ospf6_lsa_show;
 401       break;
 402     case OSPF6_LSDB_SHOW_LEVEL_INTERNAL:
 403       showfunc = ospf6_lsa_show_internal;
 404       break;
 405     case OSPF6_LSDB_SHOW_LEVEL_DUMP:
 406       showfunc = ospf6_lsa_show_dump;
 407       break;
 408     case OSPF6_LSDB_SHOW_LEVEL_NORMAL:
 409     default:
 410       showfunc = ospf6_lsa_show_summary;
 411   }
 412
 413   if (type && id && adv_router)
 414     {
 415       lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
 416       if (lsa)
 417         {
 418           if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 419             ospf6_lsa_show (vty, lsa);
 420           else
 421             (*showfunc) (vty, lsa);
 422         }
 423       return;
 424     }
 425
 426   if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 427     ospf6_lsa_show_summary_header (vty);
 428
 429   end = ospf6_lsdb_head(lsdb, !!type + !!(type && adv_router),
 430                         *type, *adv_router, &lsa);
 431   while (lsa)
 432     {
 433       if ((! adv_router || lsa->header->adv_router == *adv_router) &&
 434           (! id || lsa->header->id == *id))
 435         (*showfunc) (vty, lsa);
 436
 437       lsa = ospf6_lsdb_next (end, lsa);
 438     }
 439 }
 440
 441 u_int32_t
 442 ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
 443                  struct ospf6_lsdb *lsdb)
 444 {
 445   struct ospf6_lsa *lsa;
 446   u_int32_t id = 1, tmp_id;
 447
 448   /* This routine is curently invoked only for Inter-Prefix LSAs for
 449    * non-summarized routes (no area/range).
 450    */
 451   for (ALL_LSDB_TYPED_ADVRTR(lsdb, type, adv_router, lsa))
 452     {
 453       tmp_id = ntohl (lsa->header->id);
 454       if (tmp_id < id)
 455         continue;
 456
 457       if (tmp_id > id)
 458       {
 459         ospf6_lsdb_lsa_unlock (lsa);
 460         break;
 461       }
 462       id++;
 463     }
 464
 465   return ((u_int32_t) htonl (id));
 466 }
 467
 468 /* Decide new LS sequence number to originate.
 469    note return value is network byte order */
 470 u_int32_t
 471 ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 472                      struct ospf6_lsdb *lsdb)
 473 {
 474   struct ospf6_lsa *lsa;
 475   signed long seqnum = 0;
 476
 477   /* if current database copy not found, return InitialSequenceNumber */
 478   lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
 479   if (lsa == NULL)
 480     seqnum = OSPF_INITIAL_SEQUENCE_NUMBER;
 481   else
 482     seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
 483
 484   return ((u_int32_t) htonl (seqnum));
 485 }
 486
 487