13241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber/* 23241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * Copyright (C) 2011 Red Hat, Inc. 33241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * 43241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * This file is released under the GPL. 53241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber */ 63241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 73241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber#ifndef DM_SPACE_MAP_COMMON_H 83241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber#define DM_SPACE_MAP_COMMON_H 93241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 103241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber#include "dm-btree.h" 113241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 123241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber/*----------------------------------------------------------------*/ 133241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 143241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber/* 153241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * Low level disk format 163241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * 173241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * Bitmap btree 183241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * ------------ 193241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * 203241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * Each value stored in the btree is an index_entry. This points to a 213241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * block that is used as a bitmap. Within the bitmap hold 2 bits per 223241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * entry, which represent UNUSED = 0, REF_COUNT = 1, REF_COUNT = 2 and 233241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * REF_COUNT = many. 243241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * 253241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * Refcount btree 263241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * -------------- 273241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * 283241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * Any entry that has a ref count higher than 2 gets entered in the ref 293241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * count tree. The leaf values for this tree is the 32-bit ref count. 303241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber */ 313241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 323241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberstruct disk_index_entry { 333241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 blocknr; 343241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le32 nr_free; 353241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le32 none_free_before; 363241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber} __packed; 373241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 383241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 393241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber#define MAX_METADATA_BITMAPS 255 403241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberstruct disk_metadata_index { 413241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le32 csum; 423241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le32 padding; 433241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 blocknr; 443241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 453241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber struct disk_index_entry index[MAX_METADATA_BITMAPS]; 463241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber} __packed; 473241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 483241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberstruct ll_disk; 493241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 503241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornbertypedef int (*load_ie_fn)(struct ll_disk *ll, dm_block_t index, struct disk_index_entry *result); 513241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornbertypedef int (*save_ie_fn)(struct ll_disk *ll, dm_block_t index, struct disk_index_entry *ie); 523241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornbertypedef int (*init_index_fn)(struct ll_disk *ll); 533241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornbertypedef int (*open_index_fn)(struct ll_disk *ll); 543241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornbertypedef dm_block_t (*max_index_entries_fn)(struct ll_disk *ll); 553241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornbertypedef int (*commit_fn)(struct ll_disk *ll); 563241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 573241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberstruct ll_disk { 583241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber struct dm_transaction_manager *tm; 593241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber struct dm_btree_info bitmap_info; 603241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber struct dm_btree_info ref_count_info; 613241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 623241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber uint32_t block_size; 633241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber uint32_t entries_per_block; 643241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber dm_block_t nr_blocks; 653241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber dm_block_t nr_allocated; 663241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 673241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber /* 683241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber * bitmap_root may be a btree root or a simple index. 693241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber */ 703241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber dm_block_t bitmap_root; 713241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 723241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber dm_block_t ref_count_root; 733241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 743241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber struct disk_metadata_index mi_le; 753241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber load_ie_fn load_ie; 763241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber save_ie_fn save_ie; 773241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber init_index_fn init_index; 783241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber open_index_fn open_index; 793241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber max_index_entries_fn max_entries; 803241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber commit_fn commit; 813241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber}; 823241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 833241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberstruct disk_sm_root { 843241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 nr_blocks; 853241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 nr_allocated; 863241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 bitmap_root; 873241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 ref_count_root; 883241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber} __packed; 893241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 903241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber#define ENTRIES_PER_BYTE 4 913241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 923241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberstruct disk_bitmap_header { 933241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le32 csum; 943241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le32 not_used; 953241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber __le64 blocknr; 963241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber} __packed; 973241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 983241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberenum allocation_event { 993241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber SM_NONE, 1003241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber SM_ALLOC, 1013241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber SM_FREE, 1023241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber}; 1033241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 1043241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber/*----------------------------------------------------------------*/ 1053241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 1063241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks); 1073241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result); 1083241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result); 1093241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin, 1103241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber dm_block_t end, dm_block_t *result); 1113241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_insert(struct ll_disk *ll, dm_block_t b, uint32_t ref_count, enum allocation_event *ev); 1123241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_inc(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev); 1133241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_dec(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev); 1143241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_commit(struct ll_disk *ll); 1153241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 1163241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm); 1173241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm, 1183241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber void *root_le, size_t len); 1193241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 1203241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm); 1213241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornberint sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm, 1223241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber void *root_le, size_t len); 1233241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 1243241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber/*----------------------------------------------------------------*/ 1253241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber 1263241b1d3e0aaafbfcd320f4d71ade629728cc4f4Joe Thornber#endif /* DM_SPACE_MAP_COMMON_H */ 127