1.\" $NetBSD: extent.9,v 1.2 1996/10/17 08:33:42 thorpej Exp $ 2.\" 3.\" Copyright (c) 1996 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 REGENTS OR CONTRIBUTORS BE 29.\" 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 Sep 23, 1996 38.Dt EXTENT 9 39.Os NetBSD 40.Sh NAME 41.Nm extent 42.Nd general purpose extent manager 43.Sh SYNOPSIS 44.Fd #include <sys/malloc.h> 45.Fd #include <sys/extent.h> 46.Ft struct extent * 47.Fn extent_create "char *name" "u_long start" "u_long end" "int mtype" "caddr_t storage" "size_t storagesize" "int flags" 48.Ft void 49.Fn extent_destroy "struct extent *ex" 50.Ft int 51.Fn extent_alloc "struct extent *ex" "u_long size" "u_long alignment" "u_long boundary" "int flags" "u_long *result" 52.Ft int 53.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" 54.Ft int 55.Fn extent_alloc_region "struct extent *ex" "u_long start" "u_long size" "int flags" 56.Ft int 57.Fn extent_free "struct extent *ex" "u_long start" "u_long size" "int flags" 58.Ft void 59.Fn extent_print "struct extent *ex" 60.Sh DESCRIPTION 61The NetBSD extent manager provides management of areas of memory or 62other number spaces (such as I/O ports). An opaque structure 63called an 64.Nm extent map 65keeps track of allocated regions within the number space. 66.Pp 67.Fn extent_create 68creates an extent map managing the space from 69.Fa start 70to 71.Fa end 72inclusive. All memory allocation will use the memory type 73.Fa mtype 74(see 75.Xr malloc 9 ). 76The extent map will have the name 77.Fa name , 78used for identification in case of an error. If the flag 79.Dv EX_NOCOALESCE 80is specified, only entire regions may be freed within the extent map, 81but internal coalescing of regions is disabled so that 82.Fn extent_free 83will never have to allocate a region descriptor and therefore will 84never fail. The caller must specify one of the flags 85.Dv EX_NOWAIT 86or 87.Dv EX_WAITOK , 88specifying whether it is okay to wait for memory allocated for 89extent map overhead. 90.Pp 91There are some applications which may want to use an extent map but 92can't use 93.Fn malloc 94and 95.Fn free . 96These applications may provide pre-allocated storage for 97all descriptor overhead with the arguments 98.Fa storage 99and 100.Fa storagesize . 101An extent of this type is called a 102.Nm fixed extent . 103If the application can safely use 104.Fn malloc 105and 106.Fn free , 107.Fa storage 108should be 109.Dv NULL . 110A fixed extent has a fixed number of region descriptors, so care 111should be taken to provide enough storage for them; alternatively, the 112flag 113.Dv EX_MALLOCOK 114may be passed to allocation requests to indicate that a fixed extent 115map may be extended using a call to 116.Fn malloc . 117.Pp 118.Fn extent_destroy 119destroys the extent map 120.Fa ex , 121freeing all allocated regions. If the extent is not a fixed extent, 122the region and internal extent descriptors themselves are freed. 123This function always succeeds. 124.Pp 125.Fn extent_alloc 126allocates a region in extent 127.Fa ex 128of size 129.Fa size 130that fits the provided parameters. There are two distinct allocation 131policies, which are selected by the 132.Fa flags 133argument: 134.Bl -tag -offset indent -width "XXXXXXXXX" 135.It Dv EX_FAST 136Allocate the first region that fits the provided paramters, regardless 137of resulting extent fragmentation. 138.It default 139Allocate the smallest region that is capable of holding the request, 140thus minimizing fragmentation of the extent. 141.El 142.Pp 143The caller must specify if waiting for space in the extent is allowed 144using the flag 145.Dv EX_WAITSPACE . 146If 147.Dv EX_WAITSPACE 148is not specified, the allocation will fail if the request can not be 149satisfied without sleeping. 150The caller must also specify, using the 151.Dv EX_NOWAIT 152or 153.Dv EX_WAITOK 154flags, if waiting for overhead allocation is allowed. 155The request will be aligned to 156.Fa alignment 157boundaries. Alignment values must be a power of 2. If no alignment 158is necessary, the value 1 should be specified. If 159.Fa boundary 160is nonzero, the allocated region will not cross any of the numbers 161which are a multiple of 162.Fa boundary . 163If the caller specifies the 164.Dv EX_BOUNDZERO 165flag, the boundary lines begin at zero. Otherwise, the boundary lines 166begin at the beginning of the extent. The allocated region may begin on a 167boundary address, but the end of the region will not touch nor cross 168it. A boundary argument smaller than the size of the request is 169invalid. Upon successful completion, 170.Fa *result 171will contain the start of the allocated region. 172.Pp 173.Fn extent_alloc_subregion 174is similar to 175.Fn extent_alloc , 176but it allows the caller to specify that the allocated region must 177fall within the subregion from 178.Fa substart 179to 180.Fa subend 181inclusive. The other arguments and the return values of 182.Fn extent_alloc_subregion 183are otherwise the same as those of 184.Fn extent_alloc . 185.Pp 186.Fn extent_alloc_region 187allocates the specific region in the extent map 188.Fa ex 189beginning at 190.Fa start 191with the size 192.Fa size . 193The caller must specify whether it is okay to wait for the indicated 194region to be free using the flag 195.Dv EX_WAITSPACE . 196If 197.Dv EX_WAITSPACE 198is not specified, the allocation will fail if the request can not be 199satisfied without sleeping. 200The caller must also specify, using the 201.Dv EX_NOWAIT 202or 203.Dv EX_WAITOK 204flags, if waiting for overhead allocation is allowed. 205.Pp 206.Fn extent_free 207frees a region of 208.Fa size 209bytes in extent 210.Fa ex 211starting at 212.Fa start . 213If the extent has the 214.Dv EX_NOCOALESCE 215property, only entire regions may be freed. If the extent has the 216.Dv EX_NOCOALESCE 217property and the caller attempts to free a partial region, behavior is 218undefined. The caller must specify one of the flags 219.Dv EX_NOWAIT 220or 221.Dv EX_WAITOK 222to specify whether waiting for memory is okay; these flags have 223meaning in the event that allocation of a region descriptor is 224required during the freeing process. This situation occurs only when 225a partial region that begins and ends in the middle of another region 226is freed. Behavior is undefined if invalid arguments are provided. 227.Pp 228.Fn extent_print 229Print out information about extent 230.Fa ex . 231This function always succeeds. Behavior is undefined if invalid 232arguments are provided. 233.Sh RETURN VALUES 234The behavior of all extent manager functions is undefined if given 235invalid arguments. 236.Fn extent_create 237returns the extent map on success, or 238.Dv NULL 239if it fails to allocate storage for the extent map. It always 240succeeds when creating a fixed extent or when given the flag 241.Dv EX_WAITOK . 242.Fn extent_alloc , 243.Fn extent_alloc_region , 244.Fn extent_alloc_subregion , 245and 246.Fn extent_free 247return one of the following values: 248.Bl -tag -offset indent -width "XXXXXXXX" 249.It Dv 0 250Operation was successful. 251.It Dv ENOMEM 252If 253.Dv EX_NOWAIT 254is specified, the extent manager was not able to allocate a region 255descriptor for the new region or to split a region when freeing a 256partial region. 257.It Dv EAGAIN 258Requested region is not available and 259.Dv EX_WAITSPACE 260was not specified. 261.It Dv EINTR 262Process received a signal while waiting for the requested region to 263become available in the extent. Does not apply to 264.Fn extent_free . 265.El 266.Sh EXAMLPES 267Here is an example of a (useless) function that uses several of the 268extent manager routines. 269.Bd -literal 270void 271func() 272{ 273 struct extent *foo_ex; 274 u_long region_start; 275 int error; 276 277 /* 278 * Extent "foo" manages a 256k region starting at 0x0 and 279 * only allows complete regions to be freed so that 280 * extent_free() never needs to allocate memory. 281 */ 282 foo_ex = extent_create("foo", 0x0, 0x3ffff, M_DEVBUF, 283 NULL, 0, EX_WAITOK | EX_NOCOALESCE); 284 285 /* 286 * Allocate an 8k region, aligned to a 4k boundary, which 287 * does not cross any of the 3 64k boundaries (at 64k, 288 * 128k, and 192k) within the extent. 289 */ 290 error = extent_alloc(foo_ex, 0x2000, 0x1000, 0x10000, 291 EX_NOWAIT, ®ion_start); 292 if (error) 293 panic("you lose"); 294 295 /* 296 * Give up the extent. 297 */ 298 extent_destroy(foo_ex); 299} 300.Ed 301.Sh CODE REFERENCES 302This section describes places within the NetBSD source tree where 303actual code implementing or using the extent manager can be found. 304All pathnames are relative to 305.Nm /usr/src . 306.Pp 307The extent manager itself is implemented within the file 308.Nm sys/kern/subr_extent.c . 309Function prototypes for the framework are located in 310.Nm sys/sys/extent.h . 311.Pp 312The i386 bus management code uses the extent manager for managing I/O 313ports and I/O memory. This code is in the file 314.Nm sys/arch/i386/i386/machdep.c . 315.Sh AUTHOR 316The NetBSD extent manager was architected and implemented by Jason 317R. Thorpe <thorpej@NetBSD.ORG>. Matthias Drochner 318<drochner@zelux6.zel.kfa-juelich.de> contributed to the initial 319testing and optimization of the implementation. Chris Demetriou 320<cgd@NetBSD.ORG> contributed many architectural suggestions. 321.Sh SEE ALSO 322.Xr malloc 9 . 323.Sh HISTORY 324The NetBSD extent manager appeared in 325.Nx 1.2A . 326