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