Linear search in sanitizer allocator

[jameslarus]

The secondary allocator for large memory blocks (sanitizer_allocator_secondary.h) maintains a linked list of large memory blocks which is iterated with a lock held in GetBlockBegin. The cost of this iteration can be large in a program that uses large regions of memory and a sanitizer that invokes PointerIsMine frequently (e.g. Memoro). The latter test would be more efficiently implemented with a balanced search tree to determine if a pointer is contained within one of the blocks allocated by the secondary allocator.

void *GetBlockBegin(const void *ptr) {
    uptr p = reinterpret_cast<uptr>(ptr);
    SpinMutexLock l(&mutex_);
    uptr nearest_chunk = 0;
    // Cache-friendly linear search.
    for (uptr i = 0; i < n_chunks_; i++) {
      uptr ch = reinterpret_cast<uptr>(chunks_[i]);
      if (p < ch) continue;  // p is at left to this chunk, skip it.
      if (p - ch < p - nearest_chunk)
        nearest_chunk = ch;
    }
    if (!nearest_chunk)
      return nullptr;
    Header *h = reinterpret_cast<Header *>(nearest_chunk);
    CHECK_GE(nearest_chunk, h->map_beg);
    CHECK_LT(nearest_chunk, h->map_beg + h->map_size);
    CHECK_LE(nearest_chunk, p);
    if (h->map_beg + h->map_size <= p)
      return nullptr;
    return GetUser(h);
  }

[kcc]

Yea, this needs a fix. Can't promise it any time soon though -- we are overbooked. Also, not sure about relative priority, as this only affects programs with a really large number of large allocations.
Patches are welcome.

[jameslarus]

Yes, it is true that this primarily affects programs with large number of large allocations (and there are many), but remember that the execution path to determine that a pointer did not come from the allocator (eg alloca) always goes through this function, which locks the list. The locking is a bottleneck on heavily multithreaded programs, even if the list of large blocks is small. I clearly understand that it is not at the top of the list of things to fix, but hopefully it doesn't fall off the bottom.