Adding a key which is a full prefix of another leads to valgrind warning #17
Comments
|
@nmav I agree, there should have been a return error code or something. However, now it would be a breaking API change. |
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 1, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 1, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 1, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 2, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 2, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 2, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 3, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
wez
added a commit
to wez/watchman
that referenced
this issue
Jun 3, 2016
Summary: a facet of the libart implementation that is undocumented except for a series of issues (linked below) is this: an inserted key must not be a full prefix of another key that is already stored in the tree. The recommendation is to store keys that have a terminator character. armon/libart#4 armon/libart#12 armon/libart#14 armon/libart#17 Our usage in watchman can't guarantee to provide a NUL-terminated input, so this diff adjusts the key comparison routines to generate an implicit or synthetic NUL terminator character when comparing one character beyond the end of a key, and by asserting (or allowing ASAN to complain) if we try to look more than 1 character beyond the end. I also tidied up the function signatures of a couple of matching functions so that the semantics are clearer (return boolean true for success rather than integer 0) and removed some redundant casts when invoking callbacks. Test Plan: added an explicit test for the full-prefix issue. Built with -fsanitize=address and ran the integration tests as well as the sparse/unsparse checks I've been using for the pending list changes.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
When trying to add a key which is a full prefix of another key the following valgrind warning is issued:
==2159== Conditional jump or move depends on uninitialised value(s)
==2159== at 0x4015A8: add_child4 (art.c:420)
==2159== by 0x401CBD: recursive_insert (art.c:519)
==2159== by 0x401CBD: art_insert (art.c:583)
==2159== by 0x400842: append (test.c:36)
==2159== by 0x400842: main (test.c:73)
==2159==
==2159== Conditional jump or move depends on uninitialised value(s)
==2159== at 0x4010EA: find_child (art.c:138)
==2159== by 0x40193A: art_search (art.c:249)
==2159== by 0x400852: append (test.c:38)
==2159== by 0x400852: main (test.c:73)
==2159==
While that action is not allowed by the API (according to issue #12), it would be preferable to fail instead of triggering undefined behaviour.
The program triggering that behaviour is at:
http://paste.fedoraproject.org/281806/42043514
The text was updated successfully, but these errors were encountered: