[mirror_ubuntu-zesty-kernel.git] / drivers / lightnvm / rrpc.h

/*
 * Copyright (C) 2015 IT University of Copenhagen
 * Initial release: Matias Bjorling <m@bjorling.me>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License version
 * 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * Implementation of a Round-robin page-based Hybrid FTL for Open-channel SSDs.
 */

#ifndef RRPC_H_
#define RRPC_H_

#include <linux/blkdev.h>
#include <linux/blk-mq.h>
#include <linux/bio.h>
#include <linux/module.h>
#include <linux/kthread.h>
#include <linux/vmalloc.h>

#include <linux/lightnvm.h>

/* Run only GC if less than 1/X blocks are free */
#define GC_LIMIT_INVERSE 10
#define GC_TIME_SECS 100

#define RRPC_SECTOR (512)
#define RRPC_EXPOSED_PAGE_SIZE (4096)

#define NR_PHY_IN_LOG (RRPC_EXPOSED_PAGE_SIZE / RRPC_SECTOR)

struct rrpc_inflight {
	struct list_head reqs;
	spinlock_t lock;
};

struct rrpc_inflight_rq {
	struct list_head list;
	sector_t l_start;
	sector_t l_end;
};

struct rrpc_rq {
	struct rrpc_inflight_rq inflight_rq;
	unsigned long flags;
};

struct rrpc_block {
	int id;				/* id inside of LUN */
	struct rrpc_lun *rlun;

	struct list_head prio;		/* LUN CG list */
	struct list_head list;		/* LUN free, used, bb list */

#define MAX_INVALID_PAGES_STORAGE 8
	/* Bitmap for invalid page intries */
	unsigned long invalid_pages[MAX_INVALID_PAGES_STORAGE];
	/* points to the next writable page within a block */
	unsigned int next_page;
	/* number of pages that are invalid, wrt host page size */
	unsigned int nr_invalid_pages;

	int state;

	spinlock_t lock;
	atomic_t data_cmnt_size; /* data pages committed to stable storage */
};

struct rrpc_lun {
	struct rrpc *rrpc;

	int id;
	struct ppa_addr bppa;

	struct rrpc_block *cur, *gc_cur;
	struct rrpc_block *blocks;	/* Reference to block allocation */

	struct list_head prio_list;	/* Blocks that may be GC'ed */
	struct list_head wblk_list;	/* Queued blocks to be written to */

	/* lun block lists */
	struct list_head used_list;	/* In-use blocks */
	struct list_head free_list;	/* Not used blocks i.e. released
					 * and ready for use
					 */
	struct list_head bb_list;	/* Bad blocks. Mutually exclusive with
					 * free_list and used_list
					 */
	unsigned int nr_free_blocks;	/* Number of unused blocks */

	struct work_struct ws_gc;

	int reserved_blocks;

	spinlock_t lock;
};

struct rrpc {
	/* instance must be kept in top to resolve rrpc in unprep */
	struct nvm_tgt_instance instance;

	struct nvm_tgt_dev *dev;
	struct gendisk *disk;

	sector_t soffset; /* logical sector offset */

	int nr_luns;
	struct rrpc_lun *luns;

	/* calculated values */
	unsigned long long nr_sects;

	/* Write strategy variables. Move these into each for structure for each
	 * strategy
	 */
	atomic_t next_lun; /* Whenever a page is written, this is updated
			    * to point to the next write lun
			    */

	spinlock_t bio_lock;
	struct bio_list requeue_bios;
	struct work_struct ws_requeue;

	/* Simple translation map of logical addresses to physical addresses.
	 * The logical addresses is known by the host system, while the physical
	 * addresses are used when writing to the disk block device.
	 */
	struct rrpc_addr *trans_map;
	/* also store a reverse map for garbage collection */
	struct rrpc_rev_addr *rev_trans_map;
	spinlock_t rev_lock;

	struct rrpc_inflight inflights;

	mempool_t *addr_pool;
	mempool_t *page_pool;
	mempool_t *gcb_pool;
	mempool_t *rq_pool;

