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