1 /*
2  * Copyright (C) 2012 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_RUNTIME_GC_MAP_H_
18 #define ART_RUNTIME_GC_MAP_H_
19 
20 #include <stdint.h>
21 
22 #include "base/logging.h"
23 #include "base/macros.h"
24 
25 namespace art {
26 
27 // Lightweight wrapper for native PC offset to reference bit maps.
28 class NativePcOffsetToReferenceMap {
29  public:
NativePcOffsetToReferenceMap(const uint8_t * data)30   explicit NativePcOffsetToReferenceMap(const uint8_t* data) : data_(data) {
31     CHECK(data_ != nullptr);
32   }
33 
34   // The number of entries in the table.
NumEntries()35   size_t NumEntries() const {
36     return data_[2] | (data_[3] << 8);
37   }
38 
39   // Return address of bitmap encoding what are live references.
GetBitMap(size_t index)40   const uint8_t* GetBitMap(size_t index) const {
41     size_t entry_offset = index * EntryWidth();
42     return &Table()[entry_offset + NativeOffsetWidth()];
43   }
44 
45   // Get the native PC encoded in the table at the given index.
GetNativePcOffset(size_t index)46   uintptr_t GetNativePcOffset(size_t index) const {
47     size_t entry_offset = index * EntryWidth();
48     uintptr_t result = 0;
49     for (size_t i = 0; i < NativeOffsetWidth(); ++i) {
50       result |= Table()[entry_offset + i] << (i * 8);
51     }
52     return result;
53   }
54 
55   // Does the given offset have an entry?
HasEntry(uintptr_t native_pc_offset)56   bool HasEntry(uintptr_t native_pc_offset) {
57     for (size_t i = 0; i < NumEntries(); ++i) {
58       if (GetNativePcOffset(i) == native_pc_offset) {
59         return true;
60       }
61     }
62     return false;
63   }
64 
65   // Finds the bitmap associated with the native pc offset.
FindBitMap(uintptr_t native_pc_offset)66   const uint8_t* FindBitMap(uintptr_t native_pc_offset) {
67     size_t num_entries = NumEntries();
68     size_t index = Hash(native_pc_offset) % num_entries;
69     size_t misses = 0;
70     while (GetNativePcOffset(index) != native_pc_offset) {
71       index = (index + 1) % num_entries;
72       misses++;
73       DCHECK_LT(misses, num_entries) << "Failed to find offset: " << native_pc_offset;
74     }
75     return GetBitMap(index);
76   }
77 
Hash(uint32_t native_offset)78   static uint32_t Hash(uint32_t native_offset) {
79     uint32_t hash = native_offset;
80     hash ^= (hash >> 20) ^ (hash >> 12);
81     hash ^= (hash >> 7) ^ (hash >> 4);
82     return hash;
83   }
84 
85   // The number of bytes used to encode registers.
RegWidth()86   size_t RegWidth() const {
87     return (static_cast<size_t>(data_[0]) | (static_cast<size_t>(data_[1]) << 8)) >> 3;
88   }
89 
90  private:
91   // Skip the size information at the beginning of data.
Table()92   const uint8_t* Table() const {
93     return data_ + 4;
94   }
95 
96   // Number of bytes used to encode a native offset.
NativeOffsetWidth()97   size_t NativeOffsetWidth() const {
98     return data_[0] & 7;
99   }
100 
101   // The width of an entry in the table.
EntryWidth()102   size_t EntryWidth() const {
103     return NativeOffsetWidth() + RegWidth();
104   }
105 
106   const uint8_t* const data_;  // The header and table data
107 };
108 
109 }  // namespace art
110 
111 #endif  // ART_RUNTIME_GC_MAP_H_
112