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