ospf6d/ospf6_lsdb.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Copyright (C) 2003 Yasuhiro Ohara
   4  */
   5
   6 #include <zebra.h>
   7
   8 #include "memory.h"
   9 #include "log.h"
  10 #include "command.h"
  11 #include "prefix.h"
  12 #include "table.h"
  13 #include "vty.h"
  14
  15 #include "ospf6_proto.h"
  16 #include "ospf6_area.h"
  17 #include "ospf6_lsa.h"
  18 #include "ospf6_lsdb.h"
  19 #include "ospf6_abr.h"
  20 #include "ospf6_asbr.h"
  21 #include "ospf6_route.h"
  22 #include "ospf6d.h"
  23 #include "bitfield.h"
  24
  25 DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_LSDB, "OSPF6 LSA database");
  26
  27 struct ospf6_lsdb *ospf6_lsdb_create(void *data)
  28 {
  29         struct ospf6_lsdb *lsdb;
  30
  31         lsdb = XCALLOC(MTYPE_OSPF6_LSDB, sizeof(struct ospf6_lsdb));
  32         memset(lsdb, 0, sizeof(struct ospf6_lsdb));
  33
  34         lsdb->data = data;
  35         lsdb->table = route_table_init();
  36         return lsdb;
  37 }
  38
  39 void ospf6_lsdb_delete(struct ospf6_lsdb *lsdb)
  40 {
  41         if (lsdb != NULL) {
  42                 ospf6_lsdb_remove_all(lsdb);
  43                 route_table_finish(lsdb->table);
  44                 XFREE(MTYPE_OSPF6_LSDB, lsdb);
  45         }
  46 }
  47
  48 static void ospf6_lsdb_set_key(struct prefix_ipv6 *key, const void *value,
  49                                int len)
  50 {
  51         assert(key->prefixlen % 8 == 0);
  52
  53         memcpy((caddr_t)&key->prefix + key->prefixlen / 8, (caddr_t)value, len);
  54         key->family = AF_INET6;
  55         key->prefixlen += len * 8;
  56 }
  57
  58 #ifdef DEBUG
  59 static void _lsdb_count_assert(struct ospf6_lsdb *lsdb)
  60 {
  61         struct ospf6_lsa *debug, *debugnext;
  62         unsigned int num = 0;
  63         for (ALL_LSDB(lsdb, debug, debugnext))
  64                 num++;
  65
  66         if (num == lsdb->count)
  67                 return;
  68
  69         zlog_debug("PANIC !! lsdb[%p]->count = %d, real = %d", lsdb,
  70                    lsdb->count, num);
  71         for (ALL_LSDB(lsdb, debug, debugnext))
  72                 zlog_debug("%s lsdb[%p]", debug->name, debug->lsdb);
  73         zlog_debug("DUMP END");
  74
  75         assert(num == lsdb->count);
  76 }
  77 #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
  78 #else  /*DEBUG*/
  79 #define ospf6_lsdb_count_assert(t) ((void) 0)
  80 #endif /*DEBUG*/
  81
  82 static inline void ospf6_lsdb_stats_update(struct ospf6_lsa *lsa,
  83                                            struct ospf6_lsdb *lsdb, int count)
  84 {
  85         uint16_t stat = ntohs(lsa->header->type) & OSPF6_LSTYPE_FCODE_MASK;
  86
  87         if (stat >= OSPF6_LSTYPE_SIZE)
  88                 stat = OSPF6_LSTYPE_UNKNOWN;
  89         lsdb->stats[stat] += count;
  90 }
  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                 ospf6_lsdb_stats_update(lsa, lsdb, 1);
 113
 114                 if (OSPF6_LSA_IS_MAXAGE(lsa)) {
 115                         if (lsdb->hook_remove)
 116                                 (*lsdb->hook_remove)(lsa);
 117                 } else {
 118                         if (lsdb->hook_add)
 119                                 (*lsdb->hook_add)(lsa);
 120                 }
 121         } else {
 122                 lsa->retrans_count = old->retrans_count;
 123
 124                 if (OSPF6_LSA_IS_CHANGED(old, lsa)) {
 125                         if (OSPF6_LSA_IS_MAXAGE(lsa)) {
 126                                 if (lsdb->hook_remove) {
 127                                         (*lsdb->hook_remove)(old);
 128                                         (*lsdb->hook_remove)(lsa);
 129                                 }
 130                         } else if (OSPF6_LSA_IS_MAXAGE(old)) {
 131                                 if (lsdb->hook_add)
 132                                         (*lsdb->hook_add)(lsa);
 133                         } else {
 134                                 if (lsdb->hook_remove)
 135                                         (*lsdb->hook_remove)(old);
 136                                 if (lsdb->hook_add)
 137                                         (*lsdb->hook_add)(lsa);
 138                         }
 139                 }
 140                 /* to free the lookup lock in node get*/
 141                 route_unlock_node(current);
 142                 ospf6_lsa_unlock(old);
 143         }
 144
 145         ospf6_lsdb_count_assert(lsdb);
 146 }
 147
 148 void ospf6_lsdb_remove(struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
 149 {
 150         struct route_node *node;
 151         struct prefix_ipv6 key;
 152
 153         memset(&key, 0, sizeof(key));
 154         ospf6_lsdb_set_key(&key, &lsa->header->type, sizeof(lsa->header->type));
 155         ospf6_lsdb_set_key(&key, &lsa->header->adv_router,
 156                            sizeof(lsa->header->adv_router));
 157         ospf6_lsdb_set_key(&key, &lsa->header->id, sizeof(lsa->header->id));
 158
 159         node = route_node_lookup(lsdb->table, (struct prefix *)&key);
 160         assert(node && node->info == lsa);
 161
 162         node->info = NULL;
 163         lsdb->count--;
 164         ospf6_lsdb_stats_update(lsa, lsdb, -1);
 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(uint16_t type, uint32_t id,
 177                                     uint32_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_find_external_lsa(struct ospf6 *ospf6, struct prefix *p)
 200 {
 201         struct ospf6_route *match;
 202         struct ospf6_lsa *lsa;
 203         struct ospf6_external_info *info;
 204
 205         match = ospf6_route_lookup(p, ospf6->external_table);
 206         if (match == NULL) {
 207                 if (IS_OSPF6_DEBUG_ASBR)
 208                         zlog_debug("No such route %pFX to withdraw", p);
 209
 210                 return NULL;
 211         }
 212
 213         info = match->route_option;
 214         assert(info);
 215
 216         lsa = ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_AS_EXTERNAL),
 217                                 htonl(info->id), ospf6->router_id, ospf6->lsdb);
 218         return lsa;
 219 }
 220
 221 struct ospf6_lsa *ospf6_find_inter_prefix_lsa(struct ospf6 *ospf6,
 222                                               struct ospf6_area *area,
 223                                               struct prefix *p)
 224 {
 225         struct ospf6_lsa *lsa;
 226         uint16_t type = htons(OSPF6_LSTYPE_INTER_PREFIX);
 227
 228         for (ALL_LSDB_TYPED_ADVRTR(area->lsdb, type, ospf6->router_id, lsa)) {
 229                 struct ospf6_inter_prefix_lsa *prefix_lsa;
 230                 struct prefix prefix;
 231
 232                 prefix_lsa =
 233                         (struct ospf6_inter_prefix_lsa *)OSPF6_LSA_HEADER_END(
 234                                 lsa->header);
 235                 prefix.family = AF_INET6;
 236                 prefix.prefixlen = prefix_lsa->prefix.prefix_length;
 237                 ospf6_prefix_in6_addr(&prefix.u.prefix6, prefix_lsa,
 238                                       &prefix_lsa->prefix);
 239                 if (prefix_same(p, &prefix))
 240                         return lsa;
 241         }
 242
 243         return NULL;
 244 }
 245
 246 struct ospf6_lsa *ospf6_lsdb_lookup_next(uint16_t type, uint32_t id,
 247                                          uint32_t adv_router,
 248                                          struct ospf6_lsdb *lsdb)
 249 {
 250         struct route_node *node;
 251         struct prefix_ipv6 key;
 252
 253         if (lsdb == NULL)
 254                 return NULL;
 255
 256         memset(&key, 0, sizeof(key));
 257         ospf6_lsdb_set_key(&key, &type, sizeof(type));
 258         ospf6_lsdb_set_key(&key, &adv_router, sizeof(adv_router));
 259         ospf6_lsdb_set_key(&key, &id, sizeof(id));
 260
 261         zlog_debug("lsdb_lookup_next: key: %pFX", &key);
 262
 263         node = route_table_get_next(lsdb->table, &key);
 264
 265         /* skip to real existing entry */
 266         while (node && node->info == NULL)
 267                 node = route_next(node);
 268
 269         if (!node)
 270                 return NULL;
 271
 272         route_unlock_node(node);
 273         if (!node->info)
 274                 return NULL;
 275
 276         return (struct ospf6_lsa *)node->info;
 277 }
 278
 279 const struct route_node *ospf6_lsdb_head(struct ospf6_lsdb *lsdb, int argmode,
 280                                          uint16_t type, uint32_t adv_router,
 281                                          struct ospf6_lsa **lsa)
 282 {
 283         struct route_node *node, *end;
 284
 285         *lsa = NULL;
 286
 287         if (argmode > 0) {
 288                 struct prefix_ipv6 key = {.family = AF_INET6, .prefixlen = 0};
 289
 290                 ospf6_lsdb_set_key(&key, &type, sizeof(type));
 291                 if (argmode > 1)
 292                         ospf6_lsdb_set_key(&key, &adv_router,
 293                                            sizeof(adv_router));
 294
 295                 node = route_table_get_next(lsdb->table, &key);
 296                 if (!node || !prefix_match((struct prefix *)&key, &node->p))
 297                         return NULL;
 298
 299                 for (end = node; end && end->parent
 300                                  && end->parent->p.prefixlen >= key.prefixlen;
 301                      end = end->parent)
 302                         ;
 303         } else {
 304                 node = route_top(lsdb->table);
 305                 end = NULL;
 306         }
 307
 308         while (node && !node->info)
 309                 node = route_next_until(node, end);
 310
 311         if (!node)
 312                 return NULL;
 313         if (!node->info) {
 314                 route_unlock_node(node);
 315                 return NULL;
 316         }
 317
 318         *lsa = node->info;
 319         ospf6_lsa_lock(*lsa);
 320
 321         return end;
 322 }
 323
 324 struct ospf6_lsa *ospf6_lsdb_next(const struct route_node *iterend,
 325                                   struct ospf6_lsa *lsa)
 326 {
 327         struct route_node *node = lsa->rn;
 328
 329         ospf6_lsa_unlock(lsa);
 330
 331         do
 332                 node = route_next_until(node, iterend);
 333         while (node && !node->info);
 334
 335         if (node && node->info) {
 336                 struct ospf6_lsa *next = node->info;
 337                 ospf6_lsa_lock(next);
 338                 return next;
 339         }
 340
 341         if (node)
 342                 route_unlock_node(node);
 343         return NULL;
 344 }
 345
 346 void ospf6_lsdb_remove_all(struct ospf6_lsdb *lsdb)
 347 {
 348         struct ospf6_lsa *lsa, *lsanext;
 349
 350         if (lsdb == NULL)
 351                 return;
 352
 353         for (ALL_LSDB(lsdb, lsa, lsanext))
 354                 ospf6_lsdb_remove(lsa, lsdb);
 355 }
 356
 357 void ospf6_lsdb_lsa_unlock(struct ospf6_lsa *lsa)
 358 {
 359         if (lsa != NULL) {
 360                 if (lsa->rn != NULL)
 361                         route_unlock_node(lsa->rn);
 362                 ospf6_lsa_unlock(lsa);
 363         }
 364 }
 365
 366 int ospf6_lsdb_maxage_remover(struct ospf6_lsdb *lsdb)
 367 {
 368         int reschedule = 0;
 369         struct ospf6_lsa *lsa, *lsanext;
 370
 371         for (ALL_LSDB(lsdb, lsa, lsanext)) {
 372                 if (!OSPF6_LSA_IS_MAXAGE(lsa)) {
 373                         if (IS_OSPF6_DEBUG_LSA_TYPE(lsa->header->type))
 374                                 zlog_debug("Not MaxAge %s", lsa->name);
 375                         continue;
 376                 }
 377
 378                 if (lsa->retrans_count != 0) {
 379                         if (IS_OSPF6_DEBUG_LSA_TYPE(lsa->header->type))
 380                                 zlog_debug("Remove MaxAge %s retrans_count %d",
 381                                            lsa->name, lsa->retrans_count);
 382
 383                         reschedule = 1;
 384                         continue;
 385                 }
 386                 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa->header->type))
 387                         zlog_debug("Remove MaxAge %s", lsa->name);
 388
 389                 if (CHECK_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED)) {
 390                         UNSET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED);
 391                         /*
 392                          * lsa->header->age = 0;
 393                          */
 394                         lsa->header->seqnum =
 395                                 htonl(OSPF_MAX_SEQUENCE_NUMBER + 1);
 396                         ospf6_lsa_checksum(lsa->header);
 397
 398                         THREAD_OFF(lsa->refresh);
 399                         thread_execute(master, ospf6_lsa_refresh, lsa, 0);
 400                 } else {
 401                         zlog_debug("calling ospf6_lsdb_remove %s", lsa->name);
 402                         ospf6_lsdb_remove(lsa, lsdb);
 403                 }
 404         }
 405
 406         return (reschedule);
 407 }
 408
 409 uint32_t ospf6_new_ls_id(uint16_t type, uint32_t adv_router,
 410                          struct ospf6_lsdb *lsdb)
 411 {
 412         struct ospf6_lsa *lsa;
 413         uint32_t id = 1, tmp_id;
 414
 415         /* This routine is curently invoked only for Inter-Prefix LSAs for
 416          * non-summarized routes (no area/range).
 417          */
 418         for (ALL_LSDB_TYPED_ADVRTR(lsdb, type, adv_router, lsa)) {
 419                 tmp_id = ntohl(lsa->header->id);
 420                 if (tmp_id < id)
 421                         continue;
 422
 423                 if (tmp_id > id) {
 424                         ospf6_lsdb_lsa_unlock(lsa);
 425                         break;
 426                 }
 427                 id++;
 428         }
 429
 430         return ((uint32_t)htonl(id));
 431 }
 432
 433 /* Decide new LS sequence number to originate.
 434    note return value is network byte order */
 435 uint32_t ospf6_new_ls_seqnum(uint16_t type, uint32_t id, uint32_t adv_router,
 436                              struct ospf6_lsdb *lsdb)
 437 {
 438         struct ospf6_lsa *lsa;
 439         signed long seqnum = 0;
 440
 441         /* if current database copy not found, return InitialSequenceNumber */
 442         lsa = ospf6_lsdb_lookup(type, id, adv_router, lsdb);
 443         if (lsa == NULL)
 444                 seqnum = OSPF_INITIAL_SEQUENCE_NUMBER;
 445         else
 446                 seqnum = (signed long)ntohl(lsa->header->seqnum) + 1;
 447
 448         return ((uint32_t)htonl(seqnum));
 449 }