1/*
2 * Copyright (c) 2007-2008, 2012 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 <sys/types.h>
30#include <mach/vm_param.h>  /* For PAGE_SIZE */
31
32#define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld"
33#include <AssertMacros.h>
34
35#if !KERNEL
36    #include "kxld.h"
37    #include "kxld_types.h"
38#else
39    #include <libkern/kxld.h>
40    #include <libkern/kxld_types.h>
41#endif /* KERNEL */
42
43#include "kxld_array.h"
44#include "kxld_dict.h"
45#include "kxld_kext.h"
46#include "kxld_object.h"
47#include "kxld_sym.h"
48#include "kxld_symtab.h"
49#include "kxld_util.h"
50#include "kxld_vtable.h"
51
52struct kxld_vtable;
53
54struct kxld_context {
55    KXLDKext *kext;
56    KXLDArray *section_order;
57    KXLDArray objects;
58    KXLDArray dependencies;
59    KXLDDict defined_symbols_by_name;
60    KXLDDict defined_cxx_symbols_by_value;
61    KXLDDict obsolete_symbols_by_name;
62    KXLDDict vtables_by_name;
63    KXLDFlags flags;
64    KXLDAllocateCallback allocate_callback;
65    cpu_type_t cputype;
66    cpu_subtype_t cpusubtype;
67};
68
69/*******************************************************************************
70* Globals
71*******************************************************************************/
72
73/* Certain architectures alter the order of a kext's sections from its input
74 * binary, so we track that order in a dictionary of arrays, with one array for
75 * each architecture.  Since the kernel only has one architecture, we can
76 * eliminate the dictionary and use a simple array.
77 * XXX: If we ever use the linker in a multithreaded environment, we will need
78 * locks around these global structures.
79 */
80#if KXLD_USER_OR_OBJECT
81#if KERNEL
82static KXLDArray *s_section_order;
83#else
84static KXLDDict *s_order_dict;
85#endif
86#endif
87
88/*******************************************************************************
89* Prototypes
90*******************************************************************************/
91
92static kern_return_t init_context(KXLDContext *context, u_int ndependencies);
93static kern_return_t init_kext_objects(KXLDContext *context, u_char *file,
94    u_long size, const char *name, KXLDDependency *dependencies,
95    u_int ndependencies);
96static KXLDObject * get_object_for_file(KXLDContext *context,
97    u_char *file, u_long size, const char *name);
98static u_char * allocate_kext(KXLDContext *context, void *callback_data,
99    kxld_addr_t *vmaddr, u_long *vmsize, u_char **linked_object_alloc_out);
100static void clear_context(KXLDContext *context);
101
102/*******************************************************************************
103*******************************************************************************/
104kern_return_t
105kxld_create_context(KXLDContext **_context,
106    KXLDAllocateCallback allocate_callback, KXLDLoggingCallback logging_callback,
107    KXLDFlags flags, cpu_type_t cputype, cpu_subtype_t cpusubtype)
108{
109    kern_return_t rval = KERN_FAILURE;
110    KXLDContext       * context         = NULL;
111    KXLDArray         * section_order   = NULL;
112#if !KERNEL
113    cpu_type_t        * cputype_p       = NULL;
114#endif
115
116    check(_context);
117    check(allocate_callback);
118    check(logging_callback);
119    *_context = NULL;
120
121    context = kxld_alloc(sizeof(*context));
122    require_action(context, finish, rval=KERN_RESOURCE_SHORTAGE);
123    bzero(context, sizeof(*context));
124
125    context->flags = flags;
126    context->allocate_callback = allocate_callback;
127    context->cputype = cputype;
128    context->cpusubtype = cpusubtype;
129
130    kxld_set_logging_callback(logging_callback);
131
132    context->kext = kxld_alloc(kxld_kext_sizeof());
133    require_action(context->kext, finish, rval=KERN_RESOURCE_SHORTAGE);
134    bzero(context->kext, kxld_kext_sizeof());
135
136    /* Check if we already have an order array for this arch */
137
138#if KXLD_USER_OR_OBJECT
139#if KERNEL
140    context->section_order = s_section_order;
141#else
142    /* In userspace, create the dictionary if it doesn't already exist */
143    if (!s_order_dict) {
144        s_order_dict = kxld_alloc(sizeof(*s_order_dict));
145        require_action(s_order_dict, finish, rval=KERN_RESOURCE_SHORTAGE);
146        bzero(s_order_dict, sizeof(*s_order_dict));
147
148        rval = kxld_dict_init(s_order_dict, kxld_dict_uint32_hash,
149            kxld_dict_uint32_cmp, 0);
150        require_noerr(rval, finish);
151    }
152
153    context->section_order = kxld_dict_find(s_order_dict, &cputype);
154#endif /* KERNEL */
155
156    /* Create an order array for this arch if needed */
157
158    if (!context->section_order) {
159
160        section_order = kxld_alloc(sizeof(*section_order));
161        require_action(section_order, finish, rval=KERN_RESOURCE_SHORTAGE);
162        bzero(section_order, sizeof(*section_order));
163
164#if KERNEL
165        s_section_order = section_order;
166#else
167        /* In userspace, add the new array to the order dictionary */
168        cputype_p = kxld_alloc(sizeof(*cputype_p));
169        require_action(cputype_p, finish, rval=KERN_RESOURCE_SHORTAGE);
170        *cputype_p = cputype;
171
172        rval = kxld_dict_insert(s_order_dict, cputype_p, section_order);
173        require_noerr(rval, finish);
174
175        cputype_p = NULL;
176#endif /* KERNEL */
177
178        context->section_order = section_order;
179
180        section_order = NULL;
181    }
182#endif /* KXLD_USER_OR_OBJECT */
183
184    rval = KERN_SUCCESS;
185    *_context = context;
186    context = NULL;
187
188finish:
189    if (context) kxld_destroy_context(context);
190    if (section_order) kxld_free(section_order, sizeof(*section_order));
191#if !KERNEL
192    if (cputype_p) kxld_free(cputype_p, sizeof(*cputype_p));
193#endif
194
195    return rval;
196}
197
198/*******************************************************************************
199*******************************************************************************/
200void
201kxld_destroy_context(KXLDContext *context)
202{
203    KXLDObject *object = NULL;
204    KXLDKext *dep = NULL;
205    u_int i = 0;
206
207    check(context);
208
209    kxld_kext_deinit(context->kext);
210
211    for (i = 0; i < context->objects.maxitems; ++i) {
212        object = kxld_array_get_slot(&context->objects, i);
213        kxld_object_deinit(object);
214    }
215    kxld_array_deinit(&context->objects);
216
217    for (i = 0; i < context->dependencies.maxitems; ++i) {
218        dep = kxld_array_get_slot(&context->dependencies, i);
219        kxld_kext_deinit(dep);
220    }
221    kxld_array_deinit(&context->dependencies);
222
223    kxld_dict_deinit(&context->defined_symbols_by_name);
224    kxld_dict_deinit(&context->defined_cxx_symbols_by_value);
225    kxld_dict_deinit(&context->obsolete_symbols_by_name);
226    kxld_dict_deinit(&context->vtables_by_name);
227
228    kxld_free(context->kext, kxld_kext_sizeof());
229    kxld_free(context, sizeof(*context));
230
231    kxld_print_memory_report();
232}
233
234/*******************************************************************************
235*******************************************************************************/
236kern_return_t
237kxld_link_file(
238    KXLDContext       * context,
239    u_char            * file,
240    u_long              size,
241    const char        * name,
242    void              * callback_data,
243    KXLDDependency    * dependencies,
244    u_int               ndependencies,
245    u_char           ** linked_object_out,
246    kxld_addr_t       * kmod_info_kern)
247{
248    kern_return_t       rval                    = KERN_FAILURE;
249    kxld_addr_t         vmaddr                  = 0;
250    u_long              vmsize                  = 0;
251    u_char            * linked_object           = NULL;
252    u_char            * linked_object_alloc     = NULL;
253
254    kxld_set_logging_callback_data(name, callback_data);
255
256    kxld_log(kKxldLogLinking, kKxldLogBasic, "Linking kext %s", name);
257
258    require_action(context, finish, rval=KERN_INVALID_ARGUMENT);
259    require_action(file, finish, rval=KERN_INVALID_ARGUMENT);
260    require_action(size, finish, rval=KERN_INVALID_ARGUMENT);
261    require_action(dependencies, finish, rval=KERN_INVALID_ARGUMENT);
262    require_action(ndependencies, finish, rval=KERN_INVALID_ARGUMENT);
263    require_action(linked_object_out, finish, rval=KERN_INVALID_ARGUMENT);
264    require_action(kmod_info_kern, finish, rval=KERN_INVALID_ARGUMENT);
265
266    rval = init_context(context, ndependencies);
267    require_noerr(rval, finish);
268
269    rval = init_kext_objects(context, file, size, name,
270        dependencies, ndependencies);
271    require_noerr(rval, finish);
272
273    linked_object = allocate_kext(context, callback_data,
274        &vmaddr, &vmsize, &linked_object_alloc);
275    require_action(linked_object, finish, rval=KERN_RESOURCE_SHORTAGE);
276
277    rval = kxld_kext_relocate(context->kext, vmaddr,
278        &context->vtables_by_name,
279        &context->defined_symbols_by_name,
280        &context->obsolete_symbols_by_name,
281        &context->defined_cxx_symbols_by_value);
282    require_noerr(rval, finish);
283
284    rval = kxld_kext_export_linked_object(context->kext,
285        linked_object, kmod_info_kern);
286    require_noerr(rval, finish);
287
288    *linked_object_out = linked_object;
289    linked_object_alloc = NULL;
290
291    rval = KERN_SUCCESS;
292finish:
293    if (linked_object_alloc) {
294        kxld_page_free_untracked(linked_object_alloc, vmsize);
295    }
296
297    clear_context(context);
298    kxld_set_logging_callback_data(NULL, NULL);
299
300    return rval;
301}
302
303/*******************************************************************************
304*******************************************************************************/
305static kern_return_t
306init_context(KXLDContext *context, u_int ndependencies)
307{
308    kern_return_t rval = KERN_FAILURE;
309
310    /* Create an array of objects large enough to hold an object
311     * for every dependency, an interface for each dependency, and a kext. */
312    rval = kxld_array_init(&context->objects,
313        kxld_object_sizeof(), 2 * ndependencies + 1);
314    require_noerr(rval, finish);
315
316    rval = kxld_array_init(&context->dependencies,
317        kxld_kext_sizeof(), ndependencies);
318    require_noerr(rval, finish);
319
320    rval = kxld_dict_init(&context->defined_symbols_by_name,
321        kxld_dict_string_hash, kxld_dict_string_cmp, 0);
322    require_noerr(rval, finish);
323
324    rval = kxld_dict_init(&context->defined_cxx_symbols_by_value,
325        kxld_dict_kxldaddr_hash, kxld_dict_kxldaddr_cmp, 0);
326    require_noerr(rval, finish);
327
328    rval = kxld_dict_init(&context->obsolete_symbols_by_name,
329        kxld_dict_string_hash, kxld_dict_string_cmp, 0);
330    require_noerr(rval, finish);
331
332    rval = kxld_dict_init(&context->vtables_by_name, kxld_dict_string_hash,
333        kxld_dict_string_cmp, 0);
334    require_noerr(rval, finish);
335
336    rval = KERN_SUCCESS;
337finish:
338    return rval;
339}
340
341/*******************************************************************************
342*******************************************************************************/
343static kern_return_t
344init_kext_objects(KXLDContext *context, u_char *file, u_long size,
345    const char *name, KXLDDependency *dependencies, u_int ndependencies)
346{
347    kern_return_t rval = KERN_FAILURE;
348    KXLDKext *kext = NULL;
349    KXLDObject *kext_object = NULL;
350    KXLDObject *interface_object = NULL;
351    u_int i = 0;
352
353    /* Create a kext object for each dependency.  If it's a direct dependency,
354     * export its symbols by name by value.  If it's indirect, just export the
355     * C++ symbols by value.
356     */
357    for (i = 0; i < ndependencies; ++i) {
358        kext = kxld_array_get_item(&context->dependencies, i);
359        kext_object = NULL;
360        interface_object = NULL;
361
362        kext_object = get_object_for_file(context, dependencies[i].kext,
363            dependencies[i].kext_size, dependencies[i].kext_name);
364        require_action(kext_object, finish, rval=KERN_FAILURE);
365
366        if (dependencies[i].interface) {
367            interface_object = get_object_for_file(context,
368                dependencies[i].interface, dependencies[i].interface_size,
369                dependencies[i].interface_name);
370            require_action(interface_object, finish, rval=KERN_FAILURE);
371        }
372
373        rval = kxld_kext_init(kext, kext_object, interface_object);
374        require_noerr(rval, finish);
375
376        if (dependencies[i].is_direct_dependency) {
377            rval = kxld_kext_export_symbols(kext,
378                &context->defined_symbols_by_name,
379                &context->obsolete_symbols_by_name,
380                &context->defined_cxx_symbols_by_value);
381            require_noerr(rval, finish);
382        } else {
383            rval = kxld_kext_export_symbols(kext,
384                /* defined_symbols */ NULL, /* obsolete_symbols */ NULL,
385                &context->defined_cxx_symbols_by_value);
386            require_noerr(rval, finish);
387        }
388    }
389
390    /* Export the vtables for all of the dependencies. */
391    for (i = 0; i < context->dependencies.nitems; ++i) {
392        kext = kxld_array_get_item(&context->dependencies, i);
393
394        rval = kxld_kext_export_vtables(kext,
395            &context->defined_cxx_symbols_by_value,
396            &context->defined_symbols_by_name,
397            &context->vtables_by_name);
398        require_noerr(rval, finish);
399    }
400
401    /* Create a kext object for the kext we're linking and export its locally
402     * defined C++ symbols.
403     */
404    kext_object = get_object_for_file(context, file, size, name);
405    require_action(kext_object, finish, rval=KERN_FAILURE);
406
407    rval = kxld_kext_init(context->kext, kext_object, /* interface */ NULL);
408    require_noerr(rval, finish);
409
410    rval = kxld_kext_export_symbols(context->kext,
411        /* defined_symbols */ NULL, /* obsolete_symbols */ NULL,
412        &context->defined_cxx_symbols_by_value);
413    require_noerr(rval, finish);
414
415    rval = KERN_SUCCESS;
416finish:
417    return rval;
418}
419
420/*******************************************************************************
421*******************************************************************************/
422static KXLDObject *
423get_object_for_file(KXLDContext *context, u_char *file, u_long size,
424    const char *name)
425{
426    KXLDObject *rval = NULL;
427    KXLDObject *object = NULL;
428    kern_return_t result = 0;
429    u_int i = 0;
430
431    for (i = 0; i < context->objects.nitems; ++i) {
432        object = kxld_array_get_item(&context->objects, i);
433
434        if (!kxld_object_get_file(object)) {
435            result = kxld_object_init_from_macho(object, file, size, name,
436                context->section_order, context->cputype, context->cpusubtype, context->flags);
437            require_noerr(result, finish);
438
439            rval = object;
440            break;
441        }
442
443        if (kxld_object_get_file(object) == file) {
444            rval = object;
445            break;
446        }
447    }
448
449finish:
450    return rval;
451}
452
453/*******************************************************************************
454*******************************************************************************/
455static u_char *
456allocate_kext(KXLDContext *context, void *callback_data,
457    kxld_addr_t *vmaddr_out, u_long *vmsize_out,
458    u_char **linked_object_alloc_out)
459{
460    KXLDAllocateFlags   flags                   = 0;
461    kxld_addr_t         vmaddr                  = 0;
462    u_long              vmsize                  = 0;
463    u_long              header_size             = 0;
464    u_char            * linked_object           = NULL;
465
466    *linked_object_alloc_out = NULL;
467
468    kxld_kext_get_vmsize(context->kext, &header_size, &vmsize);
469    vmaddr = context->allocate_callback(vmsize, &flags, callback_data);
470    require_action(!(vmaddr & (PAGE_SIZE-1)), finish,
471        kxld_log(kKxldLogLinking, kKxldLogErr,
472            "Load address %p is not page-aligned.",
473            (void *) (uintptr_t) vmaddr));
474
475    if (flags & kKxldAllocateWritable) {
476        linked_object = (u_char *) (u_long) vmaddr;
477    } else {
478        linked_object = kxld_page_alloc_untracked(vmsize);
479        require(linked_object, finish);
480
481        *linked_object_alloc_out = linked_object;
482    }
483
484    kxld_kext_set_linked_object_size(context->kext, vmsize);
485
486    /* Zero out the memory before we fill it.  We fill this buffer in a
487     * sparse fashion, and it's simpler to clear it now rather than
488     * track and zero any pieces we didn't touch after we've written
489     * all of the sections to memory.
490     */
491    bzero(linked_object, vmsize);
492    *vmaddr_out = vmaddr;
493    *vmsize_out = vmsize;
494
495finish:
496    return linked_object;
497}
498
499/*******************************************************************************
500*******************************************************************************/
501static void
502clear_context(KXLDContext *context)
503{
504    KXLDObject * object = NULL;
505    KXLDKext   * dep     = NULL;
506    u_int i = 0;
507
508    check(context);
509
510    kxld_kext_clear(context->kext);
511
512    for (i = 0; i < context->objects.nitems; ++i) {
513        object = kxld_array_get_item(&context->objects, i);
514        kxld_object_clear(object);
515    }
516    kxld_array_reset(&context->objects);
517
518    for (i = 0; i < context->dependencies.nitems; ++i) {
519        dep = kxld_array_get_item(&context->dependencies, i);
520        kxld_kext_clear(dep);
521    }
522    kxld_array_reset(&context->dependencies);
523
524    kxld_dict_clear(&context->defined_symbols_by_name);
525    kxld_dict_clear(&context->defined_cxx_symbols_by_value);
526    kxld_dict_clear(&context->obsolete_symbols_by_name);
527    kxld_dict_clear(&context->vtables_by_name);
528}
529
530