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