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
 38struct rrpc_inflight {
 39	struct list_head reqs;
 40	spinlock_t lock;
 41};
 42
 43struct rrpc_inflight_rq {
 44	struct list_head list;
 45	sector_t l_start;
 46	sector_t l_end;
 47};
 48
 49struct rrpc_rq {
 50	struct rrpc_inflight_rq inflight_rq;
 51	unsigned long flags;
 52};
 53
 54struct rrpc_block {
 55	int id;				/* id inside of LUN */
 56	struct rrpc_lun *rlun;
 57
 58	struct list_head prio;		/* LUN CG list */
 59	struct list_head list;		/* LUN free, used, bb list */
 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
 69	int state;
 70
 71	spinlock_t lock;
 72	atomic_t data_cmnt_size; /* data pages committed to stable storage */
 73};
 74
 75struct rrpc_lun {
 76	struct rrpc *rrpc;
 77
 78	int id;
 79	struct ppa_addr bppa;
 80
 81	struct rrpc_block *cur, *gc_cur;
 82	struct rrpc_block *blocks;	/* Reference to block allocation */
 83
 84	struct list_head prio_list;	/* Blocks that may be GC'ed */
 85	struct list_head wblk_list;	/* Queued blocks to be written to */
 86
 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
 97	struct work_struct ws_gc;
 98
 99	int reserved_blocks;
100
101	spinlock_t lock;
102};
103
104struct rrpc {
105	/* instance must be kept in top to resolve rrpc in unprep */
106	struct nvm_tgt_instance instance;
107
108	struct nvm_tgt_dev *dev;
109	struct gendisk *disk;
110
111	sector_t soffset; /* logical sector offset */
112
113	int nr_luns;
114	struct rrpc_lun *luns;
115
116	/* calculated values */
117	unsigned long long nr_sects;
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
151struct 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 */
158struct rrpc_addr {
159	u64 addr;
160	struct rrpc_block *rblk;
161};
162
163/* Physical to logical mapping */
164struct rrpc_rev_addr {
165	u64 addr;
166};
167
168static 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
187static inline struct ppa_addr rrpc_recov_addr(struct nvm_tgt_dev *dev, u64 pba)
188{
189	return linear_to_generic_addr(&dev->geo, pba);
190}
191
192static inline u64 rrpc_blk_to_ppa(struct rrpc *rrpc, struct rrpc_block *rblk)
193{
194	struct nvm_tgt_dev *dev = rrpc->dev;
195	struct nvm_geo *geo = &dev->geo;
196	struct rrpc_lun *rlun = rblk->rlun;
197
198	return (rlun->id * geo->sec_per_lun) + (rblk->id * geo->sec_per_blk);
199}
200
201static inline sector_t rrpc_get_laddr(struct bio *bio)
202{
203	return bio->bi_iter.bi_sector / NR_PHY_IN_LOG;
204}
205
206static inline unsigned int rrpc_get_pages(struct bio *bio)
207{
208	return  bio->bi_iter.bi_size / RRPC_EXPOSED_PAGE_SIZE;
209}
210
211static inline sector_t rrpc_get_sector(sector_t laddr)
212{
213	return laddr * NR_PHY_IN_LOG;
214}
215
216static inline int request_intersects(struct rrpc_inflight_rq *r,
217				sector_t laddr_start, sector_t laddr_end)
218{
219	return (laddr_end >= r->l_start) && (laddr_start <= r->l_end);
220}
221
222static int __rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
223			     unsigned int pages, struct rrpc_inflight_rq *r)
224{
225	sector_t laddr_end = laddr + pages - 1;
226	struct rrpc_inflight_rq *rtmp;
227
228	WARN_ON(irqs_disabled());
229
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
247static inline int rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
248				 unsigned int pages,
249				 struct rrpc_inflight_rq *r)
250{
251	BUG_ON((laddr + pages) > rrpc->nr_sects);
252
253	return __rrpc_lock_laddr(rrpc, laddr, pages, r);
254}
255
256static 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
263static 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
273static 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
283static inline void rrpc_unlock_rq(struct rrpc *rrpc, struct nvm_rq *rqd)
284{
285	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
286	uint8_t pages = rqd->nr_ppas;
287
288	BUG_ON((r->l_start + pages) > rrpc->nr_sects);
289
290	rrpc_unlock_laddr(rrpc, r);
291}
292
293#endif /* RRPC_H_ */