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

7 files changed, 41 insertions, 19 deletions

diff --git a/contrib/elftoolchain/libelf/_libelf.h b/contrib/elftoolchain/libelf/_libelf.h
index f7f8d9a151c2..a3a43285cb13 100644
--- a/contrib/elftoolchain/libelf/_libelf.h
+++ b/contrib/elftoolchain/libelf/_libelf.h
@@ -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 */
diff --git a/contrib/elftoolchain/libelf/elf_end.c b/contrib/elftoolchain/libelf/elf_end.c
index 3f32ebbee8ec..5c4c76e1b7a1 100644
--- a/contrib/elftoolchain/libelf/elf_end.c
+++ b/contrib/elftoolchain/libelf/elf_end.c
@@ -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:
diff --git a/contrib/elftoolchain/libelf/elf_scn.c b/contrib/elftoolchain/libelf/elf_scn.c
index b72fef66c46b..29da21a4261e 100644
--- a/contrib/elftoolchain/libelf/elf_scn.c
+++ b/contrib/elftoolchain/libelf/elf_scn.c
@@ -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));
 }
diff --git a/contrib/elftoolchain/libelf/elf_update.c b/contrib/elftoolchain/libelf/elf_update.c
index 755f33690e36..431b473eef8d 100644
--- a/contrib/elftoolchain/libelf/elf_update.c
+++ b/contrib/elftoolchain/libelf/elf_update.c
@@ -452,7 +452,7 @@ _libelf_resync_sections(Elf *e, off_t rc, struct _Elf_Extent_List *extents)
 	 * 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 _Elf_Extent *ex)
 
 	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_Extent_List *extents)
 
 	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) {
diff --git a/contrib/elftoolchain/libelf/libelf_allocate.c b/contrib/elftoolchain/libelf/libelf_allocate.c
index 0a74facc9fc4..f9dab08d1ed6 100644
--- a/contrib/elftoolchain/libelf/libelf_allocate.c
+++ b/contrib/elftoolchain/libelf/libelf_allocate.c
@@ -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);
 
diff --git a/contrib/elftoolchain/libelf/libelf_ehdr.c b/contrib/elftoolchain/libelf/libelf_ehdr.c
index 38e4e74e14d2..0a761956418e 100644
--- a/contrib/elftoolchain/libelf/libelf_ehdr.c
+++ b/contrib/elftoolchain/libelf/libelf_ehdr.c
@@ -46,7 +46,7 @@ _libelf_load_extended(Elf *e, int ec, uint64_t shoff, uint16_t phnum,
 	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);
diff --git a/contrib/elftoolchain/libelf/libelf_extended.c b/contrib/elftoolchain/libelf/libelf_extended.c
index 96765a8293e1..21be11c87fab 100644
--- a/contrib/elftoolchain/libelf/libelf_extended.c
+++ b/contrib/elftoolchain/libelf/libelf_extended.c
@@ -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));