From owner-freebsd-ports-bugs@FreeBSD.ORG Wed Mar 8 06:40:08 2006 Return-Path: X-Original-To: freebsd-ports-bugs@hub.freebsd.org Delivered-To: freebsd-ports-bugs@hub.freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id C24C316A420 for ; Wed, 8 Mar 2006 06:40:08 +0000 (GMT) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [216.136.204.21]) by mx1.FreeBSD.org (Postfix) with ESMTP id C3BC843D49 for ; Wed, 8 Mar 2006 06:40:05 +0000 (GMT) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) by freefall.freebsd.org (8.13.4/8.13.4) with ESMTP id k286e5jB002177 for ; Wed, 8 Mar 2006 06:40:05 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.13.4/8.13.4/Submit) id k286e5xN002176; Wed, 8 Mar 2006 06:40:05 GMT (envelope-from gnats) Resent-Date: Wed, 8 Mar 2006 06:40:05 GMT Resent-Message-Id: <200603080640.k286e5xN002176@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-ports-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, dikshie Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id A376616A420 for ; Wed, 8 Mar 2006 06:37:01 +0000 (GMT) (envelope-from dikshie@ipv6.ppk.itb.ac.id) Received: from mx1.itb.ac.id (mx1.ITB.ac.id [167.205.23.6]) by mx1.FreeBSD.org (Postfix) with ESMTP id B0E8743D5F for ; Wed, 8 Mar 2006 06:36:53 +0000 (GMT) (envelope-from dikshie@ipv6.ppk.itb.ac.id) Received: from mx7.itb.ac.id (unknown [IPv6:2001:d30:3:31f:204:acff:fee8:84b4]) by mx1.itb.ac.id (Postfix) with ESMTP id 60F95F76C0 for ; Wed, 8 Mar 2006 13:36:42 +0700 (WIT) Received: from localhost (students.itb.ac.id [167.205.1.73]) by mx7.itb.ac.id (Postfix) with ESMTP id B90AF20AA3 for ; Wed, 8 Mar 2006 13:36:43 +0700 (WIT) Received: from mx7.itb.ac.id ([167.205.30.13]) by localhost (students.itb.ac.id [167.205.1.73]) (amavisd-new, port 10007) with ESMTP id 06321-05 for ; Wed, 8 Mar 2006 13:36:32 +0700 (WIT) Received: from ipv6.ppk.itb.ac.id (ipv6.ppk.itb.ac.id [167.205.30.228]) by mx7.itb.ac.id (Postfix) with ESMTP id 0109020A91 for ; Wed, 8 Mar 2006 13:36:36 +0700 (WIT) Received: by ipv6.ppk.itb.ac.id (Postfix, from userid 1001) id 3A15F11562; Wed, 8 Mar 2006 13:36:30 +0700 (WIT) Message-Id: <20060308063630.3A15F11562@ipv6.ppk.itb.ac.id> Date: Wed, 8 Mar 2006 13:36:30 +0700 (WIT) From: dikshie To: FreeBSD-gnats-submit@FreeBSD.org X-Send-Pr-Version: 3.113 Cc: Subject: ports/94216: add patch to net/zebra X-BeenThere: freebsd-ports-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: dikshie List-Id: Ports bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 08 Mar 2006 06:40:08 -0000 >Number: 94216 >Category: ports >Synopsis: add patch to net/zebra >Confidential: no >Severity: non-critical >Priority: low >Responsible: freebsd-ports-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: update >Submitter-Id: current-users >Arrival-Date: Wed Mar 08 06:40:05 GMT 2006 >Closed-Date: >Last-Modified: >Originator: dikshie >Release: FreeBSD 7.0-CURRENT i386 >Organization: Institute of Technology Bandung, Indonesia >Environment: System: FreeBSD ipv6.ppk.itb.ac.id 7.0-CURRENT FreeBSD 7.0-CURRENT #10: Fri Feb 24 14:50:26 WIT 2006 dikshie@ipv6.ppk.itb.ac.id:/usr/obj/usr/src/sys/PPK i386 >Description: http://marc.theaimsgroup.com/?l=zebra&m=114058002007887&w=2 it makes ospfd use priority queue (using heap sort) for its spf calculation. It should change spf execution time of ospfd from N^2 to N log (N). >How-To-Repeat: >Fix: --- patch-ospfd-pqueue-fixed begins here --- Index: ospfd/ospf_spf.c =================================================================== RCS file: /cvsroot/zebra/ospfd/ospf_spf.c,v retrieving revision 1.124 diff -u -r1.124 ospf_spf.c --- ospfd/ospf_spf.c 28 Mar 2003 19:55:28 -0000 1.124 +++ ospfd/ospf_spf.c 22 Feb 2006 03:03:26 -0000 @@ -29,6 +29,7 @@ #include "table.h" #include "log.h" #include "sockunion.h" /* for inet_ntop () */ +#include "pqueue.h" #include "ospfd/ospfd.h" #include "ospfd/ospf_interface.h" @@ -114,7 +115,7 @@ } void -ospf_vertex_add_parent (struct vertex *v) +ospf_vertex_connect_to_parent (struct vertex *v) { struct vertex_nexthop *nh; listnode node; @@ -458,48 +459,36 @@ } } -void -ospf_install_candidate (list candidate, struct vertex *w) +int +ospf_vertex_cmp (void *a, void *b) { - listnode node; - struct vertex *cw; - - if (list_isempty (candidate)) - { - listnode_add (candidate, w); - return; - } + struct vertex *va = (struct vertex *) a; + struct vertex *vb = (struct vertex *) b; + /* ascending order */ + return (va->distance - vb->distance); +} - /* Install vertex with sorting by distance. */ - for (node = listhead (candidate); node; nextnode (node)) - { - cw = (struct vertex *) getdata (node); - if (cw->distance > w->distance) - { - list_add_node_prev (candidate, node, w); - break; - } - else if (node->next == NULL) - { - list_add_node_next (candidate, node, w); - break; - } - } +void +ospf_install_candidate (struct pqueue *candidate_list, struct vertex *w) +{ + if (IS_DEBUG_OSPF_EVENT) + zlog_info ("candidate: type: %d id: %s p: %p distance: %lu", + w->type, inet_ntoa (w->id), w, (u_long)w->distance); + pqueue_enqueue (w, candidate_list); } /* RFC2328 Section 16.1 (2). */ void ospf_spf_next (struct vertex *v, struct ospf_area *area, - list candidate, struct route_table *rv, + struct pqueue *candidate_list, struct route_table *rv, struct route_table *nv) { struct ospf_lsa *w_lsa = NULL; - struct vertex *w, *cw; + struct vertex *w; u_char *p; u_char *lim; struct router_lsa_link *l = NULL; struct in_addr *r; - listnode node; int type = 0; /* If this is a router-LSA, and bit V of the router-LSA (see Section @@ -618,58 +607,22 @@ else w->distance = v->distance; - /* Is there already vertex W in candidate list? */ - node = ospf_vertex_lookup (candidate, w->id, w->type); - if (node == NULL) - { - /* Calculate nexthop to W. */ - ospf_nexthop_calculation (area, v, w); - - ospf_install_candidate (candidate, w); - } - else - { - cw = (struct vertex *) getdata (node); - - /* if D is greater than. */ - if (cw->distance < w->distance) - { - ospf_vertex_free (w); - continue; - } - /* equal to. */ - else if (cw->distance == w->distance) - { - /* Calculate nexthop to W. */ - ospf_nexthop_calculation (area, v, w); - ospf_nexthop_merge (cw->nexthop, w->nexthop); - list_delete_all_node (w->nexthop); - ospf_vertex_free (w); - } - /* less than. */ - else - { - /* Calculate nexthop. */ - ospf_nexthop_calculation (area, v, w); - - /* Remove old vertex from candidate list. */ - ospf_vertex_free (cw); - listnode_delete (candidate, cw); + /* calculate nexthop */ + ospf_nexthop_calculation (area, v, w); - /* Install new to candidate. */ - ospf_install_candidate (candidate, w); - } - } + /* install candidate */ + ospf_install_candidate (candidate_list, w); } } /* Add vertex V to SPF tree. */ -void +struct vertex * ospf_spf_register (struct vertex *v, struct route_table *rv, struct route_table *nv) { struct prefix p; struct route_node *rn; + struct vertex *cv; p.family = AF_INET; p.prefixlen = IPV4_MAX_BITLEN; @@ -680,7 +633,39 @@ else rn = route_node_get (nv, &p); - rn->info = v; + cv = rn->info; + + /* if the route does not exist yet, just install and return */ + if (! cv) + { + rn->info = v; + return v; + } + + /* if D is greater than. */ + if (cv->distance < v->distance) + ospf_vertex_free (v); + + /* equal to. */ + else if (cv->distance == v->distance) + { + /* Merge nexthop to D. */ + ospf_nexthop_merge (cv->nexthop, v->nexthop); + list_delete_all_node (v->nexthop); + ospf_vertex_free (v); + } + + /* less than. */ + else + { + /* As long as sorting in the candidate_list works, + cv->distance never become more than v->distance + (i.e. (cv->distance > v->distance) should not happen). */ + assert (0); + } + + /* the vertex is dropped anyway */ + return NULL; } void @@ -709,6 +694,7 @@ listnode cnode; listnode nnode; struct vertex_nexthop *nexthop; + struct vertex *w; if (v->type == OSPF_VERTEX_ROUTER) { @@ -734,8 +720,8 @@ for (cnode = listhead (v->child); cnode; nextnode (cnode)) { - v = getdata (cnode); - ospf_spf_dump (v, i); + w = getdata (cnode); + ospf_spf_dump (w, i); } } @@ -895,8 +881,7 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, struct route_table *new_rtrs) { - list candidate; - listnode node; + struct pqueue *candidate_list; struct vertex *v; struct route_table *rv; struct route_table *nv; @@ -925,7 +910,8 @@ nv = route_table_init (); /* Clear the list of candidate vertices. */ - candidate = list_new (); + candidate_list = pqueue_create (); + candidate_list->cmp = ospf_vertex_cmp; /* Initialize the shortest-path tree to only the root (which is the router doing the calculation). */ @@ -939,29 +925,37 @@ for (;;) { - /* RFC2328 16.1. (2). */ - ospf_spf_next (v, area, candidate, rv, nv); + if (v != NULL) + { + if (IS_DEBUG_OSPF_EVENT) + zlog_info ("determined: type: %d id: %s p: %p distance: %lu", + v->type, inet_ntoa (v->id), v, (u_long)v->distance); + + /* RFC2328 16.1. (2). */ + ospf_spf_next (v, area, candidate_list, rv, nv); + } /* RFC2328 16.1. (3). */ /* If at this step the candidate list is empty, the shortest- path tree (of transit vertices) has been completely built and this stage of the procedure terminates. */ - if (listcount (candidate) == 0) + if (candidate_list->size == 0) break; /* Otherwise, choose the vertex belonging to the candidate list that is closest to the root, and add it to the shortest-path tree (removing it from the candidate list in the process). */ - node = listhead (candidate); - v = getdata (node); - ospf_vertex_add_parent (v); - - /* Reveve from the candidate list. */ - listnode_delete (candidate, v); + v = pqueue_dequeue (candidate_list); /* Add to SPF tree. */ - ospf_spf_register (v, rv, nv); + v = ospf_spf_register (v, rv, nv); + + /* Skip rest if the vertex is rejected to be installed in SPF tree */ + if (v == NULL) + continue; + + ospf_vertex_connect_to_parent (v); /* Note that when there is a choice of vertices closest to the root, network vertices must be chosen before router vertices @@ -993,7 +987,7 @@ ospf_spf_route_free (nv); /* Free candidate list */ - list_free (candidate); + pqueue_delete (candidate_list); /* Increment SPF Calculation Counter. */ area->spf_calculation++; --- patch-ospfd-pqueue-fixed ends here --- >Release-Note: >Audit-Trail: >Unformatted: