/* -*- mode: C; c-basic-offset: 4; tab-width: 4 -*-
 *
 * Copyright (c) 2008-2011 Apple Inc. All rights reserved.
 *
 * @APPLE_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. 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_LICENSE_HEADER_END@
 */
 

#ifndef __COMPACT_UNWIND_ENCODING__
#define __COMPACT_UNWIND_ENCODING__

#include <stdint.h>



//
// Compilers can emit standard Dwarf FDEs in the __TEXT,__eh_frame section 
// of object files. Or compilers can emit compact unwind information in 
// the __LD,__compact_unwind section.
//
// When the linker creates a final linked image, it will create a  
// __TEXT,__unwind_info section.  This section is a small and fast way for the 
// runtime to access unwind info for any given function.  If the compiler emitted
// compact unwind info for the function, that compact unwind info will be encoded
// in the __TEXT,__unwind_info section. If the compiler emitted dwarf unwind info,
// the __TEXT,__unwind_info section will contain the offset of the FDE in the
// __TEXT,__eh_frame section in the final linked image.  
//
// Note: Previously, the linker would transform some dwarf unwind infos into 
//       compact unwind info.  But that is fragile and no longer done.


//
// The compact unwind endoding is a 32-bit value which encoded in an architecture
// specific way, which registers to restore from where, and how to unwind out
// of the function.  
//
typedef uint32_t compact_unwind_encoding_t;


// architecture independent bits
enum {
    UNWIND_IS_NOT_FUNCTION_START           = 0x80000000,
    UNWIND_HAS_LSDA                        = 0x40000000,
    UNWIND_PERSONALITY_MASK                = 0x30000000,
};




//
// x86
//
// 1-bit: start
// 1-bit: has lsda
// 2-bit: personality index
//
// 4-bits: 0=old, 1=ebp based, 2=stack-imm, 3=stack-ind, 4=dwarf
//  ebp based:
//        15-bits (5*3-bits per reg) register permutation
//        8-bits for stack offset
//  frameless:
//        8-bits stack size
//        3-bits stack adjust
//        3-bits register count
//        10-bits register permutation
//
enum {
    UNWIND_X86_MODE_MASK                         = 0x0F000000,
    UNWIND_X86_MODE_EBP_FRAME                    = 0x01000000,
    UNWIND_X86_MODE_STACK_IMMD                   = 0x02000000,
    UNWIND_X86_MODE_STACK_IND                    = 0x03000000,
    UNWIND_X86_MODE_DWARF                        = 0x04000000,
    
    UNWIND_X86_EBP_FRAME_REGISTERS               = 0x00007FFF,
    UNWIND_X86_EBP_FRAME_OFFSET                  = 0x00FF0000,
    
    UNWIND_X86_FRAMELESS_STACK_SIZE              = 0x00FF0000,
    UNWIND_X86_FRAMELESS_STACK_ADJUST            = 0x0000E000,
    UNWIND_X86_FRAMELESS_STACK_REG_COUNT         = 0x00001C00,
    UNWIND_X86_FRAMELESS_STACK_REG_PERMUTATION   = 0x000003FF,
    
    UNWIND_X86_DWARF_SECTION_OFFSET              = 0x00FFFFFF,
};

enum {
    UNWIND_X86_REG_NONE     = 0,
    UNWIND_X86_REG_EBX      = 1,
    UNWIND_X86_REG_ECX      = 2,
    UNWIND_X86_REG_EDX      = 3,
    UNWIND_X86_REG_EDI      = 4,
    UNWIND_X86_REG_ESI      = 5,
    UNWIND_X86_REG_EBP      = 6,
};

