1.\" $NetBSD: extent.9,v 1.34 2017/07/03 21:28:48 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.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd July 14, 2012 31.Dt EXTENT 9 32.Os 33.Sh NAME 34.Nm extent , 35.Nm extent_create , 36.Nm extent_destroy , 37.Nm extent_alloc , 38.Nm extent_alloc_subregion , 39.Nm extent_alloc1 , 40.Nm extent_alloc_subregion1 , 41.Nm extent_alloc_region , 42.Nm extent_free , 43.Nm extent_print 44.Nd general purpose extent manager 45.Sh SYNOPSIS 46.In sys/malloc.h 47.In sys/extent.h 48.Ft struct extent * 49.Fn extent_create "char *name" "u_long start" "u_long end" "void *storage" "size_t storagesize" "int flags" 50.Ft void 51.Fn extent_destroy "struct extent *ex" 52.Ft int 53.Fn extent_alloc "struct extent *ex" "u_long size" "u_long alignment" "u_long boundary" "int flags" "u_long *result" 54.Ft int 55.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" 56.Ft int 57.Fn extent_alloc1 "struct extent *ex" "u_long size" "u_long alignment" "u_long skew" "u_long boundary" "int flags" "u_long *result" 58.Ft int 59.\" too many arguments for a single .Fn 60.Fo extent_alloc_subregion1 61.Fa "struct extent *ex" 62.Fa "u_long substart" 63.Fa "u_long subend" 64.Fa "u_long size" 65.Fa "u_long alignment" 66.Fa "u_long skew" 67.Fa "u_long boundary" 68.Fa "u_long flags" 69.Fa "u_long *result" 70.Fc 71.Ft int 72.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags" 73.Ft int 74.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags" 75.Ft void 76.Fn extent_print "struct extent *ex" 77.Sh DESCRIPTION 78The 79.Nx 80extent manager provides management of areas of memory or 81other number spaces (such as I/O ports). 82An opaque structure called an 83.Nm extent map 84keeps track of allocated regions within the number space. 85.Pp 86.Fn extent_create 87creates an extent map managing the space from 88.Fa start 89to 90.Fa end 91inclusive. 92The extent map will have the name 93.Fa name , 94used for identification in case of an error. 95If the flag 96.Dv EX_NOCOALESCE 97is specified, only entire regions may be freed within the extent map, 98but internal coalescing of regions is disabled so that 99.Fn extent_free 100will never have to allocate a region descriptor and therefore will 101never fail. 102The caller must specify one of the flags 103.Dv EX_NOWAIT 104or 105.Dv EX_WAITOK , 106specifying whether it is okay to wait for memory allocated for 107extent map overhead. 108.Pp 109There are some applications which 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 allocation requests to indicate that a fixed extent 133map may be extended using a call to 134.Fn malloc . 135.Pp 136.Fn extent_destroy 137destroys the extent map 138.Fa ex , 139freeing all allocated regions. 140If the extent is not a fixed extent, the region and internal extent 141descriptors themselves are freed. 142This function always succeeds. 143.Pp 144.Fn extent_alloc 145allocates a region in extent 146.Fa ex 147of size 148.Fa size 149that fits the provided parameters. 150There are two distinct allocation policies, which are selected by the 151.Fa flags 152argument: 153.Bl -tag -offset indent -width "XXXXXXXXX" 154.It Dv EX_FAST 155Allocate the first region that fits the provided parameters, regardless 156of resulting extent fragmentation. 157.It default 158Allocate the smallest region that is capable of holding the request, 159thus minimizing fragmentation of the extent. 160.El 161.Pp 162The caller must specify if waiting for space in the extent is allowed 163using the flag 164.Dv EX_WAITSPACE . 165If 166.Dv EX_WAITSPACE 167is not specified, the allocation will fail if the request can not be 168satisfied without sleeping. 169The caller must also specify, using the 170.Dv EX_NOWAIT 171or 172.Dv EX_WAITOK 173flags, if waiting for overhead allocation is allowed. 174The request will be aligned to 175.Fa alignment 176boundaries. 177Alignment values must be a power of 2. 178If no alignment is necessary, the value 1 should be specified. 179If 180.Fa boundary 181is nonzero, the allocated region will not cross any of the numbers 182which are a multiple of 183.Fa boundary . 184If the caller specifies the 185.Dv EX_BOUNDZERO 186flag, the boundary lines begin at zero. 187Otherwise, the boundary lines begin at the beginning of the extent. 188The allocated region may begin on a boundary address, but the end of 189the region will not touch nor cross it. 190A boundary argument smaller than the size of the request is invalid. 191Upon successful completion, 192.Fa *result 193will contain the start of the allocated region. 194.Pp 195.Fn extent_alloc_subregion 196is similar to 197.Fn extent_alloc , 198but it allows the caller to specify that the allocated region must 199fall within the subregion from 200.Fa substart 201to 202.Fa subend 203inclusive. 204The other arguments and the return values of 205.Fn extent_alloc_subregion 206are otherwise the same as those of 207.Fn extent_alloc . 208.Pp 209.Fn extent_alloc_region 210allocates the specific region in the extent map 211.Fa ex 212beginning at 213.Fa start 214with the size 215.Fa size . 216The caller must specify whether it is okay to wait for the indicated 217region to be free using the flag 218.Dv EX_WAITSPACE . 219If 220.Dv EX_WAITSPACE 221is not specified, the allocation will fail if the request can not be 222satisfied without sleeping. 223The caller must also specify, using the 224.Dv EX_NOWAIT 225or 226.Dv EX_WAITOK 227flags, if waiting for overhead allocation is allowed. 228.Pp 229The 230.Fn extent_alloc1 231and 232.Fn extent_alloc_subregion1 233functions are extensions that take one additional argument, 234.Fa skew , 235that modifies the requested alignment result in the following way: 236the value 237.Pq Fa result No - Fa skew 238is aligned to 239.Fa alignment 240boundaries. 241.Fa skew 242must be a smaller number than 243.Fa alignment . 244Also, a boundary argument smaller than the sum of the requested skew 245and the size of the request is invalid. 246.Pp 247.Fn extent_free 248frees a region of 249.Fa size 250bytes in extent 251.Fa ex 252starting at 253.Fa start . 254If the extent has the 255.Dv EX_NOCOALESCE 256property, only entire regions may be freed. 257If the extent has the 258.Dv EX_NOCOALESCE 259property and the caller attempts to free a partial region, behavior is 260undefined. 261The caller must specify one of the flags 262.Dv EX_NOWAIT 263or 264.Dv EX_WAITOK 265to specify whether waiting for memory is okay; these flags have 266meaning in the event that allocation of a region descriptor is 267required during the freeing process. 268This situation occurs only when a partial region that begins and ends 269in the middle of another region is freed. 270Behavior is undefined if invalid arguments are provided. 271.Pp 272.Fn extent_print 273Print out information about extent 274.Fa ex . 275This function always succeeds. 276Behavior is undefined if invalid arguments are provided. 277.Sh LOCKING 278The extent manager performs all necessary locking on the extent map 279itself, and any other data structures internal to the extent manager. 280The locks used by the extent manager are simplelocks, and will never sleep 281.Po 282see 283.Xr lock 9 284.Pc . 285This should be taken into account when designing the locking protocol 286for users of the extent manager. 287.Sh RETURN VALUES 288The behavior of all extent manager functions is undefined if given 289invalid arguments. 290.Fn extent_create 291returns the extent map on success, or 292.Dv NULL 293if it fails to allocate storage for the extent map. 294It always succeeds when creating a fixed extent or when given the flag 295.Dv EX_WAITOK . 296.Fn extent_alloc , 297.Fn extent_alloc_region , 298.Fn extent_alloc_subregion , 299and 300.Fn extent_free 301return one of the following values: 302.Bl -tag -offset indent -width "XXXXXXXX" 303.It Dv 0 304Operation was successful. 305.It Dv ENOMEM 306If 307.Dv EX_NOWAIT 308is specified, the extent manager was not able to allocate a region 309descriptor for the new region or to split a region when freeing a 310partial region. 311.It Dv EAGAIN 312Requested region is not available and 313.Dv EX_WAITSPACE 314was not specified. 315.It Dv EINTR 316Process received a signal while waiting for the requested region to 317become available in the extent. 318Does not apply to 319.Fn extent_free . 320.El 321.Sh EXAMPLES 322Here is an example of a (useless) function that uses several of the 323extent manager routines. 324.Bd -literal 325void 326func() 327{ 328 struct extent *foo_ex; 329 u_long region_start; 330 int error; 331 332 /* 333 * Extent "foo" manages a 256k region starting at 0x0 and 334 * only allows complete regions to be freed so that 335 * extent_free() never needs to allocate memory. 336 */ 337 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 338 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 339 340 /* 341 * Allocate an 8k region, aligned to a 4k boundary, which 342 * does not cross any of the 3 64k boundaries (at 64k, 343 * 128k, and 192k) within the extent. 344 */ 345 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 346 EX_NOWAIT, ®ion_start); 347 if (error) 348 panic("you lose"); 349 350 /* 351 * Give up the extent. 352 */ 353 extent_destroy(foo_ex); 354} 355.Ed 356.Sh CODE REFERENCES 357The extent manager itself is implemented within the file 358.Pa sys/kern/subr_extent.c . 359Function prototypes for the framework are located in 360.Pa sys/sys/extent.h . 361.Pp 362The i386 bus management code uses the extent manager for managing I/O 363ports and I/O memory. 364This code is in the file 365.Pa sys/arch/i386/i386/machdep.c . 366.Sh SEE ALSO 367.Xr malloc 9 368.Sh HISTORY 369The 370.Nx 371extent manager appeared in 372.Nx 1.3 . 373.Sh AUTHORS 374The 375.Nx 376extent manager was architected and implemented by 377.An Jason R. Thorpe 378.Aq thorpej@NetBSD.org . 379.An Matthias Drochner 380.Aq drochner@zelux6.zel.kfa-juelich.de 381contributed to the initial testing and optimization of the implementation. 382.An Chris Demetriou 383.Aq cgd@NetBSD.org 384contributed many architectural suggestions. 385