1 //===-- LibCxxList.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/DataFormatters/FormattersHelpers.h" 13 #include "lldb/Target/Target.h" 14 #include "lldb/Utility/DataBufferHeap.h" 15 #include "lldb/Utility/Endian.h" 16 #include "lldb/Utility/Status.h" 17 #include "lldb/Utility/Stream.h" 18 #include "lldb/ValueObject/ValueObject.h" 19 #include "lldb/ValueObject/ValueObjectConstResult.h" 20 #include "lldb/lldb-enumerations.h" 21 22 using namespace lldb; 23 using namespace lldb_private; 24 using namespace lldb_private::formatters; 25 26 namespace { 27 28 class ListEntry { 29 public: 30 ListEntry() = default; 31 ListEntry(ValueObjectSP entry_sp) : m_entry_sp(std::move(entry_sp)) {} 32 ListEntry(ValueObject *entry) 33 : m_entry_sp(entry ? entry->GetSP() : ValueObjectSP()) {} 34 35 ListEntry next() { 36 if (!m_entry_sp) 37 return ListEntry(); 38 return ListEntry(m_entry_sp->GetChildMemberWithName("__next_")); 39 } 40 41 ListEntry prev() { 42 if (!m_entry_sp) 43 return ListEntry(); 44 return ListEntry(m_entry_sp->GetChildMemberWithName("__prev_")); 45 } 46 47 uint64_t value() const { 48 if (!m_entry_sp) 49 return 0; 50 return m_entry_sp->GetValueAsUnsigned(0); 51 } 52 53 bool null() { return (value() == 0); } 54 55 explicit operator bool() { return GetEntry() && !null(); } 56 57 ValueObjectSP GetEntry() { return m_entry_sp; } 58 59 void SetEntry(ValueObjectSP entry) { m_entry_sp = entry; } 60 61 bool operator==(const ListEntry &rhs) const { return value() == rhs.value(); } 62 63 bool operator!=(const ListEntry &rhs) const { return !(*this == rhs); } 64 65 private: 66 ValueObjectSP m_entry_sp; 67 }; 68 69 class ListIterator { 70 public: 71 ListIterator() = default; 72 ListIterator(ListEntry entry) : m_entry(std::move(entry)) {} 73 ListIterator(ValueObjectSP entry) : m_entry(std::move(entry)) {} 74 ListIterator(ValueObject *entry) : m_entry(entry) {} 75 76 ValueObjectSP value() { return m_entry.GetEntry(); } 77 78 ValueObjectSP advance(size_t count) { 79 if (count == 0) 80 return m_entry.GetEntry(); 81 if (count == 1) { 82 next(); 83 return m_entry.GetEntry(); 84 } 85 while (count > 0) { 86 next(); 87 count--; 88 if (m_entry.null()) 89 return lldb::ValueObjectSP(); 90 } 91 return m_entry.GetEntry(); 92 } 93 94 bool operator==(const ListIterator &rhs) const { 95 return (rhs.m_entry == m_entry); 96 } 97 98 protected: 99 void next() { m_entry = m_entry.next(); } 100 101 void prev() { m_entry = m_entry.prev(); } 102 103 private: 104 ListEntry m_entry; 105 }; 106 107 class AbstractListFrontEnd : public SyntheticChildrenFrontEnd { 108 public: 109 size_t GetIndexOfChildWithName(ConstString name) override { 110 return ExtractIndexFromString(name.GetCString()); 111 } 112 bool MightHaveChildren() override { return true; } 113 lldb::ChildCacheState Update() override; 114 115 protected: 116 AbstractListFrontEnd(ValueObject &valobj) 117 : SyntheticChildrenFrontEnd(valobj) {} 118 119 size_t m_count = 0; 120 ValueObject *m_head = nullptr; 121 122 static constexpr bool g_use_loop_detect = true; 123 size_t m_loop_detected = 0; // The number of elements that have had loop 124 // detection run over them. 125 ListEntry m_slow_runner; // Used for loop detection 126 ListEntry m_fast_runner; // Used for loop detection 127 128 size_t m_list_capping_size = 0; 129 CompilerType m_element_type; 130 std::map<size_t, ListIterator> m_iterators; 131 132 bool HasLoop(size_t count); 133 ValueObjectSP GetItem(size_t idx); 134 }; 135 136 class ForwardListFrontEnd : public AbstractListFrontEnd { 137 public: 138 ForwardListFrontEnd(ValueObject &valobj); 139 140 llvm::Expected<uint32_t> CalculateNumChildren() override; 141 ValueObjectSP GetChildAtIndex(uint32_t idx) override; 142 lldb::ChildCacheState Update() override; 143 }; 144 145 class ListFrontEnd : public AbstractListFrontEnd { 146 public: 147 ListFrontEnd(lldb::ValueObjectSP valobj_sp); 148 149 ~ListFrontEnd() override = default; 150 151 llvm::Expected<uint32_t> CalculateNumChildren() override; 152 153 lldb::ValueObjectSP GetChildAtIndex(uint32_t idx) override; 154 155 lldb::ChildCacheState Update() override; 156 157 private: 158 lldb::addr_t m_node_address = 0; 159 ValueObject *m_tail = nullptr; 160 }; 161 162 } // end anonymous namespace 163 164 lldb::ChildCacheState AbstractListFrontEnd::Update() { 165 m_loop_detected = 0; 166 m_count = UINT32_MAX; 167 m_head = nullptr; 168 m_list_capping_size = 0; 169 m_slow_runner.SetEntry(nullptr); 170 m_fast_runner.SetEntry(nullptr); 171 m_iterators.clear(); 172 173 if (m_backend.GetTargetSP()) 174 m_list_capping_size = 175 m_backend.GetTargetSP()->GetMaximumNumberOfChildrenToDisplay(); 176 if (m_list_capping_size == 0) 177 m_list_capping_size = 255; 178 179 CompilerType list_type = m_backend.GetCompilerType(); 180 if (list_type.IsReferenceType()) 181 list_type = list_type.GetNonReferenceType(); 182 183 if (list_type.GetNumTemplateArguments() == 0) 184 return lldb::ChildCacheState::eRefetch; 185 m_element_type = list_type.GetTypeTemplateArgument(0); 186 187 return lldb::ChildCacheState::eRefetch; 188 } 189 190 bool AbstractListFrontEnd::HasLoop(size_t count) { 191 if (!g_use_loop_detect) 192 return false; 193 // don't bother checking for a loop if we won't actually need to jump nodes 194 if (m_count < 2) 195 return false; 196 197 if (m_loop_detected == 0) { 198 // This is the first time we are being run (after the last update). Set up 199 // the loop invariant for the first element. 200 m_slow_runner = ListEntry(m_head).next(); 201 m_fast_runner = m_slow_runner.next(); 202 m_loop_detected = 1; 203 } 204 205 // Loop invariant: 206 // Loop detection has been run over the first m_loop_detected elements. If 207 // m_slow_runner == m_fast_runner then the loop has been detected after 208 // m_loop_detected elements. 209 const size_t steps_to_run = std::min(count, m_count); 210 while (m_loop_detected < steps_to_run && m_slow_runner && m_fast_runner && 211 m_slow_runner != m_fast_runner) { 212 213 m_slow_runner = m_slow_runner.next(); 214 m_fast_runner = m_fast_runner.next().next(); 215 m_loop_detected++; 216 } 217 if (count <= m_loop_detected) 218 return false; // No loop in the first m_loop_detected elements. 219 if (!m_slow_runner || !m_fast_runner) 220 return false; // Reached the end of the list. Definitely no loops. 221 return m_slow_runner == m_fast_runner; 222 } 223 224 ValueObjectSP AbstractListFrontEnd::GetItem(size_t idx) { 225 size_t advance = idx; 226 ListIterator current(m_head); 227 if (idx > 0) { 228 auto cached_iterator = m_iterators.find(idx - 1); 229 if (cached_iterator != m_iterators.end()) { 230 current = cached_iterator->second; 231 advance = 1; 232 } 233 } 234 ValueObjectSP value_sp = current.advance(advance); 235 m_iterators[idx] = current; 236 return value_sp; 237 } 238 239 ForwardListFrontEnd::ForwardListFrontEnd(ValueObject &valobj) 240 : AbstractListFrontEnd(valobj) { 241 Update(); 242 } 243 244 llvm::Expected<uint32_t> ForwardListFrontEnd::CalculateNumChildren() { 245 if (m_count != UINT32_MAX) 246 return m_count; 247 248 ListEntry current(m_head); 249 m_count = 0; 250 while (current && m_count < m_list_capping_size) { 251 ++m_count; 252 current = current.next(); 253 } 254 return m_count; 255 } 256 257 ValueObjectSP ForwardListFrontEnd::GetChildAtIndex(uint32_t idx) { 258 if (idx >= CalculateNumChildrenIgnoringErrors()) 259 return nullptr; 260 261 if (!m_head) 262 return nullptr; 263 264 if (HasLoop(idx + 1)) 265 return nullptr; 266 267 ValueObjectSP current_sp = GetItem(idx); 268 if (!current_sp) 269 return nullptr; 270 271 current_sp = current_sp->GetChildAtIndex(1); // get the __value_ child 272 if (!current_sp) 273 return nullptr; 274 275 // we need to copy current_sp into a new object otherwise we will end up with 276 // all items named __value_ 277 DataExtractor data; 278 Status error; 279 current_sp->GetData(data, error); 280 if (error.Fail()) 281 return nullptr; 282 283 return CreateValueObjectFromData(llvm::formatv("[{0}]", idx).str(), data, 284 m_backend.GetExecutionContextRef(), 285 m_element_type); 286 } 287 288 lldb::ChildCacheState ForwardListFrontEnd::Update() { 289 AbstractListFrontEnd::Update(); 290 291 Status err; 292 ValueObjectSP backend_addr(m_backend.AddressOf(err)); 293 if (err.Fail() || !backend_addr) 294 return lldb::ChildCacheState::eRefetch; 295 296 ValueObjectSP impl_sp(m_backend.GetChildMemberWithName("__before_begin_")); 297 if (!impl_sp) 298 return ChildCacheState::eRefetch; 299 300 if (isOldCompressedPairLayout(*impl_sp)) 301 impl_sp = GetFirstValueOfLibCXXCompressedPair(*impl_sp); 302 303 if (!impl_sp) 304 return ChildCacheState::eRefetch; 305 306 m_head = impl_sp->GetChildMemberWithName("__next_").get(); 307 308 return ChildCacheState::eRefetch; 309 } 310 311 ListFrontEnd::ListFrontEnd(lldb::ValueObjectSP valobj_sp) 312 : AbstractListFrontEnd(*valobj_sp) { 313 if (valobj_sp) 314 Update(); 315 } 316 317 llvm::Expected<uint32_t> ListFrontEnd::CalculateNumChildren() { 318 if (m_count != UINT32_MAX) 319 return m_count; 320 if (!m_head || !m_tail || m_node_address == 0) 321 return 0; 322 323 ValueObjectSP size_node_sp(m_backend.GetChildMemberWithName("__size_")); 324 if (!size_node_sp) { 325 size_node_sp = m_backend.GetChildMemberWithName( 326 "__size_alloc_"); // pre-compressed_pair rework 327 328 if (!isOldCompressedPairLayout(*size_node_sp)) 329 return llvm::createStringError("Unexpected std::list layout: expected " 330 "old __compressed_pair layout."); 331 332 size_node_sp = GetFirstValueOfLibCXXCompressedPair(*size_node_sp); 333 } 334 335 if (size_node_sp) 336 m_count = size_node_sp->GetValueAsUnsigned(UINT32_MAX); 337 338 if (m_count != UINT32_MAX) 339 return m_count; 340 341 uint64_t next_val = m_head->GetValueAsUnsigned(0); 342 uint64_t prev_val = m_tail->GetValueAsUnsigned(0); 343 if (next_val == 0 || prev_val == 0) 344 return 0; 345 if (next_val == m_node_address) 346 return 0; 347 if (next_val == prev_val) 348 return 1; 349 uint64_t size = 2; 350 ListEntry current(m_head); 351 while (current.next() && current.next().value() != m_node_address) { 352 size++; 353 current = current.next(); 354 if (size > m_list_capping_size) 355 break; 356 } 357 return m_count = (size - 1); 358 } 359 360 lldb::ValueObjectSP ListFrontEnd::GetChildAtIndex(uint32_t idx) { 361 static ConstString g_value("__value_"); 362 static ConstString g_next("__next_"); 363 364 if (idx >= CalculateNumChildrenIgnoringErrors()) 365 return lldb::ValueObjectSP(); 366 367 if (!m_head || !m_tail || m_node_address == 0) 368 return lldb::ValueObjectSP(); 369 370 if (HasLoop(idx + 1)) 371 return lldb::ValueObjectSP(); 372 373 ValueObjectSP current_sp = GetItem(idx); 374 if (!current_sp) 375 return lldb::ValueObjectSP(); 376 377 current_sp = current_sp->GetChildAtIndex(1); // get the __value_ child 378 if (!current_sp) 379 return lldb::ValueObjectSP(); 380 381 if (current_sp->GetName() == g_next) { 382 ProcessSP process_sp(current_sp->GetProcessSP()); 383 if (!process_sp) 384 return lldb::ValueObjectSP(); 385 386 // if we grabbed the __next_ pointer, then the child is one pointer deep-er 387 lldb::addr_t addr = current_sp->GetParent()->GetPointerValue(); 388 addr = addr + 2 * process_sp->GetAddressByteSize(); 389 ExecutionContext exe_ctx(process_sp); 390 current_sp = 391 CreateValueObjectFromAddress("__value_", addr, exe_ctx, m_element_type); 392 if (!current_sp) 393 return lldb::ValueObjectSP(); 394 } 395 396 // we need to copy current_sp into a new object otherwise we will end up with 397 // all items named __value_ 398 DataExtractor data; 399 Status error; 400 current_sp->GetData(data, error); 401 if (error.Fail()) 402 return lldb::ValueObjectSP(); 403 404 StreamString name; 405 name.Printf("[%" PRIu64 "]", (uint64_t)idx); 406 return CreateValueObjectFromData(name.GetString(), data, 407 m_backend.GetExecutionContextRef(), 408 m_element_type); 409 } 410 411 lldb::ChildCacheState ListFrontEnd::Update() { 412 AbstractListFrontEnd::Update(); 413 m_tail = nullptr; 414 m_node_address = 0; 415 416 Status err; 417 ValueObjectSP backend_addr(m_backend.AddressOf(err)); 418 if (err.Fail() || !backend_addr) 419 return lldb::ChildCacheState::eRefetch; 420 m_node_address = backend_addr->GetValueAsUnsigned(0); 421 if (!m_node_address || m_node_address == LLDB_INVALID_ADDRESS) 422 return lldb::ChildCacheState::eRefetch; 423 ValueObjectSP impl_sp(m_backend.GetChildMemberWithName("__end_")); 424 if (!impl_sp) 425 return lldb::ChildCacheState::eRefetch; 426 m_head = impl_sp->GetChildMemberWithName("__next_").get(); 427 m_tail = impl_sp->GetChildMemberWithName("__prev_").get(); 428 return lldb::ChildCacheState::eRefetch; 429 } 430 431 SyntheticChildrenFrontEnd *formatters::LibcxxStdListSyntheticFrontEndCreator( 432 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 433 return (valobj_sp ? new ListFrontEnd(valobj_sp) : nullptr); 434 } 435 436 SyntheticChildrenFrontEnd * 437 formatters::LibcxxStdForwardListSyntheticFrontEndCreator( 438 CXXSyntheticChildren *, lldb::ValueObjectSP valobj_sp) { 439 return valobj_sp ? new ForwardListFrontEnd(*valobj_sp) : nullptr; 440 } 441