	struct timer_list gc_timer;
	struct workqueue_struct *krqd_wq;
	struct workqueue_struct *kgc_wq;
};

struct rrpc_block_gc {
	struct rrpc *rrpc;
	struct rrpc_block *rblk;
	struct work_struct ws_gc;
};

/* Logical to physical mapping */
struct rrpc_addr {
	u64 addr;
	struct rrpc_block *rblk;
};

/* Physical to logical mapping */
struct rrpc_rev_addr {
	u64 addr;
};

static inline struct ppa_addr rrpc_linear_to_generic_addr(struct nvm_geo *geo,
							  struct ppa_addr r)
{
	struct ppa_addr l;
	int secs, pgs;
	sector_t ppa = r.ppa;

	l.ppa = 0;

	div_u64_rem(ppa, geo->sec_per_pg, &secs);
	l.g.sec = secs;

	sector_div(ppa, geo->sec_per_pg);
	div_u64_rem(ppa, geo->pgs_per_blk, &pgs);
	l.g.pg = pgs;

	return l;
}

static inline struct ppa_addr rrpc_recov_addr(struct nvm_tgt_dev *dev, u64 pba)
{
	return linear_to_generic_addr(&dev->geo, pba);
}

static inline u64 rrpc_blk_to_ppa(struct rrpc *rrpc, struct rrpc_block *rblk)
{
	struct nvm_tgt_dev *dev = rrpc->dev;
	struct nvm_geo *geo = &dev->geo;
	struct rrpc_lun *rlun = rblk->rlun;

	return (rlun->id * geo->sec_per_lun) + (rblk->id * geo->sec_per_blk);
}

static inline sector_t rrpc_get_laddr(struct bio *bio)
{
	return bio->bi_iter.bi_sector / NR_PHY_IN_LOG;
}

static inline unsigned int rrpc_get_pages(struct bio *bio)
{
	return  bio->bi_iter.bi_size / RRPC_EXPOSED_PAGE_SIZE;
}

static inline sector_t rrpc_get_sector(sector_t laddr)
{
	return laddr * NR_PHY_IN_LOG;
}

static inline int request_intersects(struct rrpc_inflight_rq *r,
				sector_t laddr_start, sector_t laddr_end)
{
	return (laddr_end >= r->l_start) && (laddr_start <= r->l_end);
}

static int __rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
			     unsigned int pages, struct rrpc_inflight_rq *r)
{
	sector_t laddr_end = laddr + pages - 1;
	struct rrpc_inflight_rq *rtmp;

	WARN_ON(irqs_disabled());

	spin_lock_irq(&rrpc->inflights.lock);
	list_for_each_entry(rtmp, &rrpc->inflights.reqs, list) {
		if (unlikely(request_intersects(rtmp, laddr, laddr_end))) {
			/* existing, overlapping request, come back later */
			spin_unlock_irq(&rrpc->inflights.lock);
			return 1;
		}
	}

	r->l_start = laddr;
	r->l_end = laddr_end;

	list_add_tail(&r->list, &rrpc->inflights.reqs);
	spin_unlock_irq(&rrpc->inflights.lock);
	return 0;
}

static inline int rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
				 unsigned int pages,
				 struct rrpc_inflight_rq *r)
{
	BUG_ON((laddr + pages) > rrpc->nr_sects);

	return __rrpc_lock_laddr(rrpc, laddr, pages, r);
}

static inline struct rrpc_inflight_rq *rrpc_get_inflight_rq(struct nvm_rq *rqd)
{
	struct rrpc_rq *rrqd = nvm_rq_to_pdu(rqd);

	return &rrqd->inflight_rq;
}

static inline int rrpc_lock_rq(struct rrpc *rrpc, struct bio *bio,
							struct nvm_rq *rqd)
{
	sector_t laddr = rrpc_get_laddr(bio);
	unsigned int pages = rrpc_get_pages(bio);
	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);

	return rrpc_lock_laddr(rrpc, laddr, pages, r);
}

static inline void rrpc_unlock_laddr(struct rrpc *rrpc,
						struct rrpc_inflight_rq *r)
{
	unsigned long flags;

