lib/50681: memory leak in tdelete(3) when deleting root node

[markiyan.kushnir%gmail.com@localhost]

>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
>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;
 }