xref: /original-bsd/sys/kern/subr_rmap.c (revision 1403a0cd) 
1 /*	subr_rmap.c	6.2	84/08/29	*/
2 
3 #include "param.h"
4 #include "systm.h"
5 #include "map.h"
6 #include "dir.h"
7 #include "user.h"
8 #include "proc.h"
9 #include "text.h"
10 #include "kernel.h"
11 
12 /*
13  * Resource map handling routines.
14  *
15  * A resource map is an array of structures each
16  * of which describes a segment of the address space of an available
17  * resource.  The segments are described by their base address and
18  * length, and sorted in address order.  Each resource map has a fixed
19  * maximum number of segments allowed.  Resources are allocated
20  * by taking part or all of one of the segments of the map.
21  *
22  * Returning of resources will require another segment if
23  * the returned resources are not adjacent in the address
24  * space to an existing segment.  If the return of a segment
25  * would require a slot which is not available, then one of
26  * the resource map segments is discarded after a warning is printed.
27  * Returning of resources may also cause the map to collapse
28  * by coalescing two existing segments and the returned space
29  * into a single segment.  In this case the resource map is
30  * made smaller by copying together to fill the resultant gap.
31  *
32  * N.B.: the current implementation uses a dense array and does
33  * not admit the value ``0'' as a legal address, since that is used
34  * as a delimiter.
35  */
36 
37 /*
38  * Initialize map mp to have (mapsize-2) segments
39  * and to be called ``name'', which we print if
40  * the slots become so fragmented that we lose space.
41  * The map itself is initialized with size elements free
42  * starting at addr.
43  */
44 rminit(mp, size, addr, name, mapsize)
45 	register struct map *mp;
46 	long size, addr;
47 	char *name;
48 	int mapsize;
49 {
50 	register struct mapent *ep = (struct mapent *)(mp+1);
51 
52 	mp->m_name = name;
53 /* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */
54 	/*
55 	 * One of the mapsize slots is taken by the map structure,
56 	 * segments has size 0 and addr 0, and acts as a delimiter.
57 	 * We insure that we never use segments past the end of
58 	 * the array which is given by mp->m_limit.
59 	 * Instead, when excess segments occur we discard some resources.
60 	 */
61 	mp->m_limit = (struct mapent *)&mp[mapsize];
62 	/*
63 	 * Simulate a rmfree(), but with the option to
64 	 * call with size 0 and addr 0 when we just want
65 	 * to initialize without freeing.
66 	 */
67 	ep->m_size = size;
68 	ep->m_addr = addr;
69 }
70 
71 /*
72  * Allocate 'size' units from the given
73  * map. Return the base of the allocated space.
74  * In a map, the addresses are increasing and the
75  * list is terminated by a 0 size.
76  *
77  * Algorithm is first-fit.
78  *
79  * This routine knows about the interleaving of the swapmap
80  * and handles that.
81  */
82 long
83 rmalloc(mp, size)
84 	register struct map *mp;
85 	long size;
86 {
87 	register struct mapent *ep = (struct mapent *)(mp+1);
88 	register int addr;
89 	register struct mapent *bp;
90 	swblk_t first, rest;
91 
92 	if (size <= 0 || mp == swapmap && size > dmmax)
93 		panic("rmalloc");
94 	/*
95 	 * Search for a piece of the resource map which has enough
96 	 * free space to accomodate the request.
97 	 */
98 	for (bp = ep; bp->m_size; bp++) {
99 		if (bp->m_size >= size) {
100 			/*
101 			 * If allocating from swapmap,
102 			 * then have to respect interleaving
103 			 * boundaries.
104 			 */
105 			if (mp == swapmap && nswdev > 1 &&
106 			    (first = dmmax - bp->m_addr%dmmax) < bp->m_size) {
107 				if (bp->m_size - first < size)
108 					continue;
109 				addr = bp->m_addr + first;
110 				rest = bp->m_size - first - size;
111 				bp->m_size = first;
112 				if (rest)
113 					rmfree(swapmap, rest, addr+size);
114 				return (addr);
115 			}
116 			/*
117 			 * Allocate from the map.
118 			 * If there is no space left of the piece
119 			 * we allocated from, move the rest of
120 			 * the pieces to the left.
121 			 */
122 			addr = bp->m_addr;
123 			bp->m_addr += size;
124 			if ((bp->m_size -= size) == 0) {
125 				do {
126 					bp++;
127 					(bp-1)->m_addr = bp->m_addr;
128 				} while ((bp-1)->m_size = bp->m_size);
129 			}
130 			if (mp == swapmap && addr % CLSIZE)
131 				panic("rmalloc swapmap");
132 			return (addr);
133 		}
134 	}
135 	return (0);
136 }
137 
138 /*
139  * Free the previously allocated space at addr
140  * of size units into the specified map.
141  * Sort addr into map and combine on
142  * one or both ends if possible.
143  */
144 rmfree(mp, size, addr)
145 	struct map *mp;
146 	long size, addr;
147 {
148 	struct mapent *firstbp;
149 	register struct mapent *bp;
150 	register int t;
151 
152 	/*
153 	 * Both address and size must be
154 	 * positive, or the protocol has broken down.
155 	 */
156 	if (addr <= 0 || size <= 0)
157 		goto badrmfree;
158 	/*
159 	 * Locate the piece of the map which starts after the
160 	 * returned space (or the end of the map).
161 	 */
162 	firstbp = bp = (struct mapent *)(mp + 1);
163 	for (; bp->m_addr <= addr && bp->m_size != 0; bp++)
164 		continue;
165 	/*
166 	 * If the piece on the left abuts us,
167 	 * then we should combine with it.
168 	 */
169 	if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) {
170 		/*
171 		 * Check no overlap (internal error).
172 		 */
173 		if ((bp-1)->m_addr+(bp-1)->m_size > addr)
174 			goto badrmfree;
175 		/*
176 		 * Add into piece on the left by increasing its size.
177 		 */
178 		(bp-1)->m_size += size;
179 		/*
180 		 * If the combined piece abuts the piece on
181 		 * the right now, compress it in also,
182 		 * by shifting the remaining pieces of the map over.
183 		 */
184 		if (bp->m_addr && addr+size >= bp->m_addr) {
185 			if (addr+size > bp->m_addr)
186 				goto badrmfree;
187 			(bp-1)->m_size += bp->m_size;
188 			while (bp->m_size) {
189 				bp++;
190 				(bp-1)->m_addr = bp->m_addr;
191 				(bp-1)->m_size = bp->m_size;
192 			}
193 		}
194 		goto done;
195 	}
196 	/*
197 	 * Don't abut on the left, check for abutting on
198 	 * the right.
199 	 */
200 	if (addr+size >= bp->m_addr && bp->m_size) {
201 		if (addr+size > bp->m_addr)
202 			goto badrmfree;
203 		bp->m_addr -= size;
204 		bp->m_size += size;
205 		goto done;
206 	}
207 	/*
208 	 * Don't abut at all.  Make a new entry
209 	 * and check for map overflow.
210 	 */
211 	do {
212 		t = bp->m_addr;
213 		bp->m_addr = addr;
214 		addr = t;
215 		t = bp->m_size;
216 		bp->m_size = size;
217 		bp++;
218 	} while (size = t);
219 	/*
220 	 * Segment at bp is to be the delimiter;
221 	 * If there is not room for it
222 	 * then the table is too full
223 	 * and we must discard something.
224 	 */
225 	if (bp+1 > mp->m_limit) {
226 		/*
227 		 * Back bp up to last available segment.
228 		 * which contains a segment already and must
229 		 * be made into the delimiter.
230 		 * Discard second to last entry,
231 		 * since it is presumably smaller than the last
232 		 * and move the last entry back one.
233 		 */
234 		bp--;
235 		printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name,
236 		    (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size);
237 		bp[-1] = bp[0];
238 		bp[0].m_size = bp[0].m_addr = 0;
239 	}
240 done:
241 	/*
242 	 * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE!
243 	 */
244 	if ((mp == kernelmap) && kmapwnt) {
245 		kmapwnt = 0;
246 		wakeup((caddr_t)kernelmap);
247 	}
248 	return;
249 badrmfree:
250 	panic("bad rmfree");
251 }
252 
253 /*
254  * Allocate 'size' units from the given map, starting at address 'addr'.
255  * Return 'addr' if successful, 0 if not.
256  * This may cause the creation or destruction of a resource map segment.
257  *
258  * This routine will return failure status if there is not enough room
259  * for a required additional map segment.
260  *
261  * An attempt to use this on 'swapmap' will result in
262  * a failure return.  This is due mainly to laziness and could be fixed
263  * to do the right thing, although it probably will never be used.
264  */
265 rmget(mp, size, addr)
266 	register struct map *mp;
267 {
268 	register struct mapent *ep = (struct mapent *)(mp+1);
269 	register struct mapent *bp, *bp2;
270 
271 	if (size <= 0)
272 		panic("rmget");
273 	if (mp == swapmap)
274 		return (0);
275 	/*
276 	 * Look for a map segment containing the requested address.
277 	 * If none found, return failure.
278 	 */
279 	for (bp = ep; bp->m_size; bp++)
280 		if (bp->m_addr <= addr && bp->m_addr + bp->m_size > addr)
281 			break;
282 	if (bp->m_size == 0)
283 		return (0);
284 
285 	/*
286 	 * If segment is too small, return failure.
287 	 * If big enough, allocate the block, compressing or expanding
288 	 * the map as necessary.
289 	 */
290 	if (bp->m_addr + bp->m_size < addr + size)
291 		return (0);
292 	if (bp->m_addr == addr)
293 		if (bp->m_addr + bp->m_size == addr + size) {
294 			/*
295 			 * Allocate entire segment and compress map
296 			 */
297 			bp2 = bp;
298 			while (bp2->m_size) {
299 				bp2++;
300 				(bp2-1)->m_addr = bp2->m_addr;
301 				(bp2-1)->m_size = bp2->m_size;
302 			}
303 		} else {
304 			/*
305 			 * Allocate first part of segment
306 			 */
307 			bp->m_addr += size;
308 			bp->m_size -= size;
309 		}
310 	else
311 		if (bp->m_addr + bp->m_size == addr + size) {
312 			/*
313 			 * Allocate last part of segment
314 			 */
315 			bp->m_size -= size;
316 		} else {
317 			/*
318 			 * Allocate from middle of segment, but only
319 			 * if table can be expanded.
320 			 */
321 			for (bp2=bp; bp2->m_size; bp2++)
322 				;
323 			if (bp2 == mp->m_limit)
324 				return (0);
325 			while (bp2 > bp) {
326 				(bp2+1)->m_addr = bp2->m_addr;
327 				(bp2+1)->m_size = bp2->m_size;
328 				bp2--;
329 			}
330 			(bp+1)->m_addr = addr + size;
331 			(bp+1)->m_size =
332 			    bp->m_addr + bp->m_size - (addr + size);
333 			bp->m_size = addr - bp->m_addr;
334 		}
335 	return (addr);
336 }
337