Index: head/contrib/elftoolchain/libelf/_libelf.h
===================================================================
--- head/contrib/elftoolchain/libelf/_libelf.h
+++ head/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 @@
 #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 @@
 				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 @@
 	} 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 */
Index: head/contrib/elftoolchain/libelf/elf_end.c
===================================================================
--- head/contrib/elftoolchain/libelf/elf_end.c
+++ head/contrib/elftoolchain/libelf/elf_end.c
@@ -66,8 +66,7 @@
 			/*
 			 * 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:
Index: head/contrib/elftoolchain/libelf/elf_scn.c
===================================================================
--- head/contrib/elftoolchain/libelf/elf_scn.c
+++ head/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 @@
 	 */
 
 	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 @@
 	    _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 @@
 	    _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 @@
 	}
 
 	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));
 }
Index: head/contrib/elftoolchain/libelf/elf_update.c
===================================================================
--- head/contrib/elftoolchain/libelf/elf_update.c
+++ head/contrib/elftoolchain/libelf/elf_update.c
@@ -452,7 +452,7 @@
 	 * 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 @@
 
 	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 @@
 
 	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) {
Index: head/contrib/elftoolchain/libelf/libelf_allocate.c
===================================================================
--- head/contrib/elftoolchain/libelf/libelf_allocate.c
+++ head/contrib/elftoolchain/libelf/libelf_allocate.c
@@ -76,7 +76,7 @@
 
 	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 @@
 			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 @@
 	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 @@
 
 	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);
 
Index: head/contrib/elftoolchain/libelf/libelf_ehdr.c
===================================================================
--- head/contrib/elftoolchain/libelf/libelf_ehdr.c
+++ head/contrib/elftoolchain/libelf/libelf_ehdr.c
@@ -46,7 +46,7 @@
 	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);
Index: head/contrib/elftoolchain/libelf/libelf_extended.c
===================================================================
--- head/contrib/elftoolchain/libelf/libelf_extended.c
+++ head/contrib/elftoolchain/libelf/libelf_extended.c
@@ -39,7 +39,7 @@
 {
 	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));