/* subr_rmap.c.sav 4.4 81/03/09 */
* 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
* 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
rminit(mp, size, addr, name, mapsize)
register struct mapent *ep = (struct mapent *)(mp+1);
/* 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.
* 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.
* This routine knows about the interleaving of the swapmap
register struct mapent *ep = (struct mapent *)(mp+1);
register struct mapent *bp;
if (size <= 0 || mp == swapmap && size > DMMAX)
* 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
(first = DMMAX - bp->m_addr%DMMAX) < bp->m_size) {
if (bp->m_size - first < size)
addr = bp->m_addr + first;
rest = bp->m_size - first - size;
rmfree(swapmap, rest, addr+size);
* If there is no space left of the piece
* we allocated from, move the rest of
* the pieces to the left.
if ((bp->m_size -= size) == 0) {
(bp-1)->m_addr = bp->m_addr;
} while ((bp-1)->m_size = bp->m_size);
if (mp == swapmap && addr % CLSIZE)
panic("rmalloc swapmap");
* Free the previously allocated space at addr
* of size units into the specified map.
* Sort addr into map and combine on
* one or both ends if possible.
register struct mapent *bp;
* Both address and size must be
* positive, or the protocol has broken down.
if (addr <= 0 || size <= 0)
* 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++)
* 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)
* Add into piece on the left by increasing its 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)
(bp-1)->m_size += bp->m_size;
(bp-1)->m_addr = bp->m_addr;
(bp-1)->m_size = bp->m_size;
* Don't abut on the left, check for abutting on
if (addr+size >= bp->m_addr && bp->m_size) {
if (addr+size > bp->m_addr)
* Don't abut at all. Make a new entry
* and check for map overflow.
* 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.
printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name,
(bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size);
bp[0].m_size = bp[0].m_addr = 0;
* THIS IS RIDICULOUS... IT DOESN'T BELONG HERE!
if ((mp == kernelmap) && kmapwnt) {
wakeup((caddr_t)kernelmap);