[unix-history] / usr / src / sys / kern / subr_rmap.c

/*
 * Copyright (c) 1982, 1986 Regents of the University of California.
 * All rights reserved.  The Berkeley software License Agreement
 * specifies the terms and conditions for redistribution.
 *
 *	@(#)subr_rmap.c	7.3 (Berkeley) %G%
 */

#include "param.h"
#include "systm.h"
#include "map.h"
#include "user.h"
#include "proc.h"
#include "text.h"
#include "kernel.h"

/*
 * Resource map handling routines.
 *
 * A resource map is an array of structures each
 * of which describes a segment of the address space of an available
 * resource.  The segments are described by their base address and
 * length, and sorted in address order.  Each resource map has a fixed
 * maximum number of segments allowed.  Resources are allocated
 * by taking part or all of one of the segments of the map.
 *
 * Returning of resources will require another segment if
 * the returned resources are not adjacent in the address
 * space to an existing segment.  If the return of a segment
 * would require a slot which is not available, then one of
 * the resource map segments is discarded after a warning is printed.
 * Returning of resources may also cause the map to collapse
 * by coalescing two existing segments and the returned space
 * into a single segment.  In this case the resource map is
 * made smaller by copying together to fill the resultant gap.
 *
 * N.B.: the current implementation uses a dense array and does
 * not admit the value ``0'' as a legal address, since that is used
 * as a delimiter.
 */

/*
 * Initialize map mp to have (mapsize-2) segments
 * and to be called ``name'', which we print if
 * the slots become so fragmented that we lose space.
 * The map itself is initialized with size elements free
 * starting at addr.
 */
rminit(mp, size, addr, name, mapsize)
	register struct map *mp;
	long size, addr;
	char *name;
	int mapsize;
{
	register struct mapent *ep = (struct mapent *)(mp+1);

	mp->m_name = name;
/* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */
	/*
	 * One of the mapsize slots is taken by the map structure,
	 * segments has size 0 and addr 0, and acts as a delimiter.
	 * We insure that we never use segments past the end of
	 * the array which is given by mp->m_limit.
	 * Instead, when excess segments occur we discard some resources.
	 */
	mp->m_limit = (struct mapent *)&mp[mapsize];
	/*
	 * Simulate a rmfree(), but with the option to
	 * call with size 0 and addr 0 when we just want
	 * to initialize without freeing.
	 */
	ep->m_size = size;
	ep->m_addr = addr;
	(++ep)->m_size = 0;
	ep->m_addr = 0;
}

/*
 * Allocate 'size' units from the given
 * map. Return the base of the allocated space.
 * In a map, the addresses are increasing and the
 * list is terminated by a 0 size.
 *
 * Algorithm is first-fit.
 *
 * This routine knows about the interleaving of the swapmap
 * and handles that.
 */
long
rmalloc(mp, size)
	register struct map *mp;
	long size;
{
	register struct mapent *ep = (struct mapent *)(mp+1);
	register int addr;
	register struct mapent *bp;
	swblk_t first, rest;

	if (size <= 0 || mp == swapmap && size > dmmax)
		panic("rmalloc");
	/*
	 * Search for a piece of the resource map which has enough
	 * free space to accomodate the request.
	 */
	for (bp = ep; bp->m_size; bp++) {
		if (bp->m_size >= size) {
			/*
			 * If allocating from swapmap,
			 * then have to respect interleaving
			 * boundaries.
			 */
			if (mp == swapmap && nswdev > 1 &&
			    (first = dmmax - bp->m_addr%dmmax) < bp->m_size) {
				if (bp->m_size - first < size)
					continue;
				addr = bp->m_addr + first;
				rest = bp->m_size - first - size;
				bp->m_size = first;
				if (rest)
					rmfree(swapmap, rest, addr+size);
				return (addr);
			}
			/*
			 * Allocate from the map.
			 * If there is no space left of the piece
			 * we allocated from, move the rest of
			 * the pieces to the left.
			 */
			addr = bp->m_addr;
			bp->m_addr += size;
			if ((bp->m_size -= size) == 0) {
				do {
					bp++;
					(bp-1)->m_addr = bp->m_addr;
				} while ((bp-1)->m_size = bp->m_size);
			}
			if (mp == swapmap && addr % CLSIZE)
				panic("rmalloc swapmap");
			return (addr);
		}
	}
	return (0);
}

