Remove obsolete ieee80211_amrr.9 manual page.
[dragonfly.git] / sys / vfs / hammer2 / FREEMAP
1
2                         HAMMER2 Freemap Design Notes
3
4                                 Overview
5
6     HAMMER2 Media is broken down into 2 GByte zones.  Each 2 GByte zone
7     contains a 4 MByte header (64 x 64K blocks = 0.2% of storage).  The
8     blocks in this header are reserved for various purposes.  For example,
9     block #0 is reserved for a volume header or volume header backup.  Most
10     of the 64KB blocks in this header are reserved for use by the freemap.
11
12     The freemap only uses blocks from these reserved areas.  In order to
13     ensure that any of the four volume headers can be used for the mount
14     (in case some are found to be corrupted), each freemap block in the
15     logical freemap topology iterates through 6 different copies.  The
16     freemap is a 4-layer topology (+1 3-bit layer in the volume header),
17     so 6x4 = 24 of the 64 reserved blocks are dedicated to freemap
18     operations.
19
20     Any given modification of a freemap block that crosses a flush group
21     must cycle to the next copy of the freemap block.  Having 6 copies
22     ensures that:
23
24     - Each of the four backup volume headers points to a consistent
25       freemap topology.  This eats 4 copies.
26
27     - That recovery operations during mount do not modify the state of the
28       freemap topology pointed to by older volume headers that are still
29       valid.  This eats 1 copy.
30
31     - The bulk free scan eats 1 copy to use as spool-off space if the
32       thread hits its ram limits.  This copy is not part of the normal
33       rotation.
34
35     - Total is 6 copies.
36
37     However, there is one major restriction: If an older volume header is
38     selected by the mount code, any newer (presumably corrupt since the
39     mount code didn't select it) volume headers will lose freemap consistency
40     as the freemap code rotates into freemap blocks that might have been used
41     by the topology pointed to by the newer (but not selected) backup
42     volume headers.  For a RW mount, this means that if an older volume
43     backup is selected, the newer ones that were not selected MUST be
44     formally invalidated and cannot be used in a remount attempt.  To
45     mitigate the potential loss of data, any volume headers lost in this
46     manner can be snapshotted and the freemap recovery scan (in a RW mount)
47     can also scan the snapshots to try to ensure that the blocks are marked
48     as allocated.  The system operator can then check the snapshot manually.
49
50     During normal operation, each filesystem flush rotates to a new backup
51     volume header (a filesystem has up to four) and retains full consistency
52     for the older volume headers.  Each logical freemap block in the topology
53     rotates through the 6 possible versions (on-modify only).
54
55                                 Freemap Topology
56
57     The freemap topology contains 4 levels of meta-data (blockref arrays),
58     one of which is embedded in the volume header (so only three real
59     meta-data levels), plus one level of leaf-data.  Unlike normal files,
60     which use a variable-radix, the freemap topology uses a fixed radix to
61     simplify the algorithm and to ensure freemap locality to the blocks
62     under management.
63
64     Level 1 - (radix 10 + 21) 64KB representing 2GB.  This is represented
65               by a hammer2_bmap_data[1024] array.  Each entry represents
66               2MB worth of media storage x 1024 entries to represent 2GB.
67               Each entry contains a 128x2 bit bitmap representing 16KB
68               of storage in 2 bits (128 x 16KB = 2MB).
69
70     Level 2 - (radix 10) 64KB blockmap representing 2TB (~2GB per entry)
71     Level 3 - (radix 10) 64KB blockmap representing 2PB (~2TB per entry)
72     Level 4 - (radix 10) 64KB blockmap representing 2EB (~2PB per entry)
73     Level 5 - (radix 3) blockref x 8 in volume header representing 16EB (2^64)
74               (this conveniently eats one 512-byte 'sector' of the 64KB
75               volume header).
76
77     Each level is assign reserved blocks in the 4MB header per 2GB zone.
78     Since we use block 0 for the volume header / volume header backup,
79     our level names above can simply also represent the relative block
80     number.  Level 1 uses block 1 through level 4 using block 4.  Level 5
81     is stored in the volume header.
82
83                                     Flushing
84
85     The freemap does not have to be flushed by fsync/sync, but should probably
86     be flushed at least once a minute by the normal filesystem sync.  The
87     reason it does not have to be flushed every time is that the freemap
88     recovery (using the last fully flushed freemap TID) will simply do an
89     incremental scan of the main filesystem tree between the freemap TID
90     and the main filesystem tree's TID to ensure that blocks allocated in
91     the interim are properly allocated in the freemap.  Simple as that.
92
93                                 Freemap Granularity
94
95     The freemap granularity is 16KB (radix of 14) but the minimum
96     allocation radix is 1KB (radix of 10) (and can be in multiples of
97     1KB with some coding).  1KB inodes can hold up to 512 bytes of direct
98     data, so tiny files eat exactly 1KB of media storage inclusive of the
99     inode.
100
101     The freemap keeps track of partial allocations in-memory but not
102     on-media, so even a normal umount will cause partially allocated
103     blocks to appear fully allocated until some later date when the
104     bulk scan code defragments it.
105
106                                    Block Selection
107
108     Block selection is localized to be near the inode's (or nearby data)
109     blockref.  The algorithmic complexity of determining locality is not
110     defined here atm.
111
112                                 Leaf Substructure
113
114     * radix  - Clustering radix.  All allocations for any given ~2MB zone
115                are always the same size, allowing the filesystem code to
116                cluster buffer cache I/O.
117
118     * bitmap - four 32 bit words representing ~2MB in 16KB allocation chunks
119                at 2 bits per chunk.  The filesystem allocation granularity
120                can be smaller (currently ~1KB minimum), and the live
121                filesystem keeps caches iterations when allocating multiple
122                chunks.  However, on remount any partial allocations out of
123                a 64KB allocation block causes the entire 64KB to be
124                considered allocated.  Fragmented space can potentially be
125                reclaimed and/or relocated by the bulk block free scan.
126
127                The 2-bit bitmap fields are assigned as follows:
128
129                00       FREE
130                01       ARMED for free stage (future use)
131                10       ARMED for free stage (future use)
132                11       ALLOCATED
133
134                It should be noted that in some cases, such as snapshot
135                destruction, H2 does not bother to actually ARM the related
136                blocks (which would take a long time).  Instead, the bulk
137                free-scan may have to do a more exhaustive scan.
138
139                               Blockref Substructure
140
141     The blockref substructure at each level steals some space from the
142     check code area (a 24-byte area).  We only need 4 bytes for the check
143     code icrc.  We use some of the remaining space to store information
144     that allows the block allocator to do its work more efficiently.
145
146     * bigmask - A mask of radixes available for allocation under this
147                 blockref.  Typically initialized to -1.
148
149     * avail   - Total available space in bytes.
150
151     The freemap allocator uses a cylinder-group-like abstraction using
152     the localized allocation concept first implemented by UFS.  In HAMMER2
153     there is no such thing as a real cylinder group, but we do the next
154     best thing by implementing our layer 1 blockmap representing 2GB.
155
156                                 Level 2, 3, 4, 5
157
158     Levels 2, 3, and 4 contains an array blockmap[1024] (64KB total),
159     supplying 10 bits of address space each.  Level 5 is a blockmap[8] stored
160     in the volume header supplying 3 bits of address space.  (level 0
161     supplies 10 + 21 bits of address space).
162
163     The Level1 blockmap is HAMMER2's idea of a 'cylinder group', thus
164     effectively fixed at multiples of ~2MB or so.
165
166                                 Initial Conditions
167
168     The freemap is a multi-indirect block structure but there is no real
169     reason to pre-format it in newfs_hammer2.  Instead, newfs_hammer2 simply
170     leaves the associated top-level indirect blocks empty and uses the
171     (voldata->allocator_beg) field to allocate space linearly, then leaves
172     it to the live filesystem to initialize the freemap as more space gets
173     allocated.
174
175     The freemap does NOT use a fixed 5-level radix tree.  It uses the same
176     blockmap algorithm used for file blocks but restricts any recursion to
177     specific radix values.  This means that small filesystems will have much
178     smaller freemap depths.  2 layers (and not counting the volume header as
179     a layer) gets us 16GB, 3 layers gets us 16TB.
180
181                         How blocks are allocated and freed
182
183     H2 keeps track of sub-16KB allocations in-memory.  On a crash/reboot any
184     partial allocations effectively become full 16KB block allocations until
185     the bulk freeing code comes along and fixes it.  2-bit patterns are as
186     follows:
187
188        00       FREE
189        01       ARMED (for free) (future use)
190        10       ARMED (for free) (future use)
191        11       ALLOCATED
192
193     Currently H2 only implements 00 and 11.  When a file, topology, or
194     snapshot is deleted H2 simply leaves the blocks marked allocated but
195     records the related freezone/radix(s) in memory.
196
197     At some point a background bulk free-scan will run.  This code must
198     scan meta-data and has a limited cache to detect duplicative sub-trees
199     (due to snapshots).  It uses the freezone/radix information recorded
200     in memory to reduce the complexity of the scan, find all references to
201     the related blocks in the meta-data, and determines what can actually
202     be freed.  Once this determination is made the bulk free-scan sets
203     the related freemap bits to FREE (00).
204
205     An exhaustive free-scan is not usually required during normal operation
206     but is typically run incrementally by cron every so often to ensure, over
207     time, that all freeable blocks are actually freed.  This is most useful
208     when maintaining multiple snapshots.
209
210                         Use of Generic indirect-block API
211
212     I decided to use the same indirect-block allocation model for the
213     freemap that normal files use, with a few special cases added to force
214     specific radix values and to 'allocate' the freemap-related blocks
215     and indirect blocks via a reserved-block calculation and (obviously)
216     not via a recursive call to the allocator.
217
218     The Freemap is defined above as a fixed 5-level scheme (level 1-5),
219     but in actual operation the radix tree can be shortcut just as it
220     is with normal files.  However, shorcuts are forced into the radix
221     values of this specification and reserved blocks are calculated based
222     on the radix level and offset, so as the freemap becomes more fleshed
223     out the tree looks more and more like the specification.
224
225     One advantage of doing things this way is that smaller filesystems
226     won't actually use a 6-level scheme.  A 16GB filesystem can use 8
227     blockrefs at layer 5 (in the volume header) that point directly to
228     layer 1.  A 16TB filesystem can use 8 blockrefs at layer5 that point
229     to layer 2.  And so forth.
230
231     At the moment we have no plans to return any of the unused 4MB zone
232     header space (per 2GB of storage) back to the filesystem for general use.
233     There are lots of things we may want to use the reserved areas for in
234     the future.