1.\" $OpenBSD: extent.9,v 1.9 2003/07/02 08:36:04 jmc 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.Pq Fa result No - Fa skew 199is aligned to 200.Fa alignment 201boundaries. 202.Fa skew 203must be a smaller number than 204.Fa alignment . 205If 206.Fa boundary 207is not 208.Dv EX_NOBOUNDARY , 209the allocated region will not cross any boundary lines, spaced 210.Fa boundary 211apart. 212If the caller specifies the 213.Dv EX_BOUNDZERO 214flag, boundary lines begin at zero. 215Otherwise, boundary lines begin at the beginning of the extent. 216The allocated region may begin on a 217boundary line, but the end of the region will not touch nor cross a 218boundary line. 219A 220.Fa boundary 221argument smaller than the sum of the requested skew and the size of 222the request is invalid. 223Upon successful completion, 224.Fa *result 225will contain the start of the allocated region. 226.Pp 227.Fn extent_alloc_subregion 228is a generalized version of 229.Fn extent_alloc 230that also allows the caller to specify that the allocated region must 231fall within the subregion from 232.Fa substart 233to 234.Fa subend 235inclusive. 236.Pp 237.Fn extent_alloc_region 238allocates the specific region in the extent map 239.Fa ex 240beginning at 241.Fa start 242with the size 243.Fa size . 244The caller may specify that it is okay to wait for the indicated 245region to be free by setting the flag 246.Dv EX_WAITSPACE . 247If 248.Dv EX_WAITSPACE 249is not set, the allocation will fail if the request can not be 250satisfied without sleeping. 251.Pp 252.Fn extent_free 253frees a region of 254.Fa size 255bytes starting at 256.Fa start 257in the extent map 258.Fa ex . 259If the extent has the 260.Dv EX_NOCOALESCE 261property, only entire regions may be freed. 262If the extent has the 263.Dv EX_NOCOALESCE 264property and the caller attempts to free a partial region, behavior is 265undefined. 266If called on an extent without the 267.Dv EX_NOCOALESCE 268property, this function can fail with error codes listed below, otherwise 269this function will always succeed. 270.Pp 271.Fn extent_print 272Prints out information about extent 273.Fa ex . 274This function always succeeds. 275.Sh RETURN VALUES 276The behavior of all extent manager functions is undefined if given 277invalid arguments. 278.Fn extent_create 279returns the extent map on success, or 280.Dv NULL 281if it fails to allocate storage for the extent map. 282It always succeeds when creating a fixed extent or when given the flag 283.Dv EX_WAITOK . 284.Fn extent_alloc , 285.Fn extent_alloc_region , 286.Fn extent_alloc_subregion , 287and 288.Fn extent_free 289return one of the following values: 290.Bl -tag -offset indent -width "XXXXXXXX" 291.It Dv 0 292Operation was successful. 293.It Dv ENOMEM 294If 295.Dv EX_NOWAIT 296is specified, the extent manager was not able to allocate a region 297descriptor for the new region or to split a region when freeing a 298partial region. 299.It Dv EAGAIN 300Requested region is not available and 301.Dv EX_WAITSPACE 302was not specified. 303.It Dv EINTR 304Process received a signal while waiting for the requested region to 305become available in the extent. 306.El 307.Sh EXAMPLES 308Here is an example of a (useless) function that uses several of the 309extent manager routines. 310.Bd -literal 311void 312func() 313{ 314 struct extent *foo_ex; 315 u_long region_start; 316 int error; 317 318 /* 319 * Extent "foo" manages a 256k region starting at 0x0 and 320 * only allows complete regions to be freed so that 321 * extent_free() never needs to allocate memory. 322 */ 323 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 324 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 325 326 /* 327 * Allocate an 8k region, aligned to a 4k boundary, which 328 * does not cross any of the 3 64k boundaries (at 64k, 329 * 128k, and 192k) within the extent. 330 */ 331 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 332 EX_NOWAIT, ®ion_start); 333 if (error) 334 panic("you lose"); 335 336 /* 337 * Give up the extent. 338 */ 339 extent_destroy(foo_ex); 340} 341.Ed 342.\" 343.\" Yeah, right... document EX_CATCH first... 344.\" 345.\" .Sh LIMITATIONS 346.\" The flag 347.\" .Dv EX_CATCH 348.\" cannot be used to catch signals in all circumstances since 349.\" .Xr malloc 9 350.\" does not provide such a functionality. 351.Sh CODE REFERENCES 352The extent manager itself is implemented within the file 353.Pa sys/kern/subr_extent.c . 354.Pp 355The i386 bus management code uses the extent manager for managing I/O 356ports and I/O memory. 357See 358.Pa sys/arch/i386/i386/machdep.c . 359.Sh SEE ALSO 360.Xr ddb 4 , 361.Xr malloc 9 362.Sh HISTORY 363The extent manager appeared in 364.Nx 1.3 . 365.Sh AUTHORS 366The extent manager was designed and implemented by 367.An Jason R. Thorpe Aq thorpej@NetBSD.ORG . 368.An Matthias Drochner Aq drochner@zelux6.zel.kfa-juelich.de 369contributed to the initial testing and optimization of the implementation. 370.An Chris Demetriou Aq cgd@NetBSD.ORG 371contributed many architectural suggestions. 372