2.11BSD/sys/sys/subr_rmap.c
/*
* Copyright (c) 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 1.2 (2.11BSD GTE) 12/24/92
*/
#include "param.h"
#include "systm.h"
#include "map.h"
#include "vm.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 or size, since that is used as a
* delimiter.
*/
/*
* Allocate 'size' units from the given map. Return the base of the
* allocated space. In a map, the addresses are increasing and the
* list is terminated by a 0 size.
*
* Algorithm is first-fit.
*/
memaddr
malloc(mp, size)
struct map *mp;
register size_t size;
{
register struct mapent *bp, *ep;
memaddr addr;
int retry;
if (!size)
panic("malloc: size = 0");
/*
* Search for a piece of the resource map which has enough
* free space to accomodate the request.
*/
retry = 0;
again:
for (bp = mp->m_map; bp->m_size; ++bp)
if (bp->m_size >= size) {
/*
* Allocate from the map. If we allocated the entire
* piece, move the rest of the map to the left.
*/
addr = bp->m_addr;
bp->m_size -= size;
if (bp->m_size)
bp->m_addr += size;
else for (ep = bp;; ++ep) {
*ep = *++bp;
if (!bp->m_size)
break;
}
#ifdef UCB_METER
if (mp == coremap)
freemem -= size;
#endif
return(addr);
}
/* no entries big enough */
if (!retry++) {
if (mp == swapmap) {
printf("short of swap\n");
xumount(NODEV);
goto again;
}
else if (mp == coremap) {
xuncore(size);
goto again;
}
}
return((memaddr)NULL);
}
/*
* Free the previously allocated size units at addr into the specified
* map. Sort addr into map and combine on one or both ends if possible.
*/
mfree(mp, size, addr)
struct map *mp;
size_t size;
register memaddr addr;
{
register struct mapent *bp, *ep;
struct mapent *start;
if (!size)
return;
/* the address must not be 0, or the protocol has broken down. */
if (!addr)
panic("mfree: addr = 0");
if (mp == coremap) {
if (runin) {
runin = 0;
wakeup((caddr_t)&runin);
}
#ifdef UCB_METER
freemem += size;
#endif
}
/*
* locate the piece of the map which starts after the
* returned space (or the end of the map).
*/
for (bp = mp->m_map; bp->m_size && bp->m_addr <= addr; ++bp);
/* if there is a piece on the left abutting us, combine with it. */
ep = bp - 1;
if (bp != mp->m_map && ep->m_addr + ep->m_size >= addr) {
#ifdef DIAGNOSTIC
/* any overlap is an internal error */
if (ep->m_addr + ep->m_size > addr)
panic("mfree overlap #1");
#endif
/* add into piece on the left by increasing its size. */
ep->m_size += size;
/*
* 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_size && addr + size >= bp->m_addr) {
#ifdef DIAGNOSTIC
if (addr + size > bp->m_addr)
panic("mfree overlap #2");
#endif
ep->m_size += bp->m_size;
do {
*++ep = *++bp;
} while (bp->m_size);
}
return;
}
/* if doesn't abut on the left, check for abutting on the right. */
if (bp->m_size && addr + size >= bp->m_addr) {
#ifdef DIAGNOSTIC
if (addr + size > bp->m_addr)
panic("mfree overlap #3");
#endif
bp->m_addr = addr;
bp->m_size += size;
return;
}
/* doesn't abut. Make a new entry and check for map overflow. */
for (start = bp; bp->m_size; ++bp);
if (++bp > mp->m_limit)
/*
* too many segments; if this happens, the correct fix
* is to make the map bigger; you can't afford to lose
* chunks of the map. If you need to implement recovery,
* use the above "for" loop to find the smallest entry
* and toss it.
*/
printf("%s: overflow, lost %u clicks at 0%o\n",
mp->m_name, size, addr);
else {
for (ep = bp - 1; ep >= start; *bp-- = *ep--);
start->m_addr = addr;
start->m_size = size;
}
}
/*
* Allocate resources for the three segments of a process (data, stack
* and u.), attempting to minimize the cost of failure part-way through.
* Since the segments are located successively, it is best for the sizes
* to be in decreasing order; generally, data, stack, then u. will be
* best. Returns NULL on failure, address of u. on success.
*/
memaddr
malloc3(mp, d_size, s_size, u_size, a)
struct map *mp;
size_t d_size, s_size, u_size;
memaddr a[3];
{
register struct mapent *bp, *remap;
register int next;
struct mapent *madd[3];
size_t sizes[3];
int found, retry;
sizes[0] = d_size; sizes[1] = s_size; sizes[2] = u_size;
retry = 0;
again:
/*
* note, this has to work for d_size and s_size of zero,
* since init() comes in that way.
*/
madd[0] = madd[1] = madd[2] = remap = NULL;
for (found = 0, bp = mp->m_map; bp->m_size; ++bp)
for (next = 0; next < 3; ++next)
if (!madd[next] && sizes[next] <= bp->m_size) {
madd[next] = bp;
bp->m_size -= sizes[next];
if (!bp->m_size && !remap)
remap = bp;
if (++found == 3)
goto resolve;
}
/* couldn't get it all; restore the old sizes, try again */
for (next = 0; next < 3; ++next)
if (madd[next])
madd[next]->m_size += sizes[next];
if (!retry++)
if (mp == swapmap) {
printf("short of swap\n");
xumount(NODEV);
goto again;
}
else if (mp == coremap) {
xuncore(sizes[2]); /* smallest to largest; */
xuncore(sizes[1]); /* free up minimum space */
xuncore(sizes[0]);
goto again;
}
return((memaddr)NULL);
resolve:
/* got it all, update the addresses. */
for (next = 0; next < 3; ++next) {
bp = madd[next];
a[next] = bp->m_addr;
bp->m_addr += sizes[next];
}
#ifdef UCB_METER
if (mp == coremap)
freemem -= d_size + s_size + u_size;
#endif
/* remove any entries of size 0; addr of 0 terminates */
if (remap)
for (bp = remap + 1;; ++bp)
if (bp->m_size || !bp->m_addr) {
*remap++ = *bp;
if (!bp->m_addr)
break;
}
return(a[2]);
}