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