X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/2694e78a51876af674b11914967855656678dcd0..9db58063b0ec3fd6346a70c6fa403c32665343df:/usr/src/sys/kern/subr_rmap.c

diff --git a/usr/src/sys/kern/subr_rmap.c b/usr/src/sys/kern/subr_rmap.c
index cb52606a98..eb0cef7229 100644
--- a/usr/src/sys/kern/subr_rmap.c
+++ b/usr/src/sys/kern/subr_rmap.c
@@ -1,34 +1,131 @@
-/*	subr_rmap.c	3.1	%H%	*/
+/*
+ * Copyright (c) 1982, 1986 Regents of the University of California.
+ * All rights reserved.  The Berkeley software License Agreement
+ * specifies the terms and conditions for redistribution.
+ *
+ *	@(#)subr_rmap.c	7.5 (Berkeley) %G%
+ */
+
+#include "param.h"
+#include "systm.h"
+#include "map.h"
+#include "user.h"
+#include "proc.h"
+#include "kernel.h"
+
+/*
+ * Resource map handling routines.
+ *
+ * A resource map is an array of structures each
+ * of which describes a segment of the address space of an available
+ * resource.  The segments are described by their base address and
+ * length, and sorted in address order.  Each resource map has a fixed
+ * maximum number of segments allowed.  Resources are allocated
+ * by taking part or all of one of the segments of the map.
+ *
+ * Returning of resources will require another segment if
+ * the returned resources are not adjacent in the address
+ * space to an existing segment.  If the return of a segment
+ * would require a slot which is not available, then one of
+ * the resource map segments is discarded after a warning is printed.
+ * Returning of resources may also cause the map to collapse
+ * by coalescing two existing segments and the returned space
+ * into a single segment.  In this case the resource map is
+ * made smaller by copying together to fill the resultant gap.
+ *
+ * N.B.: the current implementation uses a dense array and does
+ * not admit the value ``0'' as a legal address, since that is used
+ * as a delimiter.
+ */
+
+/*
+ * Initialize map mp to have (mapsize-2) segments
+ * and to be called ``name'', which we print if
+ * the slots become so fragmented that we lose space.
+ * The map itself is initialized with size elements free
+ * starting at addr.
+ */
+rminit(mp, size, addr, name, mapsize)
+	register struct map *mp;
+	long size, addr;
+	char *name;
+	int mapsize;
+{
+	register struct mapent *ep = (struct mapent *)(mp+1);
 
-#include "../h/param.h"
-#include "../h/systm.h"
-#include "../h/map.h"
-#include "../h/dir.h"
-#include "../h/user.h"
-#include "../h/proc.h"
-#include "../h/mtpr.h"
-#include "../h/text.h"
+	mp->m_name = name;
+/* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */
+	/*
+	 * One of the mapsize slots is taken by the map structure,
+	 * segments has size 0 and addr 0, and acts as a delimiter.
+	 * We insure that we never use segments past the end of
+	 * the array which is given by mp->m_limit.
+	 * Instead, when excess segments occur we discard some resources.
+	 */
+	mp->m_limit = (struct mapent *)&mp[mapsize];
+	/*
+	 * Simulate a rmfree(), but with the option to
+	 * call with size 0 and addr 0 when we just want
+	 * to initialize without freeing.
+	 */
+	ep->m_size = size;
+	ep->m_addr = addr;
+	(++ep)->m_size = 0;
+	ep->m_addr = 0;
+}
 
 /*
  * Allocate 'size' units from the given
- * map. Return the base of the allocated
- * space.
+ * map. Return the base of the allocated space.
  * In a map, the addresses are increasing and the
  * list is terminated by a 0 size.
- * The swap map unit is 512 bytes.
+ *
  * Algorithm is first-fit.
+ *
+ * This routine knows about the interleaving of the swapmap
+ * and handles that.
  */
