1652861d2Smckusick/* 2*8794991dSmckusick * Copyright (c) 1982, 1986 Regents of the University of California. 3652861d2Smckusick * All rights reserved. The Berkeley software License Agreement 4652861d2Smckusick * specifies the terms and conditions for redistribution. 5652861d2Smckusick * 6*8794991dSmckusick * @(#)subr_rmap.c.sav 7.1 (Berkeley) 06/05/86 7652861d2Smckusick */ 85594347bSbill 98d4ee905Sbloom#include "param.h" 108d4ee905Sbloom#include "systm.h" 118d4ee905Sbloom#include "map.h" 128d4ee905Sbloom#include "dir.h" 138d4ee905Sbloom#include "user.h" 148d4ee905Sbloom#include "proc.h" 158d4ee905Sbloom#include "text.h" 168d4ee905Sbloom#include "kernel.h" 175594347bSbill 185594347bSbill/* 192670a140Swnj * Resource map handling routines. 202670a140Swnj * 212670a140Swnj * A resource map is an array of structures each 222670a140Swnj * of which describes a segment of the address space of an available 232670a140Swnj * resource. The segments are described by their base address and 242670a140Swnj * length, and sorted in address order. Each resource map has a fixed 252670a140Swnj * maximum number of segments allowed. Resources are allocated 262670a140Swnj * by taking part or all of one of the segments of the map. 272670a140Swnj * 282670a140Swnj * Returning of resources will require another segment if 292670a140Swnj * the returned resources are not adjacent in the address 302670a140Swnj * space to an existing segment. If the return of a segment 312670a140Swnj * would require a slot which is not available, then one of 322670a140Swnj * the resource map segments is discarded after a warning is printed. 332670a140Swnj * Returning of resources may also cause the map to collapse 342670a140Swnj * by coalescing two existing segments and the returned space 352670a140Swnj * into a single segment. In this case the resource map is 362670a140Swnj * made smaller by copying together to fill the resultant gap. 372670a140Swnj * 382670a140Swnj * N.B.: the current implementation uses a dense array and does 392670a140Swnj * not admit the value ``0'' as a legal address, since that is used 402670a140Swnj * as a delimiter. 412670a140Swnj */ 422670a140Swnj 432670a140Swnj/* 442670a140Swnj * Initialize map mp to have (mapsize-2) segments 452670a140Swnj * and to be called ``name'', which we print if 462670a140Swnj * the slots become so fragmented that we lose space. 472670a140Swnj * The map itself is initialized with size elements free 482670a140Swnj * starting at addr. 492670a140Swnj */ 502670a140Swnjrminit(mp, size, addr, name, mapsize) 512670a140Swnj register struct map *mp; 5255c5ccafSroot long size, addr; 532670a140Swnj char *name; 542670a140Swnj int mapsize; 552670a140Swnj{ 562670a140Swnj register struct mapent *ep = (struct mapent *)(mp+1); 572670a140Swnj 582670a140Swnj mp->m_name = name; 592670a140Swnj/* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ 602670a140Swnj /* 612670a140Swnj * One of the mapsize slots is taken by the map structure, 622670a140Swnj * segments has size 0 and addr 0, and acts as a delimiter. 632670a140Swnj * We insure that we never use segments past the end of 642670a140Swnj * the array which is given by mp->m_limit. 652670a140Swnj * Instead, when excess segments occur we discard some resources. 662670a140Swnj */ 672670a140Swnj mp->m_limit = (struct mapent *)&mp[mapsize]; 682670a140Swnj /* 692670a140Swnj * Simulate a rmfree(), but with the option to 702670a140Swnj * call with size 0 and addr 0 when we just want 712670a140Swnj * to initialize without freeing. 722670a140Swnj */ 732670a140Swnj ep->m_size = size; 742670a140Swnj ep->m_addr = addr; 752670a140Swnj} 762670a140Swnj 772670a140Swnj/* 785594347bSbill * Allocate 'size' units from the given 792670a140Swnj * map. Return the base of the allocated space. 805594347bSbill * In a map, the addresses are increasing and the 815594347bSbill * list is terminated by a 0 size. 822670a140Swnj * 835594347bSbill * Algorithm is first-fit. 842670a140Swnj * 852670a140Swnj * This routine knows about the interleaving of the swapmap 862670a140Swnj * and handles that. 875594347bSbill */ 8877ef50e9Srootlong 892670a140Swnjrmalloc(mp, size) 902670a140Swnj register struct map *mp; 9177ef50e9Sroot long size; 925594347bSbill{ 932670a140Swnj register struct mapent *ep = (struct mapent *)(mp+1); 942670a140Swnj register int addr; 952670a140Swnj register struct mapent *bp; 96bb82ed02Sbill swblk_t first, rest; 975594347bSbill 9847ccb777Ssam if (size <= 0 || mp == swapmap && size > dmmax) 992670a140Swnj panic("rmalloc"); 1002670a140Swnj /* 1012670a140Swnj * Search for a piece of the resource map which has enough 1022670a140Swnj * free space to accomodate the request. 1032670a140Swnj */ 1042670a140Swnj for (bp = ep; bp->m_size; bp++) { 1055594347bSbill if (bp->m_size >= size) { 1062670a140Swnj /* 1072670a140Swnj * If allocating from swapmap, 1082670a140Swnj * then have to respect interleaving 1092670a140Swnj * boundaries. 1102670a140Swnj */ 11147ccb777Ssam if (mp == swapmap && nswdev > 1 && 11247ccb777Ssam (first = dmmax - bp->m_addr%dmmax) < bp->m_size) { 113bb82ed02Sbill if (bp->m_size - first < size) 114bb82ed02Sbill continue; 1152670a140Swnj addr = bp->m_addr + first; 116bb82ed02Sbill rest = bp->m_size - first - size; 117bb82ed02Sbill bp->m_size = first; 118bb82ed02Sbill if (rest) 1192670a140Swnj rmfree(swapmap, rest, addr+size); 1202670a140Swnj return (addr); 121bb82ed02Sbill } 1222670a140Swnj /* 1232670a140Swnj * Allocate from the map. 1242670a140Swnj * If there is no space left of the piece 1252670a140Swnj * we allocated from, move the rest of 1262670a140Swnj * the pieces to the left. 1272670a140Swnj */ 1282670a140Swnj addr = bp->m_addr; 1295594347bSbill bp->m_addr += size; 1305594347bSbill if ((bp->m_size -= size) == 0) { 1315594347bSbill do { 1325594347bSbill bp++; 1335594347bSbill (bp-1)->m_addr = bp->m_addr; 1345594347bSbill } while ((bp-1)->m_size = bp->m_size); 1355594347bSbill } 1362670a140Swnj if (mp == swapmap && addr % CLSIZE) 1372670a140Swnj panic("rmalloc swapmap"); 1382670a140Swnj return (addr); 1395594347bSbill } 1405594347bSbill } 1415594347bSbill return (0); 1425594347bSbill} 1435594347bSbill 1445594347bSbill/* 1452670a140Swnj * Free the previously allocated space at addr 1465594347bSbill * of size units into the specified map. 1472670a140Swnj * Sort addr into map and combine on 1485594347bSbill * one or both ends if possible. 1495594347bSbill */ 1502670a140Swnjrmfree(mp, size, addr) 1515594347bSbill struct map *mp; 15277ef50e9Sroot long size, addr; 1535594347bSbill{ 1542670a140Swnj struct mapent *firstbp; 1552670a140Swnj register struct mapent *bp; 1565594347bSbill register int t; 1575594347bSbill 1582670a140Swnj /* 1592670a140Swnj * Both address and size must be 1602670a140Swnj * positive, or the protocol has broken down. 1612670a140Swnj */ 1622670a140Swnj if (addr <= 0 || size <= 0) 1632670a140Swnj goto badrmfree; 1642670a140Swnj /* 1652670a140Swnj * Locate the piece of the map which starts after the 1662670a140Swnj * returned space (or the end of the map). 1672670a140Swnj */ 1682670a140Swnj firstbp = bp = (struct mapent *)(mp + 1); 1692670a140Swnj for (; bp->m_addr <= addr && bp->m_size != 0; bp++) 1705594347bSbill continue; 1712670a140Swnj /* 1722670a140Swnj * If the piece on the left abuts us, 1732670a140Swnj * then we should combine with it. 1742670a140Swnj */ 1752670a140Swnj if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { 1762670a140Swnj /* 1772670a140Swnj * Check no overlap (internal error). 1782670a140Swnj */ 1792670a140Swnj if ((bp-1)->m_addr+(bp-1)->m_size > addr) 1802670a140Swnj goto badrmfree; 1812670a140Swnj /* 1822670a140Swnj * Add into piece on the left by increasing its size. 1832670a140Swnj */ 1845594347bSbill (bp-1)->m_size += size; 1852670a140Swnj /* 1862670a140Swnj * If the combined piece abuts the piece on 1872670a140Swnj * the right now, compress it in also, 1882670a140Swnj * by shifting the remaining pieces of the map over. 1892670a140Swnj */ 1902670a140Swnj if (bp->m_addr && addr+size >= bp->m_addr) { 1912670a140Swnj if (addr+size > bp->m_addr) 1922670a140Swnj goto badrmfree; 1935594347bSbill (bp-1)->m_size += bp->m_size; 1945594347bSbill while (bp->m_size) { 1955594347bSbill bp++; 1965594347bSbill (bp-1)->m_addr = bp->m_addr; 1975594347bSbill (bp-1)->m_size = bp->m_size; 1985594347bSbill } 1995594347bSbill } 2002670a140Swnj goto done; 2012670a140Swnj } 2022670a140Swnj /* 2032670a140Swnj * Don't abut on the left, check for abutting on 2042670a140Swnj * the right. 2052670a140Swnj */ 2062670a140Swnj if (addr+size >= bp->m_addr && bp->m_size) { 2072670a140Swnj if (addr+size > bp->m_addr) 2082670a140Swnj goto badrmfree; 2095594347bSbill bp->m_addr -= size; 2105594347bSbill bp->m_size += size; 2112670a140Swnj goto done; 2122670a140Swnj } 2132670a140Swnj /* 2142670a140Swnj * Don't abut at all. Make a new entry 2152670a140Swnj * and check for map overflow. 2162670a140Swnj */ 2175594347bSbill do { 2185594347bSbill t = bp->m_addr; 2192670a140Swnj bp->m_addr = addr; 2202670a140Swnj addr = t; 2215594347bSbill t = bp->m_size; 2225594347bSbill bp->m_size = size; 2235594347bSbill bp++; 2245594347bSbill } while (size = t); 2252670a140Swnj /* 2262670a140Swnj * Segment at bp is to be the delimiter; 2272670a140Swnj * If there is not room for it 2282670a140Swnj * then the table is too full 2292670a140Swnj * and we must discard something. 2302670a140Swnj */ 2312670a140Swnj if (bp+1 > mp->m_limit) { 2322670a140Swnj /* 2332670a140Swnj * Back bp up to last available segment. 2342670a140Swnj * which contains a segment already and must 2352670a140Swnj * be made into the delimiter. 2362670a140Swnj * Discard second to last entry, 2372670a140Swnj * since it is presumably smaller than the last 2382670a140Swnj * and move the last entry back one. 2392670a140Swnj */ 2402670a140Swnj bp--; 24112fd36e8Swnj printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name, 2422670a140Swnj (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); 2432670a140Swnj bp[-1] = bp[0]; 2442670a140Swnj bp[0].m_size = bp[0].m_addr = 0; 2455594347bSbill } 2462670a140Swnjdone: 2472670a140Swnj /* 2482670a140Swnj * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE! 2492670a140Swnj */ 2505594347bSbill if ((mp == kernelmap) && kmapwnt) { 2515594347bSbill kmapwnt = 0; 2525594347bSbill wakeup((caddr_t)kernelmap); 2535594347bSbill } 2542670a140Swnj return; 2552670a140Swnjbadrmfree: 2562670a140Swnj panic("bad rmfree"); 2575594347bSbill} 25829485eeeSfeldman 25929485eeeSfeldman/* 26029485eeeSfeldman * Allocate 'size' units from the given map, starting at address 'addr'. 26129485eeeSfeldman * Return 'addr' if successful, 0 if not. 26229485eeeSfeldman * This may cause the creation or destruction of a resource map segment. 26329485eeeSfeldman * 26429485eeeSfeldman * This routine will return failure status if there is not enough room 26529485eeeSfeldman * for a required additional map segment. 26629485eeeSfeldman * 26729485eeeSfeldman * An attempt to use this on 'swapmap' will result in 26829485eeeSfeldman * a failure return. This is due mainly to laziness and could be fixed 26929485eeeSfeldman * to do the right thing, although it probably will never be used. 27029485eeeSfeldman */ 27129485eeeSfeldmanrmget(mp, size, addr) 27229485eeeSfeldman register struct map *mp; 27329485eeeSfeldman{ 27429485eeeSfeldman register struct mapent *ep = (struct mapent *)(mp+1); 27529485eeeSfeldman register struct mapent *bp, *bp2; 27629485eeeSfeldman 27729485eeeSfeldman if (size <= 0) 27829485eeeSfeldman panic("rmget"); 27929485eeeSfeldman if (mp == swapmap) 28029485eeeSfeldman return (0); 28129485eeeSfeldman /* 28229485eeeSfeldman * Look for a map segment containing the requested address. 28329485eeeSfeldman * If none found, return failure. 28429485eeeSfeldman */ 28529485eeeSfeldman for (bp = ep; bp->m_size; bp++) 28629485eeeSfeldman if (bp->m_addr <= addr && bp->m_addr + bp->m_size > addr) 28729485eeeSfeldman break; 28829485eeeSfeldman if (bp->m_size == 0) 28929485eeeSfeldman return (0); 29029485eeeSfeldman 29129485eeeSfeldman /* 29229485eeeSfeldman * If segment is too small, return failure. 29329485eeeSfeldman * If big enough, allocate the block, compressing or expanding 29429485eeeSfeldman * the map as necessary. 29529485eeeSfeldman */ 29629485eeeSfeldman if (bp->m_addr + bp->m_size < addr + size) 29729485eeeSfeldman return (0); 29829485eeeSfeldman if (bp->m_addr == addr) 29929485eeeSfeldman if (bp->m_addr + bp->m_size == addr + size) { 30029485eeeSfeldman /* 30129485eeeSfeldman * Allocate entire segment and compress map 30229485eeeSfeldman */ 30329485eeeSfeldman bp2 = bp; 30429485eeeSfeldman while (bp2->m_size) { 30529485eeeSfeldman bp2++; 30629485eeeSfeldman (bp2-1)->m_addr = bp2->m_addr; 30729485eeeSfeldman (bp2-1)->m_size = bp2->m_size; 30829485eeeSfeldman } 30929485eeeSfeldman } else { 31029485eeeSfeldman /* 31129485eeeSfeldman * Allocate first part of segment 31229485eeeSfeldman */ 31329485eeeSfeldman bp->m_addr += size; 31429485eeeSfeldman bp->m_size -= size; 31529485eeeSfeldman } 31629485eeeSfeldman else 31729485eeeSfeldman if (bp->m_addr + bp->m_size == addr + size) { 31829485eeeSfeldman /* 31929485eeeSfeldman * Allocate last part of segment 32029485eeeSfeldman */ 32129485eeeSfeldman bp->m_size -= size; 32229485eeeSfeldman } else { 32329485eeeSfeldman /* 32429485eeeSfeldman * Allocate from middle of segment, but only 32529485eeeSfeldman * if table can be expanded. 32629485eeeSfeldman */ 32729485eeeSfeldman for (bp2=bp; bp2->m_size; bp2++) 32829485eeeSfeldman ; 3292cde70a0Sbloom if (bp2 + 1 >= mp->m_limit) 33029485eeeSfeldman return (0); 33129485eeeSfeldman while (bp2 > bp) { 33229485eeeSfeldman (bp2+1)->m_addr = bp2->m_addr; 33329485eeeSfeldman (bp2+1)->m_size = bp2->m_size; 33429485eeeSfeldman bp2--; 33529485eeeSfeldman } 33629485eeeSfeldman (bp+1)->m_addr = addr + size; 33729485eeeSfeldman (bp+1)->m_size = 33829485eeeSfeldman bp->m_addr + bp->m_size - (addr + size); 33929485eeeSfeldman bp->m_size = addr - bp->m_addr; 34029485eeeSfeldman } 34129485eeeSfeldman return (addr); 34229485eeeSfeldman} 343