1 /**
2  * Compiler implementation of the D programming language.
3  * Implements LSDA (Language Specific Data Area) table generation
4  * for Dwarf Exception Handling.
5  *
6  * Copyright: Copyright (C) 2015-2020 by The D Language Foundation, All Rights Reserved
7  * Authors: Walter Bright, http://www.digitalmars.com
8  * License:   $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
9  * Source:    $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/dwarfeh.d, backend/dwarfeh.d)
10  */
11 
12 module dmd.backend.dwarfeh;
13 
14 import core.stdc.stdio;
15 import core.stdc.stdlib;
16 import core.stdc..string;
17 
18 import dmd.backend.cc;
19 import dmd.backend.cdef;
20 import dmd.backend.code;
21 import dmd.backend.code_x86;
22 import dmd.backend.outbuf;
23 
24 static if (ELFOBJ || MACHOBJ)
25 {
26 
27 import dmd.backend.dwarf;
28 import dmd.backend.dwarf2;
29 
30 extern (C++):
31 
32 nothrow:
33 
34 struct DwEhTableEntry
35 {
36     uint start;
37     uint end;           // 1 past end
38     uint lpad;          // landing pad
39     uint action;        // index into Action Table
40     block *bcatch;      // catch block data
41     int prev;           // index to enclosing entry (-1 for none)
42 }
43 
44 struct DwEhTable
45 {
46 nothrow:
47     DwEhTableEntry *ptr;    // pointer to table
48     uint dim;               // current amount used
49     uint capacity;
50 
51     DwEhTableEntry *index(uint i)
52     {
53         if (i >= dim) printf("i = %d dim = %d\n", i, dim);
54         assert(i < dim);
55         return ptr + i;
56     }
57 
58     uint push()
59     {
60         assert(dim <= capacity);
61         if (dim == capacity)
62         {
63             capacity += capacity + 16;
64             ptr = cast(DwEhTableEntry *)realloc(ptr, capacity * DwEhTableEntry.sizeof);
65             assert(ptr);
66         }
67         memset(ptr + dim, 0, DwEhTableEntry.sizeof);
68         return dim++;
69     }
70 }
71 
72 private __gshared DwEhTable dwehtable;
73 
74 /****************************
75  * Generate .gcc_except_table, aka LS
76  * Params:
77  *      sfunc = function to generate table for
78  *      seg = .gcc_except_table segment
79  *      et = buffer to insert table into
80  *      scancode = true if there are destructors in the code (i.e. usednteh & EHcleanup)
81  *      startoffset = size of function prolog
82  *      retoffset = offset from start of function to epilog
83  */
84 
85 void genDwarfEh(Funcsym *sfunc, int seg, Outbuffer *et, bool scancode, uint startoffset, uint retoffset)
86 {
87     debug
88     unittest_dwarfeh();
89 
90     /* LPstart = encoding of LPbase
91      * LPbase = landing pad base (normally omitted)
92      * TType = encoding of TTbase
93      * TTbase = offset from next byte to past end of Type Table
94      * CallSiteFormat = encoding of fields in Call Site Table
95      * CallSiteTableSize = size in bytes of Call Site Table
96      * Call Site Table[]:
97      *    CallSiteStart
98      *    CallSiteRange
99      *    LandingPad
100      *    ActionRecordPtr
101      * Action Table
102      *    TypeFilter
103      *    NextRecordPtr
104      * Type Table
105      */
106 
107     et.reserve(100);
108     block *startblock = sfunc.Sfunc.Fstartblock;
109     //printf("genDwarfEh: func = %s, offset = x%x, startblock.Boffset = x%x, scancode = %d startoffset=x%x, retoffset=x%x\n",
110       //sfunc.Sident.ptr, cast(int)sfunc.Soffset, cast(int)startblock.Boffset, scancode, startoffset, retoffset);
111 
112 static if (0)
113 {
114     printf("------- before ----------\n");
115     for (block *b = startblock; b; b = b.Bnext) WRblock(b);
116     printf("-------------------------\n");
117 }
118 
119     uint startsize = cast(uint)et.length();
120     assert((startsize & 3) == 0);       // should be aligned
121 
122     DwEhTable *deh = &dwehtable;
123     deh.dim = 0;
124     Outbuffer atbuf;
125     Outbuffer cstbuf;
126 
127     /* Build deh table, and Action Table
128      */
129     int index = -1;
130     block *bprev = null;
131     // The first entry encompasses the entire function
132     {
133         uint i = deh.push();
134         DwEhTableEntry *d = deh.index(i);
135         d.start = cast(uint)(startblock.Boffset + startoffset);
136         d.end = cast(uint)(startblock.Boffset + retoffset);
137         d.lpad = 0;                    // no cleanup, no catches
138         index = i;
139     }
140     for (block *b = startblock; b; b = b.Bnext)
141     {
142         if (index > 0 && b.Btry == bprev)
143         {
144             DwEhTableEntry *d = deh.index(index);
145             d.end = cast(uint)b.Boffset;
146             index = d.prev;
147             if (bprev)
148                 bprev = bprev.Btry;
149         }
150         if (b.BC == BC_try)
151         {
152             uint i = deh.push();
153             DwEhTableEntry *d = deh.index(i);
154             d.start = cast(uint)b.Boffset;
155 
156             block *bf = b.nthSucc(1);
157             if (bf.BC == BCjcatch)
158             {
159                 d.lpad = cast(uint)bf.Boffset;
160                 d.bcatch = bf;
161                 uint *pat = bf.actionTable;
162                 uint length = pat[0];
163                 assert(length);
164                 uint offset = -1;
165                 for (uint u = length; u; --u)
166                 {
167                     /* Buy doing depth-first insertion into the Action Table,
168                      * we can combine common tails.
169                      */
170                     offset = actionTableInsert(&atbuf, pat[u], offset);
171                 }
172                 d.action = offset + 1;
173             }
174             else
175                 d.lpad = cast(uint)bf.nthSucc(0).Boffset;
176             d.prev = index;
177             index = i;
178             bprev = b.Btry;
179         }
180         if (scancode)
181         {
182             uint coffset = cast(uint)b.Boffset;
183             int n = 0;
184             for (code *c = b.Bcode; c; c = code_next(c))
185             {
186                 if (c.Iop == (ESCAPE | ESCdctor))
187                 {
188                     uint i = deh.push();
189                     DwEhTableEntry *d = deh.index(i);
190                     d.start = coffset;
191                     d.prev = index;
192                     index = i;
193                     ++n;
194                 }
195 
196                 if (c.Iop == (ESCAPE | ESCddtor))
197                 {
198                     assert(n > 0);
199                     --n;
200                     DwEhTableEntry *d = deh.index(index);
201                     d.end = coffset;
202                     d.lpad = coffset;
203                     index = d.prev;
204                 }
205                 coffset += calccodsize(c);
206             }
207             assert(n == 0);
208         }
209     }
210     //printf("deh.dim = %d\n", (int)deh.dim);
211 
212 static if (1)
213 {
214     /* Build Call Site Table
215      * Be sure to not generate empty entries,
216      * and generate nested ranges reflecting the layout in the code.
217      */
218     assert(deh.dim);
219     uint end = deh.index(0).start;
220     for (uint i = 0; i < deh.dim; ++i)
221     {
222         DwEhTableEntry *d = deh.index(i);
223         if (d.start < d.end)
224         {
225 static if (ELFOBJ)
226                 auto WRITE = &cstbuf.writeuLEB128;
227 else static if (MACHOBJ)
228                 auto WRITE = &cstbuf.write32;
229 else
230                 assert(0);
231 
232                 uint CallSiteStart = cast(uint)(d.start - startblock.Boffset);
233                 WRITE(CallSiteStart);
234                 uint CallSiteRange = d.end - d.start;
235                 WRITE(CallSiteRange);
236                 uint LandingPad = cast(uint)(d.lpad ? d.lpad - startblock.Boffset : 0);
237                 WRITE(LandingPad);
238                 uint ActionTable = d.action;
239                 cstbuf.writeuLEB128(ActionTable);
240                 //printf("\t%x %x %x %x\n", CallSiteStart, CallSiteRange, LandingPad, ActionTable);
241         }
242     }
243 }
244 else
245 {
246     /* Build Call Site Table
247      * Be sure to not generate empty entries,
248      * and generate multiple entries for one DwEhTableEntry if the latter
249      * is split by nested DwEhTableEntry's. This is based on the (undocumented)
250      * presumption that there may not
251      * be overlapping entries in the Call Site Table.
252      */
253     assert(deh.dim);
254     uint end = deh.index(0).start;
255     for (uint i = 0; i < deh.dim; ++i)
256     {
257         uint j = i;
258         do
259         {
260             DwEhTableEntry *d = deh.index(j);
261             //printf(" [%d] start=%x end=%x lpad=%x action=%x bcatch=%p prev=%d\n",
262             //  j, d.start, d.end, d.lpad, d.action, d.bcatch, d.prev);
263             if (d.start <= end && end < d.end)
264             {
265                 uint start = end;
266                 uint dend = d.end;
267                 if (i + 1 < deh.dim)
268                 {
269                     DwEhTableEntry *dnext = deh.index(i + 1);
270                     if (dnext.start < dend)
271                         dend = dnext.start;
272                 }
273                 if (start < dend)
274                 {
275 static if (ELFOBJ)
276                     auto WRITE = &cstbuf.writeLEB128;
277 else static if (MACHOBJ)
278                     auto WRITE = &cstbuf.write32;
279 else
280                     assert(0);
281 
282                     uint CallSiteStart = start - startblock.Boffset;
283                     WRITE(CallSiteStart);
284                     uint CallSiteRange = dend - start;
285                     WRITE(CallSiteRange);
286                     uint LandingPad = d.lpad - startblock.Boffset;
287                     cstbuf.WRITE(LandingPad);
288                     uint ActionTable = d.action;
289                     WRITE(ActionTable);
290                     //printf("\t%x %x %x %x\n", CallSiteStart, CallSiteRange, LandingPad, ActionTable);
291                 }
292 
293                 end = dend;
294             }
295         } while (j--);
296     }
297 }
298 
299     /* Write LSDT header */
300     const ubyte LPstart = DW_EH_PE_omit;
301     et.writeByte(LPstart);
302     uint LPbase = 0;
303     if (LPstart != DW_EH_PE_omit)
304         et.writeuLEB128(LPbase);
305 
306     const ubyte TType = (config.flags3 & CFG3pic)
307                                 ? DW_EH_PE_indirect | DW_EH_PE_pcrel | DW_EH_PE_sdata4
308                                 : DW_EH_PE_absptr | DW_EH_PE_udata4;
309     et.writeByte(TType);
310 
311     /* Compute TTbase, which is the sum of:
312      *  1. CallSiteFormat
313      *  2. encoding of CallSiteTableSize
314      *  3. Call Site Table size
315      *  4. Action Table size
316      *  5. 4 byte alignment
317      *  6. Types Table
318      * Iterate until it converges.
319      */
320     uint TTbase = 1;
321     uint CallSiteTableSize = cast(uint)cstbuf.length();
322     uint oldTTbase;
323     do
324     {
325         oldTTbase = TTbase;
326         uint start = cast(uint)((et.length() - startsize) + uLEB128size(TTbase));
327         TTbase = cast(uint)(
328                 1 +
329                 uLEB128size(CallSiteTableSize) +
330                 CallSiteTableSize +
331                 atbuf.length());
332         uint sz = start + TTbase;
333         TTbase += -sz & 3;      // align to 4
334         TTbase += sfunc.Sfunc.typesTable.length * 4;
335     } while (TTbase != oldTTbase);
336 
337     if (TType != DW_EH_PE_omit)
338         et.writeuLEB128(TTbase);
339     uint TToffset = cast(uint)(TTbase + et.length() - startsize);
340 
341 static if (ELFOBJ)
342     const ubyte CallSiteFormat = DW_EH_PE_absptr | DW_EH_PE_uleb128;
343 else static if (MACHOBJ)
344     const ubyte CallSiteFormat = DW_EH_PE_absptr | DW_EH_PE_udata4;
345 else
346     assert(0);
347 
348     et.writeByte(CallSiteFormat);
349     et.writeuLEB128(CallSiteTableSize);
350 
351 
352     /* Insert Call Site Table */
353     et.write(cstbuf[]);
354 
355     /* Insert Action Table */
356     et.write(atbuf[]);
357 
358     /* Align to 4 */
359     for (uint n = (-et.length() & 3); n; --n)
360         et.writeByte(0);
361 
362     /* Write out Types Table in reverse */
363     auto typesTable = sfunc.Sfunc.typesTable[];
364     for (int i = cast(int)typesTable.length; i--; )
365     {
366         Symbol *s = typesTable[i];
367         /* MACHOBJ 64: pcrel 1 length 1 extern 1 RELOC_GOT
368          *         32: [0] address x004c pcrel 0 length 2 value x224 type 4 RELOC_LOCAL_SECTDIFF
369          *             [1] address x0000 pcrel 0 length 2 value x160 type 1 RELOC_PAIR
370          */
371         dwarf_reftoident(seg, et.length(), s, 0);
372     }
373     assert(TToffset == et.length() - startsize);
374 }
375 
376 
377 /****************************
378  * Insert action (ttindex, offset) in Action Table
379  * if it is not already there.
380  * Params:
381  *      atbuf = Action Table
382  *      ttindex = Types Table index (1..)
383  *      offset = offset of next action, -1 for none
384  * Returns:
385  *      offset of inserted action
386  */
387 int actionTableInsert(Outbuffer *atbuf, int ttindex, int nextoffset)
388 {
389     //printf("actionTableInsert(%d, %d)\n", ttindex, nextoffset);
390     const(ubyte)[] p = (*atbuf)[];
391     while (p.length)
392     {
393         int offset = cast(int) (atbuf.length - p.length);
394         int TypeFilter = sLEB128(p);
395         int nrpoffset = cast(int) (atbuf.length - p.length);
396         int NextRecordPtr = sLEB128(p);
397 
398         if (ttindex == TypeFilter &&
399             nextoffset == nrpoffset + NextRecordPtr)
400             return offset;
401     }
402     int offset = cast(int)atbuf.length();
403     atbuf.writesLEB128(ttindex);
404     if (nextoffset == -1)
405         nextoffset = 0;
406     else
407         nextoffset -= atbuf.length();
408     atbuf.writesLEB128(nextoffset);
409     return offset;
410 }
411 
412 debug
413 void unittest_actionTableInsert()
414 {
415     Outbuffer atbuf;
416     static immutable int[3] tt1 = [ 1,2,3 ];
417     static immutable int[1] tt2 = [ 2 ];
418 
419     int offset = -1;
420     for (size_t i = tt1.length; i--; )
421     {
422         offset = actionTableInsert(&atbuf, tt1[i], offset);
423     }
424     offset = -1;
425     for (size_t i = tt2.length; i--; )
426     {
427         offset = actionTableInsert(&atbuf, tt2[i], offset);
428     }
429 
430     static immutable ubyte[8] result = [ 3,0,2,0x7D,1,0x7D,2,0 ];
431     //for (int i = 0; i < atbuf.length(); ++i) printf(" %02x\n", atbuf.buf[i]);
432     assert(result.sizeof == atbuf.length());
433     int r = memcmp(result.ptr, atbuf.buf, atbuf.length());
434     assert(r == 0);
435 }
436 
437 
438 /**
439  * Consumes and decode an unsigned LEB128.
440  *
441  * Params:
442  *     data = reference to a slice holding the LEB128 to decode.
443  *            When this function return, the slice will point past the LEB128.
444  *
445  * Returns:
446  *      decoded value
447  *
448  * See_Also:
449  *      https://en.wikipedia.org/wiki/LEB128
450  */
451 private extern(D) uint uLEB128(ref const(ubyte)[] data)
452 {
453     const(ubyte)* q = data.ptr;
454     uint result = 0;
455     uint shift = 0;
456     while (1)
457     {
458         ubyte byte_ = *q++;
459         result |= (byte_ & 0x7F) << shift;
460         if ((byte_ & 0x80) == 0)
461             break;
462         shift += 7;
463     }
464     data = data[q - data.ptr .. $];
465     return result;
466 }
467 
468 /**
469  * Consumes and decode a signed LEB128.
470  *
471  * Params:
472  *     data = reference to a slice holding the LEB128 to decode.
473  *            When this function return, the slice will point past the LEB128.
474  *
475  * Returns:
476  *      decoded value
477  *
478  * See_Also:
479  *      https://en.wikipedia.org/wiki/LEB128
480  */
481 private extern(D) int sLEB128(ref const(ubyte)[] data)
482 {
483     const(ubyte)* q = data.ptr;
484     ubyte byte_;
485 
486     int result = 0;
487     uint shift = 0;
488     while (1)
489     {
490         byte_ = *q++;
491         result |= (byte_ & 0x7F) << shift;
492         shift += 7;
493         if ((byte_ & 0x80) == 0)
494             break;
495     }
496     if (shift < result.sizeof * 8 && (byte_ & 0x40))
497         result |= -(1 << shift);
498     data = data[q - data.ptr .. $];
499     return result;
500 }
501 
502 /******************************
503  * Determine size of Signed LEB128 encoded value.
504  * Params:
505  *      value = value to be encoded
506  * Returns:
507  *      length of decoded value
508  * See_Also:
509  *      https://en.wikipedia.org/wiki/LEB128
510  */
511 uint sLEB128size(int value)
512 {
513     uint size = 0;
514     while (1)
515     {
516         ++size;
517         ubyte b = value & 0x40;
518 
519         value >>= 7;            // arithmetic right shift
520         if (value == 0 && !b ||
521             value == -1 && b)
522         {
523              break;
524         }
525     }
526     return size;
527 }
528 
529 /******************************
530  * Determine size of Unsigned LEB128 encoded value.
531  * Params:
532  *      value = value to be encoded
533  * Returns:
534  *      length of decoded value
535  * See_Also:
536  *      https://en.wikipedia.org/wiki/LEB128
537  */
538 uint uLEB128size(uint value)
539 {
540     uint size = 1;
541     while ((value >>= 7) != 0)
542         ++size;
543     return size;
544 }
545 
546 debug
547 void unittest_LEB128()
548 {
549     Outbuffer buf;
550 
551     static immutable int[16] values =
552     [
553         0,1,2,3,300,4000,50000,600000,
554         -0,-1,-2,-3,-300,-4000,-50000,-600000,
555     ];
556 
557     for (size_t i = 0; i < values.length; ++i)
558     {
559         const int value = values[i];
560 
561         buf.reset();
562         buf.writeuLEB128(value);
563         assert(buf.length() == uLEB128size(value));
564         const(ubyte)[] p = buf[];
565         int result = uLEB128(p);
566         assert(!p.length);
567         assert(result == value);
568 
569         buf.reset();
570         buf.writesLEB128(value);
571         assert(buf.length() == sLEB128size(value));
572         p = buf[];
573         result = sLEB128(p);
574         assert(!p.length);
575         assert(result == value);
576     }
577 }
578 
579 
580 debug
581 void unittest_dwarfeh()
582 {
583     __gshared bool run = false;
584     if (run)
585         return;
586     run = true;
587 
588     unittest_LEB128();
589     unittest_actionTableInsert();
590 }
591 
592 }