/*
 * Free the previously allocated space at addr
 * of size units into the specified map.
 * Sort addr into map and combine on
 * one or both ends if possible.
 */
rmfree(mp, size, addr)
	struct map *mp;
	long size, addr;
{
	struct mapent *firstbp;
	register struct mapent *bp;
	register int t;

	/*
	 * Both address and size must be
	 * positive, or the protocol has broken down.
	 */
	if (addr <= 0 || size <= 0)
		goto badrmfree;
	/*
	 * Locate the piece of the map which starts after the
	 * returned space (or the end of the map).
	 */
	firstbp = bp = (struct mapent *)(mp + 1);
	for (; bp->m_addr <= addr && bp->m_size != 0; bp++)
		continue;
	/*
	 * If the piece on the left abuts us,
	 * then we should combine with it.
	 */
	if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) {
		/*
		 * Check no overlap (internal error).
		 */
		if ((bp-1)->m_addr+(bp-1)->m_size > addr)
			goto badrmfree;
		/*
		 * Add into piece on the left by increasing its size.
		 */
		(bp-1)->m_size += size;
		/*
		 * If the combined piece abuts the piece on
		 * the right now, compress it in also,
		 * by shifting the remaining pieces of the map over.
		 */
		if (bp->m_addr && addr+size >= bp->m_addr) {
			if (addr+size > bp->m_addr)
				goto badrmfree;
			(bp-1)->m_size += bp->m_size;
			while (bp->m_size) {
				bp++;
				(bp-1)->m_addr = bp->m_addr;
				(bp-1)->m_size = bp->m_size;
			}
		}
		goto done;
	}
	/*
	 * Don't abut on the left, check for abutting on
	 * the right.
	 */
	if (addr+size >= bp->m_addr && bp->m_size) {
		if (addr+size > bp->m_addr)
			goto badrmfree;
		bp->m_addr -= size;
		bp->m_size += size;
		goto done;
	}
	/*
	 * Don't abut at all.  Make a new entry
	 * and check for map overflow.
	 */
	do {
		t = bp->m_addr;
		bp->m_addr = addr;
		addr = t;
		t = bp->m_size;
		bp->m_size = size;
		bp++;
	} while (size = t);
	/*
	 * Segment at bp is to be the delimiter;
	 * If there is not room for it 
	 * then the table is too full
	 * and we must discard something.
	 */
	if (bp+1 > mp->m_limit) {
		/*
		 * Back bp up to last available segment.
		 * which contains a segment already and must
		 * be made into the delimiter.
		 * Discard second to last entry,
		 * since it is presumably smaller than the last
		 * and move the last entry back one.
		 */
		bp--;
		printf("%s: rmap ovflo, lost [%d,%d)\n", mp->m_name,
		    (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size);
		bp[-1] = bp[0];
		bp[0].m_size = bp[0].m_addr = 0;
	}
done:
	/*
	 * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE!
	 */
	if ((mp == kernelmap) && kmapwnt) {
		kmapwnt = 0;
		wakeup((caddr_t)kernelmap);
	}
	return;
badrmfree:
	panic("bad rmfree");
}

/*
 * Allocate 'size' units from the given map, starting at address 'addr'.
 * Return 'addr' if successful, 0 if not.
 * This may cause the creation or destruction of a resource map segment.
 *
 * This routine will return failure status if there is not enough room
 * for a required additional map segment.
 *
 * An attempt to use this on 'swapmap' will result in
 * a failure return.  This is due mainly to laziness and could be fixed
 * to do the right thing, although it probably will never be used.
 */
rmget(mp, size, addr)
	register struct map *mp;
{
	register struct mapent *ep = (struct mapent *)(mp+1);
	register struct mapent *bp, *bp2;

	if (size <= 0)
		panic("rmget");
	if (mp == swapmap)
		return (0);
	/*
	 * Look for a map segment containing the requested address.
	 * If none found, return failure.
	 */
	for (bp = ep; bp->m_size; bp++)
		if (bp->m_addr <= addr && bp->m_addr + bp->m_size > addr)
			break;
	if (bp->m_size == 0)
		return (0);

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