From e9bb90e8f8c0547185941fa40083a0230f0b616f Mon Sep 17 00:00:00 2001
From: Matthew Dillon <dillon@dragonflybsd.org>
Date: Mon, 25 Aug 2003 17:01:13 +0000
Subject: [PATCH] Add an alignment feature to vm_map_findspace().  This feature
 will be used primarily by the upcoming slab allocator but has many
 applications.

Use the alignment feature in the buffer cache to hopefully reduce
fragmentation.
---
 sys/kern/vfs_bio.c |  5 +++--
 sys/vm/vm_kern.c   |  8 +++----
 sys/vm/vm_map.c    | 52 ++++++++++++++++++++++++++++++++++++----------
 sys/vm/vm_map.h    |  4 ++--
 sys/vm/vm_page.c   |  4 ++--
 5 files changed, 52 insertions(+), 21 deletions(-)

diff --git a/sys/kern/vfs_bio.c b/sys/kern/vfs_bio.c
index 9a8c62252f..3f6559515e 100644
--- a/sys/kern/vfs_bio.c
+++ b/sys/kern/vfs_bio.c
@@ -12,7 +12,7 @@
  *		John S. Dyson.
  *
  * $FreeBSD: src/sys/kern/vfs_bio.c,v 1.242.2.20 2003/05/28 18:38:10 alc Exp $
- * $DragonFly: src/sys/kern/vfs_bio.c,v 1.11 2003/07/26 19:42:11 rob Exp $
+ * $DragonFly: src/sys/kern/vfs_bio.c,v 1.12 2003/08/25 17:01:10 dillon Exp $
  */
 
 /*
@@ -1713,7 +1713,8 @@ restart:
 			vm_map_lock(buffer_map);
 
 			if (vm_map_findspace(buffer_map,
-				vm_map_min(buffer_map), maxsize, &addr)) {
+				    vm_map_min(buffer_map), maxsize,
+				    maxsize, &addr)) {
 				/*
 				 * Uh oh.  Buffer map is to fragmented.  We
 				 * must defragment the map.
diff --git a/sys/vm/vm_kern.c b/sys/vm/vm_kern.c
index 995ca07a6e..b81c47991e 100644
--- a/sys/vm/vm_kern.c
+++ b/sys/vm/vm_kern.c
@@ -62,7 +62,7 @@
  * rights to redistribute these changes.
  *
  * $FreeBSD: src/sys/vm/vm_kern.c,v 1.61.2.2 2002/03/12 18:25:26 tegge Exp $
- * $DragonFly: src/sys/vm/vm_kern.c,v 1.5 2003/07/26 22:10:02 rob Exp $
+ * $DragonFly: src/sys/vm/vm_kern.c,v 1.6 2003/08/25 17:01:13 dillon Exp $
  */
 
 /*
@@ -167,7 +167,7 @@ kmem_alloc(map, size)
 	 * offset within the kernel map.
 	 */
 	vm_map_lock(map);
