btree off-by-one overflow

[mstniy]

ISSUE:

btree_map.c has an off-by-one overflow on line 378. Although it doesn't seem to cause any immediate problems, its existence can be dynamically shown with the following patch, which checks at run-time whether the call to memmove will cause an overflow:

diff --git a/src/examples/libpmemobj/tree_map/btree_map.c b/src/examples/libpmemobj/tree_map/btree_map.c
index 526548da0..f23af39cc 100644
--- a/src/examples/libpmemobj/tree_map/btree_map.c
+++ b/src/examples/libpmemobj/tree_map/btree_map.c
@@ -8,6 +8,7 @@
 #include <assert.h>
 #include <errno.h>
 #include <stdio.h>
+#include <stdlib.h>
 #include "btree_map.h"
 
 TOID_DECLARE(struct tree_map_node, BTREE_MAP_TYPE_OFFSET + 1);
@@ -376,6 +377,12 @@ btree_map_merge(TOID(struct btree_map) map, TOID(struct tree_map_node) rn,
        /* move everything to the right of the separator by one array slot */
        memmove(D_RW(parent)->items + p, D_RW(parent)->items + p + 1,
        sizeof(struct tree_map_node_item) * (D_RO(parent)->n - p));
+
+       if (p+2+D_RO(parent)->n - p + 1 > BTREE_ORDER) {
+               fprintf(stderr, "Uh oh\n");
+               abort();
+       }
 
        memmove(D_RW(parent)->slots + p + 1, D_RW(parent)->slots + p + 2,
        sizeof(TOID(struct tree_map_node)) * (D_RO(parent)->n - p + 1));

Environment Information

• PMDK package version(s): 1.11.1
• OS(es) version(s): Ubuntu 20.04
• ndctl version(s): 67-1
• kernel version(s): 5.11.0-36
• compiler, libraries, packaging and other related tools version(s): GCC 9.3.0

Please provide a reproduction of the bug:

• Apply the patch to src/examples/libpmemobj/tree_map/btree_map.c
• Re-build the library
• Run the map benchmark: cd src/benchmarks && LD_LIBRARY_PATH=../nondebug ./pmembench pmembench_map.cfg

How often bug is revealed: (always, often, rare):

Rare (never?) without the patch. With the patch, always.

Actual behavior:

The call to memmove does an off-by-one overflow, made evident by the patch, as the benchmark crashes with the message "Uh oh"

Expected behavior:

There should be no out-of-bounds reads, so the patch should not cause the benchmark to crash.

Details

Additional information about Priority and Help Requested:

Are you willing to submit a pull request with a proposed change? (Yes, No)

Requested priority: (Showstopper, High, Medium, Low)

[pbalcer]

Hmm... this doesn't cause any problems because the data from the out of bounds read is inserted in an array location that is > n. So it will never be read without first being overwritten anyway - this is something that valgrind memcheck would detect.

How did you find the issue? Just by analyzing the code?

[mstniy]

Makes sense. I haven't been able to dig deeper into the code, but thought it was interesting that there was an (albeit harmless) overflow.

My colleagues and I are working on a novel tool that extends the address sanitizer's detection capabilities into the pmemobj's persistent heap. This was one of the reported memory violations.