Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/BPF/BPFAbstractMemberAccess.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ BPFAbstractMemberAccess.cpp - Abstracting Member Accesses -----===//
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
// This pass abstracted struct/union member accesses in order to support
10
// compile-once run-everywhere (CO-RE). The CO-RE intends to compile the program
11
// which can run on different kernels. In particular, if bpf program tries to
12
// access a particular kernel data structure member, the details of the
13
// intermediate member access will be remembered so bpf loader can do
14
// necessary adjustment right before program loading.
15
//
16
// For example,
17
//
18
//   struct s {
19
//     int a;
20
//     int b;
21
//   };
22
//   struct t {
23
//     struct s c;
24
//     int d;
25
//   };
26
//   struct t e;
27
//
28
// For the member access e.c.b, the compiler will generate code
29
//   &e + 4
30
//
31
// The compile-once run-everywhere instead generates the following code
32
//   r = 4
33
//   &e + r
34
// The "4" in "r = 4" can be changed based on a particular kernel version.
35
// For example, on a particular kernel version, if struct s is changed to
36
//
37
//   struct s {
38
//     int new_field;
39
//     int a;
40
//     int b;
41
//   }
42
//
43
// By repeating the member access on the host, the bpf loader can
44
// adjust "r = 4" as "r = 8".
45
//
46
// This feature relies on the following three intrinsic calls:
47
//   addr = preserve_array_access_index(base, dimension, index)
48
//   addr = preserve_union_access_index(base, di_index)
49
//          !llvm.preserve.access.index <union_ditype>
50
//   addr = preserve_struct_access_index(base, gep_index, di_index)
51
//          !llvm.preserve.access.index <struct_ditype>
52
//
53
//===----------------------------------------------------------------------===//
54
55
#include "BPF.h"
56
#include "BPFCORE.h"
57
#include "BPFTargetMachine.h"
58
#include "llvm/IR/DebugInfoMetadata.h"
59
#include "llvm/IR/GlobalVariable.h"
60
#include "llvm/IR/Instruction.h"
61
#include "llvm/IR/Instructions.h"
62
#include "llvm/IR/Module.h"
63
#include "llvm/IR/Type.h"
64
#include "llvm/IR/User.h"
65
#include "llvm/IR/Value.h"
66
#include "llvm/Pass.h"
67
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
68
69
#define DEBUG_TYPE "bpf-abstract-member-access"
70
71
namespace llvm {
72
const std::string BPFCoreSharedInfo::AmaAttr = "btf_ama";
73
const std::string BPFCoreSharedInfo::PatchableExtSecName =
74
    ".BPF.patchable_externs";
75
} // namespace llvm
76
77
using namespace llvm;
78
79
namespace {
80
81
class BPFAbstractMemberAccess final : public ModulePass {
82
0
  StringRef getPassName() const override {
83
0
    return "BPF Abstract Member Access";
84
0
  }
85
86
  bool runOnModule(Module &M) override;
87
88
public:
89
  static char ID;
90
206
  BPFAbstractMemberAccess() : ModulePass(ID) {}
91
92
private:
93
  enum : uint32_t {
94
    BPFPreserveArrayAI = 1,
95
    BPFPreserveUnionAI = 2,
96
    BPFPreserveStructAI = 3,
97
  };
98
99
  std::map<std::string, GlobalVariable *> GEPGlobals;
100
  // A map to link preserve_*_access_index instrinsic calls.
101
  std::map<CallInst *, std::pair<CallInst *, uint32_t>> AIChain;
102
  // A map to hold all the base preserve_*_access_index instrinsic calls.
103
  // The base call is not an input of any other preserve_*_access_index
104
  // intrinsics.
105
  std::map<CallInst *, uint32_t> BaseAICalls;
106
107
  bool doTransformation(Module &M);
108
109
  void traceAICall(CallInst *Call, uint32_t Kind);
110
  void traceBitCast(BitCastInst *BitCast, CallInst *Parent, uint32_t Kind);
111
  void traceGEP(GetElementPtrInst *GEP, CallInst *Parent, uint32_t Kind);
112
  void collectAICallChains(Module &M, Function &F);
113
114
  bool IsPreserveDIAccessIndexCall(const CallInst *Call, uint32_t &Kind);
115
  bool removePreserveAccessIndexIntrinsic(Module &M);
116
  void replaceWithGEP(std::vector<CallInst *> &CallList,
117
                      uint32_t NumOfZerosIndex, uint32_t DIIndex);
118
119
  Value *computeBaseAndAccessStr(CallInst *Call, std::string &AccessStr,
120
                                 std::string &AccessKey, uint32_t Kind,
121
                                 MDNode *&TypeMeta);
122
  bool getAccessIndex(const Value *IndexValue, uint64_t &AccessIndex);
123
  bool transformGEPChain(Module &M, CallInst *Call, uint32_t Kind);
124
};
125
} // End anonymous namespace
126
127
char BPFAbstractMemberAccess::ID = 0;
128
INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE,
129
                "abstracting struct/union member accessees", false, false)
