omap.cc
1 // Copyright 2013 Google LLC 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 LLC 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 #ifdef HAVE_CONFIG_H 104 #include <config.h> // Must come first 105 #endif 106 107 #include "common/windows/omap.h" 108 109 #include <atlbase.h> 110 111 #include <algorithm> 112 #include <cassert> 113 #include <set> 114 115 #include "common/windows/dia_util.h" 116 117 namespace google_breakpad { 118 119 namespace { 120 121 static const wchar_t kOmapToDebugStreamName[] = L"OMAPTO"; 122 static const wchar_t kOmapFromDebugStreamName[] = L"OMAPFROM"; 123 124 // Dependending on where this is used in breakpad we sometimes get min/max from 125 // windef, and other times from algorithm. To get around this we simply 126 // define our own min/max functions. 127 template<typename T> 128 const T& Min(const T& t1, const T& t2) { return t1 < t2 ? t1 : t2; } 129 template<typename T> 130 const T& Max(const T& t1, const T& t2) { return t1 > t2 ? t1 : t2; } 131 132 // It makes things more readable to have two different OMAP types. We cast 133 // normal OMAPs into these. They must be the same size as the OMAP structure 134 // for this to work, hence the static asserts. 135 struct OmapOrigToTran { 136 DWORD rva_original; 137 DWORD rva_transformed; 138 }; 139 struct OmapTranToOrig { 140 DWORD rva_transformed; 141 DWORD rva_original; 142 }; 143 static_assert(sizeof(OmapOrigToTran) == sizeof(OMAP), 144 "OmapOrigToTran must have same size as OMAP."); 145 static_assert(sizeof(OmapTranToOrig) == sizeof(OMAP), 146 "OmapTranToOrig must have same size as OMAP."); 147 typedef std::vector<OmapOrigToTran> OmapFromTable; 148 typedef std::vector<OmapTranToOrig> OmapToTable; 149 150 // Used for sorting and searching through a Mapping. 151 bool MappedRangeOriginalLess(const MappedRange& lhs, const MappedRange& rhs) { 152 if (lhs.rva_original < rhs.rva_original) 153 return true; 154 if (lhs.rva_original > rhs.rva_original) 155 return false; 156 return lhs.length < rhs.length; 157 } 158 bool MappedRangeMappedLess(const MappedRange& lhs, const MappedRange& rhs) { 159 if (lhs.rva_transformed < rhs.rva_transformed) 160 return true; 161 if (lhs.rva_transformed > rhs.rva_transformed) 162 return false; 163 return lhs.length < rhs.length; 164 } 165 166 // Used for searching through the EndpointIndexMap. 167 bool EndpointIndexLess(const EndpointIndex& ei1, const EndpointIndex& ei2) { 168 return ei1.endpoint < ei2.endpoint; 169 } 170 171 // Finds the debug stream with the given |name| in the given |session|, and 172 // populates |table| with its contents. Casts the data directly into OMAP 173 // structs. 174 bool FindAndLoadOmapTable(const wchar_t* name, 175 IDiaSession* session, 176 OmapTable* table) { 177 assert(name != NULL); 178 assert(session != NULL); 179 assert(table != NULL); 180 181 CComPtr<IDiaEnumDebugStreamData> stream; 182 if (!FindDebugStream(name, session, &stream)) 183 return false; 184 assert(stream.p != NULL); 185 186 LONG count = 0; 187 if (FAILED(stream->get_Count(&count))) { 188 fprintf(stderr, "IDiaEnumDebugStreamData::get_Count failed for stream " 189 "\"%ws\"\n", name); 190 return false; 191 } 192 193 // Get the length of the stream in bytes. 194 DWORD bytes_read = 0; 195 ULONG count_read = 0; 196 if (FAILED(stream->Next(count, 0, &bytes_read, NULL, &count_read))) { 197 fprintf(stderr, "IDiaEnumDebugStreamData::Next failed while reading " 198 "length of stream \"%ws\"\n", name); 199 return false; 200 } 201 202 // Ensure it's consistent with the OMAP data type. 203 DWORD bytes_expected = count * sizeof(OmapTable::value_type); 204 if (count * sizeof(OmapTable::value_type) != bytes_read) { 205 fprintf(stderr, "DIA debug stream \"%ws\" has an unexpected length", name); 206 return false; 207 } 208 209 // Read the table. 210 table->resize(count); 211 bytes_read = 0; 212 count_read = 0; 213 if (FAILED(stream->Next(count, bytes_expected, &bytes_read, 214 reinterpret_cast<BYTE*>(&table->at(0)), 215 &count_read))) { 216 fprintf(stderr, "IDiaEnumDebugStreamData::Next failed while reading " 217 "data from stream \"%ws\"\n", name); 218 return false; 219 } 220 221 return true; 222 } 223 224 // This determines the original image length by looking through the segment 225 // table. 226 bool GetOriginalImageLength(IDiaSession* session, DWORD* image_length) { 227 assert(session != NULL); 228 assert(image_length != NULL); 229 230 CComPtr<IDiaEnumSegments> enum_segments; 231 if (!FindTable(session, &enum_segments)) 232 return false; 233 assert(enum_segments.p != NULL); 234 235 DWORD temp_image_length = 0; 236 CComPtr<IDiaSegment> segment; 237 ULONG fetched = 0; 238 while (SUCCEEDED(enum_segments->Next(1, &segment, &fetched)) && 239 fetched == 1) { 240 assert(segment.p != NULL); 241 242 DWORD rva = 0; 243 DWORD length = 0; 244 DWORD frame = 0; 245 if (FAILED(segment->get_relativeVirtualAddress(&rva)) || 246 FAILED(segment->get_length(&length)) || 247 FAILED(segment->get_frame(&frame))) { 248 fprintf(stderr, "Failed to get basic properties for IDiaSegment\n"); 249 return false; 250 } 251 252 if (frame > 0) { 253 DWORD segment_end = rva + length; 254 if (segment_end > temp_image_length) 255 temp_image_length = segment_end; 256 } 257 segment.Release(); 258 } 259 260 *image_length = temp_image_length; 261 return true; 262 } 263 264 // Detects regions of the original image that have been removed in the 265 // transformed image, and sets the 'removed' property on all mapped ranges 266 // immediately preceding a gap. The mapped ranges must be sorted by 267 // 'rva_original'. 268 void FillInRemovedLengths(Mapping* mapping) { 269 assert(mapping != NULL); 270 271 // Find and fill gaps. We do this with two sweeps. We first sweep forward 272 // looking for gaps. When we identify a gap we then sweep forward with a 273 // second scan and set the 'removed' property for any intervals that 274 // immediately precede the gap. 275 // 276 // Gaps are typically between two successive intervals, but not always: 277 // 278 // Range 1: --------------- 279 // Range 2: ------- 280 // Range 3: ------------- 281 // Gap : ****** 282 // 283 // In the above example the gap is between range 1 and range 3. A forward 284 // sweep finds the gap, and a second forward sweep identifies that range 1 285 // immediately precedes the gap and sets its 'removed' property. 286 287 size_t fill = 0; 288 DWORD rva_front = 0; 289 for (size_t find = 0; find < mapping->size(); ++find) { 290 #ifndef NDEBUG 291 // We expect the mapped ranges to be sorted by 'rva_original'. 292 if (find > 0) { 293 assert(mapping->at(find - 1).rva_original <= 294 mapping->at(find).rva_original); 295 } 296 #endif 297 298 if (rva_front < mapping->at(find).rva_original) { 299 // We've found a gap. Fill it in by setting the 'removed' property for 300 // any affected intervals. 301 DWORD removed = mapping->at(find).rva_original - rva_front; 302 for (; fill < find; ++fill) { 303 if (mapping->at(fill).rva_original + mapping->at(fill).length != 304 rva_front) { 305 continue; 306 } 307 308 // This interval ends right where the gap starts. It needs to have its 309 // 'removed' information filled in. 310 mapping->at(fill).removed = removed; 311 } 312 } 313 314 // Advance the front that indicates the covered portion of the image. 315 rva_front = mapping->at(find).rva_original + mapping->at(find).length; 316 } 317 } 318 319 // Builds a unified view of the mapping between the original and transformed 320 // image space by merging OMAPTO and OMAPFROM data. 321 void BuildMapping(const OmapData& omap_data, Mapping* mapping) { 322 assert(mapping != NULL); 323 324 mapping->clear(); 325 326 if (omap_data.omap_from.empty() || omap_data.omap_to.empty()) 327 return; 328 329 // The names 'omap_to' and 'omap_from' are awfully confusing, so we make 330 // ourselves more explicit here. This cast is only safe because the underlying 331 // types have the exact same size. 332 const OmapToTable& tran2orig = 333 reinterpret_cast<const OmapToTable&>(omap_data.omap_to); 334 const OmapFromTable& orig2tran = reinterpret_cast<const OmapFromTable&>( 335 omap_data.omap_from); 336 337 // Handle the range of data at the beginning of the image. This is not usually 338 // specified by the OMAP data. 339 if (tran2orig[0].rva_transformed > 0 && orig2tran[0].rva_original > 0) { 340 DWORD header_transformed = tran2orig[0].rva_transformed; 341 DWORD header_original = orig2tran[0].rva_original; 342 DWORD header = Min(header_transformed, header_original); 343 344 MappedRange mr = {}; 345 mr.length = header; 346 mr.injected = header_transformed - header; 347 mr.removed = header_original - header; 348 mapping->push_back(mr); 349 } 350 351 // Convert the implied lengths to explicit lengths, and infer which content 352 // has been injected into the transformed image. Injected content is inferred 353 // as regions of the transformed address space that does not map back to 354 // known valid content in the original image. 355 for (size_t i = 0; i < tran2orig.size(); ++i) { 356 const OmapTranToOrig& o1 = tran2orig[i]; 357 358 // This maps to content that is outside the original image, thus it 359 // describes injected content. We can skip this entry. 360 if (o1.rva_original >= omap_data.length_original) 361 continue; 362 363 // Calculate the length of the current OMAP entry. This is implicit as the 364 // distance between successive |rva| values, capped at the end of the 365 // original image. 366 DWORD length = 0; 367 if (i + 1 < tran2orig.size()) { 368 const OmapTranToOrig& o2 = tran2orig[i + 1]; 369 370 // We expect the table to be sorted by rva_transformed. 371 assert(o1.rva_transformed <= o2.rva_transformed); 372 373 length = o2.rva_transformed - o1.rva_transformed; 374 if (o1.rva_original + length > omap_data.length_original) { 375 length = omap_data.length_original - o1.rva_original; 376 } 377 } else { 378 length = omap_data.length_original - o1.rva_original; 379 } 380 381 // Zero-length entries don't describe anything and can be ignored. 382 if (length == 0) 383 continue; 384 385 // Any gaps in the transformed address-space are due to injected content. 386 if (!mapping->empty()) { 387 MappedRange& prev_mr = mapping->back(); 388 prev_mr.injected += o1.rva_transformed - 389 (prev_mr.rva_transformed + prev_mr.length); 390 } 391 392 MappedRange mr = {}; 393 mr.rva_original = o1.rva_original; 394 mr.rva_transformed = o1.rva_transformed; 395 mr.length = length; 396 mapping->push_back(mr); 397 } 398 399 // Sort based on the original image addresses. 400 std::sort(mapping->begin(), mapping->end(), MappedRangeOriginalLess); 401 402 // Fill in the 'removed' lengths by looking for gaps in the coverage of the 403 // original address space. 404 FillInRemovedLengths(mapping); 405 406 return; 407 } 408 409 void BuildEndpointIndexMap(ImageMap* image_map) { 410 assert(image_map != NULL); 411 412 if (image_map->mapping.size() == 0) 413 return; 414 415 const Mapping& mapping = image_map->mapping; 416 EndpointIndexMap& eim = image_map->endpoint_index_map; 417 418 // Get the unique set of interval endpoints. 419 std::set<DWORD> endpoints; 420 for (size_t i = 0; i < mapping.size(); ++i) { 421 endpoints.insert(mapping[i].rva_original); 422 endpoints.insert(mapping[i].rva_original + 423 mapping[i].length + 424 mapping[i].removed); 425 } 426 427 // Use the endpoints to initialize the secondary search structure for the 428 // mapping. 429 eim.resize(endpoints.size()); 430 std::set<DWORD>::const_iterator it = endpoints.begin(); 431 for (size_t i = 0; it != endpoints.end(); ++it, ++i) { 432 eim[i].endpoint = *it; 433 eim[i].index = mapping.size(); 434 } 435 436 // For each endpoint we want the smallest index of any interval containing 437 // it. We iterate over the intervals and update the indices associated with 438 // each interval endpoint contained in the current interval. In the general 439 // case of an arbitrary set of intervals this is O(n^2), but the structure of 440 // OMAP data makes this O(n). 441 for (size_t i = 0; i < mapping.size(); ++i) { 442 EndpointIndex ei1 = { mapping[i].rva_original, 0 }; 443 EndpointIndexMap::iterator it1 = std::lower_bound( 444 eim.begin(), eim.end(), ei1, EndpointIndexLess); 445 446 EndpointIndex ei2 = { mapping[i].rva_original + mapping[i].length + 447 mapping[i].removed, 0 }; 448 EndpointIndexMap::iterator it2 = std::lower_bound( 449 eim.begin(), eim.end(), ei2, EndpointIndexLess); 450 451 for (; it1 != it2; ++it1) 452 it1->index = Min(i, it1->index); 453 } 454 } 455 456 void BuildSubsequentRVAMap(const OmapData& omap_data, 457 std::map<DWORD, DWORD>* subsequent) { 458 assert(subsequent->empty()); 459 const OmapFromTable& orig2tran = 460 reinterpret_cast<const OmapFromTable&>(omap_data.omap_from); 461 462 if (orig2tran.empty()) 463 return; 464 465 for (size_t i = 0; i < orig2tran.size() - 1; ++i) { 466 // Expect that orig2tran is sorted. 467 if (orig2tran[i].rva_original >= orig2tran[i + 1].rva_original) { 468 fprintf(stderr, "OMAP 'from' table unexpectedly unsorted\n"); 469 subsequent->clear(); 470 return; 471 } 472 subsequent->insert(std::make_pair(orig2tran[i].rva_original, 473 orig2tran[i + 1].rva_original)); 474 } 475 } 476 477 // Clips the given mapped range. 478 void ClipMappedRangeOriginal(const AddressRange& clip_range, 479 MappedRange* mapped_range) { 480 assert(mapped_range != NULL); 481 482 // The clipping range is entirely outside of the mapped range. 483 if (clip_range.end() <= mapped_range->rva_original || 484 mapped_range->rva_original + mapped_range->length + 485 mapped_range->removed <= clip_range.rva) { 486 mapped_range->length = 0; 487 mapped_range->injected = 0; 488 mapped_range->removed = 0; 489 return; 490 } 491 492 // Clip the left side. 493 if (mapped_range->rva_original < clip_range.rva) { 494 DWORD clip_left = clip_range.rva - mapped_range->rva_original; 495 mapped_range->rva_original += clip_left; 496 mapped_range->rva_transformed += clip_left; 497 498 if (clip_left > mapped_range->length) { 499 // The left clipping boundary entirely erases the content section of the 500 // range. 501 DWORD trim = clip_left - mapped_range->length; 502 mapped_range->length = 0; 503 mapped_range->injected -= Min(trim, mapped_range->injected); 504 // We know that trim <= mapped_range->remove. 505 mapped_range->removed -= trim; 506 } else { 507 // The left clipping boundary removes some, but not all, of the content. 508 // As such it leaves the removed/injected component intact. 509 mapped_range->length -= clip_left; 510 } 511 } 512 513 // Clip the right side. 514 DWORD end_original = mapped_range->rva_original + mapped_range->length; 515 if (clip_range.end() < end_original) { 516 // The right clipping boundary lands in the 'content' section of the range, 517 // entirely clearing the injected/removed portion. 518 DWORD clip_right = end_original - clip_range.end(); 519 mapped_range->length -= clip_right; 520 mapped_range->injected = 0; 521 mapped_range->removed = 0; 522 return; 523 } else { 524 // The right clipping boundary is outside of the content, but may affect 525 // the removed/injected portion of the range. 526 DWORD end_removed = end_original + mapped_range->removed; 527 if (clip_range.end() < end_removed) 528 mapped_range->removed = clip_range.end() - end_original; 529 530 DWORD end_injected = end_original + mapped_range->injected; 531 if (clip_range.end() < end_injected) 532 mapped_range->injected = clip_range.end() - end_original; 533 } 534 535 return; 536 } 537 538 } // namespace 539 540 int AddressRange::Compare(const AddressRange& rhs) const { 541 if (end() <= rhs.rva) 542 return -1; 543 if (rhs.end() <= rva) 544 return 1; 545 return 0; 546 } 547 548 bool GetOmapDataAndDisableTranslation(IDiaSession* session, 549 OmapData* omap_data) { 550 assert(session != NULL); 551 assert(omap_data != NULL); 552 553 CComPtr<IDiaAddressMap> address_map; 554 if (FAILED(session->QueryInterface(&address_map))) { 555 fprintf(stderr, "IDiaSession::QueryInterface(IDiaAddressMap) failed\n"); 556 return false; 557 } 558 assert(address_map.p != NULL); 559 560 BOOL omap_enabled = FALSE; 561 if (FAILED(address_map->get_addressMapEnabled(&omap_enabled))) { 562 fprintf(stderr, "IDiaAddressMap::get_addressMapEnabled failed\n"); 563 return false; 564 } 565 566 if (!omap_enabled) { 567 // We indicate the non-presence of OMAP data by returning empty tables. 568 omap_data->omap_from.clear(); 569 omap_data->omap_to.clear(); 570 omap_data->length_original = 0; 571 return true; 572 } 573 574 // OMAP data is present. Disable translation. 575 if (FAILED(address_map->put_addressMapEnabled(FALSE))) { 576 fprintf(stderr, "IDiaAddressMap::put_addressMapEnabled failed\n"); 577 return false; 578 } 579 580 // Read the OMAP streams. 581 if (!FindAndLoadOmapTable(kOmapFromDebugStreamName, 582 session, 583 &omap_data->omap_from)) { 584 return false; 585 } 586 if (!FindAndLoadOmapTable(kOmapToDebugStreamName, 587 session, 588 &omap_data->omap_to)) { 589 return false; 590 } 591 592 // Get the lengths of the address spaces. 593 if (!GetOriginalImageLength(session, &omap_data->length_original)) 594 return false; 595 596 return true; 597 } 598 599 void BuildImageMap(const OmapData& omap_data, ImageMap* image_map) { 600 assert(image_map != NULL); 601 602 BuildMapping(omap_data, &image_map->mapping); 603 BuildEndpointIndexMap(image_map); 604 BuildSubsequentRVAMap(omap_data, &image_map->subsequent_rva_block); 605 } 606 607 void MapAddressRange(const ImageMap& image_map, 608 const AddressRange& original_range, 609 AddressRangeVector* mapped_ranges) { 610 assert(mapped_ranges != NULL); 611 612 const Mapping& map = image_map.mapping; 613 614 // Handle the trivial case of an empty image_map. This means that there is 615 // no transformation to be applied, and we can simply return the original 616 // range. 617 if (map.empty()) { 618 mapped_ranges->push_back(original_range); 619 return; 620 } 621 622 // If we get a query of length 0 we need to handle it by using a non-zero 623 // query length. 624 AddressRange query_range(original_range); 625 if (query_range.length == 0) 626 query_range.length = 1; 627 628 // Find the range of intervals that can potentially intersect our query range. 629 size_t imin = 0; 630 size_t imax = 0; 631 { 632 // The index of the earliest possible range that can affect is us done by 633 // searching through the secondary indexing structure. 634 const EndpointIndexMap& eim = image_map.endpoint_index_map; 635 EndpointIndex q1 = { query_range.rva, 0 }; 636 EndpointIndexMap::const_iterator it1 = std::lower_bound( 637 eim.begin(), eim.end(), q1, EndpointIndexLess); 638 if (it1 == eim.end()) { 639 imin = map.size(); 640 } else { 641 // Backup to find the interval that contains our query point. 642 if (it1 != eim.begin() && query_range.rva < it1->endpoint) 643 --it1; 644 imin = it1->index; 645 } 646 647 // The first range that can't possibly intersect us is found by searching 648 // through the image map directly as it is already sorted by interval start 649 // point. 650 MappedRange q2 = { query_range.end(), 0 }; 651 Mapping::const_iterator it2 = std::lower_bound( 652 map.begin(), map.end(), q2, MappedRangeOriginalLess); 653 imax = it2 - map.begin(); 654 } 655 656 // Find all intervals that intersect the query range. 657 Mapping temp_map; 658 for (size_t i = imin; i < imax; ++i) { 659 MappedRange mr = map[i]; 660 ClipMappedRangeOriginal(query_range, &mr); 661 if (mr.length + mr.injected > 0) 662 temp_map.push_back(mr); 663 } 664 665 // If there are no intersecting ranges then the query range has been removed 666 // from the image in question. 667 if (temp_map.empty()) 668 return; 669 670 // Sort based on transformed addresses. 671 std::sort(temp_map.begin(), temp_map.end(), MappedRangeMappedLess); 672 673 // Zero-length queries can't actually be merged. We simply output the set of 674 // unique RVAs that correspond to the query RVA. 675 if (original_range.length == 0) { 676 mapped_ranges->push_back(AddressRange(temp_map[0].rva_transformed, 0)); 677 for (size_t i = 1; i < temp_map.size(); ++i) { 678 if (temp_map[i].rva_transformed > mapped_ranges->back().rva) 679 mapped_ranges->push_back(AddressRange(temp_map[i].rva_transformed, 0)); 680 } 681 return; 682 } 683 684 // Merge any ranges that are consecutive in the mapped image. We merge over 685 // injected content if it makes ranges contiguous, but we ignore any injected 686 // content at the tail end of a range. This allows us to detect symbols that 687 // have been lengthened by injecting content in the middle. However, it 688 // misses the case where content has been injected at the head or the tail. 689 // The problem is that it doesn't know whether to attribute it to the 690 // preceding or following symbol. It is up to the author of the transform to 691 // output explicit OMAP info in these cases to ensure full coverage of the 692 // transformed address space. 693 DWORD rva_begin = temp_map[0].rva_transformed; 694 DWORD rva_cur_content = rva_begin + temp_map[0].length; 695 DWORD rva_cur_injected = rva_cur_content + temp_map[0].injected; 696 for (size_t i = 1; i < temp_map.size(); ++i) { 697 if (rva_cur_injected < temp_map[i].rva_transformed) { 698 // This marks the end of a continuous range in the image. Output the 699 // current range and start a new one. 700 if (rva_begin < rva_cur_content) { 701 mapped_ranges->push_back( 702 AddressRange(rva_begin, rva_cur_content - rva_begin)); 703 } 704 rva_begin = temp_map[i].rva_transformed; 705 } 706 707 rva_cur_content = temp_map[i].rva_transformed + temp_map[i].length; 708 rva_cur_injected = rva_cur_content + temp_map[i].injected; 709 } 710 711 // Output the range in progress. 712 if (rva_begin < rva_cur_content) { 713 mapped_ranges->push_back( 714 AddressRange(rva_begin, rva_cur_content - rva_begin)); 715 } 716 717 return; 718 } 719 720 } // namespace google_breakpad