1 //===-- LibCxxMap.cpp -----------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "LibCxx.h" 10 11 #include "Plugins/TypeSystem/Clang/TypeSystemClang.h" 12 #include "lldb/Core/ValueObject.h" 13 #include "lldb/Core/ValueObjectConstResult.h" 14 #include "lldb/DataFormatters/FormattersHelpers.h" 15 #include "lldb/Target/Target.h" 16 #include "lldb/Utility/DataBufferHeap.h" 17 #include "lldb/Utility/Endian.h" 18 #include "lldb/Utility/Status.h" 19 #include "lldb/Utility/Stream.h" 20 #include "lldb/lldb-forward.h" 21 22 using namespace lldb; 23 using namespace lldb_private; 24 using namespace lldb_private::formatters; 25 26 class MapEntry { 27 public: 28 MapEntry() = default; 29 explicit MapEntry(ValueObjectSP entry_sp) : m_entry_sp(entry_sp) {} 30 explicit MapEntry(ValueObject *entry) 31 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 32 33 ValueObjectSP left() const { 34 if (!m_entry_sp) 35 return m_entry_sp; 36 return m_entry_sp->GetSyntheticChildAtOffset( 37 0, m_entry_sp->GetCompilerType(), true); 38 } 39 40 ValueObjectSP right() const { 41 if (!m_entry_sp) 42 return m_entry_sp; 43 return m_entry_sp->GetSyntheticChildAtOffset( 44 m_entry_sp->GetProcessSP()->GetAddressByteSize(), 45 m_entry_sp->GetCompilerType(), true); 46 } 47 48 ValueObjectSP parent() const { 49 if (!m_entry_sp) 50 return m_entry_sp; 51 return m_entry_sp->GetSyntheticChildAtOffset( 52 2 * m_entry_sp->GetProcessSP()->GetAddressByteSize(), 53 m_entry_sp->GetCompilerType(), true); 54 } 55 56 uint64_t value() const { 57 if (!m_entry_sp) 58 return 0; 59 return m_entry_sp->GetValueAsUnsigned(0); 60 } 61 62 bool error() const { 63 if (!m_entry_sp) 64 return true; 65 return m_entry_sp->GetError().Fail(); 66 } 67 68 bool null() const { return (value() == 0); } 69 70 ValueObjectSP GetEntry() const { return m_entry_sp; } 71 72 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 73 74 bool operator==(const MapEntry &rhs) const { 75 return (rhs.m_entry_sp.get() == m_entry_sp.get()); 76 } 77 78 private: 79 ValueObjectSP m_entry_sp; 80 }; 81 82 class MapIterator { 83 public: 84 MapIterator(ValueObject *entry, size_t depth = 0) 85 : m_entry(entry), m_max_depth(depth), m_error(false) {} 86 87 MapIterator() = default; 88 89 ValueObjectSP value() { return m_entry.GetEntry(); } 90 91 ValueObjectSP advance(size_t count) { 92 ValueObjectSP fail; 93 if (m_error) 94 return fail; 95 size_t steps = 0; 96 while (count > 0) { 97 next(); 98 count--, steps++; 99 if (m_error || m_entry.null() || (steps > m_max_depth)) 100 return fail; 101 } 102 return m_entry.GetEntry(); 103 } 104 105 private: 106 /// Mimicks libc++'s __tree_next algorithm, which libc++ uses 107 /// in its __tree_iteartor::operator++. 108 void next() { 109 if (m_entry.null()) 110 return; 111 MapEntry right(m_entry.right()); 112 if (!right.null()) { 113 m_entry = tree_min(std::move(right)); 114 return; 115 } 116 size_t steps = 0; 117 while (!is_left_child(m_entry)) { 118 if (m_entry.error()) { 119 m_error = true; 120 return; 121 } 122 m_entry.SetEntry(m_entry.parent()); 123 steps++; 124 if (steps > m_max_depth) { 125 m_entry = MapEntry(); 126 return; 127 } 128 } 129 m_entry = MapEntry(m_entry.parent()); 130 } 131 132 /// Mimicks libc++'s __tree_min algorithm. 133 MapEntry tree_min(MapEntry x) { 134 if (x.null()) 135 return MapEntry(); 136 MapEntry left(x.left()); 137 size_t steps = 0; 138 while (!left.null()) { 139 if (left.error()) { 140 m_error = true; 141 return MapEntry(); 142 } 143 x = left; 144 left.SetEntry(x.left()); 145 steps++; 146 if (steps > m_max_depth) 147 return MapEntry(); 148 } 149 return x; 150 } 151 152 bool is_left_child(const MapEntry &x) { 153 if (x.null()) 154 return false; 155 MapEntry rhs(x.parent()); 156 rhs.SetEntry(rhs.left()); 157 return x.value() == rhs.value(); 158 } 159 160 MapEntry m_entry; 161 size_t m_max_depth = 0; 162 bool m_error = false; 163 }; 164 165 namespace lldb_private { 166 namespace formatters { 167 class LibcxxStdMapSyntheticFrontEnd : public SyntheticChildrenFrontEnd { 168 public: 169 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 170 171 ~LibcxxStdMapSyntheticFrontEnd() override = default; 172 173 llvm::Expected<uint32_t> CalculateNumChildren() override; 174 175 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override; 176 177 lldb::ChildCacheState Update() override; 178 179 bool MightHaveChildren() override; 180 181 size_t GetIndexOfChildWithName(ConstString name) override; 182 183 private: 184 bool GetDataType(); 185 186 void GetValueOffset(const lldb::ValueObjectSP &node); 187 188 /// Returns the ValueObject for the __tree_node type that 189 /// holds the key/value pair of the node at index \ref idx. 190 /// 191 /// \param[in] idx The child index that we're looking to get 192 /// the key/value pair for. 193 /// 194 /// \param[in] max_depth The maximum search depth after which 195 /// we stop trying to find the key/value 196 /// pair for. 197 /// 198 /// \returns On success, returns the ValueObjectSP corresponding 199 /// to the __tree_node's __value_ member (which holds 200 /// the key/value pair the formatter wants to display). 201 /// On failure, will return nullptr. 202 ValueObjectSP GetKeyValuePair(size_t idx, size_t max_depth); 203 204 ValueObject *m_tree = nullptr; 205 ValueObject *m_root_node = nullptr; 206 CompilerType m_element_type; 207 uint32_t m_skip_size = UINT32_MAX; 208 size_t m_count = UINT32_MAX; 209 std::map<size_t, MapIterator> m_iterators; 210 }; 211 212 class LibCxxMapIteratorSyntheticFrontEnd : public SyntheticChildrenFrontEnd { 213 public: 214 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp); 215 216 llvm::Expected<uint32_t> CalculateNumChildren() override; 217 218 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override; 219 220 lldb::ChildCacheState Update() override; 221 222 bool MightHaveChildren() override; 223 224 size_t GetIndexOfChildWithName(ConstString name) override; 225 226 ~LibCxxMapIteratorSyntheticFrontEnd() override; 227 228 private: 229 ValueObject *m_pair_ptr; 230 lldb::ValueObjectSP m_pair_sp; 231 }; 232 } // namespace formatters 233 } // namespace lldb_private 234 235 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 236 LibcxxStdMapSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 237 : SyntheticChildrenFrontEnd(*valobj_sp), m_element_type(), m_iterators() { 238 if (valobj_sp) 239 Update(); 240 } 241 242 llvm::Expected<uint32_t> lldb_private::formatters:: 243 LibcxxStdMapSyntheticFrontEnd::CalculateNumChildren() { 244 if (m_count != UINT32_MAX) 245 return m_count; 246 247 if (m_tree == nullptr) 248 return 0; 249 250 ValueObjectSP size_node(m_tree->GetChildMemberWithName("__pair3_")); 251 if (!size_node) 252 return 0; 253 254 size_node = GetFirstValueOfLibCXXCompressedPair(*size_node); 255 256 if (!size_node) 257 return 0; 258 259 m_count = size_node->GetValueAsUnsigned(0); 260 return m_count; 261 } 262 263 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetDataType() { 264 if (m_element_type.IsValid()) 265 return true; 266 m_element_type.Clear(); 267 ValueObjectSP deref; 268 Status error; 269 deref = m_root_node->Dereference(error); 270 if (!deref || error.Fail()) 271 return false; 272 deref = m_backend.GetChildAtNamePath({"__tree_", "__pair3_"}); 273 if (!deref) 274 return false; 275 m_element_type = deref->GetCompilerType() 276 .GetTypeTemplateArgument(1) 277 .GetTypeTemplateArgument(1); 278 if (m_element_type) { 279 std::string name; 280 uint64_t bit_offset_ptr; 281 uint32_t bitfield_bit_size_ptr; 282 bool is_bitfield_ptr; 283 m_element_type = m_element_type.GetFieldAtIndex( 284 0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr); 285 m_element_type = m_element_type.GetTypedefedType(); 286 return m_element_type.IsValid(); 287 } else { 288 m_element_type = m_backend.GetCompilerType().GetTypeTemplateArgument(0); 289 return m_element_type.IsValid(); 290 } 291 } 292 293 void lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetValueOffset( 294 const lldb::ValueObjectSP &node) { 295 if (m_skip_size != UINT32_MAX) 296 return; 297 if (!node) 298 return; 299 300 CompilerType node_type(node->GetCompilerType()); 301 auto ast_ctx = node_type.GetTypeSystem().dyn_cast_or_null<TypeSystemClang>(); 302 if (!ast_ctx) 303 return; 304 305 CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier( 306 llvm::StringRef(), 307 {{"ptr0", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 308 {"ptr1", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 309 {"ptr2", ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 310 {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)}, 311 {"payload", (m_element_type.GetCompleteType(), m_element_type)}}); 312 std::string child_name; 313 uint32_t child_byte_size; 314 int32_t child_byte_offset = 0; 315 uint32_t child_bitfield_bit_size; 316 uint32_t child_bitfield_bit_offset; 317 bool child_is_base_class; 318 bool child_is_deref_of_parent; 319 uint64_t language_flags; 320 auto child_type = 321 llvm::expectedToStdOptional(tree_node_type.GetChildCompilerTypeAtIndex( 322 nullptr, 4, true, true, true, child_name, child_byte_size, 323 child_byte_offset, child_bitfield_bit_size, child_bitfield_bit_offset, 324 child_is_base_class, child_is_deref_of_parent, nullptr, 325 language_flags)); 326 if (child_type && child_type->IsValid()) 327 m_skip_size = (uint32_t)child_byte_offset; 328 } 329 330 ValueObjectSP 331 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetKeyValuePair( 332 size_t idx, size_t max_depth) { 333 MapIterator iterator(m_root_node, max_depth); 334 335 const bool need_to_skip = (idx > 0); 336 size_t actual_advance = idx; 337 if (need_to_skip) { 338 // If we have already created the iterator for the previous 339 // index, we can start from there and advance by 1. 340 auto cached_iterator = m_iterators.find(idx - 1); 341 if (cached_iterator != m_iterators.end()) { 342 iterator = cached_iterator->second; 343 actual_advance = 1; 344 } 345 } 346 347 ValueObjectSP iterated_sp(iterator.advance(actual_advance)); 348 if (!iterated_sp) 349 // this tree is garbage - stop 350 return nullptr; 351 352 if (!GetDataType()) 353 return nullptr; 354 355 if (!need_to_skip) { 356 Status error; 357 iterated_sp = iterated_sp->Dereference(error); 358 if (!iterated_sp || error.Fail()) 359 return nullptr; 360 361 GetValueOffset(iterated_sp); 362 iterated_sp = iterated_sp->GetSyntheticChildAtOffset(m_skip_size, 363 m_element_type, true); 364 365 if (!iterated_sp) 366 return nullptr; 367 } else { 368 // because of the way our debug info is made, we need to read item 0 369 // first so that we can cache information used to generate other elements 370 if (m_skip_size == UINT32_MAX) 371 GetChildAtIndex(0); 372 373 if (m_skip_size == UINT32_MAX) 374 return nullptr; 375 376 iterated_sp = iterated_sp->GetSyntheticChildAtOffset(m_skip_size, 377 m_element_type, true); 378 if (!iterated_sp) 379 return nullptr; 380 } 381 382 m_iterators[idx] = iterator; 383 assert(iterated_sp != nullptr && 384 "Cached MapIterator for invalid ValueObject"); 385 386 return iterated_sp; 387 } 388 389 lldb::ValueObjectSP 390 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::GetChildAtIndex( 391 uint32_t idx) { 392 static ConstString g_cc_("__cc_"), g_cc("__cc"); 393 static ConstString g_nc("__nc"); 394 uint32_t num_children = CalculateNumChildrenIgnoringErrors(); 395 if (idx >= num_children) 396 return nullptr; 397 398 if (m_tree == nullptr || m_root_node == nullptr) 399 return nullptr; 400 401 ValueObjectSP key_val_sp = GetKeyValuePair(idx, /*max_depth=*/num_children); 402 if (!key_val_sp) { 403 // this will stop all future searches until an Update() happens 404 m_tree = nullptr; 405 return nullptr; 406 } 407 408 // at this point we have a valid 409 // we need to copy current_sp into a new object otherwise we will end up with 410 // all items named __value_ 411 StreamString name; 412 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 413 auto potential_child_sp = key_val_sp->Clone(ConstString(name.GetString())); 414 if (potential_child_sp) { 415 switch (potential_child_sp->GetNumChildrenIgnoringErrors()) { 416 case 1: { 417 auto child0_sp = potential_child_sp->GetChildAtIndex(0); 418 if (child0_sp && 419 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc)) 420 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 421 break; 422 } 423 case 2: { 424 auto child0_sp = potential_child_sp->GetChildAtIndex(0); 425 auto child1_sp = potential_child_sp->GetChildAtIndex(1); 426 if (child0_sp && 427 (child0_sp->GetName() == g_cc_ || child0_sp->GetName() == g_cc) && 428 child1_sp && child1_sp->GetName() == g_nc) 429 potential_child_sp = child0_sp->Clone(ConstString(name.GetString())); 430 break; 431 } 432 } 433 } 434 return potential_child_sp; 435 } 436 437 lldb::ChildCacheState 438 lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd::Update() { 439 m_count = UINT32_MAX; 440 m_tree = m_root_node = nullptr; 441 m_iterators.clear(); 442 m_tree = m_backend.GetChildMemberWithName("__tree_").get(); 443 if (!m_tree) 444 return lldb::ChildCacheState::eRefetch; 445 m_root_node = m_tree->GetChildMemberWithName("__begin_node_").get(); 446 return lldb::ChildCacheState::eRefetch; 447 } 448 449 bool lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 450 MightHaveChildren() { 451 return true; 452 } 453 454 size_t lldb_private::formatters::LibcxxStdMapSyntheticFrontEnd:: 455 GetIndexOfChildWithName(ConstString name) { 456 return ExtractIndexFromString(name.GetCString()); 457 } 458 459 SyntheticChildrenFrontEnd * 460 lldb_private::formatters::LibcxxStdMapSyntheticFrontEndCreator( 461 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 462 return (valobj_sp ? new LibcxxStdMapSyntheticFrontEnd(valobj_sp) : nullptr); 463 } 464 465 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: 466 LibCxxMapIteratorSyntheticFrontEnd(lldb::ValueObjectSP valobj_sp) 467 : SyntheticChildrenFrontEnd(*valobj_sp), m_pair_ptr(), m_pair_sp() { 468 if (valobj_sp) 469 Update(); 470 } 471 472 lldb::ChildCacheState 473 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::Update() { 474 m_pair_sp.reset(); 475 m_pair_ptr = nullptr; 476 477 ValueObjectSP valobj_sp = m_backend.GetSP(); 478 if (!valobj_sp) 479 return lldb::ChildCacheState::eRefetch; 480 481 TargetSP target_sp(valobj_sp->GetTargetSP()); 482 483 if (!target_sp) 484 return lldb::ChildCacheState::eRefetch; 485 486 // this must be a ValueObject* because it is a child of the ValueObject we 487 // are producing children for it if were a ValueObjectSP, we would end up 488 // with a loop (iterator -> synthetic -> child -> parent == iterator) and 489 // that would in turn leak memory by never allowing the ValueObjects to die 490 // and free their memory 491 m_pair_ptr = valobj_sp 492 ->GetValueForExpressionPath( 493 ".__i_.__ptr_->__value_", nullptr, nullptr, 494 ValueObject::GetValueForExpressionPathOptions() 495 .DontCheckDotVsArrowSyntax() 496 .SetSyntheticChildrenTraversal( 497 ValueObject::GetValueForExpressionPathOptions:: 498 SyntheticChildrenTraversal::None), 499 nullptr) 500 .get(); 501 502 if (!m_pair_ptr) { 503 m_pair_ptr = valobj_sp 504 ->GetValueForExpressionPath( 505 ".__i_.__ptr_", nullptr, nullptr, 506 ValueObject::GetValueForExpressionPathOptions() 507 .DontCheckDotVsArrowSyntax() 508 .SetSyntheticChildrenTraversal( 509 ValueObject::GetValueForExpressionPathOptions:: 510 SyntheticChildrenTraversal::None), 511 nullptr) 512 .get(); 513 if (m_pair_ptr) { 514 auto __i_(valobj_sp->GetChildMemberWithName("__i_")); 515 if (!__i_) { 516 m_pair_ptr = nullptr; 517 return lldb::ChildCacheState::eRefetch; 518 } 519 CompilerType pair_type( 520 __i_->GetCompilerType().GetTypeTemplateArgument(0)); 521 std::string name; 522 uint64_t bit_offset_ptr; 523 uint32_t bitfield_bit_size_ptr; 524 bool is_bitfield_ptr; 525 pair_type = pair_type.GetFieldAtIndex( 526 0, name, &bit_offset_ptr, &bitfield_bit_size_ptr, &is_bitfield_ptr); 527 if (!pair_type) { 528 m_pair_ptr = nullptr; 529 return lldb::ChildCacheState::eRefetch; 530 } 531 532 auto addr(m_pair_ptr->GetValueAsUnsigned(LLDB_INVALID_ADDRESS)); 533 m_pair_ptr = nullptr; 534 if (addr && addr != LLDB_INVALID_ADDRESS) { 535 auto ts = pair_type.GetTypeSystem(); 536 auto ast_ctx = ts.dyn_cast_or_null<TypeSystemClang>(); 537 if (!ast_ctx) 538 return lldb::ChildCacheState::eRefetch; 539 540 // Mimick layout of std::__tree_iterator::__ptr_ and read it in 541 // from process memory. 542 // 543 // The following shows the contiguous block of memory: 544 // 545 // +-----------------------------+ class __tree_end_node 546 // __ptr_ | pointer __left_; | 547 // +-----------------------------+ class __tree_node_base 548 // | pointer __right_; | 549 // | __parent_pointer __parent_; | 550 // | bool __is_black_; | 551 // +-----------------------------+ class __tree_node 552 // | __node_value_type __value_; | <<< our key/value pair 553 // +-----------------------------+ 554 // 555 CompilerType tree_node_type = ast_ctx->CreateStructForIdentifier( 556 llvm::StringRef(), 557 {{"ptr0", 558 ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 559 {"ptr1", 560 ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 561 {"ptr2", 562 ast_ctx->GetBasicType(lldb::eBasicTypeVoid).GetPointerType()}, 563 {"cw", ast_ctx->GetBasicType(lldb::eBasicTypeBool)}, 564 {"payload", pair_type}}); 565 std::optional<uint64_t> size = tree_node_type.GetByteSize(nullptr); 566 if (!size) 567 return lldb::ChildCacheState::eRefetch; 568 WritableDataBufferSP buffer_sp(new DataBufferHeap(*size, 0)); 569 ProcessSP process_sp(target_sp->GetProcessSP()); 570 Status error; 571 process_sp->ReadMemory(addr, buffer_sp->GetBytes(), 572 buffer_sp->GetByteSize(), error); 573 if (error.Fail()) 574 return lldb::ChildCacheState::eRefetch; 575 DataExtractor extractor(buffer_sp, process_sp->GetByteOrder(), 576 process_sp->GetAddressByteSize()); 577 auto pair_sp = CreateValueObjectFromData( 578 "pair", extractor, valobj_sp->GetExecutionContextRef(), 579 tree_node_type); 580 if (pair_sp) 581 m_pair_sp = pair_sp->GetChildAtIndex(4); 582 } 583 } 584 } 585 586 return lldb::ChildCacheState::eRefetch; 587 } 588 589 llvm::Expected<uint32_t> lldb_private::formatters:: 590 LibCxxMapIteratorSyntheticFrontEnd::CalculateNumChildren() { 591 return 2; 592 } 593 594 lldb::ValueObjectSP 595 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd::GetChildAtIndex( 596 uint32_t idx) { 597 if (m_pair_ptr) 598 return m_pair_ptr->GetChildAtIndex(idx); 599 if (m_pair_sp) 600 return m_pair_sp->GetChildAtIndex(idx); 601 return lldb::ValueObjectSP(); 602 } 603 604 bool lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: 605 MightHaveChildren() { 606 return true; 607 } 608 609 size_t lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: 610 GetIndexOfChildWithName(ConstString name) { 611 if (name == "first") 612 return 0; 613 if (name == "second") 614 return 1; 615 return UINT32_MAX; 616 } 617 618 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEnd:: 619 ~LibCxxMapIteratorSyntheticFrontEnd() { 620 // this will be deleted when its parent dies (since it's a child object) 621 // delete m_pair_ptr; 622 } 623 624 SyntheticChildrenFrontEnd * 625 lldb_private::formatters::LibCxxMapIteratorSyntheticFrontEndCreator( 626 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 627 return (valobj_sp ? new LibCxxMapIteratorSyntheticFrontEnd(valobj_sp) 628 : nullptr); 629 } 630