destroy_node() case NODE48, not handled properly about libart HOT 7 CLOSED

--- a/common/lib/art.c +++ b/common/lib/art.c @@ -95,7 +95,7 @@ static void destroy_node(art_node *n, art_freevalue free_func, void *ctx) { } // Handle each node type - int i; + int i, idx; union { art_node4 *p1; art_node16 *p2; @@ -119,8 +119,10 @@ static void destroy_node(art_node *n, art_freevalue free_func, void *ctx) { case NODE48: p.p3 = (art_node48*)n; - for (i=0;i<n->num_children;i++) { - destroy_node(p.p3->children[i], free_func, ctx); + for (i=0;i<256; i++) { + idx = ((art_node48*)n)->keys[i]; + if (!idx) continue; + destroy_node(p.p3->children[idx-1], free_func, ctx); } break; @@ -169,7 +171,10 @@ static art_node** find_child(art_node *n, unsigned char c) { case NODE4: p.p1 = (art_node4*)n; for (i=0;i < n->num_children; i++) { - if (p.p1->keys[i] == c) + /* this cast works around a bug in gcc 5.1 when unrolling loops + * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124 + */ + if (((unsigned char*)p.p1->keys)[i] == c) return &p.p1->children[i]; } break; @@ -296,18 +301,18 @@ static art_leaf* minimum(const art_node *n) { int idx; switch (n->type) { case NODE4: - return minimum(((art_node4*)n)->children[0]); + return minimum(((const art_node4*)n)->children[0]); case NODE16: - return minimum(((art_node16*)n)->children[0]); + return minimum(((const art_node16*)n)->children[0]); case NODE48: idx=0; - while (!((art_node48*)n)->keys[idx]) idx++; - idx = ((art_node48*)n)->keys[idx] - 1; - return minimum(((art_node48*)n)->children[idx]); + while (!((const art_node48*)n)->keys[idx]) idx++; + idx = ((const art_node48*)n)->keys[idx] - 1; + return minimum(((const art_node48*)n)->children[idx]); case NODE256: idx=0; - while (!((art_node256*)n)->children[idx]) idx++; - return minimum(((art_node256*)n)->children[idx]); + while (!((const art_node256*)n)->children[idx]) idx++; + return minimum(((const art_node256*)n)->children[idx]); default: abort(); } @@ -322,18 +327,18 @@ static art_leaf* maximum(const art_node *n) { int idx; switch (n->type) { case NODE4: - return maximum(((art_node4*)n)->children[n->num_children-1]); + return maximum(((const art_node4*)n)->children[n->num_children-1]); case NODE48: idx=255; - while (!((art_node48*)n)->keys[idx]) idx--; - idx = ((art_node48*)n)->keys[idx] - 1; - return maximum(((art_node48*)n)->children[idx]); + while (!((const art_node48*)n)->keys[idx]) idx--; + idx = ((const art_node48*)n)->keys[idx] - 1; + return maximum(((const art_node48*)n)->children[idx]); case NODE256: idx=255; - while (!((art_node256*)n)->children[idx]) idx--; - return maximum(((art_node256*)n)->children[idx]); + while (!((const art_node256*)n)->children[idx]) idx--; + return maximum(((const art_node256*)n)->children[idx]); default: abort(); } @@ -879,8 +884,7 @@ static int leaf_prefix_matches(const art_leaf *n, const unsigned char *prefix, i int art_iter_prefix(art_tree *t, const unsigned char *key, int key_len, art_callback cb, void *data) { art_node **child; art_node *n = t->root; - uint32_t prefix_len; - int depth = 0; + int prefix_len, depth = 0; while (n) { // Might be a leaf if (IS_LEAF(n)) { @@ -906,7 +910,7 @@ int art_iter_prefix(art_tree *t, const unsigned char *key, int key_len, art_call prefix_len = prefix_mismatch(n, key, key_len, depth); // Guard if the mis-match is longer than the MAX_PREFIX_LEN - if (prefix_len > n->partial_len) { + if ((uint32_t)prefix_len > n->partial_len) { prefix_len = n->partial_len; } @@ -915,7 +919,7 @@ int art_iter_prefix(art_tree *t, const unsigned char *key, int key_len, art_call return 0; // If we've matched the prefix, iterate on this node - } else if (depth + prefix_len == (uint32_t) key_len) { + } else if (depth + prefix_len == key_len) { return recursive_iter(n, cb, data); } Thanks

