From owner-freebsd-bugs@FreeBSD.ORG Fri Jan 4 02:10:00 2013 Return-Path: Delivered-To: freebsd-bugs@smarthost.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.FreeBSD.org [8.8.178.115]) by hub.freebsd.org (Postfix) with ESMTP id 8B8EBFB9 for ; Fri, 4 Jan 2013 02:10:00 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:1900:2254:206c::16:87]) by mx1.freebsd.org (Postfix) with ESMTP id 6DEE92DA for ; Fri, 4 Jan 2013 02:10:00 +0000 (UTC) Received: from freefall.freebsd.org (localhost [127.0.0.1]) by freefall.freebsd.org (8.14.5/8.14.5) with ESMTP id r042A0Im091542 for ; Fri, 4 Jan 2013 02:10:00 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.5/8.14.5/Submit) id r042A0g8091541; Fri, 4 Jan 2013 02:10:00 GMT (envelope-from gnats) Resent-Date: Fri, 4 Jan 2013 02:10:00 GMT Resent-Message-Id: <201301040210.r042A0g8091541@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Keith Sklower Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id E85A0E7D for ; Fri, 4 Jan 2013 02:03:14 +0000 (UTC) (envelope-from sklower@isi.deterlab.net) Received: from users.isi.deterlab.net (users.isi.deterlab.net [206.117.25.49]) by mx1.freebsd.org (Postfix) with ESMTP id C43BA2C3 for ; Fri, 4 Jan 2013 02:03:14 +0000 (UTC) Received: from users.isi.deterlab.net (localhost.isi.deterlab.net [127.0.0.1]) by users.isi.deterlab.net (8.14.5/8.14.4) with ESMTP id r041jBGf003569; Thu, 3 Jan 2013 17:45:11 -0800 (PST) (envelope-from sklower@users.isi.deterlab.net) Received: (from sklower@localhost) by users.isi.deterlab.net (8.14.5/8.13.8/Submit) id r041jBwb003568; Thu, 3 Jan 2013 17:45:11 -0800 (PST) (envelope-from sklower) Message-Id: <201301040145.r041jBwb003568@users.isi.deterlab.net> Date: Thu, 3 Jan 2013 17:45:11 -0800 (PST) From: Keith Sklower To: FreeBSD-gnats-submit@FreeBSD.org X-Send-Pr-Version: 3.113 Subject: kern/174959: [patch] rnh_walktree_from visits spurious nodes Cc: deter-ops@isi.edu X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: Keith Sklower List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 Jan 2013 02:10:00 -0000 >Number: 174959 >Category: kern >Synopsis: [patch] rnh_walktree_from visits spurious nodes >Confidential: no >Severity: serious >Priority: low >Responsible: freebsd-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: sw-bug >Submitter-Id: current-users >Arrival-Date: Fri Jan 04 02:10:00 UTC 2013 >Closed-Date: >Last-Modified: >Originator: Keith Sklower >Release: FreeBSD 9.1-RC2 i386 >Organization: University of California, Berkeley >Environment: System: FreeBSD users.isi.deterlab.net 9.1-RC2 FreeBSD 9.1-RC2 #7: Tue Oct 9 19:14:50 PDT 2012 root@users.isi.deterlab.net:/usr/obj/usr/src/sys/USERS9 i386 any machine, any version of FreeBSD after 2.3 >Description: The radix tree method rnh_walktree_from (as implemented by rn_walktree_from in /sys/net/radix.c) invokes the helper function f on nodes that it should not, even when supplied with inputs adhering to its unreasonably strict assumptions. It is low priority because nothing in the source distribution uses this function anymore. We have a local need for it. >How-To-Repeat: Construct a routing tree with the following 4 routes: 128.32.8.0/24 128.32.9.0/24 128.32.8.1 (host) 128.32.8.2 (host) invoke rn_walktree_from(tree, 128.32.9.0, 255.255.255.0, f, 0) where f prints the IP address in each leaf visited. [I can supply 94 line C program that demonstrates this at user level] It should only visit 128.32.9.0/24; instead it visits the entire tree. >Fix: --- radix.c 2012-11-28 10:23:37.000000000 -0800 +++ radix.c.pfix 2013-01-03 16:12:33.000000000 -0800 @@ -1009,11 +1009,11 @@ /* * Two cases: either we stepped off the end of our mask, * in which case last == rn, or we reached a leaf, in which - * case we want to start from the last node we looked at. - * Either way, last is the node we want to start from. + * case we want to start from the leaf. */ - rn = last; - lastb = rn->rn_bit; + if (rn-> rn_bit >= 0) + rn = last; + lastb = last->rn_bit; /* printf("rn %p, lastb %d\n", rn, lastb);*/ >Release-Note: >Audit-Trail: >Unformatted: