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