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 40 template<class HeapInfo> 41 class HeapMap { 42 public: 43 typedef map<uintptr_t, HeapInfo> map_t; 44 typedef typename map_t::iterator iterator; 45 HeapMap()46 HeapMap() { Reset(); } 47 begin()48 iterator begin() { return ++map_.begin(); } end()49 iterator end() { return --map_.end(); } 50 size()51 size_t size() { return map_.size() - 2; } 52 InsertInfo(uintptr_t a,HeapInfo info)53 void InsertInfo(uintptr_t a, HeapInfo info) { 54 CHECK(IsValidPtr(a)); 55 CHECK(info.ptr == a); 56 map_[a] = info; 57 } 58 EraseInfo(uintptr_t a)59 void EraseInfo(uintptr_t a) { 60 CHECK(IsValidPtr(a)); 61 map_.erase(a); 62 } 63 EraseRange(uintptr_t start,uintptr_t end)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 GetInfo(uintptr_t a)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 Clear()93 void Clear() { 94 map_.clear(); 95 Reset(); 96 } 97 98 private: IsValidPtr(uintptr_t a)99 bool IsValidPtr(uintptr_t a) { 100 return a != 0 && a != (uintptr_t) -1; 101 } Reset()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