4.4BSD/usr/src/sys/kern/subr_rmap.c
/*-
* Copyright (c) 1982, 1986, 1993
* The Regents of the University of California. All rights reserved.
*
* This module is believed to contain source code proprietary to AT&T.
* Use and redistribution is subject to the Berkeley Software License
* Agreement and your Software Agreement with AT&T (Western Electric).
*
* @(#)subr_rmap.c 8.1 (Berkeley) 6/10/93
*/
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/map.h>
#include <sys/dmap.h> /* XXX */
#include <sys/proc.h>
#include <sys/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.
*/
void
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);
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;
}
/*
* A piece of memory of at least size units is allocated from the
* specified map using a first-fit algorithm. It returns the starting
* address of the allocated space.
*
* This routine knows about and handles the interleaving of the swapmap.
*/
long
rmalloc(mp, size)
register struct map *mp;
long size;
{
register struct mapent *ep = (struct mapent *)(mp+1);
register int addr;
register struct mapent *bp;
swblk_t first, rest;
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) {
/*
* 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 {
bp++;
(bp-1)->m_addr = bp->m_addr;
} while ((bp-1)->m_size = bp->m_size);
}
if (mp == swapmap && addr % CLSIZE)
panic("rmalloc swapmap");
return (addr);
}
}
return (0);
}
/*
* The previously allocated space at addr of size units is freed
* into the specified map. This routine is responsible for sorting
* the frred space into the correct location in the map, and coalescing
* it with free space on either side if they adjoin.
*/
void
rmfree(mp, size, addr)
struct map *mp;
long size, addr;
{
struct mapent *firstbp;
register struct mapent *bp;
register int t;
/*
* 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 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 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_addr = bp->m_addr;
(bp-1)->m_size = bp->m_size;
}
}
return;
}
/*
* 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;
return;
}
/*
* 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;
}
return;
badrmfree:
panic("bad rmfree");
}