194 static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm)  in sm_ll_init()  argument
196 	memset(ll, 0, sizeof(struct ll_disk));  in sm_ll_init()
198 	ll->tm = tm;  in sm_ll_init()
200 	ll->bitmap_info.tm = tm;  in sm_ll_init()
201 	ll->bitmap_info.levels = 1;  in sm_ll_init()
208 	ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);  in sm_ll_init()
209 	ll->bitmap_info.value_type.inc = NULL;  in sm_ll_init()
210 	ll->bitmap_info.value_type.dec = NULL;  in sm_ll_init()
211 	ll->bitmap_info.value_type.equal = NULL;  in sm_ll_init()
213 	ll->ref_count_info.tm = tm;  in sm_ll_init()
214 	ll->ref_count_info.levels = 1;  in sm_ll_init()
215 	ll->ref_count_info.value_type.size = sizeof(uint32_t);  in sm_ll_init()
216 	ll->ref_count_info.value_type.inc = NULL;  in sm_ll_init()
217 	ll->ref_count_info.value_type.dec = NULL;  in sm_ll_init()
218 	ll->ref_count_info.value_type.equal = NULL;  in sm_ll_init()
220 	ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm));  in sm_ll_init()
222 	if (ll->block_size > (1 << 30)) {  in sm_ll_init()
227 	ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *  in sm_ll_init()
229 	ll->nr_blocks = 0;  in sm_ll_init()
230 	ll->bitmap_root = 0;  in sm_ll_init()
231 	ll->ref_count_root = 0;  in sm_ll_init()
232 	ll->bitmap_index_changed = false;  in sm_ll_init()
237 int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)  in sm_ll_extend()  argument
243 	nr_blocks = ll->nr_blocks + extra_blocks;  in sm_ll_extend()
244 	old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);  in sm_ll_extend()
245 	blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);  in sm_ll_extend()
247 	nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);  in sm_ll_extend()
248 	if (nr_indexes > ll->max_entries(ll)) {  in sm_ll_extend()
256 	ll->nr_blocks = nr_blocks;  in sm_ll_extend()
261 		r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);  in sm_ll_extend()
267 		dm_tm_unlock(ll->tm, b);  in sm_ll_extend()
269 		idx.nr_free = cpu_to_le32(ll->entries_per_block);  in sm_ll_extend()
272 		r = ll->save_ie(ll, i, &idx);  in sm_ll_extend()
280 int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result)  in sm_ll_lookup_bitmap()  argument
287 	if (b >= ll->nr_blocks) {  in sm_ll_lookup_bitmap()
292 	b = do_div(index, ll->entries_per_block);  in sm_ll_lookup_bitmap()
293 	r = ll->load_ie(ll, index, &ie_disk);  in sm_ll_lookup_bitmap()
297 	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),  in sm_ll_lookup_bitmap()
304 	dm_tm_unlock(ll->tm, blk);  in sm_ll_lookup_bitmap()
309 static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,  in sm_ll_lookup_big_ref_count()  argument
315 	r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);  in sm_ll_lookup_big_ref_count()
324 int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result)  in sm_ll_lookup()  argument
326 	int r = sm_ll_lookup_bitmap(ll, b, result);  in sm_ll_lookup()
334 	return sm_ll_lookup_big_ref_count(ll, b, result);  in sm_ll_lookup()
337 int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,  in sm_ll_find_free_block()  argument
343 	dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);  in sm_ll_find_free_block()
348 	begin = do_div(index_begin, ll->entries_per_block);  in sm_ll_find_free_block()
349 	end = do_div(end, ll->entries_per_block);  in sm_ll_find_free_block()
351 		end = ll->entries_per_block;  in sm_ll_find_free_block()
358 		r = ll->load_ie(ll, i, &ie_disk);  in sm_ll_find_free_block()
365 		r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),  in sm_ll_find_free_block()
370 		bit_end = (i == index_end - 1) ?  end : ll->entries_per_block;  in sm_ll_find_free_block()
380 			dm_tm_unlock(ll->tm, blk);  in sm_ll_find_free_block()
384 		dm_tm_unlock(ll->tm, blk);  in sm_ll_find_free_block()
386 		*result = i * ll->entries_per_block + (dm_block_t) position;  in sm_ll_find_free_block()
422 int sm_ll_insert(struct ll_disk *ll, dm_block_t b,  in sm_ll_insert()  argument
433 	bit = do_div(index, ll->entries_per_block);  in sm_ll_insert()
434 	r = ll->load_ie(ll, index, &ie_disk);  in sm_ll_insert()
438 	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),  in sm_ll_insert()
449 		r = sm_ll_lookup_big_ref_count(ll, b, &old);  in sm_ll_insert()
451 			dm_tm_unlock(ll->tm, nb);  in sm_ll_insert()
457 		dm_tm_unlock(ll->tm, nb);  in sm_ll_insert()
463 		dm_tm_unlock(ll->tm, nb);  in sm_ll_insert()
466 			r = dm_btree_remove(&ll->ref_count_info,  in sm_ll_insert()
467 					    ll->ref_count_root,  in sm_ll_insert()
468 					    &b, &ll->ref_count_root);  in sm_ll_insert()
477 		dm_tm_unlock(ll->tm, nb);  in sm_ll_insert()
480 		r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,  in sm_ll_insert()
481 				    &b, &le_rc, &ll->ref_count_root);  in sm_ll_insert()
490 		ll->nr_allocated++;  in sm_ll_insert()
497 		ll->nr_allocated--;  in sm_ll_insert()
503 	return ll->save_ie(ll, index, &ie_disk);  in sm_ll_insert()
527 static inline void exit_inc_context(struct ll_disk *ll, struct inc_context *ic)  in exit_inc_context()  argument
530 		dm_tm_unlock(ll->tm, ic->bitmap_block);  in exit_inc_context()
532 		dm_tm_unlock(ll->tm, ic->overflow_leaf);  in exit_inc_context()
535 static inline void reset_inc_context(struct ll_disk *ll, struct inc_context *ic)  in reset_inc_context()  argument
537 	exit_inc_context(ll, ic);  in reset_inc_context()
551 static int __sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic)  in __sm_ll_inc_overflow()  argument
563 	reset_inc_context(ll, ic);  in __sm_ll_inc_overflow()
565 	r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root,  in __sm_ll_inc_overflow()
566 				     b, &index, &ll->ref_count_root, &ic->overflow_leaf);  in __sm_ll_inc_overflow()
584 static int sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic)  in sm_ll_inc_overflow()  argument
606 	return __sm_ll_inc_overflow(ll, b, ic);  in sm_ll_inc_overflow()
609 static inline int shadow_bitmap(struct ll_disk *ll, struct inc_context *ic)  in shadow_bitmap()  argument
613 	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ic->ie_disk.blocknr),  in shadow_bitmap()
629 static inline int ensure_bitmap(struct ll_disk *ll, struct inc_context *ic)  in ensure_bitmap()  argument
632 		int r = dm_bm_write_lock(dm_tm_get_bm(ll->tm), le64_to_cpu(ic->ie_disk.blocknr),  in ensure_bitmap()
647 static inline int sm_ll_inc_bitmap(struct ll_disk *ll, dm_block_t b,  in sm_ll_inc_bitmap()  argument
662 		r = ensure_bitmap(ll, ic);  in sm_ll_inc_bitmap()
672 			ll->nr_allocated++;  in sm_ll_inc_bitmap()
686 			reset_inc_context(ll, ic);  in sm_ll_inc_bitmap()
690 			r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,  in sm_ll_inc_bitmap()
691 					    &b, &le_rc, &ll->ref_count_root);  in sm_ll_inc_bitmap()
702 			r = sm_ll_inc_overflow(ll, b, ic);  in sm_ll_inc_bitmap()
716 static int __sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e,  in __sm_ll_inc()  argument
726 	bit = do_div(index, ll->entries_per_block);  in __sm_ll_inc()
727 	r = ll->load_ie(ll, index, &ic.ie_disk);  in __sm_ll_inc()
731 	r = shadow_bitmap(ll, &ic);  in __sm_ll_inc()
735 	bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block);  in __sm_ll_inc()
736 	r = sm_ll_inc_bitmap(ll, b, bit, bit_end, nr_allocations, new_b, &ic);  in __sm_ll_inc()
738 	exit_inc_context(ll, &ic);  in __sm_ll_inc()
743 	return ll->save_ie(ll, index, &ic.ie_disk);  in __sm_ll_inc()
746 int sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e,  in sm_ll_inc()  argument
751 		int r = __sm_ll_inc(ll, b, e, nr_allocations, &b);  in sm_ll_inc()
762 static int __sm_ll_del_overflow(struct ll_disk *ll, dm_block_t b,  in __sm_ll_del_overflow()  argument
765 	reset_inc_context(ll, ic);  in __sm_ll_del_overflow()
766 	return dm_btree_remove(&ll->ref_count_info, ll->ref_count_root,  in __sm_ll_del_overflow()
767 			       &b, &ll->ref_count_root);  in __sm_ll_del_overflow()
770 static int __sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b,  in __sm_ll_dec_overflow()  argument
779 	reset_inc_context(ll, ic);  in __sm_ll_dec_overflow()
780 	r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root,  in __sm_ll_dec_overflow()
781 				     b, &index, &ll->ref_count_root, &ic->overflow_leaf);  in __sm_ll_dec_overflow()
797 		return __sm_ll_del_overflow(ll, b, ic);  in __sm_ll_dec_overflow()
804 static int sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b,  in sm_ll_dec_overflow()  argument
828 				return __sm_ll_del_overflow(ll, b, ic);  in sm_ll_dec_overflow()
834 	return __sm_ll_dec_overflow(ll, b, ic, old_rc);  in sm_ll_dec_overflow()
840 static inline int sm_ll_dec_bitmap(struct ll_disk *ll, dm_block_t b,  in sm_ll_dec_bitmap()  argument
854 		r = ensure_bitmap(ll, ic);  in sm_ll_dec_bitmap()
868 			ll->nr_allocated--;  in sm_ll_dec_bitmap()
880 			r = sm_ll_dec_overflow(ll, b, ic, &old);  in sm_ll_dec_bitmap()
885 				r = ensure_bitmap(ll, ic);  in sm_ll_dec_bitmap()
899 static int __sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e,  in __sm_ll_dec()  argument
909 	bit = do_div(index, ll->entries_per_block);  in __sm_ll_dec()
910 	r = ll->load_ie(ll, index, &ic.ie_disk);  in __sm_ll_dec()
914 	r = shadow_bitmap(ll, &ic);  in __sm_ll_dec()
918 	bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block);  in __sm_ll_dec()
919 	r = sm_ll_dec_bitmap(ll, b, bit, bit_end, &ic, nr_allocations, new_b);  in __sm_ll_dec()
920 	exit_inc_context(ll, &ic);  in __sm_ll_dec()
925 	return ll->save_ie(ll, index, &ic.ie_disk);  in __sm_ll_dec()
928 int sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e,  in sm_ll_dec()  argument
933 		int r = __sm_ll_dec(ll, b, e, nr_allocations, &b);  in sm_ll_dec()
944 int sm_ll_commit(struct ll_disk *ll)  in sm_ll_commit()  argument
948 	if (ll->bitmap_index_changed) {  in sm_ll_commit()
949 		r = ll->commit(ll);  in sm_ll_commit()
951 			ll->bitmap_index_changed = false;  in sm_ll_commit()
959 static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,  in metadata_ll_load_ie()  argument
962 	memcpy(ie, ll->mi_le.index + index, sizeof(*ie));  in metadata_ll_load_ie()
966 static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,  in metadata_ll_save_ie()  argument
969 	ll->bitmap_index_changed = true;  in metadata_ll_save_ie()
970 	memcpy(ll->mi_le.index + index, ie, sizeof(*ie));  in metadata_ll_save_ie()
974 static int metadata_ll_init_index(struct ll_disk *ll)  in metadata_ll_init_index()  argument
979 	r = dm_tm_new_block(ll->tm, &index_validator, &b);  in metadata_ll_init_index()
983 	ll->bitmap_root = dm_block_location(b);  in metadata_ll_init_index()
985 	dm_tm_unlock(ll->tm, b);  in metadata_ll_init_index()
990 static int metadata_ll_open(struct ll_disk *ll)  in metadata_ll_open()  argument
995 	r = dm_tm_read_lock(ll->tm, ll->bitmap_root,  in metadata_ll_open()
1000 	memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));  in metadata_ll_open()
1001 	dm_tm_unlock(ll->tm, block);  in metadata_ll_open()
1006 static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)  in metadata_ll_max_entries()  argument
1011 static int metadata_ll_commit(struct ll_disk *ll)  in metadata_ll_commit()  argument
1016 	r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);  in metadata_ll_commit()
1020 	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));  in metadata_ll_commit()
1021 	ll->bitmap_root = dm_block_location(b);  in metadata_ll_commit()
1023 	dm_tm_unlock(ll->tm, b);  in metadata_ll_commit()
1028 int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm)  in sm_ll_new_metadata()  argument
1032 	r = sm_ll_init(ll, tm);  in sm_ll_new_metadata()
1036 	ll->load_ie = metadata_ll_load_ie;  in sm_ll_new_metadata()
1037 	ll->save_ie = metadata_ll_save_ie;  in sm_ll_new_metadata()
1038 	ll->init_index = metadata_ll_init_index;  in sm_ll_new_metadata()
1039 	ll->open_index = metadata_ll_open;  in sm_ll_new_metadata()
1040 	ll->max_entries = metadata_ll_max_entries;  in sm_ll_new_metadata()
1041 	ll->commit = metadata_ll_commit;  in sm_ll_new_metadata()
1043 	ll->nr_blocks = 0;  in sm_ll_new_metadata()
1044 	ll->nr_allocated = 0;  in sm_ll_new_metadata()
1046 	r = ll->init_index(ll);  in sm_ll_new_metadata()
1050 	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);  in sm_ll_new_metadata()
1057 int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm,  in sm_ll_open_metadata()  argument
1074 	r = sm_ll_init(ll, tm);  in sm_ll_open_metadata()
1078 	ll->load_ie = metadata_ll_load_ie;  in sm_ll_open_metadata()
1079 	ll->save_ie = metadata_ll_save_ie;  in sm_ll_open_metadata()
1080 	ll->init_index = metadata_ll_init_index;  in sm_ll_open_metadata()
1081 	ll->open_index = metadata_ll_open;  in sm_ll_open_metadata()
1082 	ll->max_entries = metadata_ll_max_entries;  in sm_ll_open_metadata()
1083 	ll->commit = metadata_ll_commit;  in sm_ll_open_metadata()
1085 	ll->nr_blocks = le64_to_cpu(smr.nr_blocks);  in sm_ll_open_metadata()
1086 	ll->nr_allocated = le64_to_cpu(smr.nr_allocated);  in sm_ll_open_metadata()
1087 	ll->bitmap_root = le64_to_cpu(smr.bitmap_root);  in sm_ll_open_metadata()
1088 	ll->ref_count_root = le64_to_cpu(smr.ref_count_root);  in sm_ll_open_metadata()
1090 	return ll->open_index(ll);  in sm_ll_open_metadata()
1095 static inline int ie_cache_writeback(struct ll_disk *ll, struct ie_cache *iec)  in ie_cache_writeback()  argument
1099 	return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,  in ie_cache_writeback()
1100 			       &iec->index, &iec->ie, &ll->bitmap_root);  in ie_cache_writeback()
1108 static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,  in disk_ll_load_ie()  argument
1113 	struct ie_cache *iec = ll->ie_cache + h;  in disk_ll_load_ie()
1122 			r = ie_cache_writeback(ll, iec);  in disk_ll_load_ie()
1128 	r = dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);  in disk_ll_load_ie()
1139 static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,  in disk_ll_save_ie()  argument
1144 	struct ie_cache *iec = ll->ie_cache + h;  in disk_ll_save_ie()
1146 	ll->bitmap_index_changed = true;  in disk_ll_save_ie()
1155 			r = ie_cache_writeback(ll, iec);  in disk_ll_save_ie()
1168 static int disk_ll_init_index(struct ll_disk *ll)  in disk_ll_init_index()  argument
1173 		struct ie_cache *iec = ll->ie_cache + i;  in disk_ll_init_index()
1178 	return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);  in disk_ll_init_index()
1181 static int disk_ll_open(struct ll_disk *ll)  in disk_ll_open()  argument
1186 static dm_block_t disk_ll_max_entries(struct ll_disk *ll)  in disk_ll_max_entries()  argument
1191 static int disk_ll_commit(struct ll_disk *ll)  in disk_ll_commit()  argument
1197 		struct ie_cache *iec = ll->ie_cache + i;  in disk_ll_commit()
1200 			r = ie_cache_writeback(ll, iec);  in disk_ll_commit()
1206 int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm)  in sm_ll_new_disk()  argument
1210 	r = sm_ll_init(ll, tm);  in sm_ll_new_disk()
1214 	ll->load_ie = disk_ll_load_ie;  in sm_ll_new_disk()
1215 	ll->save_ie = disk_ll_save_ie;  in sm_ll_new_disk()
1216 	ll->init_index = disk_ll_init_index;  in sm_ll_new_disk()
1217 	ll->open_index = disk_ll_open;  in sm_ll_new_disk()
1218 	ll->max_entries = disk_ll_max_entries;  in sm_ll_new_disk()
1219 	ll->commit = disk_ll_commit;  in sm_ll_new_disk()
1221 	ll->nr_blocks = 0;  in sm_ll_new_disk()
1222 	ll->nr_allocated = 0;  in sm_ll_new_disk()
1224 	r = ll->init_index(ll);  in sm_ll_new_disk()
1228 	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);  in sm_ll_new_disk()
1235 int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm,  in sm_ll_open_disk()  argument
1246 	r = sm_ll_init(ll, tm);  in sm_ll_open_disk()
1250 	ll->load_ie = disk_ll_load_ie;  in sm_ll_open_disk()
1251 	ll->save_ie = disk_ll_save_ie;  in sm_ll_open_disk()
1252 	ll->init_index = disk_ll_init_index;  in sm_ll_open_disk()
1253 	ll->open_index = disk_ll_open;  in sm_ll_open_disk()
1254 	ll->max_entries = disk_ll_max_entries;  in sm_ll_open_disk()
1255 	ll->commit = disk_ll_commit;  in sm_ll_open_disk()
1257 	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);  in sm_ll_open_disk()
1258 	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);  in sm_ll_open_disk()
1259 	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);  in sm_ll_open_disk()
1260 	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);  in sm_ll_open_disk()
1262 	return ll->open_index(ll);  in sm_ll_open_disk()