[PATCH] tsearch.3: tdelete() can return dangling pointers

[Jann Horn <jannh@xxxxxxxxxx>]

POSIX says that deleting the root node must cause tdelete() to return some
unspecified non-NULL pointer. Glibc implements it by returning a dangling
pointer to the (freed) root node:

$ cat bogus_tdelete.c
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <err.h>
#include <assert.h>

static void *root = NULL;

static void *xmalloc(unsigned n) {
    void *p;
    p = malloc(n);
    if (!p)
        err(1, "malloc");
    return p;
}

static int compare(const void *pa, const void *pb) {
    if (*(int *) pa < *(int *) pb)
        return -1;
    if (*(int *) pa > *(int *) pb)
        return 1;
    return 0;
}

int main(void) {
    int *ptr;
    void *val, *parent;

    ptr = xmalloc(sizeof(int));
    *ptr = 1234;
    val = tsearch((void*)ptr, &root, compare);
    assert(*(int**)val == ptr);
    printf("root: %p\n", root);

    parent = tdelete((void*)ptr, &root, compare);
    printf("tdelete return value: %p; new root: %p\n", parent, root);

    return 0;
}
$ gcc -o bogus_tdelete bogus_tdelete.c -std=gnu99 -Wall
$ gdb ./bogus_tdelete
GNU gdb (GDB) 7.9-gg19
[...]
(gdb) break free
Function "free" not defined.
Make breakpoint pending on future shared library load? (y or [n]) y
Breakpoint 1 (free) pending.
(gdb) run
Starting program: /usr/local/google/home/jannh/tmp/bogus_tdelete
[...]
root: 0x555555756030

Breakpoint 1, 0x00007ffff7ab54e0 in free () from [...]
(gdb) print (void*)$rdi
$1 = (void *) 0x555555756030
(gdb) cont
Continuing.
tdelete return value: 0x555555756030; new root: (nil)
[Inferior 1 (process 56564) exited normally]
(gdb) quit

Therefore, explicitly note that tdelete() may return bad pointers that must
not be accessed.

Signed-off-by: Jann Horn <jannh@xxxxxxxxxx>
---
 man3/tsearch.3 | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/man3/tsearch.3 b/man3/tsearch.3
index 5cbc8b7a4..464fcae76 100644
--- a/man3/tsearch.3
+++ b/man3/tsearch.3
@@ -180,6 +180,9 @@ the item whose node is returned is unspecified.
 .BR tdelete ()
 returns a pointer to the parent of the node deleted, or
 NULL if the item was not found.
+If the deleted node was the root node,
+.BR tdelete ()
+returns a dangling pointer that must not be accessed.
 .PP
 .BR tsearch (),
 .BR tfind (),
-- 
2.16.2.804.g6dcf76e118-goog

--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html