2.9BSD - /usr/src/sys/sys/malloc.c

   1: #include "param.h"
   2: #include <sys/systm.h>
   3: #include <sys/map.h>
   4: #ifdef UCB_METER
   5: #include <sys/vm.h>
   6: #endif
   7: 
   8: 
   9: /*
  10:  *	SCCS id	@(#)malloc.c	2.1 (Berkeley)	8/5/83
  11:  */
  12: 
  13: 
  14: /*
  15:  * Resource map handling routines.
  16:  *
  17:  * A resource map is an array of structures each
  18:  * of which describes a segment of the address space of an available
  19:  * resource.  The segments are described by their base address and
  20:  * length, and sorted in address order.  Each resource map has a fixed
  21:  * maximum number of segments allowed.  Resources are allocated
  22:  * by taking part or all of one of the segments of the map.
  23:  *
  24:  * Returning of resources will require another segment if
  25:  * the returned resources are not adjacent in the address
  26:  * space to an existing segment.  If the return of a segment
  27:  * would require a slot which is not available, then one of
  28:  * the resource map segments is discarded after a warning is printed.
  29:  * Returning of resources may also cause the map to collapse
  30:  * by coalescing two existing segments and the returned space
  31:  * into a single segment.  In this case the resource map is
  32:  * made smaller by copying together to fill the resultant gap.
  33:  *
  34:  * N.B.: the current implementation uses a dense array and does
  35:  * not admit the value ``0'' as a legal address or size,
  36:  * since that is used as a delimiter.
  37:  */
  38: 
  39: /*
  40:  * Allocate 'size' units from the given
  41:  * map. Return the base of the allocated space.
  42:  * 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 memaddr addr;
  53:     register struct mapent *bp;
  54:     int retry = 0;
  55: 
  56:     if (size == 0)
  57:         panic("malloc");
  58:     /*
  59: 	 * Search for a piece of the resource map which has enough
  60: 	 * free space to accomodate the request.
  61: 	 */
  62: again:
  63:     for (bp = mp->m_map; bp->m_size; bp++) {
  64:         if (bp->m_size >= size) {
  65:             /*
  66: 			 * Allocate from the map.
  67: 			 * If there is no space left of the piece
  68: 			 * we allocated from, move the rest of
  69: 			 * the pieces to the left.
  70: 			 */
  71:             addr = bp->m_addr;
  72:             bp->m_addr += size;
  73:             if ((bp->m_size -= size) == 0) {
  74:                 do {
  75:                     bp++;
  76:                     (bp-1)->m_addr = bp->m_addr;
  77:                 } while ((bp-1)->m_size = bp->m_size);
  78:             }
  79: #ifdef  UCB_METER
  80:             if (mp == coremap)
  81:                 freemem -= size;
  82: #endif
  83:             return (addr);
  84:         }
  85:     }
  86:     if (mp == swapmap && retry++ == 0) {
  87:         /*
  88: 		 * Attempt to avoid running out of swap--
  89: 		 * free ALL unused sticky text segments.
  90: 		 */
  91:         printf("short of swap\n");
  92:         xumount(NODEV);
  93:         goto again;
  94:     }
  95:     return (0);
  96: }
  97: 
  98: /*
  99:  * Free the previously allocated space at addr
 100:  * of size units into the specified map.
 101:  * Sort addr into map and combine on
 102:  * 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:     struct mapent *firstbp;
 110:     register struct mapent *bp;
 111:     register u_short t;
 112: 
 113:     if (size == 0)
 114:         return;
 115: #ifdef  DIAGNOSTIC
 116:     /*
 117: 	 * The address must be
 118: 	 * positive, or the protocol has broken down.
 119: 	 */
 120:     if (addr == 0)
 121:         goto badmfree;
 122: #endif
 123:     if (mp == coremap) {
 124:         if (runin) {
 125:             runin = 0;
 126:             wakeup((caddr_t)&runin);
 127:         }
 128: #ifdef  UCB_METER
 129:         freemem += size;
 130: #endif
 131:     }
 132:     /*
 133: 	 * Locate the piece of the map which starts after the
 134: 	 * returned space (or the end of the map).
 135: 	 */
 136:     firstbp = bp = mp->m_map;
 137:     for (; bp->m_addr <= addr && bp->m_size != 0; bp++)
 138:         continue;
 139:     /*
 140: 	 * If the piece on the left abuts us,
 141: 	 * then we should combine with it.
 142: 	 */
 143:     if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) {
 144: #ifdef  DIAGNOSTIC
 145:         /*
 146: 		 * Check no overlap (internal error).
 147: 		 */
 148:         if ((bp-1)->m_addr+(bp-1)->m_size > addr)
 149:             goto badmfree;
 150: #endif
 151:         /*
 152: 		 * Add into piece on the left by increasing its size.
 153: 		 */
 154:         (bp-1)->m_size += size;
 155:         /*
 156: 		 * If the combined piece abuts the piece on
 157: 		 * the right now, compress it in also,
 158: 		 * by shifting the remaining pieces of the map over.
 159: 		 */
 160:         if (bp->m_addr && addr+size >= bp->m_addr) {
 161: #ifdef  DIAGNOSTIC
 162:             if (addr+size > bp->m_addr)
 163:                 goto badmfree;
 164: #endif
 165:             (bp-1)->m_size += bp->m_size;
 166:             while (bp->m_size) {
 167:                 bp++;
 168:                 (bp-1)->m_addr = bp->m_addr;
 169:                 (bp-1)->m_size = bp->m_size;
 170:             }
 171:         }
 172:         goto done;
 173:     }
 174:     /*
 175: 	 * Don't abut on the left, check for abutting on
 176: 	 * the right.
 177: 	 */
 178:     if (addr+size >= bp->m_addr && bp->m_size) {
 179: #ifdef  DIAGNOSTIC
 180:         if (addr+size > bp->m_addr)
 181:             goto badmfree;
 182: #endif
 183:         bp->m_addr -= size;
 184:         bp->m_size += size;
 185:         goto done;
 186:     }
 187:     /*
 188: 	 * Don't abut at all.  Make a new entry
 189: 	 * and check for map overflow.
 190: 	 */
 191:     do {
 192:         t = bp->m_addr;
 193:         bp->m_addr = addr;
 194:         addr = t;
 195:         t = bp->m_size;
 196:         bp->m_size = size;
 197:         bp++;
 198:     } while (size = t);
 199:     /*
 200: 	 * Segment at bp is to be the delimiter;
 201: 	 * If there is not room for it
 202: 	 * then the table is too full
 203: 	 * and we must discard something.
 204: 	 */
 205:     if (bp+1 > mp->m_limit) {
 206:         /*
 207: 		 * Back bp up to last available segment.
 208: 		 * which contains a segment already and must
 209: 		 * be made into the delimiter.
 210: 		 * Discard second to last entry,
 211: 		 * since it is presumably smaller than the last
 212: 		 * and move the last entry back one.
 213: 		 */
 214:         bp--;
 215:         printf("%s: map ovflo, lost [%d-%d)\n", mp->m_name,
 216:             (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size);
 217:         bp[-1] = bp[0];
 218:         bp->m_size = bp->m_addr = 0;
 219:     }
 220: done:
 221:     return;
 222: #ifdef  DIAGNOSTIC
 223: badmfree:
 224:     panic("bad mfree");
 225: #endif
 226: }
 227: 
 228: #ifdef  VIRUS_VFORK
 229: /*
 230:  *  Allocate resources for the three segments of a process
 231:  *  (data, stack and u.), attempting to minimize the cost of
 232:  *  failure part-way through.
 233:  *  Since the segments are located successively, it is best for the sizes
 234:  *  to be in decreasing order; generally, data, stack, then u. will be best.
 235:  *  Returns NULL on failure, with a[2] set to NULL (since a[2] is for u.).
 236:  *  Returns u. address (a[2]) on success, with all
 237:  *  addresses placed in a[].
 238:  */
 239: memaddr
 240: malloc3(mp,size0,size1,size2,a)
 241: struct map *mp;
 242: size_t size0, size1, size2;
 243: memaddr a[3];
 244: {
 245:     register struct mapent *bp, *ep;
 246:     struct mapent *found[3];
 247:     size_t sizes[3];
 248:     register next;
 249:     int retry = 0;
 250: 
 251:     sizes[0] = size0, sizes[1] = size1, sizes[2] = size2;
 252: 
 253: again:
 254:     next = 0;
 255:     for (bp=mp->m_map; bp->m_addr; ) {
 256:         if (bp->m_size >= sizes[next]) {
 257:             found[next] = bp;
 258:             bp->m_size -= sizes[next];
 259:             if (++next > 2)
 260:                 break;
 261:             bp = mp->m_map;
 262:         }
 263:         else bp++;
 264:     }
 265:     if (next < 3) {
 266:         /*
 267: 		 *  Couldn't get it all.  Restore the old sizes.
 268: 		 */
 269:         while (next--)
 270:             found[next]->m_size += sizes[next];
 271:         if (mp == swapmap && retry++ == 0) {
 272:             /*
 273: 			 * Attempt to avoid running out of swap--
 274: 			 * free ALL unused sticky text segments.
 275: 			 */
 276:             printf("short of swap\n");
 277:             xumount(NODEV);
 278:             goto again;
 279:         }
 280:         a[2] = NULL;
 281:     } else {
 282:         /*
 283: 		 *  Got it all.  Update the addresses.
 284: 		 */
 285:         for (next=0; next<3; next++) {
 286:             bp = found[next];
 287:             a[next] = bp->m_addr;
 288:             bp->m_addr += sizes[next];
 289: #ifdef  UCB_METER
 290:             if (mp == coremap)
 291:                 freemem -= sizes[next];
 292: #endif
 293:         }
 294:         /*
 295: 		 * Find the first segment with 0 size.
 296: 		 */
 297:         for (bp=mp->m_map; bp->m_size; bp++)
 298:             ;
 299:         /*
 300: 		 * Copy back any remaining entries to remove entries
 301: 		 * with size 0.  addr of 0 terminates.
 302: 		 */
 303:         if (bp->m_addr) {
 304:             ep = bp;
 305:             for (;;) {
 306:                 if ((bp->m_size == 0) && (bp->m_addr != 0))
 307:                 bp++;
 308:                 else {
 309:                 ep->m_size = bp->m_size;
 310:                 if ((ep++->m_addr = bp++->m_addr) == 0)
 311:                     break;
 312:                 }
 313:             }
 314:             /*
 315: 			 * Eliminate garbage past end.
 316: 			 */
 317:             bp--;
 318:             while (ep < bp) {
 319:                 ep->m_size = 0;
 320:                 ep++->m_addr = 0;
 321:             }
 322:         }
 323:     }
 324:     return(a[2]);
 325: }
 326: #endif	VIRUS_VFORK

Defined functions