1 // Copyright 2013 Google Inc. All rights reserved. 2 // 3 // Redistribution and use in source and binary forms, with or without 4 // modification, are permitted provided that the following conditions are 5 // met: 6 // 7 // * Redistributions of source code must retain the above copyright 8 // notice, this list of conditions and the following disclaimer. 9 // * Redistributions in binary form must reproduce the above 10 // copyright notice, this list of conditions and the following disclaimer 11 // in the documentation and/or other materials provided with the 12 // distribution. 13 // * Neither the name of Google Inc. nor the names of its 14 // contributors may be used to endorse or promote products derived from 15 // this software without specific prior written permission. 16 // 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 29 // This contains a suite of tools for transforming symbol information when 30 // when that information has been extracted from a PDB containing OMAP 31 // information. 32 33 // OMAP information is a lightweight description of a mapping between two 34 // address spaces. It consists of two streams, each of them a vector 2-tuples. 35 // The OMAPTO stream contains tuples of the form 36 // 37 // (RVA in transformed image, RVA in original image) 38 // 39 // while the OMAPFROM stream contains tuples of the form 40 // 41 // (RVA in original image, RVA in transformed image) 42 // 43 // The entries in each vector are sorted by the first value of the tuple, and 44 // the lengths associated with a mapping are implicit as the distance between 45 // two successive addresses in the vector. 46 47 // Consider a trivial 10-byte function described by the following symbol: 48 // 49 // Function: RVA 0x00001000, length 10, "foo" 50 // 51 // Now consider the same function, but with 5-bytes of instrumentation injected 52 // at offset 5. The OMAP streams describing this would look like: 53 // 54 // OMAPTO : [ [0x00001000, 0x00001000], 55 // [0x00001005, 0xFFFFFFFF], 56 // [0x0000100a, 0x00001005] ] 57 // OMAPFROM: [ [0x00001000, 0x00001000], 58 // [0x00001005, 0x0000100a] ] 59 // 60 // In this case the injected code has been marked as not originating in the 61 // source image, and thus it will have no symbol information at all. However, 62 // the injected code may also be associated with an original address range; 63 // for example, when prepending instrumentation to a basic block the 64 // instrumentation can be labelled as originating from the same source BB such 65 // that symbol resolution will still find the appropriate source code line 66 // number. In this case the OMAP stream would look like: 67 // 68 // OMAPTO : [ [0x00001000, 0x00001000], 69 // [0x00001005, 0x00001005], 70 // [0x0000100a, 0x00001005] ] 71 // OMAPFROM: [ [0x00001000, 0x00001000], 72 // [0x00001005, 0x0000100a] ] 73 // 74 // Suppose we asked DIA to lookup the symbol at location 0x0000100a of the 75 // instrumented image. It would first run this through the OMAPTO table and 76 // translate that address to 0x00001005. It would then lookup the symbol 77 // at that address and return the symbol for the function "foo". This is the 78 // correct result. 79 // 80 // However, if we query DIA for the length and address of the symbol it will 81 // tell us that it has length 10 and is at RVA 0x00001000. The location is 82 // correct, but the length doesn't take into account the 5-bytes of injected 83 // code. Symbol resolution works (starting from an instrumented address, 84 // mapping to an original address, and looking up a symbol), but the symbol 85 // metadata is incorrect. 86 // 87 // If we dump the symbols using DIA they will have their addresses 88 // appropriately transformed and reflect positions in the instrumented image. 89 // However, if we try to do a lookup using those symbols resolution can fail. 90 // For example, the address 0x0000100a will not map to the symbol for "foo", 91 // because DIA tells us it is at location 0x00001000 (correct) with length 92 // 10 (incorrect). The problem is one of order of operations: in this case 93 // we're attempting symbol resolution by looking up an instrumented address 94 // in the table of translated symbols. 95 // 96 // One way to handle this is to dump the OMAP information as part of the 97 // breakpad symbols. This requires the rest of the toolchain to be aware of 98 // OMAP information and to use it when present prior to performing lookup. The 99 // other option is to properly transform the symbols (updating length as well as 100 // position) so that resolution will work as expected for translated addresses. 101 // This is transparent to the rest of the toolchain. 102 103 #include "common/windows/omap.h" 104 105 #include <atlbase.h> 106 107 #include <algorithm> 108 #include <cassert> 109 #include <set> 110 111 #include "common/windows/dia_util.h" 112 113 namespace google_breakpad { 114 115 namespace { 116 117 static const wchar_t kOmapToDebugStreamName[] = L"OMAPTO"; 118 static const wchar_t kOmapFromDebugStreamName[] = L"OMAPFROM"; 119 120 // Dependending on where this is used in breakpad we sometimes get min/max from 121 // windef, and other times from algorithm. To get around this we simply 122 // define our own min/max functions. 123 template<typename T> 124 const T& Min(const T& t1, const T& t2) { return t1 < t2 ? t1 : t2; } 125 template<typename T> 126 const T& Max(const T& t1, const T& t2) { return t1 > t2 ? t1 : t2; } 127 128 // It makes things more readable to have two different OMAP types. We cast 129 // normal OMAPs into these. They must be the same size as the OMAP structure 130 // for this to work, hence the static asserts. 131 struct OmapOrigToTran { 132 DWORD rva_original; 133 DWORD rva_transformed; 134 }; 135 struct OmapTranToOrig { 136 DWORD rva_transformed; 137 DWORD rva_original; 138 }; 139 static_assert(sizeof(OmapOrigToTran) == sizeof(OMAP), 140 "OmapOrigToTran must have same size as OMAP."); 141 static_assert(sizeof(OmapTranToOrig) == sizeof(OMAP), 142 "OmapTranToOrig must have same size as OMAP."); 143 typedef std::vector<OmapOrigToTran> OmapFromTable; 144 typedef std::vector<OmapTranToOrig> OmapToTable; 145 146 // Used for sorting and searching through a Mapping. 147 bool MappedRangeOriginalLess(const MappedRange& lhs, const MappedRange& rhs) { 148 if (lhs.rva_original < rhs.rva_original) 149 return true; 150 if (lhs.rva_original > rhs.rva_original) 151 return false; 152 return lhs.length < rhs.length; 153 } 154 bool MappedRangeMappedLess(const MappedRange& lhs, const MappedRange& rhs) { 155 if (lhs.rva_transformed < rhs.rva_transformed) 156 return true; 157 if (lhs.rva_transformed > rhs.rva_transformed) 158 return false; 159 return lhs.length < rhs.length; 160 } 161 162 // Used for searching through the EndpointIndexMap. 163 bool EndpointIndexLess(const EndpointIndex& ei1, const EndpointIndex& ei2) { 164 return ei1.endpoint < ei2.endpoint; 165 } 166 167 // Finds the debug stream with the given |name| in the given |session|, and 168 // populates |table| with its contents. Casts the data directly into OMAP 169 // structs. 170 bool FindAndLoadOmapTable(const wchar_t* name, 171 IDiaSession* session, 172 OmapTable* table) { 173 assert(name != NULL); 174 assert(session != NULL); 175 assert(table != NULL); 176 177 CComPtr<IDiaEnumDebugStreamData> stream; 178 if (!FindDebugStream(name, session, &stream)) 179 return false; 180 assert(stream.p != NULL); 181 182 LONG count = 0; 183 if (FAILED(stream->get_Count(&count))) { 184 fprintf(stderr, "IDiaEnumDebugStreamData::get_Count failed for stream " 185 "\"%ws\"\n", name); 186 return false; 187 } 188 189 // Get the length of the stream in bytes. 190 DWORD bytes_read = 0; 191 ULONG count_read = 0; 192 if (FAILED(stream->Next(count, 0, &bytes_read, NULL, &count_read))) { 193 fprintf(stderr, "IDiaEnumDebugStreamData::Next failed while reading " 194 "length of stream \"%ws\"\n", name); 195 return false; 196 } 197 198 // Ensure it's consistent with the OMAP data type. 199 DWORD bytes_expected = count * sizeof(OmapTable::value_type); 200 if (count * sizeof(OmapTable::value_type) != bytes_read) { 201 fprintf(stderr, "DIA debug stream \"%ws\" has an unexpected length", name); 202 return false; 203 } 204 205 // Read the table. 206 table->resize(count); 207 bytes_read = 0; 208 count_read = 0; 209 if (FAILED(stream->Next(count, bytes_expected, &bytes_read, 210 reinterpret_cast<BYTE*>(&table->at(0)), 211 &count_read))) { 212 fprintf(stderr, "IDiaEnumDebugStreamData::Next failed while reading " 213 "data from stream \"%ws\"\n"); 214 return false; 215 } 216 217 return true; 218 } 219 220 // This determines the original image length by looking through the segment 221 // table. 222 bool GetOriginalImageLength(IDiaSession* session, DWORD* image_length) { 223 assert(session != NULL); 224 assert(image_length != NULL); 225 226 CComPtr<IDiaEnumSegments> enum_segments; 227 if (!FindTable(session, &enum_segments)) 228 return false; 229 assert(enum_segments.p != NULL); 230 231 DWORD temp_image_length = 0; 232 CComPtr<IDiaSegment> segment; 233 ULONG fetched = 0; 234 while (SUCCEEDED(enum_segments->Next(1, &segment, &fetched)) && 235 fetched == 1) { 236 assert(segment.p != NULL); 237 238 DWORD rva = 0; 239 DWORD length = 0; 240 DWORD frame = 0; 241 if (FAILED(segment->get_relativeVirtualAddress(&rva)) || 242 FAILED(segment->get_length(&length)) || 243 FAILED(segment->get_frame(&frame))) { 244 fprintf(stderr, "Failed to get basic properties for IDiaSegment\n"); 245 return false; 246 } 247 248 if (frame > 0) { 249 DWORD segment_end = rva + length; 250 if (segment_end > temp_image_length) 251 temp_image_length = segment_end; 252 } 253 segment.Release(); 254 } 255 256 *image_length = temp_image_length; 257 return true; 258 } 259 260 // Detects regions of the original image that have been removed in the 261 // transformed image, and sets the 'removed' property on all mapped ranges 262 // immediately preceding a gap. The mapped ranges must be sorted by 263 // 'rva_original'. 264 void FillInRemovedLengths(Mapping* mapping) { 265 assert(mapping != NULL); 266 267 // Find and fill gaps. We do this with two sweeps. We first sweep forward 268 // looking for gaps. When we identify a gap we then sweep forward with a 269 // second scan and set the 'removed' property for any intervals that 270 // immediately precede the gap. 271 // 272 // Gaps are typically between two successive intervals, but not always: 273 // 274 // Range 1: --------------- 275 // Range 2: ------- 276 // Range 3: ------------- 277 // Gap : ****** 278 // 279 // In the above example the gap is between range 1 and range 3. A forward 280 // sweep finds the gap, and a second forward sweep identifies that range 1 281 // immediately precedes the gap and sets its 'removed' property. 282 283 size_t fill = 0; 284 DWORD rva_front = 0; 285 for (size_t find = 0; find < mapping->size(); ++find) { 286 #ifndef NDEBUG 287 // We expect the mapped ranges to be sorted by 'rva_original'. 288 if (find > 0) { 289 assert(mapping->at(find - 1).rva_original <= 290 mapping->at(find).rva_original); 291 } 292 #endif 293 294 if (rva_front < mapping->at(find).rva_original) { 295 // We've found a gap. Fill it in by setting the 'removed' property for 296 // any affected intervals. 297 DWORD removed = mapping->at(find).rva_original - rva_front; 298 for (; fill < find; ++fill) { 299 if (mapping->at(fill).rva_original + mapping->at(fill).length != 300 rva_front) { 301 continue; 302 } 303 304 // This interval ends right where the gap starts. It needs to have its 305 // 'removed' information filled in. 306 mapping->at(fill).removed = removed; 307 } 308 } 309 310 // Advance the front that indicates the covered portion of the image. 311 rva_front = mapping->at(find).rva_original + mapping->at(find).length; 312 } 313 } 314 315 // Builds a unified view of the mapping between the original and transformed 316 // image space by merging OMAPTO and OMAPFROM data. 317 void BuildMapping(const OmapData& omap_data, Mapping* mapping) { 318 assert(mapping != NULL); 319 320 mapping->clear(); 321 322 if (omap_data.omap_from.empty() || omap_data.omap_to.empty()) 323 return; 324 325 // The names 'omap_to' and 'omap_from' are awfully confusing, so we make 326 // ourselves more explicit here. This cast is only safe because the underlying 327 // types have the exact same size. 328 const OmapToTable& tran2orig = 329 reinterpret_cast<const OmapToTable&>(omap_data.omap_to); 330 const OmapFromTable& orig2tran = reinterpret_cast<const OmapFromTable&>( 331 omap_data.omap_from); 332 333 // Handle the range of data at the beginning of the image. This is not usually 334 // specified by the OMAP data. 335 if (tran2orig[0].rva_transformed > 0 && orig2tran[0].rva_original > 0) { 336 DWORD header_transformed = tran2orig[0].rva_transformed; 337 DWORD header_original = orig2tran[0].rva_original; 338 DWORD header = Min(header_transformed, header_original); 339 340 MappedRange mr = {}; 341 mr.length = header; 342 mr.injected = header_transformed - header; 343 mr.removed = header_original - header; 344 mapping->push_back(mr); 345 } 346 347 // Convert the implied lengths to explicit lengths, and infer which content 348 // has been injected into the transformed image. Injected content is inferred 349 // as regions of the transformed address space that does not map back to 350 // known valid content in the original image. 351 for (size_t i = 0; i < tran2orig.size(); ++i) { 352 const OmapTranToOrig& o1 = tran2orig[i]; 353 354 // This maps to content that is outside the original image, thus it 355 // describes injected content. We can skip this entry. 356 if (o1.rva_original >= omap_data.length_original) 357 continue; 358 359 // Calculate the length of the current OMAP entry. This is implicit as the 360 // distance between successive |rva| values, capped at the end of the 361 // original image. 362 DWORD length = 0; 363 if (i + 1 < tran2orig.size()) { 364 const OmapTranToOrig& o2 = tran2orig[i + 1]; 365 366 // We expect the table to be sorted by rva_transformed. 367 assert(o1.rva_transformed <= o2.rva_transformed); 368 369 length = o2.rva_transformed - o1.rva_transformed; 370 if (o1.rva_original + length > omap_data.length_original) { 371 length = omap_data.length_original - o1.rva_original; 372 } 373 } else { 374 length = omap_data.length_original - o1.rva_original; 375 } 376 377 // Zero-length entries don't describe anything and can be ignored. 378 if (length == 0) 379 continue; 380 381 // Any gaps in the transformed address-space are due to injected content. 382 if (!mapping->empty()) { 383 MappedRange& prev_mr = mapping->back(); 384 prev_mr.injected += o1.rva_transformed - 385 (prev_mr.rva_transformed + prev_mr.length); 386 } 387 388 MappedRange mr = {}; 389 mr.rva_original = o1.rva_original; 390 mr.rva_transformed = o1.rva_transformed; 391 mr.length = length; 392 mapping->push_back(mr); 393 } 394 395 // Sort based on the original image addresses. 396 std::sort(mapping->begin(), mapping->end(), MappedRangeOriginalLess); 397 398 // Fill in the 'removed' lengths by looking for gaps in the coverage of the 399 // original address space. 400 FillInRemovedLengths(mapping); 401 402 return; 403 } 404 405 void BuildEndpointIndexMap(ImageMap* image_map) { 406 assert(image_map != NULL); 407 408 if (image_map->mapping.size() == 0) 409 return; 410 411 const Mapping& mapping = image_map->mapping; 412 EndpointIndexMap& eim = image_map->endpoint_index_map; 413 414 // Get the unique set of interval endpoints. 415 std::set<DWORD> endpoints; 416 for (size_t i = 0; i < mapping.size(); ++i) { 417 endpoints.insert(mapping[i].rva_original); 418 endpoints.insert(mapping[i].rva_original + 419 mapping[i].length + 420 mapping[i].removed); 421 } 422 423 // Use the endpoints to initialize the secondary search structure for the 424 // mapping. 425 eim.resize(endpoints.size()); 426 std::set<DWORD>::const_iterator it = endpoints.begin(); 427 for (size_t i = 0; it != endpoints.end(); ++it, ++i) { 428 eim[i].endpoint = *it; 429 eim[i].index = mapping.size(); 430 } 431 432 // For each endpoint we want the smallest index of any interval containing 433 // it. We iterate over the intervals and update the indices associated with 434 // each interval endpoint contained in the current interval. In the general 435 // case of an arbitrary set of intervals this is O(n^2), but the structure of 436 // OMAP data makes this O(n). 437 for (size_t i = 0; i < mapping.size(); ++i) { 438 EndpointIndex ei1 = { mapping[i].rva_original, 0 }; 439 EndpointIndexMap::iterator it1 = std::lower_bound( 440 eim.begin(), eim.end(), ei1, EndpointIndexLess); 441 442 EndpointIndex ei2 = { mapping[i].rva_original + mapping[i].length + 443 mapping[i].removed, 0 }; 444 EndpointIndexMap::iterator it2 = std::lower_bound( 445 eim.begin(), eim.end(), ei2, EndpointIndexLess); 446 447 for (; it1 != it2; ++it1) 448 it1->index = Min(i, it1->index); 449 } 450 } 451 452 // Clips the given mapped range. 453 void ClipMappedRangeOriginal(const AddressRange& clip_range, 454 MappedRange* mapped_range) { 455 assert(mapped_range != NULL); 456 457 // The clipping range is entirely outside of the mapped range. 458 if (clip_range.end() <= mapped_range->rva_original || 459 mapped_range->rva_original + mapped_range->length + 460 mapped_range->removed <= clip_range.rva) { 461 mapped_range->length = 0; 462 mapped_range->injected = 0; 463 mapped_range->removed = 0; 464 return; 465 } 466 467 // Clip the left side. 468 if (mapped_range->rva_original < clip_range.rva) { 469 DWORD clip_left = clip_range.rva - mapped_range->rva_original; 470 mapped_range->rva_original += clip_left; 471 mapped_range->rva_transformed += clip_left; 472 473 if (clip_left > mapped_range->length) { 474 // The left clipping boundary entirely erases the content section of the 475 // range. 476 DWORD trim = clip_left - mapped_range->length; 477 mapped_range->length = 0; 478 mapped_range->injected -= Min(trim, mapped_range->injected); 479 // We know that trim <= mapped_range->remove. 480 mapped_range->removed -= trim; 481 } else { 482 // The left clipping boundary removes some, but not all, of the content. 483 // As such it leaves the removed/injected component intact. 484 mapped_range->length -= clip_left; 485 } 486 } 487 488 // Clip the right side. 489 DWORD end_original = mapped_range->rva_original + mapped_range->length; 490 if (clip_range.end() < end_original) { 491 // The right clipping boundary lands in the 'content' section of the range, 492 // entirely clearing the injected/removed portion. 493 DWORD clip_right = end_original - clip_range.end(); 494 mapped_range->length -= clip_right; 495 mapped_range->injected = 0; 496 mapped_range->removed = 0; 497 return; 498 } else { 499 // The right clipping boundary is outside of the content, but may affect 500 // the removed/injected portion of the range. 501 DWORD end_removed = end_original + mapped_range->removed; 502 if (clip_range.end() < end_removed) 503 mapped_range->removed = clip_range.end() - end_original; 504 505 DWORD end_injected = end_original + mapped_range->injected; 506 if (clip_range.end() < end_injected) 507 mapped_range->injected = clip_range.end() - end_original; 508 } 509 510 return; 511 } 512 513 } // namespace 514 515 int AddressRange::Compare(const AddressRange& rhs) const { 516 if (end() <= rhs.rva) 517 return -1; 518 if (rhs.end() <= rva) 519 return 1; 520 return 0; 521 } 522 523 bool GetOmapDataAndDisableTranslation(IDiaSession* session, 524 OmapData* omap_data) { 525 assert(session != NULL); 526 assert(omap_data != NULL); 527 528 CComPtr<IDiaAddressMap> address_map; 529 if (FAILED(session->QueryInterface(&address_map))) { 530 fprintf(stderr, "IDiaSession::QueryInterface(IDiaAddressMap) failed\n"); 531 return false; 532 } 533 assert(address_map.p != NULL); 534 535 BOOL omap_enabled = FALSE; 536 if (FAILED(address_map->get_addressMapEnabled(&omap_enabled))) { 537 fprintf(stderr, "IDiaAddressMap::get_addressMapEnabled failed\n"); 538 return false; 539 } 540 541 if (!omap_enabled) { 542 // We indicate the non-presence of OMAP data by returning empty tables. 543 omap_data->omap_from.clear(); 544 omap_data->omap_to.clear(); 545 omap_data->length_original = 0; 546 return true; 547 } 548 549 // OMAP data is present. Disable translation. 550 if (FAILED(address_map->put_addressMapEnabled(FALSE))) { 551 fprintf(stderr, "IDiaAddressMap::put_addressMapEnabled failed\n"); 552 return false; 553 } 554 555 // Read the OMAP streams. 556 if (!FindAndLoadOmapTable(kOmapFromDebugStreamName, 557 session, 558 &omap_data->omap_from)) { 559 return false; 560 } 561 if (!FindAndLoadOmapTable(kOmapToDebugStreamName, 562 session, 563 &omap_data->omap_to)) { 564 return false; 565 } 566 567 // Get the lengths of the address spaces. 568 if (!GetOriginalImageLength(session, &omap_data->length_original)) 569 return false; 570 571 return true; 572 } 573 574 void BuildImageMap(const OmapData& omap_data, ImageMap* image_map) { 575 assert(image_map != NULL); 576 577 BuildMapping(omap_data, &image_map->mapping); 578 BuildEndpointIndexMap(image_map); 579 } 580 581 void MapAddressRange(const ImageMap& image_map, 582 const AddressRange& original_range, 583 AddressRangeVector* mapped_ranges) { 584 assert(mapped_ranges != NULL); 585 586 const Mapping& map = image_map.mapping; 587 588 // Handle the trivial case of an empty image_map. This means that there is 589 // no transformation to be applied, and we can simply return the original 590 // range. 591 if (map.empty()) { 592 mapped_ranges->push_back(original_range); 593 return; 594 } 595 596 // If we get a query of length 0 we need to handle it by using a non-zero 597 // query length. 598 AddressRange query_range(original_range); 599 if (query_range.length == 0) 600 query_range.length = 1; 601 602 // Find the range of intervals that can potentially intersect our query range. 603 size_t imin = 0; 604 size_t imax = 0; 605 { 606 // The index of the earliest possible range that can affect is us done by 607 // searching through the secondary indexing structure. 608 const EndpointIndexMap& eim = image_map.endpoint_index_map; 609 EndpointIndex q1 = { query_range.rva, 0 }; 610 EndpointIndexMap::const_iterator it1 = std::lower_bound( 611 eim.begin(), eim.end(), q1, EndpointIndexLess); 612 if (it1 == eim.end()) { 613 imin = map.size(); 614 } else { 615 // Backup to find the interval that contains our query point. 616 if (it1 != eim.begin() && query_range.rva < it1->endpoint) 617 --it1; 618 imin = it1->index; 619 } 620 621 // The first range that can't possibly intersect us is found by searching 622 // through the image map directly as it is already sorted by interval start 623 // point. 624 MappedRange q2 = { query_range.end(), 0 }; 625 Mapping::const_iterator it2 = std::lower_bound( 626 map.begin(), map.end(), q2, MappedRangeOriginalLess); 627 imax = it2 - map.begin(); 628 } 629 630 // Find all intervals that intersect the query range. 631 Mapping temp_map; 632 for (size_t i = imin; i < imax; ++i) { 633 MappedRange mr = map[i]; 634 ClipMappedRangeOriginal(query_range, &mr); 635 if (mr.length + mr.injected > 0) 636 temp_map.push_back(mr); 637 } 638 639 // If there are no intersecting ranges then the query range has been removed 640 // from the image in question. 641 if (temp_map.empty()) 642 return; 643 644 // Sort based on transformed addresses. 645 std::sort(temp_map.begin(), temp_map.end(), MappedRangeMappedLess); 646 647 // Zero-length queries can't actually be merged. We simply output the set of 648 // unique RVAs that correspond to the query RVA. 649 if (original_range.length == 0) { 650 mapped_ranges->push_back(AddressRange(temp_map[0].rva_transformed, 0)); 651 for (size_t i = 1; i < temp_map.size(); ++i) { 652 if (temp_map[i].rva_transformed > mapped_ranges->back().rva) 653 mapped_ranges->push_back(AddressRange(temp_map[i].rva_transformed, 0)); 654 } 655 return; 656 } 657 658 // Merge any ranges that are consecutive in the mapped image. We merge over 659 // injected content if it makes ranges contiguous, but we ignore any injected 660 // content at the tail end of a range. This allows us to detect symbols that 661 // have been lengthened by injecting content in the middle. However, it 662 // misses the case where content has been injected at the head or the tail. 663 // The problem is that it doesn't know whether to attribute it to the 664 // preceding or following symbol. It is up to the author of the transform to 665 // output explicit OMAP info in these cases to ensure full coverage of the 666 // transformed address space. 667 DWORD rva_begin = temp_map[0].rva_transformed; 668 DWORD rva_cur_content = rva_begin + temp_map[0].length; 669 DWORD rva_cur_injected = rva_cur_content + temp_map[0].injected; 670 for (size_t i = 1; i < temp_map.size(); ++i) { 671 if (rva_cur_injected < temp_map[i].rva_transformed) { 672 // This marks the end of a continuous range in the image. Output the 673 // current range and start a new one. 674 if (rva_begin < rva_cur_content) { 675 mapped_ranges->push_back( 676 AddressRange(rva_begin, rva_cur_content - rva_begin)); 677 } 678 rva_begin = temp_map[i].rva_transformed; 679 } 680 681 rva_cur_content = temp_map[i].rva_transformed + temp_map[i].length; 682 rva_cur_injected = rva_cur_content + temp_map[i].injected; 683 } 684 685 // Output the range in progress. 686 if (rva_begin < rva_cur_content) { 687 mapped_ranges->push_back( 688 AddressRange(rva_begin, rva_cur_content - rva_begin)); 689 } 690 691 return; 692 } 693 694 } // namespace google_breakpad