/*
 * Copyright (c) 2007-2008 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
#include <string.h>
#include <mach/boolean.h>
#include <sys/types.h>

#if KERNEL
    #include <libkern/libkern.h>
    #include <mach/machine.h>
#else
    #include <stdlib.h>
    #include <libkern/OSByteOrder.h>

    /* Get machine.h from the kernel source so we can support all platforms
     * that the kernel supports. Otherwise we're at the mercy of the host.
     */
    #include "../../osfmk/mach/machine.h"
#endif

#define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld"
#include <AssertMacros.h>

#include "kxld_array.h"
#include "kxld_demangle.h"
#include "kxld_dict.h"
#include "kxld_reloc.h"
#include "kxld_sect.h"
#include "kxld_seg.h"
#include "kxld_sym.h"
#include "kxld_symtab.h"
#include "kxld_util.h"
#include "kxld_vtable.h"

#if KXLD_PIC_KEXTS
/* This will try to pull in mach/machine.h, so it has to come after the
 * explicit include above.
 */
#include <mach-o/loader.h>
#endif

/* include target-specific relocation prototypes */
#include <mach-o/reloc.h>
#if KXLD_USER_OR_X86_64
#include <mach-o/x86_64/reloc.h>
#endif
#if KXLD_USER_OR_ARM
#include <mach-o/arm/reloc.h>
#endif
#if KXLD_USER_OR_ARM64
#include <mach-o/arm64/reloc.h>
#endif

extern uint32_t     kaslr_offsets_index;
extern uint32_t     kaslr_offsets_count;
extern uint32_t    *kaslr_offsets;

#define KXLD_TARGET_NONE        (u_int) 0x0
#define KXLD_TARGET_VALUE       (u_int) 0x1
#define KXLD_TARGET_SECTNUM     (u_int) 0x2
#define KXLD_TARGET_SYMBOLNUM   (u_int) 0x3
#define KXLD_TARGET_LOOKUP      (u_int) 0x4
#define KXLD_TARGET_GOT         (u_int) 0x5

#define ABSOLUTE_VALUE(x) (((x) < 0) ? -(x) : (x))

#define LO16(x) (0x0000FFFF & x)
#define LO16S(x) ((0x0000FFFF & x) << 16)
#define HI16(x) (0xFFFF0000 & x)
#define HI16S(x) ((0xFFFF0000 & x) >> 16)
#define BIT15(x) (0x00008000 & x)
#define BR14I(x) (0xFFFF0003 & x)
#define BR14D(x) (0x0000FFFC & x)
#define BR24I(x) (0xFC000003 & x)
#define BR24D(x) (0x03FFFFFC & x)
#define HADISP 0x00010000
#define BR14_LIMIT 0x00008000
#define BR24_LIMIT 0x02000000
#define IS_COND_BR_INSTR(x) ((x & 0xFC000000) == 0x40000000)
#define IS_NOT_ALWAYS_TAKEN(x) ((x & 0x03E00000) != 0x02800000)
#define FLIP_PREDICT_BIT(x) x ^= 0x00200000

#define SIGN_EXTEND_MASK(n) (1 << ((n) - 1))
#define SIGN_EXTEND(x,n) (((x) ^ SIGN_EXTEND_MASK(n)) - SIGN_EXTEND_MASK(n))
#define BR14_NBITS_DISPLACEMENT 16
#define BR24_NBITS_DISPLACEMENT 26

#define X86_64_RIP_RELATIVE_LIMIT 0x80000000UL

/*******************************************************************************
* Prototypes
*******************************************************************************/
#if KXLD_USER_OR_I386
static boolean_t generic_reloc_has_pair(u_int _type) 
    __attribute__((const));
static u_int generic_reloc_get_pair_type(u_int _prev_type)
    __attribute__((const));
static boolean_t generic_reloc_has_got(u_int _type)
    __attribute__((const));
static kern_return_t generic_process_reloc(const KXLDRelocator *relocator,
    u_char *instruction, u_int length, u_int pcrel, kxld_addr_t base_pc, 
    kxld_addr_t link_pc, kxld_addr_t link_disp, u_int type, kxld_addr_t target, 
    kxld_addr_t pair_target, boolean_t swap);
#endif /* KXLD_USER_OR_I386 */

#if KXLD_USER_OR_X86_64 
static boolean_t x86_64_reloc_has_pair(u_int _type) 
    __attribute__((const));
static u_int x86_64_reloc_get_pair_type(u_int _prev_type) 
    __attribute__((const));
static boolean_t x86_64_reloc_has_got(u_int _type)
    __attribute__((const));
static kern_return_t x86_64_process_reloc(const KXLDRelocator *relocator, 
    u_char *instruction, u_int length, u_int pcrel, kxld_addr_t base_pc, 
    kxld_addr_t link_pc, kxld_addr_t link_disp, u_int type, kxld_addr_t target, 
    kxld_addr_t pair_target, boolean_t swap);
static kern_return_t calculate_displacement_x86_64(uint64_t target, 
    uint64_t adjustment, int32_t *instr32);
#endif /* KXLD_USER_OR_X86_64 */

#if KXLD_USER_OR_ARM
static boolean_t arm_reloc_has_pair(u_int _type) 
    __attribute__((const));
static u_int arm_reloc_get_pair_type(u_int _prev_type) 
    __attribute__((const));
static boolean_t arm_reloc_has_got(u_int _type)
    __attribute__((const));
static kern_return_t arm_process_reloc(const KXLDRelocator *relocator, 
    u_char *instruction, u_int length, u_int pcrel, kxld_addr_t base_pc, 
    kxld_addr_t link_pc, kxld_addr_t link_disp, u_int type, kxld_addr_t target, 
    kxld_addr_t pair_target, boolean_t swap);
#endif /* KXLD_USER_OR_ARM */

#if KXLD_USER_OR_ARM64
static boolean_t arm64_reloc_has_pair(u_int _type) 
    __attribute__((const));
static u_int arm64_reloc_get_pair_type(u_int _prev_type) 
    __attribute__((const));
static boolean_t arm64_reloc_has_got(u_int _type)
    __attribute__((const));
static kern_return_t arm64_process_reloc(const KXLDRelocator *relocator, 
    u_char *instruction, u_int length, u_int pcrel, kxld_addr_t base_pc, 
    kxld_addr_t link_pc, kxld_addr_t link_disp, u_int type, kxld_addr_t target, 
    kxld_addr_t pair_target, boolean_t swap);
#endif /* KXLD_USER_OR_ARM64 */

#if KXLD_USER_OR_ILP32
static kxld_addr_t get_pointer_at_addr_32(const KXLDRelocator *relocator, 
    const u_char *data, u_long offset)
    __attribute__((pure, nonnull));
#endif /* KXLD_USER_OR_ILP32 */
#if KXLD_USER_OR_LP64
static kxld_addr_t get_pointer_at_addr_64(const KXLDRelocator *relocator, 
    const u_char *data, u_long offset)
    __attribute__((pure, nonnull));
#endif /* KXLD_USER_OR_LP64 */

static u_int count_relocatable_relocs(const KXLDRelocator *relocator, 
    const struct relocation_info *relocs, u_int nrelocs)
    __attribute__((pure));

