1 /*- 2 * Copyright (c) 1982, 1986, 1993 3 * The Regents of the University of California. All rights reserved. 4 * (c) UNIX System Laboratories, Inc. 5 * All or some portions of this file are derived from material licensed 6 * to the University of California by American Telephone and Telegraph 7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8 * the permission of UNIX System Laboratories, Inc. 9 * 10 * %sccs.include.proprietary.c% 11 * 12 * @(#)subr_rmap.c 8.2 (Berkeley) 01/21/94 13 */ 14 15 #include <sys/param.h> 16 #include <sys/systm.h> 17 #include <sys/map.h> 18 #include <sys/dmap.h> /* XXX */ 19 #include <sys/proc.h> 20 #include <sys/kernel.h> 21 22 /* 23 * Resource map handling routines. 24 * 25 * A resource map is an array of structures each 26 * of which describes a segment of the address space of an available 27 * resource. The segments are described by their base address and 28 * length, and sorted in address order. Each resource map has a fixed 29 * maximum number of segments allowed. Resources are allocated 30 * by taking part or all of one of the segments of the map. 31 * 32 * Returning of resources will require another segment if 33 * the returned resources are not adjacent in the address 34 * space to an existing segment. If the return of a segment 35 * would require a slot which is not available, then one of 36 * the resource map segments is discarded after a warning is printed. 37 * Returning of resources may also cause the map to collapse 38 * by coalescing two existing segments and the returned space 39 * into a single segment. In this case the resource map is 40 * made smaller by copying together to fill the resultant gap. 41 * 42 * N.B.: the current implementation uses a dense array and does 43 * not admit the value ``0'' as a legal address, since that is used 44 * as a delimiter. 45 */ 46 47 /* 48 * Initialize map mp to have (mapsize-2) segments 49 * and to be called ``name'', which we print if 50 * the slots become so fragmented that we lose space. 51 * The map itself is initialized with size elements free 52 * starting at addr. 53 */ 54 void 55 rminit(mp, size, addr, name, mapsize) 56 register struct map *mp; 57 long size, addr; 58 char *name; 59 int mapsize; 60 { 61 register struct mapent *ep = (struct mapent *)(mp+1); 62 63 mp->m_name = name; 64 /* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ 65 /* 66 * One of the mapsize slots is taken by the map structure, 67 * segments has size 0 and addr 0, and acts as a delimiter. 68 * We insure that we never use segments past the end of 69 * the array which is given by mp->m_limit. 70 * Instead, when excess segments occur we discard some resources. 71 */ 72 mp->m_limit = (struct mapent *)&mp[mapsize]; 73 /* 74 * Simulate a rmfree(), but with the option to 75 * call with size 0 and addr 0 when we just want 76 * to initialize without freeing. 77 */ 78 ep->m_size = size; 79 ep->m_addr = addr; 80 (++ep)->m_size = 0; 81 ep->m_addr = 0; 82 } 83 84 /* 85 * A piece of memory of at least size units is allocated from the 86 * specified map using a first-fit algorithm. It returns the starting 87 * address of the allocated space. 88 * 89 * This routine knows about and handles the interleaving of the swapmap. 90 */ 91 long 92 rmalloc(mp, size) 93 register struct map *mp; 94 long size; 95 { 96 register struct mapent *ep = (struct mapent *)(mp+1); 97 register int addr; 98 register struct mapent *bp; 99 swblk_t first, rest; 100 101 if (size <= 0 || mp == swapmap && size > dmmax) 102 panic("rmalloc"); 103 /* 104 * Search for a piece of the resource map which has enough 105 * free space to accomodate the request. 106 */ 107 for (bp = ep; bp->m_size; bp++) { 108 if (bp->m_size >= size) { 109 /* 110 * If allocating from swapmap, 111 * then have to respect interleaving 112 * boundaries. 113 */ 114 if (mp == swapmap && nswdev > 1 && 115 (first = dmmax - bp->m_addr%dmmax) < size) { 116 if (bp->m_size - first < size) 117 continue; 118 addr = bp->m_addr + first; 119 rest = bp->m_size - first - size; 120 bp->m_size = first; 121 if (rest) 122 rmfree(swapmap, rest, addr+size); 123 return (addr); 124 } 125 /* 126 * Allocate from the map. 127 * If there is no space left of the piece 128 * we allocated from, move the rest of 129 * the pieces to the left. 130 */ 131 addr = bp->m_addr; 132 bp->m_addr += size; 133 if ((bp->m_size -= size) == 0) { 134 do { 135 bp++; 136 (bp-1)->m_addr = bp->m_addr; 137 } while ((bp-1)->m_size = bp->m_size); 138 } 139 if (mp == swapmap && addr % CLSIZE) 140 panic("rmalloc swapmap"); 141 return (addr); 142 } 143 } 144 return (0); 145 } 146 147 /* 148 * The previously allocated space at addr of size units is freed 149 * into the specified map. This routine is responsible for sorting 150 * the frred space into the correct location in the map, and coalescing 151 * it with free space on either side if they adjoin. 152 */ 153 void 154 rmfree(mp, size, addr) 155 struct map *mp; 156 long size, addr; 157 { 158 struct mapent *firstbp; 159 register struct mapent *bp; 160 register int t; 161 162 /* 163 * Both address and size must be 164 * positive, or the protocol has broken down. 165 */ 166 if (addr <= 0 || size <= 0) 167 goto badrmfree; 168 /* 169 * Locate the piece of the map which starts after the 170 * returned space (or the end of the map). 171 */ 172 firstbp = bp = (struct mapent *)(mp + 1); 173 for (; bp->m_addr <= addr && bp->m_size != 0; bp++) 174 continue; 175 /* 176 * If the piece on the left abuts us, 177 * then we should combine with it. 178 */ 179 if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { 180 /* 181 * Check no overlap (internal error). 182 */ 183 if ((bp-1)->m_addr+(bp-1)->m_size > addr) 184 goto badrmfree; 185 /* 186 * Add into piece on the left by increasing its size. 187 */ 188 (bp-1)->m_size += size; 189 /* 190 * If the combined piece abuts the piece on 191 * the right now, compress it in also, 192 * by shifting the remaining pieces of the map over. 193 */ 194 if (bp->m_addr && addr+size >= bp->m_addr) { 195 if (addr+size > bp->m_addr) 196 goto badrmfree; 197 (bp-1)->m_size += bp->m_size; 198 while (bp->m_size) { 199 bp++; 200 (bp-1)->m_addr = bp->m_addr; 201 (bp-1)->m_size = bp->m_size; 202 } 203 } 204 return; 205 } 206 /* 207 * Don't abut on the left, check for abutting on 208 * the right. 209 */ 210 if (addr+size >= bp->m_addr && bp->m_size) { 211 if (addr+size > bp->m_addr) 212 goto badrmfree; 213 bp->m_addr -= size; 214 bp->m_size += size; 215 return; 216 } 217 /* 218 * Don't abut at all. Make a new entry 219 * and check for map overflow. 220 */ 221 do { 222 t = bp->m_addr; 223 bp->m_addr = addr; 224 addr = t; 225 t = bp->m_size; 226 bp->m_size = size; 227 bp++; 228 } while (size = t); 229 /* 230 * Segment at bp is to be the delimiter; 231 * If there is not room for it 232 * then the table is too full 233 * and we must discard something. 234 */ 235 if (bp+1 > mp->m_limit) { 236 /* 237 * Back bp up to last available segment. 238 * which contains a segment already and must 239 * be made into the delimiter. 240 * Discard second to last entry, 241 * since it is presumably smaller than the last 242 * and move the last entry back one. 243 */ 244 bp--; 245 printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name, 246 (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); 247 bp[-1] = bp[0]; 248 bp[0].m_size = bp[0].m_addr = 0; 249 } 250 return; 251 badrmfree: 252 panic("bad rmfree"); 253 } 254