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