Give the A-list code the ability to do a forward or reverse allocation
[dragonfly.git] / sys / vfs / hammer / hammer_alist.h
CommitLineData
c60bb2c5
MD
1/*
2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
9775c955 34 * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.h,v 1.2 2007/10/16 18:16:42 dillon Exp $
c60bb2c5
MD
35 */
36
37/*
38 * The structures below represent HAMMER's on-disk and in-memory A-List
39 * support. An A-list is a radix tree bitmap allocator with hinting. It
40 * is very fast and efficient.
41 *
42 * A-lists can be single-layered or multi-layered. A single-layered
43 * A-list uses a radix 32 leaf and radix 16 internal nodes. A multi-layered
44 * A-list uses a radix 16 leaf and radix 16 internal nodes.
45 *
46 * Multi-layered A-lists allow otherwise independant A-lists to be stacked
47 * to form a single A-list.
48 */
49
50/*
51 * This on-disk structure represents the actual information an A-list needs
52 * to store to disk. Each A-list layer is made up of a linear array of
53 * meta-elements. The number of elements needed is calculated using a
54 * recursion. A-lists contain an early-termination feature which allows
55 * an A-list's storage to scale to the actual number of blocks that need
56 * to be managed regardless of whether they are on a radix boundary or not.
57 *
58 * The first almeta structure in the array is used for housekeeping and not
59 * part of the topology proper. The second almeta structure is the 'root'
60 * meta.
61 */
62typedef struct hammer_almeta {
63 u_int32_t bm_bitmap;
64 int32_t bm_bighint;
65} *hammer_almeta_t;
66
67#define bm_alist_freeblks bm_bitmap
68
69#define HAMMER_ALMETA_SIZE 8
70
71/*
72 * This in-memory structure specifies how an a-list is configured and
73 * can be shared by multiple live alists.
74 */
75typedef struct hammer_alist_config {
76 int32_t bl_blocks; /* area of coverage */
77 int32_t bl_radix; /* coverage radix */
78 int32_t bl_base_radix; /* chain to other allocators */
79 int32_t bl_skip; /* starting skip for linear layout */
80 int32_t bl_rootblks; /* meta-blocks allocated for tree */
81 int32_t bl_terminal; /* terminal alist, else layer recursion */
9775c955
MD
82 int (*bl_radix_init)(void *info, int32_t blk, int32_t radix);
83 int (*bl_radix_destroy)(void *info, int32_t blk, int32_t radix);
c60bb2c5 84 int32_t (*bl_radix_alloc_fwd)(void *info, int32_t blk, int32_t radix,
9775c955
MD
85 int32_t count, int32_t atblk,
86 int32_t *fullp);
c60bb2c5 87 int32_t (*bl_radix_alloc_rev)(void *info, int32_t blk, int32_t radix,
9775c955
MD
88 int32_t count, int32_t atblk,
89 int32_t *fullp);
90 void (*bl_radix_free)(void *info, int32_t blk, int32_t radix,
91 int32_t base_blk, int32_t count,
c60bb2c5
MD
92 int32_t *emptyp);
93 void (*bl_radix_print)(void *info, int32_t blk, int32_t radix,
94 int tab);
95} *hammer_alist_config_t;
96
97/*
98 * This in-memory structure is needed for each live alist.
99 */
100typedef struct hammer_alist_live {
101 hammer_alist_config_t config; /* a-list configuration */
102 hammer_almeta_t meta; /* location of meta array */
103 void *info; /* chaining call info argument */
104} *hammer_alist_t;
105
106#define HAMMER_ALIST_META_RADIX (sizeof(int32_t) * 4) /* 16 */
107#define HAMMER_ALIST_BMAP_RADIX (sizeof(int32_t) * 8) /* 32 */
108#define HAMMER_ALIST_BLOCK_NONE ((int32_t)-1)
9775c955 109#define HAMMER_ALIST_BLOCK_MAX ((int32_t)0x7fffffff)
c60bb2c5
MD
110
111/*
112 * Hard-code some pre-calculated constants for managing varying numbers
113 * of blocks. These are the number of meta-elements required.
114 */
115#define HAMMER_ALIST_METAELMS_256_1LYR 11
116#define HAMMER_ALIST_METAELMS_32K_1LYR 1095
117#define HAMMER_ALIST_METAELMS_16K_2LYR HAMMER_ALIST_METAELMS_32K_1LYR
118
119#define HAMMER_ALIST_METAELMS_4K_1LYR 139
120#define HAMMER_ALIST_METAELMS_4K_2LYR 275
121
9775c955
MD
122/*
123 * Function library support available to kernel and userland
124 */
125void hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
126 int32_t base_radix, int32_t maxmeta);
127void hammer_alist_init(hammer_alist_t live);
128int32_t hammer_alist_alloc(hammer_alist_t live, int32_t count);
129int32_t hammer_alist_alloc_fwd(hammer_alist_t live,
130 int32_t count, int32_t atblk);
131int32_t hammer_alist_alloc_rev(hammer_alist_t live,
132 int32_t count, int32_t atblk);
133int hammer_alist_isfull(hammer_alist_t live);
134int hammer_alist_isempty(hammer_alist_t live);
135void hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count);
136