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