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
44struct kxld_symtab {
45    KXLDArray syms;
46    KXLDDict cxx_index;
47    KXLDDict name_index;
48    char *strings;
49    u_int strsize;
50    boolean_t cxx_index_initialized;
51    boolean_t name_index_initialized;
52};
53
54/*******************************************************************************
55* Prototypes
56*******************************************************************************/
57
58static kern_return_t init_macho(KXLDSymtab *symtab, struct symtab_command *src,
59    u_char *macho, KXLDSeg * kernel_linkedit_seg,
60    boolean_t is_32_bit)
61    __attribute__((nonnull(1,2)));
62
63#if KXLD_USER_OR_ILP32
64static kern_return_t init_syms_32(KXLDSymtab *symtab, u_char *macho, u_long offset,
65    u_int nsyms);
66#endif
67#if KXLD_USER_OR_LP64
68static kern_return_t init_syms_64(KXLDSymtab *symtab, u_char *macho, u_long offset,
69    u_int nsyms);
70#endif
71
72static void restrict_private_symbols(KXLDSymtab *symtab)
73    __attribute__((nonnull));
74static boolean_t sym_is_defined_cxx(const KXLDSym *sym);
75static boolean_t sym_is_name_indexed(const KXLDSym *sym);
76
77/*******************************************************************************
78*******************************************************************************/
79size_t
80kxld_symtab_sizeof()
81{
82    return sizeof(KXLDSymtab);
83}
84
85#if KXLD_USER_OR_ILP32
86/*******************************************************************************
87*******************************************************************************/
88kern_return_t
89kxld_symtab_init_from_macho_32(KXLDSymtab *symtab, struct symtab_command *src,
90    u_char *macho, KXLDSeg * kernel_linkedit_seg)
91{
92    return init_macho(symtab, src, macho, kernel_linkedit_seg,
93        /* is_32_bit */ TRUE);
94}
95#endif /* KXLD_USER_ILP32 */
96
97#if KXLD_USER_OR_LP64
98/*******************************************************************************
99*******************************************************************************/
100kern_return_t
101kxld_symtab_init_from_macho_64(KXLDSymtab *symtab, struct symtab_command *src,
102    u_char *macho, KXLDSeg * kernel_linkedit_seg)
103{
104    return init_macho(symtab, src, macho, kernel_linkedit_seg,
105        /* is_32_bit */ FALSE);
106}
107#endif /* KXLD_USER_OR_LP64 */
108
109/*******************************************************************************
110*******************************************************************************/
111static kern_return_t
112init_macho(KXLDSymtab *symtab, struct symtab_command *src,
113    u_char *macho, KXLDSeg * kernel_linkedit_seg,
114    boolean_t is_32_bit __unused)
115{
116    kern_return_t rval = KERN_FAILURE;
117    u_long symoff;
118    u_char * macho_or_linkedit = macho;
119
120    check(symtab);
121    check(src);
122    check(macho);
123
124    /* Initialize the symbol array */
125
126    rval = kxld_array_init(&symtab->syms, sizeof(KXLDSym), src->nsyms);
127    require_noerr(rval, finish);
128
129    /* Initialize the string table */
130
131    if (kernel_linkedit_seg) {
132
133       /* If initing the kernel file in memory, we can't trust
134        * the symtab offsets directly, because the kernel file has been mapped
135        * into memory and the mach-o offsets are disk-based.
136        *
137        * The symoff is an offset relative to the linkedit segment
138        * so we just subtract the fileoffset of the linkedit segment
139        * to get its relative start.
140        *
141        * The strings table is an actual pointer, so we calculate that from
142        * the linkedit's vmaddr.
143        *
144        * Further, the init_syms_... functions need an adjusted base
145        * pointer instead of the beginning of the macho, so we substitute
146        * the base of the linkedit segment.
147        */
148
149        symoff = (u_long)(src->symoff - kernel_linkedit_seg->fileoff);
150        symtab->strings = (char *)(uintptr_t)kernel_linkedit_seg->base_addr +
151            src->stroff - kernel_linkedit_seg->fileoff;
152        macho_or_linkedit = (u_char *)(uintptr_t)kernel_linkedit_seg->base_addr;
153    } else {
154        symoff = (u_long)src->symoff;
155        symtab->strings = (char *) (macho + src->stroff);
156    }
157
158    symtab->strsize = src->strsize;
159
160    /* Initialize the symbols */
161
162    KXLD_3264_FUNC(is_32_bit, rval,
163        init_syms_32, init_syms_64,
164        symtab, macho_or_linkedit, symoff, src->nsyms);
165    require_noerr(rval, finish);
166
167    /* Some symbols must be forced private for compatibility */
168    (void) restrict_private_symbols(symtab);
169
170    /* Save the output */
171
172    rval = KERN_SUCCESS;
173
174finish:
175    return rval;
176}
177
178#if KXLD_USER_OR_ILP32
179/*******************************************************************************
180* In the running kernel, 'macho' is actually the start of the linkedit segment.
181*******************************************************************************/
182static kern_return_t
183init_syms_32(KXLDSymtab *symtab, u_char *macho, u_long offset, u_int nsyms)
184{
185    kern_return_t rval = KERN_FAILURE;
186    KXLDSym *sym = NULL;
187    u_int i = 0;
188    struct nlist *src_syms = (struct nlist *) ((void *) (macho + offset));
189
190    for (i = 0; i < nsyms; ++i) {
191        sym = kxld_array_get_item(&symtab->syms, i);
192        require_action(sym, finish, rval=KERN_FAILURE);
193
194        rval = kxld_sym_init_from_macho32(sym, symtab->strings, &src_syms[i]);
195        require_noerr(rval, finish);
196    }
197
198    rval = KERN_SUCCESS;
199
200finish:
201    return rval;
202}
203#endif /* KXLD_USER_OR_ILP32 */
204
205#if KXLD_USER_OR_LP64
206/*******************************************************************************
207* In the running kernel, 'macho' is actually the start of the linkedit segment.
208*******************************************************************************/
209static kern_return_t
210init_syms_64(KXLDSymtab *symtab, u_char *macho, u_long offset, u_int nsyms)
211{
212    kern_return_t rval = KERN_FAILURE;
213    KXLDSym *sym = NULL;
214    u_int i = 0;
215    struct nlist_64 *src_syms = (struct nlist_64 *) ((void *) (macho + offset));
216
217    for (i = 0; i < nsyms; ++i) {
218        sym = kxld_array_get_item(&symtab->syms, i);
219        require_action(sym, finish, rval=KERN_FAILURE);
220
221        rval = kxld_sym_init_from_macho64(sym, symtab->strings, &src_syms[i]);
222        require_noerr(rval, finish);
223    }
224
225    rval = KERN_SUCCESS;
226
227finish:
228    return rval;
229}
230#endif /* KXLD_USER_OR_LP64 */
231
232/*******************************************************************************
233* Temporary workaround for PR-6668105
234* new, new[], delete, and delete[] may be overridden globally in a kext.
235* We should do this with some sort of weak symbols, but we'll use a whitelist
236* for now to minimize risk.
237*******************************************************************************/
238static void
239restrict_private_symbols(KXLDSymtab *symtab)
240{
241    const char *private_symbols[] = {
242        KXLD_KMOD_INFO_SYMBOL,
243        KXLD_OPERATOR_NEW_SYMBOL,
244        KXLD_OPERATOR_NEW_ARRAY_SYMBOL,
245        KXLD_OPERATOR_DELETE_SYMBOL,
246        KXLD_OPERATOR_DELETE_ARRAY_SYMBOL
247    };
248    KXLDSymtabIterator iter;
249    KXLDSym *sym = NULL;
250    const char *name = NULL;
251    u_int i = 0;
252
253    kxld_symtab_iterator_init(&iter, symtab, kxld_sym_is_exported, FALSE);
254    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
255        for (i = 0; i < const_array_len(private_symbols); ++i) {
256            name = private_symbols[i];
257            if (!streq(sym->name, name)) {
258                continue;
259            }
260
261            kxld_sym_mark_private(sym);
262        }
263    }
264}
265
266
267/*******************************************************************************
268*******************************************************************************/
269void
270kxld_symtab_iterator_init(KXLDSymtabIterator *iter, const KXLDSymtab *symtab,
271    KXLDSymPredicateTest test, boolean_t negate)
272{
273    check(iter);
274    check(symtab);
275    check(test);
276
277    iter->symtab = symtab;
278    iter->idx = 0;
279    iter->test = test;
280    iter->negate = negate;
281}
282
283/*******************************************************************************
284*******************************************************************************/
285void
286kxld_symtab_clear(KXLDSymtab *symtab)
287{
288    check(symtab);
289
290    kxld_array_clear(&symtab->syms);
291    kxld_dict_clear(&symtab->cxx_index);
292    kxld_dict_clear(&symtab->name_index);
293    symtab->strings = NULL;
294    symtab->strsize = 0;
295    symtab->cxx_index_initialized = 0;
296    symtab->name_index_initialized = 0;
297}
298
299/*******************************************************************************
300*******************************************************************************/
301void
302kxld_symtab_deinit(KXLDSymtab *symtab)
303{
304    check(symtab);
305
306    kxld_array_deinit(&symtab->syms);
307    kxld_dict_deinit(&symtab->cxx_index);
308    kxld_dict_deinit(&symtab->name_index);
309    bzero(symtab, sizeof(*symtab));
310}
311
312/*******************************************************************************
313*******************************************************************************/
314u_int
315kxld_symtab_get_num_symbols(const KXLDSymtab *symtab)
316{
317    check(symtab);
318
319    return symtab->syms.nitems;
320}
321
322/*******************************************************************************
323*******************************************************************************/
324KXLDSym *
325kxld_symtab_get_symbol_by_index(const KXLDSymtab *symtab, u_int idx)
326{
327    check(symtab);
328
329    return kxld_array_get_item(&symtab->syms, idx);
330}
331
332/*******************************************************************************
333*******************************************************************************/
334KXLDSym *
335kxld_symtab_get_symbol_by_name(const KXLDSymtab *symtab, const char *name)
336{
337    KXLDSym *sym = NULL;
338    u_int i = 0;
339
340    for (i = 0; i < symtab->syms.nitems; ++i) {
341        sym = kxld_array_get_item(&symtab->syms, i);
342
343        if (streq(sym->name, name)) {
344            return sym;
345        }
346    }
347
348    return NULL;
349}
350
351/*******************************************************************************
352*******************************************************************************/
353KXLDSym *
354kxld_symtab_get_locally_defined_symbol_by_name(const KXLDSymtab *symtab,
355    const char *name)
356{
357    check(symtab);
358    check(name);
359
360    return kxld_dict_find(&symtab->name_index, name);
361}
362
363/*******************************************************************************
364*******************************************************************************/
365KXLDSym *
366kxld_symtab_get_cxx_symbol_by_value(const KXLDSymtab *symtab, kxld_addr_t value)
367{
368    check(symtab);
369
370    return kxld_dict_find(&symtab->cxx_index, &value);
371}
372
373/*******************************************************************************
374*******************************************************************************/
375kern_return_t
376kxld_symtab_get_sym_index(const KXLDSymtab *symtab, const KXLDSym *sym,
377    u_int *symindex)
378{
379    kern_return_t rval = KERN_FAILURE;
380
381    rval = kxld_array_get_index(&symtab->syms, sym, symindex);
382    require_noerr(rval, finish);
383
384    rval = KERN_SUCCESS;
385
386finish:
387    return rval;
388}
389
390/*******************************************************************************
391*******************************************************************************/
392u_long
393kxld_symtab_get_macho_header_size(void)
394{
395    return sizeof(struct symtab_command);
396}
397
398/*******************************************************************************
399*******************************************************************************/
400u_long
401kxld_symtab_get_macho_data_size(const KXLDSymtab *symtab, boolean_t is_32_bit)
402{
403    KXLDSymtabIterator iter;
404    KXLDSym *sym = NULL;
405    u_long size = 1; /* strtab start padding */
406    u_int nsyms = 0;
407
408    check(symtab);
409
410    kxld_symtab_iterator_init(&iter, symtab,
411        kxld_sym_is_defined_locally, FALSE);
412
413    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
414        size += strlen(sym->name) + 1;
415        ++nsyms;
416    }
417
418    if (is_32_bit) {
419        size += nsyms * sizeof(struct nlist);
420    } else {
421        size += nsyms * sizeof(struct nlist_64);
422    }
423
424    size = (size + 7) & ~7;
425
426    return size;
427}
428
429/*******************************************************************************
430*******************************************************************************/
431kern_return_t
432kxld_symtab_export_macho(const KXLDSymtab *symtab, u_char *buf,
433    u_long *header_offset, u_long header_size,
434    u_long *data_offset, u_long data_size,
435    boolean_t is_32_bit)
436{
437    kern_return_t rval = KERN_FAILURE;
438    KXLDSymtabIterator iter;
439    KXLDSym *sym = NULL;
440    struct symtab_command *symtabhdr = NULL;
441    u_char *nl = NULL;
442    u_long nlistsize = 0;
443    char *strtab = NULL;
444    u_long stroff = 1; /* strtab start padding */
445
446    check(symtab);
447    check(buf);
448    check(header_offset);
449    check(data_offset);
450
451    require_action(sizeof(*symtabhdr) <= header_size - *header_offset,
452        finish, rval=KERN_FAILURE);
453    symtabhdr = (struct symtab_command *) ((void *) (buf + *header_offset));
454    *header_offset += sizeof(*symtabhdr);
455
456    /* Initialize the symbol table header */
457
458    symtabhdr->cmd = LC_SYMTAB;
459    symtabhdr->cmdsize = (uint32_t) sizeof(*symtabhdr);
460    symtabhdr->symoff = (uint32_t) *data_offset;
461    symtabhdr->strsize = 1; /* strtab start padding */
462
463    /* Find the size of the symbol and string tables */
464
465    kxld_symtab_iterator_init(&iter, symtab,
466        kxld_sym_is_defined_locally, FALSE);
467
468    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
469        symtabhdr->nsyms++;
470        symtabhdr->strsize += (uint32_t) (strlen(sym->name) + 1);
471    }
472
473    if (is_32_bit) {
474        nlistsize = sizeof(struct nlist);
475    } else {
476        nlistsize = sizeof(struct nlist_64);
477    }
478
479    symtabhdr->stroff = (uint32_t) (symtabhdr->symoff +
480        (symtabhdr->nsyms * nlistsize));
481    require_action(symtabhdr->stroff + symtabhdr->strsize <= data_size, finish,
482        rval=KERN_FAILURE);
483
484    /* Get pointers to the symbol and string tables */
485
486    nl = buf + symtabhdr->symoff;
487    strtab = (char *) (buf + symtabhdr->stroff);
488
489    /* Copy over the symbols */
490
491    kxld_symtab_iterator_reset(&iter);
492    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
493
494        KXLD_3264_FUNC(is_32_bit, rval,
495            kxld_sym_export_macho_32, kxld_sym_export_macho_64,
496            sym, nl, strtab, &stroff, symtabhdr->strsize);
497        require_noerr(rval, finish);
498
499        nl += nlistsize;
500        stroff += rval;
501    }
502
503    /* Update the data offset */
504    *data_offset += (symtabhdr->nsyms * nlistsize) + stroff;
505
506    *data_offset = (*data_offset + 7) & ~7;
507
508    rval = KERN_SUCCESS;
509
510finish:
511    return rval;
512}
513
514/*******************************************************************************
515*******************************************************************************/
516u_int
517kxld_symtab_iterator_get_num_remaining(const KXLDSymtabIterator *iter)
518{
519    u_int idx = 0;
520    u_int count = 0;
521
522    check(iter);
523
524    for (idx = iter->idx; idx < iter->symtab->syms.nitems; ++idx) {
525        count += iter->test(kxld_array_get_item(&iter->symtab->syms, idx));
526    }
527
528    return count;
529}
530
531/*******************************************************************************
532*******************************************************************************/
533kern_return_t
534kxld_symtab_index_cxx_symbols_by_value(KXLDSymtab *symtab)
535{
536    kern_return_t rval = KERN_FAILURE;
537    KXLDSymtabIterator iter;
538    KXLDSym *sym = NULL;
539    u_int nsyms = 0;
540
541    check(symtab);
542
543    if (symtab->cxx_index_initialized) {
544        rval = KERN_SUCCESS;
545        goto finish;
546    }
547
548    /* Count the number of C++ symbols */
549    kxld_symtab_iterator_init(&iter, symtab, sym_is_defined_cxx, FALSE);
550    nsyms = kxld_symtab_iterator_get_num_remaining(&iter);
551
552    /* Create the dictionary */
553    rval = kxld_dict_init(&symtab->cxx_index, kxld_dict_kxldaddr_hash,
554        kxld_dict_kxldaddr_cmp, nsyms);
555    require_noerr(rval, finish);
556
557    /* Insert the non-stab symbols */
558    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
559        rval = kxld_dict_insert(&symtab->cxx_index, &sym->base_addr, sym);
560        require_noerr(rval, finish);
561    }
562
563    symtab->cxx_index_initialized = TRUE;
564    rval = KERN_SUCCESS;
565finish:
566    return rval;
567}
568
569/*******************************************************************************
570*******************************************************************************/
571static boolean_t
572sym_is_defined_cxx(const KXLDSym *sym)
573{
574    return (kxld_sym_is_defined_locally(sym) && kxld_sym_is_cxx(sym));
575}
576
577/*******************************************************************************
578*******************************************************************************/
579kern_return_t
580kxld_symtab_index_symbols_by_name(KXLDSymtab *symtab)
581{
582    kern_return_t rval = KERN_FAILURE;
583    KXLDSymtabIterator iter;
584    KXLDSym *sym = NULL;
585    u_int nsyms = 0;
586
587    check(symtab);
588
589    if (symtab->name_index_initialized) {
590        rval = KERN_SUCCESS;
591        goto finish;
592    }
593
594    /* Count the number of symbols we need to index by name */
595    kxld_symtab_iterator_init(&iter, symtab, sym_is_name_indexed, FALSE);
596    nsyms = kxld_symtab_iterator_get_num_remaining(&iter);
597
598    /* Create the dictionary */
599    rval = kxld_dict_init(&symtab->name_index, kxld_dict_string_hash,
600        kxld_dict_string_cmp, nsyms);
601    require_noerr(rval, finish);
602
603    /* Insert the non-stab symbols */
604    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
605        rval = kxld_dict_insert(&symtab->name_index, sym->name, sym);
606        require_noerr(rval, finish);
607    }
608
609    symtab->name_index_initialized = TRUE;
610    rval = KERN_SUCCESS;
611finish:
612
613    return rval;
614}
615/*******************************************************************************
616*******************************************************************************/
617static boolean_t
618sym_is_name_indexed(const KXLDSym *sym)
619{
620    return (kxld_sym_is_defined_locally(sym) && !kxld_sym_is_stab(sym));
621}
622
623/*******************************************************************************
624*******************************************************************************/
625kern_return_t
626kxld_symtab_relocate(KXLDSymtab *symtab, const KXLDArray *sectarray)
627{
628    kern_return_t rval = KERN_FAILURE;
629    KXLDSymtabIterator iter;
630    KXLDSym *sym = NULL;
631    const KXLDSect *sect = NULL;
632
633    check(symtab);
634    check(sectarray);
635
636    kxld_symtab_iterator_init(&iter, symtab, kxld_sym_is_section, FALSE);
637
638    while ((sym = kxld_symtab_iterator_get_next(&iter))) {
639        sect = kxld_array_get_item(sectarray, sym->sectnum);
640        require_action(sect, finish, rval=KERN_FAILURE);
641        kxld_sym_relocate(sym, sect);
642    }
643
644    rval = KERN_SUCCESS;
645
646finish:
647
648    return rval;
649}
650
651/*******************************************************************************
652* This extends the symbol table and initializes the new symbol.  We insert the
653* symbol into the name index, but we don't bother with the c++ value index
654* because it is based on the base_addr of the symbol, and the base_addr of
655* all synthesized symbols will be 0.
656*******************************************************************************/
657kern_return_t
658kxld_symtab_add_symbol(KXLDSymtab *symtab, char *name, kxld_addr_t link_addr,
659    KXLDSym **symout)
660{
661    kern_return_t rval = KERN_FAILURE;
662    KXLDSym *sym = NULL;
663    u_int symindex = symtab->syms.nitems;
664
665    rval = kxld_array_resize(&symtab->syms, symindex + 1);
666    require_noerr(rval, finish);
667
668    sym = kxld_array_get_item(&symtab->syms, symindex);
669    kxld_sym_init_absolute(sym, name, link_addr);
670
671    rval = kxld_dict_insert(&symtab->name_index, sym->name, sym);
672    require_noerr(rval, finish);
673
674    rval = KERN_SUCCESS;
675    *symout = sym;
676
677finish:
678    return rval;
679}
680
681/*******************************************************************************
682*******************************************************************************/
683KXLDSym *
684kxld_symtab_iterator_get_next(KXLDSymtabIterator *iter)
685{
686    KXLDSym *sym = NULL;
687    KXLDSym *tmp = NULL;
688    boolean_t cmp = FALSE;
689
690    check(iter);
691
692    for (; iter->idx < iter->symtab->syms.nitems; ++iter->idx) {
693        tmp = kxld_array_get_item(&iter->symtab->syms, iter->idx);
694        cmp = iter->test(tmp);
695        if (iter->negate) cmp = !cmp;
696
697        if (cmp) {
698            sym = tmp;
699            ++iter->idx;
700            break;
701        }
702    }
703
704    return sym;
705}
706
707
708/*******************************************************************************
709*******************************************************************************/
710void
711kxld_symtab_iterator_reset(KXLDSymtabIterator *iter)
712{
713    check(iter);
714    iter->idx = 0;
715}
716
717