minix/llvm/passes/asr/ASRPass.cpp

   1 #include <asr/ASRPass.h>
   2 #include <magic_common.h>
   3 #include <magic/support/MagicUtil.h>
   4 #include <llvm/Transforms/Utils/BasicBlockUtils.h>
   5
   6 #define MAGIC_IS_MAGIC_FUNC(M, F) (!StringRef((F)->getSection()).compare(MAGIC_STATIC_FUNCTIONS_SECTION))
   7
   8 using namespace llvm;
   9
  10
  11 // command-line arguments
  12
  13 static cl::opt<int>
  14 seed("asr-seed",
  15     cl::desc("Random seed integer value for ASRPass. '0' will use current time as seed"),
  16     cl::init(DEFAULT_SEED), cl::NotHidden, cl::ValueRequired);
  17
  18
  19 static cl::opt<int>
  20 gv_max_offset("asr-gv-max-offset",
  21     cl::desc(""),
  22     cl::init(GV_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired);
  23
  24 static cl::opt<int>
  25 gv_max_padding("asr-gv-max-padding",
  26     cl::desc(""),
  27     cl::init(GV_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired);
  28
  29 static cl::opt<int>
  30 gv_do_permutate("asr-gv-do-permutate",
  31     cl::desc(""),
  32     cl::init(GV_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired);
  33
  34
  35 static cl::opt<int>
  36 func_max_offset("asr-func-max-offset",
  37     cl::desc(""),
  38     cl::init(FUNC_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired);
  39
  40 static cl::opt<int>
  41 func_max_padding("asr-func-max-padding",
  42     cl::desc(""),
  43     cl::init(FUNC_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired);
  44
  45 static cl::opt<int>
  46 func_max_bb_shift("asr-func-max-bb-shift",
  47     cl::desc(""),
  48     cl::init(FUNC_DEFAULT_MAX_BB_SHIFT), cl::NotHidden, cl::ValueRequired);
  49
  50 static cl::opt<int>
  51 func_do_permutate("asr-func-do-permutate",
  52     cl::desc(""),
  53     cl::init(FUNC_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired);
  54
  55
  56 static cl::opt<int>
  57 stack_do_offset("asr-stack-do-offset",
  58     cl::desc(""),
  59     cl::init(STACK_DEFAULT_DO_OFFSET), cl::NotHidden, cl::ValueRequired);
  60
  61 static cl::opt<int>
  62 stack_max_offset("asr-stack-max-offset",
  63     cl::desc(""),
  64     cl::init(STACK_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired);
  65
  66
  67 static cl::opt<int>
  68 stackframe_do_offset("asr-stackframe-do-offset",
  69     cl::desc(""),
  70     cl::init(STACKFRAME_DEFAULT_DO_OFFSET), cl::NotHidden, cl::ValueRequired);
  71
  72 static cl::opt<int>
  73 stackframe_max_offset("asr-stackframe-max-offset",
  74     cl::desc(""),
  75     cl::init(STACKFRAME_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired);
  76
  77 static cl::opt<int>
  78 stackframe_max_padding("asr-stackframe-max-padding",
  79     cl::desc(""),
  80     cl::init(STACKFRAME_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired);
  81
  82 static cl::opt<int>
  83 stackframe_do_permutate("asr-stackframe-do-permutate",
  84     cl::desc(""),
  85     cl::init(STACKFRAME_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired);
  86
  87 static cl::opt<int>
  88 stackframe_static_padding("asr-stackframe-static-padding",
  89     cl::desc(""),
  90     cl::init(STACKFRAME_DEFAULT_STATIC_PADDING), cl::NotHidden, cl::ValueRequired);
  91
  92 static cl::opt<int>
  93 stackframe_caller_padding("asr-stackframe-caller-padding",
  94     cl::desc(""),
  95     cl::init(STACKFRAME_DEFAULT_CALLER_PADDING), cl::NotHidden, cl::ValueRequired);
  96
  97 static cl::opt<int>
  98 heap_map_do_permutate("asr-heap-map-do-permutate",
  99     cl::desc(""),
 100     cl::init(HEAP_MAP_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired);
 101
 102
 103 static cl::opt<int>
 104 heap_max_offset("asr-heap-max-offset",
 105     cl::desc(""),
 106     cl::init(HEAP_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired);
 107
 108 static cl::opt<int>
 109 heap_max_padding("asr-heap-max-padding",
 110     cl::desc(""),
 111     cl::init(HEAP_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired);
 112
 113
 114 static cl::opt<int>
 115 map_max_offset_pages("asr-map-max-offset-pages",
 116     cl::desc(""),
 117     cl::init(MAP_DEFAULT_MAX_OFFSET_PAGES), cl::NotHidden, cl::ValueRequired);
 118
 119 static cl::opt<int>
 120 map_max_padding_pages("asr-map-max-padding-pages",
 121     cl::desc(""),
 122     cl::init(MAP_DEFAULT_MAX_PADDING_PAGES), cl::NotHidden, cl::ValueRequired);
 123
 124
 125 #define __X(P) #P
 126         std::string magicMemFuncNames[] = { MAGIC_MEM_FUNC_NAMES };
 127 #undef __X
 128
 129 namespace llvm {
 130
 131 PASS_COMMON_INIT_ONCE();
 132
 133 //===----------------------------------------------------------------------===//
 134 // Constructors, destructor, and operators
 135 //===----------------------------------------------------------------------===//
 136
 137 ASRPass::ASRPass() : ModulePass(ID) {}
 138 //===----------------------------------------------------------------------===//
 139 // Public methods
 140 //===----------------------------------------------------------------------===//
 141
 142 void fillPermutationGenerator(std::vector<unsigned> &permutationGenerator){
 143     // This function returns a list of indices. In order to create a permutation of a list of elements, for each index, remove that element and place it at the end of the list.
 144     unsigned size = permutationGenerator.size();
 145     for (unsigned i = 0; i < size; ++i) {
 146         unsigned j = rand() % (size - i);
 147         permutationGenerator[i] = j;
 148     }
 149 }
 150
 151 Function* getCalledFunctionFromCS(const CallSite &CS) {
 152     assert(CS.getInstruction());
 153     Function *function = CS.getCalledFunction();
 154     if(function) {
 155         return function;
 156     }
 157
 158     //handle the weird case of bitcasted function call
 159     ConstantExpr *CE = dyn_cast<ConstantExpr>(CS.getCalledValue());
 160     if(!CE) {
 161         return NULL;
 162     }
 163     assert(CE && CE->getOpcode() == Instruction::BitCast && "Bitcast expected, something else found!");
 164     function = dyn_cast<Function>(CE->getOperand(0));
 165     assert(function);
 166
 167     return function;
 168 }
 169
 170 #define ADVANCE_ITERATOR(IT, N_POS) for(unsigned __adv_it_count=0; __adv_it_count< N_POS; __adv_it_count++){ IT++;}
 171
 172 GlobalVariable *create_padding_gv(Module &M, GlobalVariable *InsertBefore, int n_bytes){
 173
 174     ArrayType* ArrayTy = ArrayType::get(IntegerType::get(M.getContext(), 8), n_bytes);
 175
 176     GlobalVariable* padding_char_arr = new GlobalVariable(/*Module=*/M,
 177             /*Type=*/ArrayTy,
 178             /*isConstant=*/false,
 179             /*Linkage=*/GlobalValue::InternalLinkage,
 180             /*Initializer=*/ConstantAggregateZero::get(ArrayTy),
 181             /*Name=*/"magic_asr_padding_gv",
 182             /*InsertBefore=*/InsertBefore);
 183     padding_char_arr->setAlignment(1);
 184     padding_char_arr->setSection(InsertBefore->getSection());
 185     return padding_char_arr;
 186
 187 }
 188
 189 AllocaInst *create_padding_lv(Module &M, Instruction *InsertBefore, int n_bytes){
 190
 191     ArrayType* ArrayTy = ArrayType::get(IntegerType::get(M.getContext(), 8), n_bytes);
 192     AllocaInst* ptr_x = new AllocaInst(ArrayTy, "magic_asr_padding_lv", InsertBefore);
 193     ptr_x->setAlignment(16);
 194
 195     /* Seems not to be necessary
 196
 197     ConstantInt* const_int64_0 = ConstantInt::get(M.getContext(), APInt(64, StringRef("0"), 10));
 198     ConstantInt* const_int8_0 = ConstantInt::get(M.getContext(), APInt(8, StringRef("97"), 10));
 199
 200     std::vector<Value*> ptr_indices;
 201     ptr_indices.push_back(const_int64_0);
 202     ptr_indices.push_back(const_int64_0);
 203
 204     Instruction* ptr_8 = GetElementPtrInst::Create(ptr_x, ptr_indices.begin(), ptr_indices.end(), "", ptr_x->getParent());
 205     ptr_8->removeFromParent();
 206     ptr_8->insertAfter(ptr_x);
 207
 208     StoreInst* void_9 = new StoreInst(const_int8_0, ptr_8, true, ptr_x->getParent());
 209     void_9->setAlignment(16);
 210     void_9->removeFromParent();
 211     void_9->insertAfter(ptr_8);
 212
 213     */
 214
 215     return ptr_x;
 216
 217 }
 218
 219 Function *create_padding_func(Module &M, int n_ops){
 220     /* Places a padding function at the end of the function list */
 221
 222     std::vector<TYPECONST Type*>FuncTy_0_args;
 223     TYPECONST FunctionType* FuncTy_0 = FunctionType::get(Type::getVoidTy(M.getContext()), FuncTy_0_args, false);
 224
 225     Function* func_padding_func = Function::Create(FuncTy_0, GlobalValue::ExternalLinkage, "magic_asr_padding_func", &M);
 226     func_padding_func->setCallingConv(CallingConv::C);
 227     BasicBlock* bb = BasicBlock::Create(M.getContext(), "",func_padding_func,0);
 228
 229     ConstantInt* const_int32_0 = ConstantInt::get(M.getContext(), APInt(32, StringRef("0"), 10));
 230     ConstantInt* const_int32_1 = ConstantInt::get(M.getContext(), APInt(32, StringRef("1"), 10));
 231
 232     AllocaInst* ptr_x = new AllocaInst(IntegerType::get(M.getContext(), 32), "x", bb);
 233     ptr_x->setAlignment(4);
 234
 235     StoreInst* void_1 = new StoreInst(const_int32_0, ptr_x, true, bb);
 236     void_1->setAlignment(4);
 237
 238     for(int i=0; i< n_ops; i++){
 239         LoadInst* load_x = new LoadInst(ptr_x, "", true, bb);
 240         load_x->setAlignment(4);
 241
 242         BinaryOperator* add_x = BinaryOperator::Create(Instruction::Add, load_x, const_int32_1, "", bb);
 243
 244         StoreInst* void_2 = new StoreInst(add_x, ptr_x, true, bb);
 245         void_2->setAlignment(4);
 246     }
 247
 248     ReturnInst::Create(M.getContext(), bb);
 249
 250     return func_padding_func;
 251 }
 252
 253 StringRef getStringRefFromInt(int i){
 254     std::stringstream stm;
 255     stm << i;
 256     return StringRef(*new std::string(stm.str()));
 257 }
 258
 259 bool ASRPass::runOnModule(Module &M) {
 260
 261     Module::GlobalListType &globalList = M.getGlobalList();
 262     Module::FunctionListType &functionList = M.getFunctionList();
 263     int runtime_seed = seed;
 264
 265     Function *magicEntryPointFunc = M.getFunction(MAGIC_ENTRY_POINT);
 266     if( !magicEntryPointFunc ){
 267         //if no valid entry point, we are not compiling a valid program, skip pass
 268         return false;
 269     }
 270
 271     Function *magicInitFunc = M.getFunction(MAGIC_INIT_FUNC_NAME);
 272     if( !magicInitFunc ){
 273         outs() << "Error: no " << MAGIC_INIT_FUNC_NAME << "() found";
 274         exit(1);
 275     }
 276
 277     {
 278         // get random seed number, or use the current time if the seed number is set to 0.
 279         if(!seed){
 280             seed = time(NULL);
 281         }
 282         srand(seed);
 283
 284     }{
 285
 286         /* Randomly offset and permutate list of global variables, and insert random padding between neighbouring global variables */
 287
 288         std::vector<unsigned> pg(globalList.size());
 289         fillPermutationGenerator(pg);
 290
 291         for(unsigned i=0; i < pg.size(); i++){
 292             Module::global_iterator it = globalList.begin();
 293             // get the next random global variable
 294             ADVANCE_ITERATOR(it, pg[i]);
 295             // skip certain variables
 296             if(it->getName().startswith("llvm.")
 297                 || it->getLinkage() == GlobalValue::ExternalWeakLinkage){
 298                 continue;
 299             }
 300             if(it->getLinkage() != GlobalValue::ExternalLinkage && it->getName().compare("environ")){
 301                 // This prevents most public global variables (common linkage, but not external linkage) to be kept in the same order
 302                 it->setLinkage(GlobalValue::InternalLinkage);
 303             }
 304             if(gv_do_permutate){
 305                 // randomize the order of variables, by removing the global variable, and putting it at the end of globalList
 306                 GlobalVariable *gv = globalList.remove(it);
 307                 globalList.push_back(gv);
 308                 it = --globalList.end();
 309             }
 310             // put a padding variable between each two adjacent global variables, and place a big offset before the first global variable
 311             int max_padding = i == 0 ? gv_max_offset : gv_max_padding;
 312             if(max_padding > 0){
 313                 create_padding_gv(M, it, (rand () % max_padding) + 1);
 314             }
 315         }
 316
 317     }{
 318
 319         /* Randomly offset and permutate function list, and insert random padding between neighbouring functions. */
 320
 321         std::vector<unsigned> pg(functionList.size());
 322         fillPermutationGenerator(pg);
 323
 324         for(unsigned i=0; i < pg.size(); i++){
 325             Module::iterator it = functionList.begin();
 326             if(func_do_permutate){
 327                 /* randomize the order of functions, just like we did with the global variables if permutions is disabled, we end up with the same order of functions */
 328                 ADVANCE_ITERATOR(it, pg[i]);
 329             }
 330             Function *F = functionList.remove(it);
 331             functionList.push_back(F);
 332             /* place a padding function at the end of the function list, behind the current function */
 333             int max_padding = i == 0 ? func_max_offset : func_max_padding;
 334             if(max_padding > 0){
 335                 create_padding_func(M, (rand () % (max_padding/2)) + (max_padding/2));
 336             }
 337         }
 338
 339     }{
 340
 341
 342         /* permutate and pad local function variables, and create dynamically randomized stack and stack frame offsets */
 343
 344         for (Module::iterator it = functionList.begin(); it != functionList.end(); ++it) {
 345             Function *F = it;
 346
 347             /* skip certain functions */
 348             if(F->getBasicBlockList().size() == 0){
 349                 continue;
 350             }
 351             if(MAGIC_IS_MAGIC_FUNC(M, F)){
 352                 continue;
 353             }
 354             if(!F->getName().compare("rand")){
 355                 continue;
 356             }
 357
 358
 359             /* find all allocation instructions in order to pad them. */
 360
 361             /* Helper vectors to store all alloca instructions temporarily.
 362              * Make two collections, depending on whether the address of the variable is taken and used as a pointer.
 363              * (Because pointer dereferencing, buffer overflow, etc. add extra risks to those variables that have their addresses taken)
 364              * We order the allocation instructions as follows:
 365              * - First, we allocate the ones that don't have their address taken, only permutated.
 366              * - Then, we allocate an stack frame offset (dynamically randomly sized).
 367              * - After the stack frame offset, we allocate those that have their address taken, with permutation and padding.
 368              * Because the majority doesn't have its address taken, most variables are allocated in the first basic block, before the stack frame offset allocation.
 369              * This gives the extra advantages that those allocations are folded into the prolog/epilog code by the code generator, for extra performance.
 370              * (See AllocaInst::isStaticAlloca() in llvm/Instructions.h)
 371              * */
 372             std::vector<Instruction *> allocaAddressTaken, allocaNoAddressTaken;
 373
 374             /* Only the first basic block contains alloca instructions */
 375             BasicBlock *BB =  F->getBasicBlockList().begin();
 376
 377             /* with each iteration, one of these integers will be incremented/decremented */
 378             unsigned bb_size = BB->getInstList().size();
 379             unsigned pos = 0;
 380             while(pos < bb_size){
 381
 382                 /* check if instruction at position <pos> is an allocation instruction.
 383                  * If, so remove and put in one of the helper vectors
 384                  * */
 385
 386                 BasicBlock::iterator it = BB->getInstList().begin();
 387                 /* move to current position in instruction list */
 388                 ADVANCE_ITERATOR(it, pos);
 389                 Instruction *inst = &(*it);
 390                 if (AllocaInst *allocaInst = dyn_cast<AllocaInst>(inst)){
 391                     /* this is an allocation instruction. insert it at the front of of the right helper vector
 392                      * (last found allocation instruction will be at the front), and remove it from the basic block.
 393                      * */
 394                     int hasAddressTaken = 0;
 395                     for (Value::user_iterator UI = allocaInst->user_begin(), E = allocaInst->user_end(); UI != E; ++UI) {
 396
 397                         /* Loop through all the Uses of this allocation function. */
 398
 399                         User *U = *UI;
 400                         if(dyn_cast<LoadInst>(U) || dyn_cast<StoreInst>(U)){
 401                             /* This is a load or store instruction, which does not
 402                              * indicate that a pointer of this variable is generated
 403                              * */
 404                             continue;
 405                         }else if(CallInst *cInst = dyn_cast<CallInst>(U)){
 406                             if(cInst->getCalledFunction() && MAGIC_IS_MAGIC_FUNC(M, cInst->getCalledFunction())){
 407                                 /* This is a function call instruction, but this
 408                                  * concerns a magic library function, so it does not count as a generated pointer.
 409                                  * Any other functions calls would have set hasAddressTaken to 1 */
 410                                 continue;
 411                             }
 412                         }
 413                         /* This instruction will (likely) create a pointer, because it is not a load, store or magic-function-call instruction */
 414                         hasAddressTaken = 1;
 415                         break;
 416                     }
 417
 418                     /* Put the alloca instruction in the right helper vector, and remove from the basic block. */
 419                     if(hasAddressTaken){
 420                         allocaAddressTaken.insert(allocaAddressTaken.begin(), it);
 421                     }else{
 422                         allocaNoAddressTaken.insert(allocaNoAddressTaken.begin(), it);
 423                     }
 424                     it->removeFromParent();
 425                     bb_size--;
 426                 }else{
 427                     pos++;
 428                 }
 429             }
 430
 431             /* Permutate and pad the alloca instructions whose addresses are taken. */
 432
 433             std::vector<unsigned> pg(allocaAddressTaken.size());
 434             fillPermutationGenerator(pg);
 435             for(unsigned i=0; i<pg.size(); i++){
 436                 /* get the iterator for the first element of the helper vector */
 437                 std::vector<Instruction *>::iterator it = allocaAddressTaken.begin();
 438                 if(stackframe_do_permutate){
 439                     /* get the iterator for the next random element. When permutation is disabled, it keeps pointing to the first element */
 440                     ADVANCE_ITERATOR(it, pg[i]);
 441                 }
 442                 /* put the variable at the front of the basic block, and remove it from the helper vector.
 443                  * This way, the variable that is added last will be at the front
 444                  * */
 445                 BB->getInstList().push_front(*it);
 446                 allocaAddressTaken.erase(it);
 447
 448                 /* put a padding variable between each two adjacent local variables
 449                  * this is done by inserting a padding var at the front each time a
 450                  * var has been put at the front with push_front().
 451                  * */
 452                 int max_padding = (i==pg.size()-1 ? 0 : stackframe_max_padding);
 453                 if(max_padding > 0){
 454                     create_padding_lv(M, BB->getInstList().begin(), (rand () % max_padding) + 1);
 455                 }
 456             }
 457
 458
 459             /* Create a global stack offset, and an offset for each stack frame. Both have a dynamic random size */
 460
 461             /* Determine if we must pad or offset, and how much */
 462             int max_offset, do_offset=1;
 463             if(F->getName().equals(MAGIC_ENTRY_POINT)){
 464                 if(!stack_do_offset){
 465                     do_offset=0;
 466                 }
 467                 /* give the entry function (first function) a large offset instead of an padding */
 468                 max_offset = stack_max_offset;
 469             }else{
 470                 if(!stackframe_do_offset){
 471                     do_offset=0;
 472                 }
 473                 max_offset = stackframe_max_offset;
 474             }
 475
 476             /* Create a new block before the first block. Now, all the variable allocations whose addresses are taken are no longer
 477              * in the first block, so CallInst::isStaticAlloca() does no longer apply to them.
 478              * When isStaticAlloca() == true, the code generator will fold it into the prolog/epilog code, so it is basically free.
 479              * This means that we now get less efficient code.
 480              * This is necessary to prevent the variables whose address is taken from being allocated before the stack frame offset is allocated.
 481              * Alternatively, we could allocate before the function call, instead of after. */
 482
 483             BasicBlock *OldFirstBB = F->getBasicBlockList().begin();
 484             BasicBlock *NewFirstBB = BasicBlock::Create(M.getContext(), "newBB", F, OldFirstBB);
 485
 486
 487             /* Permutate and insert the allocation instructions whose addresses are NOT taken into the new first block (dont apply padding).
 488              * These must be allocated before the stack frame offset is allocated. */
 489
 490             pg = std::vector<unsigned>(allocaNoAddressTaken.size());
 491             fillPermutationGenerator(pg);
 492             for(unsigned i=0; i<pg.size(); i++){
 493                 /* get the iterator for the first element of the helper vector */
 494                 std::vector<Instruction *>::iterator it = allocaNoAddressTaken.begin();
 495                 if(stackframe_do_permutate){
 496                     /* get the iterator for the next random element. When permutation is disabled, it keeps pointing to the first element */
 497                     ADVANCE_ITERATOR(it, pg[i]);
 498                 }
 499                 /* put the variable at the front of the basic block, and remove it from the helper vector.
 500                  * This way, the variable that is added last will be at the front
 501                  * */
 502                 NewFirstBB->getInstList().push_front(*it);
 503                 allocaNoAddressTaken.erase(it);
 504             }
 505
 506             if(do_offset){
 507                 if(stackframe_static_padding) {
 508                     if(max_offset > 0) {
 509                         new AllocaInst(IntegerType::get(M.getContext(), 8), ConstantInt::get(M.getContext(), APInt(64, (rand() % max_offset) + 1, 10)), "", NewFirstBB);
 510                     }
 511                 }
 512                 else {
 513                     /* Now insert a dynamically randomized stackframe offset */
 514                     Function *RandFunc = M.getFunction("rand");
 515                     assert(RandFunc != NULL);
 516
 517                     /* Call rand() */
 518                     std::vector<Value*> args;
 519                     CallInst* RandFuncCall = PassUtil::createCallInstruction(RandFunc, args, "", NewFirstBB);
 520                     Instruction *nextInst = RandFuncCall;
 521
 522                     if(max_offset > 0){
 523                         /* limit the rand value: rand() % max_offet */
 524                         ConstantInt* max_offset_const = ConstantInt::get(M.getContext(), APInt(32, max_offset, 10));
 525                         BinaryOperator *Remainder = BinaryOperator::Create(Instruction::SRem, RandFuncCall, max_offset_const, "", NewFirstBB);
 526                         Remainder->removeFromParent();
 527                         Remainder->insertAfter(RandFuncCall);
 528                         nextInst = Remainder;
 529                     }
 530
 531                     /* Minimum rand value must be 1, so increment it. */
 532                     ConstantInt* One = ConstantInt::get(M.getContext(), APInt(32, StringRef("1"), 10));
 533                     BinaryOperator* AddOne = BinaryOperator::Create(Instruction::Add, nextInst, One, "", NewFirstBB);
 534                     AddOne->removeFromParent();
 535                     AddOne->insertAfter(nextInst);
 536
 537                     /* Allocate the offset/padding */
 538                     AllocaInst* allocaInstruction = new AllocaInst(IntegerType::get(M.getContext(), 8), AddOne, "", NewFirstBB);
 539                     allocaInstruction->removeFromParent();
 540                     allocaInstruction->insertAfter(AddOne);
 541
 542                     /* Inline the rand() call. */
 543                     InlineFunctionInfo IFI;
 544                     InlineFunction(RandFuncCall, IFI);
 545                 }
 546             }
 547
 548             /* Go to the old first block */
 549             BranchInst *br =  BranchInst::Create (OldFirstBB, NewFirstBB);
 550             br->setSuccessor(0, OldFirstBB);
 551
 552             /* Static stack frame padding does not really need 2 basic blocks, but it may need call site instrumentation. */
 553             if(stackframe_static_padding) {
 554                 bool ret = MergeBlockIntoPredecessor(OldFirstBB, this);
 555                 assert(ret);
 556
 557                 if(stackframe_caller_padding && max_offset > 0) {
 558                     std::vector<User*> Users(F->user_begin(), F->user_end());
 559                     while (!Users.empty()) {
 560                         User *U = Users.back();
 561                         Users.pop_back();
 562                         if (Instruction *I = dyn_cast<Instruction>(U)) {
 563                             Function *parent = I->getParent()->getParent();
 564                             /* XXX Skipping MAGIC_ENTRY_POINT shouldn't be necessary. Check why. */
 565                             /* ..the reason is that main() typically contains the message loop, which loops
 566                              * forever making calls. These calls are getting padded, and AllocaInst causes a
 567                              * stack pointer adjustment every time a call is made. This stack memory is never
 568                              * released, since the function never returns. The result is that we eventually
 569                              * run out of stack. Since MINIX3 also uses user-level threads these days, the
 570                              * problem is not limited to main(), and for this reason I have disabled caller
 571                              * padding by default. -dcvmoole
 572                              */
 573                             if(MAGIC_IS_MAGIC_FUNC(M, parent) || parent->getName().equals(MAGIC_ENTRY_POINT)) {
 574                                 continue;
 575                             }
 576                             CallSite CS = PassUtil::getCallSiteFromInstruction(I);
 577                             if(!CS.getInstruction()) {
 578                                 continue;
 579                             }
 580                             Function *calledFunction = getCalledFunctionFromCS(CS);
 581                             if (CS.getInstruction() && !CS.arg_empty() && (calledFunction == F || calledFunction == NULL)) {
 582                                 new AllocaInst(IntegerType::get(M.getContext(), 8), ConstantInt::get(M.getContext(), APInt(64, (rand() % max_offset) + 1, 10)), "", I);
 583                             }
 584                         }
 585                     }
 586                 }
 587             }
 588
 589             /* Basic block shifting. */
 590             if(func_max_bb_shift > 0) {
 591                 Instruction *I;
 592                 PassUtil::getAllocaInfo(F, NULL, &I);
 593                 BasicBlock *firstBB = F->getBasicBlockList().begin();
 594                 BasicBlock *splitBB = firstBB->splitBasicBlock(I, "split");
 595                 BasicBlock *dummyBB = BasicBlock::Create(M.getContext(), "dummy", F, splitBB);
 596                 if(!stackframe_caller_padding) {
 597                     firstBB = NewFirstBB;
 598                 }
 599
 600                 /* Fill the dummy basic block with dummy instructions (using the prefetch intrinsic to emulate nop instructions), to shift the next basic block. */
 601                 Function *prefetchIntrinsic = PassUtil::getIntrinsicFunction(M, Intrinsic::prefetch);
 602                 std::vector<Value*> args;
 603                 args.push_back(ConstantPointerNull::get(PointerType::get(IntegerType::get(M.getContext(), 8), 0)));
 604                 args.push_back(ConstantInt::get(M.getContext(), APInt(32, 0)));
 605                 args.push_back(ConstantInt::get(M.getContext(), APInt(32, 0)));
 606 #if LLVM_VERSION >= 30
 607                 args.push_back(ConstantInt::get(M.getContext(), APInt(32, 0)));
 608 #endif
 609                 unsigned shift = (rand() % func_max_bb_shift) + 1;
 610                 do {
 611                     PassUtil::createCallInstruction(prefetchIntrinsic, args, "", dummyBB);
 612                     shift--;
 613                 } while(shift > 0);
 614                 BranchInst *br =  BranchInst::Create (splitBB, dummyBB);
 615                 br->setSuccessor(0, splitBB);
 616
 617                 /* Place an opaque conditional branch (always unconditionally skips the dummy basic block). */
 618                 Function *frameAddrIntrinsic = PassUtil::getIntrinsicFunction(M, Intrinsic::frameaddress);
 619                 std::vector<Value*> frameAddrArgs;
 620                 frameAddrArgs.push_back(ConstantInt::get(M.getContext(), APInt(32, 0)));
 621                 Value *frameAddr = PassUtil::createCallInstruction(frameAddrIntrinsic, frameAddrArgs, "", firstBB->getTerminator());
 622                 TerminatorInst *OldTI = firstBB->getTerminator();
 623                 IRBuilder<> Builder(firstBB);
 624                 ICmpInst* ExtraCase = new ICmpInst(OldTI, ICmpInst::ICMP_EQ, frameAddr, ConstantPointerNull::get(PointerType::get(IntegerType::get(M.getContext(), 8), 0)), "");
 625                 Builder.CreateCondBr(ExtraCase, dummyBB, splitBB);
 626                 OldTI->eraseFromParent();
 627             }
 628         }
 629
 630     }{
 631
 632
 633 #define __X(VAR) __XX(VAR)
 634 #define __XX(VAR) #VAR
 635
 636         /* heap and map padding */
 637
 638         {
 639
 640             /* Inject magic init call at the beginning of magic entry point function (before any allocaInsts).
 641              * Magic_init will return immediately if called for the second time, so both the magic pass and
 642              * this pass can insert call instructions into main
 643              * */
 644             std::vector<Value*> args;
 645             PassUtil::createCallInstruction(magicInitFunc, args, "", magicEntryPointFunc->getBasicBlockList().begin()->begin());
 646
 647         }{
 648
 649             /* set the global variables */
 650
 651             Function *magicDataInitFunc = M.getFunction(MAGIC_DATA_INIT_FUNC_NAME);
 652             if(!magicDataInitFunc){
 653                 outs() <<"Error: no " << MAGIC_DATA_INIT_FUNC_NAME << "() found";
 654                 exit(1);
 655             }
 656             Instruction *magicArrayBuildFuncInst = magicDataInitFunc->back().getTerminator();
 657
 658             GlobalVariable* magicRootVar = M.getNamedGlobal(MAGIC_ROOT_VAR_NAME);
 659             if(!magicRootVar) {
 660                 outs() << "Error: no " << MAGIC_ROOT_VAR_NAME << " variable found";
 661                 exit(1);
 662             }
 663
 664             Value *seedValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_SEED);
 665             if(!seedValue) {
 666                 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_SEED << " field found";
 667                 exit(1);
 668             }
 669             new StoreInst(ConstantInt::get(M.getContext(), APInt(32, runtime_seed)), seedValue, false, magicArrayBuildFuncInst);
 670
 671             Value *heapMapPermutateValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAP_DO_PERMUTATE);
 672             if(!heapMapPermutateValue) {
 673                 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAP_DO_PERMUTATE << " field found";
 674                 exit(1);
 675             }
 676             new StoreInst(ConstantInt::get(M.getContext(), APInt(32, heap_map_do_permutate)), heapMapPermutateValue, false, magicArrayBuildFuncInst);
 677
 678
 679             Value *heapOffsetValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_OFFSET);
 680             if(!heapOffsetValue) {
 681                 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_OFFSET << " field found";
 682                 exit(1);
 683             }
 684             new StoreInst(ConstantInt::get(M.getContext(), APInt(32, heap_max_offset)), heapOffsetValue, false, magicArrayBuildFuncInst);
 685
 686             Value *heapPaddingValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_PADDING);
 687             if(!heapPaddingValue) {
 688                 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_PADDING << " field found";
 689                 exit(1);
 690             }
 691             new StoreInst(ConstantInt::get(M.getContext(), APInt(32, heap_max_padding)), heapPaddingValue, false, magicArrayBuildFuncInst);
 692
 693
 694             Value *mapOffsetValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_OFFSET_PAGES);
 695             if(!mapOffsetValue) {
 696                 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_OFFSET_PAGES << " field found";
 697                 exit(1);
 698             }
 699             new StoreInst(ConstantInt::get(M.getContext(), APInt(32, map_max_offset_pages)), mapOffsetValue, false, magicArrayBuildFuncInst);
 700
 701             Value *mapPaddingValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_PADDING_PAGES);
 702             if(!mapPaddingValue) {
 703                 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_PADDING_PAGES << " field found";
 704                 exit(1);
 705             }
 706             new StoreInst(ConstantInt::get(M.getContext(), APInt(32, map_max_padding_pages)), mapPaddingValue, false, magicArrayBuildFuncInst);
 707
 708
 709
 710         }
 711
 712     }
 713
 714     return true;
 715 }
 716
 717 } // end namespace
 718
 719 char ASRPass::ID = 1;
 720 static RegisterPass<ASRPass> AP("asr", "Address Space Randomization Pass");