1.\" $OpenBSD: extent.9,v 1.14 2009/04/19 15:26:52 kettenis 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: April 19 2009 $ 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. 101If the flag 102.Dv EX_FILLED 103is set, the entire space managed by the extent map will be allocated 104upon creation of the extent map, such that selected regions may be 105made available through calls to 106.Fn extent_free . 107.Pp 108Some applications may want to use an extent map but 109can't use 110.Fn malloc 111and 112.Fn free . 113These applications may provide pre-allocated storage for 114all descriptor overhead with the arguments 115.Fa storage 116and 117.Fa storagesize . 118An extent of this type is called a 119.Nm fixed extent . 120If the application can safely use 121.Fn malloc 122and 123.Fn free , 124.Fa storage 125should be 126.Dv NULL . 127A fixed extent has a fixed number of region descriptors, so care 128should be taken to provide enough storage for them; alternatively, the 129flag 130.Dv EX_MALLOCOK 131may be passed to extent requests to indicate that a fixed extent 132map may be extended using a call to 133.Fn malloc . 134Note that passing the flag 135.Dv EX_FILLED 136to 137.Fn extent_create 138will consume a region descriptor upon creation of the extent map. 139.Pp 140The caller should pass the flag 141.Dv EX_WAITOK 142or 143.Dv EX_NOWAIT 144to extent functions that have a memory overhead, to specify whether 145it is okay to wait. 146These functions are 147.Fn extent_create 148(non fixed extents), 149.Fn extent_free 150(unless 151.Dv EX_NOCOALESCE 152is set), 153.Fn extent_alloc , 154.Fn extent_alloc_subregion 155and 156.Fn extent_alloc_region . 157.Pp 158.Fn extent_destroy 159destroys the extent map 160.Fa ex , 161freeing all allocated regions. 162If the extent is not a fixed extent, 163the region and internal extent descriptors themselves are freed. 164This function always succeeds. 165.Pp 166.Fn extent_alloc 167allocates a region in the extent map 168.Fa ex 169of size 170.Fa size 171that fits the provided parameters. 172There are two distinct allocation policies, which are selected by the 173.Fa flags 174argument: 175.Bl -tag -offset indent -width "XXXXXXXXX" 176.It Dv EX_FAST 177Allocate the first region that fits the provided parameters, regardless 178of resulting extent fragmentation. 179.It default 180Allocate the smallest region that is capable of holding the request, 181thus minimizing fragmentation of the extent. 182.El 183.Pp 184The caller may specify that it is okay to wait for space to become free in the 185extent by setting the flag 186.Dv EX_WAITSPACE . 187If 188.Dv EX_WAITSPACE 189is not set, the allocation will fail if the request can not be 190satisfied without sleeping. 191.Pp 192The request will be aligned to a multiple of 193.Fa alignment . 194That value must be a power of 2. 195If no alignment is necessary, the value 196.Dv EX_NOALIGN 197should be specified. 198If 199.Fa skew 200is non-zero, it modifies the requested alignment result in the following way: 201the value 202.Pq Fa result No - Fa skew 203is aligned to 204.Fa alignment 205boundaries. 206.Fa skew 207must be a smaller number than 208.Fa alignment . 209If 210.Fa boundary 211is not 212.Dv EX_NOBOUNDARY , 213the allocated region will not cross any boundary lines, spaced 214.Fa boundary 215apart. 216If the caller specifies the 217.Dv EX_BOUNDZERO 218flag, boundary lines begin at zero. 219Otherwise, boundary lines begin at the beginning of the extent. 220The allocated region may begin on a 221boundary line, but the end of the region will not touch nor cross a 222boundary line. 223A 224.Fa boundary 225argument smaller than the sum of the requested skew and the size of 226the request is invalid. 227Upon successful completion, 228.Fa *result 229will contain the start of the allocated region. 230.Pp 231.Fn extent_alloc_subregion 232is a generalized version of 233.Fn extent_alloc 234that also allows the caller to specify that the allocated region must 235fall within the subregion from 236.Fa substart 237to 238.Fa subend 239inclusive. 240.Pp 241.Fn extent_alloc_region 242allocates the specific region in the extent map 243.Fa ex 244beginning at 245.Fa start 246with the size 247.Fa size . 248If the caller specifies the 249.Dv EX_CONFLICTOK 250flag, the allocation will succeed even if part of the requested region 251has already been allocated. 252The caller may specify that it is okay to wait for the indicated 253region to be free by setting the flag 254.Dv EX_WAITSPACE . 255If neither 256.Dv EX_WAITSPACE 257nor 258.Dv EX_CONFLICTOK 259is set, the allocation will fail if the request can not be 260satisfied without sleeping. 261.Pp 262.Fn extent_free 263frees a region of 264.Fa size 265bytes starting at 266.Fa start 267in the extent map 268.Fa ex . 269If the extent has the 270.Dv EX_NOCOALESCE 271property, only entire regions may be freed. 272If the extent has the 273.Dv EX_NOCOALESCE 274property and the caller attempts to free a partial region, behavior is 275undefined. 276If called on an extent without the 277.Dv EX_NOCOALESCE 278property, this function can fail with error codes listed below, otherwise 279this function will always succeed. 280.Pp 281.Fn extent_print 282Prints out information about extent 283.Fa ex . 284This function always succeeds. 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. 316.El 317.Sh EXAMPLES 318Here is an example of a (useless) function that uses several of the 319extent manager routines. 320.Bd -literal 321void 322func() 323{ 324 struct extent *foo_ex; 325 u_long region_start; 326 int error; 327 328 /* 329 * Extent "foo" manages a 256k region starting at 0x0 and 330 * only allows complete regions to be freed so that 331 * extent_free() never needs to allocate memory. 332 */ 333 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 334 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 335 336 /* 337 * Allocate an 8k region, aligned to a 4k boundary, which 338 * does not cross any of the 3 64k boundaries (at 64k, 339 * 128k, and 192k) within the extent. 340 */ 341 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 342 EX_NOWAIT, ®ion_start); 343 if (error) 344 panic("you lose"); 345 346 /* 347 * Give up the extent. 348 */ 349 extent_destroy(foo_ex); 350} 351.Ed 352.\" 353.\" Yeah, right... document EX_CATCH first... 354.\" 355.\" .Sh LIMITATIONS 356.\" The flag 357.\" .Dv EX_CATCH 358.\" cannot be used to catch signals in all circumstances since 359.\" .Xr malloc 9 360.\" does not provide such a functionality. 361.Sh CODE REFERENCES 362The extent manager itself is implemented within the file 363.Pa sys/kern/subr_extent.c . 364.Pp 365The i386 bus management code uses the extent manager for managing I/O 366ports and I/O memory. 367See 368.Pa sys/arch/i386/i386/machdep.c . 369.Sh SEE ALSO 370.Xr ddb 4 , 371.Xr malloc 9 372.Sh HISTORY 373The extent manager appeared in 374.Nx 1.3 . 375.Sh AUTHORS 376.An -nosplit 377The extent manager was designed and implemented by 378.An Jason R. Thorpe Aq thorpej@NetBSD.ORG . 379.An Matthias Drochner Aq drochner@zelux6.zel.kfa-juelich.de 380contributed to the initial testing and optimization of the implementation. 381.An Chris Demetriou Aq cgd@NetBSD.ORG 382contributed many architectural suggestions. 383