1 //===-- BreakpointResolver.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 "lldb/Breakpoint/BreakpointResolver.h"
10 
11 #include "lldb/Breakpoint/Breakpoint.h"
12 #include "lldb/Breakpoint/BreakpointLocation.h"
13 // Have to include the other breakpoint resolver types here so the static
14 // create from StructuredData can call them.
15 #include "lldb/Breakpoint/BreakpointResolverAddress.h"
16 #include "lldb/Breakpoint/BreakpointResolverFileLine.h"
17 #include "lldb/Breakpoint/BreakpointResolverFileRegex.h"
18 #include "lldb/Breakpoint/BreakpointResolverName.h"
19 #include "lldb/Breakpoint/BreakpointResolverScripted.h"
20 #include "lldb/Core/Address.h"
21 #include "lldb/Core/ModuleList.h"
22 #include "lldb/Core/SearchFilter.h"
23 #include "lldb/Symbol/CompileUnit.h"
24 #include "lldb/Symbol/Function.h"
25 #include "lldb/Symbol/SymbolContext.h"
26 #include "lldb/Target/Target.h"
27 #include "lldb/Utility/LLDBLog.h"
28 #include "lldb/Utility/Log.h"
29 #include "lldb/Utility/Stream.h"
30 #include "lldb/Utility/StreamString.h"
31 #include <optional>
32 
33 using namespace lldb_private;
34 using namespace lldb;
35 
36 // BreakpointResolver:
37 const char *BreakpointResolver::g_ty_to_name[] = {"FileAndLine", "Address",
38                                                   "SymbolName",  "SourceRegex",
39                                                   "Python",   "Exception",
40                                                   "Unknown"};
41 
42 const char *BreakpointResolver::g_option_names[static_cast<uint32_t>(
43     BreakpointResolver::OptionNames::LastOptionName)] = {
44     "AddressOffset", "Exact",     "FileName",     "Inlines",     "Language",
45     "LineNumber",    "Column",    "ModuleName",   "NameMask",    "Offset",
46     "PythonClass",   "Regex",     "ScriptArgs",   "SectionName", "SearchDepth",
47     "SkipPrologue",  "SymbolNames"};
48 
49 const char *BreakpointResolver::ResolverTyToName(enum ResolverTy type) {
50   if (type > LastKnownResolverType)
51     return g_ty_to_name[UnknownResolver];
52 
53   return g_ty_to_name[type];
54 }
55 
56 BreakpointResolver::ResolverTy
57 BreakpointResolver::NameToResolverTy(llvm::StringRef name) {
58   for (size_t i = 0; i < LastKnownResolverType; i++) {
59     if (name == g_ty_to_name[i])
60       return (ResolverTy)i;
61   }
62   return UnknownResolver;
63 }
64 
65 BreakpointResolver::BreakpointResolver(const BreakpointSP &bkpt,
66                                        const unsigned char resolverTy,
67                                        lldb::addr_t offset)
68     : m_breakpoint(bkpt), m_offset(offset), SubclassID(resolverTy) {}
69 
70 BreakpointResolver::~BreakpointResolver() = default;
71 
72 BreakpointResolverSP BreakpointResolver::CreateFromStructuredData(
73     const StructuredData::Dictionary &resolver_dict, Status &error) {
74   BreakpointResolverSP result_sp;
75   if (!resolver_dict.IsValid()) {
76     error.SetErrorString("Can't deserialize from an invalid data object.");
77     return result_sp;
78   }
79 
80   llvm::StringRef subclass_name;
81 
82   bool success = resolver_dict.GetValueForKeyAsString(
83       GetSerializationSubclassKey(), subclass_name);
84 
85   if (!success) {
86     error.SetErrorString("Resolver data missing subclass resolver key");
87     return result_sp;
88   }
89 
90   ResolverTy resolver_type = NameToResolverTy(subclass_name);
91   if (resolver_type == UnknownResolver) {
92     error.SetErrorStringWithFormatv("Unknown resolver type: {0}.",
93                                     subclass_name);
94     return result_sp;
95   }
96 
97   StructuredData::Dictionary *subclass_options = nullptr;
98   success = resolver_dict.GetValueForKeyAsDictionary(
99       GetSerializationSubclassOptionsKey(), subclass_options);
100   if (!success || !subclass_options || !subclass_options->IsValid()) {
101     error.SetErrorString("Resolver data missing subclass options key.");
102     return result_sp;
103   }
104 
105   lldb::offset_t offset;
106   success = subclass_options->GetValueForKeyAsInteger(
107       GetKey(OptionNames::Offset), offset);
108   if (!success) {
109     error.SetErrorString("Resolver data missing offset options key.");
110     return result_sp;
111   }
112 
113   switch (resolver_type) {
114   case FileLineResolver:
115     result_sp = BreakpointResolverFileLine::CreateFromStructuredData(
116         *subclass_options, error);
117     break;
118   case AddressResolver:
119     result_sp = BreakpointResolverAddress::CreateFromStructuredData(
120         *subclass_options, error);
121     break;
122   case NameResolver:
123     result_sp = BreakpointResolverName::CreateFromStructuredData(
124         *subclass_options, error);
125     break;
126   case FileRegexResolver:
127     result_sp = BreakpointResolverFileRegex::CreateFromStructuredData(
128         *subclass_options, error);
129     break;
130   case PythonResolver:
131     result_sp = BreakpointResolverScripted::CreateFromStructuredData(
132         *subclass_options, error);
133     break;
134   case ExceptionResolver:
135     error.SetErrorString("Exception resolvers are hard.");
136     break;
137   default:
138     llvm_unreachable("Should never get an unresolvable resolver type.");
139   }
140 
141   if (error.Fail() || !result_sp)
142     return {};
143 
144   // Add on the global offset option:
145   result_sp->SetOffset(offset);
146   return result_sp;
147 }
148 
149 StructuredData::DictionarySP BreakpointResolver::WrapOptionsDict(
150     StructuredData::DictionarySP options_dict_sp) {
151   if (!options_dict_sp || !options_dict_sp->IsValid())
152     return StructuredData::DictionarySP();
153 
154   StructuredData::DictionarySP type_dict_sp(new StructuredData::Dictionary());
155   type_dict_sp->AddStringItem(GetSerializationSubclassKey(), GetResolverName());
156   type_dict_sp->AddItem(GetSerializationSubclassOptionsKey(), options_dict_sp);
157 
158   // Add the m_offset to the dictionary:
159   options_dict_sp->AddIntegerItem(GetKey(OptionNames::Offset), m_offset);
160 
161   return type_dict_sp;
162 }
163 
164 void BreakpointResolver::SetBreakpoint(const BreakpointSP &bkpt) {
165   assert(bkpt);
166   m_breakpoint = bkpt;
167   NotifyBreakpointSet();
168 }
169 
170 void BreakpointResolver::ResolveBreakpointInModules(SearchFilter &filter,
171                                                     ModuleList &modules) {
172   filter.SearchInModuleList(*this, modules);
173 }
174 
175 void BreakpointResolver::ResolveBreakpoint(SearchFilter &filter) {
176   filter.Search(*this);
177 }
178 
179 namespace {
180 struct SourceLoc {
181   uint32_t line = UINT32_MAX;
182   uint16_t column;
183   SourceLoc(uint32_t l, std::optional<uint16_t> c)
184       : line(l), column(c ? *c : LLDB_INVALID_COLUMN_NUMBER) {}
185   SourceLoc(const SymbolContext &sc)
186       : line(sc.line_entry.line),
187         column(sc.line_entry.column ? sc.line_entry.column
188                                     : LLDB_INVALID_COLUMN_NUMBER) {}
189 };
190 
191 bool operator<(const SourceLoc lhs, const SourceLoc rhs) {
192   if (lhs.line < rhs.line)
193     return true;
194   if (lhs.line > rhs.line)
195     return false;
196   //  uint32_t a_col = lhs.column ? lhs.column : LLDB_INVALID_COLUMN_NUMBER;
197   //  uint32_t b_col = rhs.column ? rhs.column : LLDB_INVALID_COLUMN_NUMBER;
198   return lhs.column < rhs.column;
199 }
200 } // namespace
201 
202 void BreakpointResolver::SetSCMatchesByLine(
203     SearchFilter &filter, SymbolContextList &sc_list, bool skip_prologue,
204     llvm::StringRef log_ident, uint32_t line, std::optional<uint16_t> column) {
205   llvm::SmallVector<SymbolContext, 16> all_scs;
206   for (uint32_t i = 0; i < sc_list.GetSize(); ++i)
207     all_scs.push_back(sc_list[i]);
208 
209   while (all_scs.size()) {
210     uint32_t closest_line = UINT32_MAX;
211 
212     // Move all the elements with a matching file spec to the end.
213     auto &match = all_scs[0];
214     auto worklist_begin = std::partition(
215         all_scs.begin(), all_scs.end(), [&](const SymbolContext &sc) {
216           if (sc.line_entry.file == match.line_entry.file ||
217               *sc.line_entry.original_file_sp ==
218                   *match.line_entry.original_file_sp) {
219             // When a match is found, keep track of the smallest line number.
220             closest_line = std::min(closest_line, sc.line_entry.line);
221             return false;
222           }
223           return true;
224         });
225 
226     // (worklist_begin, worklist_end) now contains all entries for one filespec.
227     auto worklist_end = all_scs.end();
228 
229     if (column) {
230       // If a column was requested, do a more precise match and only
231       // return the first location that comes before or at the
232       // requested location.
233       SourceLoc requested(line, *column);
234       // First, filter out all entries left of the requested column.
235       worklist_end = std::remove_if(
236           worklist_begin, worklist_end,
237           [&](const SymbolContext &sc) { return requested < SourceLoc(sc); });
238       // Sort the remaining entries by (line, column).
239       llvm::sort(worklist_begin, worklist_end,
240                  [](const SymbolContext &a, const SymbolContext &b) {
241                    return SourceLoc(a) < SourceLoc(b);
242                  });
243 
244       // Filter out all locations with a source location after the closest match.
245       if (worklist_begin != worklist_end)
246         worklist_end = std::remove_if(
247             worklist_begin, worklist_end, [&](const SymbolContext &sc) {
248               return SourceLoc(*worklist_begin) < SourceLoc(sc);
249             });
250     } else {
251       // Remove all entries with a larger line number.
252       // ResolveSymbolContext will always return a number that is >=
253       // the line number you pass in. So the smaller line number is
254       // always better.
255       worklist_end = std::remove_if(worklist_begin, worklist_end,
256                                     [&](const SymbolContext &sc) {
257                                       return closest_line != sc.line_entry.line;
258                                     });
259     }
260 
261     // Sort by file address.
262     llvm::sort(worklist_begin, worklist_end,
263                [](const SymbolContext &a, const SymbolContext &b) {
264                  return a.line_entry.range.GetBaseAddress().GetFileAddress() <
265                         b.line_entry.range.GetBaseAddress().GetFileAddress();
266                });
267 
268     // Go through and see if there are line table entries that are
269     // contiguous, and if so keep only the first of the contiguous range.
270     // We do this by picking the first location in each lexical block.
271     llvm::SmallDenseSet<Block *, 8> blocks_with_breakpoints;
272     for (auto first = worklist_begin; first != worklist_end; ++first) {
273       assert(!blocks_with_breakpoints.count(first->block));
274       blocks_with_breakpoints.insert(first->block);
275       worklist_end =
276           std::remove_if(std::next(first), worklist_end,
277                          [&](const SymbolContext &sc) {
278                            return blocks_with_breakpoints.count(sc.block);
279                          });
280     }
281 
282     // Make breakpoints out of the closest line number match.
283     for (auto &sc : llvm::make_range(worklist_begin, worklist_end))
284       AddLocation(filter, sc, skip_prologue, log_ident);
285 
286     // Remove all contexts processed by this iteration.
287     all_scs.erase(worklist_begin, all_scs.end());
288   }
289 }
290 
291 void BreakpointResolver::AddLocation(SearchFilter &filter,
292                                      const SymbolContext &sc,
293                                      bool skip_prologue,
294                                      llvm::StringRef log_ident) {
295   Log *log = GetLog(LLDBLog::Breakpoints);
296   Address line_start = sc.line_entry.range.GetBaseAddress();
297   if (!line_start.IsValid()) {
298     LLDB_LOGF(log,
299               "error: Unable to set breakpoint %s at file address "
300               "0x%" PRIx64 "\n",
301               log_ident.str().c_str(), line_start.GetFileAddress());
302     return;
303   }
304 
305   if (!filter.AddressPasses(line_start)) {
306     LLDB_LOGF(log,
307               "Breakpoint %s at file address 0x%" PRIx64
308               " didn't pass the filter.\n",
309               log_ident.str().c_str(), line_start.GetFileAddress());
310   }
311 
312   // If the line number is before the prologue end, move it there...
313   bool skipped_prologue = false;
314   if (skip_prologue && sc.function) {
315     Address prologue_addr(sc.function->GetAddressRange().GetBaseAddress());
316     if (prologue_addr.IsValid() && (line_start == prologue_addr)) {
317       const uint32_t prologue_byte_size = sc.function->GetPrologueByteSize();
318       if (prologue_byte_size) {
319         prologue_addr.Slide(prologue_byte_size);
320 
321         if (filter.AddressPasses(prologue_addr)) {
322           skipped_prologue = true;
323           line_start = prologue_addr;
324         }
325       }
326     }
327   }
328 
329   BreakpointLocationSP bp_loc_sp(AddLocation(line_start));
330   if (log && bp_loc_sp && !GetBreakpoint()->IsInternal()) {
331     StreamString s;
332     bp_loc_sp->GetDescription(&s, lldb::eDescriptionLevelVerbose);
333     LLDB_LOGF(log, "Added location (skipped prologue: %s): %s \n",
334               skipped_prologue ? "yes" : "no", s.GetData());
335   }
336 }
337 
338 BreakpointLocationSP BreakpointResolver::AddLocation(Address loc_addr,
339                                                      bool *new_location) {
340   loc_addr.Slide(m_offset);
341   return GetBreakpoint()->AddLocation(loc_addr, new_location);
342 }
343 
344 void BreakpointResolver::SetOffset(lldb::addr_t offset) {
345   // There may already be an offset, so we are actually adjusting location
346   // addresses by the difference.
347   // lldb::addr_t slide = offset - m_offset;
348   // FIXME: We should go fix up all the already set locations for the new
349   // slide.
350 
351   m_offset = offset;
352 }
353