1/* Copyright (c) 2008-2010, Google Inc.
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Neither the name of Google Inc. nor the names of its
11 * contributors may be used to endorse or promote products derived from
12 * this software without specific prior written permission.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27// This file is part of ThreadSanitizer, a dynamic data race detector.
28// Author: Konstantin Serebryany.
29// Author: Timur Iskhodzhanov.
30#ifndef TS_HEAP_INFO_
31#define TS_HEAP_INFO_
32
33#include "ts_util.h"
34
35// Information about heap memory.
36// For each heap allocation we create a struct HeapInfo.
37// This struct should have fields 'uintptr_t ptr' and 'uintptr_t size',
38// a default CTOR and a copy CTOR.
39
40template<class HeapInfo>
41class HeapMap {
42 public:
43  typedef map<uintptr_t, HeapInfo> map_t;
44  typedef typename map_t::iterator iterator;
45
46  HeapMap() { Reset(); }
47
48  iterator begin() { return ++map_.begin(); }
49  iterator end() { return --map_.end(); }
50
51  size_t size() { return map_.size() - 2; }
52
53  void InsertInfo(uintptr_t a, HeapInfo info) {
54    CHECK(IsValidPtr(a));
55    CHECK(info.ptr == a);
56    map_[a] = info;
57  }
58
59  void EraseInfo(uintptr_t a) {
60    CHECK(IsValidPtr(a));
61    map_.erase(a);
62  }
63
64  void EraseRange(uintptr_t start, uintptr_t end) {
65    CHECK(IsValidPtr(start));
66    CHECK(IsValidPtr(end));
67    // TODO(glider): the [start, end) range may cover several map_ records.
68    EraseInfo(start);
69  }
70
71  HeapInfo *GetInfo(uintptr_t a) {
72    CHECK(this);
73    CHECK(IsValidPtr(a));
74    typename map_t::iterator it = map_.lower_bound(a);
75    CHECK(it != map_.end());
76    if (it->second.ptr == a) {
77      // Exact match. 'a' is the beginning of a heap-allocated address.
78      return &it->second;
79    }
80    CHECK(a < it->second.ptr);
81    CHECK(it != map_.begin());
82    // not an exact match, try the previous iterator.
83    --it;
84    HeapInfo *info = &it->second;
85    CHECK(info->ptr < a);
86    if (info->ptr + info->size > a) {
87      // within the range.
88      return info;
89    }
90    return NULL;
91  }
92
93  void Clear() {
94    map_.clear();
95    Reset();
96  }
97
98 private:
99  bool IsValidPtr(uintptr_t a) {
100    return a != 0 && a != (uintptr_t) -1;
101  }
102  void Reset() {
103    // Insert a maximal and minimal possible values to make GetInfo simpler.
104    HeapInfo max_info;
105    memset(&max_info, 0, sizeof(HeapInfo));
106    max_info.ptr = (uintptr_t)-1;
107    map_[max_info.ptr] = max_info;
108
109    HeapInfo min_info;
110    memset(&min_info, 0, sizeof(HeapInfo));
111    map_[min_info.ptr] = min_info;
112  }
113  map_t map_;
114};
115
116#endif  // TS_HEAP_INFO_
117