-	if (vm_map_findspace(map, vm_map_min(map), size, &addr)) {
+	if (vm_map_findspace(map, vm_map_min(map), size, 1, &addr)) {
 		vm_map_unlock(map);
 		return (0);
 	}
@@ -319,7 +319,7 @@ kmem_malloc(map, size, flags)
 	 * offset within the kernel map.
 	 */
 	vm_map_lock(map);
-	if (vm_map_findspace(map, vm_map_min(map), size, &addr)) {
+	if (vm_map_findspace(map, vm_map_min(map), size, 1, &addr)) {
 		vm_map_unlock(map);
 		if (map == mb_map) {
 			mb_map_full = TRUE;
@@ -441,7 +441,7 @@ kmem_alloc_wait(map, size)
 		 * to lock out sleepers/wakers.
 		 */
 		vm_map_lock(map);
-		if (vm_map_findspace(map, vm_map_min(map), size, &addr) == 0)
+		if (vm_map_findspace(map, vm_map_min(map), size, 1, &addr) == 0)
 			break;
 		/* no space now; see if we can ever get space */
 		if (vm_map_max(map) - vm_map_min(map) < size) {
diff --git a/sys/vm/vm_map.c b/sys/vm/vm_map.c
index c70028c289..025e83b38a 100644
--- a/sys/vm/vm_map.c
+++ b/sys/vm/vm_map.c
@@ -62,7 +62,7 @@
  * rights to redistribute these changes.
  *
  * $FreeBSD: src/sys/vm/vm_map.c,v 1.187.2.19 2003/05/27 00:47:02 alc Exp $
- * $DragonFly: src/sys/vm/vm_map.c,v 1.8 2003/08/20 08:03:01 rob Exp $
+ * $DragonFly: src/sys/vm/vm_map.c,v 1.9 2003/08/25 17:01:13 dillon Exp $
  */
 
 /*
@@ -662,22 +662,41 @@ vm_map_insert(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
 /*
  * Find sufficient space for `length' bytes in the given map, starting at
  * `start'.  The map must be locked.  Returns 0 on success, 1 on no space.
+ *
+ * This function will returned an arbitrarily aligned pointer.  If no
+ * particular alignment is required you should pass align as 1.  Note that
+ * the map may return PAGE_SIZE aligned pointers if all the lengths used in
+ * the map are a multiple of PAGE_SIZE, even if you pass a smaller align
+ * argument.
+ *
+ * 'align' should be a power of 2 but is not required to be.
  */
 int
-vm_map_findspace(map, start, length, addr)
-	vm_map_t map;
-	vm_offset_t start;
-	vm_size_t length;
-	vm_offset_t *addr;
+vm_map_findspace(
+	vm_map_t map,
+	vm_offset_t start,
+	vm_size_t length,
+	vm_offset_t align,
+	vm_offset_t *addr)
 {
 	vm_map_entry_t entry, next;
 	vm_offset_t end;
+	vm_offset_t align_mask;
 
 	if (start < map->min_offset)
 		start = map->min_offset;
 	if (start > map->max_offset)
 		return (1);
 
+	/*
+	 * If the alignment is not a power of 2 we will have to use
+	 * a mod/division, set align_mask to a special value.
+	 */
+	if ((align | (align - 1)) + 1 != (align << 1))
+		align_mask = (vm_offset_t)-1;
+	else
+		align_mask = align - 1;
+
 	/*
 	 * Look for the first possible address; if there's already something
 	 * at this address, we have to start after it.
@@ -698,12 +717,23 @@ vm_map_findspace(map, start, length, addr)
 	 * gap between existing regions, or after the very last region.
 	 */
 	for (;; start = (entry = next)->end) {
+		/*
+		 * Adjust the proposed start by the requested alignment,
+		 * be sure that we didn't wrap the address.
+		 */
+		if (align_mask == (vm_offset_t)-1)
+			end = ((start + align - 1) / align) * align;
+		else
+			end = (start + align_mask) & ~align_mask;
+		if (end < start)
+			return (1);
+		start = end;
 		/*
 		 * Find the end of the proposed new region.  Be sure we didn't
-		 * go beyond the end of the map, or wrap around the address;
-		 * if so, we lose.  Otherwise, if this is the last entry, or
-		 * if the proposed new region fits before the next entry, we
-		 * win.
+		 * go beyond the end of the map, or wrap around the address.
+		 * Then check to see if this is the last entry or if the 
+		 * proposed end fits in the gap between this and the next
+		 * entry.
 		 */
 		end = start + length;
 		if (end > map->max_offset || end < start)
@@ -748,7 +778,7 @@ vm_map_find(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
 
 	vm_map_lock(map);
 	if (find_space) {
-		if (vm_map_findspace(map, start, length, addr)) {
+		if (vm_map_findspace(map, start, length, 1, addr)) {
 			vm_map_unlock(map);
 			if (map == kmem_map || map == mb_map)
 				splx(s);
diff --git a/sys/vm/vm_map.h b/sys/vm/vm_map.h
index 4ae2425a3f..4bf724c5c6 100644
--- a/sys/vm/vm_map.h
+++ b/sys/vm/vm_map.h
@@ -62,7 +62,7 @@
  * rights to redistribute these changes.
  *
  * $FreeBSD: src/sys/vm/vm_map.h,v 1.54.2.5 2003/01/13 22:51:17 dillon Exp $
- * $DragonFly: src/sys/vm/vm_map.h,v 1.5 2003/08/20 08:03:01 rob Exp $
+ * $DragonFly: src/sys/vm/vm_map.h,v 1.6 2003/08/25 17:01:13 dillon Exp $
  */
 
 /*
@@ -363,7 +363,7 @@ struct pmap;
 vm_map_t vm_map_create (struct pmap *, vm_offset_t, vm_offset_t);
 int vm_map_delete (vm_map_t, vm_offset_t, vm_offset_t);
 int vm_map_find (vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t *, vm_size_t, boolean_t, vm_prot_t, vm_prot_t, int);
-int vm_map_findspace (vm_map_t, vm_offset_t, vm_size_t, vm_offset_t *);
+int vm_map_findspace (vm_map_t, vm_offset_t, vm_size_t, vm_offset_t, vm_offset_t *);
 int vm_map_inherit (vm_map_t, vm_offset_t, vm_offset_t, vm_inherit_t);
 void vm_map_init (struct vm_map *, vm_offset_t, vm_offset_t);
 int vm_map_insert (vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t, vm_offset_t, vm_prot_t, vm_prot_t, int);
diff --git a/sys/vm/vm_page.c b/sys/vm/vm_page.c
index b69f7960ea..54f2d31404 100644
--- a/sys/vm/vm_page.c
+++ b/sys/vm/vm_page.c
@@ -35,7 +35,7 @@
  *
  *	from: @(#)vm_page.c	7.4 (Berkeley) 5/7/91
  * $FreeBSD: src/sys/vm/vm_page.c,v 1.147.2.18 2002/03/10 05:03:19 alc Exp $
- * $DragonFly: src/sys/vm/vm_page.c,v 1.7 2003/07/19 21:14:53 dillon Exp $
+ * $DragonFly: src/sys/vm/vm_page.c,v 1.8 2003/08/25 17:01:13 dillon Exp $
  */
 
 /*
@@ -1848,7 +1848,7 @@ again1:
 		 * return kernel VM pointer.
 		 */
 		vm_map_lock(map);
-		if (vm_map_findspace(map, vm_map_min(map), size, &addr) !=
+		if (vm_map_findspace(map, vm_map_min(map), size, 1, &addr) !=
 		    KERN_SUCCESS) {
 			/*
 			 * XXX We almost never run out of kernel virtual
-- 
2.41.0