	spin_lock_irqsave(&rrpc->inflights.lock, flags);
	list_del_init(&r->list);
	spin_unlock_irqrestore(&rrpc->inflights.lock, flags);
}

static inline void rrpc_unlock_rq(struct rrpc *rrpc, struct nvm_rq *rqd)
{
	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
	uint8_t pages = rqd->nr_ppas;

	BUG_ON((r->l_start + pages) > rrpc->nr_sects);

	rrpc_unlock_laddr(rrpc, r);
}

#endif /* RRPC_H_ */
Commit	Line	Data
ae1519ec MB	1	/*
	2	* Copyright (C) 2015 IT University of Copenhagen
	3	* Initial release: Matias Bjorling <m@bjorling.me>
	4	*
	5	* This program is free software; you can redistribute it and/or
	6	* modify it under the terms of the GNU General Public License version
	7	* 2 as published by the Free Software Foundation.
	8	*
	9	* This program is distributed in the hope that it will be useful, but
	10	* WITHOUT ANY WARRANTY; without even the implied warranty of
	11	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	12	* General Public License for more details.
	13	*
	14	* Implementation of a Round-robin page-based Hybrid FTL for Open-channel SSDs.
	15	*/
	16
	17	#ifndef RRPC_H_
	18	#define RRPC_H_
	19
	20	#include <linux/blkdev.h>
	21	#include <linux/blk-mq.h>
	22	#include <linux/bio.h>
	23	#include <linux/module.h>
	24	#include <linux/kthread.h>
	25	#include <linux/vmalloc.h>
	26
	27	#include <linux/lightnvm.h>
	28
	29	/* Run only GC if less than 1/X blocks are free */
	30	#define GC_LIMIT_INVERSE 10
	31	#define GC_TIME_SECS 100
	32
	33	#define RRPC_SECTOR (512)
	34	#define RRPC_EXPOSED_PAGE_SIZE (4096)
	35
	36	#define NR_PHY_IN_LOG (RRPC_EXPOSED_PAGE_SIZE / RRPC_SECTOR)
	37
	38	struct rrpc_inflight {
	39	struct list_head reqs;
	40	spinlock_t lock;
	41	};
	42
	43	struct rrpc_inflight_rq {
	44	struct list_head list;
	45	sector_t l_start;
	46	sector_t l_end;
	47	};
	48
	49	struct rrpc_rq {
	50	struct rrpc_inflight_rq inflight_rq;
ae1519ec MB	51	unsigned long flags;
	52	};
	53
	54	struct rrpc_block {
2a02e627	55	int id; /* id inside of LUN */
d7a64d27	56	struct rrpc_lun *rlun;
8e79b5cb JG	57
	58	struct list_head prio; /* LUN CG list */
	59	struct list_head list; /* LUN free, used, bb list */
ae1519ec MB	60
	61	#define MAX_INVALID_PAGES_STORAGE 8
	62	/* Bitmap for invalid page intries */
	63	unsigned long invalid_pages[MAX_INVALID_PAGES_STORAGE];
	64	/* points to the next writable page within a block */
	65	unsigned int next_page;
	66	/* number of pages that are invalid, wrt host page size */
	67	unsigned int nr_invalid_pages;
	68
8e79b5cb JG	69	int state;
8e79b5cb JG	70
ae1519ec MB	71	spinlock_t lock;
	72	atomic_t data_cmnt_size; /* data pages committed to stable storage */
	73	};
	74
	75	struct rrpc_lun {
	76	struct rrpc *rrpc;
8e53624d JG	77
	78	int id;
	79	struct ppa_addr bppa;
8e79b5cb	80
ae1519ec MB	81	struct rrpc_block cur, gc_cur;
ae1519ec MB	82	struct rrpc_block blocks; / Reference to block allocation */
ff0e498b JG	83
ff0e498b JG	84	struct list_head prio_list; /* Blocks that may be GC'ed */
855cdd2c	85	struct list_head wblk_list; /* Queued blocks to be written to */
ff0e498b	86
2a02e627 JG	87	/* lun block lists */
	88	struct list_head used_list; /* In-use blocks */
	89	struct list_head free_list; /* Not used blocks i.e. released
	90	* and ready for use
	91	*/
	92	struct list_head bb_list; /* Bad blocks. Mutually exclusive with
	93	* free_list and used_list
	94	*/
	95	unsigned int nr_free_blocks; /* Number of unused blocks */
	96
ae1519ec MB	97	struct work_struct ws_gc;
ae1519ec MB	98
8e79b5cb JG	99	int reserved_blocks;
8e79b5cb JG	100
ae1519ec MB	101	spinlock_t lock;
	102	};
	103
	104	struct rrpc {
	105	/* instance must be kept in top to resolve rrpc in unprep */
	106	struct nvm_tgt_instance instance;
	107
8e79b5cb	108	struct nvm_tgt_dev *dev;
ae1519ec MB	109	struct gendisk *disk;
ae1519ec MB	110
4c9dacb8	111	sector_t soffset; /* logical sector offset */
ae1519ec MB	112
	113	int nr_luns;
	114	struct rrpc_lun *luns;
	115
	116	/* calculated values */
4ece44af	117	unsigned long long nr_sects;
ae1519ec MB	118
	119	/* Write strategy variables. Move these into each for structure for each
	120	* strategy
	121	*/
	122	atomic_t next_lun; /* Whenever a page is written, this is updated
	123	* to point to the next write lun
	124	*/
	125
	126	spinlock_t bio_lock;
	127	struct bio_list requeue_bios;
	128	struct work_struct ws_requeue;
	129
	130	/* Simple translation map of logical addresses to physical addresses.
	131	* The logical addresses is known by the host system, while the physical
	132	* addresses are used when writing to the disk block device.
	133	*/
	134	struct rrpc_addr *trans_map;
	135	/* also store a reverse map for garbage collection */
	136	struct rrpc_rev_addr *rev_trans_map;
	137	spinlock_t rev_lock;
	138
	139	struct rrpc_inflight inflights;
	140
	141	mempool_t *addr_pool;
	142	mempool_t *page_pool;
	143	mempool_t *gcb_pool;
	144	mempool_t *rq_pool;
	145
	146	struct timer_list gc_timer;
	147	struct workqueue_struct *krqd_wq;
	148	struct workqueue_struct *kgc_wq;
	149	};
	150
	151	struct rrpc_block_gc {
	152	struct rrpc *rrpc;
	153	struct rrpc_block *rblk;
	154	struct work_struct ws_gc;
	155	};
	156
	157	/* Logical to physical mapping */
	158	struct rrpc_addr {
b7ceb7d5	159	u64 addr;
ae1519ec MB	160	struct rrpc_block *rblk;
	161	};
	162
	163	/* Physical to logical mapping */
	164	struct rrpc_rev_addr {
b7ceb7d5	165	u64 addr;
ae1519ec MB	166	};
ae1519ec MB	167
8e53624d JG	168	static inline struct ppa_addr rrpc_linear_to_generic_addr(struct nvm_geo *geo,
	169	struct ppa_addr r)
	170	{
	171	struct ppa_addr l;
	172	int secs, pgs;
	173	sector_t ppa = r.ppa;
	174
	175	l.ppa = 0;
	176
	177	div_u64_rem(ppa, geo->sec_per_pg, &secs);
	178	l.g.sec = secs;
	179
	180	sector_div(ppa, geo->sec_per_pg);
	181	div_u64_rem(ppa, geo->pgs_per_blk, &pgs);
	182	l.g.pg = pgs;
	183
	184	return l;
	185	}
	186