//
// For x86 there are four modes for the compact unwind encoding:
// UNWIND_X86_MODE_EBP_FRAME:
//    EBP based frame where EBP is push on stack immediately after return address, 
//    then ESP is moved to EBP. Thus, to unwind ESP is restored with the current 
//    EPB value, then EBP is restored by popping off the stack, and the return 
//    is done by popping the stack once more into the pc.
//    All non-volatile registers that need to be restored must have been saved
//    in a small range in the stack that starts EBP-4 to EBP-1020.  The offset/4 
//    is encoded in the UNWIND_X86_EBP_FRAME_OFFSET bits.  The registers saved
//    are encoded in the UNWIND_X86_EBP_FRAME_REGISTERS bits as five 3-bit entries.
//    Each entry contains which register to restore.  
// UNWIND_X86_MODE_STACK_IMMD:
//    A "frameless" (EBP not used as frame pointer) function with a small 
//    constant stack size.  To return, a constant (encoded in the compact 
//    unwind encoding) is added to the ESP. Then the return is done by 
//    popping the stack into the pc.
//    All non-volatile registers that need to be restored must have been saved
//    on the stack immediately after the return address.  The stack_size/4 is
//    encoded in the UNWIND_X86_FRAMELESS_STACK_SIZE (max stack size is 1024).
//    The number of registers saved is encoded in UNWIND_X86_FRAMELESS_STACK_REG_COUNT.
//    UNWIND_X86_FRAMELESS_STACK_REG_PERMUTATION constains which registers were
//    saved and their order.  
// UNWIND_X86_MODE_STACK_IND:
//    A "frameless" (EBP not used as frame pointer) function large constant 
//    stack size.  This case is like the previous, except the stack size is too
//    large to encode in the compact unwind encoding.  Instead it requires that 
//    the function contains "subl $nnnnnnnn,ESP" in its prolog.  The compact 
//    encoding contains the offset to the nnnnnnnn value in the function in
//    UNWIND_X86_FRAMELESS_STACK_SIZE.  
// UNWIND_X86_MODE_DWARF:
//    No compact unwind encoding is available.  Instead the low 24-bits of the
//    compact encoding is the offset of the dwarf FDE in the __eh_frame section.
//    This mode is never used in object files.  It is only generated by the 
//    linker in final linked images which have only dwarf unwind info for a
//    function.
//
// The following is the algorithm used to create the permutation encoding used
// with frameless stacks.  It is passed the number of registers to be saved and
// an array of the register numbers saved.
//
//uint32_t permute_encode(uint32_t registerCount, const uint32_t registers[6])
//{
//    uint32_t renumregs[6];
//    for (int i=6-registerCount; i < 6; ++i) {
//        int countless = 0;
//        for (int j=6-registerCount; j < i; ++j) {
//            if ( registers[j] < registers[i] )
//                ++countless;
//        }
//        renumregs[i] = registers[i] - countless -1;
//    }
//    uint32_t permutationEncoding = 0;
//    switch ( registerCount ) {
//        case 6:
//            permutationEncoding |= (120*renumregs[0] + 24*renumregs[1] 
//                                    + 6*renumregs[2] + 2*renumregs[3] 
//                                      + renumregs[4]);
//            break;
//        case 5:
//            permutationEncoding |= (120*renumregs[1] + 24*renumregs[2] 
//                                    + 6*renumregs[3] + 2*renumregs[4] 
//                                      + renumregs[5]);
//            break;
//        case 4:
//            permutationEncoding |= (60*renumregs[2] + 12*renumregs[3] 
//                                   + 3*renumregs[4] + renumregs[5]);
//            break;
//        case 3:
//            permutationEncoding |= (20*renumregs[3] + 4*renumregs[4] 
//                                     + renumregs[5]);
//            break;
//        case 2:
//            permutationEncoding |= (5*renumregs[4] + renumregs[5]);
//            break;
//        case 1:
//            permutationEncoding |= (renumregs[5]);
//            break;
//    }
//    return permutationEncoding;
//}
//




//
// x86_64
//
// 1-bit: start
// 1-bit: has lsda
// 2-bit: personality index
//
// 4-bits: 0=old, 1=rbp based, 2=stack-imm, 3=stack-ind, 4=dwarf
//  rbp based:
//        15-bits (5*3-bits per reg) register permutation
//        8-bits for stack offset
//  frameless:
//        8-bits stack size
//        3-bits stack adjust
//        3-bits register count
//        10-bits register permutation
//
enum {
    UNWIND_X86_64_MODE_MASK                         = 0x0F000000,
    UNWIND_X86_64_MODE_RBP_FRAME                    = 0x01000000,
    UNWIND_X86_64_MODE_STACK_IMMD                   = 0x02000000,
    UNWIND_X86_64_MODE_STACK_IND                    = 0x03000000,
    UNWIND_X86_64_MODE_DWARF                        = 0x04000000,
    
