1 /*
2  * Copyright (C) 2017 Western Digital Corporation or its affiliates.
3  *
4  * This file is released under the GPL.
5  */
6 
7 #include "dm-zoned.h"
8 
9 #include <linux/module.h>
10 #include <linux/crc32.h>
11 
12 #define	DM_MSG_PREFIX		"zoned metadata"
13 
14 /*
15  * Metadata version.
16  */
17 #define DMZ_META_VER	1
18 
19 /*
20  * On-disk super block magic.
21  */
22 #define DMZ_MAGIC	((((unsigned int)('D')) << 24) | \
23 			 (((unsigned int)('Z')) << 16) | \
24 			 (((unsigned int)('B')) <<  8) | \
25 			 ((unsigned int)('D')))
26 
27 /*
28  * On disk super block.
29  * This uses only 512 B but uses on disk a full 4KB block. This block is
30  * followed on disk by the mapping table of chunks to zones and the bitmap
31  * blocks indicating zone block validity.
32  * The overall resulting metadata format is:
33  *    (1) Super block (1 block)
34  *    (2) Chunk mapping table (nr_map_blocks)
35  *    (3) Bitmap blocks (nr_bitmap_blocks)
36  * All metadata blocks are stored in conventional zones, starting from the
37  * the first conventional zone found on disk.
38  */
39 struct dmz_super {
40 	/* Magic number */
41 	__le32		magic;			/*   4 */
42 
43 	/* Metadata version number */
44 	__le32		version;		/*   8 */
45 
46 	/* Generation number */
47 	__le64		gen;			/*  16 */
48 
49 	/* This block number */
50 	__le64		sb_block;		/*  24 */
51 
52 	/* The number of metadata blocks, including this super block */
53 	__le32		nr_meta_blocks;		/*  28 */
54 
55 	/* The number of sequential zones reserved for reclaim */
56 	__le32		nr_reserved_seq;	/*  32 */
57 
58 	/* The number of entries in the mapping table */
59 	__le32		nr_chunks;		/*  36 */
60 
61 	/* The number of blocks used for the chunk mapping table */
62 	__le32		nr_map_blocks;		/*  40 */
63 
64 	/* The number of blocks used for the block bitmaps */
65 	__le32		nr_bitmap_blocks;	/*  44 */
66 
67 	/* Checksum */
68 	__le32		crc;			/*  48 */
69 
70 	/* Padding to full 512B sector */
71 	u8		reserved[464];		/* 512 */
72 };
73 
74 /*
75  * Chunk mapping entry: entries are indexed by chunk number
76  * and give the zone ID (dzone_id) mapping the chunk on disk.
77  * This zone may be sequential or random. If it is a sequential
78  * zone, a second zone (bzone_id) used as a write buffer may
79  * also be specified. This second zone will always be a randomly
80  * writeable zone.
81  */
82 struct dmz_map {
83 	__le32			dzone_id;
84 	__le32			bzone_id;
85 };
86 
87 /*
88  * Chunk mapping table metadata: 512 8-bytes entries per 4KB block.
89  */
90 #define DMZ_MAP_ENTRIES		(DMZ_BLOCK_SIZE / sizeof(struct dmz_map))
91 #define DMZ_MAP_ENTRIES_SHIFT	(ilog2(DMZ_MAP_ENTRIES))
92 #define DMZ_MAP_ENTRIES_MASK	(DMZ_MAP_ENTRIES - 1)
93 #define DMZ_MAP_UNMAPPED	UINT_MAX
94 
95 /*
96  * Meta data block descriptor (for cached metadata blocks).
97  */
98 struct dmz_mblock {
99 	struct rb_node		node;
100 	struct list_head	link;
101 	sector_t		no;
102 	atomic_t		ref;
103 	unsigned long		state;
104 	struct page		*page;
105 	void			*data;
106 };
107 
108 /*
109  * Metadata block state flags.
110  */
111 enum {
112 	DMZ_META_DIRTY,
113 	DMZ_META_READING,
114 	DMZ_META_WRITING,
115 	DMZ_META_ERROR,
116 };
117 
118 /*
119  * Super block information (one per metadata set).
120  */
121 struct dmz_sb {
122 	sector_t		block;
123 	struct dmz_mblock	*mblk;
124 	struct dmz_super	*sb;
125 };
126 
127 /*
128  * In-memory metadata.
129  */
130 struct dmz_metadata {
131 	struct dmz_dev		*dev;
132 
133 	sector_t		zone_bitmap_size;
134 	unsigned int		zone_nr_bitmap_blocks;
135 
136 	unsigned int		nr_bitmap_blocks;
137 	unsigned int		nr_map_blocks;
138 
139 	unsigned int		nr_useable_zones;
140 	unsigned int		nr_meta_blocks;
141 	unsigned int		nr_meta_zones;
142 	unsigned int		nr_data_zones;
143 	unsigned int		nr_rnd_zones;
144 	unsigned int		nr_reserved_seq;
145 	unsigned int		nr_chunks;
146 
147 	/* Zone information array */
148 	struct dm_zone		*zones;
149 
150 	struct dm_zone		*sb_zone;
151 	struct dmz_sb		sb[2];
152 	unsigned int		mblk_primary;
153 	u64			sb_gen;
154 	unsigned int		min_nr_mblks;
155 	unsigned int		max_nr_mblks;
156 	atomic_t		nr_mblks;
157 	struct rw_semaphore	mblk_sem;
158 	struct mutex		mblk_flush_lock;
159 	spinlock_t		mblk_lock;
160 	struct rb_root		mblk_rbtree;
161 	struct list_head	mblk_lru_list;
162 	struct list_head	mblk_dirty_list;
163 	struct shrinker		mblk_shrinker;
164 
165 	/* Zone allocation management */
166 	struct mutex		map_lock;
167 	struct dmz_mblock	**map_mblk;
168 	unsigned int		nr_rnd;
169 	atomic_t		unmap_nr_rnd;
170 	struct list_head	unmap_rnd_list;
171 	struct list_head	map_rnd_list;
172 
173 	unsigned int		nr_seq;
174 	atomic_t		unmap_nr_seq;
175 	struct list_head	unmap_seq_list;
176 	struct list_head	map_seq_list;
177 
178 	atomic_t		nr_reserved_seq_zones;
179 	struct list_head	reserved_seq_zones_list;
180 
181 	wait_queue_head_t	free_wq;
182 };
183 
184 /*
185  * Various accessors
186  */
187 unsigned int dmz_id(struct dmz_metadata *zmd, struct dm_zone *zone)
188 {
189 	return ((unsigned int)(zone - zmd->zones));
190 }
191 
192 sector_t dmz_start_sect(struct dmz_metadata *zmd, struct dm_zone *zone)
193 {
194 	return (sector_t)dmz_id(zmd, zone) << zmd->dev->zone_nr_sectors_shift;
195 }
196 
197 sector_t dmz_start_block(struct dmz_metadata *zmd, struct dm_zone *zone)
198 {
199 	return (sector_t)dmz_id(zmd, zone) << zmd->dev->zone_nr_blocks_shift;
200 }
201 
202 unsigned int dmz_nr_chunks(struct dmz_metadata *zmd)
203 {
204 	return zmd->nr_chunks;
205 }
206 
207 unsigned int dmz_nr_rnd_zones(struct dmz_metadata *zmd)
208 {
209 	return zmd->nr_rnd;
210 }
211 
212 unsigned int dmz_nr_unmap_rnd_zones(struct dmz_metadata *zmd)
213 {
214 	return atomic_read(&zmd->unmap_nr_rnd);
215 }
216 
217 /*
218  * Lock/unlock mapping table.
219  * The map lock also protects all the zone lists.
220  */
221 void dmz_lock_map(struct dmz_metadata *zmd)
222 {
223 	mutex_lock(&zmd->map_lock);
224 }
225 
226 void dmz_unlock_map(struct dmz_metadata *zmd)
227 {
228 	mutex_unlock(&zmd->map_lock);
229 }
230 
231 /*
232  * Lock/unlock metadata access. This is a "read" lock on a semaphore
233  * that prevents metadata flush from running while metadata are being
234  * modified. The actual metadata write mutual exclusion is achieved with
235  * the map lock and zone styate management (active and reclaim state are
236  * mutually exclusive).
237  */
238 void dmz_lock_metadata(struct dmz_metadata *zmd)
239 {
240 	down_read(&zmd->mblk_sem);
241 }
242 
243 void dmz_unlock_metadata(struct dmz_metadata *zmd)
244 {
245 	up_read(&zmd->mblk_sem);
246 }
247 
248 /*
249  * Lock/unlock flush: prevent concurrent executions
250  * of dmz_flush_metadata as well as metadata modification in reclaim
251  * while flush is being executed.
252  */
253 void dmz_lock_flush(struct dmz_metadata *zmd)
254 {
255 	mutex_lock(&zmd->mblk_flush_lock);
256 }
257 
258 void dmz_unlock_flush(struct dmz_metadata *zmd)
259 {
260 	mutex_unlock(&zmd->mblk_flush_lock);
261 }
262 
263 /*
264  * Allocate a metadata block.
265  */
266 static struct dmz_mblock *dmz_alloc_mblock(struct dmz_metadata *zmd,
267 					   sector_t mblk_no)
268 {
269 	struct dmz_mblock *mblk = NULL;
270 
271 	/* See if we can reuse cached blocks */
272 	if (zmd->max_nr_mblks && atomic_read(&zmd->nr_mblks) > zmd->max_nr_mblks) {
273 		spin_lock(&zmd->mblk_lock);
274 		mblk = list_first_entry_or_null(&zmd->mblk_lru_list,
275 						struct dmz_mblock, link);
276 		if (mblk) {
277 			list_del_init(&mblk->link);
278 			rb_erase(&mblk->node, &zmd->mblk_rbtree);
279 			mblk->no = mblk_no;
280 		}
281 		spin_unlock(&zmd->mblk_lock);
282 		if (mblk)
283 			return mblk;
284 	}
285 
286 	/* Allocate a new block */
287 	mblk = kmalloc(sizeof(struct dmz_mblock), GFP_NOIO);
288 	if (!mblk)
289 		return NULL;
290 
291 	mblk->page = alloc_page(GFP_NOIO);
292 	if (!mblk->page) {
293 		kfree(mblk);
294 		return NULL;
295 	}
296 
297 	RB_CLEAR_NODE(&mblk->node);
298 	INIT_LIST_HEAD(&mblk->link);
299 	atomic_set(&mblk->ref, 0);
300 	mblk->state = 0;
301 	mblk->no = mblk_no;
302 	mblk->data = page_address(mblk->page);
303 
304 	atomic_inc(&zmd->nr_mblks);
305 
306 	return mblk;
307 }
308 
309 /*
310  * Free a metadata block.
311  */
312 static void dmz_free_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk)
313 {
314 	__free_pages(mblk->page, 0);
315 	kfree(mblk);
316 
317 	atomic_dec(&zmd->nr_mblks);
318 }
319 
320 /*
321  * Insert a metadata block in the rbtree.
322  */
323 static void dmz_insert_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk)
324 {
325 	struct rb_root *root = &zmd->mblk_rbtree;
326 	struct rb_node **new = &(root->rb_node), *parent = NULL;
327 	struct dmz_mblock *b;
328 
329 	/* Figure out where to put the new node */
330 	while (*new) {
331 		b = container_of(*new, struct dmz_mblock, node);
332 		parent = *new;
333 		new = (b->no < mblk->no) ? &((*new)->rb_left) : &((*new)->rb_right);
334 	}
335 
336 	/* Add new node and rebalance tree */
337 	rb_link_node(&mblk->node, parent, new);
338 	rb_insert_color(&mblk->node, root);
339 }
340 
341 /*
342  * Lookup a metadata block in the rbtree.
343  */
344 static struct dmz_mblock *dmz_lookup_mblock(struct dmz_metadata *zmd,
345 					    sector_t mblk_no)
346 {
347 	struct rb_root *root = &zmd->mblk_rbtree;
348 	struct rb_node *node = root->rb_node;
349 	struct dmz_mblock *mblk;
350 
351 	while (node) {
352 		mblk = container_of(node, struct dmz_mblock, node);
353 		if (mblk->no == mblk_no)
354 			return mblk;
355 		node = (mblk->no < mblk_no) ? node->rb_left : node->rb_right;
356 	}
357 
358 	return NULL;
359 }
360 
361 /*
362  * Metadata block BIO end callback.
363  */
364 static void dmz_mblock_bio_end_io(struct bio *bio)
365 {
366 	struct dmz_mblock *mblk = bio->bi_private;
367 	int flag;
368 
369 	if (bio->bi_status)
370 		set_bit(DMZ_META_ERROR, &mblk->state);
371 
372 	if (bio_op(bio) == REQ_OP_WRITE)
373 		flag = DMZ_META_WRITING;
374 	else
375 		flag = DMZ_META_READING;
376 
377 	clear_bit_unlock(flag, &mblk->state);
378 	smp_mb__after_atomic();
379 	wake_up_bit(&mblk->state, flag);
380 
381 	bio_put(bio);
382 }
383 
384 /*
385  * Read a metadata block from disk.
386  */
387 static struct dmz_mblock *dmz_fetch_mblock(struct dmz_metadata *zmd,
388 					   sector_t mblk_no)
389 {
390 	struct dmz_mblock *mblk;
391 	sector_t block = zmd->sb[zmd->mblk_primary].block + mblk_no;
392 	struct bio *bio;
393 
394 	/* Get block and insert it */
395 	mblk = dmz_alloc_mblock(zmd, mblk_no);
396 	if (!mblk)
397 		return NULL;
398 
399 	spin_lock(&zmd->mblk_lock);
400 	atomic_inc(&mblk->ref);
401 	set_bit(DMZ_META_READING, &mblk->state);
402 	dmz_insert_mblock(zmd, mblk);
403 	spin_unlock(&zmd->mblk_lock);
404 
405 	bio = bio_alloc(GFP_NOIO, 1);
406 	if (!bio) {
407 		dmz_free_mblock(zmd, mblk);
408 		return NULL;
409 	}
410 
411 	bio->bi_iter.bi_sector = dmz_blk2sect(block);
412 	bio_set_dev(bio, zmd->dev->bdev);
413 	bio->bi_private = mblk;
414 	bio->bi_end_io = dmz_mblock_bio_end_io;
415 	bio_set_op_attrs(bio, REQ_OP_READ, REQ_META | REQ_PRIO);
416 	bio_add_page(bio, mblk->page, DMZ_BLOCK_SIZE, 0);
417 	submit_bio(bio);
418 
419 	return mblk;
420 }
421 
422 /*
423  * Free metadata blocks.
424  */
425 static unsigned long dmz_shrink_mblock_cache(struct dmz_metadata *zmd,
426 					     unsigned long limit)
427 {
428 	struct dmz_mblock *mblk;
429 	unsigned long count = 0;
430 
431 	if (!zmd->max_nr_mblks)
432 		return 0;
433 
434 	while (!list_empty(&zmd->mblk_lru_list) &&
435 	       atomic_read(&zmd->nr_mblks) > zmd->min_nr_mblks &&
436 	       count < limit) {
437 		mblk = list_first_entry(&zmd->mblk_lru_list,
438 					struct dmz_mblock, link);
439 		list_del_init(&mblk->link);
440 		rb_erase(&mblk->node, &zmd->mblk_rbtree);
441 		dmz_free_mblock(zmd, mblk);
442 		count++;
443 	}
444 
445 	return count;
446 }
447 
448 /*
449  * For mblock shrinker: get the number of unused metadata blocks in the cache.
450  */
451 static unsigned long dmz_mblock_shrinker_count(struct shrinker *shrink,
452 					       struct shrink_control *sc)
453 {
454 	struct dmz_metadata *zmd = container_of(shrink, struct dmz_metadata, mblk_shrinker);
455 
456 	return atomic_read(&zmd->nr_mblks);
457 }
458 
459 /*
460  * For mblock shrinker: scan unused metadata blocks and shrink the cache.
461  */
462 static unsigned long dmz_mblock_shrinker_scan(struct shrinker *shrink,
463 					      struct shrink_control *sc)
464 {
465 	struct dmz_metadata *zmd = container_of(shrink, struct dmz_metadata, mblk_shrinker);
466 	unsigned long count;
467 
468 	spin_lock(&zmd->mblk_lock);
469 	count = dmz_shrink_mblock_cache(zmd, sc->nr_to_scan);
470 	spin_unlock(&zmd->mblk_lock);
471 
472 	return count ? count : SHRINK_STOP;
473 }
474 
475 /*
476  * Release a metadata block.
477  */
478 static void dmz_release_mblock(struct dmz_metadata *zmd,
479 			       struct dmz_mblock *mblk)
480 {
481 
482 	if (!mblk)
483 		return;
484 
485 	spin_lock(&zmd->mblk_lock);
486 
487 	if (atomic_dec_and_test(&mblk->ref)) {
488 		if (test_bit(DMZ_META_ERROR, &mblk->state)) {
489 			rb_erase(&mblk->node, &zmd->mblk_rbtree);
490 			dmz_free_mblock(zmd, mblk);
491 		} else if (!test_bit(DMZ_META_DIRTY, &mblk->state)) {
492 			list_add_tail(&mblk->link, &zmd->mblk_lru_list);
493 			dmz_shrink_mblock_cache(zmd, 1);
494 		}
495 	}
496 
497 	spin_unlock(&zmd->mblk_lock);
498 }
499 
500 /*
501  * Get a metadata block from the rbtree. If the block
502  * is not present, read it from disk.
503  */
504 static struct dmz_mblock *dmz_get_mblock(struct dmz_metadata *zmd,
505 					 sector_t mblk_no)
506 {
507 	struct dmz_mblock *mblk;
508 
509 	/* Check rbtree */
510 	spin_lock(&zmd->mblk_lock);
511 	mblk = dmz_lookup_mblock(zmd, mblk_no);
512 	if (mblk) {
513 		/* Cache hit: remove block from LRU list */
514 		if (atomic_inc_return(&mblk->ref) == 1 &&
515 		    !test_bit(DMZ_META_DIRTY, &mblk->state))
516 			list_del_init(&mblk->link);
517 	}
518 	spin_unlock(&zmd->mblk_lock);
519 
520 	if (!mblk) {
521 		/* Cache miss: read the block from disk */
522 		mblk = dmz_fetch_mblock(zmd, mblk_no);
523 		if (!mblk)
524 			return ERR_PTR(-ENOMEM);
525 	}
526 
527 	/* Wait for on-going read I/O and check for error */
528 	wait_on_bit_io(&mblk->state, DMZ_META_READING,
529 		       TASK_UNINTERRUPTIBLE);
530 	if (test_bit(DMZ_META_ERROR, &mblk->state)) {
531 		dmz_release_mblock(zmd, mblk);
532 		return ERR_PTR(-EIO);
533 	}
534 
535 	return mblk;
536 }
537 
538 /*
539  * Mark a metadata block dirty.
540  */
541 static void dmz_dirty_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk)
542 {
543 	spin_lock(&zmd->mblk_lock);
544 	if (!test_and_set_bit(DMZ_META_DIRTY, &mblk->state))
545 		list_add_tail(&mblk->link, &zmd->mblk_dirty_list);
546 	spin_unlock(&zmd->mblk_lock);
547 }
548 
549 /*
550  * Issue a metadata block write BIO.
551  */
552 static void dmz_write_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk,
553 			     unsigned int set)
554 {
555 	sector_t block = zmd->sb[set].block + mblk->no;
556 	struct bio *bio;
557 
558 	bio = bio_alloc(GFP_NOIO, 1);
559 	if (!bio) {
560 		set_bit(DMZ_META_ERROR, &mblk->state);
561 		return;
562 	}
563 
564 	set_bit(DMZ_META_WRITING, &mblk->state);
565 
566 	bio->bi_iter.bi_sector = dmz_blk2sect(block);
567 	bio_set_dev(bio, zmd->dev->bdev);
568 	bio->bi_private = mblk;
569 	bio->bi_end_io = dmz_mblock_bio_end_io;
570 	bio_set_op_attrs(bio, REQ_OP_WRITE, REQ_META | REQ_PRIO);
571 	bio_add_page(bio, mblk->page, DMZ_BLOCK_SIZE, 0);
572 	submit_bio(bio);
573 }
574 
575 /*
576  * Read/write a metadata block.
577  */
578 static int dmz_rdwr_block(struct dmz_metadata *zmd, int op, sector_t block,
579 			  struct page *page)
580 {
581 	struct bio *bio;
582 	int ret;
583 
584 	bio = bio_alloc(GFP_NOIO, 1);
585 	if (!bio)
586 		return -ENOMEM;
587 
588 	bio->bi_iter.bi_sector = dmz_blk2sect(block);
589 	bio_set_dev(bio, zmd->dev->bdev);
590 	bio_set_op_attrs(bio, op, REQ_SYNC | REQ_META | REQ_PRIO);
591 	bio_add_page(bio, page, DMZ_BLOCK_SIZE, 0);
592 	ret = submit_bio_wait(bio);
593 	bio_put(bio);
594 
595 	return ret;
596 }
597 
598 /*
599  * Write super block of the specified metadata set.
600  */
601 static int dmz_write_sb(struct dmz_metadata *zmd, unsigned int set)
602 {
603 	sector_t block = zmd->sb[set].block;
604 	struct dmz_mblock *mblk = zmd->sb[set].mblk;
605 	struct dmz_super *sb = zmd->sb[set].sb;
606 	u64 sb_gen = zmd->sb_gen + 1;
607 	int ret;
608 
609 	sb->magic = cpu_to_le32(DMZ_MAGIC);
610 	sb->version = cpu_to_le32(DMZ_META_VER);
611 
612 	sb->gen = cpu_to_le64(sb_gen);
613 
614 	sb->sb_block = cpu_to_le64(block);
615 	sb->nr_meta_blocks = cpu_to_le32(zmd->nr_meta_blocks);
616 	sb->nr_reserved_seq = cpu_to_le32(zmd->nr_reserved_seq);
617 	sb->nr_chunks = cpu_to_le32(zmd->nr_chunks);
618 
619 	sb->nr_map_blocks = cpu_to_le32(zmd->nr_map_blocks);
620 	sb->nr_bitmap_blocks = cpu_to_le32(zmd->nr_bitmap_blocks);
621 
622 	sb->crc = 0;
623 	sb->crc = cpu_to_le32(crc32_le(sb_gen, (unsigned char *)sb, DMZ_BLOCK_SIZE));
624 
625 	ret = dmz_rdwr_block(zmd, REQ_OP_WRITE, block, mblk->page);
626 	if (ret == 0)
627 		ret = blkdev_issue_flush(zmd->dev->bdev, GFP_NOIO, NULL);
628 
629 	return ret;
630 }
631 
632 /*
633  * Write dirty metadata blocks to the specified set.
634  */
635 static int dmz_write_dirty_mblocks(struct dmz_metadata *zmd,
636 				   struct list_head *write_list,
637 				   unsigned int set)
638 {
639 	struct dmz_mblock *mblk;
640 	struct blk_plug plug;
641 	int ret = 0;
642 
643 	/* Issue writes */
644 	blk_start_plug(&plug);
645 	list_for_each_entry(mblk, write_list, link)
646 		dmz_write_mblock(zmd, mblk, set);
647 	blk_finish_plug(&plug);
648 
649 	/* Wait for completion */
650 	list_for_each_entry(mblk, write_list, link) {
651 		wait_on_bit_io(&mblk->state, DMZ_META_WRITING,
652 			       TASK_UNINTERRUPTIBLE);
653 		if (test_bit(DMZ_META_ERROR, &mblk->state)) {
654 			clear_bit(DMZ_META_ERROR, &mblk->state);
655 			ret = -EIO;
656 		}
657 	}
658 
659 	/* Flush drive cache (this will also sync data) */
660 	if (ret == 0)
661 		ret = blkdev_issue_flush(zmd->dev->bdev, GFP_NOIO, NULL);
662 
663 	return ret;
664 }
665 
666 /*
667  * Log dirty metadata blocks.
668  */
669 static int dmz_log_dirty_mblocks(struct dmz_metadata *zmd,
670 				 struct list_head *write_list)
671 {
672 	unsigned int log_set = zmd->mblk_primary ^ 0x1;
673 	int ret;
674 
675 	/* Write dirty blocks to the log */
676 	ret = dmz_write_dirty_mblocks(zmd, write_list, log_set);
677 	if (ret)
678 		return ret;
679 
680 	/*
681 	 * No error so far: now validate the log by updating the
682 	 * log index super block generation.
683 	 */
684 	ret = dmz_write_sb(zmd, log_set);
685 	if (ret)
686 		return ret;
687 
688 	return 0;
689 }
690 
691 /*
692  * Flush dirty metadata blocks.
693  */
694 int dmz_flush_metadata(struct dmz_metadata *zmd)
695 {
696 	struct dmz_mblock *mblk;
697 	struct list_head write_list;
698 	int ret;
699 
700 	if (WARN_ON(!zmd))
701 		return 0;
702 
703 	INIT_LIST_HEAD(&write_list);
704 
705 	/*
706 	 * Make sure that metadata blocks are stable before logging: take
707 	 * the write lock on the metadata semaphore to prevent target BIOs
708 	 * from modifying metadata.
709 	 */
710 	down_write(&zmd->mblk_sem);
711 
712 	/*
713 	 * This is called from the target flush work and reclaim work.
714 	 * Concurrent execution is not allowed.
715 	 */
716 	dmz_lock_flush(zmd);
717 
718 	/* Get dirty blocks */
719 	spin_lock(&zmd->mblk_lock);
720 	list_splice_init(&zmd->mblk_dirty_list, &write_list);
721 	spin_unlock(&zmd->mblk_lock);
722 
723 	/* If there are no dirty metadata blocks, just flush the device cache */
724 	if (list_empty(&write_list)) {
725 		ret = blkdev_issue_flush(zmd->dev->bdev, GFP_NOIO, NULL);
726 		goto out;
727 	}
728 
729 	/*
730 	 * The primary metadata set is still clean. Keep it this way until
731 	 * all updates are successful in the secondary set. That is, use
732 	 * the secondary set as a log.
733 	 */
734 	ret = dmz_log_dirty_mblocks(zmd, &write_list);
735 	if (ret)
736 		goto out;
737 
738 	/*
739 	 * The log is on disk. It is now safe to update in place
740 	 * in the primary metadata set.
741 	 */
742 	ret = dmz_write_dirty_mblocks(zmd, &write_list, zmd->mblk_primary);
743 	if (ret)
744 		goto out;
745 
746 	ret = dmz_write_sb(zmd, zmd->mblk_primary);
747 	if (ret)
748 		goto out;
749 
750 	while (!list_empty(&write_list)) {
751 		mblk = list_first_entry(&write_list, struct dmz_mblock, link);
752 		list_del_init(&mblk->link);
753 
754 		spin_lock(&zmd->mblk_lock);
755 		clear_bit(DMZ_META_DIRTY, &mblk->state);
756 		if (atomic_read(&mblk->ref) == 0)
757 			list_add_tail(&mblk->link, &zmd->mblk_lru_list);
758 		spin_unlock(&zmd->mblk_lock);
759 	}
760 
761 	zmd->sb_gen++;
762 out:
763 	if (ret && !list_empty(&write_list)) {
764 		spin_lock(&zmd->mblk_lock);
765 		list_splice(&write_list, &zmd->mblk_dirty_list);
766 		spin_unlock(&zmd->mblk_lock);
767 	}
768 
769 	dmz_unlock_flush(zmd);
770 	up_write(&zmd->mblk_sem);
771 
772 	return ret;
773 }
774 
775 /*
776  * Check super block.
777  */
778 static int dmz_check_sb(struct dmz_metadata *zmd, struct dmz_super *sb)
779 {
780 	unsigned int nr_meta_zones, nr_data_zones;
781 	struct dmz_dev *dev = zmd->dev;
782 	u32 crc, stored_crc;
783 	u64 gen;
784 
785 	gen = le64_to_cpu(sb->gen);
786 	stored_crc = le32_to_cpu(sb->crc);
787 	sb->crc = 0;
788 	crc = crc32_le(gen, (unsigned char *)sb, DMZ_BLOCK_SIZE);
789 	if (crc != stored_crc) {
790 		dmz_dev_err(dev, "Invalid checksum (needed 0x%08x, got 0x%08x)",
791 			    crc, stored_crc);
792 		return -ENXIO;
793 	}
794 
795 	if (le32_to_cpu(sb->magic) != DMZ_MAGIC) {
796 		dmz_dev_err(dev, "Invalid meta magic (needed 0x%08x, got 0x%08x)",
797 			    DMZ_MAGIC, le32_to_cpu(sb->magic));
798 		return -ENXIO;
799 	}
800 
801 	if (le32_to_cpu(sb->version) != DMZ_META_VER) {
802 		dmz_dev_err(dev, "Invalid meta version (needed %d, got %d)",
803 			    DMZ_META_VER, le32_to_cpu(sb->version));
804 		return -ENXIO;
805 	}
806 
807 	nr_meta_zones = (le32_to_cpu(sb->nr_meta_blocks) + dev->zone_nr_blocks - 1)
808 		>> dev->zone_nr_blocks_shift;
809 	if (!nr_meta_zones ||
810 	    nr_meta_zones >= zmd->nr_rnd_zones) {
811 		dmz_dev_err(dev, "Invalid number of metadata blocks");
812 		return -ENXIO;
813 	}
814 
815 	if (!le32_to_cpu(sb->nr_reserved_seq) ||
816 	    le32_to_cpu(sb->nr_reserved_seq) >= (zmd->nr_useable_zones - nr_meta_zones)) {
817 		dmz_dev_err(dev, "Invalid number of reserved sequential zones");
818 		return -ENXIO;
819 	}
820 
821 	nr_data_zones = zmd->nr_useable_zones -
822 		(nr_meta_zones * 2 + le32_to_cpu(sb->nr_reserved_seq));
823 	if (le32_to_cpu(sb->nr_chunks) > nr_data_zones) {
824 		dmz_dev_err(dev, "Invalid number of chunks %u / %u",
825 			    le32_to_cpu(sb->nr_chunks), nr_data_zones);
826 		return -ENXIO;
827 	}
828 
829 	/* OK */
830 	zmd->nr_meta_blocks = le32_to_cpu(sb->nr_meta_blocks);
831 	zmd->nr_reserved_seq = le32_to_cpu(sb->nr_reserved_seq);
832 	zmd->nr_chunks = le32_to_cpu(sb->nr_chunks);
833 	zmd->nr_map_blocks = le32_to_cpu(sb->nr_map_blocks);
834 	zmd->nr_bitmap_blocks = le32_to_cpu(sb->nr_bitmap_blocks);
835 	zmd->nr_meta_zones = nr_meta_zones;
836 	zmd->nr_data_zones = nr_data_zones;
837 
838 	return 0;
839 }
840 
841 /*
842  * Read the first or second super block from disk.
843  */
844 static int dmz_read_sb(struct dmz_metadata *zmd, unsigned int set)
845 {
846 	return dmz_rdwr_block(zmd, REQ_OP_READ, zmd->sb[set].block,
847 			      zmd->sb[set].mblk->page);
848 }
849 
850 /*
851  * Determine the position of the secondary super blocks on disk.
852  * This is used only if a corruption of the primary super block
853  * is detected.
854  */
855 static int dmz_lookup_secondary_sb(struct dmz_metadata *zmd)
856 {
857 	unsigned int zone_nr_blocks = zmd->dev->zone_nr_blocks;
858 	struct dmz_mblock *mblk;
859 	int i;
860 
861 	/* Allocate a block */
862 	mblk = dmz_alloc_mblock(zmd, 0);
863 	if (!mblk)
864 		return -ENOMEM;
865 
866 	zmd->sb[1].mblk = mblk;
867 	zmd->sb[1].sb = mblk->data;
868 
869 	/* Bad first super block: search for the second one */
870 	zmd->sb[1].block = zmd->sb[0].block + zone_nr_blocks;
871 	for (i = 0; i < zmd->nr_rnd_zones - 1; i++) {
872 		if (dmz_read_sb(zmd, 1) != 0)
873 			break;
874 		if (le32_to_cpu(zmd->sb[1].sb->magic) == DMZ_MAGIC)
875 			return 0;
876 		zmd->sb[1].block += zone_nr_blocks;
877 	}
878 
879 	dmz_free_mblock(zmd, mblk);
880 	zmd->sb[1].mblk = NULL;
881 
882 	return -EIO;
883 }
884 
885 /*
886  * Read the first or second super block from disk.
887  */
888 static int dmz_get_sb(struct dmz_metadata *zmd, unsigned int set)
889 {
890 	struct dmz_mblock *mblk;
891 	int ret;
892 
893 	/* Allocate a block */
894 	mblk = dmz_alloc_mblock(zmd, 0);
895 	if (!mblk)
896 		return -ENOMEM;
897 
898 	zmd->sb[set].mblk = mblk;
899 	zmd->sb[set].sb = mblk->data;
900 
901 	/* Read super block */
902 	ret = dmz_read_sb(zmd, set);
903 	if (ret) {
904 		dmz_free_mblock(zmd, mblk);
905 		zmd->sb[set].mblk = NULL;
906 		return ret;
907 	}
908 
909 	return 0;
910 }
911 
912 /*
913  * Recover a metadata set.
914  */
915 static int dmz_recover_mblocks(struct dmz_metadata *zmd, unsigned int dst_set)
916 {
917 	unsigned int src_set = dst_set ^ 0x1;
918 	struct page *page;
919 	int i, ret;
920 
921 	dmz_dev_warn(zmd->dev, "Metadata set %u invalid: recovering", dst_set);
922 
923 	if (dst_set == 0)
924 		zmd->sb[0].block = dmz_start_block(zmd, zmd->sb_zone);
925 	else {
926 		zmd->sb[1].block = zmd->sb[0].block +
927 			(zmd->nr_meta_zones << zmd->dev->zone_nr_blocks_shift);
928 	}
929 
930 	page = alloc_page(GFP_NOIO);
931 	if (!page)
932 		return -ENOMEM;
933 
934 	/* Copy metadata blocks */
935 	for (i = 1; i < zmd->nr_meta_blocks; i++) {
936 		ret = dmz_rdwr_block(zmd, REQ_OP_READ,
937 				     zmd->sb[src_set].block + i, page);
938 		if (ret)
939 			goto out;
940 		ret = dmz_rdwr_block(zmd, REQ_OP_WRITE,
941 				     zmd->sb[dst_set].block + i, page);
942 		if (ret)
943 			goto out;
944 	}
945 
946 	/* Finalize with the super block */
947 	if (!zmd->sb[dst_set].mblk) {
948 		zmd->sb[dst_set].mblk = dmz_alloc_mblock(zmd, 0);
949 		if (!zmd->sb[dst_set].mblk) {
950 			ret = -ENOMEM;
951 			goto out;
952 		}
953 		zmd->sb[dst_set].sb = zmd->sb[dst_set].mblk->data;
954 	}
955 
956 	ret = dmz_write_sb(zmd, dst_set);
957 out:
958 	__free_pages(page, 0);
959 
960 	return ret;
961 }
962 
963 /*
964  * Get super block from disk.
965  */
966 static int dmz_load_sb(struct dmz_metadata *zmd)
967 {
968 	bool sb_good[2] = {false, false};
969 	u64 sb_gen[2] = {0, 0};
970 	int ret;
971 
972 	/* Read and check the primary super block */
973 	zmd->sb[0].block = dmz_start_block(zmd, zmd->sb_zone);
974 	ret = dmz_get_sb(zmd, 0);
975 	if (ret) {
976 		dmz_dev_err(zmd->dev, "Read primary super block failed");
977 		return ret;
978 	}
979 
980 	ret = dmz_check_sb(zmd, zmd->sb[0].sb);
981 
982 	/* Read and check secondary super block */
983 	if (ret == 0) {
984 		sb_good[0] = true;
985 		zmd->sb[1].block = zmd->sb[0].block +
986 			(zmd->nr_meta_zones << zmd->dev->zone_nr_blocks_shift);
987 		ret = dmz_get_sb(zmd, 1);
988 	} else
989 		ret = dmz_lookup_secondary_sb(zmd);
990 
991 	if (ret) {
992 		dmz_dev_err(zmd->dev, "Read secondary super block failed");
993 		return ret;
994 	}
995 
996 	ret = dmz_check_sb(zmd, zmd->sb[1].sb);
997 	if (ret == 0)
998 		sb_good[1] = true;
999 
1000 	/* Use highest generation sb first */
1001 	if (!sb_good[0] && !sb_good[1]) {
1002 		dmz_dev_err(zmd->dev, "No valid super block found");
1003 		return -EIO;
1004 	}
1005 
1006 	if (sb_good[0])
1007 		sb_gen[0] = le64_to_cpu(zmd->sb[0].sb->gen);
1008 	else
1009 		ret = dmz_recover_mblocks(zmd, 0);
1010 
1011 	if (sb_good[1])
1012 		sb_gen[1] = le64_to_cpu(zmd->sb[1].sb->gen);
1013 	else
1014 		ret = dmz_recover_mblocks(zmd, 1);
1015 
1016 	if (ret) {
1017 		dmz_dev_err(zmd->dev, "Recovery failed");
1018 		return -EIO;
1019 	}
1020 
1021 	if (sb_gen[0] >= sb_gen[1]) {
1022 		zmd->sb_gen = sb_gen[0];
1023 		zmd->mblk_primary = 0;
1024 	} else {
1025 		zmd->sb_gen = sb_gen[1];
1026 		zmd->mblk_primary = 1;
1027 	}
1028 
1029 	dmz_dev_debug(zmd->dev, "Using super block %u (gen %llu)",
1030 		      zmd->mblk_primary, zmd->sb_gen);
1031 
1032 	return 0;
1033 }
1034 
1035 /*
1036  * Initialize a zone descriptor.
1037  */
1038 static int dmz_init_zone(struct dmz_metadata *zmd, struct dm_zone *zone,
1039 			 struct blk_zone *blkz)
1040 {
1041 	struct dmz_dev *dev = zmd->dev;
1042 
1043 	/* Ignore the eventual last runt (smaller) zone */
1044 	if (blkz->len != dev->zone_nr_sectors) {
1045 		if (blkz->start + blkz->len == dev->capacity)
1046 			return 0;
1047 		return -ENXIO;
1048 	}
1049 
1050 	INIT_LIST_HEAD(&zone->link);
1051 	atomic_set(&zone->refcount, 0);
1052 	zone->chunk = DMZ_MAP_UNMAPPED;
1053 
1054 	if (blkz->type == BLK_ZONE_TYPE_CONVENTIONAL) {
1055 		set_bit(DMZ_RND, &zone->flags);
1056 		zmd->nr_rnd_zones++;
1057 	} else if (blkz->type == BLK_ZONE_TYPE_SEQWRITE_REQ ||
1058 		   blkz->type == BLK_ZONE_TYPE_SEQWRITE_PREF) {
1059 		set_bit(DMZ_SEQ, &zone->flags);
1060 	} else
1061 		return -ENXIO;
1062 
1063 	if (blkz->cond == BLK_ZONE_COND_OFFLINE)
1064 		set_bit(DMZ_OFFLINE, &zone->flags);
1065 	else if (blkz->cond == BLK_ZONE_COND_READONLY)
1066 		set_bit(DMZ_READ_ONLY, &zone->flags);
1067 
1068 	if (dmz_is_rnd(zone))
1069 		zone->wp_block = 0;
1070 	else
1071 		zone->wp_block = dmz_sect2blk(blkz->wp - blkz->start);
1072 
1073 	if (!dmz_is_offline(zone) && !dmz_is_readonly(zone)) {
1074 		zmd->nr_useable_zones++;
1075 		if (dmz_is_rnd(zone)) {
1076 			zmd->nr_rnd_zones++;
1077 			if (!zmd->sb_zone) {
1078 				/* Super block zone */
1079 				zmd->sb_zone = zone;
1080 			}
1081 		}
1082 	}
1083 
1084 	return 0;
1085 }
1086 
1087 /*
1088  * Free zones descriptors.
1089  */
1090 static void dmz_drop_zones(struct dmz_metadata *zmd)
1091 {
1092 	kfree(zmd->zones);
1093 	zmd->zones = NULL;
1094 }
1095 
1096 /*
1097  * The size of a zone report in number of zones.
1098  * This results in 4096*64B=256KB report zones commands.
1099  */
1100 #define DMZ_REPORT_NR_ZONES	4096
1101 
1102 /*
1103  * Allocate and initialize zone descriptors using the zone
1104  * information from disk.
1105  */
1106 static int dmz_init_zones(struct dmz_metadata *zmd)
1107 {
1108 	struct dmz_dev *dev = zmd->dev;
1109 	struct dm_zone *zone;
1110 	struct blk_zone *blkz;
1111 	unsigned int nr_blkz;
1112 	sector_t sector = 0;
1113 	int i, ret = 0;
1114 
1115 	/* Init */
1116 	zmd->zone_bitmap_size = dev->zone_nr_blocks >> 3;
1117 	zmd->zone_nr_bitmap_blocks = zmd->zone_bitmap_size >> DMZ_BLOCK_SHIFT;
1118 
1119 	/* Allocate zone array */
1120 	zmd->zones = kcalloc(dev->nr_zones, sizeof(struct dm_zone), GFP_KERNEL);
1121 	if (!zmd->zones)
1122 		return -ENOMEM;
1123 
1124 	dmz_dev_info(dev, "Using %zu B for zone information",
1125 		     sizeof(struct dm_zone) * dev->nr_zones);
1126 
1127 	/* Get zone information */
1128 	nr_blkz = DMZ_REPORT_NR_ZONES;
1129 	blkz = kcalloc(nr_blkz, sizeof(struct blk_zone), GFP_KERNEL);
1130 	if (!blkz) {
1131 		ret = -ENOMEM;
1132 		goto out;
1133 	}
1134 
1135 	/*
1136 	 * Get zone information and initialize zone descriptors.
1137 	 * At the same time, determine where the super block
1138 	 * should be: first block of the first randomly writable
1139 	 * zone.
1140 	 */
1141 	zone = zmd->zones;
1142 	while (sector < dev->capacity) {
1143 		/* Get zone information */
1144 		nr_blkz = DMZ_REPORT_NR_ZONES;
1145 		ret = blkdev_report_zones(dev->bdev, sector, blkz,
1146 					  &nr_blkz, GFP_KERNEL);
1147 		if (ret) {
1148 			dmz_dev_err(dev, "Report zones failed %d", ret);
1149 			goto out;
1150 		}
1151 
1152 		/* Process report */
1153 		for (i = 0; i < nr_blkz; i++) {
1154 			ret = dmz_init_zone(zmd, zone, &blkz[i]);
1155 			if (ret)
1156 				goto out;
1157 			sector += dev->zone_nr_sectors;
1158 			zone++;
1159 		}
1160 	}
1161 
1162 	/* The entire zone configuration of the disk should now be known */
1163 	if (sector < dev->capacity) {
1164 		dmz_dev_err(dev, "Failed to get correct zone information");
1165 		ret = -ENXIO;
1166 	}
1167 out:
1168 	kfree(blkz);
1169 	if (ret)
1170 		dmz_drop_zones(zmd);
1171 
1172 	return ret;
1173 }
1174 
1175 /*
1176  * Update a zone information.
1177  */
1178 static int dmz_update_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1179 {
1180 	unsigned int nr_blkz = 1;
1181 	struct blk_zone blkz;
1182 	int ret;
1183 
1184 	/* Get zone information from disk */
1185 	ret = blkdev_report_zones(zmd->dev->bdev, dmz_start_sect(zmd, zone),
1186 				  &blkz, &nr_blkz, GFP_NOIO);
1187 	if (ret) {
1188 		dmz_dev_err(zmd->dev, "Get zone %u report failed",
1189 			    dmz_id(zmd, zone));
1190 		return ret;
1191 	}
1192 
1193 	clear_bit(DMZ_OFFLINE, &zone->flags);
1194 	clear_bit(DMZ_READ_ONLY, &zone->flags);
1195 	if (blkz.cond == BLK_ZONE_COND_OFFLINE)
1196 		set_bit(DMZ_OFFLINE, &zone->flags);
1197 	else if (blkz.cond == BLK_ZONE_COND_READONLY)
1198 		set_bit(DMZ_READ_ONLY, &zone->flags);
1199 
1200 	if (dmz_is_seq(zone))
1201 		zone->wp_block = dmz_sect2blk(blkz.wp - blkz.start);
1202 	else
1203 		zone->wp_block = 0;
1204 
1205 	return 0;
1206 }
1207 
1208 /*
1209  * Check a zone write pointer position when the zone is marked
1210  * with the sequential write error flag.
1211  */
1212 static int dmz_handle_seq_write_err(struct dmz_metadata *zmd,
1213 				    struct dm_zone *zone)
1214 {
1215 	unsigned int wp = 0;
1216 	int ret;
1217 
1218 	wp = zone->wp_block;
1219 	ret = dmz_update_zone(zmd, zone);
1220 	if (ret)
1221 		return ret;
1222 
1223 	dmz_dev_warn(zmd->dev, "Processing zone %u write error (zone wp %u/%u)",
1224 		     dmz_id(zmd, zone), zone->wp_block, wp);
1225 
1226 	if (zone->wp_block < wp) {
1227 		dmz_invalidate_blocks(zmd, zone, zone->wp_block,
1228 				      wp - zone->wp_block);
1229 	}
1230 
1231 	return 0;
1232 }
1233 
1234 static struct dm_zone *dmz_get(struct dmz_metadata *zmd, unsigned int zone_id)
1235 {
1236 	return &zmd->zones[zone_id];
1237 }
1238 
1239 /*
1240  * Reset a zone write pointer.
1241  */
1242 static int dmz_reset_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1243 {
1244 	int ret;
1245 
1246 	/*
1247 	 * Ignore offline zones, read only zones,
1248 	 * and conventional zones.
1249 	 */
1250 	if (dmz_is_offline(zone) ||
1251 	    dmz_is_readonly(zone) ||
1252 	    dmz_is_rnd(zone))
1253 		return 0;
1254 
1255 	if (!dmz_is_empty(zone) || dmz_seq_write_err(zone)) {
1256 		struct dmz_dev *dev = zmd->dev;
1257 
1258 		ret = blkdev_reset_zones(dev->bdev,
1259 					 dmz_start_sect(zmd, zone),
1260 					 dev->zone_nr_sectors, GFP_NOIO);
1261 		if (ret) {
1262 			dmz_dev_err(dev, "Reset zone %u failed %d",
1263 				    dmz_id(zmd, zone), ret);
1264 			return ret;
1265 		}
1266 	}
1267 
1268 	/* Clear write error bit and rewind write pointer position */
1269 	clear_bit(DMZ_SEQ_WRITE_ERR, &zone->flags);
1270 	zone->wp_block = 0;
1271 
1272 	return 0;
1273 }
1274 
1275 static void dmz_get_zone_weight(struct dmz_metadata *zmd, struct dm_zone *zone);
1276 
1277 /*
1278  * Initialize chunk mapping.
1279  */
1280 static int dmz_load_mapping(struct dmz_metadata *zmd)
1281 {
1282 	struct dmz_dev *dev = zmd->dev;
1283 	struct dm_zone *dzone, *bzone;
1284 	struct dmz_mblock *dmap_mblk = NULL;
1285 	struct dmz_map *dmap;
1286 	unsigned int i = 0, e = 0, chunk = 0;
1287 	unsigned int dzone_id;
1288 	unsigned int bzone_id;
1289 
1290 	/* Metadata block array for the chunk mapping table */
1291 	zmd->map_mblk = kcalloc(zmd->nr_map_blocks,
1292 				sizeof(struct dmz_mblk *), GFP_KERNEL);
1293 	if (!zmd->map_mblk)
1294 		return -ENOMEM;
1295 
1296 	/* Get chunk mapping table blocks and initialize zone mapping */
1297 	while (chunk < zmd->nr_chunks) {
1298 		if (!dmap_mblk) {
1299 			/* Get mapping block */
1300 			dmap_mblk = dmz_get_mblock(zmd, i + 1);
1301 			if (IS_ERR(dmap_mblk))
1302 				return PTR_ERR(dmap_mblk);
1303 			zmd->map_mblk[i] = dmap_mblk;
1304 			dmap = (struct dmz_map *) dmap_mblk->data;
1305 			i++;
1306 			e = 0;
1307 		}
1308 
1309 		/* Check data zone */
1310 		dzone_id = le32_to_cpu(dmap[e].dzone_id);
1311 		if (dzone_id == DMZ_MAP_UNMAPPED)
1312 			goto next;
1313 
1314 		if (dzone_id >= dev->nr_zones) {
1315 			dmz_dev_err(dev, "Chunk %u mapping: invalid data zone ID %u",
1316 				    chunk, dzone_id);
1317 			return -EIO;
1318 		}
1319 
1320 		dzone = dmz_get(zmd, dzone_id);
1321 		set_bit(DMZ_DATA, &dzone->flags);
1322 		dzone->chunk = chunk;
1323 		dmz_get_zone_weight(zmd, dzone);
1324 
1325 		if (dmz_is_rnd(dzone))
1326 			list_add_tail(&dzone->link, &zmd->map_rnd_list);
1327 		else
1328 			list_add_tail(&dzone->link, &zmd->map_seq_list);
1329 
1330 		/* Check buffer zone */
1331 		bzone_id = le32_to_cpu(dmap[e].bzone_id);
1332 		if (bzone_id == DMZ_MAP_UNMAPPED)
1333 			goto next;
1334 
1335 		if (bzone_id >= dev->nr_zones) {
1336 			dmz_dev_err(dev, "Chunk %u mapping: invalid buffer zone ID %u",
1337 				    chunk, bzone_id);
1338 			return -EIO;
1339 		}
1340 
1341 		bzone = dmz_get(zmd, bzone_id);
1342 		if (!dmz_is_rnd(bzone)) {
1343 			dmz_dev_err(dev, "Chunk %u mapping: invalid buffer zone %u",
1344 				    chunk, bzone_id);
1345 			return -EIO;
1346 		}
1347 
1348 		set_bit(DMZ_DATA, &bzone->flags);
1349 		set_bit(DMZ_BUF, &bzone->flags);
1350 		bzone->chunk = chunk;
1351 		bzone->bzone = dzone;
1352 		dzone->bzone = bzone;
1353 		dmz_get_zone_weight(zmd, bzone);
1354 		list_add_tail(&bzone->link, &zmd->map_rnd_list);
1355 next:
1356 		chunk++;
1357 		e++;
1358 		if (e >= DMZ_MAP_ENTRIES)
1359 			dmap_mblk = NULL;
1360 	}
1361 
1362 	/*
1363 	 * At this point, only meta zones and mapped data zones were
1364 	 * fully initialized. All remaining zones are unmapped data
1365 	 * zones. Finish initializing those here.
1366 	 */
1367 	for (i = 0; i < dev->nr_zones; i++) {
1368 		dzone = dmz_get(zmd, i);
1369 		if (dmz_is_meta(dzone))
1370 			continue;
1371 
1372 		if (dmz_is_rnd(dzone))
1373 			zmd->nr_rnd++;
1374 		else
1375 			zmd->nr_seq++;
1376 
1377 		if (dmz_is_data(dzone)) {
1378 			/* Already initialized */
1379 			continue;
1380 		}
1381 
1382 		/* Unmapped data zone */
1383 		set_bit(DMZ_DATA, &dzone->flags);
1384 		dzone->chunk = DMZ_MAP_UNMAPPED;
1385 		if (dmz_is_rnd(dzone)) {
1386 			list_add_tail(&dzone->link, &zmd->unmap_rnd_list);
1387 			atomic_inc(&zmd->unmap_nr_rnd);
1388 		} else if (atomic_read(&zmd->nr_reserved_seq_zones) < zmd->nr_reserved_seq) {
1389 			list_add_tail(&dzone->link, &zmd->reserved_seq_zones_list);
1390 			atomic_inc(&zmd->nr_reserved_seq_zones);
1391 			zmd->nr_seq--;
1392 		} else {
1393 			list_add_tail(&dzone->link, &zmd->unmap_seq_list);
1394 			atomic_inc(&zmd->unmap_nr_seq);
1395 		}
1396 	}
1397 
1398 	return 0;
1399 }
1400 
1401 /*
1402  * Set a data chunk mapping.
1403  */
1404 static void dmz_set_chunk_mapping(struct dmz_metadata *zmd, unsigned int chunk,
1405 				  unsigned int dzone_id, unsigned int bzone_id)
1406 {
1407 	struct dmz_mblock *dmap_mblk = zmd->map_mblk[chunk >> DMZ_MAP_ENTRIES_SHIFT];
1408 	struct dmz_map *dmap = (struct dmz_map *) dmap_mblk->data;
1409 	int map_idx = chunk & DMZ_MAP_ENTRIES_MASK;
1410 
1411 	dmap[map_idx].dzone_id = cpu_to_le32(dzone_id);
1412 	dmap[map_idx].bzone_id = cpu_to_le32(bzone_id);
1413 	dmz_dirty_mblock(zmd, dmap_mblk);
1414 }
1415 
1416 /*
1417  * The list of mapped zones is maintained in LRU order.
1418  * This rotates a zone at the end of its map list.
1419  */
1420 static void __dmz_lru_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1421 {
1422 	if (list_empty(&zone->link))
1423 		return;
1424 
1425 	list_del_init(&zone->link);
1426 	if (dmz_is_seq(zone)) {
1427 		/* LRU rotate sequential zone */
1428 		list_add_tail(&zone->link, &zmd->map_seq_list);
1429 	} else {
1430 		/* LRU rotate random zone */
1431 		list_add_tail(&zone->link, &zmd->map_rnd_list);
1432 	}
1433 }
1434 
1435 /*
1436  * The list of mapped random zones is maintained
1437  * in LRU order. This rotates a zone at the end of the list.
1438  */
1439 static void dmz_lru_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1440 {
1441 	__dmz_lru_zone(zmd, zone);
1442 	if (zone->bzone)
1443 		__dmz_lru_zone(zmd, zone->bzone);
1444 }
1445 
1446 /*
1447  * Wait for any zone to be freed.
1448  */
1449 static void dmz_wait_for_free_zones(struct dmz_metadata *zmd)
1450 {
1451 	DEFINE_WAIT(wait);
1452 
1453 	prepare_to_wait(&zmd->free_wq, &wait, TASK_UNINTERRUPTIBLE);
1454 	dmz_unlock_map(zmd);
1455 	dmz_unlock_metadata(zmd);
1456 
1457 	io_schedule_timeout(HZ);
1458 
1459 	dmz_lock_metadata(zmd);
1460 	dmz_lock_map(zmd);
1461 	finish_wait(&zmd->free_wq, &wait);
1462 }
1463 
1464 /*
1465  * Lock a zone for reclaim (set the zone RECLAIM bit).
1466  * Returns false if the zone cannot be locked or if it is already locked
1467  * and 1 otherwise.
1468  */
1469 int dmz_lock_zone_reclaim(struct dm_zone *zone)
1470 {
1471 	/* Active zones cannot be reclaimed */
1472 	if (dmz_is_active(zone))
1473 		return 0;
1474 
1475 	return !test_and_set_bit(DMZ_RECLAIM, &zone->flags);
1476 }
1477 
1478 /*
1479  * Clear a zone reclaim flag.
1480  */
1481 void dmz_unlock_zone_reclaim(struct dm_zone *zone)
1482 {
1483 	WARN_ON(dmz_is_active(zone));
1484 	WARN_ON(!dmz_in_reclaim(zone));
1485 
1486 	clear_bit_unlock(DMZ_RECLAIM, &zone->flags);
1487 	smp_mb__after_atomic();
1488 	wake_up_bit(&zone->flags, DMZ_RECLAIM);
1489 }
1490 
1491 /*
1492  * Wait for a zone reclaim to complete.
1493  */
1494 static void dmz_wait_for_reclaim(struct dmz_metadata *zmd, struct dm_zone *zone)
1495 {
1496 	dmz_unlock_map(zmd);
1497 	dmz_unlock_metadata(zmd);
1498 	wait_on_bit_timeout(&zone->flags, DMZ_RECLAIM, TASK_UNINTERRUPTIBLE, HZ);
1499 	dmz_lock_metadata(zmd);
1500 	dmz_lock_map(zmd);
1501 }
1502 
1503 /*
1504  * Select a random write zone for reclaim.
1505  */
1506 static struct dm_zone *dmz_get_rnd_zone_for_reclaim(struct dmz_metadata *zmd)
1507 {
1508 	struct dm_zone *dzone = NULL;
1509 	struct dm_zone *zone;
1510 
1511 	if (list_empty(&zmd->map_rnd_list))
1512 		return NULL;
1513 
1514 	list_for_each_entry(zone, &zmd->map_rnd_list, link) {
1515 		if (dmz_is_buf(zone))
1516 			dzone = zone->bzone;
1517 		else
1518 			dzone = zone;
1519 		if (dmz_lock_zone_reclaim(dzone))
1520 			return dzone;
1521 	}
1522 
1523 	return NULL;
1524 }
1525 
1526 /*
1527  * Select a buffered sequential zone for reclaim.
1528  */
1529 static struct dm_zone *dmz_get_seq_zone_for_reclaim(struct dmz_metadata *zmd)
1530 {
1531 	struct dm_zone *zone;
1532 
1533 	if (list_empty(&zmd->map_seq_list))
1534 		return NULL;
1535 
1536 	list_for_each_entry(zone, &zmd->map_seq_list, link) {
1537 		if (!zone->bzone)
1538 			continue;
1539 		if (dmz_lock_zone_reclaim(zone))
1540 			return zone;
1541 	}
1542 
1543 	return NULL;
1544 }
1545 
1546 /*
1547  * Select a zone for reclaim.
1548  */
1549 struct dm_zone *dmz_get_zone_for_reclaim(struct dmz_metadata *zmd)
1550 {
1551 	struct dm_zone *zone;
1552 
1553 	/*
1554 	 * Search for a zone candidate to reclaim: 2 cases are possible.
1555 	 * (1) There is no free sequential zones. Then a random data zone
1556 	 *     cannot be reclaimed. So choose a sequential zone to reclaim so
1557 	 *     that afterward a random zone can be reclaimed.
1558 	 * (2) At least one free sequential zone is available, then choose
1559 	 *     the oldest random zone (data or buffer) that can be locked.
1560 	 */
1561 	dmz_lock_map(zmd);
1562 	if (list_empty(&zmd->reserved_seq_zones_list))
1563 		zone = dmz_get_seq_zone_for_reclaim(zmd);
1564 	else
1565 		zone = dmz_get_rnd_zone_for_reclaim(zmd);
1566 	dmz_unlock_map(zmd);
1567 
1568 	return zone;
1569 }
1570 
1571 /*
1572  * Activate a zone (increment its reference count).
1573  */
1574 void dmz_activate_zone(struct dm_zone *zone)
1575 {
1576 	set_bit(DMZ_ACTIVE, &zone->flags);
1577 	atomic_inc(&zone->refcount);
1578 }
1579 
1580 /*
1581  * Deactivate a zone. This decrement the zone reference counter
1582  * and clears the active state of the zone once the count reaches 0,
1583  * indicating that all BIOs to the zone have completed. Returns
1584  * true if the zone was deactivated.
1585  */
1586 void dmz_deactivate_zone(struct dm_zone *zone)
1587 {
1588 	if (atomic_dec_and_test(&zone->refcount)) {
1589 		WARN_ON(!test_bit(DMZ_ACTIVE, &zone->flags));
1590 		clear_bit_unlock(DMZ_ACTIVE, &zone->flags);
1591 		smp_mb__after_atomic();
1592 	}
1593 }
1594 
1595 /*
1596  * Get the zone mapping a chunk, if the chunk is mapped already.
1597  * If no mapping exist and the operation is WRITE, a zone is
1598  * allocated and used to map the chunk.
1599  * The zone returned will be set to the active state.
1600  */
1601 struct dm_zone *dmz_get_chunk_mapping(struct dmz_metadata *zmd, unsigned int chunk, int op)
1602 {
1603 	struct dmz_mblock *dmap_mblk = zmd->map_mblk[chunk >> DMZ_MAP_ENTRIES_SHIFT];
1604 	struct dmz_map *dmap = (struct dmz_map *) dmap_mblk->data;
1605 	int dmap_idx = chunk & DMZ_MAP_ENTRIES_MASK;
1606 	unsigned int dzone_id;
1607 	struct dm_zone *dzone = NULL;
1608 	int ret = 0;
1609 
1610 	dmz_lock_map(zmd);
1611 again:
1612 	/* Get the chunk mapping */
1613 	dzone_id = le32_to_cpu(dmap[dmap_idx].dzone_id);
1614 	if (dzone_id == DMZ_MAP_UNMAPPED) {
1615 		/*
1616 		 * Read or discard in unmapped chunks are fine. But for
1617 		 * writes, we need a mapping, so get one.
1618 		 */
1619 		if (op != REQ_OP_WRITE)
1620 			goto out;
1621 
1622 		/* Alloate a random zone */
1623 		dzone = dmz_alloc_zone(zmd, DMZ_ALLOC_RND);
1624 		if (!dzone) {
1625 			dmz_wait_for_free_zones(zmd);
1626 			goto again;
1627 		}
1628 
1629 		dmz_map_zone(zmd, dzone, chunk);
1630 
1631 	} else {
1632 		/* The chunk is already mapped: get the mapping zone */
1633 		dzone = dmz_get(zmd, dzone_id);
1634 		if (dzone->chunk != chunk) {
1635 			dzone = ERR_PTR(-EIO);
1636 			goto out;
1637 		}
1638 
1639 		/* Repair write pointer if the sequential dzone has error */
1640 		if (dmz_seq_write_err(dzone)) {
1641 			ret = dmz_handle_seq_write_err(zmd, dzone);
1642 			if (ret) {
1643 				dzone = ERR_PTR(-EIO);
1644 				goto out;
1645 			}
1646 			clear_bit(DMZ_SEQ_WRITE_ERR, &dzone->flags);
1647 		}
1648 	}
1649 
1650 	/*
1651 	 * If the zone is being reclaimed, the chunk mapping may change
1652 	 * to a different zone. So wait for reclaim and retry. Otherwise,
1653 	 * activate the zone (this will prevent reclaim from touching it).
1654 	 */
1655 	if (dmz_in_reclaim(dzone)) {
1656 		dmz_wait_for_reclaim(zmd, dzone);
1657 		goto again;
1658 	}
1659 	dmz_activate_zone(dzone);
1660 	dmz_lru_zone(zmd, dzone);
1661 out:
1662 	dmz_unlock_map(zmd);
1663 
1664 	return dzone;
1665 }
1666 
1667 /*
1668  * Write and discard change the block validity of data zones and their buffer
1669  * zones. Check here that valid blocks are still present. If all blocks are
1670  * invalid, the zones can be unmapped on the fly without waiting for reclaim
1671  * to do it.
1672  */
1673 void dmz_put_chunk_mapping(struct dmz_metadata *zmd, struct dm_zone *dzone)
1674 {
1675 	struct dm_zone *bzone;
1676 
1677 	dmz_lock_map(zmd);
1678 
1679 	bzone = dzone->bzone;
1680 	if (bzone) {
1681 		if (dmz_weight(bzone))
1682 			dmz_lru_zone(zmd, bzone);
1683 		else {
1684 			/* Empty buffer zone: reclaim it */
1685 			dmz_unmap_zone(zmd, bzone);
1686 			dmz_free_zone(zmd, bzone);
1687 			bzone = NULL;
1688 		}
1689 	}
1690 
1691 	/* Deactivate the data zone */
1692 	dmz_deactivate_zone(dzone);
1693 	if (dmz_is_active(dzone) || bzone || dmz_weight(dzone))
1694 		dmz_lru_zone(zmd, dzone);
1695 	else {
1696 		/* Unbuffered inactive empty data zone: reclaim it */
1697 		dmz_unmap_zone(zmd, dzone);
1698 		dmz_free_zone(zmd, dzone);
1699 	}
1700 
1701 	dmz_unlock_map(zmd);
1702 }
1703 
1704 /*
1705  * Allocate and map a random zone to buffer a chunk
1706  * already mapped to a sequential zone.
1707  */
1708 struct dm_zone *dmz_get_chunk_buffer(struct dmz_metadata *zmd,
1709 				     struct dm_zone *dzone)
1710 {
1711 	struct dm_zone *bzone;
1712 
1713 	dmz_lock_map(zmd);
1714 again:
1715 	bzone = dzone->bzone;
1716 	if (bzone)
1717 		goto out;
1718 
1719 	/* Alloate a random zone */
1720 	bzone = dmz_alloc_zone(zmd, DMZ_ALLOC_RND);
1721 	if (!bzone) {
1722 		dmz_wait_for_free_zones(zmd);
1723 		goto again;
1724 	}
1725 
1726 	/* Update the chunk mapping */
1727 	dmz_set_chunk_mapping(zmd, dzone->chunk, dmz_id(zmd, dzone),
1728 			      dmz_id(zmd, bzone));
1729 
1730 	set_bit(DMZ_BUF, &bzone->flags);
1731 	bzone->chunk = dzone->chunk;
1732 	bzone->bzone = dzone;
1733 	dzone->bzone = bzone;
1734 	list_add_tail(&bzone->link, &zmd->map_rnd_list);
1735 out:
1736 	dmz_unlock_map(zmd);
1737 
1738 	return bzone;
1739 }
1740 
1741 /*
1742  * Get an unmapped (free) zone.
1743  * This must be called with the mapping lock held.
1744  */
1745 struct dm_zone *dmz_alloc_zone(struct dmz_metadata *zmd, unsigned long flags)
1746 {
1747 	struct list_head *list;
1748 	struct dm_zone *zone;
1749 
1750 	if (flags & DMZ_ALLOC_RND)
1751 		list = &zmd->unmap_rnd_list;
1752 	else
1753 		list = &zmd->unmap_seq_list;
1754 again:
1755 	if (list_empty(list)) {
1756 		/*
1757 		 * No free zone: if this is for reclaim, allow using the
1758 		 * reserved sequential zones.
1759 		 */
1760 		if (!(flags & DMZ_ALLOC_RECLAIM) ||
1761 		    list_empty(&zmd->reserved_seq_zones_list))
1762 			return NULL;
1763 
1764 		zone = list_first_entry(&zmd->reserved_seq_zones_list,
1765 					struct dm_zone, link);
1766 		list_del_init(&zone->link);
1767 		atomic_dec(&zmd->nr_reserved_seq_zones);
1768 		return zone;
1769 	}
1770 
1771 	zone = list_first_entry(list, struct dm_zone, link);
1772 	list_del_init(&zone->link);
1773 
1774 	if (dmz_is_rnd(zone))
1775 		atomic_dec(&zmd->unmap_nr_rnd);
1776 	else
1777 		atomic_dec(&zmd->unmap_nr_seq);
1778 
1779 	if (dmz_is_offline(zone)) {
1780 		dmz_dev_warn(zmd->dev, "Zone %u is offline", dmz_id(zmd, zone));
1781 		zone = NULL;
1782 		goto again;
1783 	}
1784 
1785 	return zone;
1786 }
1787 
1788 /*
1789  * Free a zone.
1790  * This must be called with the mapping lock held.
1791  */
1792 void dmz_free_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1793 {
1794 	/* If this is a sequential zone, reset it */
1795 	if (dmz_is_seq(zone))
1796 		dmz_reset_zone(zmd, zone);
1797 
1798 	/* Return the zone to its type unmap list */
1799 	if (dmz_is_rnd(zone)) {
1800 		list_add_tail(&zone->link, &zmd->unmap_rnd_list);
1801 		atomic_inc(&zmd->unmap_nr_rnd);
1802 	} else if (atomic_read(&zmd->nr_reserved_seq_zones) <
1803 		   zmd->nr_reserved_seq) {
1804 		list_add_tail(&zone->link, &zmd->reserved_seq_zones_list);
1805 		atomic_inc(&zmd->nr_reserved_seq_zones);
1806 	} else {
1807 		list_add_tail(&zone->link, &zmd->unmap_seq_list);
1808 		atomic_inc(&zmd->unmap_nr_seq);
1809 	}
1810 
1811 	wake_up_all(&zmd->free_wq);
1812 }
1813 
1814 /*
1815  * Map a chunk to a zone.
1816  * This must be called with the mapping lock held.
1817  */
1818 void dmz_map_zone(struct dmz_metadata *zmd, struct dm_zone *dzone,
1819 		  unsigned int chunk)
1820 {
1821 	/* Set the chunk mapping */
1822 	dmz_set_chunk_mapping(zmd, chunk, dmz_id(zmd, dzone),
1823 			      DMZ_MAP_UNMAPPED);
1824 	dzone->chunk = chunk;
1825 	if (dmz_is_rnd(dzone))
1826 		list_add_tail(&dzone->link, &zmd->map_rnd_list);
1827 	else
1828 		list_add_tail(&dzone->link, &zmd->map_seq_list);
1829 }
1830 
1831 /*
1832  * Unmap a zone.
1833  * This must be called with the mapping lock held.
1834  */
1835 void dmz_unmap_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1836 {
1837 	unsigned int chunk = zone->chunk;
1838 	unsigned int dzone_id;
1839 
1840 	if (chunk == DMZ_MAP_UNMAPPED) {
1841 		/* Already unmapped */
1842 		return;
1843 	}
1844 
1845 	if (test_and_clear_bit(DMZ_BUF, &zone->flags)) {
1846 		/*
1847 		 * Unmapping the chunk buffer zone: clear only
1848 		 * the chunk buffer mapping
1849 		 */
1850 		dzone_id = dmz_id(zmd, zone->bzone);
1851 		zone->bzone->bzone = NULL;
1852 		zone->bzone = NULL;
1853 
1854 	} else {
1855 		/*
1856 		 * Unmapping the chunk data zone: the zone must
1857 		 * not be buffered.
1858 		 */
1859 		if (WARN_ON(zone->bzone)) {
1860 			zone->bzone->bzone = NULL;
1861 			zone->bzone = NULL;
1862 		}
1863 		dzone_id = DMZ_MAP_UNMAPPED;
1864 	}
1865 
1866 	dmz_set_chunk_mapping(zmd, chunk, dzone_id, DMZ_MAP_UNMAPPED);
1867 
1868 	zone->chunk = DMZ_MAP_UNMAPPED;
1869 	list_del_init(&zone->link);
1870 }
1871 
1872 /*
1873  * Set @nr_bits bits in @bitmap starting from @bit.
1874  * Return the number of bits changed from 0 to 1.
1875  */
1876 static unsigned int dmz_set_bits(unsigned long *bitmap,
1877 				 unsigned int bit, unsigned int nr_bits)
1878 {
1879 	unsigned long *addr;
1880 	unsigned int end = bit + nr_bits;
1881 	unsigned int n = 0;
1882 
1883 	while (bit < end) {
1884 		if (((bit & (BITS_PER_LONG - 1)) == 0) &&
1885 		    ((end - bit) >= BITS_PER_LONG)) {
1886 			/* Try to set the whole word at once */
1887 			addr = bitmap + BIT_WORD(bit);
1888 			if (*addr == 0) {
1889 				*addr = ULONG_MAX;
1890 				n += BITS_PER_LONG;
1891 				bit += BITS_PER_LONG;
1892 				continue;
1893 			}
1894 		}
1895 
1896 		if (!test_and_set_bit(bit, bitmap))
1897 			n++;
1898 		bit++;
1899 	}
1900 
1901 	return n;
1902 }
1903 
1904 /*
1905  * Get the bitmap block storing the bit for chunk_block in zone.
1906  */
1907 static struct dmz_mblock *dmz_get_bitmap(struct dmz_metadata *zmd,
1908 					 struct dm_zone *zone,
1909 					 sector_t chunk_block)
1910 {
1911 	sector_t bitmap_block = 1 + zmd->nr_map_blocks +
1912 		(sector_t)(dmz_id(zmd, zone) * zmd->zone_nr_bitmap_blocks) +
1913 		(chunk_block >> DMZ_BLOCK_SHIFT_BITS);
1914 
1915 	return dmz_get_mblock(zmd, bitmap_block);
1916 }
1917 
1918 /*
1919  * Copy the valid blocks bitmap of from_zone to the bitmap of to_zone.
1920  */
1921 int dmz_copy_valid_blocks(struct dmz_metadata *zmd, struct dm_zone *from_zone,
1922 			  struct dm_zone *to_zone)
1923 {
1924 	struct dmz_mblock *from_mblk, *to_mblk;
1925 	sector_t chunk_block = 0;
1926 
1927 	/* Get the zones bitmap blocks */
1928 	while (chunk_block < zmd->dev->zone_nr_blocks) {
1929 		from_mblk = dmz_get_bitmap(zmd, from_zone, chunk_block);
1930 		if (IS_ERR(from_mblk))
1931 			return PTR_ERR(from_mblk);
1932 		to_mblk = dmz_get_bitmap(zmd, to_zone, chunk_block);
1933 		if (IS_ERR(to_mblk)) {
1934 			dmz_release_mblock(zmd, from_mblk);
1935 			return PTR_ERR(to_mblk);
1936 		}
1937 
1938 		memcpy(to_mblk->data, from_mblk->data, DMZ_BLOCK_SIZE);
1939 		dmz_dirty_mblock(zmd, to_mblk);
1940 
1941 		dmz_release_mblock(zmd, to_mblk);
1942 		dmz_release_mblock(zmd, from_mblk);
1943 
1944 		chunk_block += DMZ_BLOCK_SIZE_BITS;
1945 	}
1946 
1947 	to_zone->weight = from_zone->weight;
1948 
1949 	return 0;
1950 }
1951 
1952 /*
1953  * Merge the valid blocks bitmap of from_zone into the bitmap of to_zone,
1954  * starting from chunk_block.
1955  */
1956 int dmz_merge_valid_blocks(struct dmz_metadata *zmd, struct dm_zone *from_zone,
1957 			   struct dm_zone *to_zone, sector_t chunk_block)
1958 {
1959 	unsigned int nr_blocks;
1960 	int ret;
1961 
1962 	/* Get the zones bitmap blocks */
1963 	while (chunk_block < zmd->dev->zone_nr_blocks) {
1964 		/* Get a valid region from the source zone */
1965 		ret = dmz_first_valid_block(zmd, from_zone, &chunk_block);
1966 		if (ret <= 0)
1967 			return ret;
1968 
1969 		nr_blocks = ret;
1970 		ret = dmz_validate_blocks(zmd, to_zone, chunk_block, nr_blocks);
1971 		if (ret)
1972 			return ret;
1973 
1974 		chunk_block += nr_blocks;
1975 	}
1976 
1977 	return 0;
1978 }
1979 
1980 /*
1981  * Validate all the blocks in the range [block..block+nr_blocks-1].
1982  */
1983 int dmz_validate_blocks(struct dmz_metadata *zmd, struct dm_zone *zone,
1984 			sector_t chunk_block, unsigned int nr_blocks)
1985 {
1986 	unsigned int count, bit, nr_bits;
1987 	unsigned int zone_nr_blocks = zmd->dev->zone_nr_blocks;
1988 	struct dmz_mblock *mblk;
1989 	unsigned int n = 0;
1990 
1991 	dmz_dev_debug(zmd->dev, "=> VALIDATE zone %u, block %llu, %u blocks",
1992 		      dmz_id(zmd, zone), (unsigned long long)chunk_block,
1993 		      nr_blocks);
1994 
1995 	WARN_ON(chunk_block + nr_blocks > zone_nr_blocks);
1996 
1997 	while (nr_blocks) {
1998 		/* Get bitmap block */
1999 		mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2000 		if (IS_ERR(mblk))
2001 			return PTR_ERR(mblk);
2002 
2003 		/* Set bits */
2004 		bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2005 		nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2006 
2007 		count = dmz_set_bits((unsigned long *)mblk->data, bit, nr_bits);
2008 		if (count) {
2009 			dmz_dirty_mblock(zmd, mblk);
2010 			n += count;
2011 		}
2012 		dmz_release_mblock(zmd, mblk);
2013 
2014 		nr_blocks -= nr_bits;
2015 		chunk_block += nr_bits;
2016 	}
2017 
2018 	if (likely(zone->weight + n <= zone_nr_blocks))
2019 		zone->weight += n;
2020 	else {
2021 		dmz_dev_warn(zmd->dev, "Zone %u: weight %u should be <= %u",
2022 			     dmz_id(zmd, zone), zone->weight,
2023 			     zone_nr_blocks - n);
2024 		zone->weight = zone_nr_blocks;
2025 	}
2026 
2027 	return 0;
2028 }
2029 
2030 /*
2031  * Clear nr_bits bits in bitmap starting from bit.
2032  * Return the number of bits cleared.
2033  */
2034 static int dmz_clear_bits(unsigned long *bitmap, int bit, int nr_bits)
2035 {
2036 	unsigned long *addr;
2037 	int end = bit + nr_bits;
2038 	int n = 0;
2039 
2040 	while (bit < end) {
2041 		if (((bit & (BITS_PER_LONG - 1)) == 0) &&
2042 		    ((end - bit) >= BITS_PER_LONG)) {
2043 			/* Try to clear whole word at once */
2044 			addr = bitmap + BIT_WORD(bit);
2045 			if (*addr == ULONG_MAX) {
2046 				*addr = 0;
2047 				n += BITS_PER_LONG;
2048 				bit += BITS_PER_LONG;
2049 				continue;
2050 			}
2051 		}
2052 
2053 		if (test_and_clear_bit(bit, bitmap))
2054 			n++;
2055 		bit++;
2056 	}
2057 
2058 	return n;
2059 }
2060 
2061 /*
2062  * Invalidate all the blocks in the range [block..block+nr_blocks-1].
2063  */
2064 int dmz_invalidate_blocks(struct dmz_metadata *zmd, struct dm_zone *zone,
2065 			  sector_t chunk_block, unsigned int nr_blocks)
2066 {
2067 	unsigned int count, bit, nr_bits;
2068 	struct dmz_mblock *mblk;
2069 	unsigned int n = 0;
2070 
2071 	dmz_dev_debug(zmd->dev, "=> INVALIDATE zone %u, block %llu, %u blocks",
2072 		      dmz_id(zmd, zone), (u64)chunk_block, nr_blocks);
2073 
2074 	WARN_ON(chunk_block + nr_blocks > zmd->dev->zone_nr_blocks);
2075 
2076 	while (nr_blocks) {
2077 		/* Get bitmap block */
2078 		mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2079 		if (IS_ERR(mblk))
2080 			return PTR_ERR(mblk);
2081 
2082 		/* Clear bits */
2083 		bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2084 		nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2085 
2086 		count = dmz_clear_bits((unsigned long *)mblk->data,
2087 				       bit, nr_bits);
2088 		if (count) {
2089 			dmz_dirty_mblock(zmd, mblk);
2090 			n += count;
2091 		}
2092 		dmz_release_mblock(zmd, mblk);
2093 
2094 		nr_blocks -= nr_bits;
2095 		chunk_block += nr_bits;
2096 	}
2097 
2098 	if (zone->weight >= n)
2099 		zone->weight -= n;
2100 	else {
2101 		dmz_dev_warn(zmd->dev, "Zone %u: weight %u should be >= %u",
2102 			     dmz_id(zmd, zone), zone->weight, n);
2103 		zone->weight = 0;
2104 	}
2105 
2106 	return 0;
2107 }
2108 
2109 /*
2110  * Get a block bit value.
2111  */
2112 static int dmz_test_block(struct dmz_metadata *zmd, struct dm_zone *zone,
2113 			  sector_t chunk_block)
2114 {
2115 	struct dmz_mblock *mblk;
2116 	int ret;
2117 
2118 	WARN_ON(chunk_block >= zmd->dev->zone_nr_blocks);
2119 
2120 	/* Get bitmap block */
2121 	mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2122 	if (IS_ERR(mblk))
2123 		return PTR_ERR(mblk);
2124 
2125 	/* Get offset */
2126 	ret = test_bit(chunk_block & DMZ_BLOCK_MASK_BITS,
2127 		       (unsigned long *) mblk->data) != 0;
2128 
2129 	dmz_release_mblock(zmd, mblk);
2130 
2131 	return ret;
2132 }
2133 
2134 /*
2135  * Return the number of blocks from chunk_block to the first block with a bit
2136  * value specified by set. Search at most nr_blocks blocks from chunk_block.
2137  */
2138 static int dmz_to_next_set_block(struct dmz_metadata *zmd, struct dm_zone *zone,
2139 				 sector_t chunk_block, unsigned int nr_blocks,
2140 				 int set)
2141 {
2142 	struct dmz_mblock *mblk;
2143 	unsigned int bit, set_bit, nr_bits;
2144 	unsigned long *bitmap;
2145 	int n = 0;
2146 
2147 	WARN_ON(chunk_block + nr_blocks > zmd->dev->zone_nr_blocks);
2148 
2149 	while (nr_blocks) {
2150 		/* Get bitmap block */
2151 		mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2152 		if (IS_ERR(mblk))
2153 			return PTR_ERR(mblk);
2154 
2155 		/* Get offset */
2156 		bitmap = (unsigned long *) mblk->data;
2157 		bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2158 		nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2159 		if (set)
2160 			set_bit = find_next_bit(bitmap, DMZ_BLOCK_SIZE_BITS, bit);
2161 		else
2162 			set_bit = find_next_zero_bit(bitmap, DMZ_BLOCK_SIZE_BITS, bit);
2163 		dmz_release_mblock(zmd, mblk);
2164 
2165 		n += set_bit - bit;
2166 		if (set_bit < DMZ_BLOCK_SIZE_BITS)
2167 			break;
2168 
2169 		nr_blocks -= nr_bits;
2170 		chunk_block += nr_bits;
2171 	}
2172 
2173 	return n;
2174 }
2175 
2176 /*
2177  * Test if chunk_block is valid. If it is, the number of consecutive
2178  * valid blocks from chunk_block will be returned.
2179  */
2180 int dmz_block_valid(struct dmz_metadata *zmd, struct dm_zone *zone,
2181 		    sector_t chunk_block)
2182 {
2183 	int valid;
2184 
2185 	valid = dmz_test_block(zmd, zone, chunk_block);
2186 	if (valid <= 0)
2187 		return valid;
2188 
2189 	/* The block is valid: get the number of valid blocks from block */
2190 	return dmz_to_next_set_block(zmd, zone, chunk_block,
2191 				     zmd->dev->zone_nr_blocks - chunk_block, 0);
2192 }
2193 
2194 /*
2195  * Find the first valid block from @chunk_block in @zone.
2196  * If such a block is found, its number is returned using
2197  * @chunk_block and the total number of valid blocks from @chunk_block
2198  * is returned.
2199  */
2200 int dmz_first_valid_block(struct dmz_metadata *zmd, struct dm_zone *zone,
2201 			  sector_t *chunk_block)
2202 {
2203 	sector_t start_block = *chunk_block;
2204 	int ret;
2205 
2206 	ret = dmz_to_next_set_block(zmd, zone, start_block,
2207 				    zmd->dev->zone_nr_blocks - start_block, 1);
2208 	if (ret < 0)
2209 		return ret;
2210 
2211 	start_block += ret;
2212 	*chunk_block = start_block;
2213 
2214 	return dmz_to_next_set_block(zmd, zone, start_block,
2215 				     zmd->dev->zone_nr_blocks - start_block, 0);
2216 }
2217 
2218 /*
2219  * Count the number of bits set starting from bit up to bit + nr_bits - 1.
2220  */
2221 static int dmz_count_bits(void *bitmap, int bit, int nr_bits)
2222 {
2223 	unsigned long *addr;
2224 	int end = bit + nr_bits;
2225 	int n = 0;
2226 
2227 	while (bit < end) {
2228 		if (((bit & (BITS_PER_LONG - 1)) == 0) &&
2229 		    ((end - bit) >= BITS_PER_LONG)) {
2230 			addr = (unsigned long *)bitmap + BIT_WORD(bit);
2231 			if (*addr == ULONG_MAX) {
2232 				n += BITS_PER_LONG;
2233 				bit += BITS_PER_LONG;
2234 				continue;
2235 			}
2236 		}
2237 
2238 		if (test_bit(bit, bitmap))
2239 			n++;
2240 		bit++;
2241 	}
2242 
2243 	return n;
2244 }
2245 
2246 /*
2247  * Get a zone weight.
2248  */
2249 static void dmz_get_zone_weight(struct dmz_metadata *zmd, struct dm_zone *zone)
2250 {
2251 	struct dmz_mblock *mblk;
2252 	sector_t chunk_block = 0;
2253 	unsigned int bit, nr_bits;
2254 	unsigned int nr_blocks = zmd->dev->zone_nr_blocks;
2255 	void *bitmap;
2256 	int n = 0;
2257 
2258 	while (nr_blocks) {
2259 		/* Get bitmap block */
2260 		mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2261 		if (IS_ERR(mblk)) {
2262 			n = 0;
2263 			break;
2264 		}
2265 
2266 		/* Count bits in this block */
2267 		bitmap = mblk->data;
2268 		bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2269 		nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2270 		n += dmz_count_bits(bitmap, bit, nr_bits);
2271 
2272 		dmz_release_mblock(zmd, mblk);
2273 
2274 		nr_blocks -= nr_bits;
2275 		chunk_block += nr_bits;
2276 	}
2277 
2278 	zone->weight = n;
2279 }
2280 
2281 /*
2282  * Cleanup the zoned metadata resources.
2283  */
2284 static void dmz_cleanup_metadata(struct dmz_metadata *zmd)
2285 {
2286 	struct rb_root *root;
2287 	struct dmz_mblock *mblk, *next;
2288 	int i;
2289 
2290 	/* Release zone mapping resources */
2291 	if (zmd->map_mblk) {
2292 		for (i = 0; i < zmd->nr_map_blocks; i++)
2293 			dmz_release_mblock(zmd, zmd->map_mblk[i]);
2294 		kfree(zmd->map_mblk);
2295 		zmd->map_mblk = NULL;
2296 	}
2297 
2298 	/* Release super blocks */
2299 	for (i = 0; i < 2; i++) {
2300 		if (zmd->sb[i].mblk) {
2301 			dmz_free_mblock(zmd, zmd->sb[i].mblk);
2302 			zmd->sb[i].mblk = NULL;
2303 		}
2304 	}
2305 
2306 	/* Free cached blocks */
2307 	while (!list_empty(&zmd->mblk_dirty_list)) {
2308 		mblk = list_first_entry(&zmd->mblk_dirty_list,
2309 					struct dmz_mblock, link);
2310 		dmz_dev_warn(zmd->dev, "mblock %llu still in dirty list (ref %u)",
2311 			     (u64)mblk->no, atomic_read(&mblk->ref));
2312 		list_del_init(&mblk->link);
2313 		rb_erase(&mblk->node, &zmd->mblk_rbtree);
2314 		dmz_free_mblock(zmd, mblk);
2315 	}
2316 
2317 	while (!list_empty(&zmd->mblk_lru_list)) {
2318 		mblk = list_first_entry(&zmd->mblk_lru_list,
2319 					struct dmz_mblock, link);
2320 		list_del_init(&mblk->link);
2321 		rb_erase(&mblk->node, &zmd->mblk_rbtree);
2322 		dmz_free_mblock(zmd, mblk);
2323 	}
2324 
2325 	/* Sanity checks: the mblock rbtree should now be empty */
2326 	root = &zmd->mblk_rbtree;
2327 	rbtree_postorder_for_each_entry_safe(mblk, next, root, node) {
2328 		dmz_dev_warn(zmd->dev, "mblock %llu ref %u still in rbtree",
2329 			     (u64)mblk->no, atomic_read(&mblk->ref));
2330 		atomic_set(&mblk->ref, 0);
2331 		dmz_free_mblock(zmd, mblk);
2332 	}
2333 
2334 	/* Free the zone descriptors */
2335 	dmz_drop_zones(zmd);
2336 
2337 	mutex_destroy(&zmd->mblk_flush_lock);
2338 	mutex_destroy(&zmd->map_lock);
2339 }
2340 
2341 /*
2342  * Initialize the zoned metadata.
2343  */
2344 int dmz_ctr_metadata(struct dmz_dev *dev, struct dmz_metadata **metadata)
2345 {
2346 	struct dmz_metadata *zmd;
2347 	unsigned int i, zid;
2348 	struct dm_zone *zone;
2349 	int ret;
2350 
2351 	zmd = kzalloc(sizeof(struct dmz_metadata), GFP_KERNEL);
2352 	if (!zmd)
2353 		return -ENOMEM;
2354 
2355 	zmd->dev = dev;
2356 	zmd->mblk_rbtree = RB_ROOT;
2357 	init_rwsem(&zmd->mblk_sem);
2358 	mutex_init(&zmd->mblk_flush_lock);
2359 	spin_lock_init(&zmd->mblk_lock);
2360 	INIT_LIST_HEAD(&zmd->mblk_lru_list);
2361 	INIT_LIST_HEAD(&zmd->mblk_dirty_list);
2362 
2363 	mutex_init(&zmd->map_lock);
2364 	atomic_set(&zmd->unmap_nr_rnd, 0);
2365 	INIT_LIST_HEAD(&zmd->unmap_rnd_list);
2366 	INIT_LIST_HEAD(&zmd->map_rnd_list);
2367 
2368 	atomic_set(&zmd->unmap_nr_seq, 0);
2369 	INIT_LIST_HEAD(&zmd->unmap_seq_list);
2370 	INIT_LIST_HEAD(&zmd->map_seq_list);
2371 
2372 	atomic_set(&zmd->nr_reserved_seq_zones, 0);
2373 	INIT_LIST_HEAD(&zmd->reserved_seq_zones_list);
2374 
2375 	init_waitqueue_head(&zmd->free_wq);
2376 
2377 	/* Initialize zone descriptors */
2378 	ret = dmz_init_zones(zmd);
2379 	if (ret)
2380 		goto err;
2381 
2382 	/* Get super block */
2383 	ret = dmz_load_sb(zmd);
2384 	if (ret)
2385 		goto err;
2386 
2387 	/* Set metadata zones starting from sb_zone */
2388 	zid = dmz_id(zmd, zmd->sb_zone);
2389 	for (i = 0; i < zmd->nr_meta_zones << 1; i++) {
2390 		zone = dmz_get(zmd, zid + i);
2391 		if (!dmz_is_rnd(zone))
2392 			goto err;
2393 		set_bit(DMZ_META, &zone->flags);
2394 	}
2395 
2396 	/* Load mapping table */
2397 	ret = dmz_load_mapping(zmd);
2398 	if (ret)
2399 		goto err;
2400 
2401 	/*
2402 	 * Cache size boundaries: allow at least 2 super blocks, the chunk map
2403 	 * blocks and enough blocks to be able to cache the bitmap blocks of
2404 	 * up to 16 zones when idle (min_nr_mblks). Otherwise, if busy, allow
2405 	 * the cache to add 512 more metadata blocks.
2406 	 */
2407 	zmd->min_nr_mblks = 2 + zmd->nr_map_blocks + zmd->zone_nr_bitmap_blocks * 16;
2408 	zmd->max_nr_mblks = zmd->min_nr_mblks + 512;
2409 	zmd->mblk_shrinker.count_objects = dmz_mblock_shrinker_count;
2410 	zmd->mblk_shrinker.scan_objects = dmz_mblock_shrinker_scan;
2411 	zmd->mblk_shrinker.seeks = DEFAULT_SEEKS;
2412 
2413 	/* Metadata cache shrinker */
2414 	ret = register_shrinker(&zmd->mblk_shrinker);
2415 	if (ret) {
2416 		dmz_dev_err(dev, "Register metadata cache shrinker failed");
2417 		goto err;
2418 	}
2419 
2420 	dmz_dev_info(dev, "Host-%s zoned block device",
2421 		     bdev_zoned_model(dev->bdev) == BLK_ZONED_HA ?
2422 		     "aware" : "managed");
2423 	dmz_dev_info(dev, "  %llu 512-byte logical sectors",
2424 		     (u64)dev->capacity);
2425 	dmz_dev_info(dev, "  %u zones of %llu 512-byte logical sectors",
2426 		     dev->nr_zones, (u64)dev->zone_nr_sectors);
2427 	dmz_dev_info(dev, "  %u metadata zones",
2428 		     zmd->nr_meta_zones * 2);
2429 	dmz_dev_info(dev, "  %u data zones for %u chunks",
2430 		     zmd->nr_data_zones, zmd->nr_chunks);
2431 	dmz_dev_info(dev, "    %u random zones (%u unmapped)",
2432 		     zmd->nr_rnd, atomic_read(&zmd->unmap_nr_rnd));
2433 	dmz_dev_info(dev, "    %u sequential zones (%u unmapped)",
2434 		     zmd->nr_seq, atomic_read(&zmd->unmap_nr_seq));
2435 	dmz_dev_info(dev, "  %u reserved sequential data zones",
2436 		     zmd->nr_reserved_seq);
2437 
2438 	dmz_dev_debug(dev, "Format:");
2439 	dmz_dev_debug(dev, "%u metadata blocks per set (%u max cache)",
2440 		      zmd->nr_meta_blocks, zmd->max_nr_mblks);
2441 	dmz_dev_debug(dev, "  %u data zone mapping blocks",
2442 		      zmd->nr_map_blocks);
2443 	dmz_dev_debug(dev, "  %u bitmap blocks",
2444 		      zmd->nr_bitmap_blocks);
2445 
2446 	*metadata = zmd;
2447 
2448 	return 0;
2449 err:
2450 	dmz_cleanup_metadata(zmd);
2451 	kfree(zmd);
2452 	*metadata = NULL;
2453 
2454 	return ret;
2455 }
2456 
2457 /*
2458  * Cleanup the zoned metadata resources.
2459  */
2460 void dmz_dtr_metadata(struct dmz_metadata *zmd)
2461 {
2462 	unregister_shrinker(&zmd->mblk_shrinker);
2463 	dmz_cleanup_metadata(zmd);
2464 	kfree(zmd);
2465 }
2466 
2467 /*
2468  * Check zone information on resume.
2469  */
2470 int dmz_resume_metadata(struct dmz_metadata *zmd)
2471 {
2472 	struct dmz_dev *dev = zmd->dev;
2473 	struct dm_zone *zone;
2474 	sector_t wp_block;
2475 	unsigned int i;
2476 	int ret;
2477 
2478 	/* Check zones */
2479 	for (i = 0; i < dev->nr_zones; i++) {
2480 		zone = dmz_get(zmd, i);
2481 		if (!zone) {
2482 			dmz_dev_err(dev, "Unable to get zone %u", i);
2483 			return -EIO;
2484 		}
2485 
2486 		wp_block = zone->wp_block;
2487 
2488 		ret = dmz_update_zone(zmd, zone);
2489 		if (ret) {
2490 			dmz_dev_err(dev, "Broken zone %u", i);
2491 			return ret;
2492 		}
2493 
2494 		if (dmz_is_offline(zone)) {
2495 			dmz_dev_warn(dev, "Zone %u is offline", i);
2496 			continue;
2497 		}
2498 
2499 		/* Check write pointer */
2500 		if (!dmz_is_seq(zone))
2501 			zone->wp_block = 0;
2502 		else if (zone->wp_block != wp_block) {
2503 			dmz_dev_err(dev, "Zone %u: Invalid wp (%llu / %llu)",
2504 				    i, (u64)zone->wp_block, (u64)wp_block);
2505 			zone->wp_block = wp_block;
2506 			dmz_invalidate_blocks(zmd, zone, zone->wp_block,
2507 					      dev->zone_nr_blocks - zone->wp_block);
2508 		}
2509 	}
2510 
2511 	return 0;
2512 }
2513