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

##### Functions

    malloc            X
    malloc3           X
    mfree             X

       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

malloc defined in line 47; used 27 times

- in /usr/src/sys/h/kernel.h line 16
- in /usr/src/sys/pdp/machdep.c line 216
- in /usr/src/sys/pdp/machdep2.c line 141, 168, 186, 194, 208, 215-220(2), 231, 237, 287, 362, 504, 518
- in /usr/src/sys/pdp/net_mac.h line 22-24(2)
- in /usr/src/sys/pdp/ram.c line 42
- in /usr/src/sys/sys/init_main.c line 377-379(2)
- in /usr/src/sys/sys/kern_exec.c line 194
- in /usr/src/sys/sys/kern_fork.c line 240
- in /usr/src/sys/sys/subr_log.c line 358
- in /usr/src/sys/sys/vm_proc.c line 88
- in /usr/src/sys/sys/vm_swap.c line 38
- in /usr/src/sys/sys/vm_text.c line 204, 256

malloc3 defined in line 199; used 3 times

- in /usr/src/sys/sys/kern_fork.c line 242
- in /usr/src/sys/sys/vm_swap.c line 45, 105

mfree defined in line 104; used 28 times

- in /usr/src/sys/pdp/machdep.c line 252
- in /usr/src/sys/pdp/machdep2.c line 122, 173, 348-350(2)
- in /usr/src/sys/sys/init_main.c line 189, 407-408(2)
- in /usr/src/sys/sys/kern_exec.c line 384
- in /usr/src/sys/sys/kern_exit.c line 93-96(3)
- in /usr/src/sys/sys/kern_fork.c line 289-290(2)
- in /usr/src/sys/sys/vm_proc.c line 43, 53, 107
- in /usr/src/sys/sys/vm_swap.c line 47, 63-70(3), 114-119(2), 144
- in /usr/src/sys/sys/vm_text.c line 318, 353-355(2), 381

Last modified: 1992-12-28 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 797 |