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