quadratic behavior in SyncTab::GetAndLock

[ramosian-glider]

Originally reported on Google Code with ID 26

% cat atomic_stress.cc 
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
  int n = argc == 1 ? 100 : atoi(argv[1]);
  int n_iter = 10000;
  int *a = new int [n];
  printf("n: %5d:  ", n);
  for (int i = 0; i < n_iter; i++) {
    for (int j = 0; j < n; j++) {
      __sync_lock_test_and_set(a + j, 0);
    }
  }
  return 0;
}
% clang -pie -fPIE -fsanitize=thread -O atomic_stress.cc
% for((i=128; i<=1024*1024; i*=2)); do (TIMEFORMAT=%R;  time ./a.out $i) ; done
n:   128:  0.328
n:   256:  0.690
n:   512:  4.380
n:  1024:  19.285
n:  2048:  87.791

Profile: 
    87.93%    a.out  a.out              [.] __tsan::SyncTab::GetAndLock(__tsan::ThreadState*,
unsigned long, unsigned long, bool, bool)
     2.59%    a.out  a.out              [.] __tsan_atomic32_exchange
     1.31%    a.out  a.out              [.] __tsan::Mutex::Unlock()

The code: 
  if (PrimaryAllocator::PointerIsMine((void*)addr)) {
    MBlock *b = user_mblock(thr, (void*)addr);
    CHECK_NE(b, 0);
    MBlock::ScopedLock l(b);
    SyncVar *res = 0;
    int iter = 0;
    for (res = b->ListHead(); res; res = res->next) {
      iter++;
      if (res->addr == addr)
        break;
    }

Obviously, if a given heap-allocated block has N objects accessed atomically, we will
spend O(N) time handling each of them. 
This was previously known, but one of our users has hit it in a real test.

We may need a more efficient data structure here :( 

Reported by konstantin.s.serebryany on 2013-08-22 09:45:46

[ramosian-glider]

Fixed by r209810.

Now numbers look like:
n:   128:  0.172
n:   256:  0.284
n:   512:  0.469
n:  1024:  0.852
n:  2048:  1.679
n:  4096:  3.298
n:  8192:  6.618
n: 16384:  13.252

Reported by dvyukov@google.com on 2014-05-29 13:59:09

• Status changed: Fixed

[ramosian-glider]

Adding Project:ThreadSanitizer as part of GitHub migration.

Reported by glider@google.com on 2015-07-30 09:21:30

• Labels added: ProjectThreadSanitizer