1.\" $NetBSD: extent.9,v 1.37 2017/08/28 06:18:40 skrll 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 August 28, 2017 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 136If the flag 137.Dv EX_EARLY 138is specified, no 139.Xr mutex 9 140calls are made in the expectation that 141mutual exclusion is not available or required. 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, the region and internal extent 148descriptors themselves are freed. 149This function always succeeds. 150.Pp 151.Fn extent_alloc 152allocates a region in extent 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 must specify if waiting for space in the extent is allowed 170using the flag 171.Dv EX_WAITSPACE . 172If 173.Dv EX_WAITSPACE 174is not specified, the allocation will fail if the request can not be 175satisfied without sleeping. 176The caller must also specify, using the 177.Dv EX_NOWAIT 178or 179.Dv EX_WAITOK 180flags, if waiting for overhead allocation is allowed. 181The request will be aligned to 182.Fa alignment 183boundaries. 184Alignment values must be a power of 2. 185If no alignment is necessary, the value 1 should be specified. 186If 187.Fa boundary 188is nonzero, the allocated region will not cross any of the numbers 189which are a multiple of 190.Fa boundary . 191If the caller specifies the 192.Dv EX_BOUNDZERO 193flag, the boundary lines begin at zero. 194Otherwise, the boundary lines begin at the beginning of the extent. 195The allocated region may begin on a boundary address, but the end of 196the region will not touch nor cross it. 197A boundary argument smaller than the size of the request is invalid. 198Upon successful completion, 199.Fa *result 200will contain the start of the allocated region. 201.Pp 202.Fn extent_alloc_subregion 203is similar to 204.Fn extent_alloc , 205but it allows the caller to specify that the allocated region must 206fall within the subregion from 207.Fa substart 208to 209.Fa subend 210inclusive. 211The other arguments and the return values of 212.Fn extent_alloc_subregion 213are otherwise the same as those of 214.Fn extent_alloc . 215.Pp 216.Fn extent_alloc_region 217allocates the specific region in the extent map 218.Fa ex 219beginning at 220.Fa start 221with the size 222.Fa size . 223The caller must specify whether it is okay to wait for the indicated 224region to be free using the flag 225.Dv EX_WAITSPACE . 226If 227.Dv EX_WAITSPACE 228is not specified, the allocation will fail if the request can not be 229satisfied without sleeping. 230The caller must also specify, using the 231.Dv EX_NOWAIT 232or 233.Dv EX_WAITOK 234flags, if waiting for overhead allocation is allowed. 235.Pp 236The 237.Fn extent_alloc1 238and 239.Fn extent_alloc_subregion1 240functions are extensions that take one additional argument, 241.Fa skew , 242that modifies the requested alignment result in the following way: 243the value 244.Pq Fa result No - Fa skew 245is aligned to 246.Fa alignment 247boundaries. 248.Fa skew 249must be a smaller number than 250.Fa alignment . 251Also, a boundary argument smaller than the sum of the requested skew 252and the size of the request is invalid. 253.Pp 254.Fn extent_free 255frees a region of 256.Fa size 257bytes in extent 258.Fa ex 259starting at 260.Fa start . 261If the extent has the 262.Dv EX_NOCOALESCE 263property, only entire regions may be freed. 264If the extent has the 265.Dv EX_NOCOALESCE 266property and the caller attempts to free a partial region, behavior is 267undefined. 268The caller must specify one of the flags 269.Dv EX_NOWAIT 270or 271.Dv EX_WAITOK 272to specify whether waiting for memory is okay; these flags have 273meaning in the event that allocation of a region descriptor is 274required during the freeing process. 275This situation occurs only when a partial region that begins and ends 276in the middle of another region is freed. 277Behavior is undefined if invalid arguments are provided. 278.Pp 279.Fn extent_print 280Print out information about extent 281.Fa ex . 282This function always succeeds. 283Behavior is undefined if invalid arguments are provided. 284.Sh LOCKING 285The extent manager performs all necessary locking (unless 286.Dv EX_EARLY 287is specified) on the extent map 288itself, and any other data structures internal to the extent manager. 289The locks used by the extent manager are simplelocks, and will never sleep 290.Po 291see 292.Xr lock 9 293.Pc . 294This should be taken into account when designing the locking protocol 295for users of the extent manager. 296.Sh RETURN VALUES 297The behavior of all extent manager functions is undefined if given 298invalid arguments. 299.Fn extent_create 300returns the extent map on success, or 301.Dv NULL 302if it fails to allocate storage for the extent map. 303It always succeeds when creating a fixed extent or when given the flag 304.Dv EX_WAITOK . 305.Fn extent_alloc , 306.Fn extent_alloc_region , 307.Fn extent_alloc_subregion , 308and 309.Fn extent_free 310return one of the following values: 311.Bl -tag -offset indent -width "XXXXXXXX" 312.It Dv 0 313Operation was successful. 314.It Dv ENOMEM 315If 316.Dv EX_NOWAIT 317is specified, the extent manager was not able to allocate a region 318descriptor for the new region or to split a region when freeing a 319partial region. 320.It Dv EAGAIN 321Requested region is not available and 322.Dv EX_WAITSPACE 323was not specified. 324.It Dv EINTR 325Process received a signal while waiting for the requested region to 326become available in the extent. 327Does not apply to 328.Fn extent_free . 329.El 330.Sh EXAMPLES 331Here is an example of a (useless) function that uses several of the 332extent manager routines. 333.Bd -literal 334void 335func() 336{ 337 struct extent *foo_ex; 338 u_long region_start; 339 int error; 340 341 /* 342 * Extent "foo" manages a 256k region starting at 0x0 and 343 * only allows complete regions to be freed so that 344 * extent_free() never needs to allocate memory. 345 */ 346 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 347 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 348 349 /* 350 * Allocate an 8k region, aligned to a 4k boundary, which 351 * does not cross any of the 3 64k boundaries (at 64k, 352 * 128k, and 192k) within the extent. 353 */ 354 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 355 EX_NOWAIT, ®ion_start); 356 if (error) 357 panic("you lose"); 358 359 /* 360 * Give up the extent. 361 */ 362 extent_destroy(foo_ex); 363} 364.Ed 365.Sh CODE REFERENCES 366The extent manager itself is implemented within the file 367.Pa sys/kern/subr_extent.c . 368Function prototypes for the framework are located in 369.Pa sys/sys/extent.h . 370.Pp 371The i386 bus management code uses the extent manager for managing I/O 372ports and I/O memory. 373This code is in the file 374.Pa sys/arch/i386/i386/machdep.c . 375.Sh SEE ALSO 376.Xr malloc 9 377.Sh HISTORY 378The 379.Nx 380extent manager appeared in 381.Nx 1.3 . 382.Sh AUTHORS 383The 384.Nx 385extent manager was architected and implemented by 386.An Jason R. Thorpe 387.Aq thorpej@NetBSD.org . 388.An Matthias Drochner 389.Aq drochner@zelux6.zel.kfa-juelich.de 390contributed to the initial testing and optimization of the implementation. 391.An Chris Demetriou 392.Aq cgd@NetBSD.org 393contributed many architectural suggestions. 394