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 */