4.3BSD - /usr/src/sys/sys/subr_rmap.c

   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.1 (Berkeley) 6/5/86
   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: }
  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) < bp->m_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: }

Defined functions