Source to kern/subr_rmap.c

Enter a symbol's name here to quickly find it. 
/*
 * Copyright (C) 1992 Wolfgang Solfrank.
 * Copyright (C) 1992 TooLs GmbH.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by TooLs GmbH.
 * 4. The name of TooLs GmbH may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY TOOLS GMBH ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL TOOLS GMBH BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * Copyright (c) 1982, 1986 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	from: @(#)subr_rmap.c	7.9 (Berkeley) 5/11/91
 *	subr_rmap.c,v 1.2 1993/07/07 06:00:15 cgd Exp
 */

#include "param.h"
#include "systm.h"
#include "map.h"
#include "dmap.h"		/* XXX */
#include "proc.h"
#include "kernel.h"

/*
 * Resource map handling routines.
 */

/*
 * Initialize map mp to have (mapsize-1) 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;
{
	/*
	 * Body deleted.
	 */
	/*
	 * and reimplemented by ws.
	 * Assume small maps. Keep it sorted by addr with empty mapents last.
	 */
	register struct mapent *ep;
	
	/* mapsize had better be at least 2 */
	if (mapsize < 2 || addr <= 0 || size < 0) {
	    panic("rminit");
	}
	mp->m_name = name;
	mp->m_limit = (struct mapent *)mp + mapsize;
	/* initially all is free */
	ep = (struct mapent *)mp + 1;
	ep->m_size = size;
	ep->m_addr = addr;
	while (++ep < mp->m_limit) {
	    ep->m_addr = 0;
	}
}

long
rmalloc(mp, size)
	register struct map *mp;
	long size;
{
	/*
	 * Body deleted.
	 */
	/*
	 * and reimplemented by ws.
	 */
	register struct mapent *ep, *fp;
	long addr;
	
	/* first check arguments */
	if (size < 0) {
	    panic("rmalloc");
	}
	if (!size) {
	    return 0;
	}
	addr = 0;
	fp = 0;
	/* try to find the smallest fit */
	for (ep = (struct mapent *)mp + 1; ep < mp->m_limit; ep++) {
	    if (!ep->m_addr) {
		break;
	    } else if (ep->m_size == size) {
		addr = ep->m_addr;
		bcopy(ep + 1,ep,(char *)mp->m_limit - (char *)(ep + 1));
		return addr;
	    } else if (ep->m_size > size
		       && (!fp
			   || fp->m_size > ep->m_size)) {
		fp = ep;
	    }
	}
	if (fp) {
	    addr = fp->m_addr;
	    fp->m_addr += size;
	    fp->m_size -= size;
	}
	return addr;
}

rmfree(mp, size, addr)
	struct map *mp;
	long size, addr;
{
	/*
	 * Body deleted.
	 */
	/*
	 * and reimplemented by ws.
	 */
	register struct mapent *ep, *fp;
	
	if (size <= 0 || addr <= 0) {
	    panic("rmfree");
	}
	
	while (1) {
	    fp = 0;
	    for (ep = (struct mapent *)mp + 1; ep < mp->m_limit; ep++) {
		if (!ep->m_addr) {
		    break;
		}
		if (ep->m_addr + ep->m_size == addr) {
		    ep->m_size += size;
		    if (ep < mp->m_limit && ep[1].m_addr && (addr += size) >= ep[1].m_addr) {
			if (addr > ep[1].m_addr) {
			    panic("rmfree");
			}
			ep->m_size += ep[1].m_size;
			bcopy(ep + 2, ep + 1, (char *)mp->m_limit - (char *)(ep + 2));
		    }
		    return;
		}
		if (addr + size == ep->m_addr) {
		    ep->m_addr = addr;
		    ep->m_size += size;
		    return;
		}
		if (addr < ep->m_addr
		    && !mp->m_limit[-1].m_addr) {
		    bcopy(ep,ep + 1,(char *)(mp->m_limit - 1) - (char *)ep);
		    ep->m_addr = addr;
		    ep->m_size = size;
		    return;
		}
		if (!fp || fp->m_size > ep->m_size) {
		    fp = ep;
		}
	    }
	    if (ep != (struct mapent *)mp + 1
		&& ep[-1].m_addr + ep[-1].m_size == addr) {
		(--ep)->m_size += size;
		return;
	    }
	    if (ep != mp->m_limit) {
		ep->m_addr = addr;
		ep->m_size = size;
		return;
	    }
	    /* sorry, have to loose space */
	    /* fp contains the smallest slot */
	    if (fp->m_size > size) {
		printf("rmfree: map '%s' looses space (%d)\n",mp->m_name,size);
	    } else {
		printf("rmfree: map '%s' looses space (%d)\n",mp->m_name,fp->m_size);
		bcopy(fp + 1,fp,(char *)(mp->m_limit - 1) - (char *)fp);
		mp->m_limit[-1].m_addr = 0;
		/* now retry */
	    }
	}
}