Line data    Source code

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