.\" $NetBSD: extent.9,v 1.33 2017/04/06 10:42:14 abhinav Exp $
.\"
.\" Copyright (c) 1996, 1998 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Jason R. Thorpe and Greg Hudson.
.\"
.\" 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.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. 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 FOUNDATION 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.
.\"
.Dd July 14, 2012
.Dt EXTENT 9
.Os
.Sh NAME
.Nm extent ,
.Nm extent_create ,
.Nm extent_destroy ,
.Nm extent_alloc ,
.Nm extent_alloc_subregion ,
.Nm extent_alloc1 ,
.Nm extent_alloc_subregion1 ,
.Nm extent_alloc_region ,
.Nm extent_free ,
.Nm extent_print
.Nd general purpose extent manager
.Sh SYNOPSIS
.In sys/malloc.h
.In sys/extent.h
.Ft struct extent *
.Fn extent_create "char *name" "u_long start" "u_long end" "void *storage" "size_t storagesize" "int flags"
.Ft void
.Fn extent_destroy "struct extent *ex"
.Ft int
.Fn extent_alloc "struct extent *ex" "u_long size" "u_long alignment" "u_long boundary" "int flags" "u_long *result"
.Ft int
.Fn extent_alloc_subregion "struct extent *ex" "u_long substart" "u_long subend" "u_long size" "u_long alignment" "u_long boundary" "u_long flags" "u_long *result"
.Ft int
.Fn extent_alloc1 "struct extent *ex" "u_long size" "u_long alignment" "u_long skew" "u_long boundary" "int flags" "u_long *result"
.Ft int
.\" too many arguments for a single .Fn
.Fo extent_alloc_subregion1
.Fa "struct extent *ex"
.Fa "u_long substart"
.Fa "u_long subend"
.Fa "u_long size"
.Fa "u_long alignment"
.Fa "u_long skew"
.Fa "u_long boundary"
.Fa "u_long flags"
.Fa "u_long *result"
.Fc
.Ft int
.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags"
.Ft int
.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags"
.Ft void
.Fn extent_print "struct extent *ex"
.Sh DESCRIPTION
The
.Nx
extent manager provides management of areas of memory or
other number spaces (such as I/O ports).
An opaque structure called an
.Nm extent map
keeps track of allocated regions within the number space.
.Pp
.Fn extent_create
creates an extent map managing the space from
.Fa start
to
.Fa end
inclusive.
The extent map will have the name
.Fa name ,
used for identification in case of an error.
If the flag
.Dv EX_NOCOALESCE
is specified, only entire regions may be freed within the extent map,
but internal coalescing of regions is disabled so that
.Fn extent_free
will never have to allocate a region descriptor and therefore will
never fail.
The caller must specify one of the flags
.Dv EX_NOWAIT
or
.Dv EX_WAITOK ,
specifying whether it is okay to wait for memory allocated for
extent map overhead.
.Pp
There are some applications which may want to use an extent map but
can't use
.Fn malloc
and
.Fn free .
These applications may provide pre-allocated storage for
all descriptor overhead with the arguments
.Fa storage
and
.Fa storagesize .
An extent of this type is called a
.Nm fixed extent .
If the application can safely use
.Fn malloc
and
.Fn free ,
.Fa storage
should be
.Dv NULL .
A fixed extent has a fixed number of region descriptors, so care
should be taken to provide enough storage for them; alternatively, the
flag
.Dv EX_MALLOCOK
may be passed to allocation requests to indicate that a fixed extent
map may be extended using a call to
.Fn malloc .
.Pp
.Fn extent_destroy
destroys the extent map
.Fa ex ,
freeing all allocated regions.
If the extent is not a fixed extent, the region and internal extent
descriptors themselves are freed.
This function always succeeds.
.Pp
.Fn extent_alloc
allocates a region in extent
.Fa ex
of size
.Fa size
that fits the provided parameters.
There are two distinct allocation policies, which are selected by the
.Fa flags
argument:
.Bl -tag -offset indent -width "XXXXXXXXX"
.It Dv EX_FAST
Allocate the first region that fits the provided parameters, regardless
of resulting extent fragmentation.
.It default
Allocate the smallest region that is capable of holding the request,
thus minimizing fragmentation of the extent.
.El
.Pp
The caller must specify if waiting for space in the extent is allowed
using the flag
.Dv EX_WAITSPACE .
If
.Dv EX_WAITSPACE
is not specified, the allocation will fail if the request can not be
satisfied without sleeping.
The caller must also specify, using the
.Dv EX_NOWAIT
or
.Dv EX_WAITOK
flags, if waiting for overhead allocation is allowed.
The request will be aligned to
.Fa alignment
boundaries.
Alignment values must be a power of 2.
If no alignment is necessary, the value 1 should be specified.
If
.Fa boundary
is nonzero, the allocated region will not cross any of the numbers
which are a multiple of
.Fa boundary .
If the caller specifies the
.Dv EX_BOUNDZERO
flag, the boundary lines begin at zero.
Otherwise, the boundary lines begin at the beginning of the extent.
The allocated region may begin on a boundary address, but the end of
the region will not touch nor cross it.
A boundary argument smaller than the size of the request is invalid.
Upon successful completion,
.Fa *result
will contain the start of the allocated region.
.Pp
.Fn extent_alloc_subregion
is similar to
.Fn extent_alloc ,
but it allows the caller to specify that the allocated region must
fall within the subregion from
.Fa substart
to
.Fa subend
inclusive.
The other arguments and the return values of
.Fn extent_alloc_subregion
are otherwise the same as those of
.Fn extent_alloc .
.Pp
.Fn extent_alloc_region
allocates the specific region in the extent map
.Fa ex
beginning at
.Fa start
with the size
.Fa size .
The caller must specify whether it is okay to wait for the indicated
region to be free using the flag
.Dv EX_WAITSPACE .
If
.Dv EX_WAITSPACE
is not specified, the allocation will fail if the request can not be
satisfied without sleeping.
The caller must also specify, using the
.Dv EX_NOWAIT
or
.Dv EX_WAITOK
flags, if waiting for overhead allocation is allowed.
.Pp
The
.Fn extent_alloc1
and
.Fn extent_alloc_subregion1
functions are extensions that take one additional argument,
.Fa skew ,
that modifies the requested alignment result in the following way:
the value
.Pq Fa result No - Fa skew
is aligned to
.Fa alignment
boundaries.
.Fa skew
must be a smaller number than
.Fa alignment .
Also, a boundary argument smaller than the sum of the requested skew
and the size of the request is invalid.
.Pp
.Fn extent_free
frees a region of
.Fa size
bytes in extent
.Fa ex
starting at
.Fa start .
If the extent has the
.Dv EX_NOCOALESCE
property, only entire regions may be freed.
If the extent has the
.Dv EX_NOCOALESCE
property and the caller attempts to free a partial region, behavior is
undefined.
The caller must specify one of the flags
.Dv EX_NOWAIT
or
.Dv EX_WAITOK
to specify whether waiting for memory is okay; 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.
Behavior is undefined if invalid arguments are provided.
.Pp
.Fn extent_print
Print out information about extent
.Fa ex .
This function always succeeds.
Behavior is undefined if invalid arguments are provided.
.Sh LOCKING
The extent manager performs all necessary locking on the extent map
itself, and any other data structures internal to the extent manager.
The locks used by the extent manager are simplelocks, and will never sleep
.Po
see
.Xr lock 9
.Pc .
This should be taken into account when designing the locking protocol
for users of the extent manager.
.Sh RETURN VALUES
The behavior of all extent manager functions is undefined if given
invalid arguments.
.Fn extent_create
returns the extent map on success, or
.Dv NULL
if it fails to allocate storage for the extent map.
It always succeeds when creating a fixed extent or when given the flag
.Dv EX_WAITOK .
.Fn extent_alloc ,
.Fn extent_alloc_region ,
.Fn extent_alloc_subregion ,
and
.Fn extent_free
return one of the following values:
.Bl -tag -offset indent -width "XXXXXXXX"
.It Dv 0
Operation was successful.
.It Dv ENOMEM
If
.Dv EX_NOWAIT
is specified, the extent manager was not able to allocate a region
descriptor for the new region or to split a region when freeing a
partial region.
.It Dv EAGAIN
Requested region is not available and
.Dv EX_WAITSPACE
was not specified.
.It Dv EINTR
Process received a signal while waiting for the requested region to
become available in the extent.
Does not apply to
.Fn extent_free .
.El
.Sh EXAMPLES
Here is an example of a (useless) function that uses several of the
extent manager routines.
.Bd -literal
void
func()
{
	struct extent *foo_ex;
	u_long region_start;
	int error;

	/*
	 * Extent "foo" manages a 256k region starting at 0x0 and
	 * only allows complete regions to be freed so that
	 * extent_free() never needs to allocate memory.
	 */
	foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF,
	    NULL, 0, EX_WAITOK | EX_NOCOALESCE);

	/*
	 * 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, \*[Am]region_start);
	if (error)
		panic("you lose");

	/*
	 * Give up the extent.
	 */
	extent_destroy(foo_ex);
}
.Ed
.Sh CODE REFERENCES
The extent manager itself is implemented within the file
.Pa sys/kern/subr_extent.c .
Function prototypes for the framework are located in
.Pa sys/sys/extent.h .
.Pp
The i386 bus management code uses the extent manager for managing I/O
ports and I/O memory.
This code is in the file
.Pa sys/arch/i386/i386/machdep.c .
.Sh SEE ALSO
.Xr malloc 9
.Sh HISTORY
The
.Nx
extent manager appeared in
.Nx 1.3 .
.Sh AUTHORS
The
.Nx
extent manager was architected and implemented by
.An Jason R. Thorpe
.Aq thorpej@NetBSD.org .
.An Matthias Drochner
.Aq drochner@zelux6.zel.kfa-juelich.de
contributed to the initial testing and optimization of the implementation.
.An Chris Demetriou
.Aq cgd@NetBSD.org
contributed many architectural suggestions.