1/*
2 * Copyright (C) 2014 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_COMPILER_GC_MAP_BUILDER_H_
18#define ART_COMPILER_GC_MAP_BUILDER_H_
19
20#include <vector>
21
22#include "gc_map.h"
23#include "utils.h"
24
25namespace art {
26
27class GcMapBuilder {
28 public:
29  GcMapBuilder(std::vector<uint8_t>* table, size_t entries, uint32_t max_native_offset,
30               size_t references_width)
31      : entries_(entries), references_width_(entries != 0u ? references_width : 0u),
32        native_offset_width_(entries != 0 && max_native_offset != 0
33                             ? sizeof(max_native_offset) - CLZ(max_native_offset) / 8u
34                             : 0u),
35        in_use_(entries), table_(table) {
36    // Resize table and set up header.
37    table->resize((EntryWidth() * entries) + sizeof(uint32_t));
38    CHECK_LT(native_offset_width_, 1U << 3);
39    (*table)[0] = native_offset_width_ & 7;
40    CHECK_LT(references_width_, 1U << 13);
41    (*table)[0] |= (references_width_ << 3) & 0xFF;
42    (*table)[1] = (references_width_ >> 5) & 0xFF;
43    CHECK_LT(entries, 1U << 16);
44    (*table)[2] = entries & 0xFF;
45    (*table)[3] = (entries >> 8) & 0xFF;
46  }
47
48  void AddEntry(uint32_t native_offset, const uint8_t* references) {
49    size_t table_index = TableIndex(native_offset);
50    while (in_use_[table_index]) {
51      table_index = (table_index + 1) % entries_;
52    }
53    in_use_[table_index] = true;
54    SetCodeOffset(table_index, native_offset);
55    DCHECK_EQ(native_offset, GetCodeOffset(table_index));
56    SetReferences(table_index, references);
57  }
58
59 private:
60  size_t TableIndex(uint32_t native_offset) {
61    return NativePcOffsetToReferenceMap::Hash(native_offset) % entries_;
62  }
63
64  uint32_t GetCodeOffset(size_t table_index) {
65    uint32_t native_offset = 0;
66    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
67    for (size_t i = 0; i < native_offset_width_; i++) {
68      native_offset |= (*table_)[table_offset + i] << (i * 8);
69    }
70    return native_offset;
71  }
72
73  void SetCodeOffset(size_t table_index, uint32_t native_offset) {
74    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
75    for (size_t i = 0; i < native_offset_width_; i++) {
76      (*table_)[table_offset + i] = (native_offset >> (i * 8)) & 0xFF;
77    }
78  }
79
80  void SetReferences(size_t table_index, const uint8_t* references) {
81    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
82    memcpy(&(*table_)[table_offset + native_offset_width_], references, references_width_);
83  }
84
85  size_t EntryWidth() const {
86    return native_offset_width_ + references_width_;
87  }
88
89  // Number of entries in the table.
90  const size_t entries_;
91  // Number of bytes used to encode the reference bitmap.
92  const size_t references_width_;
93  // Number of bytes used to encode a native offset.
94  const size_t native_offset_width_;
95  // Entries that are in use.
96  std::vector<bool> in_use_;
97  // The table we're building.
98  std::vector<uint8_t>* const table_;
99};
100
101}  // namespace art
102
103#endif  // ART_COMPILER_GC_MAP_BUILDER_H_
104