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