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