Home | History | Annotate | Download | only in tsan 
      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 
     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