| Age | Commit message (Collapse) | Author |
|---|
|
This reverts commit 9289c6ff55cd96c943d23e43fc9e5f987aa965ed.
The commit reverted an earlier change which was fixed a bug that caused
black-holes to remote destinations with multiple paths, that could occur
during convergence. Overall, the previous code is more correct.
|
|
The patch in bug 330 did two things. It add a return value
whether ospf_nexthop_calculation() failed or not and also
moved the return stmt for 16.1.1 para 5 so now SPF
will fallback to the intervening router when no back links are found
by 16.1.1 para 5. This is wrong and can potentially create black holes
or routing loops according to Dave Katz and Acee Lindem at ospf@ietf.org
Even if the current code could be proved to be harmless in all cases,
it adds substantial extra processing and memory allocations.
Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
This is better than a prefix lookup as prefixes may not be
unique, that is, the same prefix can exist on several interfaces.
Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
Maintain router LSA positions in OSPF interface.
Find the OSPF interface in nexthop_calculation using
the position in the router LSA. This is possible because
the only time nexthop_calculation needs to look up interfaces
is when dealing with its own Router LSA.
This has the following advantages:
- Multiple PtP interfaces with the same IP address between two routers.
- Use Unnumbered PtP on just one end of the link.
- Faster OI lookup for the OSPF interface and only
done once for PtoP links.
*ospf_interface.h: (struct ospf_interface) Add storage for
storing router LSA position.
*ospf_interface.c: (ospf_if_lookup_by_lsa_pos)
lookup OSPF I/F in an area using LSA position.
*ospf_lsa.c: (router_lsa_link_set) record Router LSA position.
*ospf_spf.c: (ospf_spf_next) Count and pass along lsa position.
(ospf_nexthop_calculation) Add lsa position argument.
call ospf_if_lookup_by_lsa_pos() for OSFP interface handle.
Clean up and remove all calls ospf_if_is_configured() the
rest. Adjust a few debug logs.
Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
This was found in scale testing at OSR; ospfd is adding the same link
over and over again to the SPF tree. This fix prevents the resulting
memory corruption from happening and adds a debug message to track
occurence of this issue and/or confirm a proper fix.
(This version was improved by Scott Feldman over the earlier RFC.)
* ospfd/ospf_spf.c: (ospf_spf_add_parent) loop over existing vertices
and refuse to add duplicates.
Tested-by: Martin Winter <mwinter@opensourcerouting.org>
Signed-off-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
The code for nssa_range and other bits that were written but
never used.
|
|
* 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
|
|
* ospf_{spf,lsa}.c: remove out of date comment; add comment on some
non-obvious code; Make note of a possible scaling problem.
|
|
* 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.
|
|
* 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.
|
|
* 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.
|
|
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 Paul Jakma <paul.jakma@sun.com>
* ospf_spf.c: (ospf_spf_next) Finish off the explanatory
comment made in previous commit
|
|
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 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 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 Paul Jakma <paul.jakma@sun.com>
* ospf_spf.c: (various) Add more debug statements.
|
|
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 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-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-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.
|
|
|
|
* ospf_{dump,spf,vty}.c: Oops, use the internal tv_sub
function rather than unportable timersub.
|
|
* (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.
|
|
* (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.
|
|
* ospf_dump.c, ospf_ia.c, ospf_spf.c, ospf_ase.c:
remove unused DEBUG
|
|
* 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.
|
|
* (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.
|
|
* (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.
|
|
* 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.
|
|
* *.c: Change level of debug messages to LOG_DEBUG.
|
|
|
|
|
|
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.
|
|
* ospf_spf.c (ospf_nexthop_calculation): Initialize address family
in on-stack struct prefix_ipv4. Fixes point-to-multipoint SPF
calculation.
|
|
* 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.
|
|
* 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.
|
|
from vtysh ([quagga-dev 932]).
|
|
* Add missing 'i' to getopts, short form of --pid_file.
see http://bugzilla.quagga.net/show_bug.cgi?id=25
|
|
* (ospf_spf.c): Fix indentation - primarily the mix of tabs and spaces.
Ran through indent -nut (GNU style, but only spaces for indentation)
|
|
* (ospf_spf.c): Fix consideration of costs for PtP nexthops in
ospf_nexthop_calculation().
|
|
* 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
|
|
* 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
|
|
|
|
|
