1 /*- 2 * Copyright (c) 1982, 1986 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.proprietary.c% 6 * 7 * @(#)subr_rmap.c 7.8 (Berkeley) 05/09/91 8 */ 9 10 #include "param.h" 11 #include "systm.h" 12 #include "map.h" 13 #include "dmap.h" /* XXX */ 14 #include "proc.h" 15 #include "kernel.h" 16 17 /* 18 * Resource map handling routines. 19 * 20 * A resource map is an array of structures each 21 * of which describes a segment of the address space of an available 22 * resource. The segments are described by their base address and 23 * length, and sorted in address order. Each resource map has a fixed 24 * maximum number of segments allowed. Resources are allocated 25 * by taking part or all of one of the segments of the map. 26 * 27 * Returning of resources will require another segment if 28 * the returned resources are not adjacent in the address 29 * space to an existing segment. If the return of a segment 30 * would require a slot which is not available, then one of 31 * the resource map segments is discarded after a warning is printed. 32 * Returning of resources may also cause the map to collapse 33 * by coalescing two existing segments and the returned space 34 * into a single segment. In this case the resource map is 35 * made smaller by copying together to fill the resultant gap. 36 * 37 * N.B.: the current implementation uses a dense array and does 38 * not admit the value ``0'' as a legal address, since that is used 39 * as a delimiter. 40 */ 41 42 /* 43 * Initialize map mp to have (mapsize-2) segments 44 * and to be called ``name'', which we print if 45 * the slots become so fragmented that we lose space. 46 * The map itself is initialized with size elements free 47 * starting at addr. 48 */ 49 rminit(mp, size, addr, name, mapsize) 50 register struct map *mp; 51 long size, addr; 52 char *name; 53 int mapsize; 54 { 55 register struct mapent *ep = (struct mapent *)(mp+1); 56 57 mp->m_name = name; 58 /* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ 59 /* 60 * One of the mapsize slots is taken by the map structure, 61 * segments has size 0 and addr 0, and acts as a delimiter. 62 * We insure that we never use segments past the end of 63 * the array which is given by mp->m_limit. 64 * Instead, when excess segments occur we discard some resources. 65 */ 66 mp->m_limit = (struct mapent *)&mp[mapsize]; 67 /* 68 * Simulate a rmfree(), but with the option to 69 * call with size 0 and addr 0 when we just want 70 * to initialize without freeing. 71 */ 72 ep->m_size = size; 73 ep->m_addr = addr; 74 (++ep)->m_size = 0; 75 ep->m_addr = 0; 76 } 77 78 /* 79 * Allocate 'size' units from the given 80 * map. Return the base of the allocated space. 81 * In a map, the addresses are increasing and the 82 * list is terminated by a 0 size. 83 * 84 * Algorithm is first-fit. 85 * 86 * This routine knows about the interleaving of the swapmap 87 * and handles that. 88 */ 89 long 90 rmalloc(mp, size) 91 register struct map *mp; 92 long size; 93 { 94 register struct mapent *ep = (struct mapent *)(mp+1); 95 register int addr; 96 register struct mapent *bp; 97 swblk_t first, rest; 98 99 if (size <= 0 || mp == swapmap && size > dmmax) 100 panic("rmalloc"); 101 /* 102 * Search for a piece of the resource map which has enough 103 * free space to accomodate the request. 104 */ 105 for (bp = ep; bp->m_size; bp++) { 106 if (bp->m_size >= size) { 107 /* 108 * If allocating from swapmap, 109 * then have to respect interleaving 110 * boundaries. 111 */ 112 if (mp == swapmap && nswdev > 1 && 113 (first = dmmax - bp->m_addr%dmmax) < size) { 114 if (bp->m_size - first < size) 115 continue; 116 addr = bp->m_addr + first; 117 rest = bp->m_size - first - size; 118 bp->m_size = first; 119 if (rest) 120 rmfree(swapmap, rest, addr+size); 121 return (addr); 122 } 123 /* 124 * Allocate from the map. 125 * If there is no space left of the piece 126 * we allocated from, move the rest of 127 * the pieces to the left. 128 */ 129 addr = bp->m_addr; 130 bp->m_addr += size; 131 if ((bp->m_size -= size) == 0) { 132 do { 133 bp++; 134 (bp-1)->m_addr = bp->m_addr; 135 } while ((bp-1)->m_size = bp->m_size); 136 } 137 if (mp == swapmap && addr % CLSIZE) 138 panic("rmalloc swapmap"); 139 return (addr); 140 } 141 } 142 return (0); 143 } 144 145 /* 146 * Free the previously allocated space at addr 147 * of size units into the specified map. 148 * Sort addr into map and combine on 149 * one or both ends if possible. 150 */ 151 rmfree(mp, size, addr) 152 struct map *mp; 153 long size, addr; 154 { 155 struct mapent *firstbp; 156 register struct mapent *bp; 157 register int t; 158 159 /* 160 * Both address and size must be 161 * positive, or the protocol has broken down. 162 */ 163 if (addr <= 0 || size <= 0) 164 goto badrmfree; 165 /* 166 * Locate the piece of the map which starts after the 167 * returned space (or the end of the map). 168 */ 169 firstbp = bp = (struct mapent *)(mp + 1); 170 for (; bp->m_addr <= addr && bp->m_size != 0; bp++) 171 continue; 172 /* 173 * If the piece on the left abuts us, 174 * then we should combine with it. 175 */ 176 if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { 177 /* 178 * Check no overlap (internal error). 179 */ 180 if ((bp-1)->m_addr+(bp-1)->m_size > addr) 181 goto badrmfree; 182 /* 183 * Add into piece on the left by increasing its size. 184 */ 185 (bp-1)->m_size += size; 186 /* 187 * If the combined piece abuts the piece on 188 * the right now, compress it in also, 189 * by shifting the remaining pieces of the map over. 190 */ 191 if (bp->m_addr && addr+size >= bp->m_addr) { 192 if (addr+size > bp->m_addr) 193 goto badrmfree; 194 (bp-1)->m_size += bp->m_size; 195 while (bp->m_size) { 196 bp++; 197 (bp-1)->m_addr = bp->m_addr; 198 (bp-1)->m_size = bp->m_size; 199 } 200 } 201 return; 202 } 203 /* 204 * Don't abut on the left, check for abutting on 205 * the right. 206 */ 207 if (addr+size >= bp->m_addr && bp->m_size) { 208 if (addr+size > bp->m_addr) 209 goto badrmfree; 210 bp->m_addr -= size; 211 bp->m_size += size; 212 return; 213 } 214 /* 215 * Don't abut at all. Make a new entry 216 * and check for map overflow. 217 */ 218 do { 219 t = bp->m_addr; 220 bp->m_addr = addr; 221 addr = t; 222 t = bp->m_size; 223 bp->m_size = size; 224 bp++; 225 } while (size = t); 226 /* 227 * Segment at bp is to be the delimiter; 228 * If there is not room for it 229 * then the table is too full 230 * and we must discard something. 231 */ 232 if (bp+1 > mp->m_limit) { 233 /* 234 * Back bp up to last available segment. 235 * which contains a segment already and must 236 * be made into the delimiter. 237 * Discard second to last entry, 238 * since it is presumably smaller than the last 239 * and move the last entry back one. 240 */ 241 bp--; 242 printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name, 243 (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); 244 bp[-1] = bp[0]; 245 bp[0].m_size = bp[0].m_addr = 0; 246 } 247 return; 248 badrmfree: 249 panic("bad rmfree"); 250 } 251 252 /* 253 * Allocate 'size' units from the given map, starting at address 'addr'. 254 * Return 'addr' if successful, 0 if not. 255 * This may cause the creation or destruction of a resource map segment. 256 * 257 * This routine will return failure status if there is not enough room 258 * for a required additional map segment. 259 * 260 * An attempt to use this on 'swapmap' will result in 261 * a failure return. This is due mainly to laziness and could be fixed 262 * to do the right thing, although it probably will never be used. 263 */ 264 rmget(mp, size, addr) 265 register struct map *mp; 266 { 267 register struct mapent *ep = (struct mapent *)(mp+1); 268 register struct mapent *bp, *bp2; 269 270 if (size <= 0) 271 panic("rmget"); 272 if (mp == swapmap) 273 return (0); 274 /* 275 * Look for a map segment containing the requested address. 276 * If none found, return failure. 277 */ 278 for (bp = ep; bp->m_size; bp++) 279 if (bp->m_addr <= addr && bp->m_addr + bp->m_size > addr) 280 break; 281 if (bp->m_size == 0) 282 return (0); 283 284 /* 285 * If segment is too small, return failure. 286 * If big enough, allocate the block, compressing or expanding 287 * the map as necessary. 288 */ 289 if (bp->m_addr + bp->m_size < addr + size) 290 return (0); 291 if (bp->m_addr == addr) 292 if (bp->m_addr + bp->m_size == addr + size) { 293 /* 294 * Allocate entire segment and compress map 295 */ 296 bp2 = bp; 297 while (bp2->m_size) { 298 bp2++; 299 (bp2-1)->m_addr = bp2->m_addr; 300 (bp2-1)->m_size = bp2->m_size; 301 } 302 } else { 303 /* 304 * Allocate first part of segment 305 */ 306 bp->m_addr += size; 307 bp->m_size -= size; 308 } 309 else 310 if (bp->m_addr + bp->m_size == addr + size) { 311 /* 312 * Allocate last part of segment 313 */ 314 bp->m_size -= size; 315 } else { 316 /* 317 * Allocate from middle of segment, but only 318 * if table can be expanded. 319 */ 320 for (bp2=bp; bp2->m_size; bp2++) 321 ; 322 if (bp2 + 1 >= mp->m_limit) 323 return (0); 324 while (bp2 > bp) { 325 (bp2+1)->m_addr = bp2->m_addr; 326 (bp2+1)->m_size = bp2->m_size; 327 bp2--; 328 } 329 (bp+1)->m_addr = addr + size; 330 (bp+1)->m_size = 331 bp->m_addr + bp->m_size - (addr + size); 332 bp->m_size = addr - bp->m_addr; 333 } 334 return (addr); 335 } 336