NetBSD Problem Report #50681

From www@NetBSD.org  Wed Jan 20 08:32:52 2016
Return-Path: <www@NetBSD.org>
Received: from mail.netbsd.org (mail.NetBSD.org [199.233.217.200])
	(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
	(Client CN "mail.netbsd.org", Issuer "Postmaster NetBSD.org" (verified OK))
	by mollari.NetBSD.org (Postfix) with ESMTPS id 833A07ABF0
	for <gnats-bugs@gnats.NetBSD.org>; Wed, 20 Jan 2016 08:32:52 +0000 (UTC)
Message-Id: <20160120083251.678D47ACCB@mollari.NetBSD.org>
Date: Wed, 20 Jan 2016 08:32:51 +0000 (UTC)
From: markiyan.kushnir@gmail.com
Reply-To: markiyan.kushnir@gmail.com
To: gnats-bugs@NetBSD.org
Subject: memory leak in tdelete(3) when deleting root node
X-Send-Pr-Version: www-1.0

>Number:         50681
>Category:       lib
>Synopsis:       memory leak in tdelete(3) when deleting root node
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    lib-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Wed Jan 20 08:35:00 +0000 2016
>Last-Modified:  Wed Jan 20 19:50:00 +0000 2016
>Originator:     Markiyan Kushnir
>Release:        
>Organization:
private
>Environment:
>Description:
The FreeBSD's implementation of tsearch(3) family is almost literally based on NetBSDS's one.  In NetBSD, the 1.4 revision of tdelete.c (http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/tdelete.c?rev=1.4&content-type=text/x-cvsweb-markup&only_with_tag=MAIN) introduced a case: if the node to delete is the root node, it is not free()'ed by the library.  Applications have to take care of it, which is not a good memory management pattern.
>How-To-Repeat:
I was able to reproduce it on a recent FreeBSD 11-CURRENT, which uses the NetBSD's implementation:

$ cat test-tdelete.c 
#include <search.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

typedef int (*compar_t)(const void *, const void *);

int
main(void)
{
    void *root, *node;

    root = NULL;
    printf("A=%p root=%p\n", tsearch("A", &root, (compar_t)strcmp), root);
    printf("B=%p root=%p\n", tsearch("B", &root, (compar_t)strcmp), root);

    node = tdelete("B", &root, (compar_t)strcmp);
    printf("A=%p root=%p\n", node, root);
    node = tdelete("A", &root, (compar_t)strcmp);
    printf("B=%p root=%p\n", node, root);
}

$ cc test-tdelete.c 
$ valgrind --leak-check=full ./a.out
==94266== Memcheck, a memory error detector
==94266== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==94266== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info
==94266== Command: ./a.out
==94266== 
A=0x5400040 root=0x5400040
B=0x54010e0 root=0x5400040
A=0x5400040 root=0x5400040
B=0x5400040 root=0x0
==94266== 
==94266== HEAP SUMMARY:
==94266==     in use at exit: 4,120 bytes in 2 blocks
==94266==   total heap usage: 3 allocs, 1 frees, 4,144 bytes allocated
==94266== 
==94266== 24 bytes in 1 blocks are definitely lost in loss record 1 of 2
==94266==    at 0x4C236C0: malloc (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==94266==    by 0x4E68434: tsearch (in /lib/libc.so.7)
==94266==    by 0x40084C: main (in /tmp/a.out)
==94266== 
==94266== LEAK SUMMARY:
==94266==    definitely lost: 24 bytes in 1 blocks
==94266==    indirectly lost: 0 bytes in 0 blocks
==94266==      possibly lost: 0 bytes in 0 blocks
==94266==    still reachable: 4,096 bytes in 1 blocks
==94266==         suppressed: 0 bytes in 0 blocks
==94266== Reachable blocks (those to which a pointer was found) are not shown.
==94266== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==94266== 
==94266== For counts of detected and suppressed errors, rerun with: -v
==94266== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

>Fix:
The following fix:
  - removes memory leak
  - in the case if the node to delete is the root node, makes tdelete(3) return NULL, which I believe is better than the current behavior.

$ cat out.diff 
--- /usr/src/lib/libc/stdlib/tdelete.c  2015-02-19 02:38:52.000000000 +0200
+++ /data0/mkushnir/eq/client-chroot/tmp/tdelete.c      2016-01-19 13:59:53.001365000 +0200
@@ -65,8 +65,10 @@
                        q->rlink = (*rootp)->rlink;
                }
        }
-       if (p != *rootp)
-               free(*rootp);                   /* D4: Free node */
+       if (p == *rootp) {
+               p = NULL;
+        }
+       free(*rootp);                           /* D4: Free node */
        *rootp = q;                             /* link parent to new node */
        return p;
 }

