tsan_dense_alloc.h revision 1.2 
1//===-- tsan_dense_alloc.h --------------------------------------*- C++ -*-===//
2//
3// This file is distributed under the University of Illinois Open Source
4// License. See LICENSE.TXT for details.
5//
6//===----------------------------------------------------------------------===//
7//
8// This file is a part of ThreadSanitizer (TSan), a race detector.
9//
10// A DenseSlabAlloc is a freelist-based allocator of fixed-size objects.
11// DenseSlabAllocCache is a thread-local cache for DenseSlabAlloc.
12// The only difference with traditional slab allocators is that DenseSlabAlloc
13// allocates/free indices of objects and provide a functionality to map
14// the index onto the real pointer. The index is u32, that is, 2 times smaller
15// than uptr (hense the Dense prefix).
16//===----------------------------------------------------------------------===//
17#ifndef TSAN_DENSE_ALLOC_H
18#define TSAN_DENSE_ALLOC_H
19
20#include "sanitizer_common/sanitizer_common.h"
21#include "tsan_defs.h"
22#include "tsan_mutex.h"
23
24namespace __tsan {
25
26class DenseSlabAllocCache {
27  static const uptr kSize = 128;
28  typedef u32 IndexT;
29  uptr pos;
30  IndexT cache[kSize];
31  template<typename T, uptr kL1Size, uptr kL2Size> friend class DenseSlabAlloc;
32};
33
34template<typename T, uptr kL1Size, uptr kL2Size>
35class DenseSlabAlloc {
36 public:
37  typedef DenseSlabAllocCache Cache;
38  typedef typename Cache::IndexT IndexT;
39
40  explicit DenseSlabAlloc(const char *name) {
41    // Check that kL1Size and kL2Size are sane.
42    CHECK_EQ(kL1Size & (kL1Size - 1), 0);
43    CHECK_EQ(kL2Size & (kL2Size - 1), 0);
44    CHECK_GE(1ull << (sizeof(IndexT) * 8), kL1Size * kL2Size);
45    // Check that it makes sense to use the dense alloc.
46    CHECK_GE(sizeof(T), sizeof(IndexT));
47    internal_memset(map_, 0, sizeof(map_));
48    freelist_ = 0;
49    fillpos_ = 0;
50    name_ = name;
51  }
52
53  ~DenseSlabAlloc() {
54    for (uptr i = 0; i < kL1Size; i++) {
55      if (map_[i] != 0)
56        UnmapOrDie(map_[i], kL2Size * sizeof(T));
57    }
58  }
59
60  IndexT Alloc(Cache *c) {
61    if (c->pos == 0)
62      Refill(c);
63    return c->cache[--c->pos];
64  }
65
66  void Free(Cache *c, IndexT idx) {
67    DCHECK_NE(idx, 0);
68    if (c->pos == Cache::kSize)
69      Drain(c);
70    c->cache[c->pos++] = idx;
71  }
72
73  T *Map(IndexT idx) {
74    DCHECK_NE(idx, 0);
75    DCHECK_LE(idx, kL1Size * kL2Size);
76    return &map_[idx / kL2Size][idx % kL2Size];
77  }
78
79  void FlushCache(Cache *c) {
80    SpinMutexLock lock(&mtx_);
81    while (c->pos) {
82      IndexT idx = c->cache[--c->pos];
83      *(IndexT*)Map(idx) = freelist_;
84      freelist_ = idx;
85    }
86  }
87
88  void InitCache(Cache *c) {
89    c->pos = 0;
90    internal_memset(c->cache, 0, sizeof(c->cache));
91  }
92
93 private:
94  T *map_[kL1Size];
95  SpinMutex mtx_;
96  IndexT freelist_;
97  uptr fillpos_;
98  const char *name_;
99
100  void Refill(Cache *c) {
101    SpinMutexLock lock(&mtx_);
102    if (freelist_ == 0) {
103      if (fillpos_ == kL1Size) {
104        Printf("ThreadSanitizer: %s overflow (%zu*%zu). Dying.\n",
105            name_, kL1Size, kL2Size);
106        Die();
107      }
108      VPrintf(2, "ThreadSanitizer: growing %s: %zu out of %zu*%zu\n",
109          name_, fillpos_, kL1Size, kL2Size);
110      T *batch = (T*)MmapOrDie(kL2Size * sizeof(T), name_);
111      // Reserve 0 as invalid index.
112      IndexT start = fillpos_ == 0 ? 1 : 0;
113      for (IndexT i = start; i < kL2Size; i++) {
114        new(batch + i) T;
115        *(IndexT*)(batch + i) = i + 1 + fillpos_ * kL2Size;
116      }
117      *(IndexT*)(batch + kL2Size - 1) = 0;
118      freelist_ = fillpos_ * kL2Size + start;
119      map_[fillpos_++] = batch;
120    }
121    for (uptr i = 0; i < Cache::kSize / 2 && freelist_ != 0; i++) {
122      IndexT idx = freelist_;
123      c->cache[c->pos++] = idx;
124      freelist_ = *(IndexT*)Map(idx);
125    }
126  }
127
128  void Drain(Cache *c) {
129    SpinMutexLock lock(&mtx_);
130    for (uptr i = 0; i < Cache::kSize / 2; i++) {
131      IndexT idx = c->cache[--c->pos];
132      *(IndexT*)Map(idx) = freelist_;
133      freelist_ = idx;
134    }
135  }
136};
137
138}  // namespace __tsan
139
140#endif  // TSAN_DENSE_ALLOC_H
141