1.\" $NetBSD: extent.9,v 1.22 2002/02/13 08:18:41 ross Exp $ 2.\" 3.\" Copyright (c) 1996, 1998 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 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 \*[Lt]sys/malloc.h\*[Gt] 52.Fd #include \*[Lt]sys/extent.h\*[Gt] 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_alloc1 "struct extent *ex" "u_long size" "u_long alignment" "u_long skew" "u_long boundary" "int flags" "u_long *result" 63.Ft int 64.\" too many arguments for a single .Fn 65.Fo extent_alloc_subregion1 66.Fa "struct extent *ex" 67.Fa "u_long substart" 68.Fa "u_long subend" 69.Fa "u_long size" 70.Fa "u_long alignment" 71.Fa "u_long skew" 72.Fa "u_long boundary" 73.Fa "u_long flags" 74.Fa "u_long *result" 75.Fc 76.Ft int 77.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags" 78.Ft int 79.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags" 80.Ft void 81.Fn extent_print "struct extent *ex" 82.Sh DESCRIPTION 83The 84.Nx 85extent manager provides management of areas of memory or 86other number spaces (such as I/O ports). An opaque structure 87called an 88.Nm extent map 89keeps track of allocated regions within the number space. 90.Pp 91.Fn extent_create 92creates an extent map managing the space from 93.Fa start 94to 95.Fa end 96inclusive. All memory allocation will use the memory type 97.Fa mtype 98.Po 99see 100.Xr malloc 9 101.Pc . 102The extent map will have the name 103.Fa name , 104used for identification in case of an error. If the flag 105.Dv EX_NOCOALESCE 106is specified, only entire regions may be freed within the extent map, 107but internal coalescing of regions is disabled so that 108.Fn extent_free 109will never have to allocate a region descriptor and therefore will 110never fail. The caller must specify one of the flags 111.Dv EX_NOWAIT 112or 113.Dv EX_WAITOK , 114specifying whether it is okay to wait for memory allocated for 115extent map overhead. 116.Pp 117There are some applications which may want to use an extent map but 118can't use 119.Fn malloc 120and 121.Fn free . 122These applications may provide pre-allocated storage for 123all descriptor overhead with the arguments 124.Fa storage 125and 126.Fa storagesize . 127An extent of this type is called a 128.Nm fixed extent . 129If the application can safely use 130.Fn malloc 131and 132.Fn free , 133.Fa storage 134should be 135.Dv NULL . 136A fixed extent has a fixed number of region descriptors, so care 137should be taken to provide enough storage for them; alternatively, the 138flag 139.Dv EX_MALLOCOK 140may be passed to allocation requests to indicate that a fixed extent 141map may be extended using a call to 142.Fn malloc . 143.Pp 144.Fn extent_destroy 145destroys the extent map 146.Fa ex , 147freeing all allocated regions. If the extent is not a fixed extent, 148the region and internal extent descriptors themselves are freed. 149This function always succeeds. 150.Pp 151.Fn extent_alloc 152allocates a region in extent 153.Fa ex 154of size 155.Fa size 156that fits the provided parameters. There are two distinct allocation 157policies, which are selected by the 158.Fa flags 159argument: 160.Bl -tag -offset indent -width "XXXXXXXXX" 161.It Dv EX_FAST 162Allocate the first region that fits the provided parameters, regardless 163of resulting extent fragmentation. 164.It default 165Allocate the smallest region that is capable of holding the request, 166thus minimizing fragmentation of the extent. 167.El 168.Pp 169The caller must specify if waiting for space in the extent is allowed 170using the flag 171.Dv EX_WAITSPACE . 172If 173.Dv EX_WAITSPACE 174is not specified, the allocation will fail if the request can not be 175satisfied without sleeping. 176The caller must also specify, using the 177.Dv EX_NOWAIT 178or 179.Dv EX_WAITOK 180flags, if waiting for overhead allocation is allowed. 181The request will be aligned to 182.Fa alignment 183boundaries. Alignment values must be a power of 2. If no alignment 184is necessary, the value 1 should be specified. If 185.Fa boundary 186is nonzero, the allocated region will not cross any of the numbers 187which are a multiple of 188.Fa boundary . 189If the caller specifies the 190.Dv EX_BOUNDZERO 191flag, the boundary lines begin at zero. Otherwise, the boundary lines 192begin at the beginning of the extent. The allocated region may begin on a 193boundary address, but the end of the region will not touch nor cross 194it. A boundary argument smaller than the size of the request is 195invalid. Upon successful completion, 196.Fa *result 197will contain the start of the allocated region. 198.Pp 199.Fn extent_alloc_subregion 200is similar to 201.Fn extent_alloc , 202but it allows the caller to specify that the allocated region must 203fall within the subregion from 204.Fa substart 205to 206.Fa subend 207inclusive. The other arguments and the return values of 208.Fn extent_alloc_subregion 209are otherwise the same as those of 210.Fn extent_alloc . 211.Pp 212.Fn extent_alloc_region 213allocates the specific region in the extent map 214.Fa ex 215beginning at 216.Fa start 217with the size 218.Fa size . 219The caller must specify whether it is okay to wait for the indicated 220region to be free using the flag 221.Dv EX_WAITSPACE . 222If 223.Dv EX_WAITSPACE 224is not specified, the allocation will fail if the request can not be 225satisfied without sleeping. 226The caller must also specify, using the 227.Dv EX_NOWAIT 228or 229.Dv EX_WAITOK 230flags, if waiting for overhead allocation is allowed. 231.Pp 232The 233.Fn extent_alloc1 234and 235.Fn extent_alloc_subregion1 236functions are extensions that take one additional argument, 237.Fa skew , 238that modifies the requested alignment result in the following way: 239the value 240.Po Fa result 241\& - 242.Fa skew 243.Pc 244is aligned to 245.Fa alignment 246boundaries. 247.Fa skew 248must be a smaller number than 249.Fa alignment . 250Also, a boundary argument smaller than the sum of the requested skew 251and the size of the request is invalid. 252.Pp 253.Fn extent_free 254frees a region of 255.Fa size 256bytes in extent 257.Fa ex 258starting at 259.Fa start . 260If the extent has the 261.Dv EX_NOCOALESCE 262property, only entire regions may be freed. If the extent has the 263.Dv EX_NOCOALESCE 264property and the caller attempts to free a partial region, behavior is 265undefined. The caller must specify one of the flags 266.Dv EX_NOWAIT 267or 268.Dv EX_WAITOK 269to specify whether waiting for memory is okay; these flags have 270meaning in the event that allocation of a region descriptor is 271required during the freeing process. This situation occurs only when 272a partial region that begins and ends in the middle of another region 273is freed. Behavior is undefined if invalid arguments are provided. 274.Pp 275.Fn extent_print 276Print out information about extent 277.Fa ex . 278This function always succeeds. Behavior is undefined if invalid 279arguments are provided. 280.Sh LOCKING 281The extent manager performs all necessary locking on the extent map 282itself, and any other data structures internal to the extent manager. 283The locks used by the extent manager are simplelocks, and will never sleep 284.Po 285see 286.Xr lock 9 287.Pc . 288This should be taken into account when designing the locking protocol 289for users of the extent manager. 290.Sh RETURN VALUES 291The behavior of all extent manager functions is undefined if given 292invalid arguments. 293.Fn extent_create 294returns the extent map on success, or 295.Dv NULL 296if it fails to allocate storage for the extent map. It always 297succeeds when creating a fixed extent or when given the flag 298.Dv EX_WAITOK . 299.Fn extent_alloc , 300.Fn extent_alloc_region , 301.Fn extent_alloc_subregion , 302and 303.Fn extent_free 304return one of the following values: 305.Bl -tag -offset indent -width "XXXXXXXX" 306.It Dv 0 307Operation was successful. 308.It Dv ENOMEM 309If 310.Dv EX_NOWAIT 311is specified, the extent manager was not able to allocate a region 312descriptor for the new region or to split a region when freeing a 313partial region. 314.It Dv EAGAIN 315Requested region is not available and 316.Dv EX_WAITSPACE 317was not specified. 318.It Dv EINTR 319Process received a signal while waiting for the requested region to 320become available in the extent. Does not apply to 321.Fn extent_free . 322.El 323.Sh EXAMPLES 324Here is an example of a (useless) function that uses several of the 325extent manager routines. 326.Bd -literal 327void 328func() 329{ 330 struct extent *foo_ex; 331 u_long region_start; 332 int error; 333 334 /* 335 * Extent "foo" manages a 256k region starting at 0x0 and 336 * only allows complete regions to be freed so that 337 * extent_free() never needs to allocate memory. 338 */ 339 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 340 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 341 342 /* 343 * Allocate an 8k region, aligned to a 4k boundary, which 344 * does not cross any of the 3 64k boundaries (at 64k, 345 * 128k, and 192k) within the extent. 346 */ 347 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 348 EX_NOWAIT, \*[Am]region_start); 349 if (error) 350 panic("you lose"); 351 352 /* 353 * Give up the extent. 354 */ 355 extent_destroy(foo_ex); 356} 357.Ed 358.Sh CODE REFERENCES 359This section describes places within the 360.Nx 361source tree where 362actual code implementing or using the extent manager can be found. 363All pathnames are relative to 364.Pa /usr/src . 365.Pp 366The extent manager itself is implemented within the file 367.Pa sys/kern/subr_extent.c . 368Function prototypes for the framework are located in 369.Pa sys/sys/extent.h . 370.Pp 371The i386 bus management code uses the extent manager for managing I/O 372ports and I/O memory. This code is in the file 373.Pa sys/arch/i386/i386/machdep.c . 374.Sh SEE ALSO 375.Xr malloc 9 376.Sh HISTORY 377The 378.Nx 379extent manager appeared in 380.Nx 1.3 . 381.Sh AUTHORS 382The 383.Nx 384extent manager was architected and implemented by Jason 385R. Thorpe \*[Lt]thorpej@NetBSD.ORG\*[Gt]. Matthias Drochner 386\*[Lt]drochner@zelux6.zel.kfa-juelich.de\*[Gt] contributed to the initial 387testing and optimization of the implementation. Chris Demetriou 388\*[Lt]cgd@NetBSD.ORG\*[Gt] contributed many architectural suggestions. 389