1 /*- 2 * Copyright (c) 1982, 1986 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.proprietary.c% 6 * 7 * @(#)subr_rmap.c 7.9 (Berkeley) 05/11/91 8 */ 9 10 #include "param.h" 11 #include "systm.h" 12 #include "map.h" 13 #include "dmap.h" /* XXX */ 14 #include "proc.h" 15 #include "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 rminit(mp, size, addr, name, mapsize) 50 register struct map *mp; 51 long size, addr; 52 char *name; 53 int mapsize; 54 { 55 register struct mapent *ep = (struct mapent *)(mp+1); 56 57 mp->m_name = name; 58 /* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ 59 /* 60 * One of the mapsize slots is taken by the map structure, 61 * segments has size 0 and addr 0, and acts as a delimiter. 62 * We insure that we never use segments past the end of 63 * the array which is given by mp->m_limit. 64 * Instead, when excess segments occur we discard some resources. 65 */ 66 mp->m_limit = (struct mapent *)&mp[mapsize]; 67 /* 68 * Simulate a rmfree(), but with the option to 69 * call with size 0 and addr 0 when we just want 70 * to initialize without freeing. 71 */ 72 ep->m_size = size; 73 ep->m_addr = addr; 74 (++ep)->m_size = 0; 75 ep->m_addr = 0; 76 } 77 78 /* 79 * A piece of memory of at least size units is allocated from the 80 * specified map using a first-fit algorithm. It returns the starting 81 * address of the allocated space. 82 * 83 * This routine knows about and handles the interleaving of the swapmap. 84 */ 85 long 86 rmalloc(mp, size) 87 register struct map *mp; 88 long size; 89 { 90 register struct mapent *ep = (struct mapent *)(mp+1); 91 register int addr; 92 register struct mapent *bp; 93 swblk_t first, rest; 94 95 if (size <= 0 || mp == swapmap && size > dmmax) 96 panic("rmalloc"); 97 /* 98 * Search for a piece of the resource map which has enough 99 * free space to accomodate the request. 100 */ 101 for (bp = ep; bp->m_size; bp++) { 102 if (bp->m_size >= size) { 103 /* 104 * If allocating from swapmap, 105 * then have to respect interleaving 106 * boundaries. 107 */ 108 if (mp == swapmap && nswdev > 1 && 109 (first = dmmax - bp->m_addr%dmmax) < size) { 110 if (bp->m_size - first < size) 111 continue; 112 addr = bp->m_addr + first; 113 rest = bp->m_size - first - size; 114 bp->m_size = first; 115 if (rest) 116 rmfree(swapmap, rest, addr+size); 117 return (addr); 118 } 119 /* 120 * Allocate from the map. 121 * If there is no space left of the piece 122 * we allocated from, move the rest of 123 * the pieces to the left. 124 */ 125 addr = bp->m_addr; 126 bp->m_addr += size; 127 if ((bp->m_size -= size) == 0) { 128 do { 129 bp++; 130 (bp-1)->m_addr = bp->m_addr; 131 } while ((bp-1)->m_size = bp->m_size); 132 } 133 if (mp == swapmap && addr % CLSIZE) 134 panic("rmalloc swapmap"); 135 return (addr); 136 } 137 } 138 return (0); 139 } 140 141 /* 142 * The previously allocated space at addr of size units is freed 143 * into the specified map. This routine is responsible for sorting 144 * the frred space into the correct location in the map, and coalescing 145 * it with free space on either side if they adjoin. 146 */ 147 rmfree(mp, size, addr) 148 struct map *mp; 149 long size, addr; 150 { 151 struct mapent *firstbp; 152 register struct mapent *bp; 153 register int t; 154 155 /* 156 * Both address and size must be 157 * positive, or the protocol has broken down. 158 */ 159 if (addr <= 0 || size <= 0) 160 goto badrmfree; 161 /* 162 * Locate the piece of the map which starts after the 163 * returned space (or the end of the map). 164 */ 165 firstbp = bp = (struct mapent *)(mp + 1); 166 for (; bp->m_addr <= addr && bp->m_size != 0; bp++) 167 continue; 168 /* 169 * If the piece on the left abuts us, 170 * then we should combine with it. 171 */ 172 if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { 173 /* 174 * Check no overlap (internal error). 175 */ 176 if ((bp-1)->m_addr+(bp-1)->m_size > addr) 177 goto badrmfree; 178 /* 179 * Add into piece on the left by increasing its size. 180 */ 181 (bp-1)->m_size += size; 182 /* 183 * If the combined piece abuts the piece on 184 * the right now, compress it in also, 185 * by shifting the remaining pieces of the map over. 186 */ 187 if (bp->m_addr && addr+size >= bp->m_addr) { 188 if (addr+size > bp->m_addr) 189 goto badrmfree; 190 (bp-1)->m_size += bp->m_size; 191 while (bp->m_size) { 192 bp++; 193 (bp-1)->m_addr = bp->m_addr; 194 (bp-1)->m_size = bp->m_size; 195 } 196 } 197 return; 198 } 199 /* 200 * Don't abut on the left, check for abutting on 201 * the right. 202 */ 203 if (addr+size >= bp->m_addr && bp->m_size) { 204 if (addr+size > bp->m_addr) 205 goto badrmfree; 206 bp->m_addr -= size; 207 bp->m_size += size; 208 return; 209 } 210 /* 211 * Don't abut at all. Make a new entry 212 * and check for map overflow. 213 */ 214 do { 215 t = bp->m_addr; 216 bp->m_addr = addr; 217 addr = t; 218 t = bp->m_size; 219 bp->m_size = size; 220 bp++; 221 } while (size = t); 222 /* 223 * Segment at bp is to be the delimiter; 224 * If there is not room for it 225 * then the table is too full 226 * and we must discard something. 227 */ 228 if (bp+1 > mp->m_limit) { 229 /* 230 * Back bp up to last available segment. 231 * which contains a segment already and must 232 * be made into the delimiter. 233 * Discard second to last entry, 234 * since it is presumably smaller than the last 235 * and move the last entry back one. 236 */ 237 bp--; 238 printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name, 239 (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); 240 bp[-1] = bp[0]; 241 bp[0].m_size = bp[0].m_addr = 0; 242 } 243 return; 244 badrmfree: 245 panic("bad rmfree"); 246 } 247