subroutines.c

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