| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 #include "vm/code_index_table.h" | |
| 6 | |
| 7 #include "vm/isolate.h" | |
| 8 #include "vm/object.h" | |
| 9 #include "vm/pages.h" | |
| 10 #include "vm/raw_object.h" | |
| 11 #include "vm/visitor.h" | |
| 12 | |
| 13 namespace dart { | |
| 14 | |
| 15 CodeIndexTable::CodeIndexTable() : code_pages_(NULL), | |
| 16 code_lists_(Array::null()), | |
| 17 largecode_pc_ranges_(NULL), | |
| 18 largecode_list_(Array::null()) { | |
| 19 code_pages_ = new IndexArray<CodePageInfo>(kInitialSize); | |
| 20 ASSERT(code_pages_ != NULL); | |
| 21 code_lists_ = Array::New(kInitialSize); | |
| 22 } | |
| 23 | |
| 24 | |
| 25 CodeIndexTable::~CodeIndexTable() { | |
| 26 for (intptr_t i = 0; i < code_pages_->length(); i++) { | |
| 27 IndexArray<PcRange>* pc_ranges = code_pages_->At(i).pc_ranges; | |
| 28 delete pc_ranges; | |
| 29 } | |
| 30 delete code_pages_; | |
| 31 code_lists_ = Array::null(); | |
| 32 delete largecode_pc_ranges_; | |
| 33 largecode_list_ = Array::null(); | |
| 34 } | |
| 35 | |
| 36 | |
| 37 void CodeIndexTable::AddCode(const Code& code) { | |
| 38 ASSERT(!code.IsNull()); | |
| 39 uword entrypoint = code.EntryPoint(); // Entry point for a function. | |
| 40 intptr_t instr_size = code.Size(); // Instructions size for the function. | |
| 41 if (PageSpace::IsPageAllocatableSize(instr_size)) { | |
| 42 uword page_start = (entrypoint & ~(PageSpace::kPageSize - 1)); | |
| 43 int page_index = FindPageIndex(page_start); | |
| 44 if (page_index == -1) { | |
| 45 // We do not have an entry for this code page, add one. | |
| 46 page_index = AddPageIndex(page_start); | |
| 47 } | |
| 48 ASSERT(page_index != -1); | |
| 49 // Add the entrypoint, size and function object at the specified index. | |
| 50 AddCodeToList(page_index, entrypoint, instr_size, code); | |
| 51 } else { | |
| 52 AddLargeCode(entrypoint, instr_size, code); | |
| 53 } | |
| 54 } | |
| 55 | |
| 56 | |
| 57 RawCode* CodeIndexTable::LookupCode(uword pc) const { | |
| 58 uword page_start = (pc & ~(PageSpace::kPageSize - 1)); | |
| 59 int page_index = FindPageIndex(page_start); | |
| 60 if (page_index == -1) { | |
| 61 // Check if the pc exists in the large pc ranges as this might be | |
| 62 // the pc of a large code object. This would return the large code | |
| 63 // or a null object if it doesn't exist in that list too. | |
| 64 return LookupLargeCode(pc); | |
| 65 } | |
| 66 IndexArray<PcRange>* pc_ranges = code_pages_->At(page_index).pc_ranges; | |
| 67 const Array& codes_list = Array::Handle(code_lists_); | |
| 68 ASSERT(!codes_list.IsNull()); | |
| 69 ASSERT(page_index < (codes_list.Length() - 1)); | |
| 70 Array& codes = Array::Handle(); | |
| 71 codes ^= codes_list.At(page_index); | |
| 72 return LookupCodeFromList(pc_ranges, codes, pc, kIsSorted); | |
| 73 } | |
| 74 | |
| 75 | |
| 76 void CodeIndexTable::VisitObjectPointers(ObjectPointerVisitor* visitor) { | |
| 77 ASSERT(visitor != NULL); | |
| 78 visitor->VisitPointer(reinterpret_cast<RawObject**>(&code_lists_)); | |
| 79 visitor->VisitPointer(reinterpret_cast<RawObject**>(&largecode_list_)); | |
| 80 } | |
| 81 | |
| 82 | |
| 83 void CodeIndexTable::Init(Isolate* isolate) { | |
| 84 ASSERT(isolate->code_index_table() == NULL); | |
| 85 CodeIndexTable* code_index_table = new CodeIndexTable(); | |
| 86 isolate->set_code_index_table(code_index_table); | |
| 87 } | |
| 88 | |
| 89 | |
| 90 int CodeIndexTable::AddPageIndex(uword page_start) { | |
| 91 ASSERT(FindPageIndex(page_start) == -1); | |
| 92 int page_index = code_pages_->length(); | |
| 93 CodePageInfo code; | |
| 94 code.page_start = page_start; | |
| 95 code.pc_ranges = new IndexArray<PcRange>(kInitialSize); | |
| 96 ASSERT(code.pc_ranges != NULL); | |
| 97 code_pages_->Add(code); // code gets added at 'index'. | |
| 98 const Array& codes_list = Array::Handle(code_lists_); | |
| 99 ASSERT(!codes_list.IsNull()); | |
| 100 const Array& codes = Array::Handle(Array::New(kInitialSize)); | |
| 101 codes_list.SetAt(page_index, codes); | |
| 102 if (code_pages_->IsFull()) { | |
| 103 // Grow the index table. | |
| 104 int new_size = code_pages_->length() + kInitialSize; | |
| 105 GrowCodeIndexTable(new_size); | |
| 106 } | |
| 107 return page_index; | |
| 108 } | |
| 109 | |
| 110 | |
| 111 int CodeIndexTable::FindPageIndex(uword page_start) const { | |
| 112 // We don't expect too many code pages (maybe max of 16) so it is | |
| 113 // ok to scan linearly in order to find the page_start in this index | |
| 114 // table. | |
| 115 for (int i = 0; i < code_pages_->length(); i++) { | |
| 116 if (code_pages_->At(i).page_start == page_start) { | |
| 117 return i; | |
| 118 } | |
| 119 } | |
| 120 return -1; | |
| 121 } | |
| 122 | |
| 123 | |
| 124 void CodeIndexTable::AddCodeToList(int page_index, | |
| 125 uword entrypoint, | |
| 126 intptr_t size, | |
| 127 const Code& code) { | |
| 128 // Get PC ranges index array at specified index. | |
| 129 IndexArray<PcRange>* pc_ranges = code_pages_->At(page_index).pc_ranges; | |
| 130 ASSERT(pc_ranges != NULL); | |
| 131 const Array& codes_list = Array::Handle(code_lists_); | |
| 132 ASSERT(!codes_list.IsNull()); | |
| 133 // Get functions array present at specified index. | |
| 134 Array& codes = Array::Handle(); | |
| 135 codes ^= codes_list.At(page_index); | |
| 136 ASSERT(!codes.IsNull()); | |
| 137 // Asserting with an unsorted search, to ensure addition of pc was done right. | |
| 138 ASSERT(FindPcIndex(*pc_ranges, entrypoint, kIsNotSorted) == -1); | |
| 139 AddCodeHelper(pc_ranges, codes, entrypoint, size, code); | |
| 140 if (pc_ranges->IsFull()) { | |
| 141 // Grow the pc ranges table and the associated functions table. | |
| 142 int new_size = pc_ranges->length() + kInitialSize; | |
| 143 pc_ranges->Resize(new_size); | |
| 144 codes = Array::Grow(codes, new_size); | |
| 145 codes_list.SetAt(page_index, codes); | |
| 146 } | |
| 147 } | |
| 148 | |
| 149 | |
| 150 void CodeIndexTable::AddLargeCode(uword entrypoint, | |
| 151 intptr_t size, | |
| 152 const Code& code) { | |
| 153 if (largecode_pc_ranges_ == NULL) { | |
| 154 // No large functions seen so far. | |
| 155 largecode_pc_ranges_ = new IndexArray<PcRange>(kInitialSize); | |
| 156 ASSERT(largecode_pc_ranges_ != NULL); | |
| 157 largecode_list_ = Array::New(kInitialSize); | |
| 158 } | |
| 159 ASSERT(FindPcIndex(*largecode_pc_ranges_, entrypoint, kIsNotSorted) == -1); | |
| 160 const Array& largecode_list = Array::Handle(largecode_list_); | |
| 161 ASSERT(!largecode_list.IsNull()); | |
| 162 AddCodeHelper(largecode_pc_ranges_, largecode_list, entrypoint, size, code); | |
| 163 if (largecode_pc_ranges_->IsFull()) { | |
| 164 // Grow largecode_pc_ranges_ and largecode_list_. | |
| 165 int new_size = largecode_pc_ranges_->length() + kInitialSize; | |
| 166 largecode_pc_ranges_->Resize(new_size); | |
| 167 largecode_list_ = Array::Grow(largecode_list, new_size); | |
| 168 } | |
| 169 } | |
| 170 | |
| 171 | |
| 172 void CodeIndexTable::AddCodeHelper(IndexArray<PcRange>* pc_ranges, | |
| 173 const Array& codes, | |
| 174 uword entrypoint, | |
| 175 intptr_t size, | |
| 176 const Code& code) { | |
| 177 PcRange pc_range; | |
| 178 pc_range.entrypoint = entrypoint; | |
| 179 pc_range.size = size; | |
| 180 intptr_t next_slot = pc_ranges->length(); | |
| 181 pc_ranges->Add(pc_range); // pc_range gets added at 'next_slot'. | |
| 182 codes.SetAt(next_slot, code); | |
| 183 } | |
| 184 | |
| 185 | |
| 186 RawCode* CodeIndexTable::LookupLargeCode(uword pc) const { | |
| 187 const Array& large_codes = Array::Handle(largecode_list_); | |
| 188 return LookupCodeFromList(largecode_pc_ranges_, | |
| 189 large_codes, | |
| 190 pc, | |
| 191 kIsNotSorted); | |
| 192 } | |
| 193 | |
| 194 | |
| 195 RawCode* CodeIndexTable::LookupCodeFromList( | |
| 196 IndexArray<PcRange>* pc_ranges, | |
| 197 const Array& codes, | |
| 198 uword pc, | |
| 199 bool sorted) { | |
| 200 if (pc_ranges == NULL) { | |
| 201 return Code::null(); // no entries in array so return null object. | |
| 202 } | |
| 203 intptr_t i = FindPcIndex(*pc_ranges, pc, sorted); | |
| 204 if (i == -1) { | |
| 205 return Code::null(); // no entry for pc, return null object. | |
| 206 } | |
| 207 // 'i' is in the index which holds the entry for the function, | |
| 208 // access the functions array at 'i' and return the function object. | |
| 209 ASSERT(!codes.IsNull()); | |
| 210 ASSERT(i < (codes.Length() - 1)); | |
| 211 Code& code = Code::Handle(); | |
| 212 code ^= codes.At(i); | |
| 213 return code.raw(); | |
| 214 } | |
| 215 | |
| 216 | |
| 217 intptr_t CodeIndexTable::FindPcIndex(const IndexArray<PcRange>& pc_ranges, | |
| 218 uword pc, | |
| 219 bool sorted) { | |
| 220 if (sorted) { | |
| 221 // The pc range entries are sorted, do a binary search to see if pc exists. | |
| 222 intptr_t low = 0; | |
| 223 intptr_t high = pc_ranges.length(); | |
| 224 while (low < high) { | |
| 225 intptr_t mid = low + (high - low) / 2; | |
| 226 uword entrypoint = pc_ranges.At(mid).entrypoint; | |
| 227 intptr_t size = pc_ranges.At(mid).size; | |
| 228 if (entrypoint <= pc) { | |
| 229 if (pc < (entrypoint + size)) { | |
| 230 return mid; // Found entry, return index. | |
| 231 } else { | |
| 232 low = mid + 1; | |
| 233 } | |
| 234 } else { | |
| 235 high = mid; | |
| 236 } | |
| 237 } | |
| 238 } else { | |
| 239 // The pc range entries are not sorted, do a linear search. | |
| 240 for (intptr_t i = (pc_ranges.length() - 1); i >= 0; i--) { | |
| 241 uword entrypoint = pc_ranges.At(i).entrypoint; | |
| 242 intptr_t size = pc_ranges.At(i).size; | |
| 243 if (entrypoint <= pc && pc < (entrypoint + size)) { | |
| 244 return i; // Found entry, return index. | |
| 245 } | |
| 246 } | |
| 247 } | |
| 248 return -1; // Entry not found. | |
| 249 } | |
| 250 | |
| 251 | |
| 252 void CodeIndexTable::GrowCodeIndexTable(int new_size) { | |
| 253 code_pages_->Resize(new_size); | |
| 254 code_lists_ = Array::Grow(Array::Handle(code_lists_), new_size); | |
| 255 } | |
| 256 | |
| 257 } // namespace dart | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 10082017:
Remove code index table. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/runtime/