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). The blocks in this header 8 are reserved for various purposes. For example, block #0 is used for 9 the volume header or for a volume header backup. 10 11 * It is very important to remember that the Freemap only uses blocks 12 from these reserved areas. Freemap blocks are NOT dynamically 13 allocated. 14 15 * On-mount, the synchronization TID for the main H2 filesystem is 16 compared against the synchronization TID of the freemap and the 17 H2 topology is incrementally iterated using mirror_tid to update 18 the freemap with any missing information. This way the freemap flush 19 does not need to be synchronized with the normal H2 flush. This 20 can be done very quickly on-mount. 21 22 * The freemap is flushed in a manner similar to the normal H2 filesystem, 23 but as mentioned above it can be synchronized independently of the data 24 it represents. One freemap flush could cover several H2 flushes. A 25 freemap flush is not necessary for e.g. a fsync() or sync() to 26 complete successfully. 27 28 * The freemap granularity is 64KB (radix of 16) but the minimum 29 allocation radix for code is 1KB (radix of 10). 1KB inodes can 30 hold up to 512 bytes of direct data, so small files eat exactly 31 1KB of media storage inclusive of the inode. 32 33 * Representation of storage is block-oriented with ~1KB granularity 34 in the filesystem topology. However, H2 also stores freemap locality 35 hints in the inode at all levels which specifies which freemap zones 36 all storage allocations made by the sub-tree are allocated from. Up 37 to four zones may be listed in each inode. The zones are power-of-2 38 sized and aligned the same and use a base/radix representation 39 (same as used for blockref->data_off). 40 41 During updates higher level inodes may not have a sufficient number of 42 entries to represent the storage used on a fine-grain. In this 43 situation the representations back-off to larger radix values. 44 45 Ultimately these representations will be optimized by background scans. 46 That is, ultimately storage localization can be optimized bottom-up 47 such that it winds up being fairly optimal. This includes the ability 48 to detect when a writable snapshot has differentiated sufficiently to 49 warrant a split. This optimization should NOT attempt to dup common 50 data blocks. 51 52 XXX 53 54 * The zone oriented forward storage references in the inode (the four 55 entries) is used by the bulk free-scan to reduce the amount of 56 meta-data which must be duplicatively scanned. More specifically, 57 when the sysadmin deletes storage and/or files or even whole directory 58 subhierachies, it is possible for a bulk free-scan to incrementally 59 scan the meta-data topology that covers ONLY those areas to determine 60 if it is possible to free up any actual blocks. 61 62 XXX 63 64 * H2 does not require that a rm -rf or snapshot destruction, truncation, 65 or any other operation actually mark freemap blocks as being 66 almost-free. That is, the freemap elements can remain set to 67 ALLOCATED (11). In fact, it is possible to just delete the directory 68 inode itself and not even recursively scan or delete sub-directories or 69 files. The related storage will eventually be freed by an exhaustive 70 bulk free-scan anyway. 71 72 Freemap Topology 73 74 The freemap topology contains 4 levels of meta-data (blockref arrays), 75 one of which is embedded in the volume header (so only three real 76 meta-data levels), plus one level of leaf-data. 77 78 Level 1 - (radix 10) 64KB blockmap representing 2GB. There are 1024 79 entries representing ~2MB worth of media storage per entry. 80 81 Each entry maps 32 x 64KB allocations @ 2 bits per allocation, 82 plus contains additional meta-data which allows H2 to cluster 83 I/O operations. Each entry locks the allocation granularity 84 (e.g. to 1KB = radix 10 for inodes). 85 86 Level 2 - (radix 10) 64KB blockmap representing 2TB (~2GB per entry) 87 Level 3 - (radix 10) 64KB blockmap representing 2PB (~2TB per entry) 88 Level 4 - (radix 10) 64KB blockmap representing 2EB (~2PB per entry) 89 Level 5 - (radix 3) blockref x 8 in volume header representing 16EB (2^64) 90 (this conveniently eats one 512-byte 'sector' of the 64KB 91 volume header). 92 93 Each level is assign reserved blocks in the 4MB header per 2GB zone. 94 Since we use block 0 for the volume header / volume header backup, 95 our level names above can simply also represent the relative block 96 number. Level 1 uses block 1 through level 4 using block 4. Level 5 97 is stored in the volume header. 98 99 In addition there are FOUR SETS, A, B, C, and D, each containing blocks 100 for level 1-4. Hammer2 alternates between sets on a block-by-block basis 101 in order to maintain consistency when updating the freemap. 102 103 Leaf Substructure 104 105 * radix - Clustering radix. All allocations for any given ~2MB zone 106 are always the same size, allowing the filesystem code to 107 cluster buffer cache I/O. 108 109 * bitmap - four 32 bit words representing ~2MB in 64KB allocation chunks 110 at 2 bits per chunk. The filesystem allocation granularity 111 can be smaller (currently ~1KB minimum), and the live 112 filesystem keeps caches iterations when allocating multiple 113 chunks. However, on remount any partial allocations out of 114 a 64KB allocation block causes the entire 64KB to be 115 considered allocated. Fragmented space can potentially be 116 reclaimed and/or relocated by the bulk block free scan. 117 118 The 2-bit bitmap fields are assigned as follows: 119 120 00 FREE 121 01 ARMED for free stage (future use) 122 10 ARMED for free stage (future use) 123 11 ALLOCATED 124 125 It should be noted that in some cases, such as snapshot 126 destruction, H2 does not bother to actually ARM the related 127 blocks (which would take a long time). Instead, the bulk 128 free-scan may have to do a more exhaustive scan. 129 130 Blockref Substructure 131 132 The blockref substructure at each level steals some space from the 133 check code area (a 24-byte area). We only need 4 bytes for the check 134 code icrc. We use some of the remaining space to store information 135 that allows the block allocator to do its work more efficiently. 136 137 * bigmask - A mask of radixes available for allocation under this 138 blockref. Typically initialized to -1. 139 140 * avail - Total available space in bytes. 141 142 The freemap allocator uses a cylinder-group-like abstraction using 143 the localized allocation concept first implemented by UFS. In HAMMER2 144 there is no such thing as a real cylinder group, but we do the next 145 best thing by implementing our layer 1 blockmap representing 2GB. 146 147 The layer 1 blockmap is an array of 1024 blockrefs, so each blockref 148 covers 2MB worth of media storage. HAMMER2's 'cylinder group' concept 149 thus has a minimum granularity of 2MB. A typical setting might be e.g. 150 10MB. 151 152 By localizing allocations to cylinder groups based on various bits of 153 information, HAMMER2 tries to allocate space on the disk and still leave 154 some left over for localized expansion and to reduce fragmentation at 155 the same time. Not an easy task, especially considering the copy-on-write 156 nature of the filesystem. This part of the algorithm likely needs a lot 157 of work but I hope I've laid down a media format that will not have to be 158 changed down the line to accomodate better allocation strategies. 159 160 Initial Conditions 161 162 The freemap is a multi-indirect block structure but there is no real 163 reason to pre-format it in newfs_hammer2. Instead, newfs_hammer2 simply 164 leaves the associated top-level indirect blocks empty and uses the 165 (voldata->allocator_beg) field to allocate space linearly, then leaves 166 it to the live filesystem to initialize the freemap as more space gets 167 allocated. 168 169 How blocks are freed 170 171 The freemap bit patterns for each 64KB block are as follows: 172 173 00 FREE 174 01 ARMED (for free) (future use) 175 10 ARMED (for free) (future use) 176 11 ALLOCATED 177 178 Currently H2 only implements 00 and 11. When a file, topology, or 179 snapshot is deleted H2 simply leaves the blocks marked allocated but 180 records the related freezone/radix(s) in memory. 181 182 At some point a background bulk free-scan will run. This code must 183 scan meta-data and has a limited cache to detect duplicative sub-trees 184 (due to snapshots). It uses the freezone/radix information recorded 185 in memory to reduce the complexity of the scan, find all references to 186 the related blocks in the meta-data, and determines what can actually 187 be freed. Once this determination is made the bulk free-scan sets 188 the related freemap bits to FREE (00). 189 190 An exhaustive free-scan is not usually required during normal operation 191 but is typically run incrementally by cron every so often to ensure, over 192 time, that all freeable blocks are actually freed. This is most useful 193 when maintaining multiple snapshots. 194 195 Use of Generic indirect-block API 196 197 I decided to use the same indirect-block allocation model for the 198 freemap that normal files use, with a few special cases added to force 199 specific radix values and to 'allocate' the freemap-related blocks 200 and indirect blocks via a reserved-block calculation and (obviously) 201 not via a recursive call to the allocator. 202 203 The Freemap is defined above as a fixed 5-level scheme (level 1-5), 204 but in actual operation the radix tree can be shortcut just as it 205 is with normal files. However, shorcuts are forced into the radix 206 values of this specification and reserved blocks are calculated based 207 on the radix level and offset, so as the freemap becomes more fleshed 208 out the tree looks more and more like the specification. 209 210 One advantage of doing things this way is that smaller filesystems 211 won't actually use a 6-level scheme. A 16GB filesystem can use 8 212 blockrefs at layer 5 (in the volume header) that point directly to 213 layer 1. A 16TB filesystem can use 8 blockrefs at layer5 that point 214 to layer 2. And so forth. 215 216 At the moment we have no plans to return any of the unused 4MB zone 217 header space (per 2GB of storage) back to the filesystem for general use. 218 There are lots of things we may want to use the reserved areas for in 219 the future. 220