aboutsummaryrefslogtreecommitdiffstats
path: root/kernel
diff options
context:
space:
mode:
authorJan Beulich <jbeulich@novell.com>2006-10-21 12:37:01 -0400
committerAndi Kleen <andi@basil.nowhere.org>2006-10-21 12:37:01 -0400
commit690a973f48b6ba2954465992c08e65059c8374fe (patch)
treeb30a59496628592233944b3f4340cdfdf9d3d5de /kernel
parentcdfce1f5714fec7b24715f569b2fee1607350a6d (diff)
[PATCH] x86-64: Speed up dwarf2 unwinder
This changes the dwarf2 unwinder to do a binary search for CIEs instead of a linear work. The linker is unfortunately not able to build a proper lookup table at link time, instead it creates one at runtime as soon as the bootmem allocator is usable (so you'll continue using the linear lookup for the first [hopefully] few calls). The code should be ready to utilize a build-time created table once a fixed linker becomes available. Signed-off-by: Jan Beulich <jbeulich@novell.com> Signed-off-by: Andi Kleen <ak@suse.de>
Diffstat (limited to 'kernel')
-rw-r--r--kernel/unwind.c318
1 files changed, 279 insertions, 39 deletions
diff --git a/kernel/unwind.c b/kernel/unwind.c
index 2e2368607aab..f7e50d16dbf6 100644
--- a/kernel/unwind.c
+++ b/kernel/unwind.c
@@ -11,13 +11,15 @@
11 11
12#include <linux/unwind.h> 12#include <linux/unwind.h>
13#include <linux/module.h> 13#include <linux/module.h>
14#include <linux/delay.h> 14#include <linux/bootmem.h>
15#include <linux/sort.h>
15#include <linux/stop_machine.h> 16#include <linux/stop_machine.h>
16#include <asm/sections.h> 17#include <asm/sections.h>
17#include <asm/uaccess.h> 18#include <asm/uaccess.h>
18#include <asm/unaligned.h> 19#include <asm/unaligned.h>
19 20
20extern char __start_unwind[], __end_unwind[]; 21extern char __start_unwind[], __end_unwind[];
22extern const u8 __start_unwind_hdr[], __end_unwind_hdr[];
21 23
22#define MAX_STACK_DEPTH 8 24#define MAX_STACK_DEPTH 8
23 25
@@ -100,6 +102,8 @@ static struct unwind_table {
100 } core, init; 102 } core, init;
101 const void *address; 103 const void *address;
102 unsigned long size; 104 unsigned long size;
105 const unsigned char *header;
106 unsigned long hdrsz;
103 struct unwind_table *link; 107 struct unwind_table *link;
104 const char *name; 108 const char *name;
105} root_table; 109} root_table;
@@ -145,6 +149,10 @@ static struct unwind_table *find_table(unsigned long pc)
145 return table; 149 return table;
146} 150}
147 151
152static unsigned long read_pointer(const u8 **pLoc,
153 const void *end,
154 signed ptrType);
155
148static void init_unwind_table(struct unwind_table *table, 156static void init_unwind_table(struct unwind_table *table,
149 const char *name, 157 const char *name,
150 const void *core_start, 158 const void *core_start,
@@ -152,14 +160,30 @@ static void init_unwind_table(struct unwind_table *table,
152 const void *init_start, 160 const void *init_start,
153 unsigned long init_size, 161 unsigned long init_size,
154 const void *table_start, 162 const void *table_start,
155 unsigned long table_size) 163 unsigned long table_size,
164 const u8 *header_start,
165 unsigned long header_size)
156{ 166{
167 const u8 *ptr = header_start + 4;
168 const u8 *end = header_start + header_size;
169
157 table->core.pc = (unsigned long)core_start; 170 table->core.pc = (unsigned long)core_start;
158 table->core.range = core_size; 171 table->core.range = core_size;
159 table->init.pc = (unsigned long)init_start; 172 table->init.pc = (unsigned long)init_start;
160 table->init.range = init_size; 173 table->init.range = init_size;
161 table->address = table_start; 174 table->address = table_start;
162 table->size = table_size; 175 table->size = table_size;
176 /* See if the linker provided table looks valid. */
177 if (header_size <= 4
178 || header_start[0] != 1
179 || (void *)read_pointer(&ptr, end, header_start[1]) != table_start
180 || header_start[2] == DW_EH_PE_omit
181 || read_pointer(&ptr, end, header_start[2]) <= 0
182 || header_start[3] == DW_EH_PE_omit)
183 header_start = NULL;
184 table->hdrsz = header_size;
185 smp_wmb();
186 table->header = header_start;
163 table->link = NULL; 187 table->link = NULL;
164 table->name = name; 188 table->name = name;
165} 189}
@@ -169,7 +193,143 @@ void __init unwind_init(void)
169 init_unwind_table(&root_table, "kernel", 193 init_unwind_table(&root_table, "kernel",
170 _text, _end - _text, 194 _text, _end - _text,
171 NULL, 0, 195 NULL, 0,
172 __start_unwind, __end_unwind - __start_unwind); 196 __start_unwind, __end_unwind - __start_unwind,
197 __start_unwind_hdr, __end_unwind_hdr - __start_unwind_hdr);
198}
199
200static const u32 bad_cie, not_fde;
201static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *);
202static signed fde_pointer_type(const u32 *cie);
203
204struct eh_frame_hdr_table_entry {
205 unsigned long start, fde;
206};
207
208static int cmp_eh_frame_hdr_table_entries(const void *p1, const void *p2)
209{
210 const struct eh_frame_hdr_table_entry *e1 = p1;
211 const struct eh_frame_hdr_table_entry *e2 = p2;
212
213 return (e1->start > e2->start) - (e1->start < e2->start);
214}
215
216static void swap_eh_frame_hdr_table_entries(void *p1, void *p2, int size)
217{
218 struct eh_frame_hdr_table_entry *e1 = p1;
219 struct eh_frame_hdr_table_entry *e2 = p2;
220 unsigned long v;
221
222 v = e1->start;
223 e1->start = e2->start;
224 e2->start = v;
225 v = e1->fde;
226 e1->fde = e2->fde;
227 e2->fde = v;
228}
229
230static void __init setup_unwind_table(struct unwind_table *table,
231 void *(*alloc)(unsigned long))
232{
233 const u8 *ptr;
234 unsigned long tableSize = table->size, hdrSize;
235 unsigned n;
236 const u32 *fde;
237 struct {
238 u8 version;
239 u8 eh_frame_ptr_enc;
240 u8 fde_count_enc;
241 u8 table_enc;
242 unsigned long eh_frame_ptr;
243 unsigned int fde_count;
244 struct eh_frame_hdr_table_entry table[];
245 } __attribute__((__packed__)) *header;
246
247 if (table->header)
248 return;
249
250 if (table->hdrsz)
251 printk(KERN_WARNING ".eh_frame_hdr for '%s' present but unusable\n",
252 table->name);
253
254 if (tableSize & (sizeof(*fde) - 1))
255 return;
256
257 for (fde = table->address, n = 0;
258 tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde;
259 tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
260 const u32 *cie = cie_for_fde(fde, table);
261 signed ptrType;
262
263 if (cie == &not_fde)
264 continue;
265 if (cie == NULL
266 || cie == &bad_cie
267 || (ptrType = fde_pointer_type(cie)) < 0)
268 return;
269 ptr = (const u8 *)(fde + 2);
270 if (!read_pointer(&ptr,
271 (const u8 *)(fde + 1) + *fde,
272 ptrType))
273 return;
274 ++n;
275 }
276
277 if (tableSize || !n)
278 return;
279
280 hdrSize = 4 + sizeof(unsigned long) + sizeof(unsigned int)
281 + 2 * n * sizeof(unsigned long);
282 header = alloc(hdrSize);
283 if (!header)
284 return;
285 header->version = 1;
286 header->eh_frame_ptr_enc = DW_EH_PE_abs|DW_EH_PE_native;
287 header->fde_count_enc = DW_EH_PE_abs|DW_EH_PE_data4;
288 header->table_enc = DW_EH_PE_abs|DW_EH_PE_native;
289 put_unaligned((unsigned long)table->address, &header->eh_frame_ptr);
290 BUILD_BUG_ON(offsetof(typeof(*header), fde_count)
291 % __alignof(typeof(header->fde_count)));
292 header->fde_count = n;
293
294 BUILD_BUG_ON(offsetof(typeof(*header), table)
295 % __alignof(typeof(*header->table)));
296 for (fde = table->address, tableSize = table->size, n = 0;
297 tableSize;
298 tableSize -= sizeof(*fde) + *fde, fde += 1 + *fde / sizeof(*fde)) {
299 const u32 *cie = fde + 1 - fde[1] / sizeof(*fde);
300
301 if (!fde[1])
302 continue; /* this is a CIE */
303 ptr = (const u8 *)(fde + 2);
304 header->table[n].start = read_pointer(&ptr,
305 (const u8 *)(fde + 1) + *fde,
306 fde_pointer_type(cie));
307 header->table[n].fde = (unsigned long)fde;
308 ++n;
309 }
310 WARN_ON(n != header->fde_count);
311
312 sort(header->table,
313 n,
314 sizeof(*header->table),
315 cmp_eh_frame_hdr_table_entries,
316 swap_eh_frame_hdr_table_entries);
317
318 table->hdrsz = hdrSize;
319 smp_wmb();
320 table->header = (const void *)header;
321}
322
323static void *__init balloc(unsigned long sz)
324{
325 return __alloc_bootmem_nopanic(sz,
326 sizeof(unsigned int),
327 __pa(MAX_DMA_ADDRESS));
328}
329
330void __init unwind_setup(void)
331{
332 setup_unwind_table(&root_table, balloc);
173} 333}
174 334
175#ifdef CONFIG_MODULES 335#ifdef CONFIG_MODULES
@@ -193,7 +353,8 @@ void *unwind_add_table(struct module *module,
193 init_unwind_table(table, module->name, 353 init_unwind_table(table, module->name,
194 module->module_core, module->core_size, 354 module->module_core, module->core_size,
195 module->module_init, module->init_size, 355 module->module_init, module->init_size,
196 table_start, table_size); 356 table_start, table_size,
357 NULL, 0);
197 358
198 if (last_table) 359 if (last_table)
199 last_table->link = table; 360 last_table->link = table;
@@ -303,6 +464,26 @@ static sleb128_t get_sleb128(const u8 **pcur, const u8 *end)
303 return value; 464 return value;
304} 465}
305 466
467static const u32 *cie_for_fde(const u32 *fde, const struct unwind_table *table)
468{
469 const u32 *cie;
470
471 if (!*fde || (*fde & (sizeof(*fde) - 1)))
472 return &bad_cie;
473 if (!fde[1])
474 return &not_fde; /* this is a CIE */
475 if ((fde[1] & (sizeof(*fde) - 1))
476 || fde[1] > (unsigned long)(fde + 1) - (unsigned long)table->address)
477 return NULL; /* this is not a valid FDE */
478 cie = fde + 1 - fde[1] / sizeof(*fde);
479 if (*cie <= sizeof(*cie) + 4
480 || *cie >= fde[1] - sizeof(*fde)
481 || (*cie & (sizeof(*cie) - 1))
482 || cie[1])
483 return NULL; /* this is not a (valid) CIE */
484 return cie;
485}
486
306static unsigned long read_pointer(const u8 **pLoc, 487static unsigned long read_pointer(const u8 **pLoc,
307 const void *end, 488 const void *end,
308 signed ptrType) 489 signed ptrType)
@@ -610,49 +791,108 @@ int unwind(struct unwind_frame_info *frame)
610 unsigned i; 791 unsigned i;
611 signed ptrType = -1; 792 signed ptrType = -1;
612 uleb128_t retAddrReg = 0; 793 uleb128_t retAddrReg = 0;
613 struct unwind_table *table; 794 const struct unwind_table *table;
614 struct unwind_state state; 795 struct unwind_state state;
615 796
616 if (UNW_PC(frame) == 0) 797 if (UNW_PC(frame) == 0)
617 return -EINVAL; 798 return -EINVAL;
618 if ((table = find_table(pc)) != NULL 799 if ((table = find_table(pc)) != NULL
619 && !(table->size & (sizeof(*fde) - 1))) { 800 && !(table->size & (sizeof(*fde) - 1))) {
620 unsigned long tableSize = table->size; 801 const u8 *hdr = table->header;
621 802 unsigned long tableSize;
622 for (fde = table->address; 803
623 tableSize > sizeof(*fde) && tableSize - sizeof(*fde) >= *fde; 804 smp_rmb();
624 tableSize -= sizeof(*fde) + *fde, 805 if (hdr && hdr[0] == 1) {
625 fde += 1 + *fde / sizeof(*fde)) { 806 switch(hdr[3] & DW_EH_PE_FORM) {
626 if (!*fde || (*fde & (sizeof(*fde) - 1))) 807 case DW_EH_PE_native: tableSize = sizeof(unsigned long); break;
627 break; 808 case DW_EH_PE_data2: tableSize = 2; break;
628 if (!fde[1]) 809 case DW_EH_PE_data4: tableSize = 4; break;
629 continue; /* this is a CIE */ 810 case DW_EH_PE_data8: tableSize = 8; break;
630 if ((fde[1] & (sizeof(*fde) - 1)) 811 default: tableSize = 0; break;
631 || fde[1] > (unsigned long)(fde + 1) 812 }
632 - (unsigned long)table->address) 813 ptr = hdr + 4;
633 continue; /* this is not a valid FDE */ 814 end = hdr + table->hdrsz;
634 cie = fde + 1 - fde[1] / sizeof(*fde); 815 if (tableSize
635 if (*cie <= sizeof(*cie) + 4 816 && read_pointer(&ptr, end, hdr[1])
636 || *cie >= fde[1] - sizeof(*fde) 817 == (unsigned long)table->address
637 || (*cie & (sizeof(*cie) - 1)) 818 && (i = read_pointer(&ptr, end, hdr[2])) > 0
638 || cie[1] 819 && i == (end - ptr) / (2 * tableSize)
639 || (ptrType = fde_pointer_type(cie)) < 0) { 820 && !((end - ptr) % (2 * tableSize))) {
640 cie = NULL; /* this is not a (valid) CIE */ 821 do {
641 continue; 822 const u8 *cur = ptr + (i / 2) * (2 * tableSize);
823
824 startLoc = read_pointer(&cur,
825 cur + tableSize,
826 hdr[3]);
827 if (pc < startLoc)
828 i /= 2;
829 else {
830 ptr = cur - tableSize;
831 i = (i + 1) / 2;
832 }
833 } while (startLoc && i > 1);
834 if (i == 1
835 && (startLoc = read_pointer(&ptr,
836 ptr + tableSize,
837 hdr[3])) != 0
838 && pc >= startLoc)
839 fde = (void *)read_pointer(&ptr,
840 ptr + tableSize,
841 hdr[3]);
642 } 842 }
843 }
844
845 if (fde != NULL) {
846 cie = cie_for_fde(fde, table);
643 ptr = (const u8 *)(fde + 2); 847 ptr = (const u8 *)(fde + 2);
644 startLoc = read_pointer(&ptr, 848 if(cie != NULL
645 (const u8 *)(fde + 1) + *fde, 849 && cie != &bad_cie
646 ptrType); 850 && cie != &not_fde
647 endLoc = startLoc 851 && (ptrType = fde_pointer_type(cie)) >= 0
648 + read_pointer(&ptr, 852 && read_pointer(&ptr,
649 (const u8 *)(fde + 1) + *fde, 853 (const u8 *)(fde + 1) + *fde,
650 ptrType & DW_EH_PE_indirect 854 ptrType) == startLoc) {
651 ? ptrType 855 if (!(ptrType & DW_EH_PE_indirect))
652 : ptrType & (DW_EH_PE_FORM|DW_EH_PE_signed)); 856 ptrType &= DW_EH_PE_FORM|DW_EH_PE_signed;
653 if (pc >= startLoc && pc < endLoc) 857 endLoc = startLoc
654 break; 858 + read_pointer(&ptr,
655 cie = NULL; 859 (const u8 *)(fde + 1) + *fde,
860 ptrType);
861 if(pc >= endLoc)
862 fde = NULL;
863 } else
864 fde = NULL;
865 }
866 if (fde == NULL) {
867 for (fde = table->address, tableSize = table->size;
868 cie = NULL, tableSize > sizeof(*fde)
869 && tableSize - sizeof(*fde) >= *fde;
870 tableSize -= sizeof(*fde) + *fde,
871 fde += 1 + *fde / sizeof(*fde)) {
872 cie = cie_for_fde(fde, table);
873 if (cie == &bad_cie) {
874 cie = NULL;
875 break;
876 }
877 if (cie == NULL
878 || cie == &not_fde
879 || (ptrType = fde_pointer_type(cie)) < 0)
880 continue;
881 ptr = (const u8 *)(fde + 2);
882 startLoc = read_pointer(&ptr,
883 (const u8 *)(fde + 1) + *fde,
884 ptrType);
885 if (!startLoc)
886 continue;
887 if (!(ptrType & DW_EH_PE_indirect))
888 ptrType &= DW_EH_PE_FORM|DW_EH_PE_signed;
889 endLoc = startLoc
890 + read_pointer(&ptr,
891 (const u8 *)(fde + 1) + *fde,
892 ptrType);
893 if (pc >= startLoc && pc < endLoc)
894 break;
895 }
656 } 896 }
657 } 897 }
658 if (cie != NULL) { 898 if (cie != NULL) {