Undefined behaviour in Support/DJB.h

[troelsfr]

Summary

When LLVM is compiled with undefined behaviour sanitation, the hash function in DJB.h causes following error:

sh
external/llvm-project/llvm/include/llvm/Support/DJB.h:23:12: runtime error: left shift of 4086722279 by 5 places cannot be represented in type 'uint32_t' (aka 'unsigned int')
ISSUE: UndefinedBehaviorSanitizer: undefined-behavior external/llvm-project/llvm/include/llvm/Support/DJB.h:23:12

The issue can be reproduced (and solution verified) using a standalone version of the hash function:

c++
#include <iostream>
#include <cstdint>
#include <string>
  
 inline uint32_t djbHash(std::string Buffer, uint32_t H = 5381) {
   for (unsigned char C : Buffer)
     H = (H  << 5ull) + H + C;
   return H;
 }
  
inline uint32_t djbHashFixed(std::string Buffer, uint64_t H = 5381) {
  for (unsigned char C : Buffer)
    H = ((H & 0xffffffff) << 5ull) + H + C;
  return static_cast<uint32_t>(H);
}

int main()
{
    std::cout << djbHashFixed("Hello world") << std::endl;;
    std::cout << djbHash("Hello world") << std::endl;;
    return 0;
}

Compiling with:

sh
clang++ --std=c++17 -fsanitize=address,integer,undefined -fno-omit-frame-pointer -fno-sanitize-recover=all -g -O0 test.cpp -o test

shows the error occurring in the original hash function, but not in the fixed one:

% ./test
2310742177
test.cpp:7:14: runtime error: left shift of 193458846 by 5 places cannot be represented in type 'uint32_t' (aka 'unsigned int')
ISSUE: UndefinedBehaviorSanitizer: undefined-behavior test.cpp:7:14 in
zsh: abort      ./test

[nikic]

This is not undefined behavior. -fsanitize=integer also enables some instrumentation for well-defined behaviors, e.g. to drive fuzzing. I don't think we should address failures for anything out side the -fsanitize=undefined set in LLVM.

[troelsfr]

Thanks for your comment.

You are completely right. I got misled by the output
SUMMARY: UndefinedbehaviorSanitizer, but after googling the message I
realised that this was a check added to integer in 2020 as you correctly
pointed out.

I am happy for this suggestion to be closed.

[xbolva00]

In D128407#3604905, @troelsfr wrote:

Thanks for your comment.

You are completely right. I got misled by the output
SUMMARY: UndefinedbehaviorSanitizer, but after googling the message I
realised that this was a check added to integer in 2020 as you correctly
pointed out.

I am happy for this suggestion to be closed.

This is something which should be changed, to be less misleading.

llvm/include/llvm/Support/DJB.h

 #ifndef LLVM_SUPPORT_DJB_H
 #define LLVM_SUPPORT_DJB_H
 
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
 
 /// The Bernstein hash function used by the DWARF accelerator tables.
-inline uint32_t djbHash(StringRef Buffer, uint32_t H = 5381) {
+inline uint32_t djbHash(StringRef Buffer, uint64_t H = 5381) {
   for (unsigned char C : Buffer.bytes())
-    H = (H << 5) + H + C;
-  return H;
+    H = ((H & 0xFFFFFFFF) << 5) + H + C;
+  return static_cast<uint32_t>(H);
 }
 
 /// Computes the Bernstein hash after folding the input according to the Dwarf 5
 /// standard case folding rules.
 uint32_t caseFoldingDjbHash(StringRef Buffer, uint32_t H = 5381);
 } // namespace llvm
 
 #endif // LLVM_SUPPORT_DJB_H