1.\" $OpenBSD: extent.9,v 1.5 2000/11/10 20:02:20 todd 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 boundary" "int flags" "u_long *result" 59.Ft int 60.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" 61.Ft int 62.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags" 63.Ft int 64.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags" 65.Ft void 66.Fn extent_print "struct extent *ex" 67.Sh DESCRIPTION 68The extent manager provides management of areas of memory or 69other enumerable spaces (such as I/O ports). 70An opaque structure called an 71.Nm extent map 72keeps track of allocated regions within the enumerable space. 73.Pp 74.Fn extent_create 75creates an extent map managing the space from 76.Fa start 77to 78.Fa end 79inclusive. 80All memory allocation will use the memory type 81.Fa mtype 82.Po 83see 84.Xr malloc 9 85.Pc . 86The extent map will have the name 87.Fa name , 88used for identification in case of errors or in 89.Xr ddb 4 90.Ic show extents . 91If the flag 92.Dv EX_NOCOALESCE 93is set, internal coalescing of regions is disabled, 94and only entire regions may be freed within the extent map, so that 95.Fn extent_free 96will never have to allocate a region descriptor. 97.Pp 98Some applications may want to use an extent map but 99can't use 100.Fn malloc 101and 102.Fn free . 103These applications may provide pre-allocated storage for 104all descriptor overhead with the arguments 105.Fa storage 106and 107.Fa storagesize . 108An extent of this type is called a 109.Nm fixed extent . 110If the application can safely use 111.Fn malloc 112and 113.Fn free , 114.Fa storage 115should be 116.Dv NULL . 117A fixed extent has a fixed number of region descriptors, so care 118should be taken to provide enough storage for them; alternatively, the 119flag 120.Dv EX_MALLOCOK 121may be passed to extent requests to indicate that a fixed extent 122map may be extended using a call to 123.Fn malloc . 124.Pp 125The caller should pass the flag 126.Dv EX_WAITOK 127or 128.Dv EX_NOWAIT 129to extent functions that have a memory overhead, to specify whether 130it is okay to wait. 131These functions are 132.Fn extent_create 133(non fixed extents), 134.Fn extent_free 135(unless 136.Dv EX_NOCOALESCE 137is set), 138.Fn extent_alloc , 139.Fn extent_alloc_subregion 140and 141.Fn extent_alloc_region . 142.Pp 143.Fn extent_destroy 144destroys the extent map 145.Fa ex , 146freeing all allocated regions. 147If the extent is not a fixed extent, 148the region and internal extent descriptors themselves are freed. 149This function always succeeds. 150.Pp 151.Fn extent_alloc 152allocates a region in the extent map 153.Fa ex 154of size 155.Fa size 156that fits the provided parameters. 157There are two distinct allocation policies, which are selected by the 158.Fa flags 159argument: 160.Bl -tag -offset indent -width "XXXXXXXXX" 161.It Dv EX_FAST 162Allocate the first region that fits the provided parameters, regardless 163of resulting extent fragmentation. 164.It default 165Allocate the smallest region that is capable of holding the request, 166thus minimizing fragmentation of the extent. 167.El 168.Pp 169The caller may specify that it is okay to wait for space to become free in the 170extent by setting the flag 171.Dv EX_WAITSPACE . 172If 173.Dv EX_WAITSPACE 174is not set, the allocation will fail if the request can not be 175satisfied without sleeping. 176.Pp 177The request will be aligned to a multiple of 178.Fa alignment . 179That value must be a power of 2. 180If no alignment is necessary, the value 181.Dv EX_NOALIGN 182should be specified. 183If 184.Fa boundary 185is not 186.Dv EX_NOBOUNDARY , 187the allocated region will not cross any boundary lines, spaced 188.Fa boundary 189apart. 190If the caller specifies the 191.Dv EX_BOUNDZERO 192flag, boundary lines begin at zero. 193Otherwise, boundary lines begin at the beginning of the extent. 194The allocated region may begin on a 195boundary line, but the end of the region will not touch nor cross a 196boundary line. 197A 198.Fa boundary 199argument smaller than the size of the request is invalid. 200Upon successful completion, 201.Fa *result 202will contain the start of the allocated region. 203.Pp 204.Fn extent_alloc_subregion 205is a generalized version of 206.Fn extent_alloc 207that also allows the caller to specify that the allocated region must 208fall within the subregion from 209.Fa substart 210to 211.Fa subend 212inclusive. 213.Pp 214.Fn extent_alloc_region 215allocates the specific region in the extent map 216.Fa ex 217beginning at 218.Fa start 219with the size 220.Fa size . 221The caller may specify that it is okay to wait for the indicated 222region to be free by setting the flag 223.Dv EX_WAITSPACE . 224If 225.Dv EX_WAITSPACE 226is not set, the allocation will fail if the request can not be 227satisfied without sleeping. 228.Pp 229.Fn extent_free 230frees a region of 231.Fa size 232bytes starting at 233.Fa start 234in the extent map 235.Fa ex . 236If the extent has the 237.Dv EX_NOCOALESCE 238property, only entire regions may be freed. 239If the extent has the 240.Dv EX_NOCOALESCE 241property and the caller attempts to free a partial region, behavior is 242undefined. 243.Pp 244.Fn extent_print 245Prints out information about extent 246.Fa ex . 247This function always succeeds. 248.Sh RETURN VALUES 249The behavior of all extent manager functions is undefined if given 250invalid arguments. 251.Fn extent_create 252returns the extent map on success, or 253.Dv NULL 254if it fails to allocate storage for the extent map. 255It always succeeds when creating a fixed extent or when given the flag 256.Dv EX_WAITOK . 257.Fn extent_alloc , 258.Fn extent_alloc_region , 259.Fn extent_alloc_subregion , 260and 261.Fn extent_free 262return one of the following values: 263.Bl -tag -offset indent -width "XXXXXXXX" 264.It Dv 0 265Operation was successful. 266.It Dv ENOMEM 267If 268.Dv EX_NOWAIT 269is specified, the extent manager was not able to allocate a region 270descriptor for the new region or to split a region when freeing a 271partial region. 272.It Dv EAGAIN 273Requested region is not available and 274.Dv EX_WAITSPACE 275was not specified. 276.It Dv EINTR 277Process received a signal while waiting for the requested region to 278become available in the extent. 279.El 280.Sh EXAMPLES 281Here is an example of a (useless) function that uses several of the 282extent manager routines. 283.Bd -literal 284void 285func() 286{ 287 struct extent *foo_ex; 288 u_long region_start; 289 int error; 290 291 /* 292 * Extent "foo" manages a 256k region starting at 0x0 and 293 * only allows complete regions to be freed so that 294 * extent_free() never needs to allocate memory. 295 */ 296 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 297 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 298 299 /* 300 * Allocate an 8k region, aligned to a 4k boundary, which 301 * does not cross any of the 3 64k boundaries (at 64k, 302 * 128k, and 192k) within the extent. 303 */ 304 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 305 EX_NOWAIT, ®ion_start); 306 if (error) 307 panic("you lose"); 308 309 /* 310 * Give up the extent. 311 */ 312 extent_destroy(foo_ex); 313} 314.Ed 315.\" 316.\" Yeah, right... document EX_CATCH first... 317.\" 318.\" .Sh LIMITATIONS 319.\" The flag 320.\" .Dv EX_CATCH 321.\" cannot be used to catch signals in all circumstances since 322.\" .Xr malloc 9 323.\" does not provide such a functionality. 324.Sh CODE REFERENCES 325The extent manager itself is implemented within the file 326.Pa sys/kern/subr_extent.c . 327.Pp 328The i386 bus management code uses the extent manager for managing I/O 329ports and I/O memory. 330See 331.Pa sys/arch/i386/i386/machdep.c . 332.Sh AUTHORS 333The extent manager was designed and implemented by Jason 334R. Thorpe <thorpej@NetBSD.ORG>. 335Matthias Drochner <drochner@zelux6.zel.kfa-juelich.de> contributed to the 336initial testing and optimization of the implementation. 337Chris Demetriou <cgd@NetBSD.ORG> contributed many architectural suggestions. 338.Sh SEE ALSO 339.Xr ddb 4 , 340.Xr malloc 9 341.Sh HISTORY 342The extent manager appeared in 343.Nx 1.3 . 344