Author: markj Date: Tue Jun 4 18:26:29 2019 New Revision: 348652 URL: https://svnweb.freebsd.org/changeset/base/348652
Log: libelf: Use a red-black tree to manage the section list. The tree is indexed by section number. This speeds up elf_getscn() and its callers, which previously had to traverse a linked list. In particular, since .shstrtab is often the last section in a file, elf_strptr() would have to traverse the entire list. PR: 234949 Reviewed by: emaste MFC after: 2 weeks Sponsored by: The FreeBSD Foundation Differential Revision: https://reviews.freebsd.org/D20443 Modified: head/contrib/elftoolchain/libelf/_libelf.h head/contrib/elftoolchain/libelf/elf_end.c head/contrib/elftoolchain/libelf/elf_scn.c head/contrib/elftoolchain/libelf/elf_update.c head/contrib/elftoolchain/libelf/libelf_allocate.c head/contrib/elftoolchain/libelf/libelf_ehdr.c head/contrib/elftoolchain/libelf/libelf_extended.c Modified: head/contrib/elftoolchain/libelf/_libelf.h ============================================================================== --- head/contrib/elftoolchain/libelf/_libelf.h Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/_libelf.h Tue Jun 4 18:26:29 2019 (r348652) @@ -30,6 +30,7 @@ #define __LIBELF_H_ #include <sys/queue.h> +#include <sys/tree.h> #include "_libelf_config.h" @@ -80,6 +81,9 @@ extern struct _libelf_globals _libelf; #define LIBELF_F_SHDRS_LOADED 0x200000U /* whether all shdrs were read in */ #define LIBELF_F_SPECIAL_FILE 0x400000U /* non-regular file */ +RB_HEAD(scntree, _Elf_Scn); +RB_PROTOTYPE(scntree, _Elf_Scn, e_scn, elfscn_cmp); + struct _Elf { int e_activations; /* activation count */ unsigned int e_byteorder; /* ELFDATA* */ @@ -122,7 +126,7 @@ struct _Elf { Elf32_Phdr *e_phdr32; Elf64_Phdr *e_phdr64; } e_phdr; - STAILQ_HEAD(, _Elf_Scn) e_scn; /* section list */ + struct scntree e_scn; /* sections */ size_t e_nphdr; /* number of Phdr entries */ size_t e_nscn; /* number of sections */ size_t e_strndx; /* string table section index */ @@ -147,7 +151,7 @@ struct _Elf_Scn { } s_shdr; STAILQ_HEAD(, _Libelf_Data) s_data; /* translated data */ STAILQ_HEAD(, _Libelf_Data) s_rawdata; /* raw data */ - STAILQ_ENTRY(_Elf_Scn) s_next; + RB_ENTRY(_Elf_Scn) s_tree; struct _Elf *s_elf; /* parent ELF descriptor */ unsigned int s_flags; /* flags for the section as a whole */ size_t s_ndx; /* index# for this section */ Modified: head/contrib/elftoolchain/libelf/elf_end.c ============================================================================== --- head/contrib/elftoolchain/libelf/elf_end.c Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/elf_end.c Tue Jun 4 18:26:29 2019 (r348652) @@ -66,8 +66,7 @@ elf_end(Elf *e) /* * Reclaim all section descriptors. */ - STAILQ_FOREACH_SAFE(scn, &e->e_u.e_elf.e_scn, s_next, - tscn) + RB_FOREACH_SAFE(scn, scntree, &e->e_u.e_elf.e_scn, tscn) scn = _libelf_release_scn(scn); break; case ELF_K_NUM: Modified: head/contrib/elftoolchain/libelf/elf_scn.c ============================================================================== --- head/contrib/elftoolchain/libelf/elf_scn.c Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/elf_scn.c Tue Jun 4 18:26:29 2019 (r348652) @@ -38,6 +38,19 @@ ELFTC_VCSID("$Id: elf_scn.c 3632 2018-10-10 21:12:43Z jkoshy $"); +static int +elfscn_cmp(struct _Elf_Scn *s1, struct _Elf_Scn *s2) +{ + + if (s1->s_ndx < s2->s_ndx) + return (-1); + if (s1->s_ndx > s2->s_ndx) + return (1); + return (0); +} + +RB_GENERATE(scntree, _Elf_Scn, s_tree, elfscn_cmp); + /* * Load an ELF section table and create a list of Elf_Scn structures. */ @@ -95,9 +108,9 @@ _libelf_load_section_headers(Elf *e, void *ehdr) */ i = 0; - if (!STAILQ_EMPTY(&e->e_u.e_elf.e_scn)) { - assert(STAILQ_FIRST(&e->e_u.e_elf.e_scn) == - STAILQ_LAST(&e->e_u.e_elf.e_scn, _Elf_Scn, s_next)); + if (!RB_EMPTY(&e->e_u.e_elf.e_scn)) { + assert(RB_MIN(scntree, &e->e_u.e_elf.e_scn) == + RB_MAX(scntree, &e->e_u.e_elf.e_scn)); i = 1; src += fsz; @@ -148,10 +161,16 @@ elf_getscn(Elf *e, size_t index) _libelf_load_section_headers(e, ehdr) == 0) return (NULL); - STAILQ_FOREACH(s, &e->e_u.e_elf.e_scn, s_next) + for (s = RB_ROOT(&e->e_u.e_elf.e_scn); s != NULL;) { if (s->s_ndx == index) return (s); + if (s->s_ndx < index) + s = RB_RIGHT(s, s_tree); + else + s = RB_LEFT(s, s_tree); + } + LIBELF_SET_ERROR(ARGUMENT, 0); return (NULL); } @@ -201,7 +220,7 @@ elf_newscn(Elf *e) _libelf_load_section_headers(e, ehdr) == 0) return (NULL); - if (STAILQ_EMPTY(&e->e_u.e_elf.e_scn)) { + if (RB_EMPTY(&e->e_u.e_elf.e_scn)) { assert(e->e_u.e_elf.e_nscn == 0); if ((scn = _libelf_allocate_scn(e, (size_t) SHN_UNDEF)) == NULL) @@ -231,5 +250,5 @@ elf_nextscn(Elf *e, Elf_Scn *s) } return (s == NULL ? elf_getscn(e, (size_t) 1) : - STAILQ_NEXT(s, s_next)); + RB_NEXT(scntree, &e->e_u.e_elf.e_scn, s)); } Modified: head/contrib/elftoolchain/libelf/elf_update.c ============================================================================== --- head/contrib/elftoolchain/libelf/elf_update.c Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/elf_update.c Tue Jun 4 18:26:29 2019 (r348652) @@ -452,7 +452,7 @@ _libelf_resync_sections(Elf *e, off_t rc, struct _Elf_ * Make a pass through sections, computing the extent of each * section. */ - STAILQ_FOREACH(s, &e->e_u.e_elf.e_scn, s_next) { + RB_FOREACH(s, scntree, &e->e_u.e_elf.e_scn) { if (ec == ELFCLASS32) sh_type = s->s_shdr.s_shdr32.sh_type; else @@ -980,7 +980,7 @@ _libelf_write_shdr(Elf *e, unsigned char *nf, struct _ fsz = _libelf_fsize(ELF_T_SHDR, ec, e->e_version, (size_t) 1); - STAILQ_FOREACH(scn, &e->e_u.e_elf.e_scn, s_next) { + RB_FOREACH(scn, scntree, &e->e_u.e_elf.e_scn) { if (ec == ELFCLASS32) src.d_buf = &scn->s_shdr.s_shdr32; else @@ -1142,7 +1142,7 @@ _libelf_write_elf(Elf *e, off_t newsize, struct _Elf_E e->e_flags &= ~ELF_F_DIRTY; - STAILQ_FOREACH_SAFE(scn, &e->e_u.e_elf.e_scn, s_next, tscn) + RB_FOREACH_SAFE(scn, scntree, &e->e_u.e_elf.e_scn, tscn) _libelf_release_scn(scn); if (e->e_class == ELFCLASS32) { Modified: head/contrib/elftoolchain/libelf/libelf_allocate.c ============================================================================== --- head/contrib/elftoolchain/libelf/libelf_allocate.c Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/libelf_allocate.c Tue Jun 4 18:26:29 2019 (r348652) @@ -76,7 +76,7 @@ _libelf_init_elf(Elf *e, Elf_Kind kind) switch (kind) { case ELF_K_ELF: - STAILQ_INIT(&e->e_u.e_elf.e_scn); + RB_INIT(&e->e_u.e_elf.e_scn); break; default: break; @@ -111,7 +111,7 @@ _libelf_release_elf(Elf *e) break; } - assert(STAILQ_EMPTY(&e->e_u.e_elf.e_scn)); + assert(RB_EMPTY(&e->e_u.e_elf.e_scn)); if (e->e_flags & LIBELF_F_AR_HEADER) { arh = e->e_hdr.e_arhdr; @@ -174,7 +174,7 @@ _libelf_allocate_scn(Elf *e, size_t ndx) STAILQ_INIT(&s->s_data); STAILQ_INIT(&s->s_rawdata); - STAILQ_INSERT_TAIL(&e->e_u.e_elf.e_scn, s, s_next); + RB_INSERT(scntree, &e->e_u.e_elf.e_scn, s); return (s); } @@ -202,7 +202,7 @@ _libelf_release_scn(Elf_Scn *s) assert(e != NULL); - STAILQ_REMOVE(&e->e_u.e_elf.e_scn, s, _Elf_Scn, s_next); + RB_REMOVE(scntree, &e->e_u.e_elf.e_scn, s); free(s); Modified: head/contrib/elftoolchain/libelf/libelf_ehdr.c ============================================================================== --- head/contrib/elftoolchain/libelf/libelf_ehdr.c Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/libelf_ehdr.c Tue Jun 4 18:26:29 2019 (r348652) @@ -46,7 +46,7 @@ _libelf_load_extended(Elf *e, int ec, uint64_t shoff, uint32_t shtype; _libelf_translator_function *xlator; - assert(STAILQ_EMPTY(&e->e_u.e_elf.e_scn)); + assert(RB_EMPTY(&e->e_u.e_elf.e_scn)); fsz = _libelf_fsize(ELF_T_SHDR, ec, e->e_version, 1); assert(fsz > 0); Modified: head/contrib/elftoolchain/libelf/libelf_extended.c ============================================================================== --- head/contrib/elftoolchain/libelf/libelf_extended.c Tue Jun 4 18:11:12 2019 (r348651) +++ head/contrib/elftoolchain/libelf/libelf_extended.c Tue Jun 4 18:26:29 2019 (r348652) @@ -39,7 +39,7 @@ _libelf_getscn0(Elf *e) { Elf_Scn *s; - if ((s = STAILQ_FIRST(&e->e_u.e_elf.e_scn)) != NULL) + if ((s = RB_MIN(scntree, &e->e_u.e_elf.e_scn)) != NULL) return (s); return (_libelf_allocate_scn(e, (size_t) SHN_UNDEF)); _______________________________________________ svn-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
