add a thp-based huge page alloc fallback
[pcsx_rearmed.git] / deps / lightning / lib / jit_note.c
1 /*
2  * Copyright (C) 2013-2023  Free Software Foundation, Inc.
3  *
4  * This file is part of GNU lightning.
5  *
6  * GNU lightning is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License as published
8  * by the Free Software Foundation; either version 3, or (at your option)
9  * any later version.
10  *
11  * GNU lightning is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
14  * License for more details.
15  *
16  * Authors:
17  *      Paulo Cesar Pereira de Andrade
18  */
19
20 #include <lightning.h>
21 #include <lightning/jit_private.h>
22
23 /*
24  * Prototypes
25  */
26 #define new_note(u, v)          _new_note(_jit, u, v)
27 static jit_note_t *_new_note(jit_state_t *, jit_uint8_t*, char*);
28 static void new_line(jit_int32_t,jit_note_t*,char*,jit_int32_t,jit_int32_t);
29 #define note_search_index(u)    _note_search_index(_jit, u)
30 static jit_int32_t _note_search_index(jit_state_t*, jit_uint8_t*);
31 static jit_int32_t line_insert_index(jit_note_t*,jit_int32_t);
32 static jit_int32_t line_search_index(jit_note_t*,jit_int32_t);
33 static jit_int32_t offset_insert_index(jit_line_t*,jit_int32_t);
34 static jit_int32_t offset_search_index(jit_line_t*,jit_int32_t);
35
36 /*
37  * Implementation
38  */
39 void
40 jit_init_note(void)
41 {
42 }
43
44 void
45 jit_finish_note(void)
46 {
47 }
48
49 jit_node_t *
50 _jit_name(jit_state_t *_jit, const char *name)
51 {
52     jit_node_t          *node;
53
54     node = jit_new_node(jit_code_name);
55     if (name)
56         node->v.n = jit_data(name, strlen(name) + 1, 1);
57     else
58         node->v.p = NULL;
59     if (_jitc->note.head == NULL)
60         _jitc->note.head = _jitc->note.tail = node;
61     else {
62         _jitc->note.tail->link = node;
63         _jitc->note.tail = node;
64     }
65     ++_jit->note.length;
66     _jitc->note.size += sizeof(jit_note_t);
67     /* remember previous note is invalid due to name change */
68     _jitc->note.note = NULL;
69     return (_jitc->note.name = node);
70 }
71
72 jit_node_t *
73 _jit_note(jit_state_t *_jit, const char *name, int line)
74 {
75     jit_node_t          *node;
76
77     node = jit_new_node(jit_code_note);
78     if (name)
79         node->v.n = jit_data(name, strlen(name) + 1, 1);
80     else
81         node->v.p = NULL;
82     node->w.w = line;
83     if (_jitc->note.head == NULL)
84         _jitc->note.head = _jitc->note.tail = node;
85     else {
86         _jitc->note.tail->link = node;
87         _jitc->note.tail = node;
88     }
89     if (_jitc->note.note == NULL ||
90         (name == NULL && _jitc->note.note != NULL) ||
91         (name != NULL && _jitc->note.note == NULL) ||
92         (name != NULL && _jitc->note.note != NULL &&
93          strcmp(name, (char *)_jitc->data.ptr + _jitc->note.note->v.n->u.w)))
94         _jitc->note.size += sizeof(jit_line_t);
95     _jitc->note.size += sizeof(jit_int32_t) * 2;
96     return (_jitc->note.note = node);
97 }
98
99 void
100 _jit_annotate(jit_state_t *_jit)
101 {
102     jit_node_t          *node;
103     jit_note_t          *note;
104     jit_line_t          *line;
105     jit_word_t           length;
106     jit_word_t           note_offset;
107     jit_word_t           line_offset;
108
109     /* initialize pointers in mmaped data area */
110     _jit->note.ptr = (jit_note_t *)_jitc->note.base;
111     _jit->note.length = 0;
112
113     note = NULL;
114     for (node = _jitc->note.head; node; node = node->link) {
115         if (node->code == jit_code_name)
116             note = new_note(node->u.p, node->v.p ? node->v.n->u.p : NULL);
117         else if (node->v.p) {
118             if (note == NULL)
119                 note = new_note(node->u.p, NULL);
120             jit_set_note(note, node->v.n->u.p, node->w.w,
121                          (jit_uint8_t *)node->u.p - note->code);
122         }
123     }
124     /* last note */
125     if (note)
126         note->size = _jit->pc.uc - note->code;
127
128     /* annotations may be very complex with conditions to extend
129      * or ignore redundant notes, as well as add entries to earlier
130      * notes, so, relocate the information to the data buffer,
131      * with likely over allocated reserved space */
132
133     /* relocate jit_line_t objects */
134     for (note_offset = 0; note_offset < _jit->note.length; note_offset++) {
135         note = _jit->note.ptr + note_offset;
136         if ((length = sizeof(jit_line_t) * note->length) == 0)
137             continue;
138         assert(_jitc->note.base + length <= _jit->data.ptr + _jit->data.length);
139         jit_memcpy(_jitc->note.base, note->lines, length);
140         jit_free((jit_pointer_t *)&note->lines);
141         note->lines = (jit_line_t *)_jitc->note.base;
142         _jitc->note.base += length;
143     }
144
145     /* relocate offset and line number information */
146     for (note_offset = 0; note_offset < _jit->note.length; note_offset++) {
147         note = _jit->note.ptr + note_offset;
148         for (line_offset = 0; line_offset < note->length; line_offset++) {
149             line = note->lines + line_offset;
150             length = sizeof(jit_int32_t) * line->length;
151             assert(_jitc->note.base + length <=
152                    _jit->data.ptr + _jit->data.length);
153             jit_memcpy(_jitc->note.base, line->linenos, length);
154             jit_free((jit_pointer_t *)&line->linenos);
155             line->linenos = (jit_int32_t *)_jitc->note.base;
156             _jitc->note.base += length;
157             assert(_jitc->note.base + length <=
158                    _jit->data.ptr + _jit->data.length);
159             jit_memcpy(_jitc->note.base, line->offsets, length);
160             jit_free((jit_pointer_t *)&line->offsets);
161             line->offsets = (jit_int32_t *)_jitc->note.base;
162             _jitc->note.base += length;
163         }
164     }
165 }
166
167 void
168 _jit_set_note(jit_state_t *_jit, jit_note_t *note,
169               char *file, int lineno, jit_int32_t offset)
170 {
171     jit_line_t          *line;
172     jit_int32_t          index;
173
174     index = line_insert_index(note, offset);
175     if (note->length && index == note->length &&
176         note->lines[index - 1].file == file)
177         --index;
178     if (index >= note->length || note->lines[index].file != file)
179         new_line(index, note, file, lineno, offset);
180     else {
181         line = note->lines + index;
182         index = offset_insert_index(line, offset);
183         if (index < line->length && line->offsets[index] == offset) {
184             /* common case if no code was generated for several source lines */
185             if (line->linenos[index] < lineno)
186                 line->linenos[index] = lineno;
187         }
188         else if (index < line->length && line->linenos[index] == lineno) {
189             /* common case of extending entry */
190             if (line->offsets[index] > offset)
191                 line->offsets[index] = offset;
192         }
193         else {
194             /* line or offset changed */
195             if ((line->length & 15) == 0) {
196                 jit_realloc((jit_pointer_t *)&line->linenos,
197                             line->length * sizeof(jit_int32_t),
198                             (line->length + 17) * sizeof(jit_int32_t));
199                 jit_realloc((jit_pointer_t *)&line->offsets,
200                             line->length * sizeof(jit_int32_t),
201                             (line->length + 17) * sizeof(jit_int32_t));
202             }
203             if (index < note->length) {
204                 jit_memmove(line->linenos + index + 1, line->linenos + index,
205                             sizeof(jit_int32_t) * (line->length - index));
206                 jit_memmove(line->offsets + index + 1, line->offsets + index,
207                             sizeof(jit_int32_t) * (line->length - index));
208             }
209             line->linenos[index] = lineno;
210             line->offsets[index] = offset;
211             ++line->length;
212         }
213     }
214 }
215
216 jit_bool_t
217 _jit_get_note(jit_state_t *_jit, jit_pointer_t code,
218               char **name, char **file, jit_int32_t *lineno)
219 {
220     jit_note_t          *note;
221     jit_line_t          *line;
222     jit_int32_t          index;
223     jit_int32_t          offset;
224
225     if ((index = note_search_index((jit_uint8_t *)code)) >= _jit->note.length)
226         return (0);
227     note = _jit->note.ptr + index;
228     if ((jit_uint8_t *)code < note->code ||
229         (jit_uint8_t *)code >= note->code + note->size)
230         return (0);
231     offset = (jit_uint8_t *)code - note->code;
232     if ((index = line_search_index(note, offset)) >= note->length)
233         return (0);
234     if (index == 0 && offset < note->lines[0].offsets[0])
235         return (0);
236     line = note->lines + index;
237     if ((index = offset_search_index(line, offset)) >= line->length)
238         return (0);
239
240     if (name)
241         *name = note->name;
242     if (file)
243         *file = line->file;
244     if (lineno)
245         *lineno = line->linenos[index];
246
247     return (1);
248 }
249
250 static jit_note_t *
251 _new_note(jit_state_t *_jit, jit_uint8_t *code, char *name)
252 {
253     jit_note_t          *note;
254     jit_note_t          *prev;
255
256     if (_jit->note.length) {
257         prev = _jit->note.ptr + _jit->note.length - 1;
258         assert(code >= prev->code);
259         prev->size = code - prev->code;
260     }
261     note = (jit_note_t *)_jitc->note.base;
262     _jitc->note.base += sizeof(jit_note_t);
263     ++_jit->note.length;
264     note->code = code;
265     note->name = name;
266
267     return (note);
268 }
269
270 static void
271 new_line(jit_int32_t index, jit_note_t *note,
272           char *file, jit_int32_t lineno, jit_int32_t offset)
273 {
274     jit_line_t          *line;
275
276     if (note->lines == NULL)
277         jit_alloc((jit_pointer_t *)&note->lines, 16 * sizeof(jit_line_t));
278     else if ((note->length & 15) == 15)
279         jit_realloc((jit_pointer_t *)&note->lines,
280                     note->length * sizeof(jit_line_t),
281                     (note->length + 17) * sizeof(jit_line_t));
282
283     if (index < note->length)
284         jit_memmove(note->lines + index + 1, note->lines + index,
285                     sizeof(jit_line_t) * (note->length - index));
286     line = note->lines + index;
287     ++note->length;
288
289     line->file = file;
290     line->length = 1;
291     jit_alloc((jit_pointer_t *)&line->linenos, 16 * sizeof(jit_int32_t));
292     line->linenos[0] = lineno;
293     jit_alloc((jit_pointer_t *)&line->offsets, 16 * sizeof(jit_int32_t));
294     line->offsets[0] = offset;
295 }
296
297 static jit_int32_t
298 _note_search_index(jit_state_t *_jit, jit_uint8_t *code)
299 {
300     jit_int32_t          bot;
301     jit_int32_t          top;
302     jit_int32_t          index;
303     jit_note_t          *notes;
304
305     bot = 0;
306     top = _jit->note.length;
307     notes = _jit->note.ptr;
308     for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
309         if (code < notes[index].code)
310             top = index;
311         else if (code >= notes[index].code &&
312                  code - notes[index].code < notes[index].size)
313             break;
314         else
315             bot = index + 1;
316     }
317
318     return (index);
319 }
320
321 static jit_int32_t
322 line_insert_index(jit_note_t *note, jit_int32_t offset)
323 {
324     jit_int32_t          bot;
325     jit_int32_t          top;
326     jit_int32_t          index;
327     jit_line_t          *lines;
328
329     bot = 0;
330     top = note->length;
331     if ((lines = note->lines) == NULL)
332         return (0);
333     for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
334         if (offset < *lines[index].offsets)
335             top = index;
336         else
337             bot = index + 1;
338     }
339
340     return ((bot + top) >> 1);
341 }
342
343 static jit_int32_t
344 line_search_index(jit_note_t *note, jit_int32_t offset)
345 {
346     jit_int32_t          bot;
347     jit_int32_t          top;
348     jit_int32_t          index;
349     jit_line_t          *lines;
350
351     bot = 0;
352     top = note->length;
353     if ((lines = note->lines) == NULL)
354         return (0);
355     for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
356         if (offset < *lines[index].offsets)
357             top = index;
358         /* offset should be already verified to be in range */
359         else if (index == note->length - 1 ||
360                  (offset >= *lines[index].offsets &&
361                   offset < *lines[index + 1].offsets))
362             break;
363         else
364             bot = index + 1;
365     }
366
367     return (index);
368 }
369
370 static jit_int32_t
371 offset_insert_index(jit_line_t *line, jit_int32_t offset)
372 {
373     jit_int32_t          bot;
374     jit_int32_t          top;
375     jit_int32_t          index;
376     jit_int32_t         *offsets;
377
378     bot = 0;
379     top = line->length;
380     offsets = line->offsets;
381     for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
382         if (offset < offsets[index])
383             top = index;
384         else
385             bot = index + 1;
386     }
387
388     return ((bot + top) >> 1);
389 }
390
391 static jit_int32_t
392 offset_search_index(jit_line_t *line, jit_int32_t offset)
393 {
394     jit_int32_t          bot;
395     jit_int32_t          top;
396     jit_int32_t          index;
397     jit_int32_t         *offsets;
398
399     bot = 0;
400     top = line->length;
401     offsets = line->offsets;
402     for (index = (bot + top) >> 1; bot < top; index = (bot + top) >> 1) {
403         if (offset < offsets[index])
404             top = index;
405         /* offset should be already verified to be in range */
406         else if (index == line->length - 1 ||
407                  (offset >= offsets[index] && offset < offsets[index + 1]))
408             break;
409         else
410             bot = index + 1;
411     }
412
413     return (index);
414 }