149589Sbostic /*- 249589Sbostic * Copyright (c) 1982, 1986 The Regents of the University of California. 349589Sbostic * All rights reserved. 423382Smckusick * 549589Sbostic * %sccs.include.proprietary.c% 649589Sbostic * 7*49673Smckusick * @(#)subr_rmap.c 7.9 (Berkeley) 05/11/91 823382Smckusick */ 927Sbill 1017094Sbloom #include "param.h" 1117094Sbloom #include "systm.h" 1217094Sbloom #include "map.h" 1347540Skarels #include "dmap.h" /* XXX */ 1417094Sbloom #include "proc.h" 1517094Sbloom #include "kernel.h" 1627Sbill 1727Sbill /* 182781Swnj * Resource map handling routines. 192781Swnj * 202781Swnj * A resource map is an array of structures each 212781Swnj * of which describes a segment of the address space of an available 222781Swnj * resource. The segments are described by their base address and 232781Swnj * length, and sorted in address order. Each resource map has a fixed 242781Swnj * maximum number of segments allowed. Resources are allocated 252781Swnj * by taking part or all of one of the segments of the map. 262781Swnj * 272781Swnj * Returning of resources will require another segment if 282781Swnj * the returned resources are not adjacent in the address 292781Swnj * space to an existing segment. If the return of a segment 302781Swnj * would require a slot which is not available, then one of 312781Swnj * the resource map segments is discarded after a warning is printed. 322781Swnj * Returning of resources may also cause the map to collapse 332781Swnj * by coalescing two existing segments and the returned space 342781Swnj * into a single segment. In this case the resource map is 352781Swnj * made smaller by copying together to fill the resultant gap. 362781Swnj * 372781Swnj * N.B.: the current implementation uses a dense array and does 382781Swnj * not admit the value ``0'' as a legal address, since that is used 392781Swnj * as a delimiter. 402781Swnj */ 412781Swnj 422781Swnj /* 432781Swnj * Initialize map mp to have (mapsize-2) segments 442781Swnj * and to be called ``name'', which we print if 452781Swnj * the slots become so fragmented that we lose space. 462781Swnj * The map itself is initialized with size elements free 472781Swnj * starting at addr. 482781Swnj */ 492781Swnj rminit(mp, size, addr, name, mapsize) 502781Swnj register struct map *mp; 518790Sroot long size, addr; 522781Swnj char *name; 532781Swnj int mapsize; 542781Swnj { 552781Swnj register struct mapent *ep = (struct mapent *)(mp+1); 562781Swnj 572781Swnj mp->m_name = name; 582781Swnj /* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ 592781Swnj /* 602781Swnj * One of the mapsize slots is taken by the map structure, 612781Swnj * segments has size 0 and addr 0, and acts as a delimiter. 622781Swnj * We insure that we never use segments past the end of 632781Swnj * the array which is given by mp->m_limit. 642781Swnj * Instead, when excess segments occur we discard some resources. 652781Swnj */ 662781Swnj mp->m_limit = (struct mapent *)&mp[mapsize]; 672781Swnj /* 682781Swnj * Simulate a rmfree(), but with the option to 692781Swnj * call with size 0 and addr 0 when we just want 702781Swnj * to initialize without freeing. 712781Swnj */ 722781Swnj ep->m_size = size; 732781Swnj ep->m_addr = addr; 7433605Skarels (++ep)->m_size = 0; 7533605Skarels ep->m_addr = 0; 762781Swnj } 772781Swnj 782781Swnj /* 79*49673Smckusick * A piece of memory of at least size units is allocated from the 80*49673Smckusick * specified map using a first-fit algorithm. It returns the starting 81*49673Smckusick * address of the allocated space. 822781Swnj * 83*49673Smckusick * This routine knows about and handles the interleaving of the swapmap. 8427Sbill */ 858766Sroot long 862781Swnj rmalloc(mp, size) 872781Swnj register struct map *mp; 888766Sroot long size; 8927Sbill { 902781Swnj register struct mapent *ep = (struct mapent *)(mp+1); 912781Swnj register int addr; 922781Swnj register struct mapent *bp; 93307Sbill swblk_t first, rest; 9427Sbill 9512489Ssam if (size <= 0 || mp == swapmap && size > dmmax) 962781Swnj panic("rmalloc"); 972781Swnj /* 982781Swnj * Search for a piece of the resource map which has enough 992781Swnj * free space to accomodate the request. 1002781Swnj */ 1012781Swnj for (bp = ep; bp->m_size; bp++) { 10227Sbill if (bp->m_size >= size) { 1032781Swnj /* 1042781Swnj * If allocating from swapmap, 1052781Swnj * then have to respect interleaving 1062781Swnj * boundaries. 1072781Swnj */ 10812489Ssam if (mp == swapmap && nswdev > 1 && 10941988Smckusick (first = dmmax - bp->m_addr%dmmax) < size) { 110307Sbill if (bp->m_size - first < size) 111307Sbill continue; 1122781Swnj addr = bp->m_addr + first; 113307Sbill rest = bp->m_size - first - size; 114307Sbill bp->m_size = first; 115307Sbill if (rest) 1162781Swnj rmfree(swapmap, rest, addr+size); 1172781Swnj return (addr); 118307Sbill } 1192781Swnj /* 1202781Swnj * Allocate from the map. 1212781Swnj * If there is no space left of the piece 1222781Swnj * we allocated from, move the rest of 1232781Swnj * the pieces to the left. 1242781Swnj */ 1252781Swnj addr = bp->m_addr; 12627Sbill bp->m_addr += size; 12727Sbill if ((bp->m_size -= size) == 0) { 12827Sbill do { 12927Sbill bp++; 13027Sbill (bp-1)->m_addr = bp->m_addr; 13127Sbill } while ((bp-1)->m_size = bp->m_size); 13227Sbill } 1332781Swnj if (mp == swapmap && addr % CLSIZE) 1342781Swnj panic("rmalloc swapmap"); 1352781Swnj return (addr); 13627Sbill } 13727Sbill } 1382781Swnj return (0); 13927Sbill } 14027Sbill 14127Sbill /* 142*49673Smckusick * The previously allocated space at addr of size units is freed 143*49673Smckusick * into the specified map. This routine is responsible for sorting 144*49673Smckusick * the frred space into the correct location in the map, and coalescing 145*49673Smckusick * it with free space on either side if they adjoin. 14627Sbill */ 1472781Swnj rmfree(mp, size, addr) 1482781Swnj struct map *mp; 1498766Sroot long size, addr; 15027Sbill { 1512781Swnj struct mapent *firstbp; 1522781Swnj register struct mapent *bp; 15327Sbill register int t; 15427Sbill 1552781Swnj /* 1562781Swnj * Both address and size must be 1572781Swnj * positive, or the protocol has broken down. 1582781Swnj */ 1592781Swnj if (addr <= 0 || size <= 0) 1602781Swnj goto badrmfree; 1612781Swnj /* 1622781Swnj * Locate the piece of the map which starts after the 1632781Swnj * returned space (or the end of the map). 1642781Swnj */ 1652781Swnj firstbp = bp = (struct mapent *)(mp + 1); 1662781Swnj for (; bp->m_addr <= addr && bp->m_size != 0; bp++) 16727Sbill continue; 1682781Swnj /* 1692781Swnj * If the piece on the left abuts us, 1702781Swnj * then we should combine with it. 1712781Swnj */ 1722781Swnj if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { 1732781Swnj /* 1742781Swnj * Check no overlap (internal error). 1752781Swnj */ 1762781Swnj if ((bp-1)->m_addr+(bp-1)->m_size > addr) 1772781Swnj goto badrmfree; 1782781Swnj /* 1792781Swnj * Add into piece on the left by increasing its size. 1802781Swnj */ 18127Sbill (bp-1)->m_size += size; 1822781Swnj /* 1832781Swnj * If the combined piece abuts the piece on 1842781Swnj * the right now, compress it in also, 1852781Swnj * by shifting the remaining pieces of the map over. 1862781Swnj */ 1872781Swnj if (bp->m_addr && addr+size >= bp->m_addr) { 1882781Swnj if (addr+size > bp->m_addr) 1892781Swnj goto badrmfree; 19027Sbill (bp-1)->m_size += bp->m_size; 19127Sbill while (bp->m_size) { 19227Sbill bp++; 19327Sbill (bp-1)->m_addr = bp->m_addr; 19427Sbill (bp-1)->m_size = bp->m_size; 19527Sbill } 19627Sbill } 19749281Shibler return; 19827Sbill } 1992781Swnj /* 2002781Swnj * Don't abut on the left, check for abutting on 2012781Swnj * the right. 2022781Swnj */ 2032781Swnj if (addr+size >= bp->m_addr && bp->m_size) { 2042781Swnj if (addr+size > bp->m_addr) 2052781Swnj goto badrmfree; 2062781Swnj bp->m_addr -= size; 2072781Swnj bp->m_size += size; 20849281Shibler return; 2092781Swnj } 2102781Swnj /* 2112781Swnj * Don't abut at all. Make a new entry 2122781Swnj * and check for map overflow. 2132781Swnj */ 2142781Swnj do { 2152781Swnj t = bp->m_addr; 2162781Swnj bp->m_addr = addr; 2172781Swnj addr = t; 2182781Swnj t = bp->m_size; 2192781Swnj bp->m_size = size; 2202781Swnj bp++; 2212781Swnj } while (size = t); 2222781Swnj /* 2232781Swnj * Segment at bp is to be the delimiter; 2242781Swnj * If there is not room for it 2252781Swnj * then the table is too full 2262781Swnj * and we must discard something. 2272781Swnj */ 2282781Swnj if (bp+1 > mp->m_limit) { 2292781Swnj /* 2302781Swnj * Back bp up to last available segment. 2312781Swnj * which contains a segment already and must 2322781Swnj * be made into the delimiter. 2332781Swnj * Discard second to last entry, 2342781Swnj * since it is presumably smaller than the last 2352781Swnj * and move the last entry back one. 2362781Swnj */ 2372781Swnj bp--; 2382937Swnj printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name, 2392781Swnj (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); 2402781Swnj bp[-1] = bp[0]; 2412781Swnj bp[0].m_size = bp[0].m_addr = 0; 2422781Swnj } 2432781Swnj return; 2442781Swnj badrmfree: 2452781Swnj panic("bad rmfree"); 24627Sbill } 247