130
131
206
ModulePass *llvm::createBPFAbstractMemberAccess() {
132
206
  return new BPFAbstractMemberAccess();
133
206
}
134
135
206
bool BPFAbstractMemberAccess::runOnModule(Module &M) {
136
206
  LLVM_DEBUG(dbgs() << "********** Abstract Member Accesses **********\n");
137
206
138
206
  // Bail out if no debug info.
139
206
  if (empty(M.debug_compile_units()))
140
70
    return false;
141
136
142
136
  return doTransformation(M);
143
136
}
144
145
/// Check whether a call is a preserve_*_access_index intrinsic call or not.
146
bool BPFAbstractMemberAccess::IsPreserveDIAccessIndexCall(const CallInst *Call,
147
845
                                                          uint32_t &Kind) {
148
845
  if (!Call)
149
566
    return false;
150
279
151
279
  const auto *GV = dyn_cast<GlobalValue>(Call->getCalledValue());
152
279
  if (!GV)
153
30
    return false;
154
249
  if (GV->getName().startswith("llvm.preserve.array.access.index")) {
155
14
    Kind = BPFPreserveArrayAI;
156
14
    return true;
157
14
  }
158
235
  if (GV->getName().startswith("llvm.preserve.union.access.index")) {
159
9
    Kind = BPFPreserveUnionAI;
160
9
    return true;
161
9
  }
162
226
  if (GV->getName().startswith("llvm.preserve.struct.access.index")) {
163
35
    Kind = BPFPreserveStructAI;
164
35
    return true;
165
35
  }
166
191
167
191
  return false;
168
191
}
169
170
void BPFAbstractMemberAccess::replaceWithGEP(std::vector<CallInst *> &CallList,
171
                                             uint32_t DimensionIndex,
172
272
                                             uint32_t GEPIndex) {
173
272
  for (auto Call : CallList) {
174
13
    uint32_t Dimension = 1;
175
13
    if (DimensionIndex > 0)
176
5
      Dimension = cast<ConstantInt>(Call->getArgOperand(DimensionIndex))
177
5
                      ->getZExtValue();
178
13
179
13
    Constant *Zero =
180
13
        ConstantInt::get(Type::getInt32Ty(Call->getParent()->getContext()), 0);
181
13
    SmallVector<Value *, 4> IdxList;
182
25
    for (unsigned I = 0; I < Dimension; 
++I12
)
183
12
      IdxList.push_back(Zero);
184
13
    IdxList.push_back(Call->getArgOperand(GEPIndex));
185
13
186
13
    auto *GEP = GetElementPtrInst::CreateInBounds(Call->getArgOperand(0),
187
13
                                                  IdxList, "", Call);
188
13
    Call->replaceAllUsesWith(GEP);
189
13
    Call->eraseFromParent();
190
13
  }
191
272
}
192
193
136
bool BPFAbstractMemberAccess::removePreserveAccessIndexIntrinsic(Module &M) {
194
136
  std::vector<CallInst *> PreserveArrayIndexCalls;
195
136
  std::vector<CallInst *> PreserveUnionIndexCalls;
196
136
  std::vector<CallInst *> PreserveStructIndexCalls;
197
136
  bool Found = false;
198
136
199
136
  for (Function &F : M)
200
163
    for (auto &BB : F)
201
428
      
for (auto &I : BB)68
{
202
428
        auto *Call = dyn_cast<CallInst>(&I);
203
428
        uint32_t Kind;
204
428
        if (!IsPreserveDIAccessIndexCall(Call, Kind))
205
413
          continue;
206
15
207
15
        Found = true;
208
15
        if (Kind == BPFPreserveArrayAI)
209
5
          PreserveArrayIndexCalls.push_back(Call);
210
10
        else if (Kind == BPFPreserveUnionAI)
211
2
          PreserveUnionIndexCalls.push_back(Call);
212
8
        else
213
8
          PreserveStructIndexCalls.push_back(Call);
214
15
      }
215
136
216
136
  // do the following transformation:
217
136
  // . addr = preserve_array_access_index(base, dimension, index)
218
136
  //   is transformed to
219
136
  //     addr = GEP(base, dimenion's zero's, index)
220
136
  // . addr = preserve_union_access_index(base, di_index)
221
136
  //   is transformed to
222
136
  //     addr = base, i.e., all usages of "addr" are replaced by "base".
223
136
  // . addr = preserve_struct_access_index(base, gep_index, di_index)
224
136
  //   is transformed to
225
136
  //     addr = GEP(base, 0, gep_index)
226
136
  replaceWithGEP(PreserveArrayIndexCalls, 1, 2);
227
136
  replaceWithGEP(PreserveStructIndexCalls, 0, 1);
228
136
  for (auto Call : PreserveUnionIndexCalls) {
229
2
    Call->replaceAllUsesWith(Call->getArgOperand(0));
230
2
    Call->eraseFromParent();
231
2
  }
232
136
233
136
  return Found;
234
136
}
235
236
28
void BPFAbstractMemberAccess::traceAICall(CallInst *Call, uint32_t Kind) {
237
28
  for (User *U : Call->users()) {
238
28
    Instruction *Inst = dyn_cast<Instruction>(U);
239
28
    if (!Inst)
240
0
      continue;
241
28
242
28
    if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
243
13
      traceBitCast(BI, Call, Kind);
244
15
    } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
245
13
      uint32_t CIKind;
246
13
      if (IsPreserveDIAccessIndexCall(CI, CIKind)) {
247
13
        AIChain[CI] = std::make_pair(Call, Kind);
248
13
        traceAICall(CI, CIKind);
249
13
      } else {
250
0
        BaseAICalls[Call] = Kind;
251
0
      }
252
13
    } else 
