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          12 : DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_LSDB, "OSPF6 LSA database");
      39             : 
      40          88 : struct ospf6_lsdb *ospf6_lsdb_create(void *data)
      41             : {
      42          88 :         struct ospf6_lsdb *lsdb;
      43             : 
      44          88 :         lsdb = XCALLOC(MTYPE_OSPF6_LSDB, sizeof(struct ospf6_lsdb));
      45          88 :         memset(lsdb, 0, sizeof(struct ospf6_lsdb));
      46             : 
      47          88 :         lsdb->data = data;
      48          88 :         lsdb->table = route_table_init();
      49          88 :         return lsdb;
      50             : }
      51             : 
      52          88 : void ospf6_lsdb_delete(struct ospf6_lsdb *lsdb)
      53             : {
      54          88 :         if (lsdb != NULL) {
      55          88 :                 ospf6_lsdb_remove_all(lsdb);
      56          88 :                 route_table_finish(lsdb->table);
      57          88 :                 XFREE(MTYPE_OSPF6_LSDB, lsdb);
      58             :         }
      59          88 : }
      60             : 
      61        8572 : static void ospf6_lsdb_set_key(struct prefix_ipv6 *key, const void *value,
      62             :                                int len)
      63             : {
      64        8572 :         assert(key->prefixlen % 8 == 0);
      65             : 
      66        8572 :         memcpy((caddr_t)&key->prefix + key->prefixlen / 8, (caddr_t)value, len);
      67        8572 :         key->family = AF_INET6;
      68        8572 :         key->prefixlen += len * 8;
      69        8572 : }
      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         782 : static inline void ospf6_lsdb_stats_update(struct ospf6_lsa *lsa,
      96             :                                            struct ospf6_lsdb *lsdb, int count)
      97             : {
      98         782 :         uint16_t stat = ntohs(lsa->header->type) & OSPF6_LSTYPE_FCODE_MASK;
      99             : 
     100         782 :         if (stat >= OSPF6_LSTYPE_SIZE)
     101           0 :                 stat = OSPF6_LSTYPE_UNKNOWN;
     102         782 :         lsdb->stats[stat] += count;
     103             : }
     104             : 
     105         485 : void ospf6_lsdb_add(struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
     106             : {
     107         485 :         struct prefix_ipv6 key;
     108         485 :         struct route_node *current;
     109         485 :         struct ospf6_lsa *old = NULL;
     110             : 
     111         485 :         memset(&key, 0, sizeof(key));
     112         485 :         ospf6_lsdb_set_key(&key, &lsa->header->type, sizeof(lsa->header->type));
     113         485 :         ospf6_lsdb_set_key(&key, &lsa->header->adv_router,
     114             :                            sizeof(lsa->header->adv_router));
     115         485 :         ospf6_lsdb_set_key(&key, &lsa->header->id, sizeof(lsa->header->id));
     116             : 
     117         485 :         current = route_node_get(lsdb->table, (struct prefix *)&key);
     118         485 :         old = current->info;
     119         485 :         current->info = lsa;
     120         485 :         lsa->rn = current;
     121         485 :         ospf6_lsa_lock(lsa);
     122             : 
     123         485 :         if (!old) {
     124         391 :                 lsdb->count++;
     125         391 :                 ospf6_lsdb_stats_update(lsa, lsdb, 1);
     126             : 
     127         391 :                 if (OSPF6_LSA_IS_MAXAGE(lsa)) {
     128          37 :                         if (lsdb->hook_remove)
     129           0 :                                 (*lsdb->hook_remove)(lsa);
     130             :                 } else {
     131         354 :                         if (lsdb->hook_add)
     132          45 :                                 (*lsdb->hook_add)(lsa);
     133             :                 }
     134             :         } else {
     135          94 :                 lsa->retrans_count = old->retrans_count;
     136             : 
     137          94 :                 if (OSPF6_LSA_IS_CHANGED(old, lsa)) {
     138          70 :                         if (OSPF6_LSA_IS_MAXAGE(lsa)) {
     139          15 :                                 if (lsdb->hook_remove) {
     140          15 :                                         (*lsdb->hook_remove)(old);
     141          15 :                                         (*lsdb->hook_remove)(lsa);
     142             :                                 }
     143          55 :                         } else if (OSPF6_LSA_IS_MAXAGE(old)) {
     144           8 :                                 if (lsdb->hook_add)
     145           7 :                                         (*lsdb->hook_add)(lsa);
     146             :                         } else {
     147          47 :                                 if (lsdb->hook_remove)
     148          35 :                                         (*lsdb->hook_remove)(old);
     149          47 :                                 if (lsdb->hook_add)
     150          35 :                                         (*lsdb->hook_add)(lsa);
     151             :                         }
     152             :                 }
     153             :                 /* to free the lookup lock in node get*/
     154          94 :                 route_unlock_node(current);
     155          94 :                 ospf6_lsa_unlock(old);
     156             :         }
     157             : 
     158         485 :         ospf6_lsdb_count_assert(lsdb);
     159         485 : }
     160             : 
     161         391 : void ospf6_lsdb_remove(struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
     162             : {
     163         391 :         struct route_node *node;
     164         391 :         struct prefix_ipv6 key;
     165             : 
     166         391 :         memset(&key, 0, sizeof(key));
     167         391 :         ospf6_lsdb_set_key(&key, &lsa->header->type, sizeof(lsa->header->type));
     168         391 :         ospf6_lsdb_set_key(&key, &lsa->header->adv_router,
     169             :                            sizeof(lsa->header->adv_router));
     170         391 :         ospf6_lsdb_set_key(&key, &lsa->header->id, sizeof(lsa->header->id));
     171             : 
     172         391 :         node = route_node_lookup(lsdb->table, (struct prefix *)&key);
     173         391 :         assert(node && node->info == lsa);
     174             : 
     175         391 :         node->info = NULL;
     176         391 :         lsdb->count--;
     177         391 :         ospf6_lsdb_stats_update(lsa, lsdb, -1);
     178             : 
     179         391 :         if (lsdb->hook_remove)
     180          45 :                 (*lsdb->hook_remove)(lsa);
     181             : 
     182         391 :         route_unlock_node(node); /* to free the lookup lock */
     183         391 :         route_unlock_node(node); /* to free the original lock */
     184         391 :         ospf6_lsa_unlock(lsa);
     185             : 
     186         391 :         ospf6_lsdb_count_assert(lsdb);
     187         391 : }
     188             : 
     189        1781 : struct ospf6_lsa *ospf6_lsdb_lookup(uint16_t type, uint32_t id,
     190             :                                     uint32_t adv_router,
     191             :                                     struct ospf6_lsdb *lsdb)
     192             : {
     193        1781 :         struct route_node *node;
     194        1781 :         struct prefix_ipv6 key;
     195             : 
     196        1781 :         if (lsdb == NULL)
     197             :                 return NULL;
     198             : 
     199        1781 :         memset(&key, 0, sizeof(key));
     200        1781 :         ospf6_lsdb_set_key(&key, &type, sizeof(type));
     201        1781 :         ospf6_lsdb_set_key(&key, &adv_router, sizeof(adv_router));
     202        1781 :         ospf6_lsdb_set_key(&key, &id, sizeof(id));
     203             : 
     204        1781 :         node = route_node_lookup(lsdb->table, (struct prefix *)&key);
     205        1781 :         if (node == NULL || node->info == NULL)
     206             :                 return NULL;
     207             : 
     208         919 :         route_unlock_node(node);
     209         919 :         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        1101 : 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        1101 :         struct route_node *node, *end;
     272             : 
     273        1101 :         *lsa = NULL;
     274             : 
     275        1101 :         if (argmode > 0) {
     276         328 :                 struct prefix_ipv6 key = {.family = AF_INET6, .prefixlen = 0};
     277             : 
     278         328 :                 ospf6_lsdb_set_key(&key, &type, sizeof(type));
     279         328 :                 if (argmode > 1)
     280         273 :                         ospf6_lsdb_set_key(&key, &adv_router,
     281             :                                            sizeof(adv_router));
     282             : 
     283         328 :                 node = route_table_get_next(lsdb->table, &key);
     284         328 :                 if (!node || !prefix_match((struct prefix *)&key, &node->p))
     285          34 :                         return NULL;
     286             : 
     287         294 :                 for (end = node; end && end->parent
     288         294 :                                  && end->parent->p.prefixlen >= key.prefixlen;
     289             :                      end = end->parent)
     290             :                         ;
     291             :         } else {
     292         773 :                 node = route_top(lsdb->table);
     293         773 :                 end = NULL;
     294             :         }
     295             : 
     296        1785 :         while (node && !node->info)
     297         718 :                 node = route_next_until(node, end);
     298             : 
     299        1067 :         if (!node)
     300             :                 return NULL;
     301         628 :         if (!node->info) {
     302           0 :                 route_unlock_node(node);
     303           0 :                 return NULL;
     304             :         }
     305             : 
     306         628 :         *lsa = node->info;
     307         628 :         ospf6_lsa_lock(*lsa);
     308             : 
     309         628 :         return end;
     310             : }
     311             : 
     312        1714 : struct ospf6_lsa *ospf6_lsdb_next(const struct route_node *iterend,
     313             :                                   struct ospf6_lsa *lsa)
     314             : {
     315        1714 :         struct route_node *node = lsa->rn;
     316             : 
     317        1714 :         ospf6_lsa_unlock(lsa);
     318             : 
     319        2082 :         do
     320        2082 :                 node = route_next_until(node, iterend);
     321        2082 :         while (node && !node->info);
     322             : 
     323        1714 :         if (node && node->info) {
     324        1086 :                 struct ospf6_lsa *next = node->info;
     325        1086 :                 ospf6_lsa_lock(next);
     326        1086 :                 return next;
     327             :         }
     328             : 
     329           0 :         if (node)
     330           0 :                 route_unlock_node(node);
     331             :         return NULL;
     332             : }
     333             : 
     334         227 : void ospf6_lsdb_remove_all(struct ospf6_lsdb *lsdb)
     335             : {
     336         227 :         struct ospf6_lsa *lsa, *lsanext;
     337             : 
     338         227 :         if (lsdb == NULL)
     339           0 :                 return;
     340             : 
     341         331 :         for (ALL_LSDB(lsdb, lsa, lsanext))
     342         104 :                 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           0 : uint32_t ospf6_new_ls_id(uint16_t type, uint32_t adv_router,
     398             :                          struct ospf6_lsdb *lsdb)
     399             : {
     400           0 :         struct ospf6_lsa *lsa;
     401           0 :         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           0 :         for (ALL_LSDB_TYPED_ADVRTR(lsdb, type, adv_router, lsa)) {
     407           0 :                 tmp_id = ntohl(lsa->header->id);
     408           0 :                 if (tmp_id < id)
     409           0 :                         continue;
     410             : 
     411           0 :                 if (tmp_id > id) {
     412           0 :                         ospf6_lsdb_lsa_unlock(lsa);
     413           0 :                         break;
     414             :                 }
     415           0 :                 id++;
     416             :         }
     417             : 
     418           0 :         return ((uint32_t)htonl(id));
     419             : }
     420             : 
     421             : /* Decide new LS sequence number to originate.
     422             :    note return value is network byte order */
     423          38 : uint32_t ospf6_new_ls_seqnum(uint16_t type, uint32_t id, uint32_t adv_router,
     424             :                              struct ospf6_lsdb *lsdb)
     425             : {
     426          38 :         struct ospf6_lsa *lsa;
     427          38 :         signed long seqnum = 0;
     428             : 
     429             :         /* if current database copy not found, return InitialSequenceNumber */
     430          38 :         lsa = ospf6_lsdb_lookup(type, id, adv_router, lsdb);
     431          38 :         if (lsa == NULL)
     432             :                 seqnum = OSPF_INITIAL_SEQUENCE_NUMBER;
     433             :         else
     434          25 :                 seqnum = (signed long)ntohl(lsa->header->seqnum) + 1;
     435             : 
     436          38 :         return ((uint32_t)htonl(seqnum));
     437             : }