1 : // Copyright 2012 Google Inc.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : #include "syzygy/block_graph/block_graph.h"
16 :
17 : #include <limits>
18 :
19 : #include "base/logging.h"
20 : #include "base/stringprintf.h"
21 :
22 : namespace block_graph {
23 :
24 : namespace {
25 :
26 : // A list of printable names corresponding to block types. This needs to
27 : // be kept in sync with the BlockGraph::BlockType enum!
28 : const char* kBlockType[] = {
29 : "CODE_BLOCK", "DATA_BLOCK",
30 : };
31 : COMPILE_ASSERT(arraysize(kBlockType) == BlockGraph::BLOCK_TYPE_MAX,
32 : kBlockType_not_in_sync);
33 :
34 : // Shift all items in an offset -> item map by 'distance', provided the initial
35 : // item offset was >= @p offset.
36 : template<typename ItemType>
37 : void ShiftOffsetItemMap(BlockGraph::Offset offset,
38 : BlockGraph::Offset distance,
39 E : std::map<BlockGraph::Offset, ItemType>* items) {
40 E : DCHECK_GE(offset, 0);
41 E : DCHECK_NE(distance, 0);
42 E : DCHECK(items != NULL);
43 :
44 : typedef std::map<BlockGraph::Offset, ItemType> ItemMap;
45 :
46 : // Get iterators to all of the items that need changing.
47 E : std::vector<ItemMap::iterator> item_its;
48 E : ItemMap::iterator item_it = items->lower_bound(offset);
49 E : while (item_it != items->end()) {
50 E : item_its.push_back(item_it);
51 E : ++item_it;
52 E : }
53 :
54 : // Get the direction and bounds of the iteration. We need to walk through
55 : // the iterators in a different order depending on if we're shifting left
56 : // or right. This is to ensure that earlier shifts don't land on the values
57 : // of later unshifted offsets.
58 E : int start = 0;
59 E : int stop = item_its.size();
60 E : int step = 1;
61 E : if (distance > 0) {
62 E : start = stop - 1;
63 E : stop = -1;
64 E : step = -1;
65 : }
66 :
67 E : for (int i = start; i != stop; i += step) {
68 E : item_it = item_its[i];
69 : items->insert(std::make_pair(item_it->first + distance,
70 E : item_it->second));
71 E : items->erase(item_it);
72 E : }
73 E : }
74 :
75 : void ShiftReferences(BlockGraph::Block* block,
76 : BlockGraph::Offset offset,
77 E : BlockGraph::Offset distance) {
78 : // Make a copy of the reference map for simplicity.
79 E : BlockGraph::Block::ReferenceMap references = block->references();
80 :
81 : // Start by removing all references that have moved.
82 : BlockGraph::Block::ReferenceMap::const_iterator it =
83 E : references.lower_bound(offset);
84 E : for (; it != references.end(); ++it) {
85 E : if (it->first >= offset)
86 E : block->RemoveReference(it->first);
87 E : }
88 :
89 : // Then patch up all existing references.
90 E : it = references.begin();
91 E : for (; it != references.end(); ++it) {
92 E : BlockGraph::Reference ref(it->second);
93 E : BlockGraph::Offset new_offset(it->first);
94 :
95 : // If this is self-referential, fix the destination offset.
96 E : if (ref.referenced() == block && ref.offset() >= offset) {
97 : ref = BlockGraph::Reference(ref.type(),
98 : ref.size(),
99 : ref.referenced(),
100 : ref.offset() + distance,
101 i : ref.base() + distance);
102 : }
103 :
104 : // If its offset is past the change point, fix that.
105 E : if (it->first >= offset)
106 E : new_offset += distance;
107 :
108 : // In many cases this'll be a noop.
109 : // TODO(siggi): Optimize this.
110 E : block->SetReference(new_offset, ref);
111 E : }
112 E : }
113 :
114 : // Shift all referrers beyond @p offset by @p distance.
115 : void ShiftReferrers(BlockGraph::Block* self,
116 : BlockGraph::Offset offset,
117 : BlockGraph::Offset distance,
118 E : BlockGraph::Block::ReferrerSet* referrers) {
119 E : DCHECK_GE(offset, 0);
120 E : DCHECK_NE(distance, 0);
121 E : DCHECK(referrers != NULL);
122 :
123 : typedef BlockGraph::Block::ReferrerSet ReferrerSet;
124 : typedef BlockGraph::Reference Reference;
125 :
126 E : ReferrerSet::iterator ref_it = referrers->begin();
127 E : while (ref_it != referrers->end()) {
128 : // We need to keep around the next iterator as 'ref_it' will be invalidated
129 : // if we need to update the reference. (It will be deleted and then
130 : // recreated.)
131 E : ReferrerSet::iterator next_ref_it = ref_it;
132 E : ++next_ref_it;
133 :
134 E : BlockGraph::Block* ref_block = ref_it->first;
135 : // Our own references will have been moved already.
136 E : if (ref_block != self) {
137 E : BlockGraph::Offset ref_offset = ref_it->second;
138 :
139 E : Reference ref;
140 E : bool ref_found = ref_block->GetReference(ref_offset, &ref);
141 E : DCHECK(ref_found);
142 :
143 : // Shift the reference if need be.
144 E : if (ref.offset() >= offset) {
145 : Reference new_ref(ref.type(),
146 : ref.size(),
147 : ref.referenced(),
148 : ref.offset() + distance,
149 E : ref.base() + distance);
150 E : bool inserted = ref_block->SetReference(ref_offset, new_ref);
151 E : DCHECK(!inserted);
152 : }
153 : }
154 :
155 E : ref_it = next_ref_it;
156 E : }
157 E : }
158 :
159 i : const char* BlockAttributeToString(BlockGraph::BlockAttributeEnum attr) {
160 i : switch (attr) {
161 : #define DEFINE_CASE(name, unused) case BlockGraph::name: return #name;
162 i : BLOCK_ATTRIBUTE_ENUM(DEFINE_CASE)
163 : #undef DEFINE_CASE
164 : default:
165 i : NOTREACHED();
166 i : return NULL;
167 : }
168 i : }
169 :
170 : } // namespace
171 :
172 i : std::string BlockGraph::BlockAttributesToString(BlockAttributes attrs) {
173 i : BlockAttributes attr = 1;
174 i : std::string s;
175 i : for (; attr < BLOCK_ATTRIBUTES_MAX; attr <<= 1) {
176 i : if (attr & attrs) {
177 i : if (!s.empty())
178 i : s.append("|");
179 i : s.append(BlockAttributeToString(static_cast<BlockAttributeEnum>(attr)));
180 : }
181 i : }
182 i : return s;
183 i : }
184 :
185 E : const char* BlockGraph::BlockTypeToString(BlockGraph::BlockType type) {
186 E : DCHECK_LE(BlockGraph::CODE_BLOCK, type);
187 E : DCHECK_GT(BlockGraph::BLOCK_TYPE_MAX, type);
188 E : return kBlockType[type];
189 E : }
190 :
191 : std::string BlockGraph::LabelAttributesToString(
192 E : BlockGraph::LabelAttributes label_attributes) {
193 : static const char* kLabelAttributes[] = {
194 : "Code", "DebugStart", "DebugEnd", "ScopeStart", "ScopeEnd",
195 : "CallSite", "JumpTable", "CaseTable", "Data" };
196 : COMPILE_ASSERT((1 << arraysize(kLabelAttributes)) == LABEL_ATTRIBUTES_MAX,
197 : label_attribute_names_not_in_sync_with_enum);
198 :
199 E : size_t i = 0;
200 E : std::string s;
201 E : for (size_t i = 0; i < arraysize(kLabelAttributes); ++i) {
202 E : if (label_attributes & (1 << i)) {
203 E : if (!s.empty())
204 E : s.append("|");
205 E : s.append(kLabelAttributes[i]);
206 : }
207 E : }
208 E : return s;
209 E : }
210 :
211 E : const core::RelativeAddress kInvalidAddress(0xFFFFFFFF);
212 :
213 : const BlockGraph::SectionId BlockGraph::kInvalidSectionId = -1;
214 :
215 : BlockGraph::BlockGraph()
216 : : next_section_id_(0),
217 E : next_block_id_(0) {
218 E : }
219 :
220 E : BlockGraph::~BlockGraph() {
221 E : }
222 :
223 : BlockGraph::Section* BlockGraph::AddSection(const base::StringPiece& name,
224 E : uint32 characteristics) {
225 E : Section new_section(next_section_id_++, name, characteristics);
226 : std::pair<SectionMap::iterator, bool> result = sections_.insert(
227 E : std::make_pair(new_section.id(), new_section));
228 E : DCHECK(result.second);
229 :
230 E : return &result.first->second;
231 E : }
232 :
233 E : BlockGraph::Section* BlockGraph::FindSection(const base::StringPiece& name) {
234 : // This is a linear scan, but thankfully images generally do not have many
235 : // sections and we do not create them very often. Fast lookup by index is
236 : // more important. If this ever becomes an issue, we could keep around a
237 : // second index by name.
238 E : SectionMap::iterator it = sections_.begin();
239 E : for (; it != sections_.end(); ++it) {
240 E : if (it->second.name() == name)
241 E : return &it->second;
242 E : }
243 :
244 E : return NULL;
245 E : }
246 :
247 : BlockGraph::Section* BlockGraph::FindOrAddSection(const base::StringPiece& name,
248 E : uint32 characteristics) {
249 E : Section* section = FindSection(name);
250 E : if (section) {
251 E : section->set_characteristic(characteristics);
252 E : return section;
253 : }
254 E : return AddSection(name, characteristics);
255 E : }
256 :
257 E : bool BlockGraph::RemoveSection(Section* section) {
258 E : DCHECK(section != NULL);
259 :
260 E : SectionMap::iterator it(sections_.find(section->id()));
261 E : if (it == sections_.end() || &it->second != section)
262 i : return false;
263 :
264 E : sections_.erase(it);
265 E : return true;
266 E : }
267 :
268 E : bool BlockGraph::RemoveSectionById(SectionId id) {
269 E : SectionMap::iterator it(sections_.find(id));
270 E : if (it == sections_.end())
271 E : return false;
272 :
273 E : sections_.erase(it);
274 E : return true;
275 E : }
276 :
277 : BlockGraph::Block* BlockGraph::AddBlock(BlockType type,
278 : Size size,
279 E : const base::StringPiece& name) {
280 E : BlockId id = ++next_block_id_;
281 : BlockMap::iterator it = blocks_.insert(
282 E : std::make_pair(id, Block(id, type, size, name))).first;
283 :
284 E : return &it->second;
285 E : }
286 :
287 E : bool BlockGraph::RemoveBlock(Block* block) {
288 E : DCHECK(block != NULL);
289 :
290 E : BlockMap::iterator it(blocks_.find(block->id()));
291 E : if (it == blocks_.end() || &it->second != block)
292 E : return false;
293 :
294 E : return RemoveBlockByIterator(it);
295 E : }
296 :
297 E : bool BlockGraph::RemoveBlockById(BlockId id) {
298 E : BlockMap::iterator it(blocks_.find(id));
299 E : if (it == blocks_.end())
300 E : return false;
301 :
302 E : return RemoveBlockByIterator(it);
303 E : }
304 :
305 E : BlockGraph::Section* BlockGraph::GetSectionById(SectionId id) {
306 E : SectionMap::iterator it(sections_.find(id));
307 :
308 E : if (it == sections_.end())
309 E : return NULL;
310 :
311 E : return &it->second;
312 E : }
313 :
314 E : const BlockGraph::Section* BlockGraph::GetSectionById(SectionId id) const {
315 E : SectionMap::const_iterator it(sections_.find(id));
316 :
317 E : if (it == sections_.end())
318 E : return NULL;
319 :
320 E : return &it->second;
321 E : }
322 :
323 E : BlockGraph::Block* BlockGraph::GetBlockById(BlockId id) {
324 E : BlockMap::iterator it(blocks_.find(id));
325 :
326 E : if (it == blocks_.end())
327 E : return NULL;
328 :
329 E : return &it->second;
330 E : }
331 :
332 : const BlockGraph::Block* BlockGraph::GetBlockById(BlockId id) const {
333 : BlockMap::const_iterator it(blocks_.find(id));
334 :
335 : if (it == blocks_.end())
336 : return NULL;
337 :
338 : return &it->second;
339 : }
340 :
341 E : bool BlockGraph::RemoveBlockByIterator(BlockMap::iterator it) {
342 E : DCHECK(it != blocks_.end());
343 :
344 : // Verify this block is fully disconnected.
345 E : if (it->second.referrers().size() > 0 || it->second.references().size() > 0)
346 E : return false;
347 :
348 E : blocks_.erase(it);
349 :
350 E : return true;
351 E : }
352 :
353 : BlockGraph::AddressSpace::AddressSpace(BlockGraph* graph)
354 E : : graph_(graph) {
355 E : DCHECK(graph != NULL);
356 E : }
357 :
358 : BlockGraph::Block* BlockGraph::AddressSpace::AddBlock(
359 : BlockType type, RelativeAddress addr, Size size,
360 E : const base::StringPiece& name) {
361 : // First check to see that the range is clear.
362 E : AddressSpaceImpl::Range range(addr, size);
363 : AddressSpaceImpl::RangeMap::iterator it =
364 E : address_space_.FindFirstIntersection(range);
365 E : if (it != address_space_.ranges().end())
366 E : return NULL;
367 :
368 E : BlockGraph::Block* block = graph_->AddBlock(type, size, name);
369 E : DCHECK(block != NULL);
370 E : bool inserted = InsertImpl(addr, block);
371 E : DCHECK(inserted);
372 :
373 E : return block;
374 E : }
375 :
376 E : bool BlockGraph::AddressSpace::InsertBlock(RelativeAddress addr, Block* block) {
377 E : return InsertImpl(addr, block);
378 E : }
379 :
380 : BlockGraph::Block* BlockGraph::AddressSpace::GetBlockByAddress(
381 E : RelativeAddress addr) const {
382 E : return GetContainingBlock(addr, 1);
383 E : }
384 :
385 : BlockGraph::Block* BlockGraph::AddressSpace::GetContainingBlock(
386 E : RelativeAddress addr, Size size) const {
387 E : AddressSpaceImpl::Range range(addr, size);
388 : AddressSpaceImpl::RangeMap::const_iterator it =
389 E : address_space_.FindContaining(range);
390 E : if (it == address_space_.ranges().end())
391 E : return NULL;
392 :
393 E : return it->second;
394 E : }
395 :
396 : BlockGraph::Block* BlockGraph::AddressSpace::GetFirstIntersectingBlock(
397 E : RelativeAddress addr, Size size) {
398 E : AddressSpaceImpl::Range range(addr, size);
399 : AddressSpaceImpl::RangeMap::iterator it =
400 E : address_space_.FindFirstIntersection(range);
401 E : if (it == address_space_.ranges().end())
402 E : return NULL;
403 :
404 E : return it->second;
405 E : }
406 :
407 : BlockGraph::AddressSpace::RangeMapConstIterPair
408 : BlockGraph::AddressSpace::GetIntersectingBlocks(RelativeAddress address,
409 E : Size size) const {
410 E : return address_space_.FindIntersecting(Range(address, size));
411 E : }
412 :
413 : BlockGraph::AddressSpace::RangeMapIterPair
414 : BlockGraph::AddressSpace::GetIntersectingBlocks(RelativeAddress address,
415 E : Size size) {
416 E : return address_space_.FindIntersecting(Range(address, size));
417 E : }
418 :
419 : bool BlockGraph::AddressSpace::GetAddressOf(const Block* block,
420 E : RelativeAddress* addr) const {
421 E : DCHECK(block != NULL);
422 E : DCHECK(addr != NULL);
423 :
424 E : BlockAddressMap::const_iterator it(block_addresses_.find(block));
425 E : if (it == block_addresses_.end())
426 E : return false;
427 :
428 E : *addr = it->second;
429 E : return true;
430 E : }
431 :
432 E : bool BlockGraph::AddressSpace::InsertImpl(RelativeAddress addr, Block* block) {
433 E : Range range(addr, block->size());
434 E : bool inserted = address_space_.Insert(range, block);
435 E : if (!inserted)
436 E : return false;
437 :
438 E : inserted = block_addresses_.insert(std::make_pair(block, addr)).second;
439 E : DCHECK(inserted);
440 : // Update the address stored in the block.
441 E : block->set_addr(addr);
442 :
443 E : return true;
444 E : }
445 :
446 E : bool BlockGraph::AddressSpace::ContainsBlock(const Block* block) {
447 E : DCHECK(block != NULL);
448 E : return block_addresses_.count(block) != 0;
449 E : }
450 :
451 : BlockGraph::Block* BlockGraph::AddressSpace::MergeIntersectingBlocks(
452 E : const Range& range) {
453 : typedef std::vector<std::pair<RelativeAddress, BlockGraph::Block*>>
454 : BlockAddressVector;
455 :
456 : // Find all the blocks that intersect the range, keep them and their
457 : // addresses. Start by finding the first intersection, then iterate
458 : // from there until we find a block that doesn't intersect with range.
459 : AddressSpaceImpl::RangeMap::iterator address_start =
460 E : address_space_.FindFirstIntersection(range);
461 E : AddressSpaceImpl::RangeMap::iterator address_it(address_start);
462 :
463 E : BlockAddressVector intersecting;
464 : for (; address_it != address_space_.ranges().end() &&
465 E : address_it->first.Intersects(range); ++address_it) {
466 : intersecting.push_back(std::make_pair(address_it->first.start(),
467 E : address_it->second));
468 E : }
469 :
470 : // Bail if the intersection doesn't cover at least two blocks.
471 E : if (intersecting.empty())
472 i : return NULL;
473 :
474 : // In case of single-block intersection, we're done.
475 E : if (intersecting.size() == 1)
476 i : return intersecting[0].second;
477 :
478 E : DCHECK(!intersecting.empty());
479 :
480 : // Calculate the start and end addresses of the new block.
481 E : BlockGraph::Block* first_block = intersecting[0].second;
482 E : BlockGraph::Block* last_block = intersecting[intersecting.size() - 1].second;
483 E : DCHECK(first_block != NULL && last_block != NULL);
484 :
485 E : RelativeAddress begin = std::min(range.start(), intersecting[0].first);
486 : RelativeAddress end = std::max(range.start() + range.size(),
487 E : intersecting[intersecting.size() - 1].first + last_block->size());
488 :
489 E : DCHECK(begin <= range.start());
490 E : DCHECK(end >= range.start() + range.size());
491 :
492 E : base::StringPiece block_name = first_block->name();
493 E : BlockType block_type = first_block->type();
494 E : size_t section_id = first_block->section();
495 E : size_t alignment = first_block->alignment();
496 E : BlockAttributes attributes = 0;
497 :
498 E : BlockGraph::Block::SourceRanges source_ranges;
499 :
500 : // Remove the found blocks from the address space, and make sure they're all
501 : // of the same type and from the same section as the first block. Merge the
502 : // data from all the blocks as we go along, as well as the attributes and
503 : // source ranges.
504 E : std::vector<uint8> merged_data(end - begin);
505 E : bool have_data = false;
506 E : for (size_t i = 0; i < intersecting.size(); ++i) {
507 E : RelativeAddress addr = intersecting[i].first;
508 E : BlockGraph::Block* block = intersecting[i].second;
509 E : DCHECK_EQ(block_type, block->type());
510 E : DCHECK_EQ(section_id, block->section());
511 :
512 E : if (block->data() != NULL) {
513 E : have_data = true;
514 E : memcpy(&merged_data.at(addr - begin), block->data(), block->data_size());
515 : }
516 E : attributes |= block->attributes();
517 :
518 : // Merge in the source ranges from each block.
519 E : BlockGraph::Offset block_offset = addr - begin;
520 : BlockGraph::Block::SourceRanges::RangePairs::const_iterator src_it =
521 E : block->source_ranges().range_pairs().begin();
522 E : for (; src_it != block->source_ranges().range_pairs().end(); ++src_it) {
523 : // The data range is wrt to the containing block, wo we have to translate
524 : // each individual block's offset to an offset in the merged block.
525 E : BlockGraph::Offset merged_offset = block_offset + src_it->first.start();
526 : bool pushed = source_ranges.Push(
527 : BlockGraph::Block::DataRange(merged_offset, src_it->first.size()),
528 E : src_it->second);
529 E : DCHECK(pushed);
530 E : }
531 :
532 E : bool removed = address_space_.Remove(Range(addr, block->size()));
533 E : DCHECK(removed);
534 E : size_t num_removed = block_addresses_.erase(intersecting[i].second);
535 E : DCHECK_EQ(1U, num_removed);
536 E : }
537 :
538 : // Create the new block.
539 : BlockGraph::Block* new_block = AddBlock(block_type,
540 : begin, end - begin,
541 E : block_name);
542 E : DCHECK(new_block != NULL);
543 :
544 : // Set the rest of the properties for the new block.
545 E : new_block->source_ranges() = source_ranges;
546 E : new_block->set_section(section_id);
547 E : new_block->set_alignment(alignment);
548 E : new_block->set_attributes(attributes);
549 E : if (have_data) {
550 E : uint8* data = new_block->CopyData(merged_data.size(), &merged_data.at(0));
551 E : if (data == NULL) {
552 i : LOG(ERROR) << "Unable to copy merged data";
553 i : return false;
554 : }
555 : }
556 :
557 : // Now move all labels and references to the new block.
558 E : for (size_t i = 0; i < intersecting.size(); ++i) {
559 E : RelativeAddress addr = intersecting[i].first;
560 E : BlockGraph::Block* block = intersecting[i].second;
561 E : BlockGraph::Offset start_offset = addr - begin;
562 :
563 : // If the destination block is not a code block, preserve the old block
564 : // names as labels for debugging. We also need to make sure the label is
565 : // not empty, as that is verboten.
566 E : if (block_type != BlockGraph::CODE_BLOCK && !block->name().empty()) {
567 : new_block->SetLabel(start_offset,
568 : block->name(),
569 E : BlockGraph::DATA_LABEL);
570 : }
571 :
572 : // Move labels.
573 : BlockGraph::Block::LabelMap::const_iterator
574 E : label_it(block->labels().begin());
575 E : for (; label_it != block->labels().end(); ++label_it) {
576 : new_block->SetLabel(start_offset + label_it->first,
577 E : label_it->second);
578 E : }
579 :
580 : // Copy the reference map since we mutate the original.
581 E : BlockGraph::Block::ReferenceMap refs(block->references());
582 E : BlockGraph::Block::ReferenceMap::const_iterator ref_it(refs.begin());
583 E : for (; ref_it != refs.end(); ++ref_it) {
584 E : block->RemoveReference(ref_it->first);
585 E : new_block->SetReference(start_offset + ref_it->first, ref_it->second);
586 E : }
587 :
588 : // Redirect all referrers to the new block.
589 E : block->TransferReferrers(start_offset, new_block);
590 :
591 : // Check that we've removed all references and
592 : // referrers from the original block.
593 E : DCHECK(block->references().empty());
594 E : DCHECK(block->referrers().empty());
595 :
596 : // Remove the original block.
597 E : bool removed = graph_->RemoveBlock(block);
598 E : DCHECK(removed);
599 E : }
600 :
601 E : return new_block;
602 E : }
603 :
604 E : bool BlockGraph::Section::set_name(const base::StringPiece& name) {
605 E : if (name == NULL)
606 i : return false;
607 :
608 E : if (name.empty())
609 i : return false;
610 :
611 E : name.CopyToString(&name_);
612 E : return true;
613 E : }
614 :
615 E : bool BlockGraph::Section::Save(core::OutArchive* out_archive) const {
616 E : DCHECK(out_archive != NULL);
617 : return out_archive->Save(id_) && out_archive->Save(name_) &&
618 E : out_archive->Save(characteristics_);
619 E : }
620 :
621 E : bool BlockGraph::Section::Load(core::InArchive* in_archive) {
622 E : DCHECK(in_archive != NULL);
623 : return in_archive->Load(&id_) && in_archive->Load(&name_) &&
624 E : in_archive->Load(&characteristics_);
625 E : }
626 :
627 E : std::string BlockGraph::Label::ToString() const {
628 : return base::StringPrintf("%s (%s)",
629 : name_.c_str(),
630 E : LabelAttributesToString(attributes_).c_str());
631 E : }
632 :
633 E : bool BlockGraph::Label::IsValid() const {
634 E : return AreValidAttributes(attributes_);
635 E : }
636 :
637 E : bool BlockGraph::Label::AreValidAttributes(LabelAttributes attributes) {
638 : // A label needs to have at least one attribute.
639 E : if (attributes == 0)
640 E : return false;
641 :
642 : // TODO(chrisha): Once we make the switch to VS2010 determine where call
643 : // site labels may land. Are they at the beginning of the call
644 : // instruction (in which case they may coincide with *_START_LABEL,
645 : // *_END_LABEL and CODE_LABEL), or do they point at the address of the
646 : // call (in which case they must be completely on their own)? For now, we
647 : // simply ignore them entirely from consideration.
648 E : attributes &= ~CALL_SITE_LABEL;
649 :
650 : // A code label can coincide with a debug and scope labels. (It can coincide
651 : // with *_END_LABEL labels because of 1-byte instructions, like RET or INT.)
652 : const LabelAttributes kCodeDebugScopeLabels =
653 : CODE_LABEL | DEBUG_START_LABEL | DEBUG_END_LABEL | SCOPE_START_LABEL |
654 E : SCOPE_END_LABEL;
655 : if ((attributes & CODE_LABEL) != 0 &&
656 E : (attributes & ~kCodeDebugScopeLabels) != 0) {
657 E : return false;
658 : }
659 :
660 : // A jump table must be paired with a data label and nothing else.
661 : const LabelAttributes kJumpDataLabelAttributes =
662 E : JUMP_TABLE_LABEL | DATA_LABEL;
663 E : if (attributes & JUMP_TABLE_LABEL) {
664 E : if ((attributes & kJumpDataLabelAttributes) != kJumpDataLabelAttributes)
665 E : return false;
666 E : if ((attributes & ~kJumpDataLabelAttributes) != 0)
667 i : return false;
668 E : return true;
669 : }
670 :
671 : // A case table must be paired with a data label and nothing else.
672 : const LabelAttributes kCaseDataLabelAttributes =
673 E : CASE_TABLE_LABEL | DATA_LABEL;
674 E : if (attributes & CASE_TABLE_LABEL) {
675 E : if ((attributes & kCaseDataLabelAttributes) != kCaseDataLabelAttributes)
676 E : return false;
677 E : if ((attributes & ~kCaseDataLabelAttributes) != 0)
678 i : return false;
679 E : return true;
680 : }
681 :
682 : // If there is no case or jump label, then a data label must be on its own.
683 E : if ((attributes & DATA_LABEL) != 0 && (attributes & ~DATA_LABEL) != 0)
684 i : return false;
685 :
686 E : return true;
687 E : }
688 :
689 : BlockGraph::Block::Block()
690 : : id_(0),
691 : type_(BlockGraph::CODE_BLOCK),
692 : size_(0),
693 : alignment_(1),
694 : addr_(kInvalidAddress),
695 : section_(kInvalidSectionId),
696 : attributes_(0),
697 : owns_data_(false),
698 : data_(NULL),
699 E : data_size_(0) {
700 E : }
701 :
702 : BlockGraph::Block::Block(BlockId id,
703 : BlockType type,
704 : Size size,
705 : const base::StringPiece& name)
706 : : id_(id),
707 : type_(type),
708 : size_(size),
709 : alignment_(1),
710 : name_(name.begin(), name.end()),
711 : addr_(kInvalidAddress),
712 : section_(kInvalidSectionId),
713 : attributes_(0),
714 : owns_data_(false),
715 : data_(NULL),
716 E : data_size_(0) {
717 E : }
718 :
719 E : BlockGraph::Block::~Block() {
720 E : if (owns_data_)
721 E : delete [] data_;
722 E : }
723 :
724 E : uint8* BlockGraph::Block::AllocateRawData(size_t data_size) {
725 E : DCHECK_GT(data_size, 0u);
726 E : DCHECK_LE(data_size, size_);
727 :
728 E : uint8* new_data = new uint8[data_size];
729 E : if (!new_data)
730 i : return NULL;
731 :
732 E : if (owns_data()) {
733 i : DCHECK(data_ != NULL);
734 i : delete [] data_;
735 : }
736 :
737 E : data_ = new_data;
738 E : data_size_ = data_size;
739 E : owns_data_ = true;
740 :
741 E : return new_data;
742 E : }
743 :
744 : void BlockGraph::Block::InsertData(Offset offset,
745 : Size size,
746 E : bool always_allocate_data) {
747 E : DCHECK_GE(offset, 0);
748 E : DCHECK_LE(offset, static_cast<Offset>(size_));
749 :
750 E : if (size > 0) {
751 : // Patch up the block.
752 E : size_ += size;
753 E : ShiftOffsetItemMap(offset, size, &labels_);
754 E : ShiftReferences(this, offset, size);
755 E : ShiftReferrers(this, offset, size, &referrers_);
756 E : source_ranges_.InsertUnmappedRange(DataRange(offset, size));
757 :
758 : // Does this affect already allocated data?
759 E : if (static_cast<Size>(offset) < data_size_) {
760 : // Reallocate, shift the old data to the end, and zero out the new data.
761 E : size_t old_data_size = data_size_;
762 E : size_t bytes_to_shift = data_size_ - offset;
763 E : ResizeData(data_size_ + size);
764 E : uint8* new_data = GetMutableData();
765 E : memmove(new_data + offset + size, new_data + offset, bytes_to_shift);
766 E : memset(new_data + offset, 0, size);
767 : }
768 : }
769 :
770 : // If we've been asked to, at least make sure that the data is allocated.
771 E : if (always_allocate_data && data_size_ < offset + size)
772 E : ResizeData(offset + size);
773 :
774 : return;
775 E : }
776 :
777 E : bool BlockGraph::Block::RemoveData(Offset offset, Size size) {
778 E : DCHECK_GE(offset, 0);
779 E : DCHECK_LE(offset, static_cast<Offset>(size_));
780 :
781 E : if (size == 0)
782 i : return true;
783 :
784 : // Ensure there are no labels in this range.
785 E : if (labels_.lower_bound(offset) != labels_.lower_bound(offset + size))
786 E : return false;
787 :
788 : // Ensure that there are no references intersecting this range.
789 E : ReferenceMap::const_iterator refc_it = references_.begin();
790 E : for (; refc_it != references_.end(); ++refc_it) {
791 E : if (refc_it->first >= static_cast<Offset>(offset + size))
792 E : break;
793 E : if (static_cast<Offset>(refc_it->first + refc_it->second.size()) > offset)
794 E : return false;
795 E : }
796 :
797 : // Ensure there are no referrers pointing to the data we want to remove.
798 E : ReferrerSet::const_iterator refr_it = referrers_.begin();
799 E : for (; refr_it != referrers_.end(); ++refr_it) {
800 E : Reference ref;
801 E : if (!refr_it->first->GetReference(refr_it->second, &ref)) {
802 i : LOG(ERROR) << "Unable to get reference from referrer.";
803 i : return false;
804 : }
805 : if (ref.offset() < static_cast<Offset>(offset + size) &&
806 E : static_cast<Offset>(ref.offset() + ref.size()) > offset) {
807 E : return false;
808 : }
809 E : }
810 :
811 : // Patch up the block.
812 E : size_ -= size;
813 E : ShiftOffsetItemMap(offset + size, -static_cast<int>(size), &labels_);
814 E : ShiftReferences(this, offset + size, -static_cast<int>(size));
815 E : ShiftReferrers(this, offset + size, -static_cast<int>(size), &referrers_);
816 E : source_ranges_.RemoveMappedRange(DataRange(offset, size));
817 :
818 : // Does this affect already allocated data?
819 E : if (static_cast<Size>(offset) < data_size_) {
820 E : size_t new_data_size = data_size_ - size;
821 : // Is there data beyond the section to delete?
822 E : if (static_cast<Size>(offset + size) < data_size_) {
823 : // Shift tail data to left.
824 E : uint8* data = GetMutableData();
825 E : size_t bytes_to_shift = data_size_ - offset - size;
826 E : size_t old_data_size = data_size_;
827 : memmove(data + new_data_size - bytes_to_shift,
828 : data + old_data_size - bytes_to_shift,
829 E : bytes_to_shift);
830 E : } else {
831 E : new_data_size = offset;
832 : }
833 E : ResizeData(new_data_size);
834 : }
835 :
836 E : return true;
837 E : }
838 :
839 : bool BlockGraph::Block::InsertOrRemoveData(Offset offset,
840 : Size current_size,
841 : Size new_size,
842 E : bool always_allocate_data) {
843 E : DCHECK_GE(offset, 0);
844 E : DCHECK_LE(offset, static_cast<Offset>(size_));
845 :
846 : // If we're growing use InsertData.
847 E : if (new_size > current_size) {
848 E : Offset insert_offset = offset + current_size;
849 E : Size insert_size = new_size - current_size;
850 E : InsertData(insert_offset, insert_size, always_allocate_data);
851 E : return true;
852 : }
853 :
854 : // If we're shrinking we'll need to use RemoveData.
855 E : if (new_size < current_size) {
856 E : Offset remove_offset = offset + new_size;
857 E : Size remove_size = current_size - new_size;
858 E : if (!RemoveData(remove_offset, remove_size))
859 i : return false;
860 : // We fall through so that 'always_allocate_data' can be respected.
861 : }
862 :
863 : // If we've been asked to, at least make sure that the data is allocated.
864 E : if (always_allocate_data && data_size_ < offset + new_size)
865 E : ResizeData(offset + new_size);
866 :
867 E : return true;
868 E : }
869 :
870 E : void BlockGraph::Block::SetData(const uint8* data, size_t data_size) {
871 : DCHECK((data_size == 0 && data == NULL) ||
872 E : (data_size != 0 && data != NULL));
873 E : DCHECK(data_size <= size_);
874 :
875 E : if (owns_data_)
876 E : delete [] data_;
877 :
878 E : owns_data_ = false;
879 E : data_ = data;
880 E : data_size_ = data_size;
881 E : }
882 :
883 E : uint8* BlockGraph::Block::AllocateData(size_t size) {
884 E : uint8* new_data = AllocateRawData(size);
885 E : if (new_data == NULL)
886 i : return NULL;
887 :
888 E : ::memset(new_data, 0, size);
889 E : return new_data;
890 E : }
891 :
892 E : uint8* BlockGraph::Block::CopyData(size_t size, const void* data) {
893 E : uint8* new_data = AllocateRawData(size);
894 E : if (new_data == NULL)
895 i : return NULL;
896 :
897 E : memcpy(new_data, data, size);
898 E : return new_data;
899 E : }
900 :
901 E : const uint8* BlockGraph::Block::ResizeData(size_t new_size) {
902 E : if (new_size == data_size_)
903 E : return data_;
904 :
905 E : if (!owns_data() && new_size < data_size_) {
906 : // Not in our ownership and shrinking. We only need to adjust our length.
907 E : data_size_ = new_size;
908 E : } else {
909 : // Either our own data, or it's growing (or both). We need to reallocate.
910 E : uint8* new_data = new uint8[new_size];
911 E : if (new_data == NULL)
912 i : return NULL;
913 :
914 : // Copy the (head of the) old data.
915 E : memcpy(new_data, data_, std::min(data_size_, new_size));
916 E : if (new_size > data_size_) {
917 : // Zero the tail.
918 E : memset(new_data + data_size_, 0, new_size - data_size_);
919 : }
920 :
921 E : if (owns_data())
922 E : delete [] data_;
923 :
924 E : owns_data_ = true;
925 E : data_ = new_data;
926 E : data_size_ = new_size;
927 : }
928 :
929 E : return data_;
930 E : }
931 :
932 E : uint8* BlockGraph::Block::GetMutableData() {
933 E : DCHECK(data_size_ != 0);
934 E : DCHECK(data_ != NULL);
935 :
936 : // Make a copy if we don't already own the data.
937 E : if (!owns_data()) {
938 E : uint8* new_data = new uint8[data_size_];
939 E : if (new_data == NULL)
940 i : return NULL;
941 E : memcpy(new_data, data_, data_size_);
942 E : data_ = new_data;
943 E : owns_data_ = true;
944 : }
945 E : DCHECK(owns_data_);
946 :
947 E : return const_cast<uint8*>(data_);
948 E : }
949 :
950 E : bool BlockGraph::Block::HasExternalReferrers() const {
951 E : ReferrerSet::const_iterator it = referrers().begin();
952 E : for (; it != referrers().end(); ++it) {
953 E : if (it->first != this)
954 E : return true;
955 E : }
956 E : return false;
957 E : }
958 :
959 E : bool BlockGraph::Block::SetReference(Offset offset, const Reference& ref) {
960 E : DCHECK(ref.referenced() != NULL);
961 :
962 : // Non-code blocks can be referred to by pointers that lie outside of their
963 : // extent (due to loop induction, arrays indexed with an implicit offset,
964 : // etc). Code blocks can not be referred to in this manner, because references
965 : // in code blocks must be places where the flow of execution actually lands.
966 E : if (ref.referenced()->type() == CODE_BLOCK) {
967 : DCHECK(ref.offset() >= 0 &&
968 E : static_cast<size_t>(ref.offset()) <= ref.referenced()->size());
969 E : DCHECK(offset + ref.size() <= size());
970 : }
971 :
972 : #if defined(DEBUG) || !defined(NDEBUG)
973 : {
974 : // NOTE: It might be worthwhile making SetReference return true on success,
975 : // and false on failure as it is possible for references to conflict.
976 : // For now we simply check for conflicts in debug builds and die an
977 : // unglorious death if we find any.
978 :
979 E : if (!ref.IsValid())
980 i : NOTREACHED() << "Trying to insert invalid reference.";
981 :
982 : // Examine references before us that could possibly conflict with us.
983 E : Offset offset_begin = offset - Reference::kMaximumSize + 1;
984 : ReferenceMap::const_iterator it =
985 E : references_.lower_bound(offset_begin);
986 E : for (; it != references_.end() && it->first < offset; ++it) {
987 E : if (static_cast<Offset>(it->first + it->second.size()) > offset)
988 i : NOTREACHED() << "Trying to insert conflicting reference.";
989 E : }
990 :
991 : // Examine the reference at the same offset if there is one. We expect it to
992 : // have the same size and type.
993 E : if (it != references_.end() && it->first == offset) {
994 E : if (it->second.size() != ref.size() || it->second.type() != ref.type()) {
995 : }
996 E : ++it;
997 : }
998 :
999 : // This is the first reference after our offset. Check to see if it lands
1000 : // within the range we want to occupy.
1001 : if (it != references_.end() &&
1002 E : it->first < static_cast<Offset>(offset + ref.size())) {
1003 i : NOTREACHED() << "Trying to insert conflicting reference.";
1004 : }
1005 E : }
1006 : #endif
1007 :
1008 : // Did we have an earlier reference at this location?
1009 E : ReferenceMap::iterator it(references_.find(offset));
1010 E : bool inserted = false;
1011 E : if (it != references_.end()) {
1012 : // Erase the back reference.
1013 E : BlockGraph::Block* referenced = it->second.referenced();
1014 E : Referrer referrer(this, offset);
1015 E : size_t removed = referenced->referrers_.erase(referrer);
1016 E : DCHECK_EQ(1U, removed);
1017 :
1018 : // Lastly switch the reference.
1019 E : it->second = ref;
1020 E : } else {
1021 : // It's a new reference, insert it.
1022 E : inserted = references_.insert(std::make_pair(offset, ref)).second;
1023 E : DCHECK(inserted);
1024 : }
1025 :
1026 : // Record the back-reference.
1027 E : ref.referenced()->referrers_.insert(std::make_pair(this, offset));
1028 :
1029 E : return inserted;
1030 E : }
1031 :
1032 : bool BlockGraph::Block::GetReference(Offset offset,
1033 E : Reference* reference) const {
1034 E : DCHECK(reference != NULL);
1035 E : ReferenceMap::const_iterator it(references_.find(offset));
1036 E : if (it == references_.end())
1037 E : return false;
1038 :
1039 E : *reference = it->second;
1040 E : return true;
1041 E : }
1042 :
1043 E : bool BlockGraph::Block::RemoveReference(Offset offset) {
1044 : // Do we have reference at this location?
1045 E : ReferenceMap::iterator it(references_.find(offset));
1046 E : if (it == references_.end())
1047 i : return false;
1048 :
1049 E : BlockGraph::Block* referenced = it->second.referenced();
1050 E : Referrer referrer(this, offset);
1051 E : size_t removed = referenced->referrers_.erase(referrer);
1052 E : DCHECK_EQ(1U, removed);
1053 E : references_.erase(it);
1054 :
1055 E : return true;
1056 E : }
1057 :
1058 E : bool BlockGraph::Block::RemoveAllReferences() {
1059 E : ReferenceMap::iterator it = references_.begin();
1060 E : while (it != references_.end()) {
1061 E : ReferenceMap::iterator to_remove = it;
1062 E : ++it;
1063 :
1064 : // TODO(rogerm): As an optimization, we don't need to drop intra-block
1065 : // references when disconnecting from the block_graph. Consider having
1066 : // BlockGraph::RemoveBlockByIterator() check that the block has no
1067 : // external referrers before calling this function and erasing the
1068 : // block.
1069 :
1070 : // Unregister this reference from the referred block then erase it.
1071 E : BlockGraph::Block* referenced = to_remove->second.referenced();
1072 E : Referrer referrer(this, to_remove->first);
1073 E : size_t removed = referenced->referrers_.erase(referrer);
1074 E : DCHECK_EQ(1U, removed);
1075 E : references_.erase(to_remove);
1076 E : }
1077 :
1078 E : return true;
1079 E : }
1080 :
1081 E : bool BlockGraph::Block::SetLabel(Offset offset, const Label& label) {
1082 E : DCHECK_LE(0, offset);
1083 E : DCHECK_LE(static_cast<size_t>(offset), size_);
1084 :
1085 E : VLOG(2) << name() << ": adding "
1086 : << LabelAttributesToString(label.attributes()) << " label '"
1087 : << label.name() << "' at offset " << offset << ".";
1088 :
1089 : // Try inserting the label into the label map.
1090 : std::pair<LabelMap::iterator, bool> result(
1091 E : labels_.insert(std::make_pair(offset, label)));
1092 :
1093 : // If it was freshly inserted then we're done.
1094 E : if (result.second)
1095 E : return true;
1096 :
1097 E : return false;
1098 E : }
1099 :
1100 E : bool BlockGraph::Block::GetLabel(Offset offset, Label* label) const {
1101 E : DCHECK(offset >= 0 && static_cast<size_t>(offset) <= size_);
1102 E : DCHECK(label != NULL);
1103 :
1104 E : LabelMap::const_iterator it = labels_.find(offset);
1105 E : if (it == labels_.end())
1106 E : return false;
1107 :
1108 E : *label = it->second;
1109 E : return true;
1110 E : }
1111 :
1112 E : bool BlockGraph::Block::RemoveLabel(Offset offset) {
1113 E : DCHECK(offset >= 0 && static_cast<size_t>(offset) <= size_);
1114 :
1115 E : return labels_.erase(offset) == 1;
1116 E : }
1117 :
1118 E : bool BlockGraph::Block::HasLabel(Offset offset) {
1119 E : DCHECK(offset >= 0 && static_cast<size_t>(offset) <= size_);
1120 :
1121 E : return labels_.find(offset) != labels_.end();
1122 E : }
1123 :
1124 : bool BlockGraph::Block::TransferReferrers(Offset offset,
1125 E : Block* new_block) {
1126 : // Redirect all referrers to the new block, we copy the referrer set
1127 : // because it is otherwise mutated during iteration.
1128 E : BlockGraph::Block::ReferrerSet referrers = referrers_;
1129 E : BlockGraph::Block::ReferrerSet::const_iterator referrer_it(referrers.begin());
1130 :
1131 E : for (; referrer_it != referrers.end(); ++referrer_it) {
1132 : // Get the original reference.
1133 E : BlockGraph::Block::Referrer referrer = *referrer_it;
1134 : BlockGraph::Block::ReferenceMap::const_iterator found_ref(
1135 E : referrer.first->references().find(referrer.second));
1136 E : DCHECK(found_ref != referrer.first->references().end());
1137 E : BlockGraph::Reference ref(found_ref->second);
1138 :
1139 E : Offset new_offset = ref.offset() + offset;
1140 E : Offset new_base = ref.base() + offset;
1141 :
1142 : // Same thing as in SetReferrer, references to non-code blocks may lie
1143 : // outside the extent of the block.
1144 E : if (type_ == CODE_BLOCK) {
1145 : if (new_offset < 0 ||
1146 E : static_cast<size_t>(new_offset) > new_block->size()) {
1147 E : LOG(ERROR) << "Transferred reference lies outside of code block.";
1148 E : return false;
1149 : }
1150 : }
1151 :
1152 : // Redirect the reference to the new block with the adjusted offset.
1153 : BlockGraph::Reference new_ref(ref.type(),
1154 : ref.size(),
1155 : new_block,
1156 : new_offset,
1157 E : new_base);
1158 E : referrer.first->SetReference(referrer.second, new_ref);
1159 E : }
1160 :
1161 E : return true;
1162 E : }
1163 :
1164 : // Returns true if this block contains the given range of bytes.
1165 E : bool BlockGraph::Block::Contains(RelativeAddress address, size_t size) const {
1166 E : return (address >= addr_ && address + size <= addr_ + size_);
1167 E : }
1168 :
1169 E : bool BlockGraph::Reference::IsValid() const {
1170 : // We can't reference a NULL block.
1171 E : if (referenced_ == NULL)
1172 E : return false;
1173 :
1174 : // First see if the base address is valid for the referenced block.
1175 E : if (base_ < 0 || static_cast<size_t>(base_) >= referenced_->size())
1176 i : return false;
1177 :
1178 E : if (!IsValidTypeSize(type_, size_))
1179 i : return false;
1180 :
1181 E : return true;
1182 E : }
1183 :
1184 E : bool BlockGraph::Reference::IsValidTypeSize(ReferenceType type, Size size) {
1185 E : switch (type) {
1186 : // We see 8- and 32-bit relative JMPs.
1187 : case PC_RELATIVE_REF:
1188 E : return size == 1 || size == 4;
1189 :
1190 : // These guys are all pointer sized.
1191 : case ABSOLUTE_REF:
1192 : case RELATIVE_REF:
1193 : case FILE_OFFSET_REF:
1194 E : return size == 4;
1195 :
1196 : default:
1197 i : NOTREACHED() << "Unknown ReferenceType.";
1198 : }
1199 :
1200 i : return false;
1201 E : }
1202 :
1203 : } // namespace block_graph
|