text: /*-
   * Copyright (c) 1982, 1986, 1993
   *	The Regents of the University of California.  All rights reserved.
   * (c) UNIX System Laboratories, Inc.
   * All or some portions of this file are derived from material licensed
   * to the University of California by American Telephone and Telegraph
   * Co. or Unix System Laboratories, Inc. and are reproduced herein with
   * the permission of UNIX System Laboratories, Inc.
   *
   * %sccs.include.proprietary.c%
   *
   *	@(#)subr_rmap.c	8.2 (Berkeley) 01/21/94
   */
  
  #include <sys/param.h>
  #include <sys/systm.h>
  #include <sys/map.h>
  #include <sys/dmap.h>		/* XXX */
  #include <sys/proc.h>
  #include <sys/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.
   */
  void
  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;
  }
  
  /*
   * A piece of memory of at least size units is allocated from the
   * specified map using a first-fit algorithm. It returns the starting
   * address of the allocated space.
   *
   * This routine knows about and handles the interleaving of the swapmap.
   */
  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) < 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);
  }
  
  /*
   * The previously allocated space at addr of size units is freed
   * into the specified map. This routine is responsible for sorting
   * the frred space into the correct location in the map, and coalescing
   * it with free space on either side if they adjoin.
   */
  void
  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;
  			}
  		}
  		return;
  	}
  	/*
  	 * 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;
  		return;
  	}
  	/*
  	 * 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;
  	}
  	return;
  badrmfree:
  	panic("bad rmfree");
  }
  