Debian Codegraph @

libcextract/SymbolExternalizer.hh

raw
1 //===- SymbolExternalizer.cpp - Externalize or rename symbols ---*- C++ -*-===//
2 //
3 // This project is licensed 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 /// \file
10 /// Externalize or rename symbols.
11 //
12 //===----------------------------------------------------------------------===//
13
14 /* Author: Giuliano Belinassi */
15
16 #pragma once
17
18 #include "MacroWalker.hh"
19 #include "InlineAnalysis.hh"
20 #include "Closure.hh"
21
22 #include <clang/Tooling/Tooling.h>
23 #include <clang/Rewrite/Core/Rewriter.h>
24 #include "llvm/ADT/StringMap.h"
25
26 using namespace clang;
27
28 struct ExternalizerLogEntry
29 {
30 std::string OldName;
31 std::string NewName;
32 ExternalizationType Type;
33 };
34
35 /* Contains the context of an externalized symbol. It's necessary when the
36 * symbol is being handled in different visitors to know why/if it was already
37 * externalized. */
38 struct SymbolUpdateStatus
39 {
40
41 SymbolUpdateStatus(std::string new_name, ExternalizationType ext, bool done, bool wrap) :
42 NewName(new_name),
43 ExtType(ext),
44 OldDecl(nullptr),
45 NewDecl(nullptr),
46 FirstUse(nullptr),
47 LateInsertLocation(SourceLocation()),
48 Done(done),
49 Wrap(wrap)
50 {
51 }
52
53 SymbolUpdateStatus(ExternalizationType ext) :
54 NewName(""),
55 ExtType(ext),
56 OldDecl(nullptr),
57 NewDecl(nullptr),
58 FirstUse(nullptr),
59 LateInsertLocation(SourceLocation()),
60 Done(false),
61 Wrap(false)
62 {
63 }
64
65 /* The name that was used when the symbol was externalized. */
66 std::string NewName;
67
68 /* The type of the externalization: STRONG, WEAK of RENAME. */
69 ExternalizationType ExtType;
70
71 /* The old non-externalized declaration. */
72 DeclaratorDecl *OldDecl;
73
74 /* The new externalized declaration. */
75 DeclaratorDecl *NewDecl;
76
77 /* The first use of the symbol. */
78 DeclRefExpr *FirstUse;
79
80 /* The late insertion location. */
81 SourceLocation LateInsertLocation;
82
83 /* Set when the symbol was externalized. */
84 bool Done;
85
86 /* Set when the symbol usage should be dereferenced when used. */
87 bool Wrap;
88
89 /* Get the correct name used when the code was transformed */
90 inline std::string getUseName(void)
91 {
92 return Wrap ? "(*" + NewName + ")"
93 : NewName;
94 }
95
96 /* Check if this SymbolUpdateStatus was used, e.g. it wasn't a result of an
97 attempt of externalize an symbol which was removed by the ClosurePass. */
98 inline bool Is_Used(void)
99 {
100 return OldDecl && NewDecl && FirstUse;
101 }
102
103 /* For IBT, NewDecl and OldDecl are the same if the symbols is a function, so
104 don't replace text if the name didn't change.
105 In the case of WEAK externalization NewDecl will also be empty, but in this
106 case we don't want a symbol rename. */
107 inline bool Needs_Sym_Rename(void) {
108 if (ExtType == ExternalizationType::WEAK)
109 return false;
110
111 if (NewDecl == nullptr)
112 return true;
113
114 return NewDecl->getName() != OldDecl->getName();
115 }
116
117 void Dump(SourceManager &SM)
118 {
119 llvm::outs() << "SymbolUpdateStatus at 0x" << this << '\n';
120 if (OldDecl != nullptr) {
121 SourceLocation loc = OldDecl->getLocation();
122 PresumedLoc ploc = SM.getPresumedLoc(loc);
123 llvm::outs() << " OldDecl " << OldDecl->getName() << " at " << ploc.getFilename() << ':' << ploc.getLine() << '\n';
124 } else {
125 llvm::outs() << " OldDecl is NULL\n";
126 }
127 if (FirstUse != nullptr) {
128 SourceLocation loc = FirstUse->getLocation();
129 PresumedLoc ploc = SM.getPresumedLoc(loc);
130 llvm::outs() << " FirstUse at " << ploc.getFilename() << ':' << ploc.getLine() << ':' << ploc.getColumn() << '\n';
131 } else {
132 llvm::outs() << " FirstUse is NULL\n";
133 }
134 if (LateInsertLocation.isValid()) {
135 PresumedLoc ploc = SM.getPresumedLoc(LateInsertLocation);
136 llvm::outs() << " LateInsertLocation at " << ploc.getFilename() << ':' << ploc.getLine() << ':' << ploc.getColumn() << '\n';
137 } else {
138 llvm::outs() << " LateInsertLocation is invalid\n";
139 }
140 llvm::outs() << " ExternalizationType = " << ExtType << '\n';
141 }
142 };
143
144 /** Text Modification class wrapping Clang's Rewriter.
145 *
146 * Clang has a Rewriter class in order to issue Text Modifications into the
147 * same Compilation Unit. The problem is that this class expects that every
148 * modifications is commutative, that means A + B = B + A. This is not the
149 * case when whe are externalizing things, once we may externalize a function
150 * that in its body contains a reference to another externalized function.
151 * Hence we have to cleverly find which modifications stays and which should
152 * be discarded.
153 *
154 * We do this by setting a priority in each Text Modifications, and if two
155 * modifications wants to modify the same piece of text, we only let the one
156 * with highest priority. With this, we classify the modifications which
157 * removes content to be the highest priority, and the ones which only changes
158 * the name of things to be the lowest priority. Hence at some point we compute
159 * the insersection of all with all and discards the ones with lower priority.
160 */
161 class TextModifications
162 {
163 public:
164 /** A delta -- a single text modification. */
165 struct Delta
166 {
167 Delta(const SourceRange &to_change, const std::string &new_text, int prio);
168
169 Delta(void)
170 : ToChange(),
171 NewText(),
172 Priority(0),
173 ID(0)
174 {
175 }
176
177 /* Check if two changes results in the same change. */
178 static bool Is_Same_Change(const Delta &a, const Delta &b)
179 {
180 return a.ToChange == b.ToChange && a.NewText == b.NewText;
181 }
182
183 bool operator<(const Delta& other) const
184 {
185 return !(Is_Same_Change(*this, other));
186 }
187
188 bool operator==(const Delta &other) const
189 {
190 return Is_Same_Change(*this, other);
191 }
192
193 /* Which part of the original code should be changed? */
194 SourceRange ToChange;
195
196 /* With what text? */
197 std::string NewText;
198
199 /* What is the priority of this change? */
200 int Priority;
201
202 /* ID. */
203 int ID;
204 };
205
206 /** Constructor for the TextModification class. */
207 TextModifications(ASTUnit *ast, bool dump = false)
208 : SM(ast->getSourceManager()),
209 LO(ast->getLangOpts()),
210 RW(SM, LO),
211 DumpingEnabled(dump)
212 {}
213
214 /** Get underlying Rewriter class. */
215 inline Rewriter &Get_Rewriter(void)
216 {
217 return RW;
218 }
219
220 /* Insert a text modification. */
221 void Insert(Delta &delta);
222
223 /* Solve the modifications according to their priorities and apply to clang's
224 Rewriter class instance. */
225 void Commit(void);
226
227 /* Get FileEntry map. */
228 typedef std::unordered_map<const FileEntry *, std::pair<FileID, StringRef>>
229 FileEntryMapType;
230
231 inline const FileEntryMapType &Get_FileEntry_Map(void)
232 {
233 return FileEntryMap;
234 }
235
236 /* Insert into the FileEntryMap hash. */
237 bool Insert_Into_FileEntryMap(const SourceLocation &loc);
238 bool Insert_Into_FileEntryMap(const SourceRange &range);
239
240 /* Dump, for debugging purposes. */
241 void Dump(unsigned, const Delta &a);
242
243 private:
244
245 /* Solve the modifications according to their priorities. */
246 void Solve(void);
247
248 /* Sort the DeltaLists (sequence of text modifications) according to their
249 priorities. */
250 void Sort(void);
251
252 /* Checks if two SourceRanges intersects. */
253 bool Intersects(const SourceRange &a, const SourceRange &b);
254
255 /* Check if two Deltas (text modifications) intersects. */
256 bool Intersects(const Delta &a, const Delta &b);
257
258 /* Check which SourceLocation comes first. */
259 bool Is_Before_Or_Equal(const PresumedLoc &a, const PresumedLoc &b);
260
261 /* Reference to the AST SourceManager. */
262 SourceManager &SM;
263
264 /* Reference to the AST LangOptions. */
265 const LangOptions &LO;
266
267 /* The clang's Rewriter class. */
268 Rewriter RW;
269
270 /* Flag indicating we want to dump our changes. */
271 bool DumpingEnabled;
272
273 /* The list of Text Modifications we want to do. */
274 std::vector<Delta> DeltaList;
275
276 /* Our own mapping from FileEntry to FileID to get the modifications to the
277 files. */
278 FileEntryMapType FileEntryMap;
279 };
280
281 /** Class encapsulating the Symbol externalizer mechanism.
282 *
283 * Livepatched functions very often references static functions or variables
284 * that we have to `externalize` them. Assume we want to externalize a
285 * function f. We externalize it by applying the following transformation:
286 *
287 * before:
288 * int f(void) {
289 * ... code
290 * return x;
291 * }
292 *
293 * after:
294 * static int (*f)(void);
295 *
296 * then libpulp or klp is responsible for initializing the pointer `f` with
297 * its correct address in the target binary.
298 *
299 */
300 class SymbolExternalizer
301 {
302 public:
303 SymbolExternalizer(ASTUnit *ast, InlineAnalysis &ia, bool ibt,
304 bool allow_late_externalize, std::string patch_object,
305 const std::vector<std::string> &functions_to_extract,
306 IncludeExpansionPolicy::Policy exp_policy,
307 std::vector<std::string> const &must_expand,
308 std::vector<std::string> const &must_not_expand,
309 bool dump = false)
310 : AST(ast),
311 MW(ast->getPreprocessor()),
312 TM(ast, dump),
313 IA(ia),
314 Ibt(ibt),
315 AllowLateExternalization(allow_late_externalize),
316 PatchObject(patch_object),
317 SymbolsMap({}),
318 ClosureVisitor(ast),
319 IT(AST, exp_policy, must_expand, must_not_expand)
320 {
321 ClosureVisitor.Compute_Closure_Of_Symbols(functions_to_extract);
322 }
323
324 friend class ExternalizerVisitor;
325
326 /* Create the externalized var as a AST node ready to be slapped into the
327 AST. */
328 VarDecl *Create_Externalized_Var(DeclaratorDecl *decl, const std::string &name);
329
330 /* Externalize a symbol, that means transforming functions into a function
331 pointer, or an global variable into a variable pointer.
332
333 WARNING: Modifies the to_rename_array vector. */
334 void Externalize_Symbols(std::vector<std::string> const &to_externalize_array,
335 std::vector<std::string> &to_rename_array);
336 inline void Externalize_Symbols(std::vector<std::string> const &to_externalize_array)
337 {
338 std::vector<std::string> empty = {};
339 Externalize_Symbols(to_externalize_array, empty);
340 }
341
342 std::vector<std::pair<std::string, SourceRange>>
343 Get_Range_Of_Identifier_In_Macro_Expansion(const MacroExpansion *exp);
344
345 SymbolUpdateStatus *getSymbolsUpdateStatus(const StringRef &sym);
346
347 bool Drop_Static(FunctionDecl *decl);
348
349 /* Replace `static` keyword in decl with extern. */
350 template <typename DECL>
351 bool Add_Extern(DECL *decl);
352
353 /* Replace `static` keyword in decl with extern. */
354 template <typename DECL>
355 bool Drop_Static_Add_Extern(DECL *decl);
356
357 /** Commit changes to the loaded source file buffer. Should NOT modify the
358 original file, only the content that was loaded in llvm's InMemory file
359 system. */
360 bool Commit_Changes_To_Source(IntrusiveRefCntPtr<llvm::vfs::OverlayFileSystem> &ofs,
361 IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> &mfs,
362 std::vector<std::string> &headers_to_expand);
363
364 std::string Get_Modifications_To_Main_File(void);
365
366 inline std::vector<ExternalizerLogEntry> &Get_Log_Of_Changed_Names(void)
367 {
368 return Log;
369 }
370
371 /** Returns true if there was at least one externalized symbol */
372 inline bool Has_Externalizations(void)
373 {
374 for (auto const& [key, val] : SymbolsMap) {
375 if (val.ExtType == ExternalizationType::STRONG)
376 return true;
377 }
378
379 return false;
380 }
381
382 /** Dump the SymbolsMap structure into stdout for debugging purposes. */
383 void Dump_SymbolsMap(void);
384
385 private:
386
387 /** Get the ExternalizationType from a string. */
388 enum ExternalizationType Get_Symbol_Ext_Type(const std::string &to_externalize);
389
390 /** Compute the late insert locations when -DCE_LATE_EXTERNALIZE is passed by
391 the user. It will attempt to find a SourceLocation before the first use
392 of the variable that is valid, so we can put our externalized symbol there. */
393 void Compute_SymbolsMap_Late_Insert_Locations(std::vector<SymbolUpdateStatus *> &array);
394
395 /** Do the late externalize logic. */
396 void Late_Externalize(void);
397
398 /** Rewrite the macros which tokens matches the symbols we want to externalize. */
399 void Rewrite_Macros(void);
400
401 /* Issue a Text Replacement with a given `priority`. The priority will be
402 used in case that there are two replacements to the same piece of text. */
403 void Replace_Text(const SourceRange &range, StringRef new_name, int priority);
404 void Remove_Text(const SourceRange &range, int priority);
405 void Insert_Text(const SourceLocation &range, StringRef text);
406
407 /** Drop body of function. */
408 void Drop_Function_Body(FunctionDecl *decl);
409
410 /** Drop Variable Initializer. */
411 void Drop_Var_Initializer(VarDecl *decl);
412
413 /** Handle externalization on IBT case. */
414 void Handle_IBT_Ext(SymbolUpdateStatus *);
415
416 /** AST in analysis. */
417 ASTUnit *AST;
418
419 /** MacroWalker object which helps iterating on Macros. */
420 MacroWalker MW;
421
422 /** Clang's Rewriter class used to auxiliate us with changes in the source code. */
423 TextModifications TM;
424
425 /** Reference to the InlineAnalysis in the PassManager::Context instance. */
426 InlineAnalysis &IA;
427
428 /** Log of changed names. */
429 std::vector<ExternalizerLogEntry> Log;
430
431 /** Defines the method that a private symbol will be searched. */
432 bool Ibt;
433
434 /* True if we can write the externalized decl later than the original symbol. */
435 bool AllowLateExternalization;
436
437 /* Name of the object that will be patched. */
438 std::string PatchObject;
439
440 /** Symbols and its externalization type */
441 llvm::StringMap<SymbolUpdateStatus> SymbolsMap;
442
443 /* ClosureVisitor to compute the closure. */
444 DeclClosureVisitor ClosureVisitor;
445
446 /* IncludeTree to verify if a certain header can be marked for expansion. */
447 IncludeTree IT;
448 };