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