1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* 3 * Copyright (C) 2011 Red Hat, Inc. 4 * 5 * This file is released under the GPL. 6 */ 7 8 #ifndef DM_SPACE_MAP_COMMON_H 9 #define DM_SPACE_MAP_COMMON_H 10 11 #include "dm-btree.h" 12 13 /*----------------------------------------------------------------*/ 14 15 /* 16 * Low level disk format 17 * 18 * Bitmap btree 19 * ------------ 20 * 21 * Each value stored in the btree is an index_entry. This points to a 22 * block that is used as a bitmap. Within the bitmap hold 2 bits per 23 * entry, which represent UNUSED = 0, REF_COUNT = 1, REF_COUNT = 2 and 24 * REF_COUNT = many. 25 * 26 * Refcount btree 27 * -------------- 28 * 29 * Any entry that has a ref count higher than 2 gets entered in the ref 30 * count tree. The leaf values for this tree is the 32-bit ref count. 31 */ 32 33 struct disk_index_entry { 34 __le64 blocknr; 35 __le32 nr_free; 36 __le32 none_free_before; 37 } __packed __aligned(8); 38 39 40 #define MAX_METADATA_BITMAPS 255 41 struct disk_metadata_index { 42 __le32 csum; 43 __le32 padding; 44 __le64 blocknr; 45 46 struct disk_index_entry index[MAX_METADATA_BITMAPS]; 47 } __packed __aligned(8); 48 49 struct ll_disk; 50 51 typedef int (*load_ie_fn)(struct ll_disk *ll, dm_block_t index, struct disk_index_entry *result); 52 typedef int (*save_ie_fn)(struct ll_disk *ll, dm_block_t index, struct disk_index_entry *ie); 53 typedef int (*init_index_fn)(struct ll_disk *ll); 54 typedef int (*open_index_fn)(struct ll_disk *ll); 55 typedef dm_block_t (*max_index_entries_fn)(struct ll_disk *ll); 56 typedef int (*commit_fn)(struct ll_disk *ll); 57 58 /* 59 * A lot of time can be wasted reading and writing the same 60 * index entry. So we cache a few entries. 61 */ 62 #define IE_CACHE_SIZE 64 63 #define IE_CACHE_MASK (IE_CACHE_SIZE - 1) 64 65 struct ie_cache { 66 bool valid; 67 bool dirty; 68 dm_block_t index; 69 struct disk_index_entry ie; 70 }; 71 72 struct ll_disk { 73 struct dm_transaction_manager *tm; 74 struct dm_btree_info bitmap_info; 75 struct dm_btree_info ref_count_info; 76 77 uint32_t block_size; 78 uint32_t entries_per_block; 79 dm_block_t nr_blocks; 80 dm_block_t nr_allocated; 81 82 /* 83 * bitmap_root may be a btree root or a simple index. 84 */ 85 dm_block_t bitmap_root; 86 87 dm_block_t ref_count_root; 88 89 struct disk_metadata_index mi_le; 90 load_ie_fn load_ie; 91 save_ie_fn save_ie; 92 init_index_fn init_index; 93 open_index_fn open_index; 94 max_index_entries_fn max_entries; 95 commit_fn commit; 96 bool bitmap_index_changed:1; 97 98 struct ie_cache ie_cache[IE_CACHE_SIZE]; 99 }; 100 101 struct disk_sm_root { 102 __le64 nr_blocks; 103 __le64 nr_allocated; 104 __le64 bitmap_root; 105 __le64 ref_count_root; 106 } __packed __aligned(8); 107 108 #define ENTRIES_PER_BYTE 4 109 110 struct disk_bitmap_header { 111 __le32 csum; 112 __le32 not_used; 113 __le64 blocknr; 114 } __packed __aligned(8); 115 116 /*----------------------------------------------------------------*/ 117 118 int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks); 119 int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result); 120 int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result); 121 int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin, 122 dm_block_t end, dm_block_t *result); 123 int sm_ll_find_common_free_block(struct ll_disk *old_ll, struct ll_disk *new_ll, 124 dm_block_t begin, dm_block_t end, dm_block_t *result); 125 126 /* 127 * The next three functions return (via nr_allocations) the net number of 128 * allocations that were made. This number may be negative if there were 129 * more frees than allocs. 130 */ 131 int sm_ll_insert(struct ll_disk *ll, dm_block_t b, uint32_t ref_count, int32_t *nr_allocations); 132 int sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e, int32_t *nr_allocations); 133 int sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e, int32_t *nr_allocations); 134 int sm_ll_commit(struct ll_disk *ll); 135 136 int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm); 137 int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm, 138 void *root_le, size_t len); 139 140 int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm); 141 int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm, 142 void *root_le, size_t len); 143 144 /*----------------------------------------------------------------*/ 145 146 #endif /* DM_SPACE_MAP_COMMON_H */ 147