if (auto *2
GI2
= dyn_cast<GetElementPtrInst>(Inst)) {
253
2
      if (GI->hasAllZeroIndices())
254
2
        traceGEP(GI, Call, Kind);
255
0
      else
256
0
        BaseAICalls[Call] = Kind;
257
2
    }
258
28
  }
259
28
}
260
261
void BPFAbstractMemberAccess::traceBitCast(BitCastInst *BitCast,
262
13
                                           CallInst *Parent, uint32_t Kind) {
263
13
  for (User *U : BitCast->users()) {
264
13
    Instruction *Inst = dyn_cast<Instruction>(U);
265
13
    if (!Inst)
266
0
      continue;
267
13
268
13
    if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
269
0
      traceBitCast(BI, Parent, Kind);
270
13
    } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
271
13
      uint32_t CIKind;
272
13
      if (IsPreserveDIAccessIndexCall(CI, CIKind)) {
273
0
        AIChain[CI] = std::make_pair(Parent, Kind);
274
0
        traceAICall(CI, CIKind);
275
13
      } else {
276
13
        BaseAICalls[Parent] = Kind;
277
13
      }
278
13
    } else 
if (auto *0
GI0
= dyn_cast<GetElementPtrInst>(Inst)) {
279
0
      if (GI->hasAllZeroIndices())
280
0
        traceGEP(GI, Parent, Kind);
281
0
      else
282
0
        BaseAICalls[Parent] = Kind;
283
0
    }
284
13
  }
285
13
}
286
287
void BPFAbstractMemberAccess::traceGEP(GetElementPtrInst *GEP, CallInst *Parent,
288
2
                                       uint32_t Kind) {
289
2
  for (User *U : GEP->users()) {
290
2
    Instruction *Inst = dyn_cast<Instruction>(U);
291
2
    if (!Inst)
292
0
      continue;
293
2
294
2
    if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
295
0
      traceBitCast(BI, Parent, Kind);
296
2
    } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
297
2
      uint32_t CIKind;
298
2
      if (IsPreserveDIAccessIndexCall(CI, CIKind)) {
299
2
        AIChain[CI] = std::make_pair(Parent, Kind);
300
2
        traceAICall(CI, CIKind);
301
2
      } else {
302
0
        BaseAICalls[Parent] = Kind;
303
0
      }
304
2
    } else 
