vm_map: Fix taking into account high bits in mask

glibc's sysdeps/mach/hurd/dl-sysdep.c has been wanting to use this for
decades.

* include/string.h (ffs): New declaration.
* vm/vm_map.c: Include <string.h>.
(vm_map_find_entry_anywhere): Separate out high bits from mask, to
compute the maximum offset instead of map->max_offset.
* doc/mach.texi (vm_map): Update documentation accordingly.

3 files changed, 33 insertions, 4 deletions

diff --git a/doc/mach.texi b/doc/mach.texi
index 11b0a066..ff15a95a 100644
--- a/doc/mach.texi
+++ b/doc/mach.texi
@@ -3434,8 +3434,8 @@ exception.
 @var{address}.  If the @var{anywhere} option is used, this address is
 ignored.  The address actually allocated will be returned in
 @var{address}. @var{size} is the number of bytes to allocate (rounded by
-the system in a machine dependent way).  The alignment restriction is
-specified by @var{mask}.  Bits asserted in this mask must not be
+the system in a machine dependent way).  The alignment and maximum address
+restrictions are specified by @var{mask}.  Bits asserted in this mask must not be
 asserted in the address returned.  If @var{anywhere} is set, the kernel
 should find and allocate any region of the specified size, and return
 the address of the resulting region in @var{address}.
diff --git a/include/string.h b/include/string.h
index c31b4292..cddcbeb9 100644
--- a/include/string.h
+++ b/include/string.h
@@ -54,4 +54,6 @@ extern size_t strlen (const char *s) __attribute__ ((pure));
 
 extern char *strstr(const char *haystack, const char *needle);
 
+extern int ffs(int i);
+
 #endif /* _MACH_SA_SYS_STRING_H_ */
diff --git a/vm/vm_map.c b/vm/vm_map.c
index ffc8934b..8ab6b1da 100644
--- a/vm/vm_map.c
+++ b/vm/vm_map.c
@@ -54,6 +54,7 @@
 #include <vm/vm_resident.h>
 #include <vm/vm_kern.h>
 #include <ipc/ipc_port.h>
+#include <string.h>
 
 #if	MACH_KDB
 #include <ddb/db_output.h>
@@ -672,9 +673,30 @@ vm_map_find_entry_anywhere(struct vm_map *map,
 	struct rbtree_node *node;
 	vm_size_t max_size;
 	vm_offset_t start, end;
+	vm_offset_t max;
 
 	assert(size != 0);
 
+	max = map->max_offset;
+	if (((mask + 1) & mask) != 0) {
+		/* We have high bits in addition to the low bits */
+
+		int first0 = ffs(~mask);		/* First zero after low bits */
+		vm_offset_t lowmask = (1UL << (first0-1)) - 1;		/* low bits */
+		vm_offset_t himask = mask - lowmask;			/* high bits */
+		int second1 = ffs(himask);		/* First one after low bits */
+
+		max = 1UL << (second1-1);
+
+		if (himask + max != 0) {
+			/* high bits do not continue up to the end */
+			printf("invalid mask %lx\n", mask);
+			return NULL;
+		}
+
+		mask = lowmask;
+	}
+
 	if (!map_locked) {
 		vm_map_lock(map);
 	}
@@ -685,7 +707,7 @@ restart:
 		start = (map->min_offset + mask) & ~mask;
 		end = start + size;
 
-		if ((start < map->min_offset) || (end <= start) || (end > map->max_offset)) {
+		if ((start < map->min_offset) || (end <= start) || (end > max)) {
 			goto error;
 		}
 
@@ -701,7 +723,7 @@ restart:
 
 		if ((start >= entry->vme_end)
 		    && (end > start)
-		    && (end <= map->max_offset)
+		    && (end <= max)
 		    && (end <= (entry->vme_end + entry->gap_size))) {
 			*startp = start;
 			return entry;
@@ -743,6 +765,11 @@ restart:
 	end = start + size;
 	assert(end > start);
 	assert(end <= (entry->vme_end + entry->gap_size));
+	if (end > max) {
+		/* Does not respect the allowed maximum */
+		printf("%lx does not respect %lx\n", end, max);
+		return NULL;
+	}
 	*startp = start;
 	return entry;