>Audit-Trail:
From: "Christos Zoulas" <christos@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/50681 CVS commit: src/lib/libc/stdlib
Date: Wed, 20 Jan 2016 10:31:55 -0500

 Module Name:	src
 Committed By:	christos
 Date:		Wed Jan 20 15:31:55 UTC 2016

 Modified Files:
 	src/lib/libc/stdlib: tdelete.c

 Log Message:
 PR/50681: Markiyan Kushnir: Fix memory leak when we delete the root node.
 It is questionable if we should return NULL in that case, but what is the
 parent of root? The new adjusted root?


 To generate a diff of this commit:
 cvs rdiff -u -r1.6 -r1.7 src/lib/libc/stdlib/tdelete.c

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

From: Markiyan Kushnir <markiyan.kushnir@gmail.com>
To: gnats-bugs@netbsd.org
Cc: 
Subject: Re: lib/50681: memory leak in tdelete(3) when deleting root node
Date: Wed, 20 Jan 2016 21:31:50 +0200

 Based on discussion with Pedro F. Giffuni (pfg@freebsd.org) and
 further with Ed Shouten (ed@freebsd.org), my suggestion to return NULL
 in that case was not correct.  A recent revision of POSIX prescribes
 to return "unspecified non-null pointer" in this case.  So just a
 reversal of revision 1.4 of tdelete.c was suggested.

 --
 Markiyan.


 2016-01-20 10:35 GMT+02:00  <gnats-admin@netbsd.org>:
 > Thank you very much for your problem report.
 > It has the internal identification `lib/50681'.
 > The individual assigned to look at your
 > report is: lib-bug-people.
 >
 >>Category:       lib
 >>Responsible:    lib-bug-people
 >>Synopsis:       memory leak in tdelete(3) when deleting root node
 >>Arrival-Date:   Wed Jan 20 08:35:00 +0000 2016
 >

From: christos@zoulas.com (Christos Zoulas)
To: gnats-bugs@NetBSD.org, lib-bug-people@netbsd.org, 
	gnats-admin@netbsd.org, netbsd-bugs@netbsd.org, 
	markiyan.kushnir@gmail.com
Cc: 
Subject: Re: lib/50681: memory leak in tdelete(3) when deleting root node
Date: Wed, 20 Jan 2016 14:44:14 -0500

 On Jan 20,  7:35pm, markiyan.kushnir@gmail.com (Markiyan Kushnir) wrote:
 -- Subject: Re: lib/50681: memory leak in tdelete(3) when deleting root node

 |  Based on discussion with Pedro F. Giffuni (pfg@freebsd.org) and
 |  further with Ed Shouten (ed@freebsd.org), my suggestion to return NULL
 |  in that case was not correct.  A recent revision of POSIX prescribes
 |  to return "unspecified non-null pointer" in this case.  So just a
 |  reversal of revision 1.4 of tdelete.c was suggested.
 |  

 But that leaks? Right?

 christos

From: Markiyan Kushnir <markiyan.kushnir@gmail.com>
To: Christos Zoulas <christos@zoulas.com>
Cc: gnats-bugs@netbsd.org, lib-bug-people@netbsd.org, gnats-admin@netbsd.org, 
	netbsd-bugs@netbsd.org
Subject: Re: lib/50681: memory leak in tdelete(3) when deleting root node
Date: Wed, 20 Jan 2016 21:49:47 +0200

 so 1.4 put free() under an "if" condition -- which cased the leak.
 Removing just if(), and calling free() unconditionally would fix the
 problem.  In this case, the tdelete() will return the pointer to the
 node that was just deleted, which should be fine according to POSIX.

 --
 Markiyan

 2016-01-20 21:44 GMT+02:00 Christos Zoulas <christos@zoulas.com>:
 > On Jan 20,  7:35pm, markiyan.kushnir@gmail.com (Markiyan Kushnir) wrote:
 > -- Subject: Re: lib/50681: memory leak in tdelete(3) when deleting root node
 >
 > |  Based on discussion with Pedro F. Giffuni (pfg@freebsd.org) and
 > |  further with Ed Shouten (ed@freebsd.org), my suggestion to return NULL
 > |  in that case was not correct.  A recent revision of POSIX prescribes
 > |  to return "unspecified non-null pointer" in this case.  So just a
 > |  reversal of revision 1.4 of tdelete.c was suggested.
 > |
 >
 > But that leaks? Right?
 >
 > christos

NetBSD Home
NetBSD PR Database Search

(Contact us) $NetBSD: query-full-pr,v 1.39 2013/11/01 18:47:49 spz Exp $
$NetBSD: gnats_config.sh,v 1.8 2006/05/07 09:23:38 tsutsui Exp $
Copyright © 1994-2014 The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.