NetBSD Problem Report #39684

From www@NetBSD.org  Fri Oct  3 14:08:11 2008
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
	by narn.NetBSD.org (Postfix) with ESMTP id ABA9663BD01
	for <gnats-bugs@gnats.netbsd.org>; Fri,  3 Oct 2008 14:08:11 +0000 (UTC)
Message-Id: <20081003140803.45F5A63BA98@narn.NetBSD.org>
Date: Fri,  3 Oct 2008 14:08:03 +0000 (UTC)
From: m-Matti-a.Lehtonen@IKI.Fi
Reply-To: m-Matti-a.Lehtonen@IKI.Fi
To: gnats-bugs@NetBSD.org
Subject: RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree
X-Send-Pr-Version: www-1.0

>Number:         39684
>Category:       lib
>Synopsis:       RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    lib-bug-people
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Oct 03 14:10:00 +0000 2008
>Closed-Date:    Sat Feb 14 22:53:11 +0000 2009
>Last-Modified:  Mon Feb 23 09:15:02 +0000 2009
>Originator:     Lehtonen, Matti
>Release:        --
>Organization:
Helsinki Institute for Information Technology HIIT
>Environment:
/*	$NetBSD: tree.h,v 1.16 2008/03/21 13:07:15 ad Exp $	*/
/*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/
>Description:
RB_REMOVE trashes root of tree (set to NULL), when requested to remove object that isn't in tree.

I would expect that "nothing" is done, when removing object that isn't in tree, instead of losing the whole tree.
>How-To-Repeat:
Try to remove an object from [populated] tree that isn't actually inserted there.
>Fix:
Make sure that object exists (by e.g. RB_INSERT() or RB_FIND() ) in tree, before remove operation.

>Release-Note:

>Audit-Trail:
From: Antti Kantee <pooka@cs.hut.fi>
To: gnats-bugs@NetBSD.org
Cc: 
Subject: Re: lib/39684: RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree
Date: Fri, 3 Oct 2008 18:00:21 +0300

 On Fri Oct 03 2008 at 14:10:00 +0000, m-Matti-a.Lehtonen@IKI.Fi wrote:
 > RB_REMOVE trashes root of tree (set to NULL), when requested to remove object that isn't in tree.
 > 
 > I would expect that "nothing" is done, when removing object that isn't in tree, instead of losing the whole tree.
 > >How-To-Repeat:
 > Try to remove an object from [populated] tree that isn't actually inserted there.
 > >Fix:
 > Make sure that object exists (by e.g. RB_INSERT() or RB_FIND() ) in tree, before remove operation.

 IMHO this is a case of "garbage in, garbage out".  You should probably
 add a "ONTREE" flag or somesuch to your local data structure.

State-Changed-From-To: open->feedback
State-Changed-By: pooka@NetBSD.org
State-Changed-When: Tue, 07 Oct 2008 01:03:20 +0300
State-Changed-Why:
I'd like to close this per the reason cited in the email.  Ok?


From: "Matti Lehtonen" <m-Matti-a.Lehtonen@IKI.Fi>
To: gnats-bugs@netbsd.org
Cc: lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org, gnats-admin@netbsd.org, 
	pooka@netbsd.org
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)
Date: Tue, 7 Oct 2008 11:26:59 +0300

 ------=_Part_47536_2261053.1223368019867
 Content-Type: text/plain; charset=ISO-8859-1
 Content-Transfer-Encoding: 7bit
 Content-Disposition: inline

 Hi!

 In perfect world that "garbage in, garbage out" reasoning would be good
 enough. However, this isn't perfect world, there aren't applications that
 are *perfect*.

 Let's hope that this function isn't ever used in mission critical
 environments like hospital devices, aeroplanes, satellites, nuclear plants
 etc

 Lehtonen, Matti

 2008/10/7 <pooka@netbsd.org>

 > Synopsis: RB_REMOVE trashes link to tree, when requested to remove object
 > that isn't in tree
 >
 > State-Changed-From-To: open->feedback
 > State-Changed-By: pooka@NetBSD.org
 > State-Changed-When: Tue, 07 Oct 2008 01:03:20 +0300
 > State-Changed-Why:
 > I'd like to close this per the reason cited in the email.  Ok?
 >
 >
 >
 >


 -- 
 Life is complex. It has real and imaginary parts.

 ------=_Part_47536_2261053.1223368019867
 Content-Type: text/html; charset=ISO-8859-1
 Content-Transfer-Encoding: 7bit
 Content-Disposition: inline

 <div dir="ltr">Hi!<br><br>In perfect world that &quot;garbage in, garbage out&quot; reasoning would be good enough. However, this isn&#39;t perfect world, there aren&#39;t applications that are *perfect*. <br>
 <br>
 Let&#39;s hope that this function isn&#39;t ever used in mission critical environments like hospital devices, aeroplanes, satellites, nuclear plants etc<br>
 <br>
 Lehtonen, Matti<br><br><div class="gmail_quote">2008/10/7  <span dir="ltr">&lt;<a href="mailto:pooka@netbsd.org">pooka@netbsd.org</a>&gt;</span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
 Synopsis: RB_REMOVE trashes link to tree, when requested to remove object that isn&#39;t in tree<br>
 <br>
 State-Changed-From-To: open-&gt;feedback<br>
 State-Changed-By: pooka@NetBSD.org<br>
 State-Changed-When: Tue, 07 Oct 2008 01:03:20 +0300<br>
 State-Changed-Why:<br>
 I&#39;d like to close this per the reason cited in the email. &nbsp;Ok?<br>
 <br>
 <br>
 <br>
 </blockquote></div><br><br clear="all"><br>-- <br>Life is complex. It has real and imaginary parts. <br><br>
 </div>

 ------=_Part_47536_2261053.1223368019867--

From: "Matti Lehtonen" <m-Matti-a.Lehtonen@IKI.Fi>
To: gnats-bugs@netbsd.org
Cc: lib-bug-people@netbsd.org, netbsd-bugs@netbsd.org, gnats-admin@netbsd.org, 
	pooka@netbsd.org
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)
Date: Tue, 7 Oct 2008 13:53:35 +0300

 Hi!

 In perfect world that "garbage in, garbage out" reasoning would be
 good enough. However, this isn't perfect world, there aren't
 applications that are *perfect*.

 Let's hope that this function isn't ever used in mission critical
 environments like hospital devices, aeroplanes, satellites, nuclear
 plants etc

 Lehtonen, Matti

 2008/10/7 <pooka@netbsd.org>
 >
 > Synopsis: RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree
 >
 > State-Changed-From-To: open->feedback
 > State-Changed-By: pooka@NetBSD.org
 > State-Changed-When: Tue, 07 Oct 2008 01:03:20 +0300
 > State-Changed-Why:
 > I'd like to close this per the reason cited in the email.  Ok?
 >
 >
 >



 --
 Life is complex. It has real and imaginary parts.

From: Quentin Garnier <cube@cubidou.net>
To: Matti Lehtonen <m-Matti-a.Lehtonen@IKI.Fi>
Cc: gnats-bugs@netbsd.org, pooka@netbsd.org
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to
	remove object that isn't in tree)
Date: Tue, 7 Oct 2008 13:48:27 +0200

 --QD1r0wI5tTrL9hxl
 Content-Type: text/plain; charset=us-ascii
 Content-Disposition: inline
 Content-Transfer-Encoding: quoted-printable

 On Tue, Oct 07, 2008 at 01:53:35PM +0300, Matti Lehtonen wrote:
 > Hi!
 >=20
 > In perfect world that "garbage in, garbage out" reasoning would be
 > good enough. However, this isn't perfect world, there aren't
 > applications that are *perfect*.
 >=20
 > Let's hope that this function isn't ever used in mission critical
 > environments like hospital devices, aeroplanes, satellites, nuclear
 > plants etc

 You know, the fact that you're the one letting your code logic do
 something that it should not do puts you in a very bad position to make
 such comments.  If code of yours runs into any of the devices you list,
 could you tell us brands and exact models?  I feel kind of worried.

 --=20
 Quentin Garnier - cube@cubidou.net - cube@NetBSD.org
 "See the look on my face from staying too long in one place
 [...] every time the morning breaks I know I'm closer to falling"
 KT Tunstall, Saving My Face, Drastic Fantastic, 2007.

 --QD1r0wI5tTrL9hxl
 Content-Type: application/pgp-signature
 Content-Disposition: inline

 -----BEGIN PGP SIGNATURE-----
 Version: GnuPG v1.4.9 (NetBSD)

 iQEcBAEBAgAGBQJI60yKAAoJENgoQloHrPno5ywH/i6Jqq3FPYGrR0blqq0onkq2
 TC3dSYdvqQsbX3V3VBRLJv+JF0beu1MsJoQhCvbYmfyjYhcz2RqcHLO0TxlDtwa5
 QnVQj7lEX0nLVkQ7w0Qs8zgMHMrgGaxhcy20TM7bAgr2GuZfNolyfhrDZER2CV6Q
 i/nlO120kYUcBUEcO/fg/UERmJKnLYnbAmvfnFoYo1YKEqajb67AHGXIiTvtj++F
 C9dgcMUQoQAo8Rr7TS9OcHrJyVkQSAGBp+M/nFYtVj/AtTOTsfuwPefPGnlI0r6a
 7PRL/y3Rq9JjiL5V1grU7cOccwavcWo7os50nLHDUR1einpPB7i/YbjjHwPGJnU=
 =OTR+
 -----END PGP SIGNATURE-----

 --QD1r0wI5tTrL9hxl--

From: Alan Barrett <apb@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/39684 CVS commit: src/share/man/man3
Date: Tue,  7 Oct 2008 13:03:50 +0000 (UTC)

 Module Name:	src
 Committed By:	apb
 Date:		Tue Oct  7 13:03:50 UTC 2008

 Modified Files:
 	src/share/man/man3: queue.3 tree.3

 Log Message:
 Add a NOTE saying that invalid usage leads to undefined behaviour.
 Inspired by PR 39684.


 To generate a diff of this commit:
 cvs rdiff -r1.38 -r1.39 src/share/man/man3/queue.3
 cvs rdiff -r1.3 -r1.4 src/share/man/man3/tree.3

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

From: christos@zoulas.com (Christos Zoulas)
To: gnats-bugs@NetBSD.org, lib-bug-people@netbsd.org, 
	gnats-admin@netbsd.org, netbsd-bugs@netbsd.org, 
	m-Matti-a.Lehtonen@IKI.Fi
Cc: 
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)
Date: Tue, 7 Oct 2008 14:13:58 -0400

 On Oct 7, 11:50am, cube@cubidou.net (Quentin Garnier) wrote:
 -- Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to 

 |  You know, the fact that you're the one letting your code logic do
 |  something that it should not do puts you in a very bad position to make
 |  such comments.  If code of yours runs into any of the devices you list,
 |  could you tell us brands and exact models?  I feel kind of worried.

 Well, this is really not productive. I think that the submitter here
 has a point. The manual page states:

      Accordingly, RB_REMOVE() and SPLAY_REMOVE() return the pointer to the
      removed element, otherwise they return NULL to indicate an error.

 Looking at the red-black code this is a lie. It never returns NULL and it
 should really either:
 	1. not trash the tree or
 	2. at least document that it will trash the tree

 christos

From: Quentin Garnier <cube@cubidou.net>
To: Christos Zoulas <christos@zoulas.com>
Cc: gnats-bugs@NetBSD.org
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to
	remove object that isn't in tree)
Date: Tue, 7 Oct 2008 20:33:57 +0200

 --CpYjv1NmbuaesVen
 Content-Type: text/plain; charset=us-ascii
 Content-Disposition: inline
 Content-Transfer-Encoding: quoted-printable

 On Tue, Oct 07, 2008 at 02:13:58PM -0400, Christos Zoulas wrote:
 > On Oct 7, 11:50am, cube@cubidou.net (Quentin Garnier) wrote:
 > -- Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested=
  to=20
 >=20
 > |  You know, the fact that you're the one letting your code logic do
 > |  something that it should not do puts you in a very bad position to make
 > |  such comments.  If code of yours runs into any of the devices you list,
 > |  could you tell us brands and exact models?  I feel kind of worried.
 >=20
 > Well, this is really not productive. I think that the submitter here
 > has a point. The manual page states:
 >=20
 >      Accordingly, RB_REMOVE() and SPLAY_REMOVE() return the pointer to the
 >      removed element, otherwise they return NULL to indicate an error.
 >=20
 > Looking at the red-black code this is a lie. It never returns NULL and it
 > should really either:
 > 	1. not trash the tree or
 > 	2. at least document that it will trash the tree

 I don't see how the submitter's use of the function is different from,
 say, doing strlen(NULL).  And would you really think there is a need to
 mention that you shouldn't do strlen(NULL) in strlen(3)?

 If so you have a huge documentation task ahead of you.

 --=20
 Quentin Garnier - cube@cubidou.net - cube@NetBSD.org
 "See the look on my face from staying too long in one place
 [...] every time the morning breaks I know I'm closer to falling"
 KT Tunstall, Saving My Face, Drastic Fantastic, 2007.

 --CpYjv1NmbuaesVen
 Content-Type: application/pgp-signature
 Content-Disposition: inline

 -----BEGIN PGP SIGNATURE-----
 Version: GnuPG v1.4.9 (NetBSD)

 iQEcBAEBAgAGBQJI66uUAAoJENgoQloHrPnokIIH/R5eVthsHDm3fhnXYw4LGo1N
 LJxp397lLqETYOylqz1P8WPPOjIFM7zXP1bWvBiGFnyq9T7CN2TDX8QpoxfKpIrF
 Ydr8RVHpfX0HpzPRg9LHk1meaqfNCbrU0s/eAheAdjDR6xsT5EBDzWYLx809KHeK
 s07GzzvgMjZA0265G5mZwy5XHYa8bylI8ZhnyeFK11kMlpZNFhgDILpckAzWN/eM
 JExyfAJ3hC9vDkU0G6LdF7hz2qFDNOXXAnnlcOn/mAvkcVrQclgBblah9hMlDUGN
 rJG0fFZ61HfTzQQJPJUxI5sm0X8G7z0kXo1aRjonEW7drYLxpnqnmeOplfta4H0=
 =rLmp
 -----END PGP SIGNATURE-----

 --CpYjv1NmbuaesVen--

From: christos@zoulas.com (Christos Zoulas)
To: Quentin Garnier <cube@cubidou.net>
Cc: gnats-bugs@NetBSD.org
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)
Date: Tue, 7 Oct 2008 14:42:35 -0400

 On Oct 7,  8:33pm, cube@cubidou.net (Quentin Garnier) wrote:
 -- Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to 

 | I don't see how the submitter's use of the function is different from,
 | say, doing strlen(NULL).  And would you really think there is a need to
 | mention that you shouldn't do strlen(NULL) in strlen(3)?
 | 
 | If so you have a huge documentation task ahead of you.

 I am not planning to do this of course and I understand what you are saying.
 The issue here is that the documentation used to say that it would return
 NULL on error and the code did not. Now it has been fixed.

 christos

From: "Matti Lehtonen" <m-Matti-a.Lehtonen@IKI.Fi>
To: gnats-bugs@netbsd.org
Cc: lib-bug-people@netbsd.org, gnats-admin@netbsd.org, netbsd-bugs@netbsd.org
Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)
Date: Wed, 8 Oct 2008 10:31:01 +0300

 Hi!

 Documenting features *correctly* is okay, returning NULL on error is
 excellent and not trashing tree is superb.

 Lehtonen, Matti

 2008/10/7 Christos Zoulas <christos@zoulas.com>:
 > The following reply was made to PR lib/39684; it has been noted by GNATS.
 >
 > From: christos@zoulas.com (Christos Zoulas)
 > To: Quentin Garnier <cube@cubidou.net>
 > Cc: gnats-bugs@NetBSD.org
 > Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to remove object that isn't in tree)
 > Date: Tue, 7 Oct 2008 14:42:35 -0400
 >
 >  On Oct 7,  8:33pm, cube@cubidou.net (Quentin Garnier) wrote:
 >  -- Subject: Re: lib/39684 (RB_REMOVE trashes link to tree, when requested to
 >
 >  | I don't see how the submitter's use of the function is different from,
 >  | say, doing strlen(NULL).  And would you really think there is a need to
 >  | mention that you shouldn't do strlen(NULL) in strlen(3)?
 >  |
 >  | If so you have a huge documentation task ahead of you.
 >
 >  I am not planning to do this of course and I understand what you are saying.
 >  The issue here is that the documentation used to say that it would return
 >  NULL on error and the code did not. Now it has been fixed.
 >
 >  christos
 >
 >



 -- 
 Life is complex. It has real and imaginary parts.

From: "David A. Holland" <dholland@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/39684 CVS commit: src/share/man/man3
Date: Sat, 14 Feb 2009 22:07:04 +0000 (UTC)

 Module Name:	src
 Committed By:	dholland
 Date:		Sat Feb 14 22:07:04 UTC 2009

 Modified Files:
 	src/share/man/man3: tree.3

 Log Message:
 Document that the element argument of RB_REMOVE must be present in the
 tree. Minor adjoining grammar fix. PR 39684.
 Bump date.


 To generate a diff of this commit:
 cvs rdiff -r1.4 -r1.5 src/share/man/man3/tree.3

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

State-Changed-From-To: feedback->closed
State-Changed-By: dholland@NetBSD.org
State-Changed-When: Sat, 14 Feb 2009 22:53:11 +0000
State-Changed-Why:
I think that since the remove operation takes an object (as opposed to
e.g. a key to look up to find an object) it makes sense for it to 
require that the object be actually in the tree it's to be removed from.
The analogous remove operation in any linked list library, if it needs
the list head at all, will require that the node to be removed be on the
list whose head is provided, and not some other list or no list.

However, because there's also a perfectly valid model where a tree is a
lookup table and it makes sense to ask the tree to remove any object(s)
matching some lookup key, and it's not entirely obvious at first glance
that this model doesn't apply to RB_REMOVE, I've documented the requirement
prominently.

It doesn't appear all that practical or particularly desirable to check
if the object and tree passed in match up; also, if the object isn't on
*any* tree the link pointers might equally likely be uninitialized, and
then you get nasal demons in any event.

Hopefully this will satisfy everyone... patches to improve the docs
further are of course always welcome.


From: Soren Jacobsen <snj@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/39684 CVS commit: [netbsd-5] src/share/man/man3
Date: Mon, 23 Feb 2009 09:12:21 +0000 (UTC)

 Module Name:	src
 Committed By:	snj
 Date:		Mon Feb 23 09:12:21 UTC 2009

 Modified Files:
 	src/share/man/man3 [netbsd-5]: tree.3

 Log Message:
 Pull up following revision(s) (requested by dholland in ticket #466):
 	share/man/man3/tree.3: revision 1.5
 Document that the element argument of RB_REMOVE must be present in the
 tree. Minor adjoining grammar fix. PR 39684.
 Bump date.


 To generate a diff of this commit:
 cvs rdiff -r1.4 -r1.4.2.1 src/share/man/man3/tree.3

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

>Unformatted:

Home	PR Database Search