subroutines.c

   1 /**
   2  * Author: Humberto Naves (hsnaves@gmail.com)
   3  */
   4
   5 #include "code.h"
   6 #include "utils.h"
   7
   8
   9 static
  10 void mark_reachable (struct code *c, struct location *loc)
  11 {
  12   uint32 remaining = 1 + ((c->end->address - loc->address) >> 2);
  13   for (; remaining--; loc++) {
  14     if (loc->reachable == LOCATION_REACHABLE) break;
  15     loc->reachable = LOCATION_REACHABLE;
  16
  17     if (!loc->insn) return;
  18
  19     if (loc->insn->flags & INSN_JUMP) {
  20       if (remaining > 0) {
  21         if (loc[1].reachable != LOCATION_REACHABLE)
  22           loc[1].reachable = LOCATION_DELAY_SLOT;
  23       }
  24
  25       if (loc->target)
  26         mark_reachable (c, loc->target);
  27
  28       if (loc->cswitch) {
  29         if (loc->cswitch->checked) {
  30           element el = list_head (loc->cswitch->references);
  31           while (el) {
  32             struct location *target = element_getvalue (el);
  33             mark_reachable (c, target);
  34             if (!target->references)
  35               target->references = list_alloc (c->lstpool);
  36             if (target->cswitch != loc->cswitch)
  37               list_inserttail (target->references, loc);
  38             target->cswitch = loc->cswitch;
  39             el = element_next (el);
  40           }
  41         }
  42       }
  43
  44       if ((remaining == 0) || !(loc->insn->flags & (INSN_LINK | INSN_WRITE_GPR_D)))
  45         return;
  46
  47       loc++;
  48       remaining--;
  49     } else if (loc->insn->flags & INSN_BRANCH) {
  50       if (remaining > 0) {
  51         if (loc[1].reachable != LOCATION_REACHABLE)
  52           loc[1].reachable = LOCATION_DELAY_SLOT;
  53       }
  54
  55       if (loc->target) {
  56         mark_reachable (c, loc->target);
  57       }
  58
  59       if ((remaining == 0) || (loc->branchalways && !(loc->insn->flags & INSN_LINK)))
  60         return;
  61
  62       loc++;
  63       remaining--;
  64     }
  65   };
  66 }
  67
  68 static
  69 void new_subroutine (struct code *c, struct location *loc, struct prx_function *imp, struct prx_function *exp)
  70 {
  71   struct subroutine *sub = loc->sub;
  72
  73   if (!sub) {
  74     sub = fixedpool_alloc (c->subspool);
  75     sub->begin = loc;
  76     sub->code = c;
  77     sub->whereused = list_alloc (c->lstpool);
  78     sub->callblocks = list_alloc (c->lstpool);
  79     loc->sub = sub;
  80   }
  81   if (imp) sub->import = imp;
  82   if (exp) sub->export = exp;
  83
  84   if (sub->import && sub->export) {
  85     sub->haserror = TRUE;
  86     error (__FILE__ ": location 0x%08X is both import and export", loc->address);
  87   }
  88
  89   mark_reachable (c, loc);
  90 }
  91
  92 static
  93 void extract_from_relocs (struct code *c)
  94 {
  95   uint32 i, tgt;
  96
  97   i = prx_findreloc (c->file, c->baddr);
  98   for (; i < c->file->relocnum; i++) {
  99     struct location *loc;
 100     struct prx_reloc *rel = &c->file->relocs[i];
 101
 102     tgt = (rel->target - c->baddr) >> 2;
 103     if (tgt >= c->numopc) continue;
 104
 105     if (rel->target & 0x03) {
 106       error (__FILE__ ": relocation not word aligned 0x%08X", rel->target);
 107       continue;
 108     }
 109
 110     loc = &c->base[tgt];
 111
 112     if (rel->type == R_MIPSX_JAL26) {
 113       new_subroutine (c, loc, NULL, NULL);
 114     } else if (rel->type == R_MIPS_26) {
 115       struct location *calledfrom;
 116       uint32 ctgt;
 117
 118       if (rel->vaddr < c->baddr) continue;
 119       if (rel->vaddr & 0x03) {
 120         error (__FILE__ ": relocation address not word aligned 0x%08X", rel->vaddr);
 121         continue;
 122       }
 123
 124       ctgt = (rel->vaddr - c->baddr) >> 2;
 125       if (ctgt >= c->numopc) continue;
 126
 127       calledfrom = &c->base[ctgt];
 128       if (calledfrom->insn->insn == I_JAL) {
 129         new_subroutine (c, loc, NULL, NULL);
 130       }
 131     } else if (rel->type == R_MIPS_32) {
 132       if (!loc->cswitch)
 133         new_subroutine (c, loc, NULL, NULL);
 134     } else if (rel->type == R_MIPS_HI16 || rel->type == R_MIPSX_HI16) {
 135       /* TODO: is this OK to do? */
 136       if (!loc->cswitch)
 137         new_subroutine (c, loc, NULL, NULL);
 138     }
 139   }
 140 }
 141
 142 static
 143 void extract_from_exports (struct code *c)
 144 {
 145   uint32 i, j, tgt;
 146
 147   for (i = 0; i < c->file->modinfo->numexports; i++) {
 148     struct prx_export *exp;
 149
 150     exp = &c->file->modinfo->exports[i];
 151     for (j = 0; j < exp->nfuncs; j++) {
 152       struct prx_function *func = &exp->funcs[j];
 153       struct location *loc;
 154
 155       tgt = (func->vaddr - c->baddr) >> 2;
 156       if (func->vaddr < c->baddr ||
 157           tgt >= c->numopc) {
 158         error (__FILE__ ": invalid exported function");
 159         continue;
 160       }
 161
 162       loc = &c->base[tgt];
 163       new_subroutine (c, loc, NULL, func);
 164       func->pfunc = loc->sub;
 165     }
 166   }
 167 }
 168
 169 static
 170 void extract_from_imports (struct code *c)
 171 {
 172   uint32 i, j, tgt;
 173
 174   for (i = 0; i < c->file->modinfo->numimports; i++) {
 175     struct prx_import *imp;
 176
 177     imp = &c->file->modinfo->imports[i];
 178     for (j = 0; j < imp->nfuncs; j++) {
 179       struct prx_function *func = &imp->funcs[j];
 180       struct location *loc;
 181
 182       tgt = (func->vaddr - c->baddr) >> 2;
 183       if (func->vaddr < c->baddr ||
 184           tgt >= c->numopc) {
 185         error (__FILE__ ": invalid imported function");
 186         continue;
 187       }
 188
 189       loc = &c->base[tgt];
 190       new_subroutine (c, loc, func, NULL);
 191       func->pfunc = loc->sub;
 192       loc->sub->numregargs = func->numargs;
 193     }
 194   }
 195 }
 196
 197 static
 198 struct subroutine *find_sub (struct code *c, struct location *loc)
 199 {
 200   do {
 201     if (loc->sub) return loc->sub;
 202   } while (loc-- != c->base);
 203   return NULL;
 204 }
 205
 206 static
 207 void extract_hidden_subroutines (struct code *c)
 208 {
 209   struct subroutine *cursub = NULL;
 210   uint32 i;
 211   int changed = TRUE;
 212
 213   /* TODO: improve the hidden subroutine detection algorithm */
 214   while (changed) {
 215     changed = FALSE;
 216     for (i = 0; i < c->numopc; i++) {
 217       struct location *loc = &c->base[i];
 218       if (loc->sub) cursub = loc->sub;
 219       if (loc->reachable == LOCATION_UNREACHABLE) continue;
 220
 221       if (loc->target) {
 222         struct location *target;
 223         struct subroutine *targetsub;
 224
 225         target = loc->target;
 226         targetsub = find_sub (c, target);
 227
 228         if (!target->sub && (targetsub != cursub)) {
 229           report (__FILE__ ": hidden subroutine at 0x%08X (called by 0x%08X)\n", target->address, loc->address);
 230           new_subroutine (c, target, NULL, NULL);
 231           changed = TRUE;
 232         }
 233       }
 234     }
 235   }
 236 }
 237
 238
 239
 240 static
 241 void delimit_borders (struct code *c)
 242 {
 243   struct subroutine *prevsub = NULL;
 244   uint32 i;
 245
 246   for (i = 0; i < c->numopc; i++) {
 247     if (c->base[i].sub) {
 248       list_inserttail (c->subroutines, c->base[i].sub);
 249       if (prevsub) {
 250         prevsub->end = &c->base[i - 1];
 251       }
 252       prevsub = c->base[i].sub;
 253     } else {
 254       c->base[i].sub = prevsub;
 255     }
 256   }
 257   if (prevsub) {
 258     prevsub->end = &c->base[i - 1];
 259   }
 260 }
 261
 262
 263 static
 264 void check_switches (struct subroutine *sub)
 265 {
 266   struct location *loc;
 267   loc = sub->begin;
 268   do {
 269     if (!loc->cswitch) continue;
 270     if (loc->cswitch->jumplocation == loc) {
 271       element el;
 272       int haserror = FALSE;
 273
 274       el = list_head (loc->cswitch->references);
 275       while (el) {
 276         struct location *target = element_getvalue (el);
 277         if (target->sub != loc->sub) haserror = TRUE;
 278         target->cswitch = NULL;
 279         el = element_next (el);
 280       }
 281
 282       if (haserror) {
 283         report (__FILE__ ": invalid switch at 0x%08X\n", loc->address);
 284         fixedpool_free (sub->code->switchpool, loc->cswitch);
 285         loc->cswitch = NULL;
 286       } else {
 287         loc->cswitch->checked = TRUE;
 288         if (loc->reachable == LOCATION_REACHABLE) {
 289           loc->reachable = LOCATION_UNREACHABLE;
 290           mark_reachable (sub->code, loc);
 291         }
 292       }
 293     }
 294   } while (loc++ != sub->end);
 295 }
 296
 297 static
 298 void check_subroutine (struct subroutine *sub)
 299 {
 300   struct location *loc;
 301   loc = sub->begin;
 302
 303   if ((sub->end->address - sub->begin->address) < 4) {
 304     error (__FILE__ ": subroutine is too short: 0x%08X", sub->begin->address);
 305     sub->haserror = TRUE;
 306     return;
 307   }
 308
 309   do {
 310     if (loc->reachable == LOCATION_UNREACHABLE) continue;
 311
 312     if (loc->error != ERROR_NONE) {
 313       switch (loc->error) {
 314       case ERROR_INVALID_OPCODE:
 315         error (__FILE__ ": invalid opcode 0x%08X at 0x%08X (sub: 0x%08X)", loc->opc, loc->address, sub->begin->address);
 316         sub->haserror = TRUE;
 317         break;
 318       case ERROR_TARGET_OUTSIDE_FILE:
 319         error (__FILE__ ": branch/jump outside file at 0x%08X (sub: 0x%08X)", loc->address, sub->begin->address);
 320         sub->haserror = TRUE;
 321         break;
 322       case ERROR_DELAY_SLOT:
 323         error (__FILE__ ": delay slot error at 0x%08X (sub: 0x%08X)", loc->address, sub->begin->address);
 324         sub->haserror = TRUE;
 325         break;
 326       case ERROR_ILLEGAL_BRANCH:
 327         error (__FILE__ ": illegal branch at 0x%08X (sub: 0x%08X)", loc->address, sub->begin->address);
 328         sub->haserror = TRUE;
 329         break;
 330       case ERROR_NONE:
 331         break;
 332       }
 333     }
 334
 335     if (sub->haserror) continue;
 336
 337
 338     if (loc->target) {
 339       if (!loc->target->references)
 340         loc->target->references = list_alloc (sub->code->lstpool);
 341       list_inserttail (loc->target->references, loc);
 342     }
 343   } while (loc++ != sub->end);
 344   loc--;
 345
 346   if (loc->reachable == LOCATION_UNREACHABLE) return;
 347   loc--;
 348
 349   if ((loc->insn->flags & (INSN_JUMP | INSN_LINK | INSN_WRITE_GPR_D)) == INSN_JUMP)
 350     return;
 351
 352   if ((loc->insn->flags & (INSN_BRANCH | INSN_LINK)) == INSN_BRANCH && loc->branchalways)
 353     return;
 354
 355   error (__FILE__ ": subroutine at 0x%08X (end 0x%08X) has no finish", sub->begin->address, sub->end->address);
 356   sub->haserror = TRUE;
 357 }
 358
 359 void extract_subroutines (struct code *c)
 360 {
 361   element el;
 362
 363   c->subroutines = list_alloc (c->lstpool);
 364
 365   extract_from_exports (c);
 366   extract_from_imports (c);
 367   extract_from_relocs (c);
 368
 369   if (!c->base->sub) {
 370     error (__FILE__ ": creating artificial subroutine at address 0x%08X", c->baddr);
 371     new_subroutine (c, c->base, NULL, NULL);
 372   }
 373
 374   extract_hidden_subroutines (c);
 375   delimit_borders (c);
 376
 377
 378   el = list_head (c->subroutines);
 379   while (el) {
 380     struct subroutine *sub = element_getvalue (el);
 381     if (!sub->import) {
 382       check_switches (sub);
 383       check_subroutine (sub);
 384
 385       if (!sub->haserror) {
 386         sub->status |= SUB_STAT_EXTRACTED;
 387         extract_cfg (sub);
 388       }
 389
 390       if (!sub->haserror) {
 391         sub->status |= SUB_STAT_CFG_EXTRACTED;
 392         extract_operations (sub);
 393       }
 394
 395       if (!sub->haserror) {
 396         sub->status |= SUB_STAT_OPERATIONS_EXTRACTED;
 397       }
 398     }
 399     el = element_next (el);
 400   }
 401 }
 402