Clean up the structural organization. Separate out A-lists and make
[dragonfly.git] / sys / vfs / hammer / hammer_alist.h
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  * 
34  * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.h,v 1.1 2007/10/12 18:57:45 dillon Exp $
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  */
62 typedef 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  */
75 typedef 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 */
82         int     (*bl_radix_init)(void *info, int32_t blk, int32_t radix,
83                                         int32_t count);
84         int32_t (*bl_radix_alloc_fwd)(void *info, int32_t blk, int32_t radix,
85                                         int32_t count, int32_t *fullp);
86         int32_t (*bl_radix_alloc_rev)(void *info, int32_t blk, int32_t radix,
87                                         int32_t count, int32_t *fullp);
88         void    (*bl_radix_free)(void *info, int32_t freeBlk, int32_t count,
89                                         int32_t radix, int32_t blk,
90                                         int32_t *emptyp);
91         void    (*bl_radix_print)(void *info, int32_t blk, int32_t radix,
92                                         int tab);
93 } *hammer_alist_config_t;
94
95 /*
96  * This in-memory structure is needed for each live alist.
97  */
98 typedef struct hammer_alist_live {
99         hammer_alist_config_t config;   /* a-list configuration */
100         hammer_almeta_t meta;           /* location of meta array */
101         void *info;                     /* chaining call info argument */
102 } *hammer_alist_t;
103
104 #define HAMMER_ALIST_META_RADIX (sizeof(int32_t) * 4)   /* 16 */
105 #define HAMMER_ALIST_BMAP_RADIX (sizeof(int32_t) * 8)   /* 32 */
106 #define HAMMER_ALIST_BLOCK_NONE ((int32_t)-1)
107
108 /*
109  * Hard-code some pre-calculated constants for managing varying numbers
110  * of blocks.  These are the number of meta-elements required.
111  */
112 #define HAMMER_ALIST_METAELMS_256_1LYR  11
113 #define HAMMER_ALIST_METAELMS_32K_1LYR  1095
114 #define HAMMER_ALIST_METAELMS_16K_2LYR  HAMMER_ALIST_METAELMS_32K_1LYR
115
116 #define HAMMER_ALIST_METAELMS_4K_1LYR   139
117 #define HAMMER_ALIST_METAELMS_4K_2LYR   275
118