For the last couple of months I've been dropping hints about my extent 
manager, which, among other things, is going to be used for the 
<machine/bus.h> and ISA bounce buffer stuff Chris has been working on (at 
least, that's what he told me last time we talked about it :-)

Think of an extent map as a resource map on steroids.

I think I've finally got all of the features that have been asked for 
implemented, so I thought I'd open it up for general comments now...

Attached below is a rough interface description.

Share and enjoy...

--------------------------------------------------------------------------
Jason R. Thorpe                                       thorpej@nas.nasa.gov
NASA Ames Research Center                               Home: 408.866.1912
NAS: M/S 258-6                                          Work: 415.604.0935
Moffett Field, CA 94035                                Pager: 415.428.6939

----- snip -----

This document describes the interface to the proposed General Purpose
Extent Manager.

The caller must include the file <sys/extent.h>, which defines data
structures and declares prototypes for the functions described below.

Callers of extent_create() must include the file <sys/malloc.h> to
get the defintions of the memory types used in extent_create() calls.

struct extent *
extent_create(name, start, end, mtype, storage, storagesize, flags)
	char *name;
	u_long start, end;
	int mtype;
	caddr_t storage;
	size_t storagesize;
	int flags;

	Create an extent map, managing the space from "start" to "end".
	All memory allocation will use the memory type "mtype".  The
	extent map will have the name "name", used for identification
	in case of an error.

	There are some applications which may use an extent map but
	can't, for one reason or another, use malloc() and free().
	These applications may provide pre-allocated storage for
	all descriptor overhead with the arguments "storage" and
	"storagesize".  An extent of this type is called a "fixed extent".
	If the application can safely use malloc() and free(), "storage"
	should be NULL.  A fixed extent has a fixed number of region
	descriptors, so care should be taken to provide enough storage
	for them.  All fixed extent descriptors are allocated on long
	boundaries.

	The caller may provide the flag EX_NOBLOB.  If EX_NOBLOB is set,
	the regions behave as "solid chunks, not goey blobs".  That is,
	coalescing of regions (for saving overhead) is disallowed,
	and entire regions must be freed (rather than partial regions).

	Returns a pointer to the extent descriptor on success, NULL
	if memory allocation fails.  This function always succeeds
	when a fixed extent is created.  Behavior is undefined if
	invalid arguments are provided.

void
extent_destroy(ex)
	struct extent *ex;

	Destroy extent map "ex".  All regions are freed.  If the extent
	is not a fixed extent, the region and extent descriptors themselves
	are freed.

	This function always succeeds.  Behavior is undefined if
	invalid arguments are provided.

int
extent_alloc_region(ex, start, size, flags)
	struct extent *ex;
	u_long start, size;
	int flags;

	Allocate a specific region in extent map "ex", beginning
	at "start" with size "size".  The caller must pass one of
	the following flags:

		EX_NOWAIT	not safe to sleep

		EX_WAITOK	safe to sleep

	If the request conflicts with an allocated region, the
	calling process will wait until space becomes available
	if EX_WAITOK is specified.

	This function returns one of the following values:

		0		Allocation was successful.

		EINTR		Process recieved a signal while
				waiting for the requested region to
				become available in the extent.

		ENOMEM		The extent manager was not able to
				allocate a region descriptor for
				the request.

		EAGAIN		Requested region is not available
				and EX_NOWAIT was specified.

	Behavior is undefined if invalid arguments are provided.

int
extent_alloc(ex, size, alignment, boundary, flags, result)
	struct extent *ex;
	u_long size, alignment, boundary;
	int flags;
	u_long result;

	Allocate a region in extent "ex" of size "size" that fits
	the provided parameters.  There are two distinct allocation
	policies, which are selected by the "flags" argument:

		EX_FAST		Allocate the first region that fits
				the provided parameters, regardless
				of resulting extent fragmentation.

		default (0)	Allocate the smallest region that
				is capable of holding the request,
				thus minimizing fragmentation of the
				extent.

	The caller may specify if waiting for space in the extent
	is allowed, as in extent_alloc_region().

	The request will be aligned to "alignment" boundaries.  If
	no alignment is requested, the value "1" should be specified.
	The value "1" does not actually disable alignment, but merely
	aligns regions on 1-byte boundaries (which has the same effect).
	Alignment values must be a power of 2.  The value "0" is an
	invalid alignment value.

	The caller may also specify a boundary within the extent that
	is not to be crossed during allocation.  To enable this feature,
	the caller should provide a non-zero value for "boundary".  If
	the caller does not wish to perform boundary checking, the value
	"0" should be specified.  Boundary checking is implemented such
	that a region may begin on a boundary, but the end of the region
	may not touch nor cross it.  A boundary argument smaller than
	the size of the request is invalid.

	This function returns one of the following values:

		0		Allocation was successful.

		EINTR		Process recieved a signal while
				waiting for the requested region to
				become available in the extent.

		ENOMEM		The extent manager was not able to
				allocate a region descriptor for
				the request.

		EAGAIN		Requested region is not available
				and EX_NOWAIT was specified.

	Upon successful completion, *result will contain the start
	of the allocated region.  Behavior is undefined if invalid
	arguments are provided.

	The following code fragment is an example of the use
	of extent_alloc():

	void
	func()
	{
		extern struct extent *foo_ex;
		u_long region_start;
		int error;

		/*
		 * Extent "foo" starts at 0x0 and ends at
		 * 0x40000 (256k).
		 *
		 * Allocate an 8k region, aligned to a 4k
		 * boundary, which does not cross any of
		 * the 3 64k boundaries (at 64k, 128k, and
		 * 192k) within the extent.
		 */
		error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000,
		    EX_NOWAIT, &region_start);
		if (error)
			panic("you lose");
	}

int
extent_free(ex, start, size, flags)
	struct extent *ex;
	u_long start, size;
	int flags;

	Free a region of "size" bytes in extent "ex" starting at "start".

	If the extent has the EX_NOBLOB property, only entire regions
	may be freed.  If the extent as the EX_NOBLOB property and
	the caller attempts to free a partial region, behavior is
	undefined.

	The caller must specify one of the following flags:

		EX_WAITOK	safe to sleep

		EX_NOWAIT	not safe to sleep

	These flags have meaning in the event that allocation of
	a region descriptor is required during the freeing process.
	This situation occurs only when a partial region that begins
	and ends in the middle of another region is freed.

	This function returns one of the following values:

		0		Region was successfully freed.

		ENOMEM		Allocation of a region descriptor
				was required and failed.  Region
				was not freed.

	Behavior is undefined if invalid arguments are provided.

void
extent_print(ex)
	struct extent *ex;

	Print out information about extent "ex".  This function always
	succeeds.  Behavoir is undefined if invalid arguments are
	provided.