xref: /original-bsd/sys/kern/subr_rmap.c (revision 9a96b58b) 
1 /*	subr_rmap.c	4.5	82/04/11	*/
2 
3 #include "../h/param.h"
4 #include "../h/systm.h"
5 #include "../h/map.h"
6 #include "../h/dir.h"
7 #include "../h/user.h"
8 #include "../h/proc.h"
9 #include "../h/mtpr.h"
10 #include "../h/text.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 	int 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 rmalloc(mp, size)
83 	register struct map *mp;
84 {
85 	register struct mapent *ep = (struct mapent *)(mp+1);
86 	register int addr;
87 	register struct mapent *bp;
88 	swblk_t first, rest;
89 
90 	if (size <= 0 || mp == swapmap && size > DMMAX)
91 		panic("rmalloc");
92 	/*
93 	 * Search for a piece of the resource map which has enough
94 	 * free space to accomodate the request.
95 	 */
96 	for (bp = ep; bp->m_size; bp++) {
97 		if (bp->m_size >= size) {
98 			/*
99 			 * If allocating from swapmap,
100 			 * then have to respect interleaving
101 			 * boundaries.
102 			 */
103 			if (mp == swapmap &&
104 			    (first = DMMAX - bp->m_addr%DMMAX) < bp->m_size) {
105 				if (bp->m_size - first < size)
106 					continue;
107 				addr = bp->m_addr + first;
108 				rest = bp->m_size - first - size;
109 				bp->m_size = first;
110 				if (rest)
111 					rmfree(swapmap, rest, addr+size);
112 				return (addr);
113 			}
114 			/*
115 			 * Allocate from the map.
116 			 * If there is no space left of the piece
117 			 * we allocated from, move the rest of
118 			 * the pieces to the left.
119 			 */
120 			addr = bp->m_addr;
121 			bp->m_addr += size;
122 			if ((bp->m_size -= size) == 0) {
123 				do {
124 					bp++;
125 					(bp-1)->m_addr = bp->m_addr;
126 				} while ((bp-1)->m_size = bp->m_size);
127 			}
128 			if (mp == swapmap && addr % CLSIZE)
129 				panic("rmalloc swapmap");
130 			return (addr);
131 		}
132 	}
133 	return (0);
134 }
135 
136 /*
137  * Free the previously allocated space at addr
138  * of size units into the specified map.
139  * Sort addr into map and combine on
140  * one or both ends if possible.
141  */
142 rmfree(mp, size, addr)
143 	struct map *mp;
144 	register int size, addr;
145 {
146 	struct mapent *firstbp;
147 	register struct mapent *bp;
148 	register int t;
149 
150 	/*
151 	 * Both address and size must be
152 	 * positive, or the protocol has broken down.
153 	 */
154 	if (addr <= 0 || size <= 0)
155 		goto badrmfree;
156 	/*
157 	 * Locate the piece of the map which starts after the
158 	 * returned space (or the end of the map).
159 	 */
160 	firstbp = bp = (struct mapent *)(mp + 1);
161 	for (; bp->m_addr <= addr && bp->m_size != 0; bp++)
162 		continue;
163 	/*
164 	 * If the piece on the left abuts us,
165 	 * then we should combine with it.
166 	 */
167 	if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) {
168 		/*
169 		 * Check no overlap (internal error).
170 		 */
171 		if ((bp-1)->m_addr+(bp-1)->m_size > addr)
172 			goto badrmfree;
173 		/*
174 		 * Add into piece on the left by increasing its size.
175 		 */
176 		(bp-1)->m_size += size;
177 		/*
178 		 * If the combined piece abuts the piece on
179 		 * the right now, compress it in also,
180 		 * by shifting the remaining pieces of the map over.
181 		 */
182 		if (bp->m_addr && addr+size >= bp->m_addr) {
183 			if (addr+size > bp->m_addr)
184 				goto badrmfree;
185 			(bp-1)->m_size += bp->m_size;
186 			while (bp->m_size) {
187 				bp++;
188 				(bp-1)->m_addr = bp->m_addr;
189 				(bp-1)->m_size = bp->m_size;
190 			}
191 		}
192 		goto done;
193 	}
194 	/*
195 	 * Don't abut on the left, check for abutting on
196 	 * the right.
197 	 */
198 	if (addr+size >= bp->m_addr && bp->m_size) {
199 		if (addr+size > bp->m_addr)
200 			goto badrmfree;
201 		bp->m_addr -= size;
202 		bp->m_size += size;
203 		goto done;
204 	}
205 	/*
206 	 * Don't abut at all.  Make a new entry
207 	 * and check for map overflow.
208 	 */
209 	do {
210 		t = bp->m_addr;
211 		bp->m_addr = addr;
212 		addr = t;
213 		t = bp->m_size;
214 		bp->m_size = size;
215 		bp++;
216 	} while (size = t);
217 	/*
218 	 * Segment at bp is to be the delimiter;
219 	 * If there is not room for it
220 	 * then the table is too full
221 	 * and we must discard something.
222 	 */
223 	if (bp+1 > mp->m_limit) {
224 		/*
225 		 * Back bp up to last available segment.
226 		 * which contains a segment already and must
227 		 * be made into the delimiter.
228 		 * Discard second to last entry,
229 		 * since it is presumably smaller than the last
230 		 * and move the last entry back one.
231 		 */
232 		bp--;
233 		printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name,
234 		    (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size);
235 		bp[-1] = bp[0];
236 		bp[0].m_size = bp[0].m_addr = 0;
237 	}
238 done:
239 	/*
240 	 * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE!
241 	 */
242 	if ((mp == kernelmap) && kmapwnt) {
243 		kmapwnt = 0;
244 		wakeup((caddr_t)kernelmap);
245 	}
246 	return;
247 badrmfree:
248 	panic("bad rmfree");
249 }
250 
251 /*
252  * Allocate 'size' units from the given map, starting at address 'addr'.
253  * Return 'addr' if successful, 0 if not.
254  * This may cause the creation or destruction of a resource map segment.
255  *
256  * This routine will return failure status if there is not enough room
257  * for a required additional map segment.
258  *
259  * An attempt to use this on 'swapmap' will result in
260  * a failure return.  This is due mainly to laziness and could be fixed
261  * to do the right thing, although it probably will never be used.
262  */
263 rmget(mp, size, addr)
264 	register struct map *mp;
265 {
266 	register struct mapent *ep = (struct mapent *)(mp+1);
267 	register struct mapent *bp, *bp2;
268 
269 	if (size <= 0)
270 		panic("rmget");
271 	if (mp == swapmap)
272 		return (0);
273 	/*
274 	 * Look for a map segment containing the requested address.
275 	 * If none found, return failure.
276 	 */
277 	for (bp = ep; bp->m_size; bp++)
278 		if (bp->m_addr <= addr && bp->m_addr + bp->m_size > addr)
279 			break;
280 	if (bp->m_size == 0)
281 		return (0);
282 
283 	/*
284 	 * If segment is too small, return failure.
285 	 * If big enough, allocate the block, compressing or expanding
286 	 * the map as necessary.
287 	 */
288 	if (bp->m_addr + bp->m_size < addr + size)
289 		return (0);
290 	if (bp->m_addr == addr)
291 		if (bp->m_addr + bp->m_size == addr + size) {
292 			/*
293 			 * Allocate entire segment and compress map
294 			 */
295 			bp2 = bp;
296 			while (bp2->m_size) {
297 				bp2++;
298 				(bp2-1)->m_addr = bp2->m_addr;
299 				(bp2-1)->m_size = bp2->m_size;
300 			}
301 		} else {
302 			/*
303 			 * Allocate first part of segment
304 			 */
305 			bp->m_addr += size;
306 			bp->m_size -= size;
307 		}
308 	else
309 		if (bp->m_addr + bp->m_size == addr + size) {
310 			/*
311 			 * Allocate last part of segment
312 			 */
313 			bp->m_size -= size;
314 		} else {
315 			/*
316 			 * Allocate from middle of segment, but only
317 			 * if table can be expanded.
318 			 */
319 			for (bp2=bp; bp2->m_size; bp2++)
320 				;
321 			if (bp2 == mp->m_limit)
322 				return (0);
323 			while (bp2 > bp) {
324 				(bp2+1)->m_addr = bp2->m_addr;
325 				(bp2+1)->m_size = bp2->m_size;
326 				bp2--;
327 			}
328 			(bp+1)->m_addr = addr + size;
329 			(bp+1)->m_size =
330 			    bp->m_addr + bp->m_size - (addr + size);
331 			bp->m_size = addr - bp->m_addr;
332 		}
333 	return (addr);
334 }
335