1 // SPDX-License-Identifier: CDDL-1.0 2 /* 3 * This file and its contents are supplied under the terms of the 4 * Common Development and Distribution License ("CDDL"), version 1.0. 5 * You may only use this file in accordance with the terms of version 6 * 1.0 of the CDDL. 7 * 8 * A full copy of the text of the CDDL should have accompanied this 9 * source. A copy of the CDDL is also available via the Internet at 10 * https://opensource.org/license/CDDL-1.0. 11 */ 12 /* 13 * Copyright (c) 2020, 2021, 2022 by Pawel Jakub Dawidek 14 */ 15 16 #ifndef _SYS_BRT_IMPL_H 17 #define _SYS_BRT_IMPL_H 18 19 #ifdef __cplusplus 20 extern "C" { 21 #endif 22 23 /* 24 * BRT - Block Reference Table. 25 */ 26 #define BRT_OBJECT_VDEV_PREFIX "com.fudosecurity:brt:vdev:" 27 28 /* 29 * We divide each VDEV into 16MB chunks. Each chunk is represented in memory 30 * by a 16bit counter, thus 1TB VDEV requires 128kB of memory: (1TB / 16MB) * 2B 31 * Each element in this array represents how many BRT entries do we have in this 32 * chunk of storage. We always load this entire array into memory and update as 33 * needed. By having it in memory we can quickly tell (during zio_free()) if 34 * there are any BRT entries that we might need to update. 35 * 36 * This value cannot be larger than 16MB, at least as long as we support 37 * 512 byte block sizes. With 512 byte block size we can have exactly 38 * 32768 blocks in 16MB. In 32MB we could have 65536 blocks, which is one too 39 * many for a 16bit counter. 40 */ 41 #define BRT_RANGESIZE (16 * 1024 * 1024) 42 _Static_assert(BRT_RANGESIZE / SPA_MINBLOCKSIZE <= UINT16_MAX, 43 "BRT_RANGESIZE is too large."); 44 /* 45 * We don't want to update the whole structure every time. Maintain bitmap 46 * of dirty blocks within the regions, so that a single bit represents a 47 * block size of entcounts. For example if we have a 1PB vdev then all 48 * entcounts take 128MB of memory ((64TB / 16MB) * 2B). We can divide this 49 * 128MB array of entcounts into 32kB disk blocks, as we don't want to update 50 * the whole 128MB on disk when we have updated only a single entcount. 51 * We maintain a bitmap where each 32kB disk block within 128MB entcounts array 52 * is represented by a single bit. This gives us 4096 bits. A set bit in the 53 * bitmap means that we had a change in at least one of the 16384 entcounts 54 * that reside on a 32kB disk block (32kB / sizeof (uint16_t)). 55 */ 56 #define BRT_BLOCKSIZE (32 * 1024) 57 #define BRT_RANGESIZE_TO_NBLOCKS(size) \ 58 (((size) - 1) / (BRT_BLOCKSIZE / sizeof (uint16_t)) + 1) 59 60 #define BRT_LITTLE_ENDIAN 0 61 #define BRT_BIG_ENDIAN 1 62 #ifdef _ZFS_LITTLE_ENDIAN 63 #define BRT_NATIVE_BYTEORDER BRT_LITTLE_ENDIAN 64 #define BRT_NON_NATIVE_BYTEORDER BRT_BIG_ENDIAN 65 #else 66 #define BRT_NATIVE_BYTEORDER BRT_BIG_ENDIAN 67 #define BRT_NON_NATIVE_BYTEORDER BRT_LITTLE_ENDIAN 68 #endif 69 70 typedef struct brt_vdev_phys { 71 uint64_t bvp_mos_entries; 72 uint64_t bvp_size; 73 uint64_t bvp_byteorder; 74 uint64_t bvp_totalcount; 75 uint64_t bvp_rangesize; 76 uint64_t bvp_usedspace; 77 uint64_t bvp_savedspace; 78 } brt_vdev_phys_t; 79 80 struct brt_vdev { 81 /* 82 * Pending changes from open contexts. 83 */ 84 kmutex_t bv_pending_lock; 85 avl_tree_t bv_pending_tree[TXG_SIZE]; 86 /* 87 * Protects bv_mos_*. 88 */ 89 krwlock_t bv_mos_entries_lock ____cacheline_aligned; 90 /* 91 * Protects all the fields starting from bv_initiated. 92 */ 93 krwlock_t bv_lock ____cacheline_aligned; 94 /* 95 * VDEV id. 96 */ 97 uint64_t bv_vdevid ____cacheline_aligned; 98 /* 99 * Object number in the MOS for the entcount array and brt_vdev_phys. 100 */ 101 uint64_t bv_mos_brtvdev; 102 /* 103 * Object number in the MOS and dnode for the entries table. 104 */ 105 uint64_t bv_mos_entries; 106 dnode_t *bv_mos_entries_dnode; 107 /* 108 * Is the structure initiated? 109 * (bv_entcount and bv_bitmap are allocated?) 110 */ 111 boolean_t bv_initiated; 112 /* 113 * Does the bv_entcount[] array needs byte swapping? 114 */ 115 boolean_t bv_need_byteswap; 116 /* 117 * Number of entries in the bv_entcount[] array. 118 */ 119 uint64_t bv_size; 120 /* 121 * This is the array with BRT entry count per BRT_RANGESIZE. 122 */ 123 uint16_t *bv_entcount; 124 /* 125 * bv_entcount[] potentially can be a bit too big to sychronize it all 126 * when we just changed few entcounts. The fields below allow us to 127 * track updates to bv_entcount[] array since the last sync. 128 * A single bit in the bv_bitmap represents as many entcounts as can 129 * fit into a single BRT_BLOCKSIZE. 130 * For example we have 65536 entcounts in the bv_entcount array 131 * (so the whole array is 128kB). We updated bv_entcount[2] and 132 * bv_entcount[5]. In that case only first bit in the bv_bitmap will 133 * be set and we will write only first BRT_BLOCKSIZE out of 128kB. 134 */ 135 ulong_t *bv_bitmap; 136 /* 137 * bv_entcount[] needs updating on disk. 138 */ 139 boolean_t bv_entcount_dirty; 140 /* 141 * brt_vdev_phys needs updating on disk. 142 */ 143 boolean_t bv_meta_dirty; 144 /* 145 * Sum of all bv_entcount[]s. 146 */ 147 uint64_t bv_totalcount; 148 /* 149 * Space on disk occupied by cloned blocks (without compression). 150 */ 151 uint64_t bv_usedspace; 152 /* 153 * How much additional space would be occupied without block cloning. 154 */ 155 uint64_t bv_savedspace; 156 /* 157 * Entries to sync. 158 */ 159 avl_tree_t bv_tree; 160 }; 161 162 /* 163 * Clones of blocks with the DEDUP bit set reference the DDT instead of 164 * the BRT. Their pending entries are kept separately from the per-vdev 165 * pending trees, sorted by the block checksum, matching the DDT ZAP hash 166 * order (the first checksum word is the pre-hashed ZAP key), and sharded 167 * by its top bits. It allows syncing context to process the shards in 168 * parallel, each walking a disjoint range of DDT ZAP leaves in the hash 169 * order, so that each compressed leaf block is decompressed only once 170 * and never by more than one thread. 171 */ 172 #define BRT_DEDUP_SHARDS_SHIFT 4 173 #define BRT_DEDUP_SHARDS (1 << BRT_DEDUP_SHARDS_SHIFT) 174 #define BRT_DEDUP_SHARD(bp) \ 175 ((bp)->blk_cksum.zc_word[0] >> (64 - BRT_DEDUP_SHARDS_SHIFT)) 176 177 struct brt_dedup_shard { 178 kmutex_t bds_lock; 179 avl_tree_t bds_tree[TXG_SIZE]; 180 }; 181 182 /* Size of offset / sizeof (uint64_t). */ 183 #define BRT_KEY_WORDS (1) 184 185 #define BRE_OFFSET(bre) (DVA_GET_OFFSET(&(bre)->bre_bp.blk_dva[0])) 186 187 /* 188 * In-core brt entry. 189 * On-disk we use ZAP with offset as the key and count as the value. 190 */ 191 typedef struct brt_entry { 192 avl_node_t bre_node; 193 blkptr_t bre_bp; 194 uint64_t bre_count; 195 uint64_t bre_pcount; 196 } brt_entry_t; 197 198 #ifdef __cplusplus 199 } 200 #endif 201 202 #endif /* _SYS_BRT_IMPL_H */ 203