1/* subr_rmap.c.sav 4.4 81/03/09 */ 2 3#include "../h/param.h" 4#include "../h/systm.h" 5#include "../h/map.h" 6#include "../h/dir.h" 7#include "../h/user.h" 8#include "../h/proc.h" 9#include "../h/mtpr.h" 10#include "../h/text.h" 11 12/* 13 * Resource map handling routines. 14 * 15 * A resource map is an array of structures each 16 * of which describes a segment of the address space of an available 17 * resource. The segments are described by their base address and 18 * length, and sorted in address order. Each resource map has a fixed 19 * maximum number of segments allowed. Resources are allocated 20 * by taking part or all of one of the segments of the map. 21 * 22 * Returning of resources will require another segment if 23 * the returned resources are not adjacent in the address 24 * space to an existing segment. If the return of a segment 25 * would require a slot which is not available, then one of 26 * the resource map segments is discarded after a warning is printed. 27 * Returning of resources may also cause the map to collapse 28 * by coalescing two existing segments and the returned space 29 * into a single segment. In this case the resource map is 30 * made smaller by copying together to fill the resultant gap. 31 * 32 * N.B.: the current implementation uses a dense array and does 33 * not admit the value ``0'' as a legal address, since that is used 34 * as a delimiter. 35 */ 36 37/* 38 * Initialize map mp to have (mapsize-2) segments 39 * and to be called ``name'', which we print if 40 * the slots become so fragmented that we lose space. 41 * The map itself is initialized with size elements free 42 * starting at addr. 43 */ 44rminit(mp, size, addr, name, mapsize) 45 register struct map *mp; 46 int size, addr; 47 char *name; 48 int mapsize; 49{ 50 register struct mapent *ep = (struct mapent *)(mp+1); 51 52 mp->m_name = name; 53/* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ 54 /* 55 * One of the mapsize slots is taken by the map structure, 56 * segments has size 0 and addr 0, and acts as a delimiter. 57 * We insure that we never use segments past the end of 58 * the array which is given by mp->m_limit. 59 * Instead, when excess segments occur we discard some resources. 60 */ 61 mp->m_limit = (struct mapent *)&mp[mapsize]; 62 /* 63 * Simulate a rmfree(), but with the option to 64 * call with size 0 and addr 0 when we just want 65 * to initialize without freeing. 66 */ 67 ep->m_size = size; 68 ep->m_addr = addr; 69} 70 71/* 72 * Allocate 'size' units from the given 73 * map. Return the base of the allocated space. 74 * In a map, the addresses are increasing and the 75 * list is terminated by a 0 size. 76 * 77 * Algorithm is first-fit. 78 * 79 * This routine knows about the interleaving of the swapmap 80 * and handles that. 81 */ 82rmalloc(mp, size) 83 register struct map *mp; 84{ 85 register struct mapent *ep = (struct mapent *)(mp+1); 86 register int addr; 87 register struct mapent *bp; 88 swblk_t first, rest; 89 90 if (size <= 0 || mp == swapmap && size > DMMAX) 91 panic("rmalloc"); 92 /* 93 * Search for a piece of the resource map which has enough 94 * free space to accomodate the request. 95 */ 96 for (bp = ep; bp->m_size; bp++) { 97 if (bp->m_size >= size) { 98 /* 99 * If allocating from swapmap, 100 * then have to respect interleaving 101 * boundaries. 102 */ 103 if (mp == swapmap && 104 (first = DMMAX - bp->m_addr%DMMAX) < bp->m_size) { 105 if (bp->m_size - first < size) 106 continue; 107 addr = bp->m_addr + first; 108 rest = bp->m_size - first - size; 109 bp->m_size = first; 110 if (rest) 111 rmfree(swapmap, rest, addr+size); 112 return (addr); 113 } 114 /* 115 * Allocate from the map. 116 * If there is no space left of the piece 117 * we allocated from, move the rest of 118 * the pieces to the left. 119 */ 120 addr = bp->m_addr; 121 bp->m_addr += size; 122 if ((bp->m_size -= size) == 0) { 123 do { 124 bp++; 125 (bp-1)->m_addr = bp->m_addr; 126 } while ((bp-1)->m_size = bp->m_size); 127 } 128 if (mp == swapmap && addr % CLSIZE) 129 panic("rmalloc swapmap"); 130 return (addr); 131 } 132 } 133 return (0); 134} 135 136/* 137 * Free the previously allocated space at addr 138 * of size units into the specified map. 139 * Sort addr into map and combine on 140 * one or both ends if possible. 141 */ 142rmfree(mp, size, addr) 143 struct map *mp; 144 register int size, addr; 145{ 146 struct mapent *firstbp; 147 register struct mapent *bp; 148 register int t; 149 150 /* 151 * Both address and size must be 152 * positive, or the protocol has broken down. 153 */ 154 if (addr <= 0 || size <= 0) 155 goto badrmfree; 156 /* 157 * Locate the piece of the map which starts after the 158 * returned space (or the end of the map). 159 */ 160 firstbp = bp = (struct mapent *)(mp + 1); 161 for (; bp->m_addr <= addr && bp->m_size != 0; bp++) 162 continue; 163 /* 164 * If the piece on the left abuts us, 165 * then we should combine with it. 166 */ 167 if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { 168 /* 169 * Check no overlap (internal error). 170 */ 171 if ((bp-1)->m_addr+(bp-1)->m_size > addr) 172 goto badrmfree; 173 /* 174 * Add into piece on the left by increasing its size. 175 */ 176 (bp-1)->m_size += size; 177 /* 178 * If the combined piece abuts the piece on 179 * the right now, compress it in also, 180 * by shifting the remaining pieces of the map over. 181 */ 182 if (bp->m_addr && addr+size >= bp->m_addr) { 183 if (addr+size > bp->m_addr) 184 goto badrmfree; 185 (bp-1)->m_size += bp->m_size; 186 while (bp->m_size) { 187 bp++; 188 (bp-1)->m_addr = bp->m_addr; 189 (bp-1)->m_size = bp->m_size; 190 } 191 } 192 goto done; 193 } 194 /* 195 * Don't abut on the left, check for abutting on 196 * the right. 197 */ 198 if (addr+size >= bp->m_addr && bp->m_size) { 199 if (addr+size > bp->m_addr) 200 goto badrmfree; 201 bp->m_addr -= size; 202 bp->m_size += size; 203 goto done; 204 } 205 /* 206 * Don't abut at all. Make a new entry 207 * and check for map overflow. 208 */ 209 do { 210 t = bp->m_addr; 211 bp->m_addr = addr; 212 addr = t; 213 t = bp->m_size; 214 bp->m_size = size; 215 bp++; 216 } while (size = t); 217 /* 218 * Segment at bp is to be the delimiter; 219 * If there is not room for it 220 * then the table is too full 221 * and we must discard something. 222 */ 223 if (bp+1 > mp->m_limit) { 224 /* 225 * Back bp up to last available segment. 226 * which contains a segment already and must 227 * be made into the delimiter. 228 * Discard second to last entry, 229 * since it is presumably smaller than the last 230 * and move the last entry back one. 231 */ 232 bp--; 233 printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name, 234 (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); 235 bp[-1] = bp[0]; 236 bp[0].m_size = bp[0].m_addr = 0; 237 } 238done: 239 /* 240 * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE! 241 */ 242 if ((mp == kernelmap) && kmapwnt) { 243 kmapwnt = 0; 244 wakeup((caddr_t)kernelmap); 245 } 246 return; 247badrmfree: 248 panic("bad rmfree"); 249} 250