    UNWIND_X86_64_RBP_FRAME_REGISTERS               = 0x00007FFF,
    UNWIND_X86_64_RBP_FRAME_OFFSET                  = 0x00FF0000,

    UNWIND_X86_64_FRAMELESS_STACK_SIZE              = 0x00FF0000,
    UNWIND_X86_64_FRAMELESS_STACK_ADJUST            = 0x0000E000,
    UNWIND_X86_64_FRAMELESS_STACK_REG_COUNT         = 0x00001C00,
    UNWIND_X86_64_FRAMELESS_STACK_REG_PERMUTATION   = 0x000003FF,

    UNWIND_X86_64_DWARF_SECTION_OFFSET              = 0x00FFFFFF,
};

enum {
    UNWIND_X86_64_REG_NONE       = 0,
    UNWIND_X86_64_REG_RBX        = 1,
    UNWIND_X86_64_REG_R12        = 2,
    UNWIND_X86_64_REG_R13        = 3,
    UNWIND_X86_64_REG_R14        = 4,
    UNWIND_X86_64_REG_R15        = 5,
    UNWIND_X86_64_REG_RBP        = 6,
};
//
// For x86_64 there are four modes for the compact unwind encoding:
// UNWIND_X86_64_MODE_RBP_FRAME:
//    RBP based frame where RBP is push on stack immediately after return address, 
//    then RSP is moved to RBP. Thus, to unwind RSP is restored with the current 
//    EPB value, then RBP is restored by popping off the stack, and the return 
//    is done by popping the stack once more into the pc.
//    All non-volatile registers that need to be restored must have been saved
//    in a small range in the stack that starts RBP-8 to RBP-1020.  The offset/4 
//    is encoded in the UNWIND_X86_64_RBP_FRAME_OFFSET bits.  The registers saved
//    are encoded in the UNWIND_X86_64_RBP_FRAME_REGISTERS bits as five 3-bit entries.
//    Each entry contains which register to restore.  
// UNWIND_X86_64_MODE_STACK_IMMD:
//    A "frameless" (RBP not used as frame pointer) function with a small 
//    constant stack size.  To return, a constant (encoded in the compact 
//    unwind encoding) is added to the RSP. Then the return is done by 
//    popping the stack into the pc.
//    All non-volatile registers that need to be restored must have been saved
//    on the stack immediately after the return address.  The stack_size/4 is
//    encoded in the UNWIND_X86_64_FRAMELESS_STACK_SIZE (max stack size is 1024).
//    The number of registers saved is encoded in UNWIND_X86_64_FRAMELESS_STACK_REG_COUNT.
//    UNWIND_X86_64_FRAMELESS_STACK_REG_PERMUTATION constains which registers were
//    saved and their order.  
// UNWIND_X86_64_MODE_STACK_IND:
//    A "frameless" (RBP not used as frame pointer) function large constant 
//    stack size.  This case is like the previous, except the stack size is too
//    large to encode in the compact unwind encoding.  Instead it requires that 
//    the function contains "subq $nnnnnnnn,RSP" in its prolog.  The compact 
//    encoding contains the offset to the nnnnnnnn value in the function in
//    UNWIND_X86_64_FRAMELESS_STACK_SIZE.  
// UNWIND_X86_64_MODE_DWARF:
//    No compact unwind encoding is available.  Instead the low 24-bits of the
//    compact encoding is the offset of the dwarf FDE in the __eh_frame section.
//    This mode is never used in object files.  It is only generated by the 
//    linker in final linked images which have only dwarf unwind info for a
//    function.
//



////////////////////////////////////////////////////////////////////////////////
//
//  Relocatable Object Files: __LD,__compact_unwind
//
////////////////////////////////////////////////////////////////////////////////

