2.9BSD/usr/src/sys/sys/malloc.c
#include "param.h"
#include <sys/systm.h>
#include <sys/map.h>
#ifdef UCB_METER
#include <sys/vm.h>
#endif
/*
* SCCS id @(#)malloc.c 2.1 (Berkeley) 8/5/83
*/
/*
* 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 memaddr addr;
register struct mapent *bp;
int retry = 0;
if (size == 0)
panic("malloc");
/*
* Search for a piece of the resource map which has enough
* free space to accomodate the request.
*/
again:
for (bp = mp->m_map; bp->m_size; bp++) {
if (bp->m_size >= size) {
/*
* 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);
}
#ifdef UCB_METER
if (mp == coremap)
freemem -= size;
#endif
return (addr);
}
}
if (mp == swapmap && retry++ == 0) {
/*
* Attempt to avoid running out of swap--
* free ALL unused sticky text segments.
*/
printf("short of swap\n");
xumount(NODEV);
goto again;
}
return (0);
}
/*
* 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.
*/
mfree(mp, size, addr)
struct map *mp;
size_t size;
register memaddr addr;
{
struct mapent *firstbp;
register struct mapent *bp;
register u_short t;
if (size == 0)
return;
#ifdef DIAGNOSTIC
/*
* The address must be
* positive, or the protocol has broken down.
*/
if (addr == 0)
goto badmfree;
#endif
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).
*/
firstbp = bp = mp->m_map;
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) {
#ifdef DIAGNOSTIC
/*
* Check no overlap (internal error).
*/
if ((bp-1)->m_addr+(bp-1)->m_size > addr)
goto badmfree;
#endif
/*
* 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) {
#ifdef DIAGNOSTIC
if (addr+size > bp->m_addr)
goto badmfree;
#endif
(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;
}
}
goto done;
}
/*
* Don't abut on the left, check for abutting on
* the right.
*/
if (addr+size >= bp->m_addr && bp->m_size) {
#ifdef DIAGNOSTIC
if (addr+size > bp->m_addr)
goto badmfree;
#endif
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: map 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->m_size = bp->m_addr = 0;
}
done:
return;
#ifdef DIAGNOSTIC
badmfree:
panic("bad mfree");
#endif
}
#ifdef VIRUS_VFORK
/*
* 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, with a[2] set to NULL (since a[2] is for u.).
* Returns u. address (a[2]) on success, with all
* addresses placed in a[].
*/
memaddr
malloc3(mp,size0,size1,size2,a)
struct map *mp;
size_t size0, size1, size2;
memaddr a[3];
{
register struct mapent *bp, *ep;
struct mapent *found[3];
size_t sizes[3];
register next;
int retry = 0;
sizes[0] = size0, sizes[1] = size1, sizes[2] = size2;
again:
next = 0;
for (bp=mp->m_map; bp->m_addr; ) {
if (bp->m_size >= sizes[next]) {
found[next] = bp;
bp->m_size -= sizes[next];
if (++next > 2)
break;
bp = mp->m_map;
}
else bp++;
}
if (next < 3) {
/*
* Couldn't get it all. Restore the old sizes.
*/
while (next--)
found[next]->m_size += sizes[next];
if (mp == swapmap && retry++ == 0) {
/*
* Attempt to avoid running out of swap--
* free ALL unused sticky text segments.
*/
printf("short of swap\n");
xumount(NODEV);
goto again;
}
a[2] = NULL;
} else {
/*
* Got it all. Update the addresses.
*/
for (next=0; next<3; next++) {
bp = found[next];
a[next] = bp->m_addr;
bp->m_addr += sizes[next];
#ifdef UCB_METER
if (mp == coremap)
freemem -= sizes[next];
#endif
}
/*
* Find the first segment with 0 size.
*/
for (bp=mp->m_map; bp->m_size; bp++)
;
/*
* Copy back any remaining entries to remove entries
* with size 0. addr of 0 terminates.
*/
if (bp->m_addr) {
ep = bp;
for (;;) {
if ((bp->m_size == 0) && (bp->m_addr != 0))
bp++;
else {
ep->m_size = bp->m_size;
if ((ep++->m_addr = bp++->m_addr) == 0)
break;
}
}
/*
* Eliminate garbage past end.
*/
bp--;
while (ep < bp) {
ep->m_size = 0;
ep++->m_addr = 0;
}
}
}
return(a[2]);
}
#endif VIRUS_VFORK