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