[Libomptarget] Fix bucket selection in MemoryManager.h

[protze.joachim]

Summary

Fixes an integer overflow in floorToPowerOfTwo for 0x8000 0000 (32bit arch) / 0x8000 0000 0000 0000 (64bit arch) and higher.

Fixes the binary search in findBucket to return the intended bucket (e.g., 35 and 120 or 259 and 1020 went to the same bucket).

[tianshilei1992]

I don't understand. Here we all do >> operation. How could it cause overflow?

[protze.joachim]

In D128896#3623818, @tianshilei1992 wrote:

I don't understand. Here we all do >> operation. How could it cause overflow?

The function also has | (soft addition) and one +, which overflows, when you pass 0x8000 0000 to the function. The first few lines propagate the 1 all the way to the right, so that you get 0xFFFF FFFF, adding 1 gives you 0x0.

[tianshilei1992]

In D128896#3624297, @protze.joachim wrote:

In D128896#3623818, @tianshilei1992 wrote:

I don't understand. Here we all do >> operation. How could it cause overflow?

The function also has | (soft addition) and one +, which overflows, when you pass 0x8000 0000 to the function. The first few lines propagate the 1 all the way to the right, so that you get 0xFFFF FFFF, adding 1 gives you 0x0.

I see. Yeah, that should be the case.

openmp/libomptarget/plugins/common/MemoryManager/MemoryManager.h

static size_t floorToPowerOfTwo(size_t Num) {
     Num |= Num >> 16;
 #if INTPTR_MAX == INT64_MAX
     Num |= Num >> 32;
 #elif INTPTR_MAX == INT32_MAX
     // Do nothing with 32-bit
 #else
 #error Unsupported architecture
 #endif
-    Num += 1;
-    return Num >> 1;
+    Num = Num >> 1;
+    return Num + 1;
   }
 
   /// Find a suitable bucket
   static int findBucket(size_t Size) {
     const size_t F = floorToPowerOfTwo(Size);
 
     DP("findBucket: Size %zu is floored to %zu.\n", Size, F);
 
     int L = 0, H = NumBuckets - 1;
-    while (H - L > 1) {
+    while (H >= L) {
       int M = (L + H) >> 1;
-      if (BucketSize[M] == F)
+      if (BucketSize[M] == F) {
+        DP("findBucket: Size %zu goes to bucket %d\n", Size, M);
         return M;
+      }
       if (BucketSize[M] > F)
         H = M - 1;
       else
-        L = M;
+        L = M + 1;
     }
 
-    assert(L >= 0 && L < NumBuckets && "L is out of range");
+    assert(H >= 0 && H < NumBuckets && "H is out of range");
 
-    DP("findBucket: Size %zu goes to bucket %d\n", Size, L);
+    DP("findBucket: Size %zu goes to bucket %d\n", Size, H);
 
-    return L;
+    return H;
   }
 
   /// A structure stores the meta data of a target pointer
   struct NodeTy {
     /// Memory size
     const size_t Size;
     /// Target pointer
     void *Ptr;