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 { |
111 | __le32 ; |
112 | __le32 ; |
113 | __le64 ; |
114 | } __packed __aligned(8); |
115 | |
116 | /*----------------------------------------------------------------*/ |
117 | |
118 | int sm_ll_extend(struct ll_disk *ll, dm_block_t ); |
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 | |