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