1.\" $NetBSD: extent.9,v 1.8 1997/11/24 06:29:23 lukem Exp $ 2.\" 3.\" Copyright (c) 1996 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Jason R. Thorpe and Greg Hudson. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 3. All advertising materials mentioning features or use of this software 18.\" must display the following acknowledgement: 19.\" This product includes software developed by the NetBSD 20.\" Foundation, Inc. and its contributors. 21.\" 4. Neither the name of The NetBSD Foundation nor the names of its 22.\" contributors may be used to endorse or promote products derived 23.\" from this software without specific prior written permission. 24.\" 25.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 26.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 27.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 29.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 30.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 31.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 32.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 33.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 34.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 35.\" POSSIBILITY OF SUCH DAMAGE. 36.\" 37.Dd September 23, 1996 38.Dt EXTENT 9 39.Os NetBSD 40.Sh NAME 41.Nm extent , 42.Nm extent_create , 43.Nm extent_destroy , 44.Nm extent_alloc , 45.Nm extent_alloc_subregion , 46.Nm extent_alloc_region , 47.Nm extent_free , 48.Nm extent_print 49.Nd general purpose extent manager 50.Sh SYNOPSIS 51.Fd #include <sys/malloc.h> 52.Fd #include <sys/extent.h> 53.Ft struct extent * 54.Fn extent_create "char *name" "u_long start" "u_long end" "int mtype" "caddr_t storage" "size_t storagesize" "int flags" 55.Ft void 56.Fn extent_destroy "struct extent *ex" 57.Ft int 58.Fn extent_alloc "struct extent *ex" "u_long size" "u_long alignment" "u_long boundary" "int flags" "u_long *result" 59.Ft int 60.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" 61.Ft int 62.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags" 63.Ft int 64.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags" 65.Ft void 66.Fn extent_print "struct extent *ex" 67.Sh DESCRIPTION 68The NetBSD extent manager provides management of areas of memory or 69other number spaces (such as I/O ports). An opaque structure 70called an 71.Nm extent map 72keeps track of allocated regions within the number space. 73.Pp 74.Fn extent_create 75creates an extent map managing the space from 76.Fa start 77to 78.Fa end 79inclusive. All memory allocation will use the memory type 80.Fa mtype 81(see 82.Xr malloc 9 ). 83The extent map will have the name 84.Fa name , 85used for identification in case of an error. If the flag 86.Dv EX_NOCOALESCE 87is specified, only entire regions may be freed within the extent map, 88but internal coalescing of regions is disabled so that 89.Fn extent_free 90will never have to allocate a region descriptor and therefore will 91never fail. The caller must specify one of the flags 92.Dv EX_NOWAIT 93or 94.Dv EX_WAITOK , 95specifying whether it is okay to wait for memory allocated for 96extent map overhead. 97.Pp 98There are some applications which may want to use an extent map but 99can't use 100.Fn malloc 101and 102.Fn free . 103These applications may provide pre-allocated storage for 104all descriptor overhead with the arguments 105.Fa storage 106and 107.Fa storagesize . 108An extent of this type is called a 109.Nm fixed extent . 110If the application can safely use 111.Fn malloc 112and 113.Fn free , 114.Fa storage 115should be 116.Dv NULL . 117A fixed extent has a fixed number of region descriptors, so care 118should be taken to provide enough storage for them; alternatively, the 119flag 120.Dv EX_MALLOCOK 121may be passed to allocation requests to indicate that a fixed extent 122map may be extended using a call to 123.Fn malloc . 124.Pp 125.Fn extent_destroy 126destroys the extent map 127.Fa ex , 128freeing all allocated regions. If the extent is not a fixed extent, 129the region and internal extent descriptors themselves are freed. 130This function always succeeds. 131.Pp 132.Fn extent_alloc 133allocates a region in extent 134.Fa ex 135of size 136.Fa size 137that fits the provided parameters. There are two distinct allocation 138policies, which are selected by the 139.Fa flags 140argument: 141.Bl -tag -offset indent -width "XXXXXXXXX" 142.It Dv EX_FAST 143Allocate the first region that fits the provided paramters, regardless 144of resulting extent fragmentation. 145.It default 146Allocate the smallest region that is capable of holding the request, 147thus minimizing fragmentation of the extent. 148.El 149.Pp 150The caller must specify if waiting for space in the extent is allowed 151using the flag 152.Dv EX_WAITSPACE . 153If 154.Dv EX_WAITSPACE 155is not specified, the allocation will fail if the request can not be 156satisfied without sleeping. 157The caller must also specify, using the 158.Dv EX_NOWAIT 159or 160.Dv EX_WAITOK 161flags, if waiting for overhead allocation is allowed. 162The request will be aligned to 163.Fa alignment 164boundaries. Alignment values must be a power of 2. If no alignment 165is necessary, the value 1 should be specified. If 166.Fa boundary 167is nonzero, the allocated region will not cross any of the numbers 168which are a multiple of 169.Fa boundary . 170If the caller specifies the 171.Dv EX_BOUNDZERO 172flag, the boundary lines begin at zero. Otherwise, the boundary lines 173begin at the beginning of the extent. The allocated region may begin on a 174boundary address, but the end of the region will not touch nor cross 175it. A boundary argument smaller than the size of the request is 176invalid. Upon successful completion, 177.Fa *result 178will contain the start of the allocated region. 179.Pp 180.Fn extent_alloc_subregion 181is similar to 182.Fn extent_alloc , 183but it allows the caller to specify that the allocated region must 184fall within the subregion from 185.Fa substart 186to 187.Fa subend 188inclusive. The other arguments and the return values of 189.Fn extent_alloc_subregion 190are otherwise the same as those of 191.Fn extent_alloc . 192.Pp 193.Fn extent_alloc_region 194allocates the specific region in the extent map 195.Fa ex 196beginning at 197.Fa start 198with the size 199.Fa size . 200The caller must specify whether it is okay to wait for the indicated 201region to be free using the flag 202.Dv EX_WAITSPACE . 203If 204.Dv EX_WAITSPACE 205is not specified, the allocation will fail if the request can not be 206satisfied without sleeping. 207The caller must also specify, using the 208.Dv EX_NOWAIT 209or 210.Dv EX_WAITOK 211flags, if waiting for overhead allocation is allowed. 212.Pp 213.Fn extent_free 214frees a region of 215.Fa size 216bytes in extent 217.Fa ex 218starting at 219.Fa start . 220If the extent has the 221.Dv EX_NOCOALESCE 222property, only entire regions may be freed. If the extent has the 223.Dv EX_NOCOALESCE 224property and the caller attempts to free a partial region, behavior is 225undefined. The caller must specify one of the flags 226.Dv EX_NOWAIT 227or 228.Dv EX_WAITOK 229to specify whether waiting for memory is okay; these flags have 230meaning in the event that allocation of a region descriptor is 231required during the freeing process. This situation occurs only when 232a partial region that begins and ends in the middle of another region 233is freed. Behavior is undefined if invalid arguments are provided. 234.Pp 235.Fn extent_print 236Print out information about extent 237.Fa ex . 238This function always succeeds. Behavior is undefined if invalid 239arguments are provided. 240.Sh RETURN VALUES 241The behavior of all extent manager functions is undefined if given 242invalid arguments. 243.Fn extent_create 244returns the extent map on success, or 245.Dv NULL 246if it fails to allocate storage for the extent map. It always 247succeeds when creating a fixed extent or when given the flag 248.Dv EX_WAITOK . 249.Fn extent_alloc , 250.Fn extent_alloc_region , 251.Fn extent_alloc_subregion , 252and 253.Fn extent_free 254return one of the following values: 255.Bl -tag -offset indent -width "XXXXXXXX" 256.It Dv 0 257Operation was successful. 258.It Dv ENOMEM 259If 260.Dv EX_NOWAIT 261is specified, the extent manager was not able to allocate a region 262descriptor for the new region or to split a region when freeing a 263partial region. 264.It Dv EAGAIN 265Requested region is not available and 266.Dv EX_WAITSPACE 267was not specified. 268.It Dv EINTR 269Process received a signal while waiting for the requested region to 270become available in the extent. Does not apply to 271.Fn extent_free . 272.El 273.Sh EXAMPLES 274Here is an example of a (useless) function that uses several of the 275extent manager routines. 276.Bd -literal 277void 278func() 279{ 280 struct extent *foo_ex; 281 u_long region_start; 282 int error; 283 284 /* 285 * Extent "foo" manages a 256k region starting at 0x0 and 286 * only allows complete regions to be freed so that 287 * extent_free() never needs to allocate memory. 288 */ 289 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 290 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 291 292 /* 293 * Allocate an 8k region, aligned to a 4k boundary, which 294 * does not cross any of the 3 64k boundaries (at 64k, 295 * 128k, and 192k) within the extent. 296 */ 297 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 298 EX_NOWAIT, ®ion_start); 299 if (error) 300 panic("you lose"); 301 302 /* 303 * Give up the extent. 304 */ 305 extent_destroy(foo_ex); 306} 307.Ed 308.Sh CODE REFERENCES 309This section describes places within the NetBSD source tree where 310actual code implementing or using the extent manager can be found. 311All pathnames are relative to 312.Nm /usr/src . 313.Pp 314The extent manager itself is implemented within the file 315.Nm sys/kern/subr_extent.c . 316Function prototypes for the framework are located in 317.Nm sys/sys/extent.h . 318.Pp 319The i386 bus management code uses the extent manager for managing I/O 320ports and I/O memory. This code is in the file 321.Nm sys/arch/i386/i386/machdep.c . 322.Sh AUTHOR 323The NetBSD extent manager was architected and implemented by Jason 324R. Thorpe <thorpej@NetBSD.ORG>. Matthias Drochner 325<drochner@zelux6.zel.kfa-juelich.de> contributed to the initial 326testing and optimization of the implementation. Chris Demetriou 327<cgd@NetBSD.ORG> contributed many architectural suggestions. 328.Sh SEE ALSO 329.Xr malloc 9 . 330.Sh HISTORY 331The NetBSD extent manager appeared in 332.Nx 1.3 . 333