1.\" $NetBSD: extent.9,v 1.23 2002/10/14 13:43:22 wiz Exp $ 2.\" 3.\" Copyright (c) 1996, 1998 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Jason R. Thorpe and Greg Hudson. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 3. All advertising materials mentioning features or use of this software 18.\" must display the following acknowledgement: 19.\" This product includes software developed by the NetBSD 20.\" Foundation, Inc. and its contributors. 21.\" 4. Neither the name of The NetBSD Foundation nor the names of its 22.\" contributors may be used to endorse or promote products derived 23.\" from this software without specific prior written permission. 24.\" 25.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 26.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 27.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 29.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 30.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 31.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 32.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 33.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 34.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 35.\" POSSIBILITY OF SUCH DAMAGE. 36.\" 37.Dd September 23, 1996 38.Dt EXTENT 9 39.Os 40.Sh NAME 41.Nm extent , 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 \*[Lt]sys/malloc.h\*[Gt] 52.Fd #include \*[Lt]sys/extent.h\*[Gt] 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_alloc1 "struct extent *ex" "u_long size" "u_long alignment" "u_long skew" "u_long boundary" "int flags" "u_long *result" 63.Ft int 64.\" too many arguments for a single .Fn 65.Fo extent_alloc_subregion1 66.Fa "struct extent *ex" 67.Fa "u_long substart" 68.Fa "u_long subend" 69.Fa "u_long size" 70.Fa "u_long alignment" 71.Fa "u_long skew" 72.Fa "u_long boundary" 73.Fa "u_long flags" 74.Fa "u_long *result" 75.Fc 76.Ft int 77.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags" 78.Ft int 79.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags" 80.Ft void 81.Fn extent_print "struct extent *ex" 82.Sh DESCRIPTION 83The 84.Nx 85extent manager provides management of areas of memory or 86other number spaces (such as I/O ports). 87An opaque structure called an 88.Nm extent map 89keeps track of allocated regions within the number space. 90.Pp 91.Fn extent_create 92creates an extent map managing the space from 93.Fa start 94to 95.Fa end 96inclusive. 97All memory allocation will use the memory type 98.Fa mtype 99.Po 100see 101.Xr malloc 9 102.Pc . 103The extent map will have the name 104.Fa name , 105used for identification in case of an error. 106If the flag 107.Dv EX_NOCOALESCE 108is specified, only entire regions may be freed within the extent map, 109but internal coalescing of regions is disabled so that 110.Fn extent_free 111will never have to allocate a region descriptor and therefore will 112never fail. 113The caller must specify one of the flags 114.Dv EX_NOWAIT 115or 116.Dv EX_WAITOK , 117specifying whether it is okay to wait for memory allocated for 118extent map overhead. 119.Pp 120There are some applications which may want to use an extent map but 121can't use 122.Fn malloc 123and 124.Fn free . 125These applications may provide pre-allocated storage for 126all descriptor overhead with the arguments 127.Fa storage 128and 129.Fa storagesize . 130An extent of this type is called a 131.Nm fixed extent . 132If the application can safely use 133.Fn malloc 134and 135.Fn free , 136.Fa storage 137should be 138.Dv NULL . 139A fixed extent has a fixed number of region descriptors, so care 140should be taken to provide enough storage for them; alternatively, the 141flag 142.Dv EX_MALLOCOK 143may be passed to allocation requests to indicate that a fixed extent 144map may be extended using a call to 145.Fn malloc . 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, the region and internal extent 152descriptors themselves are freed. 153This function always succeeds. 154.Pp 155.Fn extent_alloc 156allocates a region in extent 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 must specify if waiting for space in the extent is allowed 174using the flag 175.Dv EX_WAITSPACE . 176If 177.Dv EX_WAITSPACE 178is not specified, the allocation will fail if the request can not be 179satisfied without sleeping. 180The caller must also specify, using the 181.Dv EX_NOWAIT 182or 183.Dv EX_WAITOK 184flags, if waiting for overhead allocation is allowed. 185The request will be aligned to 186.Fa alignment 187boundaries. 188Alignment values must be a power of 2. 189If no alignment is necessary, the value 1 should be specified. 190If 191.Fa boundary 192is nonzero, the allocated region will not cross any of the numbers 193which are a multiple of 194.Fa boundary . 195If the caller specifies the 196.Dv EX_BOUNDZERO 197flag, the boundary lines begin at zero. 198Otherwise, the boundary lines begin at the beginning of the extent. 199The allocated region may begin on a boundary address, but the end of 200the region will not touch nor cross it. 201A boundary argument smaller than the size of the request is invalid. 202Upon successful completion, 203.Fa *result 204will contain the start of the allocated region. 205.Pp 206.Fn extent_alloc_subregion 207is similar to 208.Fn extent_alloc , 209but it allows the caller to specify that the allocated region must 210fall within the subregion from 211.Fa substart 212to 213.Fa subend 214inclusive. 215The other arguments and the return values of 216.Fn extent_alloc_subregion 217are otherwise the same as those of 218.Fn extent_alloc . 219.Pp 220.Fn extent_alloc_region 221allocates the specific region in the extent map 222.Fa ex 223beginning at 224.Fa start 225with the size 226.Fa size . 227The caller must specify whether it is okay to wait for the indicated 228region to be free using the flag 229.Dv EX_WAITSPACE . 230If 231.Dv EX_WAITSPACE 232is not specified, the allocation will fail if the request can not be 233satisfied without sleeping. 234The caller must also specify, using the 235.Dv EX_NOWAIT 236or 237.Dv EX_WAITOK 238flags, if waiting for overhead allocation is allowed. 239.Pp 240The 241.Fn extent_alloc1 242and 243.Fn extent_alloc_subregion1 244functions are extensions that take one additional argument, 245.Fa skew , 246that modifies the requested alignment result in the following way: 247the value 248.Po Fa result 249\& - 250.Fa skew 251.Pc 252is aligned to 253.Fa alignment 254boundaries. 255.Fa skew 256must be a smaller number than 257.Fa alignment . 258Also, a boundary argument smaller than the sum of the requested skew 259and the size of the request is invalid. 260.Pp 261.Fn extent_free 262frees a region of 263.Fa size 264bytes in extent 265.Fa ex 266starting at 267.Fa start . 268If the extent has the 269.Dv EX_NOCOALESCE 270property, only entire regions may be freed. 271If the extent has the 272.Dv EX_NOCOALESCE 273property and the caller attempts to free a partial region, behavior is 274undefined. 275The caller must specify one of the flags 276.Dv EX_NOWAIT 277or 278.Dv EX_WAITOK 279to specify whether waiting for memory is okay; these flags have 280meaning in the event that allocation of a region descriptor is 281required during the freeing process. 282This situation occurs only when a partial region that begins and ends 283in the middle of another region is freed. 284Behavior is undefined if invalid arguments are provided. 285.Pp 286.Fn extent_print 287Print out information about extent 288.Fa ex . 289This function always succeeds. 290Behavior is undefined if invalid arguments are provided. 291.Sh LOCKING 292The extent manager performs all necessary locking on the extent map 293itself, and any other data structures internal to the extent manager. 294The locks used by the extent manager are simplelocks, and will never sleep 295.Po 296see 297.Xr lock 9 298.Pc . 299This should be taken into account when designing the locking protocol 300for users of the extent manager. 301.Sh RETURN VALUES 302The behavior of all extent manager functions is undefined if given 303invalid arguments. 304.Fn extent_create 305returns the extent map on success, or 306.Dv NULL 307if it fails to allocate storage for the extent map. 308It always succeeds when creating a fixed extent or when given the flag 309.Dv EX_WAITOK . 310.Fn extent_alloc , 311.Fn extent_alloc_region , 312.Fn extent_alloc_subregion , 313and 314.Fn extent_free 315return one of the following values: 316.Bl -tag -offset indent -width "XXXXXXXX" 317.It Dv 0 318Operation was successful. 319.It Dv ENOMEM 320If 321.Dv EX_NOWAIT 322is specified, the extent manager was not able to allocate a region 323descriptor for the new region or to split a region when freeing a 324partial region. 325.It Dv EAGAIN 326Requested region is not available and 327.Dv EX_WAITSPACE 328was not specified. 329.It Dv EINTR 330Process received a signal while waiting for the requested region to 331become available in the extent. 332Does not apply to 333.Fn extent_free . 334.El 335.Sh EXAMPLES 336Here is an example of a (useless) function that uses several of the 337extent manager routines. 338.Bd -literal 339void 340func() 341{ 342 struct extent *foo_ex; 343 u_long region_start; 344 int error; 345 346 /* 347 * Extent "foo" manages a 256k region starting at 0x0 and 348 * only allows complete regions to be freed so that 349 * extent_free() never needs to allocate memory. 350 */ 351 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 352 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 353 354 /* 355 * Allocate an 8k region, aligned to a 4k boundary, which 356 * does not cross any of the 3 64k boundaries (at 64k, 357 * 128k, and 192k) within the extent. 358 */ 359 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 360 EX_NOWAIT, \*[Am]region_start); 361 if (error) 362 panic("you lose"); 363 364 /* 365 * Give up the extent. 366 */ 367 extent_destroy(foo_ex); 368} 369.Ed 370.Sh CODE REFERENCES 371This section describes places within the 372.Nx 373source tree where 374actual code implementing or using the extent manager can be found. 375All pathnames are relative to 376.Pa /usr/src . 377.Pp 378The extent manager itself is implemented within the file 379.Pa sys/kern/subr_extent.c . 380Function prototypes for the framework are located in 381.Pa sys/sys/extent.h . 382.Pp 383The i386 bus management code uses the extent manager for managing I/O 384ports and I/O memory. 385This code is in the file 386.Pa sys/arch/i386/i386/machdep.c . 387.Sh SEE ALSO 388.Xr malloc 9 389.Sh HISTORY 390The 391.Nx 392extent manager appeared in 393.Nx 1.3 . 394.Sh AUTHORS 395The 396.Nx 397extent manager was architected and implemented by Jason 398R. Thorpe \*[Lt]thorpej@NetBSD.ORG\*[Gt]. 399Matthias Drochner \*[Lt]drochner@zelux6.zel.kfa-juelich.de\*[Gt] 400contributed to the initial testing and optimization of the implementation. 401Chris Demetriou \*[Lt]cgd@NetBSD.ORG\*[Gt] contributed many 402architectural suggestions. 403