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