Date: Thu, 30 May 2002 16:01:36 -0700 From: "Qing Li" <Qing.Li@windriver.com> To: <FreeBSD-gnats-submit@FreeBSD.org> Subject: kern/38752: rn_walktree_from not halting at the right node Message-ID: <DMEGKJAJNLKBGDDBEAIPMEFPFCAA.Qing.Li@windriver.com>
next in thread | raw e-mail | index | archive | help
>Number: 38752
>Category: kern
>Synopsis: rn_walktree_from not halting at the right node
>Confidential: no
>Severity: serious
>Priority: high
>Responsible: freebsd-bugs
>State: open
>Quarter:
>Keywords:
>Date-Required:
>Class: sw-bug
>Submitter-Id: current-users
>Arrival-Date: Thu May 30 16:10:02 PDT 2002
>Closed-Date:
>Last-Modified:
>Originator: Qing Li
>Release: FreeBSD 4.6-PRERELEASE i386
>Organization:
>Environment:
System: FreeBSD a.b.c 4.6-PRERELEASE FreeBSD 4.6-PRERELEASE #0: Wed May 15
16:17:16 GMT 2002 root@:/usr/obj/usr/src/sys/GENERIC i386
CPU: Pentium II/Pentium II Xeon/Celeron (265.37-MHz 686-class CPU)
Origin = "GenuineIntel" Id = 0x634 Stepping = 4
Features=0x80f9ff<FPU,VME,DE,PSE,TSC,MSR,PAE,MCE,CX8,SEP,MTRR,PGE,MCA,CMOV,M
MX>
real memory = 167772160 (163840K bytes)
avail memory = 158183424 (154476K bytes)
>Description:
The code in "rn_walktree_from" that checks if we backed up too far
did not stop at the right node.
<snip>
while (!stopping) {
/* printf("node %p (%d)\n", rn, rn->rn_bit); */
base = rn;
/* If at right child go back up, otherwise, go right */
while (rn->rn_parent->rn_right == rn
&& !(rn->rn_flags & RNF_ROOT)) {
rn = rn->rn_parent;
/* if went up beyond last, stop */
if (rn->rn_bit < lastb) {
^^^^^^^^^^^^^^^^^^^^^^^
|||||||||||||||||||||||
stopping = 1;
/* printf("up too far\n"); */
}
}
/* Find the next *leaf* since next node might vanish, too */
for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
rn = rn->rn_left;
<snip>
The IF statement will be true after the complete traversal of
the right branch of its parent, due to the
"rn = rn->rn_parent->rn_right" assignment in the following FOR loop.
One additional problem is the insertion of the default route will
traverse the entire tree.
>How-To-Repeat:
Problem 1, Construct the routing tree to shape as the following:
ROOT
[o]
|
|
[o] ____|_______
|
|
|
(lastb) [o]------------[o]
| |
| |
| |
[o]-----{LF} {LF}------{LF}
|
|
|
{LF}------{LF}
Problem 2, enable IPv6, and after system initialization, add
a default route as in
route add -net -inet6 default -inet6
fe80::2c0:4fff:fe8d:63b9%xl0 -netmask -inet6 default
>Fix:
*** radix.c Tue Apr 30 14:09:48 2002
--- radix.c.new Thu May 30 14:22:44 2002
***************
*** 942,952 ****
rn = rn->rn_parent;
/* if went up beyond last, stop */
! if (rn->rn_bit < lastb) {
stopping = 1;
/* printf("up too far\n"); */
}
}
/* Find the next *leaf* since next node might vanish, too */
for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
--- 942,955 ----
rn = rn->rn_parent;
/* if went up beyond last, stop */
! if (rn->rn_bit <= lastb) {
stopping = 1;
/* printf("up too far\n"); */
}
}
+
+ if (rn->rn_parent->rn_flags & RNF_ROOT)
+ stopping = 1;
/* Find the next *leaf* since next node might vanish, too */
for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
>Release-Note:
>Audit-Trail:
>Unformatted:
SEND-PR: -*- send-pr -*-
SEND-PR: Lines starting with `SEND-PR' will be removed automatically, as
SEND-PR: will all comments (text enclosed in `<' and `>').
SEND-PR:
SEND-PR: Please consult the following URL if you are not sure how to
SEND-PR: fill out a problem report:
SEND-PR: http://www.freebsd.org/doc/en/articles/problem-reports/article.html
SEND-PR:
SEND-PR: Note that the Synopsis field is mandatory.
SEND-PR:
SEND-PR: Please note that (unless you state otherwise) if your report
SEND-PR: includes a patch then it will be taken under the same license as
SEND-PR: the one on the file(s) you want to change.
SEND-PR:
SEND-PR: BE ADVISED THAT FREEBSD PROBLEM REPORTS ARE PUBLIC INFORMATION AND
SEND-PR: WILL BE PUBLISHED AS-IS ON THE PROJECT'S MAILING LISTS AND WEB
SITES.
SEND-PR: DO NOT SUBMIT ANY INFORMATION YOU DO NOT WANT MADE PUBLIC.
SEND-PR:
SEND-PR: For sensitive security issues, consider contacting the FreeBSD
SEND-PR: security officer team (security-officer@freebsd.org) directly.
SEND-PR:
SEND-PR: Choose from the following categories:
SEND-PR:
SEND-PR: advocacy alpha bin conf docs gnu
SEND-PR: i386 kern misc ports sparc
SEND-PR:
To: FreeBSD-gnats-submit@freebsd.org
From: Qing.Li@windriver.com
Reply-To: Qing.Li@windriver.com
Cc:
X-send-pr-version: 3.113
X-GNATS-Notify:
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-bugs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?DMEGKJAJNLKBGDDBEAIPMEFPFCAA.Qing.Li>