Re: undefined behaviour in hamt.c

[Marc Nieper-Wißkirchen]

Hi Bruno,

thanks for exhibiting this. The complaint by the UB sanitizer is
correct. Although the code won't use the 64-bit value shifted by 65,
it is technically UB. When I wrote the code, I erroneously assumed
that it would not be UB, but that the result of the shift would be
implementation-dependent.

This can easily be fixed, see the attached diff. Could you patch the
upstream version and repeat the clang test? (I don't have clang
installed and currently do not have the time to do a formal commit
myself.)

Marc

diff --git a/lib/hamt.c b/lib/hamt.c
index 2b07cf23b..4018ad34e 100644
--- a/lib/hamt.c
+++ b/lib/hamt.c
@@ -680,6 +680,11 @@ entry_insert (const struct function_table
*functions, Hamt_entry *entry,
       Hamt_entry *new_entry = copy_entry (*elt_ptr);
       if (replace)
         *elt_ptr = NULL;
+      /* We have to take this shortcut as shifting an integer of N
+        bits by N or more bits triggers undefined behavior.
+        See: 
https://lists.gnu.org/archive/html/bug-gnulib/2022-04/msg00023.html.
*/
+      if (depth >= _GL_HAMT_MAX_DEPTH)
+       return (Hamt_entry *) create_populated_bucket (new_entry,
copy_entry (entry));
       return create_populated_subtrie (new_entry, copy_entry (entry), hash,
                                        (hash_element (functions, entry)
                                         >> (5 * depth)), depth);

Am Do., 14. Apr. 2022 um 01:43 Uhr schrieb Bruno Haible <bruno@clisp.org>:
>
> Hi Marc,
>
> When running the gnulib tests with clang's UndefinedBehaviorSanitizer, I got
> this output in test-hamt.log:
>
> ../../gllib/hamt.c:685:41: runtime error: shift exponent 65 is too large for 
> 64-bit type 'size_t' (aka 'unsigned long')
> SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior 
> ../../gllib/hamt.c:685:41 in
> PASS test-hamt (exit status: 0)
>
> How to reproduce:
> 1. Install clang 13.
> 2. Set CC, CXX, CFLAGS, CXXFLAGS:
>    CC="clang 
> -fsanitize=undefined,signed-integer-overflow,shift,integer-divide-by-zero 
> -fno-sanitize=pointer-overflow"; \
>    CXX="clang++ -L/usr/lib/gcc/x86_64-linux-gnu/9 -I/usr/include/c++/9 
> -I/usr/include/x86_64-linux-gnu/c++/9 
> -fsanitize=undefined,signed-integer-overflow,shift,integer-divide-by-zero 
> -fno-sanitize=pointer-overflow"; \
>    CFLAGS="-O1 -fno-omit-frame-pointer -ggdb"; \
>    CXXFLAGS="-O1 -fno-omit-frame-pointer -ggdb"; \
>    export CC CXX CFLAGS CXXFLAGS
>    (The set of -I options in CXX depend on your local g++ installation.)
> 3. Prepare a gnulib testdir.
> 4. Configure, make, make check
> 5. Search the *.log files for 'UndefinedBehaviorSanitizer'.
>
> Bruno
>
>
>