libkern/kxld/kxld_symtab.c

   1 /*
   2  * Copyright (c) 2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 #include <string.h>
  29 #include <mach-o/loader.h>
  30 #include <mach-o/nlist.h>
  31 #include <sys/queue.h>
  32 #include <sys/types.h>
  33
  34 #define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld"
  35 #include <AssertMacros.h>
  36
  37 #include "kxld_array.h"
  38 #include "kxld_dict.h"
  39 #include "kxld_sect.h"
  40 #include "kxld_sym.h"
  41 #include "kxld_symtab.h"
  42 #include "kxld_util.h"
  43
  44 struct kxld_symtab {
  45     KXLDArray syms;
  46     KXLDDict cxx_index;
  47     KXLDDict name_index;
  48     char *strings;
  49     u_int strsize;
  50 };
  51
  52 /*******************************************************************************
  53 * Prototypes
  54 *******************************************************************************/
  55
  56 static kern_return_t init_macho(KXLDSymtab *symtab, u_char *macho,
  57     struct symtab_command *src, kxld_addr_t linkedit_offset, boolean_t is_32_bit)
  58     __attribute__((nonnull));
  59
  60 #if KXLD_USER_OR_ILP32
  61 static kern_return_t init_syms_32(KXLDSymtab *symtab, u_char *macho, u_long offset,
  62     u_int nsyms);
  63 #endif
  64 #if KXLD_USER_OR_LP64
  65 static kern_return_t init_syms_64(KXLDSymtab *symtab, u_char *macho, u_long offset,
  66     u_int nsyms);
  67 #endif
  68
  69 static kern_return_t make_cxx_index(KXLDSymtab *symtab)
  70     __attribute__((nonnull));
  71 static boolean_t sym_is_defined_cxx(const KXLDSym *sym);
  72 static kern_return_t make_name_index(KXLDSymtab *symtab)
  73     __attribute__((nonnull));
  74 static boolean_t sym_is_name_indexed(const KXLDSym *sym);
  75
  76
  77 /*******************************************************************************
  78 *******************************************************************************/
  79 size_t
  80 kxld_symtab_sizeof()
  81 {
  82     return sizeof(KXLDSymtab);
  83 }
  84
  85 #if KXLD_USER_OR_ILP32
  86 /*******************************************************************************
  87 *******************************************************************************/
  88 kern_return_t
  89 kxld_symtab_init_from_macho_32(KXLDSymtab *symtab, u_char *macho,
  90     struct symtab_command *src, kxld_addr_t linkedit_offset)
  91 {
  92     return init_macho(symtab, macho, src, linkedit_offset, TRUE);
  93 }
  94 #endif /* KXLD_USER_ILP32 */
  95
  96 #if KXLD_USER_OR_LP64
  97 /*******************************************************************************
  98 *******************************************************************************/
  99 kern_return_t
 100 kxld_symtab_init_from_macho_64(KXLDSymtab *symtab, u_char *macho,
 101     struct symtab_command *src, kxld_addr_t linkedit_offset)
 102 {
 103     return init_macho(symtab, macho, src, linkedit_offset, FALSE);
 104 }
 105 #endif /* KXLD_USER_OR_LP64 */
 106
 107 /*******************************************************************************
 108 *******************************************************************************/
 109 static kern_return_t
 110 init_macho(KXLDSymtab *symtab, u_char *macho, struct symtab_command *src,
 111     kxld_addr_t linkedit_offset, boolean_t is_32_bit __unused)
 112 {
 113     kern_return_t rval = KERN_FAILURE;
 114
 115     check(symtab);
 116     check(macho);
 117     check(src);
 118
 119     /* Initialize the symbol array */
 120
 121     rval = kxld_array_init(&symtab->syms, sizeof(KXLDSym), src->nsyms);
 122     require_noerr(rval, finish);
 123
 124     /* Initialize the string table */
 125
 126     symtab->strings = (char *) (macho + src->stroff + linkedit_offset);
 127     symtab->strsize = src->strsize;
 128
 129     /* Initialize the symbols */
 130
 131     KXLD_3264_FUNC(is_32_bit, rval,
 132         init_syms_32, init_syms_64,
 133         symtab, macho, (u_long) (src->symoff + linkedit_offset), src->nsyms);
 134     require_noerr(rval, finish);
 135
 136     /* Create the C++ index */
 137
 138     rval = make_cxx_index(symtab);
 139     require_noerr(rval, finish);
 140
 141     /* Create the name index */
 142
 143     rval = make_name_index(symtab);
 144     require_noerr(rval, finish);
 145
 146     /* Save the output */
 147
 148     rval = KERN_SUCCESS;
 149
 150 finish:
 151     return rval;
 152 }
 153
 154 #if KXLD_USER_OR_ILP32
 155 /*******************************************************************************
 156 *******************************************************************************/
 157 static kern_return_t
 158 init_syms_32(KXLDSymtab *symtab, u_char *macho, u_long offset, u_int nsyms)
 159 {
 160     kern_return_t rval = KERN_FAILURE;
 161     KXLDSym *sym = NULL;
 162     u_int i = 0;
 163     struct nlist *src_syms = (struct nlist *) (macho + offset);
 164
 165     for (i = 0; i < nsyms; ++i) {
 166         sym = kxld_array_get_item(&symtab->syms, i);
 167         require_action(sym, finish, rval=KERN_FAILURE);
 168
 169         rval = kxld_sym_init_from_macho32(sym, symtab->strings, &src_syms[i]);
 170         require_noerr(rval, finish);
 171     }
 172
 173     rval = KERN_SUCCESS;
 174
 175 finish:
 176     return rval;
 177 }
 178 #endif /* KXLD_USER_OR_ILP32 */
 179
 180 #if KXLD_USER_OR_LP64
 181 /*******************************************************************************
 182 *******************************************************************************/
 183 static kern_return_t
 184 init_syms_64(KXLDSymtab *symtab, u_char *macho, u_long offset, u_int nsyms)
 185 {
 186     kern_return_t rval = KERN_FAILURE;
 187     KXLDSym *sym = NULL;
 188     u_int i = 0;
 189     struct nlist_64 *src_syms = (struct nlist_64 *) (macho + offset);
 190
 191     for (i = 0; i < nsyms; ++i) {
 192         sym = kxld_array_get_item(&symtab->syms, i);
 193         require_action(sym, finish, rval=KERN_FAILURE);
 194
 195         rval = kxld_sym_init_from_macho64(sym, symtab->strings, &src_syms[i]);
 196         require_noerr(rval, finish);
 197     }
 198
 199     rval = KERN_SUCCESS;
 200
 201 finish:
 202     return rval;
 203 }
 204 #endif /* KXLD_USER_OR_LP64 */
 205
 206 /*******************************************************************************
 207 *******************************************************************************/
 208 void
 209 kxld_symtab_iterator_init(KXLDSymtabIterator *iter, const KXLDSymtab *symtab,
 210     KXLDSymPredicateTest test, boolean_t negate)
 211 {
 212     check(iter);
 213     check(symtab);
 214     check(test);
 215
 216     iter->symtab = symtab;
 217     iter->idx = 0;
 218     iter->test = test;
 219     iter->negate = negate;
 220 }
 221
 222 /*******************************************************************************
 223 *******************************************************************************/
 224 void
 225 kxld_symtab_clear(KXLDSymtab *symtab)
 226 {
 227     check(symtab);
 228
 229     kxld_array_clear(&symtab->syms);
 230     kxld_dict_clear(&symtab->cxx_index);
 231     kxld_dict_clear(&symtab->name_index);
 232 }
 233
 234 /*******************************************************************************
 235 *******************************************************************************/
 236 void
 237 kxld_symtab_deinit(KXLDSymtab *symtab)
 238 {
 239     check(symtab);
 240
 241     kxld_array_deinit(&symtab->syms);
 242     kxld_dict_deinit(&symtab->cxx_index);
 243     kxld_dict_deinit(&symtab->name_index);
 244 }
 245
 246 /*******************************************************************************
 247 *******************************************************************************/
 248 u_int
 249 kxld_symtab_get_num_symbols(const KXLDSymtab *symtab)
 250 {
 251     check(symtab);
 252
 253     return symtab->syms.nitems;
 254 }
 255
 256 /*******************************************************************************
 257 *******************************************************************************/
 258 KXLDSym *
 259 kxld_symtab_get_symbol_by_index(const KXLDSymtab *symtab, u_int idx)
 260 {
 261     check(symtab);
 262
 263     return kxld_array_get_item(&symtab->syms, idx);
 264 }
 265
 266 /*******************************************************************************
 267 *******************************************************************************/
 268 KXLDSym *
 269 kxld_symtab_get_symbol_by_name(const KXLDSymtab *symtab, const char *name)
 270 {
 271     check(symtab);
 272     check(name);
 273
 274     return kxld_dict_find(&symtab->name_index, name);
 275 }
 276
 277 /*******************************************************************************
 278 *******************************************************************************/
 279 KXLDSym *
 280 kxld_symtab_get_cxx_symbol_by_value(const KXLDSymtab *symtab, kxld_addr_t value)
 281 {
 282     check(symtab);
 283
 284     /*
 285      * value may hold a THUMB address (with bit 0 set to 1) but the index will
 286      * have the real address (bit 0 set to 0).  So if bit 0 is set here,
 287      * we clear it (should impact no architectures but ARM).
 288      */
 289     kxld_addr_t v = value & ~1;
 290
 291     return kxld_dict_find(&symtab->cxx_index, &v);
 292 }
 293
 294 /*******************************************************************************
 295 *******************************************************************************/
 296 kern_return_t
 297 kxld_symtab_get_sym_index(const KXLDSymtab *symtab, const KXLDSym *sym,
 298     u_int *symindex)
 299 {
 300     kern_return_t rval = KERN_FAILURE;
 301
 302     rval = kxld_array_get_index(&symtab->syms, sym, symindex);
 303     require_noerr(rval, finish);
 304
 305     rval = KERN_SUCCESS;
 306
 307 finish:
 308     return rval;
 309 }
 310
 311 /*******************************************************************************
 312 *******************************************************************************/
 313 u_long
 314 kxld_symtab_get_macho_header_size(void)
 315 {
 316     return sizeof(struct symtab_command);
 317 }
 318
 319 /*******************************************************************************
 320 *******************************************************************************/
 321 u_long
 322 kxld_symtab_get_macho_data_size(const KXLDSymtab *symtab,
 323     boolean_t is_link_state, boolean_t is_32_bit)
 324 {
 325     KXLDSymtabIterator iter;
 326     KXLDSym *sym = NULL;
 327     u_long size = 1; /* strtab start padding */
 328     u_int nsyms = 0;
 329
 330     check(symtab);
 331
 332     if (is_link_state) {
 333         kxld_symtab_iterator_init(&iter, symtab, kxld_sym_is_exported, FALSE);
 334     } else {
 335         kxld_symtab_iterator_init(&iter, symtab,
 336             kxld_sym_is_defined_locally, FALSE);
 337     }
 338
 339     while ((sym = kxld_symtab_iterator_get_next(&iter))) {
 340         size += strlen(sym->name) + 1;
 341         ++nsyms;
 342     }
 343
 344     if (is_32_bit) {
 345         size += nsyms * sizeof(struct nlist);
 346     } else {
 347         size += nsyms * sizeof(struct nlist_64);
 348     }
 349
 350     return size;
 351 }
 352
 353 /*******************************************************************************
 354 *******************************************************************************/
 355 kern_return_t
 356 kxld_symtab_export_macho(const KXLDSymtab *symtab, u_char *buf,
 357     u_long *header_offset, u_long header_size,
 358     u_long *data_offset, u_long data_size,
 359     boolean_t is_link_state, boolean_t is_32_bit)
 360 {
 361     kern_return_t rval = KERN_FAILURE;
 362     KXLDSymtabIterator iter;
 363     KXLDSym *sym = NULL;
 364     struct symtab_command *symtabhdr = NULL;
 365     u_char *nl = NULL;
 366     u_long nlistsize = 0;
 367     char *strtab = NULL;
 368     u_long stroff = 1; /* strtab start padding */
 369
 370     check(symtab);
 371     check(buf);
 372     check(header_offset);
 373     check(data_offset);
 374
 375     require_action(sizeof(*symtabhdr) <= header_size - *header_offset,
 376         finish, rval=KERN_FAILURE);
 377     symtabhdr = (struct symtab_command *) (buf + *header_offset);
 378     *header_offset += sizeof(*symtabhdr);
 379
 380     /* Initialize the symbol table header */
 381
 382     symtabhdr->cmd = LC_SYMTAB;
 383     symtabhdr->cmdsize = (uint32_t) sizeof(*symtabhdr);
 384     symtabhdr->symoff = (uint32_t) *data_offset;
 385     symtabhdr->strsize = 1; /* strtab start padding */
 386
 387     /* Find the size of the symbol and string tables */
 388
 389     if (is_link_state) {
 390         kxld_symtab_iterator_init(&iter, symtab, kxld_sym_is_exported, FALSE);
 391     } else {
 392         kxld_symtab_iterator_init(&iter, symtab,
 393             kxld_sym_is_defined_locally, FALSE);
 394     }
 395
 396     while ((sym = kxld_symtab_iterator_get_next(&iter))) {
 397         symtabhdr->nsyms++;
 398         symtabhdr->strsize += (uint32_t) (strlen(sym->name) + 1);
 399     }
 400
 401     if (is_32_bit) {
 402         nlistsize = sizeof(struct nlist);
 403     } else {
 404         nlistsize = sizeof(struct nlist_64);
 405     }
 406
 407     symtabhdr->stroff = (uint32_t) (symtabhdr->symoff +
 408         (symtabhdr->nsyms * nlistsize));
 409     require_action(symtabhdr->stroff + symtabhdr->strsize <= data_size, finish,
 410         rval=KERN_FAILURE);
 411
 412     /* Get pointers to the symbol and string tables */
 413
 414     nl = buf + symtabhdr->symoff;
 415     strtab = (char *) (buf + symtabhdr->stroff);
 416
 417     /* Copy over the symbols */
 418
 419     kxld_symtab_iterator_reset(&iter);
 420     while ((sym = kxld_symtab_iterator_get_next(&iter))) {
 421
 422         KXLD_3264_FUNC(is_32_bit, rval,
 423             kxld_sym_export_macho_32, kxld_sym_export_macho_64,
 424             sym, nl, strtab, &stroff, symtabhdr->strsize, is_link_state);
 425         require_noerr(rval, finish);
 426
 427         nl += nlistsize;
 428         stroff += rval;
 429     }
 430
 431     /* Update the data offset */
 432     *data_offset += (symtabhdr->nsyms * nlistsize) + stroff;
 433
 434     rval = KERN_SUCCESS;
 435
 436 finish:
 437     return rval;
 438 }
 439
 440 /*******************************************************************************
 441 *******************************************************************************/
 442 u_int
 443 kxld_symtab_iterator_get_num_remaining(const KXLDSymtabIterator *iter)
 444 {
 445     u_int idx = 0;
 446     u_int count = 0;
 447
 448     check(iter);
 449
 450     idx = iter->idx;
 451
 452     for (idx = iter->idx; idx < iter->symtab->syms.nitems; ++idx) {
 453         count += iter->test(kxld_array_get_item(&iter->symtab->syms, idx));
 454     }
 455
 456     return count;
 457 }
 458
 459 /*******************************************************************************
 460 *******************************************************************************/
 461 static kern_return_t
 462 make_cxx_index(KXLDSymtab *symtab)
 463 {
 464     kern_return_t rval = KERN_FAILURE;
 465     KXLDSymtabIterator iter;
 466     KXLDSym *sym = NULL;
 467     u_int nsyms = 0;
 468
 469     check(symtab);
 470
 471     /* Count the number of C++ symbols */
 472     kxld_symtab_iterator_init(&iter, symtab, sym_is_defined_cxx, FALSE);
 473     nsyms = kxld_symtab_iterator_get_num_remaining(&iter);
 474
 475     /* Create the dictionary */
 476     rval = kxld_dict_init(&symtab->cxx_index, kxld_dict_kxldaddr_hash,
 477         kxld_dict_kxldaddr_cmp, nsyms);
 478     require_noerr(rval, finish);
 479
 480     /* Insert the non-stab symbols */
 481     while ((sym = kxld_symtab_iterator_get_next(&iter))) {
 482         rval = kxld_dict_insert(&symtab->cxx_index, &sym->base_addr, sym);
 483         require_noerr(rval, finish);
 484     }
 485
 486     rval = KERN_SUCCESS;
 487
 488 finish:
 489
 490     return rval;
 491 }
 492
 493 /*******************************************************************************
 494 *******************************************************************************/
 495 static boolean_t
 496 sym_is_defined_cxx(const KXLDSym *sym)
 497 {
 498     return (kxld_sym_is_defined_locally(sym) && kxld_sym_is_cxx(sym));
 499 }
 500
 501 /*******************************************************************************
 502 *******************************************************************************/
 503 static kern_return_t
 504 make_name_index(KXLDSymtab *symtab)
 505 {
 506     kern_return_t rval = KERN_FAILURE;
 507     KXLDSymtabIterator iter;
 508     KXLDSym *sym = NULL;
 509     u_int nsyms = 0;
 510
 511     check(symtab);
 512
 513     /* Count the number of symbols we need to index by name */
 514     kxld_symtab_iterator_init(&iter, symtab, sym_is_name_indexed, FALSE);
 515     nsyms = kxld_symtab_iterator_get_num_remaining(&iter);
 516
 517     /* Create the dictionary */
 518     rval = kxld_dict_init(&symtab->name_index, kxld_dict_string_hash,
 519         kxld_dict_string_cmp, nsyms);
 520     require_noerr(rval, finish);
 521
 522     /* Insert the non-stab symbols */
 523     while ((sym = kxld_symtab_iterator_get_next(&iter))) {
 524         rval = kxld_dict_insert(&symtab->name_index, sym->name, sym);
 525         require_noerr(rval, finish);
 526     }
 527
 528     rval = KERN_SUCCESS;
 529
 530 finish:
 531
 532     return rval;
 533 }
 534
 535 /*******************************************************************************
 536 *******************************************************************************/
 537 static boolean_t
 538 sym_is_name_indexed(const KXLDSym *sym)
 539 {
 540     return (kxld_sym_is_vtable(sym)                     ||
 541         streq_safe(sym->name, KXLD_KMOD_INFO_SYMBOL,
 542             const_strlen(KXLD_KMOD_INFO_SYMBOL))        ||
 543         streq_safe(sym->name, KXLD_WEAK_TEST_SYMBOL,
 544             const_strlen(KXLD_WEAK_TEST_SYMBOL)));
 545 }
 546
 547 /*******************************************************************************
 548 *******************************************************************************/
 549 kern_return_t
 550 kxld_symtab_relocate(KXLDSymtab *symtab, const KXLDArray *sectarray)
 551 {
 552     kern_return_t rval = KERN_FAILURE;
 553     KXLDSymtabIterator iter;
 554     KXLDSym *sym = NULL;
 555     const KXLDSect *sect = NULL;
 556
 557     check(symtab);
 558     check(sectarray);
 559
 560     kxld_symtab_iterator_init(&iter, symtab, kxld_sym_is_section, FALSE);
 561
 562     while ((sym = kxld_symtab_iterator_get_next(&iter))) {
 563         sect = kxld_array_get_item(sectarray, sym->sectnum);
 564         require_action(sect, finish, rval=KERN_FAILURE);
 565         kxld_sym_relocate(sym, sect);
 566     }
 567
 568     rval = KERN_SUCCESS;
 569
 570 finish:
 571
 572     return rval;
 573 }
 574
 575 /*******************************************************************************
 576 * This extends the symbol table and initializes the new symbol.  We insert the
 577 * symbol into the name index, but we don't bother with the c++ value index
 578 * because it is based on the base_addr of the symbol, and the base_addr of
 579 * all synthesized symbols will be 0.
 580 *******************************************************************************/
 581 kern_return_t
 582 kxld_symtab_add_symbol(KXLDSymtab *symtab, char *name, kxld_addr_t link_addr,
 583     KXLDSym **symout)
 584 {
 585     kern_return_t rval = KERN_FAILURE;
 586     KXLDSym *sym = NULL;
 587     u_int symindex = symtab->syms.nitems;
 588
 589     rval = kxld_array_resize(&symtab->syms, symindex + 1);
 590     require_noerr(rval, finish);
 591
 592     sym = kxld_array_get_item(&symtab->syms, symindex);
 593     kxld_sym_init_absolute(sym, name, link_addr);
 594
 595     rval = kxld_dict_insert(&symtab->name_index, sym->name, sym);
 596     require_noerr(rval, finish);
 597
 598     rval = KERN_SUCCESS;
 599     *symout = sym;
 600
 601 finish:
 602     return rval;
 603 }
 604
 605 /*******************************************************************************
 606 *******************************************************************************/
 607 KXLDSym *
 608 kxld_symtab_iterator_get_next(KXLDSymtabIterator *iter)
 609 {
 610     KXLDSym *sym = NULL;
 611     KXLDSym *tmp = NULL;
 612     boolean_t cmp = FALSE;
 613
 614     check(iter);
 615
 616     for (; iter->idx < iter->symtab->syms.nitems; ++iter->idx) {
 617         tmp = kxld_array_get_item(&iter->symtab->syms, iter->idx);
 618         cmp = iter->test(tmp);
 619         if (iter->negate) cmp = !cmp;
 620
 621         if (cmp) {
 622             sym = tmp;
 623             ++iter->idx;
 624             break;
 625         }
 626     }
 627
 628     return sym;
 629 }
 630
 631
 632 /*******************************************************************************
 633 *******************************************************************************/
 634 void
 635 kxld_symtab_iterator_reset(KXLDSymtabIterator *iter)
 636 {
 637     check(iter);
 638     iter->idx = 0;
 639 }
 640