Accumulate intermediate imutables locally before applying

OK deraadt

4 files changed, 88 insertions, 89 deletions

diff --git a/libexec/ld.so/library.c b/libexec/ld.so/library.c
index f22b2db306b..68752074644 100644
--- a/libexec/ld.so/library.c
+++ b/libexec/ld.so/library.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: library.c,v 1.89 2022/12/04 15:42:07 deraadt Exp $ */
+/*	$OpenBSD: library.c,v 1.90 2023/01/29 20:30:56 gnezdo Exp $ */
 
 /*
  * Copyright (c) 2002 Dale Rahn
@@ -98,7 +98,7 @@ unload:
 elf_object_t *
 _dl_tryload_shlib(const char *libname, int type, int flags, int nodelete)
 {
-	struct mutate imut[MAXMUT], mut[MAXMUT];
+	struct range_vector imut, mut;
 	int	libfile, i;
 	struct load_list *next_load, *load_list = NULL;
 	Elf_Addr maxva = 0, minva = ELF_NO_ADDR;
@@ -216,7 +216,7 @@ _dl_tryload_shlib(const char *libname, int type, int flags, int nodelete)
 	phdp = (Elf_Phdr *)(hbuf + ehdr->e_phoff);
 
 	/* Entire mapping can become immutable, minus exceptions chosen later */
-	_dl_defer_immut(imut, loff, maxva - minva);
+	_dl_push_range_size(&imut, loff, maxva - minva);
 
 	for (i = 0; i < ehdr->e_phnum; i++, phdp++) {
 		switch (phdp->p_type) {
@@ -300,11 +300,12 @@ _dl_tryload_shlib(const char *libname, int type, int flags, int nodelete)
 		case PT_GNU_RELRO:
 			relro_addr = phdp->p_vaddr + loff;
 			relro_size = phdp->p_memsz;
-			_dl_defer_mut(mut, phdp->p_vaddr + loff, phdp->p_memsz);
+			_dl_push_range_size(&mut, relro_addr, relro_size);
 			break;
 
 		case PT_OPENBSD_MUTABLE:
-			_dl_defer_mut(mut, phdp->p_vaddr + loff, phdp->p_memsz);
+			_dl_push_range_size(&mut, phdp->p_vaddr + loff,
+			    phdp->p_memsz);
 			break;
 
 		default:
@@ -341,8 +342,8 @@ _dl_tryload_shlib(const char *libname, int type, int flags, int nodelete)
 				_dl_printf("msyscall %lx %lx error\n",
 				    exec_start, exec_size);
 		}
-		_dl_bcopy(mut, object->mut, sizeof mut);
-		_dl_bcopy(imut, object->imut, sizeof imut);
+		_dl_bcopy(&mut, &object->mut, sizeof mut);
+		_dl_bcopy(&imut, &object->imut, sizeof imut);
 	} else {
 		_dl_munmap((void *)libaddr, maxva - minva);
 		_dl_load_list_free(load_list);
diff --git a/libexec/ld.so/library_mquery.c b/libexec/ld.so/library_mquery.c
index 143c44c526b..93019a039e1 100644
--- a/libexec/ld.so/library_mquery.c
+++ b/libexec/ld.so/library_mquery.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: library_mquery.c,v 1.69 2022/12/04 15:42:07 deraadt Exp $ */
+/*	$OpenBSD: library_mquery.c,v 1.70 2023/01/29 20:30:56 gnezdo Exp $ */
 
 /*
  * Copyright (c) 2002 Dale Rahn
@@ -103,7 +103,7 @@ unload:
 elf_object_t *
 _dl_tryload_shlib(const char *libname, int type, int flags, int nodelete)
 {
-	struct mutate imut[MAXMUT], mut[MAXMUT];
+	struct range_vector imut, mut;
 	int libfile, i;
 	struct load_list *ld, *lowld = NULL;
 	elf_object_t *object;
@@ -289,7 +289,7 @@ retry:
 		}
 
 		/* Entire mapping can become immutable, minus exceptions chosen later */
-		_dl_defer_immut(imut, LOFF + ld->moff, ROUND_PG(ld->size));
+		_dl_push_range_size(&imut, LOFF + ld->moff, ROUND_PG(ld->size));
 
 		ld->start = res;
 	}