da2d7cb8	187	static inline struct ppa_addr rrpc_recov_addr(struct nvm_tgt_dev *dev, u64 pba)
8e53624d JG	188	{
	189	return linear_to_generic_addr(&dev->geo, pba);
	190	}
	191
2a02e627	192	static inline u64 rrpc_blk_to_ppa(struct rrpc rrpc, struct rrpc_block rblk)
afb18e0e	193	{
8e79b5cb	194	struct nvm_tgt_dev *dev = rrpc->dev;
2a02e627 JG	195	struct nvm_geo *geo = &dev->geo;
2a02e627 JG	196	struct rrpc_lun *rlun = rblk->rlun;
afb18e0e	197
8e53624d	198	return (rlun->id * geo->sec_per_lun) + (rblk->id * geo->sec_per_blk);
afb18e0e JG	199	}
afb18e0e JG	200
ae1519ec MB	201	static inline sector_t rrpc_get_laddr(struct bio *bio)
	202	{
	203	return bio->bi_iter.bi_sector / NR_PHY_IN_LOG;
	204	}
	205
	206	static inline unsigned int rrpc_get_pages(struct bio *bio)
	207	{
	208	return bio->bi_iter.bi_size / RRPC_EXPOSED_PAGE_SIZE;
	209	}
	210
	211	static inline sector_t rrpc_get_sector(sector_t laddr)
	212	{
	213	return laddr * NR_PHY_IN_LOG;
	214	}
	215
	216	static inline int request_intersects(struct rrpc_inflight_rq *r,
	217	sector_t laddr_start, sector_t laddr_end)
	218	{
3704e098	219	return (laddr_end >= r->l_start) && (laddr_start <= r->l_end);
ae1519ec MB	220	}
	221
	222	static int __rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
