2 * Copyright (C) 2015 IT University of Copenhagen
3 * Initial release: Matias Bjorling <m@bjorling.me>
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.
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.
14 * Implementation of a Round-robin page-based Hybrid FTL for Open-channel SSDs.
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>
27 #include <linux/lightnvm.h>
29 /* Run only GC if less than 1/X blocks are free */
30 #define GC_LIMIT_INVERSE 10
31 #define GC_TIME_SECS 100
33 #define RRPC_SECTOR (512)
34 #define RRPC_EXPOSED_PAGE_SIZE (4096)
36 #define NR_PHY_IN_LOG (RRPC_EXPOSED_PAGE_SIZE / RRPC_SECTOR)
38 struct rrpc_inflight {
39 struct list_head reqs;
43 struct rrpc_inflight_rq {
44 struct list_head list;
50 struct rrpc_inflight_rq inflight_rq;
55 int id; /* id inside of LUN */
56 struct rrpc_lun *rlun;
58 struct list_head prio; /* LUN CG list */
59 struct list_head list; /* LUN free, used, bb list */
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;
72 atomic_t data_cmnt_size; /* data pages committed to stable storage */
77 struct nvm_lun *parent;
79 struct rrpc_block *cur, *gc_cur;
80 struct rrpc_block *blocks; /* Reference to block allocation */
82 struct list_head prio_list; /* Blocks that may be GC'ed */
83 struct list_head wblk_list; /* Queued blocks to be written to */
86 struct list_head used_list; /* In-use blocks */
87 struct list_head free_list; /* Not used blocks i.e. released
90 struct list_head bb_list; /* Bad blocks. Mutually exclusive with
91 * free_list and used_list
93 unsigned int nr_free_blocks; /* Number of unused blocks */
95 struct work_struct ws_gc;
103 /* instance must be kept in top to resolve rrpc in unprep */
104 struct nvm_tgt_instance instance;
106 struct nvm_tgt_dev *dev;
107 struct gendisk *disk;
109 sector_t soffset; /* logical sector offset */
110 u64 poffset; /* physical page offset */
113 struct rrpc_lun *luns;
115 /* calculated values */
116 unsigned long long nr_sects;
118 /* Write strategy variables. Move these into each for structure for each
121 atomic_t next_lun; /* Whenever a page is written, this is updated
122 * to point to the next write lun
126 struct bio_list requeue_bios;
127 struct work_struct ws_requeue;
129 /* Simple translation map of logical addresses to physical addresses.
130 * The logical addresses is known by the host system, while the physical
131 * addresses are used when writing to the disk block device.
133 struct rrpc_addr *trans_map;
134 /* also store a reverse map for garbage collection */
135 struct rrpc_rev_addr *rev_trans_map;
138 struct rrpc_inflight inflights;
140 mempool_t *addr_pool;
141 mempool_t *page_pool;
145 struct timer_list gc_timer;
146 struct workqueue_struct *krqd_wq;
147 struct workqueue_struct *kgc_wq;
150 struct rrpc_block_gc {
152 struct rrpc_block *rblk;
153 struct work_struct ws_gc;
156 /* Logical to physical mapping */
159 struct rrpc_block *rblk;
162 /* Physical to logical mapping */
163 struct rrpc_rev_addr {
167 static inline u64 rrpc_blk_to_ppa(struct rrpc *rrpc, struct rrpc_block *rblk)
169 struct nvm_tgt_dev *dev = rrpc->dev;
170 struct nvm_geo *geo = &dev->geo;
171 struct rrpc_lun *rlun = rblk->rlun;
172 struct nvm_lun *lun = rlun->parent;
174 return (lun->id * geo->sec_per_lun) + (rblk->id * geo->sec_per_blk);
177 static inline sector_t rrpc_get_laddr(struct bio *bio)
179 return bio->bi_iter.bi_sector / NR_PHY_IN_LOG;
182 static inline unsigned int rrpc_get_pages(struct bio *bio)
184 return bio->bi_iter.bi_size / RRPC_EXPOSED_PAGE_SIZE;
187 static inline sector_t rrpc_get_sector(sector_t laddr)
189 return laddr * NR_PHY_IN_LOG;
192 static inline int request_intersects(struct rrpc_inflight_rq *r,
193 sector_t laddr_start, sector_t laddr_end)
195 return (laddr_end >= r->l_start) && (laddr_start <= r->l_end);
198 static int __rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
199 unsigned int pages, struct rrpc_inflight_rq *r)
201 sector_t laddr_end = laddr + pages - 1;
202 struct rrpc_inflight_rq *rtmp;
204 WARN_ON(irqs_disabled());
206 spin_lock_irq(&rrpc->inflights.lock);
207 list_for_each_entry(rtmp, &rrpc->inflights.reqs, list) {
208 if (unlikely(request_intersects(rtmp, laddr, laddr_end))) {
209 /* existing, overlapping request, come back later */
210 spin_unlock_irq(&rrpc->inflights.lock);
216 r->l_end = laddr_end;
218 list_add_tail(&r->list, &rrpc->inflights.reqs);
219 spin_unlock_irq(&rrpc->inflights.lock);
223 static inline int rrpc_lock_laddr(struct rrpc *rrpc, sector_t laddr,
225 struct rrpc_inflight_rq *r)
227 BUG_ON((laddr + pages) > rrpc->nr_sects);
229 return __rrpc_lock_laddr(rrpc, laddr, pages, r);
232 static inline struct rrpc_inflight_rq *rrpc_get_inflight_rq(struct nvm_rq *rqd)
234 struct rrpc_rq *rrqd = nvm_rq_to_pdu(rqd);
236 return &rrqd->inflight_rq;
239 static inline int rrpc_lock_rq(struct rrpc *rrpc, struct bio *bio,
242 sector_t laddr = rrpc_get_laddr(bio);
243 unsigned int pages = rrpc_get_pages(bio);
244 struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
246 return rrpc_lock_laddr(rrpc, laddr, pages, r);
249 static inline void rrpc_unlock_laddr(struct rrpc *rrpc,
250 struct rrpc_inflight_rq *r)
254 spin_lock_irqsave(&rrpc->inflights.lock, flags);
255 list_del_init(&r->list);
256 spin_unlock_irqrestore(&rrpc->inflights.lock, flags);
259 static inline void rrpc_unlock_rq(struct rrpc *rrpc, struct nvm_rq *rqd)
261 struct rrpc_inflight_rq *r = rrpc_get_inflight_rq(rqd);
262 uint8_t pages = rqd->nr_ppas;
264 BUG_ON((r->l_start + pages) > rrpc->nr_sects);
266 rrpc_unlock_laddr(rrpc, r);