From fd2c3489ad3d9761ccd9d26bc4cd09ef2b7ca40c Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Fri, 2 Feb 2007 21:10:50 +0000 Subject: [PATCH] * elf-bfd.h (struct elf_obj_tdata): Change symbuf type to void *. * elf.c (struct elf_symbuf_symbol, struct elf_symbuf_head): New types. (struct elf_symbol): Change first member into union. (elf_sort_elf_symbol): Compare pointers to internal syms rather than internal syms. Only compare st_shndx fields. (elf_create_symbuf): New function. (bfd_elf_match_symbols_in_sections): Use it. If symbufs are available for bfds, use a binary search, otherwise don't qsort symbols unnecessarily only to select which symbols are for the particular shndx. --- bfd/ChangeLog | 13 +++ bfd/elf-bfd.h | 2 +- bfd/elf.c | 310 +++++++++++++++++++++++++++++++++++++++------------------- 3 files changed, 225 insertions(+), 100 deletions(-) diff --git a/bfd/ChangeLog b/bfd/ChangeLog index e919ff3057..9d27953fbd 100644 --- a/bfd/ChangeLog +++ b/bfd/ChangeLog @@ -1,3 +1,16 @@ +2007-02-02 Jakub Jelinek + + * elf-bfd.h (struct elf_obj_tdata): Change symbuf type to void *. + * elf.c (struct elf_symbuf_symbol, struct elf_symbuf_head): New types. + (struct elf_symbol): Change first member into union. + (elf_sort_elf_symbol): Compare pointers to internal syms rather than + internal syms. Only compare st_shndx fields. + (elf_create_symbuf): New function. + (bfd_elf_match_symbols_in_sections): Use it. If symbufs are available + for bfds, use a binary search, otherwise don't qsort symbols + unnecessarily only to select which symbols are for the particular + shndx. + 2007-02-01 Nick Clifton PR ld/3852 diff --git a/bfd/elf-bfd.h b/bfd/elf-bfd.h index 3798322c89..a9d51a3598 100644 --- a/bfd/elf-bfd.h +++ b/bfd/elf-bfd.h @@ -1392,7 +1392,7 @@ struct elf_obj_tdata bfd_boolean flags_init; /* Symbol buffer. */ - Elf_Internal_Sym *symbuf; + void *symbuf; }; #define elf_tdata(bfd) ((bfd) -> tdata.elf_obj_data) diff --git a/bfd/elf.c b/bfd/elf.c index c5c8c61802..7efca9ca14 100644 --- a/bfd/elf.c +++ b/bfd/elf.c @@ -8745,39 +8745,41 @@ _bfd_elf_get_synthetic_symtab (bfd *abfd, return n; } -/* Sort symbol by binding and section. We want to put definitions - sorted by section at the beginning. */ - -static int -elf_sort_elf_symbol (const void *arg1, const void *arg2) +struct elf_symbuf_symbol { - const Elf_Internal_Sym *s1; - const Elf_Internal_Sym *s2; - int shndx; - - /* Make sure that undefined symbols are at the end. */ - s1 = (const Elf_Internal_Sym *) arg1; - if (s1->st_shndx == SHN_UNDEF) - return 1; - s2 = (const Elf_Internal_Sym *) arg2; - if (s2->st_shndx == SHN_UNDEF) - return -1; - - /* Sorted by section index. */ - shndx = s1->st_shndx - s2->st_shndx; - if (shndx != 0) - return shndx; + unsigned long st_name; /* Symbol name, index in string tbl */ + unsigned char st_info; /* Type and binding attributes */ + unsigned char st_other; /* Visibilty, and target specific */ +}; - /* Sorted by binding. */ - return ELF_ST_BIND (s1->st_info) - ELF_ST_BIND (s2->st_info); -} +struct elf_symbuf_head +{ + struct elf_symbuf_symbol *ssym; + bfd_size_type count; + unsigned int st_shndx; +}; struct elf_symbol { - Elf_Internal_Sym *sym; + union + { + Elf_Internal_Sym *isym; + struct elf_symbuf_symbol *ssym; + } u; const char *name; }; +/* Sort references to symbols by ascending section number. */ + +static int +elf_sort_elf_symbol (const void *arg1, const void *arg2) +{ + const Elf_Internal_Sym *s1 = *(const Elf_Internal_Sym **) arg1; + const Elf_Internal_Sym *s2 = *(const Elf_Internal_Sym **) arg2; + + return s1->st_shndx - s2->st_shndx; +} + static int elf_sym_name_compare (const void *arg1, const void *arg2) { @@ -8786,6 +8788,64 @@ elf_sym_name_compare (const void *arg1, const void *arg2) return strcmp (s1->name, s2->name); } +static struct elf_symbuf_head * +elf_create_symbuf (bfd_size_type symcount, Elf_Internal_Sym *isymbuf) +{ + Elf_Internal_Sym **ind, **indbufend, **indbuf + = bfd_malloc2 (symcount, sizeof (*indbuf)); + struct elf_symbuf_symbol *ssym; + struct elf_symbuf_head *ssymbuf, *ssymhead; + bfd_size_type i, shndx_count; + + if (indbuf == NULL) + return NULL; + + for (ind = indbuf, i = 0; i < symcount; i++) + if (isymbuf[i].st_shndx != SHN_UNDEF) + *ind++ = &isymbuf[i]; + indbufend = ind; + + qsort (indbuf, indbufend - indbuf, sizeof (Elf_Internal_Sym *), + elf_sort_elf_symbol); + + shndx_count = 0; + if (indbufend > indbuf) + for (ind = indbuf, shndx_count++; ind < indbufend - 1; ind++) + if (ind[0]->st_shndx != ind[1]->st_shndx) + shndx_count++; + + ssymbuf = bfd_malloc ((shndx_count + 1) * sizeof (*ssymbuf) + + (indbufend - indbuf) * sizeof (*ssymbuf)); + if (ssymbuf == NULL) + { + free (indbuf); + return NULL; + } + + ssym = (struct elf_symbuf_symbol *) (ssymbuf + shndx_count); + ssymbuf->ssym = NULL; + ssymbuf->count = shndx_count; + ssymbuf->st_shndx = 0; + for (ssymhead = ssymbuf, ind = indbuf; ind < indbufend; ssym++, ind++) + { + if (ind == indbuf || ssymhead->st_shndx != (*ind)->st_shndx) + { + ssymhead++; + ssymhead->ssym = ssym; + ssymhead->count = 0; + ssymhead->st_shndx = (*ind)->st_shndx; + } + ssym->st_name = (*ind)->st_name; + ssym->st_info = (*ind)->st_info; + ssym->st_other = (*ind)->st_other; + ssymhead->count++; + } + BFD_ASSERT ((bfd_size_type) (ssymhead - ssymbuf) == shndx_count); + + free (indbuf); + return ssymbuf; +} + /* Check if 2 sections define the same set of local and global symbols. */ @@ -8798,9 +8858,9 @@ bfd_elf_match_symbols_in_sections (asection *sec1, asection *sec2, Elf_Internal_Shdr *hdr1, *hdr2; bfd_size_type symcount1, symcount2; Elf_Internal_Sym *isymbuf1, *isymbuf2; - Elf_Internal_Sym *isymstart1 = NULL, *isymstart2 = NULL, *isym; - Elf_Internal_Sym *isymend; - struct elf_symbol *symp, *symtable1 = NULL, *symtable2 = NULL; + struct elf_symbuf_head *ssymbuf1, *ssymbuf2; + Elf_Internal_Sym *isym, *isymend; + struct elf_symbol *symtable1 = NULL, *symtable2 = NULL; bfd_size_type count1, count2, i; int shndx1, shndx2; bfd_boolean result; @@ -8848,99 +8908,154 @@ bfd_elf_match_symbols_in_sections (asection *sec1, asection *sec2, return FALSE; result = FALSE; - isymbuf1 = elf_tdata (bfd1)->symbuf; - isymbuf2 = elf_tdata (bfd2)->symbuf; + isymbuf1 = NULL; + isymbuf2 = NULL; + ssymbuf1 = elf_tdata (bfd1)->symbuf; + ssymbuf2 = elf_tdata (bfd2)->symbuf; - if (isymbuf1 == NULL) + if (ssymbuf1 == NULL) { isymbuf1 = bfd_elf_get_elf_syms (bfd1, hdr1, symcount1, 0, NULL, NULL, NULL); if (isymbuf1 == NULL) goto done; - /* Sort symbols by binding and section. Global definitions are at - the beginning. */ - qsort (isymbuf1, symcount1, sizeof (Elf_Internal_Sym), - elf_sort_elf_symbol); + if (!info->reduce_memory_overheads) - elf_tdata (bfd1)->symbuf = isymbuf1; + elf_tdata (bfd1)->symbuf = ssymbuf1 + = elf_create_symbuf (symcount1, isymbuf1); } - if (isymbuf2 == NULL) + if (ssymbuf1 == NULL || ssymbuf2 == NULL) { isymbuf2 = bfd_elf_get_elf_syms (bfd2, hdr2, symcount2, 0, NULL, NULL, NULL); if (isymbuf2 == NULL) goto done; - /* Sort symbols by binding and section. Global definitions are at - the beginning. */ - qsort (isymbuf2, symcount2, sizeof (Elf_Internal_Sym), - elf_sort_elf_symbol); - if (!info->reduce_memory_overheads) - elf_tdata (bfd2)->symbuf = isymbuf2; + + if (ssymbuf1 != NULL && !info->reduce_memory_overheads) + elf_tdata (bfd2)->symbuf = ssymbuf2 + = elf_create_symbuf (symcount2, isymbuf2); } - /* Count definitions in the section. */ - count1 = 0; - for (isym = isymbuf1, isymend = isym + symcount1; - isym < isymend; isym++) + if (ssymbuf1 != NULL && ssymbuf2 != NULL) { - if (isym->st_shndx == (unsigned int) shndx1) + /* Optimized faster version. */ + bfd_size_type lo, hi, mid; + struct elf_symbol *symp; + struct elf_symbuf_symbol *ssym, *ssymend; + + lo = 0; + hi = ssymbuf1->count; + ssymbuf1++; + count1 = 0; + while (lo < hi) { - if (count1 == 0) - isymstart1 = isym; - count1++; + mid = (lo + hi) / 2; + if ((unsigned int) shndx1 < ssymbuf1[mid].st_shndx) + hi = mid; + else if ((unsigned int) shndx1 > ssymbuf1[mid].st_shndx) + lo = mid + 1; + else + { + count1 = ssymbuf1[mid].count; + ssymbuf1 += mid; + break; + } } - if (count1 && isym->st_shndx != (unsigned int) shndx1) - break; - } + lo = 0; + hi = ssymbuf2->count; + ssymbuf2++; + count2 = 0; + while (lo < hi) + { + mid = (lo + hi) / 2; + if ((unsigned int) shndx2 < ssymbuf2[mid].st_shndx) + hi = mid; + else if ((unsigned int) shndx2 > ssymbuf2[mid].st_shndx) + lo = mid + 1; + else + { + count2 = ssymbuf2[mid].count; + ssymbuf2 += mid; + break; + } + } - count2 = 0; - for (isym = isymbuf2, isymend = isym + symcount2; - isym < isymend; isym++) - { - if (isym->st_shndx == (unsigned int) shndx2) + if (count1 == 0 || count2 == 0 || count1 != count2) + goto done; + + symtable1 = bfd_malloc (count1 * sizeof (struct elf_symbol)); + symtable2 = bfd_malloc (count2 * sizeof (struct elf_symbol)); + if (symtable1 == NULL || symtable2 == NULL) + goto done; + + symp = symtable1; + for (ssym = ssymbuf1->ssym, ssymend = ssym + count1; + ssym < ssymend; ssym++, symp++) { - if (count2 == 0) - isymstart2 = isym; - count2++; + symp->u.ssym = ssym; + symp->name = bfd_elf_string_from_elf_section (bfd1, + hdr1->sh_link, + ssym->st_name); } - if (count2 && isym->st_shndx != (unsigned int) shndx2) - break; + symp = symtable2; + for (ssym = ssymbuf2->ssym, ssymend = ssym + count2; + ssym < ssymend; ssym++, symp++) + { + symp->u.ssym = ssym; + symp->name = bfd_elf_string_from_elf_section (bfd2, + hdr2->sh_link, + ssym->st_name); + } + + /* Sort symbol by name. */ + qsort (symtable1, count1, sizeof (struct elf_symbol), + elf_sym_name_compare); + qsort (symtable2, count1, sizeof (struct elf_symbol), + elf_sym_name_compare); + + for (i = 0; i < count1; i++) + /* Two symbols must have the same binding, type and name. */ + if (symtable1 [i].u.ssym->st_info != symtable2 [i].u.ssym->st_info + || symtable1 [i].u.ssym->st_other != symtable2 [i].u.ssym->st_other + || strcmp (symtable1 [i].name, symtable2 [i].name) != 0) + goto done; + + result = TRUE; + goto done; } - if (count1 == 0 || count2 == 0 || count1 != count2) + symtable1 = bfd_malloc (symcount1 * sizeof (struct elf_symbol)); + symtable2 = bfd_malloc (symcount2 * sizeof (struct elf_symbol)); + if (symtable1 == NULL || symtable2 == NULL) goto done; - symtable1 = bfd_malloc (count1 * sizeof (struct elf_symbol)); - symtable2 = bfd_malloc (count1 * sizeof (struct elf_symbol)); + /* Count definitions in the section. */ + count1 = 0; + for (isym = isymbuf1, isymend = isym + symcount1; isym < isymend; isym++) + if (isym->st_shndx == (unsigned int) shndx1) + symtable1[count1++].u.isym = isym; - if (symtable1 == NULL || symtable2 == NULL) + count2 = 0; + for (isym = isymbuf2, isymend = isym + symcount2; isym < isymend; isym++) + if (isym->st_shndx == (unsigned int) shndx2) + symtable2[count2++].u.isym = isym; + + if (count1 == 0 || count2 == 0 || count1 != count2) goto done; - symp = symtable1; - for (isym = isymstart1, isymend = isym + count1; - isym < isymend; isym++) - { - symp->sym = isym; - symp->name = bfd_elf_string_from_elf_section (bfd1, - hdr1->sh_link, - isym->st_name); - symp++; - } - - symp = symtable2; - for (isym = isymstart2, isymend = isym + count1; - isym < isymend; isym++) - { - symp->sym = isym; - symp->name = bfd_elf_string_from_elf_section (bfd2, - hdr2->sh_link, - isym->st_name); - symp++; - } - + for (i = 0; i < count1; i++) + symtable1[i].name + = bfd_elf_string_from_elf_section (bfd1, hdr1->sh_link, + symtable1[i].u.isym->st_name); + + for (i = 0; i < count2; i++) + symtable2[i].name + = bfd_elf_string_from_elf_section (bfd2, hdr2->sh_link, + symtable2[i].u.isym->st_name); + /* Sort symbol by name. */ qsort (symtable1, count1, sizeof (struct elf_symbol), elf_sym_name_compare); @@ -8949,8 +9064,8 @@ bfd_elf_match_symbols_in_sections (asection *sec1, asection *sec2, for (i = 0; i < count1; i++) /* Two symbols must have the same binding, type and name. */ - if (symtable1 [i].sym->st_info != symtable2 [i].sym->st_info - || symtable1 [i].sym->st_other != symtable2 [i].sym->st_other + if (symtable1 [i].u.isym->st_info != symtable2 [i].u.isym->st_info + || symtable1 [i].u.isym->st_other != symtable2 [i].u.isym->st_other || strcmp (symtable1 [i].name, symtable2 [i].name) != 0) goto done; @@ -8961,13 +9076,10 @@ done: free (symtable1); if (symtable2) free (symtable2); - if (info->reduce_memory_overheads) - { - if (isymbuf1) - free (isymbuf1); - if (isymbuf2) - free (isymbuf2); - } + if (isymbuf1) + free (isymbuf1); + if (isymbuf2) + free (isymbuf2); return result; } -- 2.11.0