X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/15f789eaa09d58cbf06b92b82357da8397681e9e..b725a0caed0e5e642ad56eca5a13c8c68996a127:/usr/src/sys/kern/subr_rmap.c.sav diff --git a/usr/src/sys/kern/subr_rmap.c.sav b/usr/src/sys/kern/subr_rmap.c.sav index 4724e9ceb1..187bc193dc 100644 --- a/usr/src/sys/kern/subr_rmap.c.sav +++ b/usr/src/sys/kern/subr_rmap.c.sav @@ -1,4 +1,4 @@ -/* subr_rmap.c.sav 4.1 %G% */ +/* subr_rmap.c.sav 4.2 %G% */ #include "../h/param.h" #include "../h/systm.h" @@ -9,38 +9,115 @@ #include "../h/mtpr.h" #include "../h/text.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; + int 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; +} + /* * 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; +rmalloc(mp, size) + register struct map *mp; { - 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 || mp == swapmap && size > DMMAX) - panic("malloc"); - for (bp=mp; bp->m_size; bp++) { + 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 && (first = DMMAX - bp->m_addr%DMMAX) < bp->m_size) { if (bp->m_size - first < size) continue; - a = bp->m_addr + first; + addr = bp->m_addr + first; rest = bp->m_size - first - size; bp->m_size = first; if (rest) - mfree(swapmap, rest, a+size); - return (a); + rmfree(swapmap, rest, addr+size); + return (addr); } - a = bp->m_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 { @@ -48,41 +125,63 @@ struct map *mp; (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; + register int 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++; @@ -90,23 +189,61 @@ register int size, a; (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 overflow, 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"); }