1 //===------------------ mach-o/compact_unwind_encoding.h ------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //
8 // Darwin's alternative to DWARF based unwind encodings.
9 //
10 //===----------------------------------------------------------------------===//
11 
12 
13 #ifndef __COMPACT_UNWIND_ENCODING__
14 #define __COMPACT_UNWIND_ENCODING__
15 
16 #include <stdint.h>
17 
18 //
19 // Compilers can emit standard DWARF FDEs in the __TEXT,__eh_frame section
20 // of object files. Or compilers can emit compact unwind information in
21 // the __LD,__compact_unwind section.
22 //
23 // When the linker creates a final linked image, it will create a
24 // __TEXT,__unwind_info section.  This section is a small and fast way for the
25 // runtime to access unwind info for any given function.  If the compiler
26 // emitted compact unwind info for the function, that compact unwind info will
27 // be encoded in the __TEXT,__unwind_info section. If the compiler emitted
28 // DWARF unwind info, the __TEXT,__unwind_info section will contain the offset
29 // of the FDE in the __TEXT,__eh_frame section in the final linked image.
30 //
31 // Note: Previously, the linker would transform some DWARF unwind infos into
32 //       compact unwind info.  But that is fragile and no longer done.
33 
34 
35 //
36 // The compact unwind endoding is a 32-bit value which encoded in an
37 // architecture specific way, which registers to restore from where, and how
38 // to unwind out of the function.
39 //
40 typedef uint32_t compact_unwind_encoding_t;
41 
42 
43 // architecture independent bits
44 enum {
45     UNWIND_IS_NOT_FUNCTION_START           = 0x80000000,
46     UNWIND_HAS_LSDA                        = 0x40000000,
47     UNWIND_PERSONALITY_MASK                = 0x30000000,
48 };
49 
50 
51 
52 
53 //
54 // x86
55 //
56 // 1-bit: start
57 // 1-bit: has lsda
58 // 2-bit: personality index
59 //
60 // 4-bits: 0=old, 1=ebp based, 2=stack-imm, 3=stack-ind, 4=DWARF
61 //  ebp based:
62 //        15-bits (5*3-bits per reg) register permutation
63 //        8-bits for stack offset
64 //  frameless:
65 //        8-bits stack size
66 //        3-bits stack adjust
67 //        3-bits register count
68 //        10-bits register permutation
69 //
70 enum {
71     UNWIND_X86_MODE_MASK                         = 0x0F000000,
72     UNWIND_X86_MODE_EBP_FRAME                    = 0x01000000,
73     UNWIND_X86_MODE_STACK_IMMD                   = 0x02000000,
74     UNWIND_X86_MODE_STACK_IND                    = 0x03000000,
75     UNWIND_X86_MODE_DWARF                        = 0x04000000,
76 
77     UNWIND_X86_EBP_FRAME_REGISTERS               = 0x00007FFF,
78     UNWIND_X86_EBP_FRAME_OFFSET                  = 0x00FF0000,
79 
80     UNWIND_X86_FRAMELESS_STACK_SIZE              = 0x00FF0000,
81     UNWIND_X86_FRAMELESS_STACK_ADJUST            = 0x0000E000,
82     UNWIND_X86_FRAMELESS_STACK_REG_COUNT         = 0x00001C00,
83     UNWIND_X86_FRAMELESS_STACK_REG_PERMUTATION   = 0x000003FF,
84 
85     UNWIND_X86_DWARF_SECTION_OFFSET              = 0x00FFFFFF,
86 };
87 
88 enum {
89     UNWIND_X86_REG_NONE     = 0,
90     UNWIND_X86_REG_EBX      = 1,
91     UNWIND_X86_REG_ECX      = 2,
92     UNWIND_X86_REG_EDX      = 3,
93     UNWIND_X86_REG_EDI      = 4,
94     UNWIND_X86_REG_ESI      = 5,
95     UNWIND_X86_REG_EBP      = 6,
96 };
97 
98 //
99 // For x86 there are four modes for the compact unwind encoding:
100 // UNWIND_X86_MODE_EBP_FRAME:
101 //    EBP based frame where EBP is push on stack immediately after return address,
102 //    then ESP is moved to EBP. Thus, to unwind ESP is restored with the current
103 //    EPB value, then EBP is restored by popping off the stack, and the return
104 //    is done by popping the stack once more into the pc.
105 //    All non-volatile registers that need to be restored must have been saved
106 //    in a small range in the stack that starts EBP-4 to EBP-1020.  The offset/4
107 //    is encoded in the UNWIND_X86_EBP_FRAME_OFFSET bits.  The registers saved
108 //    are encoded in the UNWIND_X86_EBP_FRAME_REGISTERS bits as five 3-bit entries.
109 //    Each entry contains which register to restore.
110 // UNWIND_X86_MODE_STACK_IMMD:
111 //    A "frameless" (EBP not used as frame pointer) function with a small
112 //    constant stack size.  To return, a constant (encoded in the compact
113 //    unwind encoding) is added to the ESP. Then the return is done by
114 //    popping the stack into the pc.
115 //    All non-volatile registers that need to be restored must have been saved
116 //    on the stack immediately after the return address.  The stack_size/4 is
117 //    encoded in the UNWIND_X86_FRAMELESS_STACK_SIZE (max stack size is 1024).
118 //    The number of registers saved is encoded in UNWIND_X86_FRAMELESS_STACK_REG_COUNT.
119 //    UNWIND_X86_FRAMELESS_STACK_REG_PERMUTATION constains which registers were
120 //    saved and their order.
121 // UNWIND_X86_MODE_STACK_IND:
122 //    A "frameless" (EBP not used as frame pointer) function large constant
123 //    stack size.  This case is like the previous, except the stack size is too
124 //    large to encode in the compact unwind encoding.  Instead it requires that
125 //    the function contains "subl $nnnnnnnn,ESP" in its prolog.  The compact
126 //    encoding contains the offset to the nnnnnnnn value in the function in
127 //    UNWIND_X86_FRAMELESS_STACK_SIZE.
128 // UNWIND_X86_MODE_DWARF:
129 //    No compact unwind encoding is available.  Instead the low 24-bits of the
130 //    compact encoding is the offset of the DWARF FDE in the __eh_frame section.
131 //    This mode is never used in object files.  It is only generated by the
132 //    linker in final linked images which have only DWARF unwind info for a
133 //    function.
134 //
135 // The permutation encoding is a Lehmer code sequence encoded into a
136 // single variable-base number so we can encode the ordering of up to
137 // six registers in a 10-bit space.
138 //
139 // The following is the algorithm used to create the permutation encoding used
140 // with frameless stacks.  It is passed the number of registers to be saved and
141 // an array of the register numbers saved.
142 //
143 //uint32_t permute_encode(uint32_t registerCount, const uint32_t registers[6])
144 //{
145 //    uint32_t renumregs[6];
146 //    for (int i=6-registerCount; i < 6; ++i) {
147 //        int countless = 0;
148 //        for (int j=6-registerCount; j < i; ++j) {
149 //            if ( registers[j] < registers[i] )
150 //                ++countless;
151 //        }
152 //        renumregs[i] = registers[i] - countless -1;
153 //    }
154 //    uint32_t permutationEncoding = 0;
155 //    switch ( registerCount ) {
156 //        case 6:
157 //            permutationEncoding |= (120*renumregs[0] + 24*renumregs[1]
158 //                                    + 6*renumregs[2] + 2*renumregs[3]
159 //                                      + renumregs[4]);
160 //            break;
161 //        case 5:
162 //            permutationEncoding |= (120*renumregs[1] + 24*renumregs[2]
163 //                                    + 6*renumregs[3] + 2*renumregs[4]
164 //                                      + renumregs[5]);
165 //            break;
166 //        case 4:
167 //            permutationEncoding |= (60*renumregs[2] + 12*renumregs[3]
168 //                                   + 3*renumregs[4] + renumregs[5]);
169 //            break;
170 //        case 3:
171 //            permutationEncoding |= (20*renumregs[3] + 4*renumregs[4]
172 //                                     + renumregs[5]);
173 //            break;
174 //        case 2:
175 //            permutationEncoding |= (5*renumregs[4] + renumregs[5]);
176 //            break;
177 //        case 1:
178 //            permutationEncoding |= (renumregs[5]);
179 //            break;
180 //    }
181 //    return permutationEncoding;
182 //}
183 //
184 
185 
186 
187 
188 //
189 // x86_64
190 //
191 // 1-bit: start
192 // 1-bit: has lsda
193 // 2-bit: personality index
194 //
195 // 4-bits: 0=old, 1=rbp based, 2=stack-imm, 3=stack-ind, 4=DWARF
196 //  rbp based:
197 //        15-bits (5*3-bits per reg) register permutation
198 //        8-bits for stack offset
199 //  frameless:
200 //        8-bits stack size
201 //        3-bits stack adjust
202 //        3-bits register count
203 //        10-bits register permutation
204 //
205 enum {
206     UNWIND_X86_64_MODE_MASK                         = 0x0F000000,
207     UNWIND_X86_64_MODE_RBP_FRAME                    = 0x01000000,
208     UNWIND_X86_64_MODE_STACK_IMMD                   = 0x02000000,
209     UNWIND_X86_64_MODE_STACK_IND                    = 0x03000000,
210     UNWIND_X86_64_MODE_DWARF                        = 0x04000000,
211 
212     UNWIND_X86_64_RBP_FRAME_REGISTERS               = 0x00007FFF,
213     UNWIND_X86_64_RBP_FRAME_OFFSET                  = 0x00FF0000,
214 
215     UNWIND_X86_64_FRAMELESS_STACK_SIZE              = 0x00FF0000,
216     UNWIND_X86_64_FRAMELESS_STACK_ADJUST            = 0x0000E000,
217     UNWIND_X86_64_FRAMELESS_STACK_REG_COUNT         = 0x00001C00,
218     UNWIND_X86_64_FRAMELESS_STACK_REG_PERMUTATION   = 0x000003FF,
219 
220     UNWIND_X86_64_DWARF_SECTION_OFFSET              = 0x00FFFFFF,
221 };
222 
223 enum {
224     UNWIND_X86_64_REG_NONE       = 0,
225     UNWIND_X86_64_REG_RBX        = 1,
226     UNWIND_X86_64_REG_R12        = 2,
227     UNWIND_X86_64_REG_R13        = 3,
228     UNWIND_X86_64_REG_R14        = 4,
229     UNWIND_X86_64_REG_R15        = 5,
230     UNWIND_X86_64_REG_RBP        = 6,
231 };
232 //
233 // For x86_64 there are four modes for the compact unwind encoding:
234 // UNWIND_X86_64_MODE_RBP_FRAME:
235 //    RBP based frame where RBP is push on stack immediately after return address,
236 //    then RSP is moved to RBP. Thus, to unwind RSP is restored with the current
237 //    EPB value, then RBP is restored by popping off the stack, and the return
238 //    is done by popping the stack once more into the pc.
239 //    All non-volatile registers that need to be restored must have been saved
240 //    in a small range in the stack that starts RBP-8 to RBP-2040.  The offset/8
241 //    is encoded in the UNWIND_X86_64_RBP_FRAME_OFFSET bits.  The registers saved
242 //    are encoded in the UNWIND_X86_64_RBP_FRAME_REGISTERS bits as five 3-bit entries.
243 //    Each entry contains which register to restore.
244 // UNWIND_X86_64_MODE_STACK_IMMD:
245 //    A "frameless" (RBP not used as frame pointer) function with a small
246 //    constant stack size.  To return, a constant (encoded in the compact
247 //    unwind encoding) is added to the RSP. Then the return is done by
248 //    popping the stack into the pc.
249 //    All non-volatile registers that need to be restored must have been saved
250 //    on the stack immediately after the return address.  The stack_size/8 is
251 //    encoded in the UNWIND_X86_64_FRAMELESS_STACK_SIZE (max stack size is 2048).
252 //    The number of registers saved is encoded in UNWIND_X86_64_FRAMELESS_STACK_REG_COUNT.
253 //    UNWIND_X86_64_FRAMELESS_STACK_REG_PERMUTATION constains which registers were
254 //    saved and their order.
255 // UNWIND_X86_64_MODE_STACK_IND:
256 //    A "frameless" (RBP not used as frame pointer) function large constant
257 //    stack size.  This case is like the previous, except the stack size is too
258 //    large to encode in the compact unwind encoding.  Instead it requires that
259 //    the function contains "subq $nnnnnnnn,RSP" in its prolog.  The compact
260 //    encoding contains the offset to the nnnnnnnn value in the function in
261 //    UNWIND_X86_64_FRAMELESS_STACK_SIZE.
262 // UNWIND_X86_64_MODE_DWARF:
263 //    No compact unwind encoding is available.  Instead the low 24-bits of the
264 //    compact encoding is the offset of the DWARF FDE in the __eh_frame section.
265 //    This mode is never used in object files.  It is only generated by the
266 //    linker in final linked images which have only DWARF unwind info for a
267 //    function.
268 //
269 
270 
271 // ARM64
272 //
273 // 1-bit: start
274 // 1-bit: has lsda
275 // 2-bit: personality index
276 //
277 // 4-bits: 4=frame-based, 3=DWARF, 2=frameless
278 //  frameless:
279 //        12-bits of stack size
280 //  frame-based:
281 //        4-bits D reg pairs saved
282 //        5-bits X reg pairs saved
283 //  DWARF:
284 //        24-bits offset of DWARF FDE in __eh_frame section
285 //
286 enum {
287     UNWIND_ARM64_MODE_MASK                     = 0x0F000000,
288     UNWIND_ARM64_MODE_FRAMELESS                = 0x02000000,
289     UNWIND_ARM64_MODE_DWARF                    = 0x03000000,
290     UNWIND_ARM64_MODE_FRAME                    = 0x04000000,
291 
292     UNWIND_ARM64_FRAME_X19_X20_PAIR            = 0x00000001,
293     UNWIND_ARM64_FRAME_X21_X22_PAIR            = 0x00000002,
294     UNWIND_ARM64_FRAME_X23_X24_PAIR            = 0x00000004,
295     UNWIND_ARM64_FRAME_X25_X26_PAIR            = 0x00000008,
296     UNWIND_ARM64_FRAME_X27_X28_PAIR            = 0x00000010,
297     UNWIND_ARM64_FRAME_D8_D9_PAIR              = 0x00000100,
298     UNWIND_ARM64_FRAME_D10_D11_PAIR            = 0x00000200,
299     UNWIND_ARM64_FRAME_D12_D13_PAIR            = 0x00000400,
300     UNWIND_ARM64_FRAME_D14_D15_PAIR            = 0x00000800,
301 
302     UNWIND_ARM64_FRAMELESS_STACK_SIZE_MASK     = 0x00FFF000,
303     UNWIND_ARM64_DWARF_SECTION_OFFSET          = 0x00FFFFFF,
304 };
305 // For arm64 there are three modes for the compact unwind encoding:
306 // UNWIND_ARM64_MODE_FRAME:
307 //    This is a standard arm64 prolog where FP/LR are immediately pushed on the
308 //    stack, then SP is copied to FP. If there are any non-volatile registers
309 //    saved, then are copied into the stack frame in pairs in a contiguous
310 //    range right below the saved FP/LR pair.  Any subset of the five X pairs
311 //    and four D pairs can be saved, but the memory layout must be in register
312 //    number order.
313 // UNWIND_ARM64_MODE_FRAMELESS:
314 //    A "frameless" leaf function, where FP/LR are not saved. The return address
315 //    remains in LR throughout the function. If any non-volatile registers
316 //    are saved, they must be pushed onto the stack before any stack space is
317 //    allocated for local variables.  The stack sized (including any saved
318 //    non-volatile registers) divided by 16 is encoded in the bits
319 //    UNWIND_ARM64_FRAMELESS_STACK_SIZE_MASK.
320 // UNWIND_ARM64_MODE_DWARF:
321 //    No compact unwind encoding is available.  Instead the low 24-bits of the
322 //    compact encoding is the offset of the DWARF FDE in the __eh_frame section.
323 //    This mode is never used in object files.  It is only generated by the
324 //    linker in final linked images which have only DWARF unwind info for a
325 //    function.
326 //
327 
328 
329 
330 
331 
332 ////////////////////////////////////////////////////////////////////////////////
333 //
334 //  Relocatable Object Files: __LD,__compact_unwind
335 //
336 ////////////////////////////////////////////////////////////////////////////////
337 
338 //
339 // A compiler can generated compact unwind information for a function by adding
340 // a "row" to the __LD,__compact_unwind section.  This section has the
341 // S_ATTR_DEBUG bit set, so the section will be ignored by older linkers.
342 // It is removed by the new linker, so never ends up in final executables.
343 // This section is a table, initially with one row per function (that needs
344 // unwind info).  The table columns and some conceptual entries are:
345 //
346 //     range-start               pointer to start of function/range
347 //     range-length
348 //     compact-unwind-encoding   32-bit encoding
349 //     personality-function      or zero if no personality function
350 //     lsda                      or zero if no LSDA data
351 //
352 // The length and encoding fields are 32-bits.  The other are all pointer sized.
353 //
354 // In x86_64 assembly, these entry would look like:
355 //
356 //     .section __LD,__compact_unwind,regular,debug
357 //
358 //     #compact unwind for _foo
359 //     .quad    _foo
360 //     .set     L1,LfooEnd-_foo
361 //     .long    L1
362 //     .long    0x01010001
363 //     .quad    0
364 //     .quad    0
365 //
366 //     #compact unwind for _bar
367 //     .quad    _bar
368 //     .set     L2,LbarEnd-_bar
369 //     .long    L2
370 //     .long    0x01020011
371 //     .quad    __gxx_personality
372 //     .quad    except_tab1
373 //
374 //
375 // Notes: There is no need for any labels in the the __compact_unwind section.
376 //        The use of the .set directive is to force the evaluation of the
377 //        range-length at assembly time, instead of generating relocations.
378 //
379 // To support future compiler optimizations where which non-volatile registers
380 // are saved changes within a function (e.g. delay saving non-volatiles until
381 // necessary), there can by multiple lines in the __compact_unwind table for one
382 // function, each with a different (non-overlapping) range and each with
383 // different compact unwind encodings that correspond to the non-volatiles
384 // saved at that range of the function.
385 //
386 // If a particular function is so wacky that there is no compact unwind way
387 // to encode it, then the compiler can emit traditional DWARF unwind info.
388 // The runtime will use which ever is available.
389 //
390 // Runtime support for compact unwind encodings are only available on 10.6
391 // and later.  So, the compiler should not generate it when targeting pre-10.6.
392 
393 
394 
395 
396 ////////////////////////////////////////////////////////////////////////////////
397 //
398 //  Final Linked Images: __TEXT,__unwind_info
399 //
400 ////////////////////////////////////////////////////////////////////////////////
401 
402 //
403 // The __TEXT,__unwind_info section is laid out for an efficient two level lookup.
404 // The header of the section contains a coarse index that maps function address
405 // to the page (4096 byte block) containing the unwind info for that function.
406 //
407 
408 #define UNWIND_SECTION_VERSION 1
409 struct unwind_info_section_header
410 {
411     uint32_t    version;            // UNWIND_SECTION_VERSION
412     uint32_t    commonEncodingsArraySectionOffset;
413     uint32_t    commonEncodingsArrayCount;
414     uint32_t    personalityArraySectionOffset;
415     uint32_t    personalityArrayCount;
416     uint32_t    indexSectionOffset;
417     uint32_t    indexCount;
418     // compact_unwind_encoding_t[]
419     // uint32_t personalities[]
420     // unwind_info_section_header_index_entry[]
421     // unwind_info_section_header_lsda_index_entry[]
422 };
423 
424 struct unwind_info_section_header_index_entry
425 {
426     uint32_t        functionOffset;
427     uint32_t        secondLevelPagesSectionOffset;  // section offset to start of regular or compress page
428     uint32_t        lsdaIndexArraySectionOffset;    // section offset to start of lsda_index array for this range
429 };
430 
431 struct unwind_info_section_header_lsda_index_entry
432 {
433     uint32_t        functionOffset;
434     uint32_t        lsdaOffset;
435 };
436 
437 //
438 // There are two kinds of second level index pages: regular and compressed.
439 // A compressed page can hold up to 1021 entries, but it cannot be used
440 // if too many different encoding types are used.  The regular page holds
441 // 511 entries.
442 //
443 
444 struct unwind_info_regular_second_level_entry
445 {
446     uint32_t                    functionOffset;
447     compact_unwind_encoding_t    encoding;
448 };
449 
450 #define UNWIND_SECOND_LEVEL_REGULAR 2
451 struct unwind_info_regular_second_level_page_header
452 {
453     uint32_t    kind;    // UNWIND_SECOND_LEVEL_REGULAR
454     uint16_t    entryPageOffset;
455     uint16_t    entryCount;
456     // entry array
457 };
458 
459 #define UNWIND_SECOND_LEVEL_COMPRESSED 3
460 struct unwind_info_compressed_second_level_page_header
461 {
462     uint32_t    kind;    // UNWIND_SECOND_LEVEL_COMPRESSED
463     uint16_t    entryPageOffset;
464     uint16_t    entryCount;
465     uint16_t    encodingsPageOffset;
466     uint16_t    encodingsCount;
467     // 32-bit entry array
468     // encodings array
469 };
470 
471 #define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(entry)            (entry & 0x00FFFFFF)
472 #define UNWIND_INFO_COMPRESSED_ENTRY_ENCODING_INDEX(entry)        ((entry >> 24) & 0xFF)
473 
474 
475 
476 #endif
477 
478