//
// A compiler can generated compact unwind information for a function by adding
// a "row" to the __LD,__compact_unwind section.  This section has the 
// S_ATTR_DEBUG bit set, so the section will be ignored by older linkers. 
// It is removed by the new linker, so never ends up in final executables. 
// This section is a table, initially with one row per function (that needs 
// unwind info).  The table columns and some conceptual entries are:
//
//	   range-start               pointer to start of function/range
//     range-length              
//     compact-unwind-encoding   32-bit encoding  
//     personality-function      or zero if no personality function
//     lsda                      or zero if no LSDA data
//
// The length and encoding fields are 32-bits.  The other are all pointer sized. 
//
// In x86_64 assembly, these entry would look like:
//
//     .section __LD,__compact_unwind,regular,debug
//
//     #compact unwind for _foo
//     .quad    _foo
//     .set     L1,LfooEnd-_foo
//     .long    L1
//     .long    0x01010001
//     .quad    0
//     .quad    0
//
//     #compact unwind for _bar
//     .quad    _bar
//     .set     L2,LbarEnd-_bar
//     .long    L2
//     .long    0x01020011
//     .quad    __gxx_personality
//     .quad    except_tab1
//
//
// Notes: There is no need for any labels in the the __compact_unwind section.  
//        The use of the .set directive is to force the evaluation of the 
//        range-length at assembly time, instead of generating relocations.
//
// To support future compiler optimizations where which non-volatile registers 
// are saved changes within a function (e.g. delay saving non-volatiles until
// necessary), there can by multiple lines in the __compact_unwind table for one
// function, each with a different (non-overlapping) range and each with 
// different compact unwind encodings that correspond to the non-volatiles 
// saved at that range of the function.
//
// If a particular function is so wacky that there is no compact unwind way
// to encode it, then the compiler can emit traditional dwarf unwind info.  
// The runtime will use which ever is available.
//
// Runtime support for compact unwind encodings are only available on 10.6 
// and later.  So, the compiler should not generate it when targeting pre-10.6. 




////////////////////////////////////////////////////////////////////////////////
//
//  Final Linked Images: __TEXT,__unwind_info
//
////////////////////////////////////////////////////////////////////////////////

//
// The __TEXT,__unwind_info section is laid out for an efficient two level lookup.
// The header of the section contains a coarse index that maps function address
// to the page (4096 byte block) containing the unwind info for that function.  
//

#define UNWIND_SECTION_VERSION 1
struct unwind_info_section_header
{
    uint32_t    version;            // UNWIND_SECTION_VERSION
    uint32_t    commonEncodingsArraySectionOffset;
    uint32_t    commonEncodingsArrayCount;
    uint32_t    personalityArraySectionOffset;
    uint32_t    personalityArrayCount;
    uint32_t    indexSectionOffset;
    uint32_t    indexCount;
    // compact_unwind_encoding_t[]
    // uintptr_t personalities[]
    // unwind_info_section_header_index_entry[]
    // unwind_info_section_header_lsda_index_entry[]
};

struct unwind_info_section_header_index_entry 
{
    uint32_t        functionOffset;
    uint32_t        secondLevelPagesSectionOffset;  // section offset to start of regular or compress page
    uint32_t        lsdaIndexArraySectionOffset;    // section offset to start of lsda_index array for this range
};

struct unwind_info_section_header_lsda_index_entry 
{
    uint32_t        functionOffset;
    uint32_t        lsdaOffset;
};

//
// There are two kinds of second level index pages: regular and compressed.
// A compressed page can hold up to 1021 entries, but it cannot be used
// if too many different encoding types are used.  The regular page holds
// 511 entries.  
//

struct unwind_info_regular_second_level_entry 
{
    uint32_t                    functionOffset;
    compact_unwind_encoding_t    encoding;
};

#define UNWIND_SECOND_LEVEL_REGULAR 2
struct unwind_info_regular_second_level_page_header
{
    uint32_t    kind;    // UNWIND_SECOND_LEVEL_REGULAR
    uint16_t    entryPageOffset;
    uint16_t    entryCount;
    // entry array
};

#define UNWIND_SECOND_LEVEL_COMPRESSED 3
struct unwind_info_compressed_second_level_page_header
{
    uint32_t    kind;    // UNWIND_SECOND_LEVEL_COMPRESSED
    uint16_t    entryPageOffset;
    uint16_t    entryCount;
    uint16_t    encodingsPageOffset;
    uint16_t    encodingsCount;
    // 32-bit entry array    
    // encodings array
};

#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(entry)            (entry & 0x00FFFFFF)
#define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX(entry)        ((entry >> 24) & 0xFF)



#endif