@@ -312,10 +312,11 @@ retry:
 		case PT_GNU_RELRO:
 			relro_addr = phdp->p_vaddr + LOFF;
 			relro_size = phdp->p_memsz;
-			_dl_defer_mut(mut, phdp->p_vaddr + LOFF, phdp->p_memsz);
+			_dl_push_range_size(&mut, relro_addr, relro_size);
 			break;
 		case PT_OPENBSD_MUTABLE:
-			_dl_defer_mut(mut, phdp->p_vaddr + LOFF, phdp->p_memsz);
+			_dl_push_range_size(&mut, phdp->p_vaddr + LOFF,
+			    phdp->p_memsz);
 			break;
 		}
 	}
@@ -350,8 +351,8 @@ retry:
 				_dl_printf("msyscall %lx %lx error\n",
 				    exec_start, exec_size);
 		}
-		_dl_bcopy(mut, object->mut, sizeof mut);
-		_dl_bcopy(imut, object->imut, sizeof imut);
+		_dl_bcopy(&mut, &object->mut, sizeof mut);
+		_dl_bcopy(&imut, &object->imut, sizeof imut);
 	} else {
 		_dl_load_list_free(lowld);
 	}
diff --git a/libexec/ld.so/loader.c b/libexec/ld.so/loader.c
index a78408302e9..889712b9d8d 100644
--- a/libexec/ld.so/loader.c
+++ b/libexec/ld.so/loader.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: loader.c,v 1.209 2022/12/25 09:39:37 visa Exp $ */
+/*	$OpenBSD: loader.c,v 1.210 2023/01/29 20:30:56 gnezdo Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -1018,92 +1018,87 @@ _dl_rreloc(elf_object_t *object)
 }
 
 void
-_dl_defer_immut(struct mutate *m, vaddr_t start, vsize_t len)
+_dl_push_range(struct range_vector *v, vaddr_t s, vaddr_t e)
 {
-	int i;
+	int i = v->count;
 
-	for (i = 0; i < MAXMUT; i++) {
-		if (m[i].valid == 0) {
-			m[i].start = start;
-			m[i].end = start + len;
-			m[i].valid = 1;
-			return;
-		}
+	if (i == nitems(v->slice)) {
+		_dl_die("too many ranges");
+	}
+	/* Skips the empty ranges (s == e). */
+	if (s < e) {
+		v->slice[i].start = s;
+		v->slice[i].end = e;
+		v->count++;
+	} else if (s > e) {
+		_dl_die("invalid range");
 	}
-	if (i == MAXMUT)
-		_dl_die("too many _dl_defer_immut");
 }
 
 void
-_dl_defer_mut(struct mutate *m, vaddr_t start, size_t len)
+_dl_push_range_size(struct range_vector *v, vaddr_t s, vsize_t size)
 {
-	int i;
-
-	for (i = 0; i < MAXMUT; i++) {
-		if (m[i].valid == 0) {
-			m[i].start = start;
-			m[i].end = start + len;
-			m[i].valid = 1;
-			return;
-		}
-	}
-	if (i == MAXMUT)
-		_dl_die("too many _dl_defer_mut");
+	_dl_push_range(v, s, s + size);
 }
 
