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
33struct 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
41struct 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
49struct ll_disk;
50
51typedef int (*load_ie_fn)(struct ll_disk *ll, dm_block_t index, struct disk_index_entry *result);
52typedef int (*save_ie_fn)(struct ll_disk *ll, dm_block_t index, struct disk_index_entry *ie);
53typedef int (*init_index_fn)(struct ll_disk *ll);
54typedef int (*open_index_fn)(struct ll_disk *ll);
55typedef dm_block_t (*max_index_entries_fn)(struct ll_disk *ll);
56typedef 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
65struct ie_cache {
66 bool valid;
67 bool dirty;
68 dm_block_t index;
69 struct disk_index_entry ie;
70};
71
72struct 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
101struct 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
110struct disk_bitmap_header {
111 __le32 csum;
112 __le32 not_used;
113 __le64 blocknr;
114} __packed __aligned(8);
115
116/*----------------------------------------------------------------*/
117
118int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks);
119int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result);
120int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result);
121int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
122 dm_block_t end, dm_block_t *result);
123int 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 */
131int sm_ll_insert(struct ll_disk *ll, dm_block_t b, uint32_t ref_count, int32_t *nr_allocations);
132int sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e, int32_t *nr_allocations);
133int sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e, int32_t *nr_allocations);
134int sm_ll_commit(struct ll_disk *ll);
135
136int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm);
137int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm,
138 void *root_le, size_t len);
139
140int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm);
141int 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

source code of linux/drivers/md/persistent-data/dm-space-map-common.h