if (auto *0
GI0
= dyn_cast<GetElementPtrInst>(Inst)) {
305
0
      if (GI->hasAllZeroIndices())
306
0
        traceGEP(GI, Parent, Kind);
307
0
      else
308
0
        BaseAICalls[Parent] = Kind;
309
0
    }
310
2
  }
311
2
}
312
313
163
void BPFAbstractMemberAccess::collectAICallChains(Module &M, Function &F) {
314
163
  AIChain.clear();
315
163
  BaseAICalls.clear();
316
163
317
163
  for (auto &BB : F)
318
389
    
for (auto &I : BB)68
{
319
389
      uint32_t Kind;
320
389
      auto *Call = dyn_cast<CallInst>(&I);
321
389
      if (!IsPreserveDIAccessIndexCall(Call, Kind) ||
322
389
          
AIChain.find(Call) != AIChain.end()28
)
323
376
        continue;
324
13
325
13
      traceAICall(Call, Kind);
326
13
    }
327
163
}
328
329
/// Get access index from the preserve_*_access_index intrinsic calls.
330
bool BPFAbstractMemberAccess::getAccessIndex(const Value *IndexValue,
331
28
                                             uint64_t &AccessIndex) {
332
28
  const ConstantInt *CV = dyn_cast<ConstantInt>(IndexValue);
333
28
  if (!CV)
334
0
    return false;
335
28
336
28
  AccessIndex = CV->getValue().getZExtValue();
337
28
  return true;
338
28
}
339
340
/// Compute the base of the whole preserve_*_access_index chains, i.e., the base
341
/// pointer of the first preserve_*_access_index call, and construct the access
342
/// string, which will be the name of a global variable.
343
Value *BPFAbstractMemberAccess::computeBaseAndAccessStr(CallInst *Call,
344
                                                        std::string &AccessStr,
345
                                                        std::string &AccessKey,
346
                                                        uint32_t Kind,
347
13
                                                        MDNode *&TypeMeta) {
348
13
  Value *Base = nullptr;
349
13
  std::vector<uint64_t> AccessIndices;
350
13
  uint64_t TypeNameIndex = 0;
351
13
  std::string LastTypeName;
352
13
353
41
  while (Call) {
354
28
    // Base of original corresponding GEP
355
28
    Base = Call->getArgOperand(0);
356
28
357
28
    // Type Name
358
28
    std::string TypeName;
359
28
    MDNode *MDN;
360
28
    if (Kind == BPFPreserveUnionAI || 
Kind == BPFPreserveStructAI23
) {
361
23
      MDN = Call->getMetadata(LLVMContext::MD_preserve_access_index);
362
23
      if (!MDN)
363
0
        return nullptr;
364
23
365
23
      DIType *Ty = dyn_cast<DIType>(MDN);
366
23
      if (!Ty)
367
0
        return nullptr;
368
23
369
23
      TypeName = Ty->getName();
370
23
    }
371
28
372
28
    // Access Index
373
28
    uint64_t AccessIndex;
374
28
    uint32_t ArgIndex = (Kind == BPFPreserveUnionAI) ? 
15
:
223
;
375
28
    if (!getAccessIndex(Call->getArgOperand(ArgIndex), AccessIndex))
376
0
      return nullptr;
377
28
378
28
    AccessIndices.push_back(AccessIndex);
379
28
    if (TypeName.size()) {
380
17
      TypeNameIndex = AccessIndices.size() - 1;
381
17
      LastTypeName = TypeName;
382
17
      TypeMeta = MDN;
383
17
    }
384
28
385
28
    Kind = AIChain[Call].second;
386
28
    Call = AIChain[Call].first;
387
28
  }
388
13
389
13
  // The intial type name is required.
390
13
  // FIXME: if the initial type access is an array index, e.g.,
391
13
  // &a[3].b.c, only one dimentional array is supported.
392
13
  if (!LastTypeName.size() || AccessIndices.size() > TypeNameIndex + 2)
393
0
    return nullptr;
394
13
395
13
  // Construct the type string AccessStr.
396
41
  
for (unsigned I = 0; 13
I < AccessIndices.size();
++I28
)
397
28
    AccessStr = std::to_string(AccessIndices[I]) + ":" + AccessStr;
398
13
399
13
  if (TypeNameIndex == AccessIndices.size() - 1)
400
12
    AccessStr = "0:" + AccessStr;
401
13
402
13
  // Access key is the type name + access string, uniquely identifying
403
13
  // one kernel memory access.
404
13
  AccessKey = LastTypeName + ":" + AccessStr;
405
13
406
13
  return Base;
407
13
}
408
409
/// Call/Kind is the base preserve_*_access_index() call. Attempts to do
410
/// transformation to a chain of relocable GEPs.
411
bool BPFAbstractMemberAccess::transformGEPChain(Module &M, CallInst *Call,
412
13
                                                uint32_t Kind) {
413
13
  std::string AccessStr, AccessKey;
414
13
  MDNode *TypeMeta = nullptr;
415
13
  Value *Base =
416
13
      computeBaseAndAccessStr(Call, AccessStr, AccessKey, Kind, TypeMeta);
417
13
  if (!Base)
418
0
    return false;
419
13
420
13
  // Do the transformation
421
13
  // For any original GEP Call and Base %2 like
422
13
  //   %4 = bitcast %struct.net_device** %dev1 to i64*
423
13
  // it is transformed to:
424
13
  //   %6 = load __BTF_0:sk_buff:0:0:2:0:
425
13
  //   %7 = bitcast %struct.sk_buff* %2 to i8*
426
13
  //   %8 = getelementptr i8, i8* %7, %6
427
13
  //   %9 = bitcast i8* %8 to i64*
428
13
  //   using %9 instead of %4
429
13
  // The original Call inst is removed.
430
13
  BasicBlock *BB = Call->getParent();
431
13
  GlobalVariable *GV;
432
13
433
13
  if (GEPGlobals.find(AccessKey) == GEPGlobals.end()) {
434
13
    GV = new GlobalVariable(M, Type::getInt64Ty(BB->getContext()), false,
435
13
                            GlobalVariable::ExternalLinkage, NULL, AccessStr);
436
13
    GV->addAttribute(BPFCoreSharedInfo::AmaAttr);
437
13
    // Set the metadata (debuginfo types) for the global.
438
13
    if (TypeMeta)
439
13
      GV->setMetadata(LLVMContext::MD_preserve_access_index, TypeMeta);
440
13
    GEPGlobals[AccessKey] = GV;
441
13
  } else {
442
0
    GV = GEPGlobals[AccessKey];
443
0
  }
444
13
445
13
  // Load the global variable.
446
13
  auto *LDInst = new LoadInst(Type::getInt64Ty(BB->getContext()), GV);
447
13
  BB->getInstList().insert(Call->getIterator(), LDInst);
448
13
449
13
  // Generate a BitCast
450
13
  auto *BCInst = new BitCastInst(Base, Type::getInt8PtrTy(BB->getContext()));
451
13
  BB->getInstList().insert(Call->getIterator(), BCInst);
452
13
453
13
  // Generate a GetElementPtr
454
13
  auto *GEP = GetElementPtrInst::Create(Type::getInt8Ty(BB->getContext()),
455
13
                                        BCInst, LDInst);
456
13
  BB->getInstList().insert(Call->getIterator(), GEP);
457
13
458
13
  // Generate a BitCast
459
13
  auto *BCInst2 = new BitCastInst(GEP, Call->getType());
460
13
  BB->getInstList().insert(Call->getIterator(), BCInst2);
461
13
462
13
  Call->replaceAllUsesWith(BCInst2);
463
13
  Call->eraseFromParent();
464
13
465
13
  return true;
466
13
}
467
468
136
bool BPFAbstractMemberAccess::doTransformation(Module &M) {
469
136
  bool Transformed = false;
470
136
471
163
  for (Function &F : M) {
472
163
    // Collect PreserveDIAccessIndex Intrinsic call chains.
473
163
    // The call chains will be used to generate the access
474
163
    // patterns similar to GEP.
475
163
    collectAICallChains(M, F);
476
163
477
163
    for (auto &C : BaseAICalls)
478
13
      Transformed = transformGEPChain(M, C.first, C.second) || 
Transformed0
;
479
163
  }
480
136
481
136
  return removePreserveAccessIndexIntrinsic(M) || 
Transformed127
;
482
136
}