summaryrefslogtreecommitdiff
path: root/ospfd/ospf_spf.c
AgeCommit message (Collapse)Author
2011-09-27ospfd: sizing macros cleanupDenis Ovsienko
* ospf_spf.c * ROUTER_LSA_TOS_SIZE: prepend OSPF_ and move to ospf_lsa.h * ROUTER_LSA_MIN_SIZE: replace with existing OSPF_ROUTER_LSA_LINK_SIZE
2009-08-03ospfd: update some commentsPaul Jakma
* ospf_{spf,lsa}.c: remove out of date comment; add comment on some non-obvious code; Make note of a possible scaling problem.
2009-08-03ospfd: Change struct ospf_path *oi to ifindex.Joakim Tjernlund
* global: In struct ospf_path, change struct ospf_interface *oi to int ifindex. It is unsafe to reference *oi as an ospf interface can be deleted under your feet. Use a weak reference instead.
2009-07-30ospfd: Discriminate better when selecting links between vertices in SPFJoakim Tjernlund
* ospf_spf.c: (ospf_get_next_link) One must check the vertex type, Router or Network, to select type link to match against. Link type 1 has neighbour router ID in link_id and link type 2 has IP address of DR. Since router id may have same value as an existing IP address one risks matching a router ID against a DR.
2008-09-04[ospfd] Minor enhancements to recent self-host-routes suppression patchPaul Jakma
* ospf_spf.c: (ospf_spf_process_stubs) Track whether parent router vertex is the root, so that the host-route suppression logic need only be activated for such vertices. Move the actual logic to ospf_intra_add_stub. * ospf_route.c: (ospf_intra_add_stub) Main test of link moved here, notionally more appropriate.
2008-08-25Ignore host routes to self.Joakim Tjernlund
PtP links with /32 masks adds host routes to the remote host, see RFC 2328, 12.4.1.1, Option 1. Make sure that such routes are ignored
2007-08-07[ospfd] Finish explanatory comment started in previous commit..Paul Jakma
2007-08-07 Paul Jakma <paul.jakma@sun.com> * ospf_spf.c: (ospf_spf_next) Finish off the explanatory comment made in previous commit
2007-08-06[ospfd] Fix bad SPF calculation on some topologies - incorrect sortingPaul Jakma
2007-08-07 Atis Elsts <atis@mikrotik.com> * ospf_spf.c: (ospf_spf_next) Sort heap in correct direction after vertex cost is changed, thus fixing incorrect SPF calculation on certain topologies. * lib/pqueue.{c,h}: Export trickle_up
2007-05-07[ospfd] Bug #330 regression: Fix ospf_spf_add_parent assertPaul Jakma
2007-05-07 Paul Jakma <paul.jakma@sun.com> * ospf_spf.c: (ospf_vertex_new) Dont init vertices to infinity, just let 0 be a special case. (ospf_spf_add_parent) 0 distance candidate vertex is special, cost still to be initialised - asserting that new distance is <= existing only makes sense where w already has a cost. (ospf_spf_next) Infinite cost links should not be followed, bar those of the root.
2007-03-23[ospfd] Bug #330 regression: failure to calculate routes through networksPaul Jakma
2007-03-23 Paul Jakma <paul.jakma@sun.com> * ospf_spf.c: (ospf_nexthop_calculation) Fix silly regression causing ospfd to fail to calculate paths past networks not attached to root vertex, introduced with bug #330 fixes.
2007-03-23[ospfd] Instrument ospf_spf with more debug log messagesPaul Jakma
2007-03-23 Paul Jakma <paul.jakma@sun.com> * ospf_spf.c: (various) Add more debug statements.
2007-02-26[ospfd] Fix regression in SPF introduced by bug#330 fixesPaul Jakma
2007-02-26 Paul Jakma <paul.jakma@sun.com> * ospf_spf.c: Fix regression introduced with bug #330 fix: The cost update added to ospf_spf_add_parent only handled PtP case, differing from same functionality in higher-level ospf_spf_next. Regression diagnosed by Anders Pedersen, mailnews+router-quagga-dev@news.cohaesio.com. (ospf_vertex_new) Initialise vertices to max-cost. (ospf_spf_init) Root vertex always creates with 0 cost. (ospf_spf_add_parent) Remove the buggy V->W cost calculating code, instead take the new distance as a parameter. (ospf_nexthop_calculation) Take distance as parameter, so it can be passed down to add_parent. (ospf_spf_next) Dont initialise candiate vertex distance, vertex_new does so already. Pass distance down to nexthop_calculation (see above).
2007-01-24[ospfd] Bug #330: SPF must consider that nexthop-calc may failPaul Jakma
2007-01-24 Paul Jakma <paul.jakma@sun.com> * ospf_spf.c: Bug #330: Nexthop calculation sometimes may fail, and it needs to indicate this result to SPF. (ospf_spf_add_parent) Flush of parent list needs to be done here, for simplicity. (ospf_nexthop_calculation) Caller needs to know whether nexthop calculation succeeded. Every return statement must correctly indicate such. (ospf_spf_next) Queueing/prioritisation of vertices in SPF must take into account whether nexthop_calculation succeeded, or SPF may fail to find best paths.
2006-08-27[ospfd] Bug #134, ospfd should be more robust to backward time changePaul Jakma
2006-08-25 Paul Jakma <paul.jakma@sun.com> * (general) Bug #134. Be more robust to backward time changes, use the newly added libzebra time functions. In most cases: recent_time -> recent_relative_time() gettimeofday -> quagga_gettime (QUAGGA_CLK_MONOTONIC, ..) time -> quagga_time. (ospf_make_md5_digest) time() call deliberately not changed. (ospf_external_lsa_refresh) remove useless gettimeofday, LSA tv_orig time was already set in ospf_lsa_new, called via ospf_external_lsa_new.
2006-05-04[ospfd] Fix SPF of virtual-linksPaul Jakma
2006-04-24 Paul Jakma <paul.jakma@sun.com> * (general) More Virtual-link fixes, again with much help in testing / debug from Juergen Kammer. Primarily in SPF. * ospf_spf.h: Add guard. ospf_interface.h will include this header. * ospf_interface.h: Modify ospf_vl_lookup definition to take struct ospf as argument, so as to allow for NULL area argument. (struct ospf_vl_data) Remove out_oi, instead add a struct vertex_nexthop, to use as initial nexthop for backbone paths through a vlink. * ospf_interface.c: (ospf_vl_lookup) Modified to allow NULL area to be passed to indicate "any" (first) area. Add extra debug. (ospf_vl_set_params) vl_oi -> nexthop. Add extra debug. (ospf_vl_up_check) Fix debug, inet_ntoa returns a static buffer.. * ospf_route.c: (ospf_intra_add_router) Vlinks dont go through backbone, don't bother checking. * ospf_spf.c: (static struct list vertex_list) Record vertices that will need to be freed. (cmp) Order network before router vertices, as required, wasn't implemented. (vertex_nexthop_free) Mild additional robustness check. (vertex_parent_free) Take void argument, as this function is passed as list deconstructor for vertex parent list. (ospf_vertex_new) More debug. Set deconstructor for parent list. Track allocated vertices on the vertex_list. (ospf_vertex_free) Get rid of the tricky recursive cleanup of vertices. Now frees only the given vertex. (ospf_vertex_add_parent) Fix assert. (ospf_nexthop_calculation) Fix calculation of nexthop for VLink vertices, lookup the vl_data and use its previously recorded nexthop information. (ospf_spf_calculate) Vertices are freed simply by deleting vertex_list nodes and letting ospf_vertex_free as deconstructor work per-node. (ospf_spf_calculate_timer) Trivial optimisation, leave backbone SPF calculation till last to reduce SPF churn on VLink updates. * ospf_vty.c: (ospf_find_vl_data) update call to ospf_vl_lookup (no_ospf_area_vlink_cmd) ditto. (show_ip_ospf_interface_sub) For Vlinks, the peer address is more interesting than the output interface.
2005-11-11[ospfd] SPF ospf_canonical_nexthops_free bugfix.paul
2005-11-042005-11-04 Paul Jakma <paul.jakma@sun.com>paul
* ospf_{dump,spf,vty}.c: Oops, use the internal tv_sub function rather than unportable timersub.
2005-10-212005-10-21 Paul Jakma <paul.jakma@sun.com>paul
* (general) SPF millisecond resolution timer with adaptive, linear back-off holdtime. Prettification of ospf_timer_dump. * ospf_dump.c: (ospf_timeval_dump) new function. The guts of ospf_timer_dump, but made to be more dynamic in printing out the relative timeval, sliding the precision printed out according to the value. (ospf_timer_dump) guts moved to ospf_timeval_dump. * ospf_dump.h: export ospf_timeval_dump. * ospf_flood.c: (ospf_flood) remove gettimeofday, use the libzebra exported recent_time instead, as it's not terribly critical to have time exactly right - the dropped LSA will be retransmited to us if we don't ACK it. * ospf_packet.c: (ospf_ls_upd_timer) Ditto, but here we're not transmitting, just putting LSA back on update transmit list. * ospfd.h: delay and holdtimes should be unsigned. Add spf_max_holdtime and spf_hold_multiplier. Update default defines for delay and hold time to be in msec. (struct ospf) change the SPF timestamp to a struct timeval. Remove ospf_timers_spf_(un)?set. * ospfd.c: (ospf_timers_spf_{set,unset}) removed. (ospf_new) initialise spf_max_holdtime and spf_hold_multiplier * ospf_spf.c: (ospf_spf_calculate) SPF timestamp is a timeval now, update with gettimeofday. (ospf_spf_calculate_schedule) Change SPF timers to millisecond resolution. Make the holdtime be adaptive, with a linear increase in holdtime ever consecutive SPF run which occurs within holdtime of previous SPF, bounded by spf_max_holdtime. * ospf_vty.c: Update spf timers commands. (ospf_timers_spf_set) trivial helper. (ospf_timers_throttle_spf_cmd) new command to set SPF delay, initial hold and max hold times with millisecond resolution. (ospf_timers_spf_cmd) Deprecated. Accept the old values, convert to msec, truncate to new limits. (no_ospf_timers_throttle_spf_cmd) set timers to defaults. (no_ospf_timers_spf_cmd) deprecated form, same as previous. (show_ip_ospf_cmd) Display SPF parameters and times. (show_ip_ospf_neighbour_header) Centralise the 'sh ip os ne' header. (show_ip_ospf_neighbor_sub) Fix the field widths. Get rid of the multiple spaces which were making the lines even longer. (show_ip_ospf_neighbor_cmd) Use show_ip_ospf_neighbour_header (show_ip_ospf_neighbor_all_cmd) ditto and fix the field widths for NBMA neighbours. (show_ip_ospf_neighbor_int) Use header function. (show_ip_ospf_nbr_nbma_detail_sub) use sizeof for timebuf, local array - safer. (show_ip_ospf_neighbor_detail_sub) ditto (ospf_vty_init) install the new SPF throttle timer commands.
2005-10-182005-10-18 Paul Jakma <paul.jakma@sun.com>paul
* (general) SPF memory management cleanup and fix for rare double-free bug. * ospf_spf.h: (struct vertex_parent) New struct to hold parent specific data, eg the backlink and the parent vertex pointer, and point to the appropriate general struct vertex_nexthop. (struct vertex_nexthop) remove parent vertex pointer, so this struct can be shared across vertices. (struct vertex) rename list child to list children. Remove list of nexthops, replace with list of vertex_parents. * ospf_spf.c: (update_stat) trivial, remove cast from void *. (vertex_nexthop_new) remove init of parent - field is gone from struct vertex_nexthop. (ospf_canonical_nexthops_free) Remove the canonical vertex_nexthop memory objects. These are the vertex_nexthops attached to the first level of router vertices from the root. (vertex_parent_new) new function, create a vertex_parent. (vertex_parent_free) ditto, but free it. (ospf_vertex_new) Update to match changes to struct vertex. (ospf_vertex_free) Recursively free a struct vertex and its children. The parent list is used as a reference count. vertex_nexthops must be free seperately, if required. (ospf_vertex_dump) update to match struct vertex changes. Print out backlink of parents too. (ospf_vertex_add_parent) ditto. (ospf_lsa_has_link) update comment. (ospf_nexthop_add_unique) removed, not needed anymore. (ospf_nexthop_merge) ditto. (ospf_spf_consider_nexthop) renamed to ospf_spf_add_parent. Simplified to just create vertex_parent and add it. (ospf_spf_flush_parents) new function, flush out the parent list. (ospf_nexthop_calculation) Take the relevant route_lsa_link as an argument, which simplifies things and removes the need for the hack in ospf_nexthop_add_unique - ospf_spf_next already knew exactly which link the cost calculated was for. Update to match struct vertex changes too. (ospf_spf_next) Don't create a vertex for W unnecessarily, if it's there's a vertex already created for W, use it, and hence there's no need to free it either. Update some manipulation/comparisons of distance to match. Flush the parent list if a lower cost path is found. (ospf_spf_route_free) unused, removed. (ospf_spf_dump) match the struct vertex changes, and dump the ifname if possible. (ospf_spf_calculate) At end of SPF, free the canonical nexthops and call ospf_vertex_free on the root vertex to free the entire tree. * ospf_interface.c: (ospf_vl_set_params) match struct vertex changes. * ospf_route.c: (ospf_intra_route_add) ditto (ospf_route_copy_nexthops_from_vertex) ditto * memtypes.c: (memory_list_ospf) Add MTYPE_OSPF_VERTEX_PARENT.
2005-10-012005-09-30 Vincent Jardin <vincent.jardin@6wind.com>jardin
* ospf_dump.c, ospf_ia.c, ospf_spf.c, ospf_ase.c: remove unused DEBUG
2005-06-132005-06-13 Paul Jakma <paul.jakma@sun.com>paul
* ospf_spf.c: Try get more information on a SEGV under ospf_spf_vertex_add_parent. (ospf_vertex_free) NULL out the child and nexthop lists (ospf_vertex_add_parent) nexthop and child can not be NULL vertex_nexthop's parent->child list can not be NULL (ospf_spf_next) w and cw are per-loop iteration variables, move declarations into loop body.
2005-05-062005-05-06 Paul Jakma <paul.jakma@sun.com>paul
* (general) extern and static qualifiers added. unspecified arguments in definitions fixed, typically they should be 'void'. function casts added for callbacks. Guards added to headers which lacked them. Proper headers included rather than relying on incomplete definitions. gcc noreturn function attribute where appropriate. * ospf_opaque.c: remove the private definition of ospf_lsa's ospf_lsa_refresh_delay. * ospf_lsa.h: export ospf_lsa_refresh_delay * ospf_packet.c: (ospf_make_md5_digest) make *auth_key const, correct thing to do - removes need for the casts later. * ospf_vty.c: Use vty.h's VTY_GET_INTEGER rather than ospf_vty's home-brewed versions, shuts up several warnings. * ospf_vty.h: remove VTY_GET_UINT32. VTY_GET_IPV4_ADDRESS and VTY_GET_IPV4_PREFIX moved to lib/vty.h. * ospf_zebra.c: (ospf_distribute_list_update_timer) hacky overloading of the THREAD_ARG pointer should at least use uintptr_t.
2005-04-072005-04-07 Paul Jakma <paul.jakma@sun.com>paul
* (global): Fix up list loops to match changes in lib/linklist, and some basic auditing of usage. * configure.ac: define QUAGGA_NO_DEPRECATED_INTERFACES * HACKING: Add notes about deprecating interfaces and commands. * lib/linklist.h: Add usage comments. Rename getdata macro to listgetdata. Rename nextnode to listnextnode and fix its odd behaviour to be less dangerous. Make listgetdata macro assert node is not null, NULL list entries should be bug condition. ALL_LIST_ELEMENTS, new macro, forward-referencing macro for use with for loop, Suggested by Jim Carlson of Sun. Add ALL_LIST_ELEMENTS_RO for cases which obviously do not need the "safety" of previous macro. LISTNODE_ADD and DELETE macros renamed to ATTACH, DETACH, to distinguish from the similarly named functions, and reflect their effect better. Add a QUAGGA_NO_DEPRECATED_INTERFACES define guarded section with the old defines which were modified above, for backwards compatibility - guarded to prevent Quagga using it.. * lib/linklist.c: fix up for linklist.h changes. * ospf6d/ospf6_abr.c: (ospf6_abr_examin_brouter) change to a single scan of the area list, rather than scanning all areas first for INTER_ROUTER and then again for INTER_NETWORK. According to 16.2, the scan should be area specific anyway, and further ospf6d does not seem to implement 16.3 anyway.
2005-02-23 * ospf_lsa.h: New flag to the LSA structure for the SPF calculation.hasso
* ospf_lsdb.h: Export ospf_lsdb_clean_stat() function. * ospf_spf.h: Add link to the LSA stat structure into vertex. * ospf_spf.c: New functions cmp() and update_stat() to manage candidates. Remove ospf_spf_has_vertex(), ospf_vertex_lookup(), ospf_install_candidate() and ospf_spf_register() functions not needed any more. Update ospf_vertex_new(), ospf_spf_next() and ospf_spf_calculate() functions to use pqueue instead of linked list.
2004-12-082004-12-08 Andrew J. Schorr <ajschorr@alumni.princeton.edu>ajs
* *.c: Change level of debug messages to LOG_DEBUG.
2004-10-08Compiler warnings fixes round 1.hasso
2004-09-23Remove usage of evil list and listnode typedefs.hasso
2004-08-31Assorted changes from work at BBN. Most are minor, and several are ingdt
support of more significant changes not in this commit. The last item in the ChangeLog below may be needed for p2mp to work correctly. 2004-08-31 David Wiggins <dwiggins@bbn.com> * hash.c (hash_iterate): Save next pointer before calling procedure, so that iteration works even if the called procedure deletes the hash backet. * linklist.h (listtail): new macro, not yet used. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_spf.c (ospf_spf_calculate): Many more comments and debug print statements. New function ospf_vertex_dump used in debugging. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_spf.h (struct vertex): Comments for flags and structure members. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_route.c: When finding an alternate route, log cost as well. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_interface.c (ospf_lookup_if_params): Initialize af in struct prefix allocated on stack. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_packet.c (ospf_ls_ack_send_delayed): In p2mp mode, send acks to AllSPFRouters, rather than All-DR.
2004-08-272004-08-27 David Wiggins <dwiggins@bbn.com>gdt
* ospf_spf.c (ospf_nexthop_calculation): Initialize address family in on-stack struct prefix_ipv4. Fixes point-to-multipoint SPF calculation.
2004-08-052004-08-04 Paul Jakma <paul@dishone.st>paul
* ospf_spf.c: (ospf_spf_consider_nexthop) Add comment about issue. Compare only against list head - all nexthops must be same cost anyway, fixes a reference-listnode-after-delete bug noted by Kir Kostuchenko. (ospf_nexthop_calculation) Use ospf_spf_consider_nexthop for all candidates attached to root.
2004-04-082004-04-08 Paul Jakma <paul@dishone.st>paul
* ospf_spf.h: Add backlink field to struct vertex * ospf_spf.h: (ospf_vertex_new) initialise backlink (ospf_lsa_has_link) return index of link back to vertex V from candidate vertex W, or -1 if no link exists. (ospf_spf_next) save backlink index for candidate vertex * ospf_interface.c: (ospf_vl_set_params) Use the backlink index to determine correct address for virtual-link peers. Fall back to older "pick first link" method if no backlink index exists.
2004-03-04Many warning fixes from PC Drew ([quagga-dev 940]) and removing using PAGERhasso
from vtysh ([quagga-dev 932]).
2003-08-102003-08-10 amir <amir@datacore.ch>paul
* Add missing 'i' to getopts, short form of --pid_file. see http://bugzilla.quagga.net/show_bug.cgi?id=25
2003-06-062003-06-07 Paul Jakma <paul@dishone.st>paul
* (ospf_spf.c): Fix indentation - primarily the mix of tabs and spaces. Ran through indent -nut (GNU style, but only spaces for indentation)
2003-06-062003-06-7 kamatchi soundaram <kamatchi@tdd.sj.nec.com>paul
* (ospf_spf.c): Fix consideration of costs for PtP nexthops in ospf_nexthop_calculation().
2003-04-042003-04-04 Paul Jakma <paul@dishone.st>paul
* Sync to Zebra CVS * Fix lib/thread.h leak * Fix small Opaque LSA leak * Do not configure OSPF interfaces for secondary addresses * vtysh fixes from Hasso * Dave Watson's missing ntohs fix
2003-03-252003-03-25 Paul Jakma <paul@dishone.st>paul
* sync to latest zebra CVS * spec file: updated and added define for ospf-api/client NB: OSPF-API has been broken by the zebra.org changes, which has added struct ospf * as a new arg to many functions
2002-12-13ospfd Point-to-Multipoint supportpaul
2002-12-13Initial revisionpaul