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
;
51 struct rrpc_addr
*addr
;
56 struct nvm_block
*parent
;
57 struct rrpc_lun
*rlun
;
58 struct list_head prio
;
59 struct list_head 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
;
70 atomic_t data_cmnt_size
; /* data pages committed to stable storage */
75 struct nvm_lun
*parent
;
76 struct rrpc_block
*cur
, *gc_cur
;
77 struct rrpc_block
*blocks
; /* Reference to block allocation */
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
84 struct list_head closed_list
; /* In-use closed blocks. These are
85 * blocks that can _only_ be read from
88 struct work_struct ws_gc
;
94 /* instance must be kept in top to resolve rrpc in unprep */
95 struct nvm_tgt_instance instance
;
100 u64 poffset
; /* physical page offset */
104 struct rrpc_lun
*luns
;
106 /* calculated values */
107 unsigned long long nr_pages
;
108 unsigned long total_blocks
;
110 /* Write strategy variables. Move these into each for structure for each
113 atomic_t next_lun
; /* Whenever a page is written, this is updated
114 * to point to the next write lun
118 struct bio_list requeue_bios
;
119 struct work_struct ws_requeue
;
121 /* Simple translation map of logical addresses to physical addresses.
122 * The logical addresses is known by the host system, while the physical
123 * addresses are used when writing to the disk block device.
125 struct rrpc_addr
*trans_map
;
126 /* also store a reverse map for garbage collection */
127 struct rrpc_rev_addr
*rev_trans_map
;
130 struct rrpc_inflight inflights
;
132 mempool_t
*addr_pool
;
133 mempool_t
*page_pool
;
137 struct timer_list gc_timer
;
138 struct workqueue_struct
*krqd_wq
;
139 struct workqueue_struct
*kgc_wq
;
142 struct rrpc_block_gc
{
144 struct rrpc_block
*rblk
;
145 struct work_struct ws_gc
;
148 /* Logical to physical mapping */
151 struct rrpc_block
*rblk
;
154 /* Physical to logical mapping */
155 struct rrpc_rev_addr
{
159 static inline sector_t
rrpc_get_laddr(struct bio
*bio
)
161 return bio
->bi_iter
.bi_sector
/ NR_PHY_IN_LOG
;
164 static inline unsigned int rrpc_get_pages(struct bio
*bio
)
166 return bio
->bi_iter
.bi_size
/ RRPC_EXPOSED_PAGE_SIZE
;
169 static inline sector_t
rrpc_get_sector(sector_t laddr
)
171 return laddr
* NR_PHY_IN_LOG
;
174 static inline int request_intersects(struct rrpc_inflight_rq
*r
,
175 sector_t laddr_start
, sector_t laddr_end
)
177 return (laddr_end
>= r
->l_start
) && (laddr_start
<= r
->l_end
);
180 static int __rrpc_lock_laddr(struct rrpc
*rrpc
, sector_t laddr
,
181 unsigned pages
, struct rrpc_inflight_rq
*r
)
183 sector_t laddr_end
= laddr
+ pages
- 1;
184 struct rrpc_inflight_rq
*rtmp
;
186 WARN_ON(irqs_disabled());
188 spin_lock_irq(&rrpc
->inflights
.lock
);
189 list_for_each_entry(rtmp
, &rrpc
->inflights
.reqs
, list
) {
190 if (unlikely(request_intersects(rtmp
, laddr
, laddr_end
))) {
191 /* existing, overlapping request, come back later */
192 spin_unlock_irq(&rrpc
->inflights
.lock
);
198 r
->l_end
= laddr_end
;
200 list_add_tail(&r
->list
, &rrpc
->inflights
.reqs
);
201 spin_unlock_irq(&rrpc
->inflights
.lock
);
205 static inline int rrpc_lock_laddr(struct rrpc
*rrpc
, sector_t laddr
,
207 struct rrpc_inflight_rq
*r
)
209 BUG_ON((laddr
+ pages
) > rrpc
->nr_pages
);
211 return __rrpc_lock_laddr(rrpc
, laddr
, pages
, r
);
214 static inline struct rrpc_inflight_rq
*rrpc_get_inflight_rq(struct nvm_rq
*rqd
)
216 struct rrpc_rq
*rrqd
= nvm_rq_to_pdu(rqd
);
218 return &rrqd
->inflight_rq
;
221 static inline int rrpc_lock_rq(struct rrpc
*rrpc
, struct bio
*bio
,
224 sector_t laddr
= rrpc_get_laddr(bio
);
225 unsigned int pages
= rrpc_get_pages(bio
);
226 struct rrpc_inflight_rq
*r
= rrpc_get_inflight_rq(rqd
);
228 return rrpc_lock_laddr(rrpc
, laddr
, pages
, r
);
231 static inline void rrpc_unlock_laddr(struct rrpc
*rrpc
,
232 struct rrpc_inflight_rq
*r
)
236 spin_lock_irqsave(&rrpc
->inflights
.lock
, flags
);
237 list_del_init(&r
->list
);
238 spin_unlock_irqrestore(&rrpc
->inflights
.lock
, flags
);
241 static inline void rrpc_unlock_rq(struct rrpc
*rrpc
, struct nvm_rq
*rqd
)
243 struct rrpc_inflight_rq
*r
= rrpc_get_inflight_rq(rqd
);
244 uint8_t pages
= rqd
->nr_pages
;
246 BUG_ON((r
->l_start
+ pages
) > rrpc
->nr_pages
);
248 rrpc_unlock_laddr(rrpc
, r
);