5114e277	223	unsigned int pages, struct rrpc_inflight_rq *r)
ae1519ec MB	224	{
	225	sector_t laddr_end = laddr + pages - 1;
	226	struct rrpc_inflight_rq *rtmp;
	227
bba7f40a JG	228	WARN_ON(irqs_disabled());
bba7f40a JG	229
ae1519ec MB	230	spin_lock_irq(&rrpc->inflights.lock);
	231	list_for_each_entry(rtmp, &rrpc->inflights.reqs, list) {
	232	if (unlikely(request_intersects(rtmp, laddr, laddr_end))) {
	233	/* existing, overlapping request, come back later */
	234	spin_unlock_irq(&rrpc->inflights.lock);
	235	return 1;
	236	}
	237	}
	238
	239	r->l_start = laddr;
	240	r->l_end = laddr_end;
	241
	242	list_add_tail(&r->list, &rrpc->inflights.reqs);
	243	spin_unlock_irq(&rrpc->inflights.lock);
	244	return 0;
	245	}
	246
	247	static inline int rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
5114e277	248	unsigned int pages,
ae1519ec MB	249	struct rrpc_inflight_rq *r)
ae1519ec MB	250	{
4ece44af	251	BUG_ON((laddr + pages) > rrpc->nr_sects);
ae1519ec MB	252
	253	return __rrpc_lock_laddr(rrpc, laddr, pages, r);
	254	}
	255
	256	static inline struct rrpc_inflight_rq rrpc_get_inflight_rq(struct nvm_rq rqd)
	257	{
	258	struct rrpc_rq *rrqd = nvm_rq_to_pdu(rqd);
	259
	260	return &rrqd->inflight_rq;
	261	}
	262
	263	static inline int rrpc_lock_rq(struct rrpc rrpc, struct bio bio,
	264	struct nvm_rq *rqd)
	265	{
	266	sector_t laddr = rrpc_get_laddr(bio);
	267	unsigned int pages = rrpc_get_pages(bio);
	268	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
	269
	270	return rrpc_lock_laddr(rrpc, laddr, pages, r);
	271	}
	272
	273	static inline void rrpc_unlock_laddr(struct rrpc *rrpc,
	274	struct rrpc_inflight_rq *r)
	275	{
	276	unsigned long flags;
	277
	278	spin_lock_irqsave(&rrpc->inflights.lock, flags);
	279	list_del_init(&r->list);
	280	spin_unlock_irqrestore(&rrpc->inflights.lock, flags);
	281	}
	282
	283	static inline void rrpc_unlock_rq(struct rrpc rrpc, struct nvm_rq rqd)
	284	{
	285	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
6d5be959	286	uint8_t pages = rqd->nr_ppas;
ae1519ec	287
4ece44af	288	BUG_ON((r->l_start + pages) > rrpc->nr_sects);
ae1519ec MB	289
	290	rrpc_unlock_laddr(rrpc, r);
	291	}
	292
	293	#endif /* RRPC_H_ */