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	struct rrpc_addr *addr;
 52	unsigned long flags;
 53};
 54
 55struct rrpc_block {
 56	struct nvm_block *parent;
 57	struct rrpc_lun *rlun;
 58	struct list_head prio;
 59	struct list_head 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	spinlock_t lock;
 70	atomic_t data_cmnt_size; /* data pages committed to stable storage */
 71};
 72
 73struct rrpc_lun {
 74	struct rrpc *rrpc;
 75	struct nvm_lun *parent;
 76	struct rrpc_block *cur, *gc_cur;
 77	struct rrpc_block *blocks;	/* Reference to block allocation */
 78
 79	struct list_head prio_list;	/* Blocks that may be GC'ed */
 80	struct list_head open_list;	/* In-use open blocks. These are blocks
 81					 * that can be both written to and read
 82					 * from
 83					 */
 84	struct list_head closed_list;	/* In-use closed blocks. These are
 85					 * blocks that can _only_ be read from
 86					 */
 87
 88	struct work_struct ws_gc;
 89
 90	spinlock_t lock;
 91};
 92
 93struct rrpc {
 94	/* instance must be kept in top to resolve rrpc in unprep */
 95	struct nvm_tgt_instance instance;
 96
 97	struct nvm_dev *dev;
 98	struct gendisk *disk;
 99
100	sector_t soffset; /* logical sector offset */
101	u64 poffset; /* physical page offset */
102	int lun_offset;
103
104	int nr_luns;
105	struct rrpc_lun *luns;
106
107	/* calculated values */
108	unsigned long long nr_sects;
109	unsigned long total_blocks;
110
111	/* Write strategy variables. Move these into each for structure for each
112	 * strategy
113	 */
114	atomic_t next_lun; /* Whenever a page is written, this is updated
115			    * to point to the next write lun
116			    */
117
118	spinlock_t bio_lock;
119	struct bio_list requeue_bios;
120	struct work_struct ws_requeue;
121
122	/* Simple translation map of logical addresses to physical addresses.
123	 * The logical addresses is known by the host system, while the physical
124	 * addresses are used when writing to the disk block device.
125	 */
126	struct rrpc_addr *trans_map;
127	/* also store a reverse map for garbage collection */
128	struct rrpc_rev_addr *rev_trans_map;
129	spinlock_t rev_lock;
130
131	struct rrpc_inflight inflights;
132
133	mempool_t *addr_pool;
134	mempool_t *page_pool;
135	mempool_t *gcb_pool;
136	mempool_t *rq_pool;
137
138	struct timer_list gc_timer;
139	struct workqueue_struct *krqd_wq;
140	struct workqueue_struct *kgc_wq;
141};
142
143struct rrpc_block_gc {
144	struct rrpc *rrpc;
145	struct rrpc_block *rblk;
146	struct work_struct ws_gc;
147};
148
149/* Logical to physical mapping */
150struct rrpc_addr {
151	u64 addr;
152	struct rrpc_block *rblk;
153};
154
155/* Physical to logical mapping */
156struct rrpc_rev_addr {
157	u64 addr;
158};
159
160static inline struct rrpc_block *rrpc_get_rblk(struct rrpc_lun *rlun,
161								int blk_id)
162{
163	struct rrpc *rrpc = rlun->rrpc;
164	int lun_blk = blk_id % rrpc->dev->blks_per_lun;
165
166	return &rlun->blocks[lun_blk];
167}
168
169static inline sector_t rrpc_get_laddr(struct bio *bio)
170{
171	return bio->bi_iter.bi_sector / NR_PHY_IN_LOG;
172}
173
174static inline unsigned int rrpc_get_pages(struct bio *bio)
175{
176	return  bio->bi_iter.bi_size / RRPC_EXPOSED_PAGE_SIZE;
177}
178
179static inline sector_t rrpc_get_sector(sector_t laddr)
180{
181	return laddr * NR_PHY_IN_LOG;
182}
183
184static inline int request_intersects(struct rrpc_inflight_rq *r,
185				sector_t laddr_start, sector_t laddr_end)
186{
187	return (laddr_end >= r->l_start) && (laddr_start <= r->l_end);
188}
189
190static int __rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
191			     unsigned pages, struct rrpc_inflight_rq *r)
192{
193	sector_t laddr_end = laddr + pages - 1;
194	struct rrpc_inflight_rq *rtmp;
195
196	WARN_ON(irqs_disabled());
197
198	spin_lock_irq(&rrpc->inflights.lock);
199	list_for_each_entry(rtmp, &rrpc->inflights.reqs, list) {
200		if (unlikely(request_intersects(rtmp, laddr, laddr_end))) {
201			/* existing, overlapping request, come back later */
202			spin_unlock_irq(&rrpc->inflights.lock);
203			return 1;
204		}
205	}
206
207	r->l_start = laddr;
208	r->l_end = laddr_end;
209
210	list_add_tail(&r->list, &rrpc->inflights.reqs);
211	spin_unlock_irq(&rrpc->inflights.lock);
212	return 0;
213}
214
215static inline int rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
216				 unsigned pages,
217				 struct rrpc_inflight_rq *r)
218{
219	BUG_ON((laddr + pages) > rrpc->nr_sects);
220
221	return __rrpc_lock_laddr(rrpc, laddr, pages, r);
222}
223
224static inline struct rrpc_inflight_rq *rrpc_get_inflight_rq(struct nvm_rq *rqd)
225{
226	struct rrpc_rq *rrqd = nvm_rq_to_pdu(rqd);
227
228	return &rrqd->inflight_rq;
229}
230
231static inline int rrpc_lock_rq(struct rrpc *rrpc, struct bio *bio,
232							struct nvm_rq *rqd)
233{
234	sector_t laddr = rrpc_get_laddr(bio);
235	unsigned int pages = rrpc_get_pages(bio);
236	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
237
238	return rrpc_lock_laddr(rrpc, laddr, pages, r);
239}
240
241static inline void rrpc_unlock_laddr(struct rrpc *rrpc,
242						struct rrpc_inflight_rq *r)
243{
244	unsigned long flags;
245
246	spin_lock_irqsave(&rrpc->inflights.lock, flags);
247	list_del_init(&r->list);
248	spin_unlock_irqrestore(&rrpc->inflights.lock, flags);
249}
250
251static inline void rrpc_unlock_rq(struct rrpc *rrpc, struct nvm_rq *rqd)
252{
253	struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
254	uint8_t pages = rqd->nr_pages;
255
256	BUG_ON((r->l_start + pages) > rrpc->nr_sects);
257
258	rrpc_unlock_laddr(rrpc, r);
259}
260
261#endif /* RRPC_H_ */