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