static kern_return_t calculate_targets(KXLDRelocator *relocator, 
    kxld_addr_t *_target, kxld_addr_t *_pair_target, const KXLDReloc *reloc);

static kxld_addr_t align_raw_function_address(const KXLDRelocator *relocator, 
    kxld_addr_t value);

static kern_return_t get_target_by_address_lookup(kxld_addr_t *target, 
    kxld_addr_t addr, const KXLDArray *sectarray);

static kern_return_t check_for_direct_pure_virtual_call(
    const KXLDRelocator *relocator, u_long offset);

#if KXLD_PIC_KEXTS
static u_long get_macho_data_size_for_array(const KXLDArray *relocs);

static kern_return_t export_macho_for_array(const KXLDRelocator *relocator,
    const KXLDArray *relocs, struct relocation_info **dstp);
#endif /* KXLD_PIC_KEXTS */

/*******************************************************************************
*******************************************************************************/
kern_return_t 
kxld_relocator_init(KXLDRelocator *relocator, u_char *file,
    const KXLDSymtab *symtab, const KXLDArray *sectarray, cpu_type_t cputype, 
    cpu_subtype_t cpusubtype __unused, boolean_t swap)
{
    kern_return_t rval = KERN_FAILURE;

    check(relocator);

    switch(cputype) {
#if KXLD_USER_OR_I386
    case CPU_TYPE_I386:
        relocator->reloc_has_pair = generic_reloc_has_pair;
        relocator->reloc_get_pair_type = generic_reloc_get_pair_type;
        relocator->reloc_has_got = generic_reloc_has_got;
        relocator->process_reloc = generic_process_reloc;
        relocator->function_align = 0;
        relocator->is_32_bit = TRUE;
        relocator->may_scatter = TRUE;
        break;
#endif /* KXLD_USER_OR_I386 */
#if KXLD_USER_OR_X86_64
    case CPU_TYPE_X86_64:
        relocator->reloc_has_pair = x86_64_reloc_has_pair;
        relocator->reloc_get_pair_type = x86_64_reloc_get_pair_type;
        relocator->reloc_has_got = x86_64_reloc_has_got;
        relocator->process_reloc = x86_64_process_reloc;
        relocator->function_align = 0;
        relocator->is_32_bit = FALSE;
        relocator->may_scatter = FALSE;
        break;
#endif /* KXLD_USER_OR_X86_64 */
#if KXLD_USER_OR_ARM
    case CPU_TYPE_ARM:
        relocator->reloc_has_pair = arm_reloc_has_pair;
        relocator->reloc_get_pair_type = arm_reloc_get_pair_type;
        relocator->reloc_has_got = arm_reloc_has_got;
        relocator->process_reloc = arm_process_reloc;
        relocator->function_align = 1;
        relocator->is_32_bit = TRUE;
        relocator->may_scatter = FALSE;
        break;
#endif /* KXLD_USER_OR_ARM */
#if KXLD_USER_OR_ARM64
    case CPU_TYPE_ARM64:
        relocator->reloc_has_pair = arm64_reloc_has_pair;
        relocator->reloc_get_pair_type = arm64_reloc_get_pair_type;
        relocator->reloc_has_got = arm64_reloc_has_got;
        relocator->process_reloc = arm64_process_reloc;
        relocator->function_align = 0;
        relocator->is_32_bit = FALSE;
        relocator->may_scatter = FALSE;
        break;
#endif /* KXLD_USER_OR_ARM64 */

    default:
        rval = KERN_FAILURE;
        kxld_log(kKxldLogLinking, kKxldLogErr,
            kKxldLogArchNotSupported, cputype);
        goto finish;
    }

    relocator->file = file;
    relocator->symtab = symtab;
    relocator->sectarray = sectarray;
    relocator->is_32_bit = kxld_is_32_bit(cputype);
    relocator->swap = swap;

    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
kern_return_t
kxld_reloc_create_macho(KXLDArray *relocarray, const KXLDRelocator *relocator, 
    const struct relocation_info *srcs, u_int nsrcs)
{
    kern_return_t rval = KERN_FAILURE;
    KXLDReloc *reloc = NULL;
    u_int nrelocs = 0;
    const struct relocation_info *src = NULL;
    const struct scattered_relocation_info *scatsrc = NULL;
    u_int i = 0;
    u_int reloc_index = 0;

    check(relocarray);
    check(srcs);

    /* If there are no relocation entries, just return */
    if (!nsrcs) {
        rval = KERN_SUCCESS;
        goto finish;
    }

    /* Count the number of non-pair relocs */
    nrelocs = count_relocatable_relocs(relocator, srcs, nsrcs);

    if (nrelocs) {

        /* Allocate the array of relocation entries */

        rval = kxld_array_init(relocarray, sizeof(KXLDReloc), nrelocs);
        require_noerr(rval, finish);

        /* Initialize the relocation entries */
        
        for (i = 0; i < nsrcs; ++i) {
            src = srcs + i;
            scatsrc = (const struct scattered_relocation_info *) src;

            /* A section-based relocation entry can be skipped for absolute 
             * symbols.
             */

            if (!(relocator->may_scatter && (src->r_address & R_SCATTERED)) &&
                !(src->r_extern) && (R_ABS == src->r_symbolnum))
            {
                continue;
            }
            
            /* Pull out the data from the relocation entries.  The target_type
             * depends on the r_extern bit:
             *  Scattered -> Section Lookup by Address
             *  Local (not extern) -> Section by Index
             *  Extern -> Symbolnum by Index
             */
            reloc = kxld_array_get_item(relocarray, reloc_index++);
            if (relocator->may_scatter && (src->r_address & R_SCATTERED)) {
                reloc->address = scatsrc->r_address;
                reloc->pcrel = scatsrc->r_pcrel;
                reloc->length = scatsrc->r_length;
                reloc->reloc_type = scatsrc->r_type;
                reloc->target = scatsrc->r_value;
                reloc->target_type = KXLD_TARGET_LOOKUP;
            } else {
                reloc->address = src->r_address;
                reloc->pcrel = src->r_pcrel;
                reloc->length = src->r_length;
                reloc->reloc_type = src->r_type;
                reloc->target = src->r_symbolnum;

                if (0 == src->r_extern) {
                    reloc->target_type = KXLD_TARGET_SECTNUM;
                    reloc->target -= 1;
                } else {
                    reloc->target_type = KXLD_TARGET_SYMBOLNUM;
                }
            }
            
            /* Find the pair entry if it exists */

            if (relocator->reloc_has_pair(reloc->reloc_type)) {
                ++i;
                require_action(i < nsrcs, finish, rval=KERN_FAILURE);

                src = srcs + i;
                scatsrc = (const struct scattered_relocation_info *) src;
                 
                if (relocator->may_scatter && (src->r_address & R_SCATTERED)) {
                    require_action(relocator->reloc_get_pair_type(
                        reloc->reloc_type) == scatsrc->r_type,
                        finish, rval=KERN_FAILURE);
                    reloc->pair_address= scatsrc->r_address;
                    reloc->pair_target = scatsrc->r_value;
                    reloc->pair_target_type = KXLD_TARGET_LOOKUP;
                } else {
                    require_action(relocator->reloc_get_pair_type(
                        reloc->reloc_type) == scatsrc->r_type,
                        finish, rval=KERN_FAILURE);
                    reloc->pair_address = scatsrc->r_address;
                    if (src->r_extern) {
                        reloc->pair_target = src->r_symbolnum;
                        reloc->pair_target_type = KXLD_TARGET_SYMBOLNUM;
                    } else {
                        reloc->pair_target = src->r_address;
                        reloc->pair_target_type = KXLD_TARGET_VALUE;
                    }
                }
            } else {
                reloc->pair_target = 0;
                if (relocator->reloc_has_got(reloc->reloc_type)) {
                   reloc->pair_target_type = KXLD_TARGET_GOT;
                } else {
                   reloc->pair_target_type = KXLD_TARGET_NONE;
                }
            }
       } // for...
    }
    rval = KERN_SUCCESS;

finish:
    return rval;
}


/*******************************************************************************
* Relocatable relocs :
*   1) Are not _PAIR_ relocs
*   2) Don't reference N_ABS symbols
*******************************************************************************/
static u_int
count_relocatable_relocs(const KXLDRelocator *relocator,
    const struct relocation_info *relocs, u_int nrelocs)
{
    u_int num_nonpair_relocs = 0;
    u_int i = 0;
    const struct relocation_info *reloc = NULL;
    const struct scattered_relocation_info *sreloc = NULL;

    check(relocator);
    check(relocs);

    /* Loop over all of the relocation entries */

    num_nonpair_relocs = 1;
    for (i = 1; i < nrelocs; ++i) {
        reloc = relocs + i;

        if (reloc->r_address & R_SCATTERED) {
            /* A scattered relocation entry is relocatable as long as it's not a
             * pair.
             */
            sreloc = (const struct scattered_relocation_info *) reloc;

            num_nonpair_relocs += 
                !relocator->reloc_has_pair(sreloc->r_type);
        } else {
            /* A normal relocation entry is relocatable if it is not a pair and
             * if it is not a section-based relocation for an absolute symbol.
             */
            num_nonpair_relocs += 
                !(relocator->reloc_has_pair(reloc->r_type)
                 || (0 == reloc->r_extern && R_ABS == reloc->r_symbolnum));
        }

    }
    
    return num_nonpair_relocs;
}

/*******************************************************************************
*******************************************************************************/
void
kxld_relocator_clear(KXLDRelocator *relocator)
{
    bzero(relocator, sizeof(*relocator));
}

/*******************************************************************************
*******************************************************************************/
boolean_t 
kxld_relocator_has_pair(const KXLDRelocator *relocator, u_int r_type)
{
    check(relocator);

    return relocator->reloc_has_pair(r_type);
}

/*******************************************************************************
*******************************************************************************/
u_int 
kxld_relocator_get_pair_type(const KXLDRelocator *relocator,
    u_int prev_r_type)
{
    check(relocator);

    return relocator->reloc_get_pair_type(prev_r_type);
}

/*******************************************************************************
*******************************************************************************/
boolean_t 
kxld_relocator_has_got(const KXLDRelocator *relocator, u_int r_type)
{
    check(relocator);

    return relocator->reloc_has_got(r_type);
}

/*******************************************************************************
*******************************************************************************/
KXLDSym *
kxld_reloc_get_symbol(const KXLDRelocator *relocator, const KXLDReloc *reloc,
    const u_char *data)
{
    KXLDSym *sym = NULL;
    kxld_addr_t value = 0;

    check(reloc);

    switch (reloc->target_type) {
    case KXLD_TARGET_SYMBOLNUM:
        sym = kxld_symtab_get_symbol_by_index(relocator->symtab, reloc->target);
        break;
    case KXLD_TARGET_SECTNUM:
       if (data) {
            value = kxld_relocator_get_pointer_at_addr(relocator, data,
                                                       reloc->address);
            sym = kxld_symtab_get_cxx_symbol_by_value(relocator->symtab, value);
       }
        break;
    default:
        sym = NULL;
        break;
    }

    return sym;
}

/*******************************************************************************
*******************************************************************************/
kern_return_t
kxld_reloc_get_reloc_index_by_offset(const KXLDArray *relocs, 
    kxld_size_t offset, u_int *idx)
{
    kern_return_t rval = KERN_FAILURE;
    KXLDReloc *reloc = NULL;
    u_int i = 0;

    for (i = 0; i < relocs->nitems; ++i) {
        reloc = kxld_array_get_item(relocs, i);
        if (reloc->address == offset) break;
    }
    
    if (i >= relocs->nitems) {
        rval = KERN_FAILURE;
        goto finish;
    }

    *idx = i;
    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
KXLDReloc *
kxld_reloc_get_reloc_by_offset(const KXLDArray *relocs, kxld_addr_t offset)
{
    kern_return_t rval = KERN_FAILURE;
    KXLDReloc *reloc = NULL;
    u_int i = 0;

    rval = kxld_reloc_get_reloc_index_by_offset(relocs, offset, &i);
    if (rval) goto finish;

    reloc = kxld_array_get_item(relocs, i);
    
finish:
    return reloc;
}

#if KXLD_PIC_KEXTS
/*******************************************************************************
*******************************************************************************/
u_long
kxld_reloc_get_macho_header_size()
{
    return sizeof(struct dysymtab_command);
}

/*******************************************************************************
*******************************************************************************/
u_long
kxld_reloc_get_macho_data_size(
    const KXLDArray *locrelocs,
    const KXLDArray *extrelocs)
{
    u_long    rval = 0;

    rval += get_macho_data_size_for_array(locrelocs);
    rval += get_macho_data_size_for_array(extrelocs);

    return (rval);
}

/*******************************************************************************
*******************************************************************************/
kern_return_t
kxld_reloc_export_macho(const KXLDRelocator *relocator,
    const KXLDArray *locrelocs, const KXLDArray *extrelocs,
    u_char *buf, u_long *header_offset, u_long header_size,
    u_long *data_offset, u_long size)
{
    kern_return_t rval = KERN_FAILURE;
    struct dysymtab_command *dysymtabhdr = NULL;
    struct relocation_info *start = NULL;
    struct relocation_info *dst = NULL;
    u_long count = 0;
    u_long data_size = 0;

    check(locrelocs);
    check(extrelocs);
    check(buf);
    check(header_offset);
    check(data_offset);

    require_action(sizeof(*dysymtabhdr) <= header_size - *header_offset, finish, rval=KERN_FAILURE);
    dysymtabhdr = (struct dysymtab_command *) ((void *) (buf + *header_offset));
    *header_offset += sizeof(*dysymtabhdr);

    data_size = kxld_reloc_get_macho_data_size(locrelocs, extrelocs);
    require_action((*data_offset + data_size) <= size, finish, rval=KERN_FAILURE);

    start = dst = (struct relocation_info *) ((void *) (buf + *data_offset));

    if (kaslr_offsets == NULL) {
        kaslr_offsets_index = 0;
        kaslr_offsets_count = locrelocs->nitems + extrelocs->nitems;
        kaslr_offsets = (uint32_t *)malloc(kaslr_offsets_count * sizeof(*kaslr_offsets));
        bzero(kaslr_offsets, kaslr_offsets_count * sizeof(*kaslr_offsets));
    }

    // copies the reloc data into the __LINKEDIT segment
    // data_offset is the new value for locreloff
    rval = export_macho_for_array(relocator, locrelocs, &dst);
    require_noerr(rval, finish);
    
    rval = export_macho_for_array(relocator, extrelocs, &dst);
    require_noerr(rval, finish);

    count = dst - start;
    
    memset(dysymtabhdr, 0, sizeof(*dysymtabhdr));
    dysymtabhdr->cmd = LC_DYSYMTAB;
    dysymtabhdr->cmdsize = (uint32_t) sizeof(*dysymtabhdr);
    dysymtabhdr->locreloff = (uint32_t) *data_offset;
    dysymtabhdr->nlocrel = (uint32_t) count;
    
    *data_offset += count * sizeof(struct relocation_info);
    
#if SPLIT_KEXTS_DEBUG
    kxld_log(kKxldLogLinking, kKxldLogErr,
             "%p >>> Start of dysymtabhdr (size %lu) <%s> ",
             (void *) dysymtabhdr,
             sizeof(*dysymtabhdr),
             __func__);
    kxld_log(kKxldLogLinking, kKxldLogErr,
             "%p <<< End of dysymtabhdr <%s> ",
             (void *) ((u_char *)dysymtabhdr + sizeof(*dysymtabhdr)),
             __func__);

    kxld_log(kKxldLogLinking, kKxldLogErr,
             "dysymtabhdr at %p: cmdsize %u indirectsymoff %u nindirectsyms %u extreloff %u nextrel %u locreloff %u nlocrel %u <%s>",
             (void *) dysymtabhdr,
             dysymtabhdr->cmdsize,
             dysymtabhdr->indirectsymoff,
             dysymtabhdr->nindirectsyms,
             dysymtabhdr->extreloff,
             dysymtabhdr->nextrel,
             dysymtabhdr->locreloff,
             dysymtabhdr->nlocrel,
             __func__);
#endif
    
    rval = KERN_SUCCESS;
finish:
   return rval;
}
#endif /* KXLD_PIC_KEXTS */

/*******************************************************************************
*******************************************************************************/
kxld_addr_t
kxld_relocator_get_pointer_at_addr(const KXLDRelocator *relocator,
    const u_char *data, u_long offset)
{
    kxld_addr_t value;

    KXLD_3264_FUNC(relocator->is_32_bit, value,
        get_pointer_at_addr_32, get_pointer_at_addr_64,
        relocator, data, offset);

    return value;
}

#if KXLD_USER_OR_ILP32
/*******************************************************************************
*******************************************************************************/
static kxld_addr_t
get_pointer_at_addr_32(const KXLDRelocator *relocator, 
    const u_char *data, u_long offset)
{
    uint32_t addr = 0;
    
    check(relocator);

    addr = *(const uint32_t *) ((const void *) (data + offset));
#if !KERNEL
    if (relocator->swap) {
        addr = OSSwapInt32(addr);
    }
#endif

    return align_raw_function_address(relocator, addr);
}
#endif /* KXLD_USER_OR_ILP32 */

#if KXLD_USER_OR_LP64
/*******************************************************************************
*******************************************************************************/
static kxld_addr_t
get_pointer_at_addr_64(const KXLDRelocator *relocator, 
    const u_char *data, u_long offset)
{
    uint64_t addr = 0;
    
    check(relocator);

    addr = *(const uint64_t *) ((const void *) (data + offset));
    
#if !KERNEL
    if (relocator->swap) {
        addr = OSSwapInt64(addr);
    }
#endif

    return align_raw_function_address(relocator, addr);
}
#endif /* KXLD_USER_OR_LP64 */

/*******************************************************************************
*******************************************************************************/
void 
kxld_relocator_set_vtables(KXLDRelocator *relocator, const KXLDDict *vtables)
{
    relocator->vtables = vtables;
}

/*******************************************************************************
* When we're inspecting the raw binary and not the symbol table, value may
* hold a THUMB address (with bit 0 set to 1) but the index will have the real
* address (bit 0 set to 0). So if bit 0 is set here, we clear it. This only
* impacts ARM for now, but it's implemented as a generic function alignment
* mask.
*******************************************************************************/
static kxld_addr_t
align_raw_function_address(const KXLDRelocator *relocator, kxld_addr_t value)
{
    if (relocator->function_align) { 
        value &= ~((1ULL << relocator->function_align) - 1); 
    }

    return value; 
}

/*******************************************************************************
*******************************************************************************/
kern_return_t 
kxld_relocator_process_sect_reloc(KXLDRelocator *relocator,
    const KXLDReloc *reloc, const KXLDSect *sect)
{
    kern_return_t rval = KERN_FAILURE;
    u_char *instruction = NULL;
    kxld_addr_t target = 0;
    kxld_addr_t pair_target = 0;
    kxld_addr_t base_pc = 0;
    kxld_addr_t link_pc = 0;
    kxld_addr_t link_disp = 0;

    check(relocator);
    check(reloc);
    check(sect);

    /* Find the instruction */

    instruction = sect->data + reloc->address;

    /* Calculate the target */

    rval = calculate_targets(relocator, &target, &pair_target, reloc);
    require_noerr(rval, finish);

    base_pc = reloc->address;
    link_pc = base_pc + sect->link_addr;
    link_disp = sect->link_addr - sect->base_addr;

    /* Relocate */

    rval = relocator->process_reloc(relocator, instruction, reloc->length, 
        reloc->pcrel, base_pc, link_pc, link_disp, reloc->reloc_type, target, 
        pair_target, relocator->swap);
    require_noerr(rval, finish);
    
    /* Return */

    relocator->current_vtable = NULL;
    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
kern_return_t 
kxld_reloc_update_symindex(KXLDReloc *reloc, u_int symindex)
{
    kern_return_t rval = KERN_FAILURE;

    require_action(reloc->target_type == KXLD_TARGET_SYMBOLNUM, 
        finish, rval = KERN_FAILURE);

    reloc->target = symindex;

    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
kern_return_t 
kxld_relocator_process_table_reloc(KXLDRelocator *relocator,
                                   const KXLDReloc *reloc,
                                   const KXLDSeg *seg,
                                    kxld_addr_t link_addr)
{
    kern_return_t rval = KERN_FAILURE;
    u_char *instruction = NULL;
    kxld_addr_t target = 0;
    kxld_addr_t pair_target = 0;
    kxld_addr_t base_pc = 0;
    kxld_addr_t link_pc = 0;
    u_long offset = 0;

    check(relocator);
    check(reloc);

    /* Find the instruction in original kext file we are trying to link */

    offset = (u_long)(seg->fileoff + (reloc->address - seg->base_addr));
    instruction = relocator->file + offset;

    /* Calculate the target */

    rval = calculate_targets(relocator, &target, &pair_target, reloc);
    require_noerr(rval, finish);

    base_pc = reloc->address;
    link_pc = base_pc + link_addr;
    if (kxld_seg_is_split_seg(seg)) {
        // link_pc for split segment special case, do not add in the base_pc
        link_pc = link_addr;
    }

    /* Relocate */

    rval = relocator->process_reloc(relocator, instruction, reloc->length,
        reloc->pcrel, base_pc, link_pc, link_addr, reloc->reloc_type, target,
        pair_target, relocator->swap);
    require_noerr(rval, finish);
    
    /* Return */

    relocator->current_vtable = NULL;
    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t
calculate_targets(KXLDRelocator *relocator, kxld_addr_t *_target, 
    kxld_addr_t *_pair_target, const KXLDReloc *reloc)
{
    kern_return_t rval = KERN_FAILURE;
    const KXLDSect *sect = NULL;
    const KXLDSym *sym = NULL;
    kxld_addr_t target = 0;
    kxld_addr_t pair_target = 0;
    char *demangled_name = NULL;
    size_t demangled_length = 0;

    check(_target);
    check(_pair_target);
    *_target = 0;
    *_pair_target = 0;

    /* Find the target based on the lookup type */

    switch(reloc->target_type) {
    case KXLD_TARGET_LOOKUP:
        require_action(reloc->pair_target_type == KXLD_TARGET_NONE ||
            reloc->pair_target_type == KXLD_TARGET_LOOKUP ||
            reloc->pair_target_type == KXLD_TARGET_VALUE,
            finish, rval=KERN_FAILURE);

        rval = get_target_by_address_lookup(&target, reloc->target, 
            relocator->sectarray);
        require_noerr(rval, finish);

        if (reloc->pair_target_type == KXLD_TARGET_LOOKUP) {
            rval = get_target_by_address_lookup(&pair_target,
                reloc->pair_target, relocator->sectarray);
            require_noerr(rval, finish);
        } else if (reloc->pair_target_type == KXLD_TARGET_VALUE) {
            pair_target = reloc->pair_target;
        }
        break;
    case KXLD_TARGET_SECTNUM:
        require_action(reloc->pair_target_type == KXLD_TARGET_NONE ||
            reloc->pair_target_type == KXLD_TARGET_VALUE, 
            finish, rval=KERN_FAILURE);

        /* Get the target's section by section number */
        sect = kxld_array_get_item(relocator->sectarray, reloc->target);
        require_action(sect, finish, rval=KERN_FAILURE);

        /* target is the change in the section's address */
        target = sect->link_addr - sect->base_addr;

        if (reloc->pair_target_type) {
            pair_target = reloc->pair_target;
        } else {
            /* x86_64 needs to know when we have a non-external relocation,
             * so we hack that information in here.
             */
            pair_target = TRUE;
        }
        break;
    case KXLD_TARGET_SYMBOLNUM:
        require_action(reloc->pair_target_type == KXLD_TARGET_NONE ||
            reloc->pair_target_type == KXLD_TARGET_GOT ||
            reloc->pair_target_type == KXLD_TARGET_SYMBOLNUM ||
            reloc->pair_target_type == KXLD_TARGET_VALUE, finish,
            rval=KERN_FAILURE);

        /* Get the target's symbol by symbol number */
        sym = kxld_symtab_get_symbol_by_index(relocator->symtab, reloc->target);
        require_action(sym, finish, rval=KERN_FAILURE);

        /* If this symbol is a padslot that has already been replaced, then the
         * only way a relocation entry can still reference it is if there is a
         * vtable that has not been patched.  The vtable patcher uses the
         * MetaClass structure to find classes for patching, so an unpatched
         * vtable means that there is an OSObject-dervied class that is missing
         * its OSDeclare/OSDefine macros.
         */
        require_action(!kxld_sym_is_padslot(sym) || !kxld_sym_is_replaced(sym), 
            finish, rval=KERN_FAILURE;
            kxld_log(kKxldLogLinking, kKxldLogErr, kKxldLogRelocatingPatchedSym,
                kxld_demangle(sym->name, &demangled_name, &demangled_length)));

        target = sym->link_addr;

        if (kxld_sym_is_vtable(sym)) {
            relocator->current_vtable = kxld_dict_find(relocator->vtables, sym->name);
        }

        /* Some relocation types need the GOT entry address instead of the
         * symbol's actual address.  These types don't have pair relocation
         * entries, so we store the GOT entry address as the pair target.
         */
        if (reloc->pair_target_type == KXLD_TARGET_VALUE) {
            pair_target = reloc->pair_target;
        } else if (reloc->pair_target_type == KXLD_TARGET_SYMBOLNUM ) {
            sym = kxld_symtab_get_symbol_by_index(relocator->symtab, 
                reloc->pair_target);
            require_action(sym, finish, rval=KERN_FAILURE);
            pair_target = sym->link_addr;
        } else if (reloc->pair_target_type == KXLD_TARGET_GOT) {
            pair_target = sym->got_addr;
        }
        break;
    default:
        rval = KERN_FAILURE;
        goto finish;
    }

    *_target = target;
    *_pair_target = pair_target;
    rval = KERN_SUCCESS;

finish:
    if (demangled_name) kxld_free(demangled_name, demangled_length);
    return rval;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t
get_target_by_address_lookup(kxld_addr_t *target, kxld_addr_t addr,
    const KXLDArray *sectarray)
{
    kern_return_t rval = KERN_FAILURE;
    const KXLDSect *sect = NULL;
    kxld_addr_t start = 0;
    kxld_addr_t end = 0;
    u_int i = 0;

    check(target);
    check(sectarray);
    *target = 0;

    for (i = 0; i < sectarray->nitems; ++i) {
        sect = kxld_array_get_item(sectarray, i);
        start = sect->base_addr;
        end = start + sect->size;

        if (start <= addr && addr < end) break;
        
        sect = NULL;
    }
    require_action(sect, finish, rval=KERN_FAILURE);

    *target = sect->link_addr - sect->base_addr;
    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t
check_for_direct_pure_virtual_call(const KXLDRelocator *relocator, u_long offset)
{
    kern_return_t rval = KERN_FAILURE;
    const KXLDVTableEntry *entry = NULL;

    if (relocator->current_vtable) {
        entry = kxld_vtable_get_entry_for_offset(relocator->current_vtable, 
            offset, relocator->is_32_bit);
        require_action(!entry || !entry->patched.name ||
            !kxld_sym_name_is_pure_virtual(entry->patched.name),
            finish, rval=KERN_FAILURE;
            kxld_log(kKxldLogLinking, kKxldLogErr, 
                kKxldLogDirectPureVirtualCall));
    }

    rval = KERN_SUCCESS;
finish:
    return rval;
}

#if KXLD_PIC_KEXTS
/*******************************************************************************
*******************************************************************************/
static u_long
get_macho_data_size_for_array(const KXLDArray *relocs)
{
    const KXLDReloc *reloc = NULL;
    u_int i = 0;
    u_long size = 0;

    check(relocs);

    for (i = 0; i < relocs->nitems; ++i) {
        reloc = kxld_array_get_item(relocs, i);
        if (!reloc->pcrel) {
            size += sizeof(struct relocation_info);
            if(reloc->pair_target_type != KXLD_TARGET_NONE) {
                size += sizeof(struct relocation_info);
            }
        }
    }

    return size;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t
export_macho_for_array(const KXLDRelocator *relocator,
    const KXLDArray *relocs, struct relocation_info **dstp)
{
    kern_return_t rval = KERN_FAILURE;
    const KXLDReloc *reloc = NULL;
    struct relocation_info *dst = NULL;
    struct scattered_relocation_info *scatdst = NULL;
    u_int i = 0;
    
    dst = *dstp;

    for (i = 0; i < relocs->nitems; ++i) {
        reloc = kxld_array_get_item(relocs, i);
        scatdst = (struct scattered_relocation_info *) dst;

        if (reloc->pcrel) {
            continue;
        }

        switch (reloc->target_type) {
        case KXLD_TARGET_LOOKUP:
            if (kaslr_offsets) {
                if (kaslr_offsets_index >= kaslr_offsets_count) {
                    kxld_log(kKxldLogLinking, kKxldLogErr,
                             "kaslr_offsets overflow %d > %d <%s> ",
                             kaslr_offsets_index, kaslr_offsets_count,
                             __func__);
                    abort();
                }
                // reloc->address is really an offset from the start of the kext
                *(kaslr_offsets + kaslr_offsets_index++) = reloc->address;
            }
            scatdst->r_address = reloc->address;
            scatdst->r_pcrel = reloc->pcrel;
            scatdst->r_length = reloc->length;
            scatdst->r_type = reloc->reloc_type;
            scatdst->r_value = reloc->target;
            scatdst->r_scattered = 1;
            break;
        case KXLD_TARGET_SECTNUM:
            if (kaslr_offsets) {
                if (kaslr_offsets_index >= kaslr_offsets_count) {
                    kxld_log(kKxldLogLinking, kKxldLogErr,
                             "kaslr_offsets overflow <%s> ", __func__);
                    abort();
                }
                // reloc->address is really an offset from the start of the kext
                *(kaslr_offsets + kaslr_offsets_index++) = reloc->address;
            }
            dst->r_address = reloc->address;
            dst->r_pcrel = reloc->pcrel;
            dst->r_length = reloc->length;
            dst->r_type = reloc->reloc_type;
            dst->r_symbolnum = reloc->target + 1;
            dst->r_extern = 0;
            break;
        case KXLD_TARGET_SYMBOLNUM:
           /* Assume that everything will be slid together; otherwise,
            * there is no sensible value for the section number.
            */
            if (kaslr_offsets) {
                if (kaslr_offsets_index >= kaslr_offsets_count) {
                    kxld_log(kKxldLogLinking, kKxldLogErr,
                             "kaslr_offsets overflow <%s> ", __func__);
                    abort();
                }
                // reloc->address is really an offset from the start of the kext
                *(kaslr_offsets + kaslr_offsets_index++) = reloc->address;
            }
            dst->r_address = reloc->address;
            dst->r_pcrel = reloc->pcrel;
            dst->r_length = reloc->length;
            dst->r_type = reloc->reloc_type;
            dst->r_symbolnum = 1;
            dst->r_extern = 0;
            break;
        default:
            rval = KERN_FAILURE;
            goto finish;
        }

        ++dst;

        if(reloc->pair_target_type != KXLD_TARGET_NONE) {
            ++i;
            require_action(i < relocs->nitems, finish, rval=KERN_FAILURE);
            scatdst = (struct scattered_relocation_info *) dst;
            switch (reloc->pair_target_type) {
            case KXLD_TARGET_LOOKUP:
                scatdst->r_address = reloc->pair_address;
                scatdst->r_pcrel = reloc->pcrel;
                scatdst->r_length = reloc->length;
                scatdst->r_type = relocator->reloc_get_pair_type(reloc->reloc_type);
                scatdst->r_value = reloc->pair_target;
                scatdst->r_scattered = 1;
                break;
            case KXLD_TARGET_SECTNUM:
                dst->r_address = reloc->pair_address;
                dst->r_pcrel = reloc->pcrel;
                dst->r_length = reloc->length;
                dst->r_type = relocator->reloc_get_pair_type(reloc->reloc_type);
                dst->r_symbolnum = reloc->pair_target + 1;
                dst->r_extern = 0;
                break;
            case KXLD_TARGET_SYMBOLNUM:
                dst->r_address = reloc->pair_address;
                dst->r_pcrel = reloc->pcrel;
                dst->r_length = reloc->length;
                dst->r_type = relocator->reloc_get_pair_type(reloc->reloc_type);
                dst->r_symbolnum = 1;
                dst->r_extern = 0;
                break;
            default:
                rval = KERN_FAILURE;
                goto finish;
            }
            ++dst;
        }
    }

    rval = KERN_SUCCESS;
finish:
    *dstp = dst;
    return rval;
}
#endif /* KXLD_PIC_KEXTS */

#if KXLD_USER_OR_I386 
/*******************************************************************************
*******************************************************************************/
static boolean_t
generic_reloc_has_pair(u_int _type)
{
    enum reloc_type_generic type = _type;

    return (type == GENERIC_RELOC_SECTDIFF || 
        type == GENERIC_RELOC_LOCAL_SECTDIFF);
}

/*******************************************************************************
*******************************************************************************/
static u_int 
generic_reloc_get_pair_type(u_int _prev_type __unused)
{
    return GENERIC_RELOC_PAIR;
}

/*******************************************************************************
*******************************************************************************/
static boolean_t generic_reloc_has_got(u_int _type __unused)
{
    return FALSE;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t 
generic_process_reloc(const KXLDRelocator *relocator, u_char *instruction, 
    u_int length, u_int pcrel, kxld_addr_t _base_pc, kxld_addr_t _link_pc, 
    kxld_addr_t _link_disp __unused, u_int _type, kxld_addr_t _target, 
    kxld_addr_t _pair_target, boolean_t swap __unused)
{
    kern_return_t rval = KERN_FAILURE;
    uint32_t base_pc = (uint32_t) _base_pc;
    uint32_t link_pc = (uint32_t) _link_pc;
    uint32_t *instr_addr = NULL;
    uint32_t instr_data = 0;
    uint32_t target = (uint32_t) _target;
    uint32_t pair_target = (uint32_t) _pair_target;
    enum reloc_type_generic type = _type;

    check(instruction);
    require_action(length == 2, finish, rval=KERN_FAILURE);

    if (pcrel) target = target + base_pc - link_pc;

    instr_addr = (uint32_t *) ((void *) instruction);
    instr_data = *instr_addr;

#if !KERNEL
    if (swap) instr_data = OSSwapInt32(instr_data);
#endif

    rval = check_for_direct_pure_virtual_call(relocator, instr_data);
    require_noerr(rval, finish);

    switch (type) {
    case GENERIC_RELOC_VANILLA:
        instr_data += target;
        break;
    case GENERIC_RELOC_SECTDIFF:
    case GENERIC_RELOC_LOCAL_SECTDIFF:
        instr_data = instr_data + target - pair_target;
        break;
    case GENERIC_RELOC_PB_LA_PTR:
        rval = KERN_FAILURE;
        goto finish;
    case GENERIC_RELOC_PAIR:
    default:
        rval = KERN_FAILURE;
        goto finish;
    }

#if !KERNEL
    if (swap) instr_data = OSSwapInt32(instr_data);
#endif

    *instr_addr = instr_data;

    rval = KERN_SUCCESS;

finish:
    return rval;
}
#endif /* KXLD_USER_OR_I386 */

#if KXLD_USER_OR_X86_64
/*******************************************************************************
*******************************************************************************/
static boolean_t 
x86_64_reloc_has_pair(u_int _type)
{
    enum reloc_type_x86_64 type = _type;

    return (type == X86_64_RELOC_SUBTRACTOR);
}

/*******************************************************************************
*******************************************************************************/
static u_int 
x86_64_reloc_get_pair_type(u_int _prev_type __unused)
{
    return X86_64_RELOC_UNSIGNED;
}

/*******************************************************************************
*******************************************************************************/
static boolean_t 
x86_64_reloc_has_got(u_int _type)
{
    enum reloc_type_x86_64 type = _type;

    return (type == X86_64_RELOC_GOT_LOAD || type == X86_64_RELOC_GOT);
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t 
x86_64_process_reloc(const KXLDRelocator *relocator __unused, u_char *instruction, 
    u_int length, u_int pcrel, kxld_addr_t _base_pc __unused, 
    kxld_addr_t _link_pc, kxld_addr_t _link_disp, u_int _type, 
    kxld_addr_t _target, kxld_addr_t _pair_target, boolean_t swap __unused)
{
    kern_return_t rval = KERN_FAILURE;
    enum reloc_type_x86_64 type = _type;
    int32_t *instr32p = NULL;
    int32_t instr32 = 0;
    uint64_t *instr64p = NULL;
    uint64_t instr64 = 0;
    uint64_t target = _target;
    uint64_t pair_target = _pair_target;
    uint64_t link_pc = (uint64_t) _link_pc;
    uint64_t link_disp = (uint64_t) _link_disp;
    uint64_t adjustment = 0;

    check(instruction);
    require_action(length == 2 || length == 3, 
        finish, rval=KERN_FAILURE);

    if (length == 2) {
        instr32p = (int32_t *) ((void *) instruction);
        instr32 = *instr32p;

#if !KERNEL
        if (swap) instr32 = OSSwapInt32(instr32);
#endif

        rval = check_for_direct_pure_virtual_call(relocator, instr32);
        require_noerr(rval, finish);

        /* There are a number of different small adjustments for pc-relative
         * relocation entries.  The general case is to subtract the size of the
         * relocation (represented by the length parameter), and it applies to
         * the GOT types and external SIGNED types.  The non-external signed types
         * have a different adjustment corresponding to the specific type.
         */
        switch (type) {
        case X86_64_RELOC_SIGNED:
            if (pair_target) {
                adjustment = 0;    
                break;
            }
            /* Fall through */
        case X86_64_RELOC_SIGNED_1:
            if (pair_target) {
                adjustment = 1;
                break;
            }
            /* Fall through */
        case X86_64_RELOC_SIGNED_2:
            if (pair_target) {
                adjustment = 2;
                break;
            }
            /* Fall through */
        case X86_64_RELOC_SIGNED_4:
            if (pair_target) {
                adjustment = 4;
                break;
            }
            /* Fall through */
        case X86_64_RELOC_BRANCH:
        case X86_64_RELOC_GOT:
        case X86_64_RELOC_GOT_LOAD:
            adjustment = (1 << length);
            break;
        default:
            break;
        }

        /* Perform the actual relocation.  All of the 32-bit relocations are 
         * pc-relative except for SUBTRACTOR, so a good chunk of the logic is
         * stuck in calculate_displacement_x86_64.  The signed relocations are
         * a special case, because when they are non-external, the instruction
         * already contains the pre-relocation displacement, so we only need to
         * find the difference between how far the PC was relocated, and how
         * far the target is relocated.  Since the target variable already
         * contains the difference between the target's base and link
         * addresses, we add the difference between the PC's base and link
         * addresses to the adjustment variable.  This will yield the
         * appropriate displacement in calculate_displacement.
         */
        switch (type) {
        case X86_64_RELOC_BRANCH:
            require_action(pcrel, finish, rval=KERN_FAILURE);
            adjustment += link_pc;
            break;
        case X86_64_RELOC_SIGNED:
        case X86_64_RELOC_SIGNED_1:
        case X86_64_RELOC_SIGNED_2:
        case X86_64_RELOC_SIGNED_4:
            require_action(pcrel, finish, rval=KERN_FAILURE);
            adjustment += (pair_target) ? (link_disp) : (link_pc);
            break;
        case X86_64_RELOC_GOT:
        case X86_64_RELOC_GOT_LOAD:
            require_action(pcrel, finish, rval=KERN_FAILURE);
            adjustment += link_pc;
            target = pair_target;
            break;
        case X86_64_RELOC_SUBTRACTOR:
            require_action(!pcrel, finish, rval=KERN_FAILURE);
            instr32 = (int32_t) (target - pair_target);
            break;
        case X86_64_RELOC_UNSIGNED:
        default:
            rval = KERN_FAILURE;
            goto finish;
        }

        /* Call calculate_displacement for the pc-relative relocations */
        if (pcrel) {
            rval = calculate_displacement_x86_64(target, adjustment, &instr32); 
            require_noerr(rval, finish);
        }

#if !KERNEL
        if (swap) instr32 = OSSwapInt32(instr32);
#endif
        
        *instr32p = instr32;
    } else {
        instr64p = (uint64_t *) ((void *) instruction);
        instr64 = *instr64p;

#if !KERNEL
        if (swap) instr64 = OSSwapInt64(instr64);
#endif

        rval = check_for_direct_pure_virtual_call(relocator, (u_long) instr64);
        require_noerr(rval, finish);

        switch (type) {
        case X86_64_RELOC_UNSIGNED:
            require_action(!pcrel, finish, rval=KERN_FAILURE);
            
            instr64 += target;
            break;
        case X86_64_RELOC_SUBTRACTOR:
            require_action(!pcrel, finish, rval=KERN_FAILURE);

            instr64 = target - pair_target;
            break;
        case X86_64_RELOC_SIGNED_1:
        case X86_64_RELOC_SIGNED_2:
        case X86_64_RELOC_SIGNED_4:
        case X86_64_RELOC_GOT_LOAD:
        case X86_64_RELOC_BRANCH:
        case X86_64_RELOC_SIGNED:
        case X86_64_RELOC_GOT:
        default:
            rval = KERN_FAILURE;
            goto finish;
        }

#if !KERNEL
        if (swap) instr64 = OSSwapInt64(instr64);
#endif
        *instr64p = instr64;
    }

    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t
calculate_displacement_x86_64(uint64_t target, uint64_t adjustment, 
    int32_t *instr32)
{
    kern_return_t rval = KERN_FAILURE;
    int64_t displacement;
    uint64_t difference;

    displacement = *instr32 + target - adjustment;
    difference = ABSOLUTE_VALUE(displacement);
    require_action(difference < X86_64_RIP_RELATIVE_LIMIT, finish, 
        rval=KERN_FAILURE;
        kxld_log(kKxldLogLinking, kKxldLogErr, kKxldLogRelocationOverflow));

    *instr32 = (int32_t) displacement;
    rval = KERN_SUCCESS;

finish:
    return rval;
}
#endif /* KXLD_USER_OR_X86_64 */

#if KXLD_USER_OR_ARM
/*******************************************************************************
*******************************************************************************/
static boolean_t 
arm_reloc_has_pair(u_int _type)
{
    enum reloc_type_arm type = _type;

    switch(type) {
    case ARM_RELOC_SECTDIFF:
        return TRUE;
    default:
        return FALSE;
    }
    return FALSE;
}

/*******************************************************************************
*******************************************************************************/
static u_int 
arm_reloc_get_pair_type(u_int _prev_type __unused)
{
    return ARM_RELOC_PAIR;
}

/*******************************************************************************
*******************************************************************************/
static boolean_t 
arm_reloc_has_got(u_int _type __unused)
{
    return FALSE;
}

/*******************************************************************************
*******************************************************************************/
static kern_return_t 
arm_process_reloc(const KXLDRelocator *relocator __unused, u_char *instruction, 
    u_int length, u_int pcrel, kxld_addr_t _base_pc __unused, 
    kxld_addr_t _link_pc __unused, kxld_addr_t _link_disp __unused,
    u_int _type __unused, kxld_addr_t _target __unused, 
    kxld_addr_t _pair_target __unused,  boolean_t swap __unused)
{
    kern_return_t rval = KERN_FAILURE;
    uint32_t *instr_addr = NULL;
    uint32_t instr_data = 0;
    uint32_t base_pc = (uint32_t) _base_pc;
    uint32_t link_pc = (uint32_t) _link_pc;
    uint32_t target = (uint32_t) _target;
    int32_t displacement = 0;
    enum reloc_type_arm type = _type;

    check(instruction);
    require_action(length == 2, finish, rval=KERN_FAILURE);

    if (pcrel) displacement = target + base_pc - link_pc;

    instr_addr = (uint32_t *) ((void *) instruction);
    instr_data = *instr_addr;
    
#if !KERNEL
    if (swap) instr_data = OSSwapInt32(instr_data);
#endif

    rval = check_for_direct_pure_virtual_call(relocator, instr_data);
    require_noerr(rval, finish);

    switch (type) {
    case ARM_RELOC_VANILLA:
        instr_data += target;
        break;

    /*
     * If the displacement is 0 (the offset between the pc and the target has
     * not changed), then we don't need to do anything for BR24 and BR22
     * relocs.  As it turns out, because kexts build with -mlong-calls all
     * relocations currently end up being either vanilla (handled above) or 
     * BR22/BR24 with a displacement of 0.
     * We could handle other displacements here but to keep things simple, we
     * won't until it is needed (at which point the kernelcache will fail to
     * link)
     */
    case ARM_RELOC_BR24:
        require_action(pcrel, finish, rval=KERN_FAILURE);
        require_action(displacement == 0, finish, rval=KERN_FAILURE);
        break;
    case ARM_THUMB_RELOC_BR22:
        require_action(pcrel, finish, rval=KERN_FAILURE);
        require_action(displacement == 0, finish, rval=KERN_FAILURE);
        break;

    case ARM_RELOC_SECTDIFF:
    case ARM_RELOC_LOCAL_SECTDIFF:
    case ARM_RELOC_PB_LA_PTR:
        rval = KERN_FAILURE;
        goto finish;

    case ARM_RELOC_PAIR:
    default:
        rval = KERN_FAILURE;
        goto finish;
    }

#if !KERNEL
    if (swap) instr_data = OSSwapInt32(instr_data);
#endif

    *instr_addr = instr_data;

    rval = KERN_SUCCESS;

finish:
    return rval;
}

#endif /* KXLD_USER_OR_ARM */

#if KXLD_USER_OR_ARM64
/*******************************************************************************
*******************************************************************************/
boolean_t
arm64_reloc_has_pair(u_int _type)
{
    return (_type == ARM64_RELOC_SUBTRACTOR);
}

/*******************************************************************************
*******************************************************************************/
u_int
arm64_reloc_get_pair_type(u_int _prev_type __unused)
{
    if (_prev_type == ARM64_RELOC_SUBTRACTOR) {
        return ARM64_RELOC_UNSIGNED;
    } else {
        return -1u;
    }
}

/*******************************************************************************
*******************************************************************************/
boolean_t
arm64_reloc_has_got(u_int _type)
{
    return (_type == ARM64_RELOC_GOT_LOAD_PAGE21 ||
            _type == ARM64_RELOC_GOT_LOAD_PAGEOFF12);
}

/*******************************************************************************
*******************************************************************************/
kern_return_t
arm64_process_reloc(const KXLDRelocator *relocator __unused, u_char *instruction,
    u_int length, u_int pcrel, kxld_addr_t _base_pc __unused, kxld_addr_t _link_pc,
    kxld_addr_t _link_disp __unused, u_int _type, kxld_addr_t _target,
    kxld_addr_t _pair_target __unused, boolean_t swap)
{
    kern_return_t rval = KERN_FAILURE;
    enum reloc_type_arm64 type = _type;
    uint64_t target = _target;
    uint64_t link_pc = (uint64_t) _link_pc;
    uint64_t difference = 0;
    int64_t displacement = 0;
    uint32_t addend = 0;

    check(instruction);
    require_action((length == 2 || length == 3), finish, rval=KERN_FAILURE);

    if (length == 2) {
        uint32_t *instr32p = (uint32_t *) (void *) instruction;
        uint32_t instr32 = *instr32p;

#if !KERNEL
        if (swap) instr32 = OSSwapInt32(instr32);
#endif

        switch (type) {
        case ARM64_RELOC_BRANCH26:
            require_action(pcrel, finish, rval=KERN_FAILURE);
            addend = (instr32 & 0x03FFFFFF) << 2;
            addend = SIGN_EXTEND(addend, 27);
            displacement = (target - link_pc + addend);
            difference = ABSOLUTE_VALUE(displacement);
            displacement = (displacement >> 2);
            require_action(difference < (128 * 1024 * 1024), finish,
                           rval = KERN_FAILURE;
                           kxld_log(kKxldLogLinking, kKxldLogErr, kKxldLogRelocationOverflow));
            instr32 = (instr32 & 0xFC000000) | (displacement & 0x03FFFFFF);
            break;

        default:
            rval = KERN_FAILURE;
            goto finish;
        }

#if !KERNEL
        if (swap) instr32 = OSSwapInt32(instr32);
#endif
        
        *instr32p = instr32;
    } else { /* length == 3 */
        uint64_t *instr64p = (uint64_t *) (void *) instruction;
        uint64_t instr64 = *instr64p;

#if !KERNEL
        if (swap) instr64 = OSSwapInt64(instr64);
#endif

        switch (type) {
        case ARM64_RELOC_UNSIGNED:
            require_action(!pcrel, finish, rval=KERN_FAILURE);
            instr64 += target;
            break;
        default:
            rval = KERN_FAILURE;
            goto finish;
        }

#if !KERNEL
        if (swap) instr64 = OSSwapInt64(instr64);
#endif
        
        *instr64p = instr64;
    }

    rval = KERN_SUCCESS;
finish:
    return rval;
}


#endif /* KXLD_USER_OR_ARM64 */
