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