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
25namespace art {
26
27// Lightweight wrapper for native PC offset to reference bit maps.
28class NativePcOffsetToReferenceMap {
29 public:
30  explicit NativePcOffsetToReferenceMap(const uint8_t* data) : data_(data) {
31    CHECK(data_ != NULL);
32  }
33
34  // The number of entries in the table.
35  size_t NumEntries() const {
36    return data_[2] | (data_[3] << 8);
37  }
38
39  // Return address of bitmap encoding what are live references.
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.
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?
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.
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
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.
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.
92  const uint8_t* Table() const {
93    return data_ + 4;
94  }
95
96  // Number of bytes used to encode a native offset.
97  size_t NativeOffsetWidth() const {
98    return data_[0] & 7;
99  }
100
101  // The width of an entry in the table.
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