sys/src/libmach/sym.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <bio.h>
   4 #include <mach.h>
   5
   6 #define HUGEINT 0x7fffffff
   7 #define NNAME   20              /* a relic of the past */
   8
   9 typedef struct txtsym Txtsym;
  10 typedef struct file File;
  11 typedef struct hist Hist;
  12
  13 struct txtsym {                         /* Text Symbol table */
  14         int     n;                      /* number of local vars */
  15         Sym     **locals;               /* array of ptrs to autos */
  16         Sym     *sym;                   /* function symbol entry */
  17 };
  18
  19 struct hist {                           /* Stack of include files & #line directives */
  20         char    *name;                  /* Assumes names Null terminated in file */
  21         long    line;                   /* line # where it was included */
  22         long    offset;                 /* line # of #line directive */
  23 };
  24
  25 struct file {                           /* Per input file header to history stack */
  26         uvlong  addr;                   /* address of first text sym */
  27         union {
  28                 Txtsym  *txt;           /* first text symbol */
  29                 Sym     *sym;           /* only during initilization */
  30         };
  31         int     n;                      /* size of history stack */
  32         Hist    *hist;                  /* history stack */
  33 };
  34
  35 static  int     debug = 0;
  36
  37 static  Sym     **autos;                /* Base of auto variables */
  38 static  File    *files;                 /* Base of file arena */
  39 static  int     fmax;                   /* largest file path index */
  40 static  Sym     **fnames;               /* file names path component table */
  41 static  Sym     **globals;              /* globals by addr table */
  42 static  Hist    *hist;                  /* base of history stack */
  43 static  int     isbuilt;                /* internal table init flag */
  44 static  long    nauto;                  /* number of automatics */
  45 static  long    nfiles;                 /* number of files */
  46 static  long    nglob;                  /* number of globals */
  47 static  long    nhist;                  /* number of history stack entries */
  48 static  long    nsym;                   /* number of symbols */
  49 static  int     ntxt;                   /* number of text symbols */
  50 static  uchar   *pcline;                /* start of pc-line state table */
  51 static  uchar   *pclineend;             /* end of pc-line table */
  52 static  uchar   *spoff;                 /* start of pc-sp state table */
  53 static  uchar   *spoffend;              /* end of pc-sp offset table */
  54 static  Sym     *symbols;               /* symbol table */
  55 static  Txtsym  *txt;                   /* Base of text symbol table */
  56 static  uvlong  txtstart;               /* start of text segment */
  57 static  uvlong  txtend;                 /* end of text segment */
  58
  59 static void     cleansyms(void);
  60 static long     decodename(Biobuf*, Sym*);
  61 static short    *encfname(char*);
  62 static int      fline(char*, int, long, Hist*, Hist**);
  63 static void     fillsym(Sym*, Symbol*);
  64 static int      findglobal(char*, Symbol*);
  65 static int      findlocvar(Symbol*, char *, Symbol*);
  66 static int      findtext(char*, Symbol*);
  67 static int      hcomp(Hist*, short*);
  68 static int      hline(File*, short*, long*);
  69 static void     printhist(char*, Hist*, int);
  70 static int      buildtbls(void);
  71 static int      symcomp(void*, void*);
  72 static int      symerrmsg(int, char*);
  73 static int      txtcomp(void*, void*);
  74 static int      filecomp(void*, void*);
  75
  76 /*
  77  *      initialize the symbol tables
  78  */
  79 int
  80 syminit(int fd, Fhdr *fp)
  81 {
  82         Sym *p;
  83         long i, l, size;
  84         vlong vl;
  85         Biobuf b;
  86         int svalsz;
  87
  88         if(fp->symsz == 0)
  89                 return 0;
  90         if(fp->type == FNONE)
  91                 return 0;
  92
  93         cleansyms();
  94         textseg(fp->txtaddr, fp);
  95                 /* minimum symbol record size = 4+1+2 bytes */
  96         symbols = malloc((fp->symsz/(4+1+2)+1)*sizeof(Sym));
  97         if(symbols == 0) {
  98                 werrstr("can't malloc %ld bytes", fp->symsz);
  99                 return -1;
 100         }
 101         Binit(&b, fd, OREAD);
 102         Bseek(&b, fp->symoff, 0);
 103         nsym = 0;
 104         size = 0;
 105         if((fp->_magic && (fp->magic & HDR_MAGIC)) || mach->szaddr == 8)
 106                 svalsz = 8;
 107         else
 108                 svalsz = 4;
 109         for(p = symbols; size < fp->symsz; p++, nsym++) {
 110                 if(svalsz == 8){
 111                         if(Bread(&b, &vl, 8) != 8)
 112                                 return symerrmsg(8, "symbol");
 113                         p->value = beswav(vl);
 114                 }
 115                 else{
 116                         if(Bread(&b, &l, 4) != 4)
 117                                 return symerrmsg(4, "symbol");
 118                         p->value = (u32int)beswal(l);
 119                 }
 120                 if(Bread(&b, &p->type, sizeof(p->type)) != sizeof(p->type))
 121                         return symerrmsg(sizeof(p->value), "symbol");
 122
 123                 i = decodename(&b, p);
 124                 if(i < 0)
 125                         return -1;
 126                 size += i+svalsz+sizeof(p->type);
 127
 128                 /* count global & auto vars, text symbols, and file names */
 129                 switch (p->type) {
 130                 case 'l':
 131                 case 'L':
 132                 case 't':
 133                 case 'T':
 134                         ntxt++;
 135                         break;
 136                 case 'd':
 137                 case 'D':
 138                 case 'b':
 139                 case 'B':
 140                         nglob++;
 141                         break;
 142                 case 'f':
 143                         if(strcmp(p->name, ".frame") == 0) {
 144                                 p->type = 'm';
 145                                 nauto++;
 146                         }
 147                         else if(p->value > fmax)
 148                                 fmax = p->value;        /* highest path index */
 149                         break;
 150                 case 'a':
 151                 case 'p':
 152                 case 'm':
 153                         nauto++;
 154                         break;
 155                 case 'z':
 156                         if(p->value == 1) {             /* one extra per file */
 157                                 nhist++;
 158                                 nfiles++;
 159                         }
 160                         nhist++;
 161                         break;
 162                 default:
 163                         break;
 164                 }
 165         }
 166         if (debug)
 167                 print("NG: %ld NT: %d NF: %d\n", nglob, ntxt, fmax);
 168         if (fp->sppcsz) {                       /* pc-sp offset table */
 169                 spoff = (uchar *)malloc(fp->sppcsz);
 170                 if(spoff == 0) {
 171                         werrstr("can't malloc %ld bytes", fp->sppcsz);
 172                         return -1;
 173                 }
 174                 Bseek(&b, fp->sppcoff, 0);
 175                 if(Bread(&b, spoff, fp->sppcsz) != fp->sppcsz){
 176                         spoff = 0;
 177                         return symerrmsg(fp->sppcsz, "sp-pc");
 178                 }
 179                 spoffend = spoff+fp->sppcsz;
 180         }
 181         if (fp->lnpcsz) {                       /* pc-line number table */
 182                 pcline = (uchar *)malloc(fp->lnpcsz);
 183                 if(pcline == 0) {
 184                         werrstr("can't malloc %ld bytes", fp->lnpcsz);
 185                         return -1;
 186                 }
 187                 Bseek(&b, fp->lnpcoff, 0);
 188                 if(Bread(&b, pcline, fp->lnpcsz) != fp->lnpcsz){
 189                         pcline = 0;
 190                         return symerrmsg(fp->lnpcsz, "pc-line");
 191                 }
 192                 pclineend = pcline+fp->lnpcsz;
 193         }
 194         return nsym;
 195 }
 196
 197 static int
 198 symerrmsg(int n, char *table)
 199 {
 200         werrstr("can't read %d bytes of %s table", n, table);
 201         return -1;
 202 }
 203
 204 static long
 205 decodename(Biobuf *bp, Sym *p)
 206 {
 207         char *cp;
 208         int c1, c2;
 209         long n;
 210         vlong o;
 211
 212         if((p->type & 0x80) == 0) {             /* old-style, fixed length names */
 213                 p->name = malloc(NNAME);
 214                 if(p->name == 0) {
 215                         werrstr("can't malloc %d bytes", NNAME);
 216                         return -1;
 217                 }
 218                 if(Bread(bp, p->name, NNAME) != NNAME)
 219                         return symerrmsg(NNAME, "symbol");
 220                 Bseek(bp, 3, 1);
 221                 return NNAME+3;
 222         }
 223
 224         p->type &= ~0x80;
 225         if(p->type == 'z' || p->type == 'Z') {
 226                 o = Bseek(bp, 0, 1);
 227                 if(Bgetc(bp) < 0) {
 228                         werrstr("can't read symbol name");
 229                         return -1;
 230                 }
 231                 for(;;) {
 232                         c1 = Bgetc(bp);
 233                         c2 = Bgetc(bp);
 234                         if(c1 < 0 || c2 < 0) {
 235                                 werrstr("can't read symbol name");
 236                                 return -1;
 237                         }
 238                         if(c1 == 0 && c2 == 0)
 239                                 break;
 240                 }
 241                 n = Bseek(bp, 0, 1)-o;
 242                 p->name = malloc(n);
 243                 if(p->name == 0) {
 244                         werrstr("can't malloc %ld bytes", n);
 245                         return -1;
 246                 }
 247                 Bseek(bp, -n, 1);
 248                 if(Bread(bp, p->name, n) != n) {
 249                         werrstr("can't read %ld bytes of symbol name", n);
 250                         return -1;
 251                 }
 252         } else {
 253                 cp = Brdline(bp, '\0');
 254                 if(cp == 0) {
 255                         werrstr("can't read symbol name");
 256                         return -1;
 257                 }
 258                 n = Blinelen(bp);
 259                 p->name = malloc(n);
 260                 if(p->name == 0) {
 261                         werrstr("can't malloc %ld bytes", n);
 262                         return -1;
 263                 }
 264                 strcpy(p->name, cp);
 265         }
 266         return n;
 267 }
 268
 269 /*
 270  *      free any previously loaded symbol tables
 271  */
 272 static void
 273 cleansyms(void)
 274 {
 275         if(globals)
 276                 free(globals);
 277         globals = 0;
 278         nglob = 0;
 279         if(txt)
 280                 free(txt);
 281         txt = 0;
 282         ntxt = 0;
 283         if(fnames)
 284                 free(fnames);
 285         fnames = 0;
 286         fmax = 0;
 287
 288         if(files)
 289                 free(files);
 290         files = 0;
 291         nfiles = 0;
 292         if(hist)
 293                 free(hist);
 294         hist = 0;
 295         nhist = 0;
 296         if(autos)
 297                 free(autos);
 298         autos = 0;
 299         nauto = 0;
 300         isbuilt = 0;
 301         if(symbols)
 302                 free(symbols);
 303         symbols = 0;
 304         nsym = 0;
 305         if(spoff)
 306                 free(spoff);
 307         spoff = 0;
 308         if(pcline)
 309                 free(pcline);
 310         pcline = 0;
 311 }
 312
 313 /*
 314  *      delimit the text segment
 315  */
 316 void
 317 textseg(uvlong base, Fhdr *fp)
 318 {
 319         txtstart = base;
 320         txtend = base+fp->txtsz;
 321 }
 322
 323 /*
 324  *      symbase: return base and size of raw symbol table
 325  *              (special hack for high access rate operations)
 326  */
 327 Sym *
 328 symbase(long *n)
 329 {
 330         *n = nsym;
 331         return symbols;
 332 }
 333
 334 /*
 335  *      Get the ith symbol table entry
 336  */
 337 Sym *
 338 getsym(int index)
 339 {
 340         if(index >= 0 && index < nsym)
 341                 return &symbols[index];
 342         return 0;
 343 }
 344
 345 /*
 346  *      initialize internal symbol tables
 347  */
 348 static int
 349 buildtbls(void)
 350 {
 351         long i;
 352         int j, nh, ng, nt;
 353         File *f;
 354         Txtsym *tp;
 355         Hist *hp;
 356         Sym *p, **ap;
 357
 358         if(isbuilt)
 359                 return 1;
 360         isbuilt = 1;
 361                         /* allocate the tables */
 362         if(nglob) {
 363                 globals = malloc(nglob*sizeof(*globals));
 364                 if(!globals) {
 365                         werrstr("can't malloc global symbol table");
 366                         return 0;
 367                 }
 368         }
 369         if(ntxt) {
 370                 txt = malloc(ntxt*sizeof(*txt));
 371                 if (!txt) {
 372                         werrstr("can't malloc text symbol table");
 373                         return 0;
 374                 }
 375         }
 376         fnames = malloc((fmax+1)*sizeof(*fnames));
 377         if (!fnames) {
 378                 werrstr("can't malloc file name table");
 379                 return 0;
 380         }
 381         memset(fnames, 0, (fmax+1)*sizeof(*fnames));
 382         files = malloc(nfiles*sizeof(*files));
 383         if(!files) {
 384                 werrstr("can't malloc file table");
 385                 return 0;
 386         }
 387         hist = malloc(nhist*sizeof(Hist));
 388         if(hist == 0) {
 389                 werrstr("can't malloc history stack");
 390                 return 0;
 391         }
 392         autos = malloc(nauto*sizeof(Sym*));
 393         if(autos == 0) {
 394                 werrstr("can't malloc auto symbol table");
 395                 return 0;
 396         }
 397                 /* load the tables */
 398         ng = nt = nh = 0;
 399         f = 0;
 400         tp = 0;
 401         i = nsym;
 402         hp = hist;
 403         ap = autos;
 404         for(p = symbols; i-- > 0; p++) {
 405                 switch(p->type) {
 406                 case 'D':
 407                 case 'd':
 408                 case 'B':
 409                 case 'b':
 410                         if(debug)
 411                                 print("Global: %s %llux\n", p->name, p->value);
 412                         globals[ng++] = p;
 413                         break;
 414                 case 'z':
 415                         if(p->value == 1) {             /* New file */
 416                                 if(f) {
 417                                         f->n = nh;
 418                                         f->hist[nh].name = 0;   /* one extra */
 419                                         hp += nh+1;
 420                                         f++;
 421                                 }
 422                                 else
 423                                         f = files;
 424                                 f->hist = hp;
 425                                 f->sym = 0;
 426                                 f->addr = 0;
 427                                 nh = 0;
 428                         }
 429                                 /* alloc one slot extra as terminator */
 430                         f->hist[nh].name = p->name;
 431                         f->hist[nh].line = p->value;
 432                         f->hist[nh].offset = 0;
 433                         if(debug)
 434                                 printhist("-> ", &f->hist[nh], 1);
 435                         nh++;
 436                         break;
 437                 case 'Z':
 438                         if(f && nh > 0)
 439                                 f->hist[nh-1].offset = p->value;
 440                         break;
 441                 case 'T':
 442                 case 't':       /* Text: terminate history if first in file */
 443                 case 'L':
 444                 case 'l':
 445                         tp = &txt[nt++];
 446                         tp->n = 0;
 447                         tp->sym = p;
 448                         tp->locals = ap;
 449                         if(debug)
 450                                 print("TEXT: %s at %llux\n", p->name, p->value);
 451                         if(f && !f->sym) {                      /* first  */
 452                                 f->sym = p;
 453                                 f->addr = p->value;
 454                         }
 455                         break;
 456                 case 'a':
 457                 case 'p':
 458                 case 'm':               /* Local Vars */
 459                         if(!tp)
 460                                 print("Warning: Free floating local var: %s\n",
 461                                         p->name);
 462                         else {
 463                                 if(debug)
 464                                         print("Local: %s %llux\n", p->name, p->value);
 465                                 tp->locals[tp->n] = p;
 466                                 tp->n++;
 467                                 ap++;
 468                         }
 469                         break;
 470                 case 'f':               /* File names */
 471                         if(debug)
 472                                 print("Fname: %s\n", p->name);
 473                         fnames[p->value] = p;
 474                         break;
 475                 default:
 476                         break;
 477                 }
 478         }
 479                 /* sort global and text tables into ascending address order */
 480         qsort(globals, nglob, sizeof(Sym*), symcomp);
 481         qsort(txt, ntxt, sizeof(Txtsym), txtcomp);
 482         qsort(files, nfiles, sizeof(File), filecomp);
 483         tp = txt;
 484         for(i = 0, f = files; i < nfiles; i++, f++) {
 485                 for(j = 0; j < ntxt; j++) {
 486                         if(f->sym == tp->sym) {
 487                                 if(debug) {
 488                                         print("LINK: %s to at %llux", f->sym->name, f->addr);
 489                                         printhist("... ", f->hist, 1);
 490                                 }
 491                                 f->txt = tp++;
 492                                 break;
 493                         }
 494                         if(++tp >= txt+ntxt)    /* wrap around */
 495                                 tp = txt;
 496                 }
 497         }
 498         return 1;
 499 }
 500
 501 /*
 502  * find symbol function.var by name.
 503  *      fn != 0 && var != 0     => look for fn in text, var in data
 504  *      fn != 0 && var == 0     => look for fn in text
 505  *      fn == 0 && var != 0     => look for var first in text then in data space.
 506  */
 507 int
 508 lookup(char *fn, char *var, Symbol *s)
 509 {
 510         int found;
 511
 512         if(buildtbls() == 0)
 513                 return 0;
 514         if(fn) {
 515                 found = findtext(fn, s);
 516                 if(var == 0)            /* case 2: fn not in text */
 517                         return found;
 518                 else if(!found)         /* case 1: fn not found */
 519                         return 0;
 520         } else if(var) {
 521                 found = findtext(var, s);
 522                 if(found)
 523                         return 1;       /* case 3: var found in text */
 524         } else return 0;                /* case 4: fn & var == zero */
 525
 526         if(found)
 527                 return findlocal(s, var, s);    /* case 1: fn found */
 528         return findglobal(var, s);              /* case 3: var not found */
 529
 530 }
 531
 532 /*
 533  * find a function by name
 534  */
 535 static int
 536 findtext(char *name, Symbol *s)
 537 {
 538         int i;
 539
 540         for(i = 0; i < ntxt; i++) {
 541                 if(strcmp(txt[i].sym->name, name) == 0) {
 542                         fillsym(txt[i].sym, s);
 543                         s->handle = (void *) &txt[i];
 544                         s->index = i;
 545                         return 1;
 546                 }
 547         }
 548         return 0;
 549 }
 550 /*
 551  * find global variable by name
 552  */
 553 static int
 554 findglobal(char *name, Symbol *s)
 555 {
 556         long i;
 557
 558         for(i = 0; i < nglob; i++) {
 559                 if(strcmp(globals[i]->name, name) == 0) {
 560                         fillsym(globals[i], s);
 561                         s->index = i;
 562                         return 1;
 563                 }
 564         }
 565         return 0;
 566 }
 567
 568 /*
 569  *      find the local variable by name within a given function
 570  */
 571 int
 572 findlocal(Symbol *s1, char *name, Symbol *s2)
 573 {
 574         if(s1 == 0)
 575                 return 0;
 576         if(buildtbls() == 0)
 577                 return 0;
 578         return findlocvar(s1, name, s2);
 579 }
 580
 581 /*
 582  *      find the local variable by name within a given function
 583  *              (internal function - does no parameter validation)
 584  */
 585 static int
 586 findlocvar(Symbol *s1, char *name, Symbol *s2)
 587 {
 588         Txtsym *tp;
 589         int i;
 590
 591         tp = (Txtsym *)s1->handle;
 592         if(tp && tp->locals) {
 593                 for(i = 0; i < tp->n; i++)
 594                         if (strcmp(tp->locals[i]->name, name) == 0) {
 595                                 fillsym(tp->locals[i], s2);
 596                                 s2->handle = (void *)tp;
 597                                 s2->index = tp->n-1 - i;
 598                                 return 1;
 599                         }
 600         }
 601         return 0;
 602 }
 603
 604 /*
 605  *      Get ith text symbol
 606  */
 607 int
 608 textsym(Symbol *s, int index)
 609 {
 610
 611         if(buildtbls() == 0)
 612                 return 0;
 613         if(index < 0 || index >= ntxt)
 614                 return 0;
 615         fillsym(txt[index].sym, s);
 616         s->handle = (void *)&txt[index];
 617         s->index = index;
 618         return 1;
 619 }
 620
 621 /*
 622  *      Get ith file name
 623  */
 624 int
 625 filesym(int index, char *buf, int n)
 626 {
 627         Hist *hp;
 628
 629         if(buildtbls() == 0)
 630                 return 0;
 631         if(index < 0 || index >= nfiles)
 632                 return 0;
 633         hp = files[index].hist;
 634         if(!hp || !hp->name)
 635                 return 0;
 636         return fileelem(fnames, (uchar*)hp->name, buf, n);
 637 }
 638
 639 /*
 640  *      Lookup name of local variable located at an offset into the frame.
 641  *      The type selects either a parameter or automatic.
 642  */
 643 int
 644 getauto(Symbol *s1, int off, int type, Symbol *s2)
 645 {
 646         Txtsym *tp;
 647         Sym *p;
 648         int i, t;
 649
 650         if(s1 == 0)
 651                 return 0;
 652         if(type == CPARAM)
 653                 t = 'p';
 654         else if(type == CAUTO)
 655                 t = 'a';
 656         else
 657                 return 0;
 658         if(buildtbls() == 0)
 659                 return 0;
 660         tp = (Txtsym *)s1->handle;
 661         if(tp == 0)
 662                 return 0;
 663         for(i = 0; i < tp->n; i++) {
 664                 p = tp->locals[i];
 665                 if(p->type == t && p->value == off) {
 666                         fillsym(p, s2);
 667                         s2->handle = s1->handle;
 668                         s2->index = tp->n-1 - i;
 669                         return 1;
 670                 }
 671         }
 672         return 0;
 673 }
 674
 675 /*
 676  * Find text symbol containing addr; binary search assumes text array is sorted by addr
 677  */
 678 static int
 679 srchtext(uvlong addr)
 680 {
 681         uvlong val;
 682         int top, bot, mid;
 683         Sym *sp;
 684
 685         val = addr;
 686         bot = 0;
 687         top = ntxt;
 688         for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
 689                 sp = txt[mid].sym;
 690                 if(val < sp->value)
 691                         top = mid;
 692                 else if(mid != ntxt-1 && val >= txt[mid+1].sym->value)
 693                         bot = mid;
 694                 else
 695                         return mid;
 696         }
 697         return -1;
 698 }
 699
 700 /*
 701  * Find data symbol containing addr; binary search assumes data array is sorted by addr
 702  */
 703 static int
 704 srchdata(uvlong addr)
 705 {
 706         uvlong val;
 707         int top, bot, mid;
 708         Sym *sp;
 709
 710         bot = 0;
 711         top = nglob;
 712         val = addr;
 713         for(mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
 714                 sp = globals[mid];
 715                 if(val < sp->value)
 716                         top = mid;
 717                 else if(mid < nglob-1 && val >= globals[mid+1]->value)
 718                         bot = mid;
 719                 else
 720                         return mid;
 721         }
 722         return -1;
 723 }
 724
 725 /*
 726  * Find symbol containing val in specified search space
 727  * There is a special case when a value falls beyond the end
 728  * of the text segment; if the search space is CTEXT, that value
 729  * (usually etext) is returned.  If the search space is CANY, symbols in the
 730  * data space are searched for a match.
 731  */
 732 int
 733 findsym(uvlong val, int type, Symbol *s)
 734 {
 735         int i;
 736
 737         if(buildtbls() == 0)
 738                 return 0;
 739
 740         if(type == CTEXT || type == CANY) {
 741                 i = srchtext(val);
 742                 if(i >= 0) {
 743                         if(type == CTEXT || i != ntxt-1) {
 744                                 fillsym(txt[i].sym, s);
 745                                 s->handle = (void *) &txt[i];
 746                                 s->index = i;
 747                                 return 1;
 748                         }
 749                 }
 750         }
 751         if(type == CDATA || type == CANY) {
 752                 i = srchdata(val);
 753                 if(i >= 0) {
 754                         fillsym(globals[i], s);
 755                         s->index = i;
 756                         return 1;
 757                 }
 758         }
 759         return 0;
 760 }
 761
 762 /*
 763  *      Find the start and end address of the function containing addr
 764  */
 765 int
 766 fnbound(uvlong addr, uvlong *bounds)
 767 {
 768         int i;
 769
 770         if(buildtbls() == 0)
 771                 return 0;
 772
 773         i = srchtext(addr);
 774         if(0 <= i && i < ntxt-1) {
 775                 bounds[0] = txt[i].sym->value;
 776                 bounds[1] = txt[i+1].sym->value;
 777                 return 1;
 778         }
 779         return 0;
 780 }
 781
 782 /*
 783  * get the ith local symbol for a function
 784  * the input symbol table is reverse ordered, so we reverse
 785  * accesses here to maintain approx. parameter ordering in a stack trace.
 786  */
 787 int
 788 localsym(Symbol *s, int index)
 789 {
 790         Txtsym *tp;
 791
 792         if(s == 0 || index < 0)
 793                 return 0;
 794         if(buildtbls() == 0)
 795                 return 0;
 796
 797         tp = (Txtsym *)s->handle;
 798         if(tp && tp->locals && index < tp->n) {
 799                 fillsym(tp->locals[tp->n-index-1], s);  /* reverse */
 800                 s->handle = (void *)tp;
 801                 s->index = index;
 802                 return 1;
 803         }
 804         return 0;
 805 }
 806
 807 /*
 808  * get the ith global symbol
 809  */
 810 int
 811 globalsym(Symbol *s, int index)
 812 {
 813         if(s == 0)
 814                 return 0;
 815         if(buildtbls() == 0)
 816                 return 0;
 817
 818         if(index >=0 && index < nglob) {
 819                 fillsym(globals[index], s);
 820                 s->index = index;
 821                 return 1;
 822         }
 823         return 0;
 824 }
 825
 826 /*
 827  *      find the pc given a file name and line offset into it.
 828  */
 829 uvlong
 830 file2pc(char *file, long line)
 831 {
 832         File *fp;
 833         long i;
 834         uvlong pc, start, end;
 835         short *name;
 836
 837         if(buildtbls() == 0 || files == 0)
 838                 return ~0;
 839         name = encfname(file);
 840         if(name == 0) {                 /* encode the file name */
 841                 werrstr("file %s not found", file);
 842                 return ~0;
 843         }
 844                 /* find this history stack */
 845         for(i = 0, fp = files; i < nfiles; i++, fp++)
 846                 if (hline(fp, name, &line))
 847                         break;
 848         free(name);
 849         if(i >= nfiles) {
 850                 werrstr("line %ld in file %s not found", line, file);
 851                 return ~0;
 852         }
 853         start = fp->addr;               /* first text addr this file */
 854         if(i < nfiles-1)
 855                 end = (fp+1)->addr;     /* first text addr next file */
 856         else
 857                 end = 0;                /* last file in load module */
 858         /*
 859          * At this point, line contains the offset into the file.
 860          * run the state machine to locate the pc closest to that value.
 861          */
 862         if(debug)
 863                 print("find pc for %ld - between: %llux and %llux\n", line, start, end);
 864         pc = line2addr(line, start, end);
 865         if(pc == ~0) {
 866                 werrstr("line %ld not in file %s", line, file);
 867                 return ~0;
 868         }
 869         return pc;
 870 }
 871
 872 /*
 873  *      search for a path component index
 874  */
 875 static int
 876 pathcomp(char *s, int n)
 877 {
 878         int i;
 879
 880         for(i = 0; i <= fmax; i++)
 881                 if(fnames[i] && strncmp(s, fnames[i]->name, n) == 0)
 882                         return i;
 883         return -1;
 884 }
 885
 886 /*
 887  *      Encode a char file name as a sequence of short indices
 888  *      into the file name dictionary.
 889  */
 890 static short*
 891 encfname(char *file)
 892 {
 893         int i, j;
 894         char *cp, *cp2;
 895         short *dest;
 896
 897         if(*file == '/')        /* always check first '/' */
 898                 cp2 = file+1;
 899         else {
 900                 cp2 = strchr(file, '/');
 901                 if(!cp2)
 902                         cp2 = strchr(file, 0);
 903         }
 904         cp = file;
 905         dest = 0;
 906         for(i = 0; *cp; i++) {
 907                 j = pathcomp(cp, cp2-cp);
 908                 if(j < 0)
 909                         return 0;       /* not found */
 910                 dest = realloc(dest, (i+1)*sizeof(short));
 911                 dest[i] = j;
 912                 cp = cp2;
 913                 while(*cp == '/')       /* skip embedded '/'s */
 914                         cp++;
 915                 cp2 = strchr(cp, '/');
 916                 if(!cp2)
 917                         cp2 = strchr(cp, 0);
 918         }
 919         dest = realloc(dest, (i+1)*sizeof(short));
 920         dest[i] = 0;
 921         return dest;
 922 }
 923
 924 /*
 925  *      Search a history stack for a matching file name accumulating
 926  *      the size of intervening files in the stack.
 927  */
 928 static int
 929 hline(File *fp, short *name, long *line)
 930 {
 931         Hist *hp;
 932         int offset, depth;
 933         long ln;
 934
 935         for(hp = fp->hist; hp->name; hp++)              /* find name in stack */
 936                 if(hp->name[1] || hp->name[2]) {
 937                         if(hcomp(hp, name))
 938                                 break;
 939                 }
 940         if(!hp->name)           /* match not found */
 941                 return 0;
 942         if(debug)
 943                 printhist("hline found ... ", hp, 1);
 944         /*
 945          * unwind the stack until empty or we hit an entry beyond our line
 946          */
 947         ln = *line;
 948         offset = hp->line-1;
 949         depth = 1;
 950         for(hp++; depth && hp->name; hp++) {
 951                 if(debug)
 952                         printhist("hline inspect ... ", hp, 1);
 953                 if(hp->name[1] || hp->name[2]) {
 954                         if(hp->offset){                 /* Z record */
 955                                 offset = 0;
 956                                 if(hcomp(hp, name)) {
 957                                         if(*line <= hp->offset)
 958                                                 break;
 959                                         ln = *line+hp->line-hp->offset;
 960                                         depth = 1;      /* implicit pop */
 961                                 } else
 962                                         depth = 2;      /* implicit push */
 963                         } else if(depth == 1 && ln < hp->line-offset)
 964                                         break;          /* Beyond our line */
 965                         else if(depth++ == 1)           /* push */
 966                                 offset -= hp->line;
 967                 } else if(--depth == 1)         /* pop */
 968                         offset += hp->line;
 969         }
 970         *line = ln+offset;
 971         return 1;
 972 }
 973
 974 /*
 975  *      compare two encoded file names
 976  */
 977 static int
 978 hcomp(Hist *hp, short *sp)
 979 {
 980         uchar *cp;
 981         int i, j;
 982         short *s;
 983
 984         cp = (uchar *)hp->name;
 985         s = sp;
 986         if (*s == 0)
 987                 return 0;
 988         for (i = 1; j = (cp[i]<<8)|cp[i+1]; i += 2) {
 989                 if(j == 0)
 990                         break;
 991                 if(*s == j)
 992                         s++;
 993                 else
 994                         s = sp;
 995         }
 996         return *s == 0;
 997 }
 998
 999 /*
1000  *      Convert a pc to a "file:line {file:line}" string.
1001  */
1002 long
1003 fileline(char *str, int n, uvlong dot)
1004 {
1005         long line, top, bot, mid;
1006         File *f;
1007
1008         *str = 0;
1009         if(buildtbls() == 0)
1010                 return 0;
1011                 /* binary search assumes file list is sorted by addr */
1012         bot = 0;
1013         top = nfiles;
1014         for (mid = (bot+top)/2; mid < top; mid = (bot+top)/2) {
1015                 f = &files[mid];
1016                 if(dot < f->addr)
1017                         top = mid;
1018                 else if(mid < nfiles-1 && dot >= (f+1)->addr)
1019                         bot = mid;
1020                 else {
1021                         line = pc2line(dot);
1022                         if(line > 0 && fline(str, n, line, f->hist, 0) >= 0)
1023                                 return 1;
1024                         break;
1025                 }
1026         }
1027         return 0;
1028 }
1029
1030 /*
1031  *      Convert a line number within a composite file to relative line
1032  *      number in a source file.  A composite file is the source
1033  *      file with included files inserted in line.
1034  */
1035 static int
1036 fline(char *str, int n, long line, Hist *base, Hist **ret)
1037 {
1038         Hist *start;                    /* start of current level */
1039         Hist *h;                        /* current entry */
1040         long delta;                     /* sum of size of files this level */
1041         int k;
1042
1043         start = base;
1044         h = base;
1045         delta = h->line;
1046         while(h && h->name && line > h->line) {
1047                 if(h->name[1] || h->name[2]) {
1048                         if(h->offset != 0) {    /* #line Directive */
1049                                 delta = h->line-h->offset+1;
1050                                 start = h;
1051                                 base = h++;
1052                         } else {                /* beginning of File */
1053                                 if(start == base)
1054                                         start = h++;
1055                                 else {
1056                                         k = fline(str, n, line, start, &h);
1057                                         if(k <= 0)
1058                                                 return k;
1059                                 }
1060                         }
1061                 } else {
1062                         if(start == base && ret) {      /* end of recursion level */
1063                                 *ret = h;
1064                                 return 1;
1065                         } else {                        /* end of included file */
1066                                 delta += h->line-start->line;
1067                                 h++;
1068                                 start = base;
1069                         }
1070                 }
1071         }
1072         if(!h)
1073                 return -1;
1074         if(start != base)
1075                 line = line-start->line+1;
1076         else
1077                 line = line-delta+1;
1078         if(!h->name)
1079                 strncpy(str, "<eof>", n);
1080         else {
1081                 k = fileelem(fnames, (uchar*)start->name, str, n);
1082                 if(k+8 < n)
1083                         sprint(str+k, ":%ld", line);
1084         }
1085 /**********Remove comments for complete back-trace of include sequence
1086  *      if(start != base) {
1087  *              k = strlen(str);
1088  *              if(k+2 < n) {
1089  *                      str[k++] = ' ';
1090  *                      str[k++] = '{';
1091  *              }
1092  *              k += fileelem(fnames, (uchar*) base->name, str+k, n-k);
1093  *              if(k+10 < n)
1094  *                      sprint(str+k, ":%ld}", start->line-delta);
1095  *      }
1096  ********************/
1097         return 0;
1098 }
1099
1100 /*
1101  *      convert an encoded file name to a string.
1102  */
1103 int
1104 fileelem(Sym **fp, uchar *cp, char *buf, int n)
1105 {
1106         int i, j;
1107         char *c, *bp, *end;
1108
1109         bp = buf;
1110         end = buf+n-1;
1111         for(i = 1; j = (cp[i]<<8)|cp[i+1]; i+=2){
1112                 c = fp[j]->name;
1113                 if(bp != buf && bp[-1] != '/' && bp < end)
1114                         *bp++ = '/';
1115                 while(bp < end && *c)
1116                         *bp++ = *c++;
1117         }
1118         *bp = 0;
1119         i =  bp-buf;
1120         if(i > 1) {
1121                 cleanname(buf);
1122                 i = strlen(buf);
1123         }
1124         return i;
1125 }
1126
1127 /*
1128  *      compare the values of two symbol table entries.
1129  */
1130 static int
1131 symcomp(void *a, void *b)
1132 {
1133         int i;
1134
1135         i = (*(Sym**)a)->value - (*(Sym**)b)->value;
1136         if (i)
1137                 return i;
1138         return strcmp((*(Sym**)a)->name, (*(Sym**)b)->name);
1139 }
1140
1141 /*
1142  *      compare the values of the symbols referenced by two text table entries
1143  */
1144 static int
1145 txtcomp(void *a, void *b)
1146 {
1147         return ((Txtsym*)a)->sym->value - ((Txtsym*)b)->sym->value;
1148 }
1149
1150 /*
1151  *      compare the values of the symbols referenced by two file table entries
1152  */
1153 static int
1154 filecomp(void *a, void *b)
1155 {
1156         return ((File*)a)->addr - ((File*)b)->addr;
1157 }
1158
1159 /*
1160  *      fill an interface Symbol structure from a symbol table entry
1161  */
1162 static void
1163 fillsym(Sym *sp, Symbol *s)
1164 {
1165         s->type = sp->type;
1166         s->value = sp->value;
1167         s->name = sp->name;
1168         s->index = 0;
1169         switch(sp->type) {
1170         case 'b':
1171         case 'B':
1172         case 'D':
1173         case 'd':
1174                 s->class = CDATA;
1175                 break;
1176         case 't':
1177         case 'T':
1178         case 'l':
1179         case 'L':
1180                 s->class = CTEXT;
1181                 break;
1182         case 'a':
1183                 s->class = CAUTO;
1184                 break;
1185         case 'p':
1186                 s->class = CPARAM;
1187                 break;
1188         case 'm':
1189                 s->class = CSTAB;
1190                 break;
1191         default:
1192                 s->class = CNONE;
1193                 break;
1194         }
1195         s->handle = 0;
1196 }
1197
1198 /*
1199  *      find the stack frame, given the pc
1200  */
1201 uvlong
1202 pc2sp(uvlong pc)
1203 {
1204         uchar *c, u;
1205         uvlong currpc, currsp;
1206
1207         if(spoff == 0)
1208                 return ~0;
1209         currsp = 0;
1210         currpc = txtstart - mach->pcquant;
1211
1212         if(pc<currpc || pc>txtend)
1213                 return ~0;
1214         for(c = spoff; c < spoffend; c++) {
1215                 if (currpc >= pc)
1216                         return currsp;
1217                 u = *c;
1218                 if (u == 0) {
1219                         currsp += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1220                         c += 4;
1221                 }
1222                 else if (u < 65)
1223                         currsp += 4*u;
1224                 else if (u < 129)
1225                         currsp -= 4*(u-64);
1226                 else
1227                         currpc += mach->pcquant*(u-129);
1228                 currpc += mach->pcquant;
1229         }
1230         return ~0;
1231 }
1232
1233 /*
1234  *      find the source file line number for a given value of the pc
1235  */
1236 long
1237 pc2line(uvlong pc)
1238 {
1239         uchar *c, u;
1240         uvlong currpc;
1241         long currline;
1242
1243         if(pcline == 0)
1244                 return -1;
1245         currline = 0;
1246         currpc = txtstart-mach->pcquant;
1247         if(pc<currpc || pc>txtend)
1248                 return ~0;
1249
1250         for(c = pcline; c < pclineend; c++) {
1251                 if(currpc >= pc)
1252                         return currline;
1253                 u = *c;
1254                 if(u == 0) {
1255                         currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1256                         c += 4;
1257                 }
1258                 else if(u < 65)
1259                         currline += u;
1260                 else if(u < 129)
1261                         currline -= (u-64);
1262                 else
1263                         currpc += mach->pcquant*(u-129);
1264                 currpc += mach->pcquant;
1265         }
1266         return ~0;
1267 }
1268
1269 /*
1270  *      find the pc associated with a line number
1271  *      basepc and endpc are text addresses bounding the search.
1272  *      if endpc == 0, the end of the table is used (i.e., no upper bound).
1273  *      usually, basepc and endpc contain the first text address in
1274  *      a file and the first text address in the following file, respectively.
1275  */
1276 uvlong
1277 line2addr(long line, uvlong basepc, uvlong endpc)
1278 {
1279         uchar *c,  u;
1280         uvlong currpc, pc;
1281         long currline;
1282         long delta, d;
1283         int found;
1284
1285         if(pcline == 0 || line == 0)
1286                 return ~0;
1287
1288         currline = 0;
1289         currpc = txtstart-mach->pcquant;
1290         pc = ~0;
1291         found = 0;
1292         delta = HUGEINT;
1293
1294         for(c = pcline; c < pclineend; c++) {
1295                 if(endpc && currpc >= endpc)    /* end of file of interest */
1296                         break;
1297                 if(currpc >= basepc) {          /* proper file */
1298                         if(currline >= line) {
1299                                 d = currline-line;
1300                                 found = 1;
1301                         } else
1302                                 d = line-currline;
1303                         if(d < delta) {
1304                                 delta = d;
1305                                 pc = currpc;
1306                         }
1307                 }
1308                 u = *c;
1309                 if(u == 0) {
1310                         currline += (c[1]<<24)|(c[2]<<16)|(c[3]<<8)|c[4];
1311                         c += 4;
1312                 }
1313                 else if(u < 65)
1314                         currline += u;
1315                 else if(u < 129)
1316                         currline -= (u-64);
1317                 else
1318                         currpc += mach->pcquant*(u-129);
1319                 currpc += mach->pcquant;
1320         }
1321         if(found)
1322                 return pc;
1323         return ~0;
1324 }
1325
1326 /*
1327  *      Print a history stack (debug). if count is 0, prints the whole stack
1328  */
1329 static void
1330 printhist(char *msg, Hist *hp, int count)
1331 {
1332         int i;
1333         uchar *cp;
1334         char buf[128];
1335
1336         i = 0;
1337         while(hp->name) {
1338                 if(count && ++i > count)
1339                         break;
1340                 print("%s Line: %lx (%ld)  Offset: %lx (%ld)  Name: ", msg,
1341                         hp->line, hp->line, hp->offset, hp->offset);
1342                 for(cp = (uchar *)hp->name+1; (*cp<<8)|cp[1]; cp += 2) {
1343                         if (cp != (uchar *)hp->name+1)
1344                                 print("/");
1345                         print("%x", (*cp<<8)|cp[1]);
1346                 }
1347                 fileelem(fnames, (uchar *) hp->name, buf, sizeof(buf));
1348                 print(" (%s)\n", buf);
1349                 hp++;
1350         }
1351 }
1352
1353 #ifdef DEBUG
1354 /*
1355  *      print the history stack for a file. (debug only)
1356  *      if (name == 0) => print all history stacks.
1357  */
1358 void
1359 dumphist(char *name)
1360 {
1361         int i;
1362         File *f;
1363         short *fname;
1364
1365         if(buildtbls() == 0)
1366                 return;
1367         if(name)
1368                 fname = encfname(name);
1369         for(i = 0, f = files; i < nfiles; i++, f++)
1370                 if(fname == 0 || hcomp(f->hist, fname))
1371                         printhist("> ", f->hist, f->n);
1372
1373         if(fname)
1374                 free(fname);
1375 }
1376 #endif