123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582 |
- /*
- * Copyright (C) 2003 Yasuhiro Ohara
- *
- * This file is part of GNU Zebra.
- *
- * GNU Zebra is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation; either version 2, or (at your option) any
- * later version.
- *
- * GNU Zebra is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with GNU Zebra; see the file COPYING. If not, write to the
- * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- * Boston, MA 02111-1307, USA.
- */
- #include <zebra.h>
- #include "memory.h"
- #include "log.h"
- #include "command.h"
- #include "prefix.h"
- #include "table.h"
- #include "vty.h"
- #include "ospf6_proto.h"
- #include "ospf6_lsa.h"
- #include "ospf6_lsdb.h"
- #include "ospf6d.h"
- struct ospf6_lsdb *
- ospf6_lsdb_create (void *data)
- {
- struct ospf6_lsdb *lsdb;
- lsdb = XCALLOC (MTYPE_OSPF6_LSDB, sizeof (struct ospf6_lsdb));
- if (lsdb == NULL)
- {
- zlog_warn ("Can't malloc lsdb");
- return NULL;
- }
- memset (lsdb, 0, sizeof (struct ospf6_lsdb));
- lsdb->data = data;
- lsdb->table = route_table_init ();
- return lsdb;
- }
- void
- ospf6_lsdb_delete (struct ospf6_lsdb *lsdb)
- {
- ospf6_lsdb_remove_all (lsdb);
- route_table_finish (lsdb->table);
- XFREE (MTYPE_OSPF6_LSDB, lsdb);
- }
- static void
- ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len)
- {
- assert (key->prefixlen % 8 == 0);
- memcpy ((caddr_t) &key->prefix + key->prefixlen / 8,
- (caddr_t) value, len);
- key->family = AF_INET6;
- key->prefixlen += len * 8;
- }
- #ifndef NDEBUG
- static void
- _lsdb_count_assert (struct ospf6_lsdb *lsdb)
- {
- struct ospf6_lsa *debug;
- unsigned int num = 0;
- for (debug = ospf6_lsdb_head (lsdb); debug;
- debug = ospf6_lsdb_next (debug))
- num++;
- if (num == lsdb->count)
- return;
- zlog_debug ("PANIC !! lsdb[%p]->count = %d, real = %d",
- lsdb, lsdb->count, num);
- for (debug = ospf6_lsdb_head (lsdb); debug;
- debug = ospf6_lsdb_next (debug))
- zlog_debug ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name,
- debug->lsdb);
- zlog_debug ("DUMP END");
- assert (num == lsdb->count);
- }
- #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
- #else /*NDEBUG*/
- #define ospf6_lsdb_count_assert(t) ((void) 0)
- #endif /*NDEBUG*/
- void
- ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
- {
- struct prefix_ipv6 key;
- struct route_node *current, *nextnode, *prevnode;
- struct ospf6_lsa *next, *prev, *old = NULL;
- memset (&key, 0, sizeof (key));
- ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
- ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
- sizeof (lsa->header->adv_router));
- ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
- current = route_node_get (lsdb->table, (struct prefix *) &key);
- old = current->info;
- current->info = lsa;
- ospf6_lsa_lock (lsa);
- if (old)
- {
- if (old->prev)
- old->prev->next = lsa;
- if (old->next)
- old->next->prev = lsa;
- lsa->next = old->next;
- lsa->prev = old->prev;
- }
- else
- {
- /* next link */
- nextnode = current;
- route_lock_node (nextnode);
- do {
- nextnode = route_next (nextnode);
- } while (nextnode && nextnode->info == NULL);
- if (nextnode == NULL)
- lsa->next = NULL;
- else
- {
- next = nextnode->info;
- lsa->next = next;
- next->prev = lsa;
- route_unlock_node (nextnode);
- }
- /* prev link */
- prevnode = current;
- route_lock_node (prevnode);
- do {
- prevnode = route_prev (prevnode);
- } while (prevnode && prevnode->info == NULL);
- if (prevnode == NULL)
- lsa->prev = NULL;
- else
- {
- prev = prevnode->info;
- lsa->prev = prev;
- prev->next = lsa;
- route_unlock_node (prevnode);
- }
- lsdb->count++;
- }
- if (old)
- {
- if (OSPF6_LSA_IS_CHANGED (old, lsa))
- {
- if (OSPF6_LSA_IS_MAXAGE (lsa))
- {
- if (lsdb->hook_remove)
- {
- (*lsdb->hook_remove) (old);
- (*lsdb->hook_remove) (lsa);
- }
- }
- else if (OSPF6_LSA_IS_MAXAGE (old))
- {
- if (lsdb->hook_add)
- (*lsdb->hook_add) (lsa);
- }
- else
- {
- if (lsdb->hook_remove)
- (*lsdb->hook_remove) (old);
- if (lsdb->hook_add)
- (*lsdb->hook_add) (lsa);
- }
- }
- }
- else if (OSPF6_LSA_IS_MAXAGE (lsa))
- {
- if (lsdb->hook_remove)
- (*lsdb->hook_remove) (lsa);
- }
- else
- {
- if (lsdb->hook_add)
- (*lsdb->hook_add) (lsa);
- }
- if (old)
- ospf6_lsa_unlock (old);
- ospf6_lsdb_count_assert (lsdb);
- }
- void
- ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
- {
- struct route_node *node;
- struct prefix_ipv6 key;
- memset (&key, 0, sizeof (key));
- ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
- ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
- sizeof (lsa->header->adv_router));
- ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
- node = route_node_lookup (lsdb->table, (struct prefix *) &key);
- assert (node && node->info == lsa);
- if (lsa->prev)
- lsa->prev->next = lsa->next;
- if (lsa->next)
- lsa->next->prev = lsa->prev;
- node->info = NULL;
- lsdb->count--;
- if (lsdb->hook_remove)
- (*lsdb->hook_remove) (lsa);
- ospf6_lsa_unlock (lsa);
- route_unlock_node (node);
- ospf6_lsdb_count_assert (lsdb);
- }
- struct ospf6_lsa *
- ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
- struct ospf6_lsdb *lsdb)
- {
- struct route_node *node;
- struct prefix_ipv6 key;
- if (lsdb == NULL)
- return NULL;
- memset (&key, 0, sizeof (key));
- ospf6_lsdb_set_key (&key, &type, sizeof (type));
- ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
- ospf6_lsdb_set_key (&key, &id, sizeof (id));
- node = route_node_lookup (lsdb->table, (struct prefix *) &key);
- if (node == NULL || node->info == NULL)
- return NULL;
- return (struct ospf6_lsa *) node->info;
- }
- struct ospf6_lsa *
- ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
- struct ospf6_lsdb *lsdb)
- {
- struct route_node *node;
- struct route_node *matched = NULL;
- struct prefix_ipv6 key;
- struct prefix *p;
- if (lsdb == NULL)
- return NULL;
- memset (&key, 0, sizeof (key));
- ospf6_lsdb_set_key (&key, &type, sizeof (type));
- ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
- ospf6_lsdb_set_key (&key, &id, sizeof (id));
- p = (struct prefix *) &key;
- {
- char buf[64];
- prefix2str (p, buf, sizeof (buf));
- zlog_debug ("lsdb_lookup_next: key: %s", buf);
- }
- node = lsdb->table->top;
- /* walk down tree. */
- while (node && node->p.prefixlen <= p->prefixlen &&
- prefix_match (&node->p, p))
- {
- matched = node;
- node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)];
- }
- if (matched)
- node = matched;
- else
- node = lsdb->table->top;
- route_lock_node (node);
- /* skip to real existing entry */
- while (node && node->info == NULL)
- node = route_next (node);
- if (! node)
- return NULL;
- if (prefix_same (&node->p, p))
- {
- struct route_node *prev = node;
- struct ospf6_lsa *lsa_prev;
- struct ospf6_lsa *lsa_next;
- node = route_next (node);
- while (node && node->info == NULL)
- node = route_next (node);
- lsa_prev = prev->info;
- lsa_next = (node ? node->info : NULL);
- assert (lsa_prev);
- assert (lsa_prev->next == lsa_next);
- if (lsa_next)
- assert (lsa_next->prev == lsa_prev);
- zlog_debug ("lsdb_lookup_next: assert OK with previous LSA");
- }
- if (! node)
- return NULL;
- route_unlock_node (node);
- return (struct ospf6_lsa *) node->info;
- }
- /* Iteration function */
- struct ospf6_lsa *
- ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
- {
- struct route_node *node;
- node = route_top (lsdb->table);
- if (node == NULL)
- return NULL;
- /* skip to the existing lsdb entry */
- while (node && node->info == NULL)
- node = route_next (node);
- if (node == NULL)
- return NULL;
- route_unlock_node (node);
- if (node->info)
- ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
- return (struct ospf6_lsa *) node->info;
- }
- struct ospf6_lsa *
- ospf6_lsdb_next (struct ospf6_lsa *lsa)
- {
- struct ospf6_lsa *next = lsa->next;
- ospf6_lsa_unlock (lsa);
- if (next)
- ospf6_lsa_lock (next);
- return next;
- }
- struct ospf6_lsa *
- ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
- struct ospf6_lsdb *lsdb)
- {
- struct route_node *node;
- struct prefix_ipv6 key;
- struct ospf6_lsa *lsa;
- memset (&key, 0, sizeof (key));
- ospf6_lsdb_set_key (&key, &type, sizeof (type));
- ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
- node = lsdb->table->top;
- /* Walk down tree. */
- while (node && node->p.prefixlen <= key.prefixlen &&
- prefix_match (&node->p, (struct prefix *) &key))
- node = node->link[prefix_bit(&key.prefix, node->p.prefixlen)];
- if (node)
- route_lock_node (node);
- while (node && node->info == NULL)
- node = route_next (node);
- if (node == NULL)
- return NULL;
- else
- route_unlock_node (node);
- if (! prefix_match ((struct prefix *) &key, &node->p))
- return NULL;
- lsa = node->info;
- ospf6_lsa_lock (lsa);
- return lsa;
- }
- struct ospf6_lsa *
- ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
- struct ospf6_lsa *lsa)
- {
- struct ospf6_lsa *next = lsa->next;
- if (next)
- {
- if (next->header->type != type ||
- next->header->adv_router != adv_router)
- next = NULL;
- }
- if (next)
- ospf6_lsa_lock (next);
- ospf6_lsa_unlock (lsa);
- return next;
- }
- struct ospf6_lsa *
- ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
- {
- struct route_node *node;
- struct prefix_ipv6 key;
- struct ospf6_lsa *lsa;
- memset (&key, 0, sizeof (key));
- ospf6_lsdb_set_key (&key, &type, sizeof (type));
- /* Walk down tree. */
- node = lsdb->table->top;
- while (node && node->p.prefixlen <= key.prefixlen &&
- prefix_match (&node->p, (struct prefix *) &key))
- node = node->link[prefix_bit(&key.prefix, node->p.prefixlen)];
- if (node)
- route_lock_node (node);
- while (node && node->info == NULL)
- node = route_next (node);
- if (node == NULL)
- return NULL;
- else
- route_unlock_node (node);
- if (! prefix_match ((struct prefix *) &key, &node->p))
- return NULL;
- lsa = node->info;
- ospf6_lsa_lock (lsa);
- return lsa;
- }
- struct ospf6_lsa *
- ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
- {
- struct ospf6_lsa *next = lsa->next;
- if (next)
- {
- if (next->header->type != type)
- next = NULL;
- }
- if (next)
- ospf6_lsa_lock (next);
- ospf6_lsa_unlock (lsa);
- return next;
- }
- void
- ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
- {
- struct ospf6_lsa *lsa;
- for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
- ospf6_lsdb_remove (lsa, lsdb);
- }
- void
- ospf6_lsdb_show (struct vty *vty, int level,
- u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
- struct ospf6_lsdb *lsdb)
- {
- struct ospf6_lsa *lsa;
- void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
- if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
- showfunc = ospf6_lsa_show_summary;
- else if (level == OSPF6_LSDB_SHOW_LEVEL_DETAIL)
- showfunc = ospf6_lsa_show;
- else if (level == OSPF6_LSDB_SHOW_LEVEL_INTERNAL)
- showfunc = ospf6_lsa_show_internal;
- else if (level == OSPF6_LSDB_SHOW_LEVEL_DUMP)
- showfunc = ospf6_lsa_show_dump;
- if (type && id && adv_router)
- {
- lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
- if (lsa)
- {
- if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
- ospf6_lsa_show (vty, lsa);
- else
- (*showfunc) (vty, lsa);
- }
- return;
- }
- if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
- ospf6_lsa_show_summary_header (vty);
- if (type && adv_router)
- lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
- else if (type)
- lsa = ospf6_lsdb_type_head (*type, lsdb);
- else
- lsa = ospf6_lsdb_head (lsdb);
- while (lsa)
- {
- if ((! adv_router || lsa->header->adv_router == *adv_router) &&
- (! id || lsa->header->id == *id))
- (*showfunc) (vty, lsa);
- if (type && adv_router)
- lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
- else if (type)
- lsa = ospf6_lsdb_type_next (*type, lsa);
- else
- lsa = ospf6_lsdb_next (lsa);
- }
- }
- /* Decide new Link State ID to originate.
- note return value is network byte order */
- u_int32_t
- ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
- struct ospf6_lsdb *lsdb)
- {
- struct ospf6_lsa *lsa;
- u_int32_t id = 1;
- for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
- lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
- {
- if (ntohl (lsa->header->id) < id)
- continue;
- if (ntohl (lsa->header->id) > id)
- {
- ospf6_lsa_unlock (lsa);
- break;
- }
- id++;
- }
- return ((u_int32_t) htonl (id));
- }
- /* Decide new LS sequence number to originate.
- note return value is network byte order */
- u_int32_t
- ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
- struct ospf6_lsdb *lsdb)
- {
- struct ospf6_lsa *lsa;
- signed long seqnum = 0;
- /* if current database copy not found, return InitialSequenceNumber */
- lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
- if (lsa == NULL)
- seqnum = INITIAL_SEQUENCE_NUMBER;
- else
- seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
- return ((u_int32_t) htonl (seqnum));
- }
|