-/* subr_rmap.c.sav 3.2 %G% */
+/*
+ * 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.sav 7.2 (Berkeley) %G%
+ */
+
+#include "param.h"
+#include "systm.h"
+#include "map.h"
+#include "dir.h"
+#include "user.h"
+#include "proc.h"
+#include "text.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;
+}
/*
* 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) < bp->m_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 {
(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++;
(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);
}