+/*
+ * Finds the truly immutable ranges by taking mutable ones out.  Implements
+ * interval difference of imut and mut. Interval splitting necessitates
+ * intermediate storage and complex double buffering.
+ */
 void
 _dl_apply_immutable(elf_object_t *object)
 {
-	struct mutate *m, *im, *imtail;
-	int mut, imut;
-	
+	struct range_vector acc[2];  /* flips out to avoid copying */
+	struct addr_range *m, *im;
+	int i, j, imut, in, out;
+
 	if (object->obj_type != OBJTYPE_LIB)
 		return;
 
-	imtail = &object->imut[MAXMUT - 1];
-
-	for (imut = 0; imut < MAXMUT; imut++) {
-		im = &object->imut[imut];
-		if (im->valid == 0)
-			continue;
-
-		for (mut = 0; mut < MAXMUT; mut++) {
-			m = &object->mut[mut];
-			if (m->valid == 0)
-				continue;
-			if (m->start <= im->start) {
-				if (m->end < im->start) {
+	for (imut = 0; imut < object->imut.count; imut++) {
+		im = &object->imut.slice[imut];
+		out = 0;
+		acc[out].count = 0;
+		_dl_push_range(&acc[out], im->start, im->end);
+
+		for (i = 0; i < object->mut.count; i++) {
+			m = &object->mut.slice[i];
+			in = out;
+			out = 1 - in;
+			acc[out].count = 0;
+			for (j = 0; j < acc[in].count; j++) {
+				const vaddr_t ms = m->start, me = m->end;
+				const vaddr_t is = acc[in].slice[j].start,
+				    ie = acc[in].slice[j].end;
+				if (ie <= ms || me <= is) {
+					/* is .. ie .. ms .. me -> is .. ie */
+					/* ms .. me .. is .. ie -> is .. ie */
+					_dl_push_range(&acc[out], is, ie);
+				} else if (ms <= is && ie <= me) {
+					/* PROVIDED: ms < ie && is < me */
+					/* ms .. is .. ie .. me -> [] */
 					;
-				} else if (m->end >= im->end) {
-					im->start = im->end = im->valid = 0;
+				} else if (ie <= me) {
+					/* is .. ms .. ie .. me -> is .. ms */
+					_dl_push_range(&acc[out], is, ms);
+				} else if (is < ms) {
+					/* is .. ms .. me .. ie -> is .. ms */
+					_dl_push_range(&acc[out], is, ms);
+					_dl_push_range(&acc[out], me, ie);
 				} else {
-					im->start = m->end;
-				}
-			} else if (m->start > im->start) {
-				if (m->end > im->end) {
-					;
-				} else if (m->end == im->end) {
-					im->end = m->start;
-				} else if (m->end < im->end) {
-					imtail->start = im->start;
-					imtail->end = m->start;
-					imtail->valid = 1;
-					imtail--;
-					imtail->start = m->end;
-					imtail->end = im->end;
-					imtail->valid = 1;
-					imtail--;
-					im->start = im->end = im->valid = 0;
+					/* ms .. is .. me .. ie -> me .. ie */
+					_dl_push_range(&acc[out], me, ie);
 				}
 			}
 		}
-	}
 
-	/* and now, install immutability for objects */
-	for (imut = 0; imut < MAXMUT; imut++) {
-		im = &object->imut[imut];
-		if (im->valid == 0)
-			continue;
-		_dl_mimmutable((void *)im->start, im->end - im->start);
+		/* and now, install immutability for objects */
+		for (i = 0; i < acc[out].count; i++) {
+			const struct addr_range *ar = &acc[out].slice[i];
+			_dl_mimmutable((void *)ar->start, ar->end - ar->start);
+		}
+
 	}
+
 }
diff --git a/libexec/ld.so/resolve.h b/libexec/ld.so/resolve.h
index 550fd7d5102..19e8bea4b98 100644
--- a/libexec/ld.so/resolve.h
+++ b/libexec/ld.so/resolve.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: resolve.h,v 1.103 2022/12/04 15:42:07 deraadt Exp $ */
+/*	$OpenBSD: resolve.h,v 1.104 2023/01/29 20:30:56 gnezdo Exp $ */
 
 /*
  * Copyright (c) 1998 Per Fogelstrom, Opsycon AB
@@ -77,10 +77,14 @@ struct object_vector {
 };
 void	object_vec_grow(struct object_vector *_vec, int _more);
 
-struct mutate {
+struct addr_range {
 	vaddr_t start;
 	vaddr_t end;
-	int valid;
+};
+
+struct range_vector {
+	struct addr_range slice[40];
+	int count;
 };
 
 /*
@@ -239,9 +243,8 @@ struct elf_object {
 	/* nonzero if trace enabled for this object */
 	int traced;
 
-#define MAXMUT 40
-	struct mutate imut[MAXMUT];
-	struct mutate mut[MAXMUT];
+	struct range_vector imut;
+	struct range_vector mut;
 };
 
 struct dep_node {
@@ -330,8 +333,7 @@ char	*_dl_find_shlib(struct sod *sodp, char **searchpath, int nohints);
 void	_dl_load_list_free(struct load_list *load_list);
 
 void _dl_find_immutables(int type, elf_object_t *object, Elf_Ehdr *);
-void _dl_defer_mut(struct mutate *m, vaddr_t start, vsize_t len);
-void _dl_defer_immut(struct mutate *m, vaddr_t start, vsize_t len);
+void _dl_push_range_size(struct range_vector *v, vaddr_t start, vsize_t len);
 void _dl_apply_immutable(elf_object_t *object);
 
 typedef void lock_cb(int);