2.11BSD#431 - /usr/src/sys/sys/subr_rmap.c

   1: /*
   2:  * Copyright (c) 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	1.2 (2.11BSD GTE) 12/24/92
   7:  */
   8: 
   9: #include "param.h"
  10: #include "systm.h"
  11: #include "map.h"
  12: #include "vm.h"
  13: 
  14: /*
  15:  * Resource map handling routines.
  16:  *
  17:  * A resource map is an array of structures each of which describes a
  18:  * segment of the address space of an available resource.  The segments
  19:  * are described by their base address and length, and sorted in address
  20:  * order.  Each resource map has a fixed maximum number of segments
  21:  * allowed.  Resources are allocated by taking part or all of one of the
  22:  * segments of the map.
  23:  *
  24:  * Returning of resources will require another segment if the returned
  25:  * resources are not adjacent in the address space to an existing segment.
  26:  * If the return of a segment would require a slot which is not available,
  27:  * then one of the resource map segments is discarded after a warning is
  28:  * printed.
  29:  *
  30:  * Returning of resources may also cause the map to collapse by coalescing
  31:  * two existing segments and the returned space into a single segment.  In
  32:  * this case the resource map is made smaller by copying together to fill
  33:  * the resultant gap.
  34:  *
  35:  * N.B.: the current implementation uses a dense array and does not admit
  36:  * the value ``0'' as a legal address or size, since that is used as a
  37:  * delimiter.
  38:  */
  39: 
  40: /*
  41:  * Allocate 'size' units from the given map.  Return the base of the
  42:  * allocated space.  In a map, the addresses are increasing and the
  43:  * list is terminated by a 0 size.
  44:  *
  45:  * Algorithm is first-fit.
  46:  */
  47: memaddr
  48: malloc(mp, size)
  49:     struct map *mp;
  50:     register size_t size;
  51: {
  52:     register struct mapent *bp, *ep;
  53:     memaddr addr;
  54:     int retry;
  55: 
  56:     if (!size)
  57:         panic("malloc: size = 0");
  58:     /*
  59: 	 * Search for a piece of the resource map which has enough
  60: 	 * free space to accomodate the request.
  61: 	 */
  62:     retry = 0;
  63: again:
  64:     for (bp = mp->m_map; bp->m_size; ++bp)
  65:         if (bp->m_size >= size) {
  66:             /*
  67: 			 * Allocate from the map.  If we allocated the entire
  68: 			 * piece, move the rest of the map to the left.
  69: 			 */
  70:             addr = bp->m_addr;
  71:             bp->m_size -= size;
  72:             if (bp->m_size)
  73:                 bp->m_addr += size;
  74:             else for (ep = bp;; ++ep) {
  75:                 *ep = *++bp;
  76:                 if (!bp->m_size)
  77:                     break;
  78:             }
  79: #ifdef UCB_METER
  80:             if (mp == coremap)
  81:                 freemem -= size;
  82: #endif
  83:             return(addr);
  84:         }
  85:     /* no entries big enough */
  86:     if (!retry++) {
  87:         if (mp == swapmap) {
  88:             printf("short of swap\n");
  89:             xumount(NODEV);
  90:             goto again;
  91:         }
  92:         else if (mp == coremap) {
  93:             xuncore(size);
  94:             goto again;
  95:         }
  96:     }
  97:     return((memaddr)NULL);
  98: }
  99: 
 100: /*
 101:  * Free the previously allocated size units at addr into the specified
 102:  * map.  Sort addr into map and combine on one or both ends if possible.
 103:  */
 104: mfree(mp, size, addr)
 105:     struct map *mp;
 106:     size_t size;
 107:     register memaddr addr;
 108: {
 109:     register struct mapent *bp, *ep;
 110:     struct mapent *start;
 111: 
 112:     if (!size)
 113:         return;
 114:     /* the address must not be 0, or the protocol has broken down. */
 115:     if (!addr)
 116:         panic("mfree: addr = 0");
 117:     if (mp == coremap) {
 118:         if (runin) {
 119:             runin = 0;
 120:             wakeup((caddr_t)&runin);
 121:         }
 122: #ifdef UCB_METER
 123:         freemem += size;
 124: #endif
 125:     }
 126: 
 127:     /*
 128: 	 * locate the piece of the map which starts after the
 129: 	 * returned space (or the end of the map).
 130: 	 */
 131:     for (bp = mp->m_map; bp->m_size && bp->m_addr <= addr; ++bp);
 132: 
 133:     /* if there is a piece on the left abutting us, combine with it. */
 134:     ep = bp - 1;
 135:     if (bp != mp->m_map && ep->m_addr + ep->m_size >= addr) {
 136: #ifdef DIAGNOSTIC
 137:         /* any overlap is an internal error */
 138:         if (ep->m_addr + ep->m_size > addr)
 139:             panic("mfree overlap #1");
 140: #endif
 141:         /* add into piece on the left by increasing its size. */
 142:         ep->m_size += size;
 143: 
 144:         /*
 145: 		 * if the combined piece abuts the piece on the right now,
 146: 		 * compress it in also, by shifting the remaining pieces
 147: 		 * of the map over.
 148: 		 */
 149:         if (bp->m_size && addr + size >= bp->m_addr) {
 150: #ifdef DIAGNOSTIC
 151:             if (addr + size > bp->m_addr)
 152:                 panic("mfree overlap #2");
 153: #endif
 154:             ep->m_size += bp->m_size;
 155:             do {
 156:                 *++ep = *++bp;
 157:             } while (bp->m_size);
 158:         }
 159:         return;
 160:     }
 161: 
 162:     /* if doesn't abut on the left, check for abutting on the right. */
 163:     if (bp->m_size && addr + size >= bp->m_addr) {
 164: #ifdef DIAGNOSTIC
 165:         if (addr + size > bp->m_addr)
 166:             panic("mfree overlap #3");
 167: #endif
 168:         bp->m_addr = addr;
 169:         bp->m_size += size;
 170:         return;
 171:     }
 172: 
 173:     /* doesn't abut.  Make a new entry and check for map overflow. */
 174:     for (start = bp; bp->m_size; ++bp);
 175:     if (++bp > mp->m_limit)
 176:         /*
 177: 		 * too many segments; if this happens, the correct fix
 178: 		 * is to make the map bigger; you can't afford to lose
 179: 		 * chunks of the map.  If you need to implement recovery,
 180: 		 * use the above "for" loop to find the smallest entry
 181: 		 * and toss it.
 182: 		 */
 183:         printf("%s: overflow, lost %u clicks at 0%o\n",
 184:             mp->m_name, size, addr);
 185:     else {
 186:         for (ep = bp - 1; ep >= start; *bp-- = *ep--);
 187:         start->m_addr = addr;
 188:         start->m_size = size;
 189:     }
 190: }
 191: 
 192: /*
 193:  * Allocate resources for the three segments of a process (data, stack
 194:  * and u.), attempting to minimize the cost of failure part-way through.
 195:  * Since the segments are located successively, it is best for the sizes
 196:  * to be in decreasing order; generally, data, stack, then u. will be
 197:  * best.  Returns NULL on failure, address of u. on success.
 198:  */
 199: memaddr
 200: malloc3(mp, d_size, s_size, u_size, a)
 201:     struct map *mp;
 202:     size_t d_size, s_size, u_size;
 203:     memaddr a[3];
 204: {
 205:     register struct mapent *bp, *remap;
 206:     register int next;
 207:     struct mapent *madd[3];
 208:     size_t sizes[3];
 209:     int found, retry;
 210: 
 211:     sizes[0] = d_size; sizes[1] = s_size; sizes[2] = u_size;
 212:     retry = 0;
 213: again:
 214:     /*
 215: 	 * note, this has to work for d_size and s_size of zero,
 216: 	 * since init() comes in that way.
 217: 	 */
 218:     madd[0] = madd[1] = madd[2] = remap = NULL;
 219:     for (found = 0, bp = mp->m_map; bp->m_size; ++bp)
 220:         for (next = 0; next < 3; ++next)
 221:             if (!madd[next] && sizes[next] <= bp->m_size) {
 222:                 madd[next] = bp;
 223:                 bp->m_size -= sizes[next];
 224:                 if (!bp->m_size && !remap)
 225:                     remap = bp;
 226:                 if (++found == 3)
 227:                     goto resolve;
 228:             }
 229: 
 230:     /* couldn't get it all; restore the old sizes, try again */
 231:     for (next = 0; next < 3; ++next)
 232:         if (madd[next])
 233:             madd[next]->m_size += sizes[next];
 234:     if (!retry++)
 235:         if (mp == swapmap) {
 236:             printf("short of swap\n");
 237:             xumount(NODEV);
 238:             goto again;
 239:         }
 240:         else if (mp == coremap) {
 241:             xuncore(sizes[2]);  /* smallest to largest; */
 242:             xuncore(sizes[1]);  /* free up minimum space */
 243:             xuncore(sizes[0]);
 244:             goto again;
 245:         }
 246:     return((memaddr)NULL);
 247: 
 248: resolve:
 249:     /* got it all, update the addresses. */
 250:     for (next = 0; next < 3; ++next) {
 251:         bp = madd[next];
 252:         a[next] = bp->m_addr;
 253:         bp->m_addr += sizes[next];
 254:     }
 255: 
 256: #ifdef UCB_METER
 257:     if (mp == coremap)
 258:         freemem -= d_size + s_size + u_size;
 259: #endif
 260: 
 261:     /* remove any entries of size 0; addr of 0 terminates */
 262:     if (remap)
 263:         for (bp = remap + 1;; ++bp)
 264:             if (bp->m_size || !bp->m_addr) {
 265:                 *remap++ = *bp;
 266:                 if (!bp->m_addr)
 267:                     break;
 268:             }
 269:     return(a[2]);
 270: }

Defined functions