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