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_SIMPLE_CACHE_
     31 #define TS_SIMPLE_CACHE_
     32 
     33 #include "ts_util.h"
     34 
     35 // Few simple 'cache' classes.
     36 // -------- PtrToBoolCache ------ {{{1
     37 // Maps a pointer to a boolean.
     38 template <int kSize>
     39 class PtrToBoolCache {
     40  public:
     41   PtrToBoolCache() {
     42     Flush();
     43   }
     44   void Flush() {
     45     memset(this, 0, sizeof(*this));
     46   }
     47   void Insert(uintptr_t ptr, bool val) {
     48     size_t idx  = ptr % kSize;
     49     arr_[idx] = ptr;
     50     if (val) {
     51       bits_[idx / 32] |= 1U << (idx % 32);
     52     } else {
     53       bits_[idx / 32] &= ~(1U << (idx % 32));
     54     }
     55   }
     56   bool Lookup(uintptr_t ptr, bool *val) {
     57     size_t idx  = ptr % kSize;
     58     if (arr_[idx] == ptr) {
     59       *val = (bits_[idx / 32] >> (idx % 32)) & 1;
     60       return true;
     61     }
     62     return false;
     63   }
     64  private:
     65   uintptr_t arr_[kSize];
     66   uint32_t bits_[(kSize + 31) / 32];
     67 };
     68 
     69 // -------- IntPairToBoolCache ------ {{{1
     70 // Maps two integers to a boolean.
     71 // The second integer should be less than 1^31.
     72 template <int32_t kSize>
     73 class IntPairToBoolCache {
     74  public:
     75   IntPairToBoolCache() {
     76     Flush();
     77   }
     78   void Flush() {
     79     memset(arr_, 0, sizeof(arr_));
     80   }
     81   void Insert(uint32_t a, uint32_t b, bool val) {
     82     DCHECK((int32_t)b >= 0);
     83     uint32_t i = idx(a, b);
     84     if (val) {
     85       b |= 1U << 31;
     86     }
     87     arr_[i * 2 + 0] = a;
     88     arr_[i * 2 + 1] = b;
     89   }
     90   bool Lookup(uint32_t a, uint32_t b, bool *val) {
     91     DCHECK((int32_t)b >= 0);
     92     uint32_t i = idx(a, b);
     93     if (arr_[i * 2] != a) return false;
     94     uint32_t maybe_b = arr_[i * 2 + 1];
     95     if (b == (maybe_b & (~(1U << 31)))) {
     96       *val = (maybe_b & (1U << 31)) != 0;
     97       return true;
     98     }
     99     return false;
    100   }
    101  private:
    102   uint32_t idx(uint32_t a, uint32_t b) {
    103     return (a ^ ((b >> 16) | (b << 16))) % kSize;
    104   }
    105   uint32_t arr_[kSize * 2];
    106 };
    107 
    108 // end. {{{1
    109 #endif  // TS_SIMPLE_CACHE_
    110 // vim:shiftwidth=2:softtabstop=2:expandtab:tw=80
    111