-malloc(mp, size)
-struct map *mp;
+long
+rmalloc(mp, size)
+	register struct map *mp;
+	long size;
 {
-	register int a;
-	register struct map *bp;
+	register struct mapent *ep = (struct mapent *)(mp+1);
+	register int addr;
+	register struct mapent *bp;
+	swblk_t first, rest;
 
-	if (size <= 0)
-		panic("malloc");
-	for (bp=mp; bp->m_size; bp++) {
+	if (size <= 0 || mp == swapmap && size > dmmax)
+		panic("rmalloc");
+	/*
+	 * Search for a piece of the resource map which has enough
+	 * free space to accomodate the request.
+	 */
+	for (bp = ep; bp->m_size; bp++) {
 		if (bp->m_size >= size) {
-			a = bp->m_addr;
+			/*
+			 * If allocating from swapmap,
+			 * then have to respect interleaving
+			 * boundaries.
+			 */
+			if (mp == swapmap && nswdev > 1 &&
+			    (first = dmmax - bp->m_addr%dmmax) < size) {
+				if (bp->m_size - first < size)
+					continue;
+				addr = bp->m_addr + first;
+				rest = bp->m_size - first - size;
+				bp->m_size = first;
+				if (rest)
+					rmfree(swapmap, rest, addr+size);
+				return (addr);
+			}
+			/*
+			 * Allocate from the map.
+			 * If there is no space left of the piece
+			 * we allocated from, move the rest of
+			 * the pieces to the left.
+			 */
+			addr = bp->m_addr;
 			bp->m_addr += size;
 			if ((bp->m_size -= size) == 0) {
 				do {
@@ -36,41 +133,63 @@ struct map *mp;
 					(bp-1)->m_addr = bp->m_addr;
 				} while ((bp-1)->m_size = bp->m_size);
 			}
-			if (mp == swapmap && a % CLSIZE)
-				panic("malloc swapmap");
-			return(a);
+			if (mp == swapmap && addr % CLSIZE)
+				panic("rmalloc swapmap");
+			return (addr);
 		}
 	}
-	return(0);
+	return (0);
 }
 
 /*
- * Free the previously allocated space aa
+ * Free the previously allocated space at addr
  * of size units into the specified map.
- * Sort aa into map and combine on
+ * Sort addr into map and combine on
  * one or both ends if possible.
  */
-mfree(mp, size, a)
-struct map *mp;
-register int size, a;
+rmfree(mp, size, addr)
+	struct map *mp;
+	long size, addr;
 {
-	register struct map *bp;
+	struct mapent *firstbp;
+	register struct mapent *bp;
 	register int t;
 
-	if (a <= 0)
-		panic("mfree addr");
-	if (size <= 0)
-		panic("mfree size");
-	bp = mp;
-	for (; bp->m_addr<=a && bp->m_size!=0; bp++)
+	/*
+	 * Both address and size must be
+	 * positive, or the protocol has broken down.
+	 */
+	if (addr <= 0 || size <= 0)
+		goto badrmfree;
+	/*
+	 * Locate the piece of the map which starts after the
+	 * returned space (or the end of the map).
+	 */
+	firstbp = bp = (struct mapent *)(mp + 1);
+	for (; bp->m_addr <= addr && bp->m_size != 0; bp++)
 		continue;
-	if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size > a)
-		panic("mfree begov");
-	if (a+size > bp->m_addr && bp->m_size)
-		panic("mfree endov");
-	if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size == a) {
+	/*
+	 * If the piece on the left abuts us,
+	 * then we should combine with it.
+	 */
+	if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) {
+		/*
+		 * Check no overlap (internal error).
+		 */
+		if ((bp-1)->m_addr+(bp-1)->m_size > addr)
+			goto badrmfree;
+		/*
+		 * Add into piece on the left by increasing its size.
+		 */
 		(bp-1)->m_size += size;
-		if (a+size == bp->m_addr) {
+		/*
+		 * If the combined piece abuts the piece on
+		 * the right now, compress it in also,
+		 * by shifting the remaining pieces of the map over.
+		 */
+		if (bp->m_addr && addr+size >= bp->m_addr) {
+			if (addr+size > bp->m_addr)
+				goto badrmfree;
 			(bp-1)->m_size += bp->m_size;
 			while (bp->m_size) {
 				bp++;
@@ -78,23 +197,146 @@ register int size, a;
 				(bp-1)->m_size = bp->m_size;
 			}
 		}
-	} else {
-		if (a+size == bp->m_addr && bp->m_size) {
-			bp->m_addr -= size;
-			bp->m_size += size;
-		} else if (size) {
-			do {
-				t = bp->m_addr;
-				bp->m_addr = a;
-				a = t;
-				t = bp->m_size;
-				bp->m_size = size;
-				bp++;
-			} while (size = t);
-		}
+		goto done;
 	}
+	/*
+	 * Don't abut on the left, check for abutting on
+	 * the right.
+	 */
+	if (addr+size >= bp->m_addr && bp->m_size) {
+		if (addr+size > bp->m_addr)
+			goto badrmfree;
+		bp->m_addr -= size;
+		bp->m_size += size;
+		goto done;
+	}
+	/*
+	 * Don't abut at all.  Make a new entry
+	 * and check for map overflow.
+	 */
+	do {
+		t = bp->m_addr;
+		bp->m_addr = addr;
+		addr = t;
+		t = bp->m_size;
+		bp->m_size = size;
+		bp++;
+	} while (size = t);
+	/*
+	 * Segment at bp is to be the delimiter;
+	 * If there is not room for it 
+	 * then the table is too full
+	 * and we must discard something.
+	 */
+	if (bp+1 > mp->m_limit) {
+		/*
+		 * Back bp up to last available segment.
+		 * which contains a segment already and must
+		 * be made into the delimiter.
+		 * Discard second to last entry,
+		 * since it is presumably smaller than the last
+		 * and move the last entry back one.
+		 */
+		bp--;
+		printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name,
+		    (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size);
+		bp[-1] = bp[0];
+		bp[0].m_size = bp[0].m_addr = 0;
+	}
+done:
+	/*
+	 * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE!
+	 */
 	if ((mp == kernelmap) && kmapwnt) {
 		kmapwnt = 0;
 		wakeup((caddr_t)kernelmap);
 	}
+	return;
+badrmfree:
+	panic("bad rmfree");
+}
+
+/*
+ * Allocate 'size' units from the given map, starting at address 'addr'.
+ * Return 'addr' if successful, 0 if not.
+ * This may cause the creation or destruction of a resource map segment.
+ *
+ * This routine will return failure status if there is not enough room
+ * for a required additional map segment.
+ *
+ * An attempt to use this on 'swapmap' will result in
+ * a failure return.  This is due mainly to laziness and could be fixed
+ * to do the right thing, although it probably will never be used.
+ */
+rmget(mp, size, addr)
+	register struct map *mp;
+{
+	register struct mapent *ep = (struct mapent *)(mp+1);
+	register struct mapent *bp, *bp2;
+
+	if (size <= 0)
+		panic("rmget");
+	if (mp == swapmap)
+		return (0);
+	/*
+	 * Look for a map segment containing the requested address.
+	 * If none found, return failure.
+	 */
+	for (bp = ep; bp->m_size; bp++)
+		if (bp->m_addr <= addr && bp->m_addr + bp->m_size > addr)
+			break;
+	if (bp->m_size == 0)
+		return (0);
+
+	/*
+	 * If segment is too small, return failure.
+	 * If big enough, allocate the block, compressing or expanding
+	 * the map as necessary.
+	 */
+	if (bp->m_addr + bp->m_size < addr + size)
+		return (0);
+	if (bp->m_addr == addr)
+		if (bp->m_addr + bp->m_size == addr + size) {
+			/*
+			 * Allocate entire segment and compress map
+			 */
+			bp2 = bp;
+			while (bp2->m_size) {
+				bp2++;
+				(bp2-1)->m_addr = bp2->m_addr;
+				(bp2-1)->m_size = bp2->m_size;
+			}
+		} else {
+			/*
+			 * Allocate first part of segment
+			 */
+			bp->m_addr += size;
+			bp->m_size -= size;
+		}
+	else
+		if (bp->m_addr + bp->m_size == addr + size) {
+			/*
+			 * Allocate last part of segment
+			 */
+			bp->m_size -= size;
+		} else {
+			/*
+			 * Allocate from middle of segment, but only
+			 * if table can be expanded.
+			 */
+			for (bp2=bp; bp2->m_size; bp2++)
+				;
+			if (bp2 + 1 >= mp->m_limit)
+				return (0);
+			while (bp2 > bp) {
+				(bp2+1)->m_addr = bp2->m_addr;
+				(bp2+1)->m_size = bp2->m_size;
+				bp2--;
+			}
+			(bp+1)->m_addr = addr + size;
+			(bp+1)->m_size =
+			    bp->m_addr + bp->m_size - (addr + size);
+			bp->m_size = addr - bp->m_addr;
+		}
+	return (addr);
 }