-kiru *From:* AntonyMCs [mailto:[email protected]] *Sent:* Wednesday, November 22, 2017 4:47 AM *To:* armon/libart *Cc:* kirubakk; Mention *Subject:* Re: [armon/libart] destroy_node() case NODE48, not handled properly (#32) @armon <https://github.com/armon> I'm experiencing the same issue. It's pretty easy to reproduce with the following example: `START_TEST(test_art_insert) { art_tree t; int res = art_tree_init(&t); fail_unless(res == 0); int len; char buf[512]; FILE *f = fopen("tests/words.txt", "r"); uintptr_t line = 1; while (fgets(buf, sizeof buf, f)) { len = strlen(buf); buf[len-1] = '\0'; fail_unless(NULL == art_insert(&t, (unsigned char*)buf, len, (void*)line)); fail_unless(art_size(&t) == line); line++; } uintptr_t a; a = (uintptr_t )art_search(&t, (const unsigned char *) "A", 2); printf("Value of A: %" PRIuPTR "\n", a); a = (uintptr_t )art_delete(&t, (const unsigned char *) "A", 2); printf("Value of A: %" PRIuPTR "\n", a); a = (uintptr_t )art_search(&t, (const unsigned char *) "A", 2); printf("Value of A: %" PRIuPTR "\n", a); res = art_tree_destroy(&t); fail_unless(res == 0); } END_TEST` $ scons && LD_LIBRARY_PATH=deps/check-0.9.8/src/.libs:. valgrind --leak-check=full ./test_runner ... Running suite(s): art Value of A: 1 Value of A: 1 Value of A: 0 ==16772== ==16772== HEAP SUMMARY: ==16772== in use at exit: 2,784 bytes in 55 blocks ==16772== total heap usage: 845,047 allocs, 844,992 frees, 28,872,413 bytes allocated ==16772== ==16772== 1,196 (168 direct, 1,028 indirect) bytes in 1 blocks are definitely lost in loss record 31 of 31 ==16772== at 0x4C2FB55: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==16772== by 0x5043099: alloc_node (art.c:34) ==16772== by 0x5043099: add_child4 (art.c:494) ==16772== by 0x5043C2E: add_child (art.c:511) ==16772== by 0x5043C2E: recursive_insert (art.c:628) ==16772== by 0x5043C2E: art_insert (art.c:643) ==16772== by 0x400E9B: test_art_insert (test_art.c:25) ==16772== by 0x4E3EACA: tcase_run_tfun_fork (check_run.c:353) ==16772== by 0x4E3EACA: srunner_iterate_tcase_tfuns (check_run.c:166) ==16772== by 0x4E3EACA: srunner_run_tcase (check_run.c:286) ==16772== by 0x4E3EACA: srunner_iterate_suites (check_run.c:141) ==16772== by 0x4E3EACA: srunner_run_all (check_run.c:535) ==16772== by 0x400C87: main (runner.c:29) ==16772== ==16772== LEAK SUMMARY: ==16772== definitely lost: 168 bytes in 1 blocks ==16772== indirectly lost: 1,028 bytes in 28 blocks ==16772== possibly lost: 0 bytes in 0 blocks ==16772== still reachable: 1,588 bytes in 26 blocks ==16772== suppressed: 0 bytes in 0 blocks ==16772== Reachable blocks (those to which a pointer was found) are not shown. ==16772== To see them, rerun with: --leak-check=full --show-leak-kinds=all ==16772== ==16772== For counts of detected and suppressed errors, rerun with: -v ==16772== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) 100%: Checks: 1, Failures: 0, Errors: 0 So it seems that when there are manual removes from the tree, it's not properly released with the destroy method. If this is the expected behavior, can you please specify how is it supposed to be done? I would like to be able to selectively remove some entries and then release the full tree without traversing it. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#32 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKo-GNTF3feGe-vFRTC4zU3SuyZQAjdHks5s41oFgaJpZM4MPQ4i> .