2 * Copyright (C) 2016 CNEX Labs
3 * Initial release: Javier Gonzalez <javier@cnexlabs.com>
5 * Based upon the circular ringbuffer.
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License version
9 * 2 as published by the Free Software Foundation.
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * pblk-rb.c - pblk's write buffer
19 #include <linux/circ_buf.h>
23 static DECLARE_RWSEM(pblk_rb_lock);
25 void pblk_rb_data_free(struct pblk_rb *rb)
27 struct pblk_rb_pages *p, *t;
29 down_write(&pblk_rb_lock);
30 list_for_each_entry_safe(p, t, &rb->pages, list) {
31 free_pages((unsigned long)page_address(p->pages), p->order);
35 up_write(&pblk_rb_lock);
39 * Initialize ring buffer. The data and metadata buffers must be previously
40 * allocated and their size must be a power of two
41 * (Documentation/circular-buffers.txt)
43 int pblk_rb_init(struct pblk_rb *rb, struct pblk_rb_entry *rb_entry_base,
44 unsigned int power_size, unsigned int power_seg_sz)
46 struct pblk *pblk = container_of(rb, struct pblk, rwb);
47 unsigned int init_entry = 0;
48 unsigned int alloc_order = power_size;
49 unsigned int max_order = MAX_ORDER - 1;
50 unsigned int order, iter;
52 down_write(&pblk_rb_lock);
53 rb->entries = rb_entry_base;
54 rb->seg_size = (1 << power_seg_sz);
55 rb->nr_entries = (1 << power_size);
56 rb->mem = rb->subm = rb->sync = rb->l2p_update = 0;
57 rb->sync_point = EMPTY_ENTRY;
59 spin_lock_init(&rb->w_lock);
60 spin_lock_init(&rb->s_lock);
62 INIT_LIST_HEAD(&rb->pages);
64 if (alloc_order >= max_order) {
66 iter = (1 << (alloc_order - max_order));
73 struct pblk_rb_entry *entry;
74 struct pblk_rb_pages *page_set;
76 unsigned long set_size;
79 page_set = kmalloc(sizeof(struct pblk_rb_pages), GFP_KERNEL);
81 up_write(&pblk_rb_lock);
85 page_set->order = order;
86 page_set->pages = alloc_pages(GFP_KERNEL, order);
87 if (!page_set->pages) {
89 pblk_rb_data_free(rb);
90 up_write(&pblk_rb_lock);
93 kaddr = page_address(page_set->pages);
95 entry = &rb->entries[init_entry];
97 entry->cacheline = pblk_cacheline_to_addr(init_entry++);
98 entry->w_ctx.flags = PBLK_WRITABLE_ENTRY;
100 set_size = (1 << order);
101 for (i = 1; i < set_size; i++) {
102 entry = &rb->entries[init_entry];
103 entry->cacheline = pblk_cacheline_to_addr(init_entry++);
104 entry->data = kaddr + (i * rb->seg_size);
105 entry->w_ctx.flags = PBLK_WRITABLE_ENTRY;
106 bio_list_init(&entry->w_ctx.bios);
109 list_add_tail(&page_set->list, &rb->pages);
112 up_write(&pblk_rb_lock);
114 #ifdef CONFIG_NVM_DEBUG
115 atomic_set(&rb->inflight_sync_point, 0);
119 * Initialize rate-limiter, which controls access to the write buffer
120 * but user and GC I/O
122 pblk_rl_init(&pblk->rl, rb->nr_entries);
128 * pblk_rb_calculate_size -- calculate the size of the write buffer
130 unsigned int pblk_rb_calculate_size(unsigned int nr_entries)
132 /* Alloc a write buffer that can at least fit 128 entries */
133 return (1 << max(get_count_order(nr_entries), 7));
136 void *pblk_rb_entries_ref(struct pblk_rb *rb)
141 static void clean_wctx(struct pblk_w_ctx *w_ctx)
146 flags = READ_ONCE(w_ctx->flags);
147 if (!(flags & PBLK_SUBMITTED_ENTRY))
150 /* Release flags on context. Protect from writes and reads */
151 smp_store_release(&w_ctx->flags, PBLK_WRITABLE_ENTRY);
152 pblk_ppa_set_empty(&w_ctx->ppa);
155 #define pblk_rb_ring_count(head, tail, size) CIRC_CNT(head, tail, size)
156 #define pblk_rb_ring_space(rb, head, tail, size) \
157 (CIRC_SPACE(head, tail, size))
160 * Buffer space is calculated with respect to the back pointer signaling
161 * synchronized entries to the media.
163 static unsigned int pblk_rb_space(struct pblk_rb *rb)
165 unsigned int mem = READ_ONCE(rb->mem);
166 unsigned int sync = READ_ONCE(rb->sync);
168 return pblk_rb_ring_space(rb, mem, sync, rb->nr_entries);
172 * Buffer count is calculated with respect to the submission entry signaling the
173 * entries that are available to send to the media
175 unsigned int pblk_rb_read_count(struct pblk_rb *rb)
177 unsigned int mem = READ_ONCE(rb->mem);
178 unsigned int subm = READ_ONCE(rb->subm);
180 return pblk_rb_ring_count(mem, subm, rb->nr_entries);
183 unsigned int pblk_rb_read_commit(struct pblk_rb *rb, unsigned int nr_entries)
187 subm = READ_ONCE(rb->subm);
188 /* Commit read means updating submission pointer */
189 smp_store_release(&rb->subm,
190 (subm + nr_entries) & (rb->nr_entries - 1));
195 static int __pblk_rb_update_l2p(struct pblk_rb *rb, unsigned int *l2p_upd,
196 unsigned int to_update)
198 struct pblk *pblk = container_of(rb, struct pblk, rwb);
199 struct pblk_line *line;
200 struct pblk_rb_entry *entry;
201 struct pblk_w_ctx *w_ctx;
202 unsigned int user_io = 0, gc_io = 0;
206 for (i = 0; i < to_update; i++) {
207 entry = &rb->entries[*l2p_upd];
208 w_ctx = &entry->w_ctx;
210 flags = READ_ONCE(entry->w_ctx.flags);
211 if (flags & PBLK_IOTYPE_USER)
213 else if (flags & PBLK_IOTYPE_GC)
216 WARN(1, "pblk: unknown IO type\n");
218 pblk_update_map_dev(pblk, w_ctx->lba, w_ctx->ppa,
221 line = &pblk->lines[pblk_tgt_ppa_to_line(w_ctx->ppa)];
222 kref_put(&line->ref, pblk_line_put);
224 *l2p_upd = (*l2p_upd + 1) & (rb->nr_entries - 1);
227 pblk_rl_out(&pblk->rl, user_io, gc_io);
233 * When we move the l2p_update pointer, we update the l2p table - lookups will
234 * point to the physical address instead of to the cacheline in the write buffer
235 * from this moment on.
237 static int pblk_rb_update_l2p(struct pblk_rb *rb, unsigned int nr_entries,
238 unsigned int mem, unsigned int sync)
240 unsigned int space, count;
243 lockdep_assert_held(&rb->w_lock);
245 /* Update l2p only as buffer entries are being overwritten */
246 space = pblk_rb_ring_space(rb, mem, rb->l2p_update, rb->nr_entries);
247 if (space > nr_entries)
250 count = nr_entries - space;
251 /* l2p_update used exclusively under rb->w_lock */
252 ret = __pblk_rb_update_l2p(rb, &rb->l2p_update, count);
259 * Update the l2p entry for all sectors stored on the write buffer. This means
260 * that all future lookups to the l2p table will point to a device address, not
261 * to the cacheline in the write buffer.
263 void pblk_rb_sync_l2p(struct pblk_rb *rb)
266 unsigned int to_update;
268 spin_lock(&rb->w_lock);
270 /* Protect from reads and writes */
271 sync = smp_load_acquire(&rb->sync);
273 to_update = pblk_rb_ring_count(sync, rb->l2p_update, rb->nr_entries);
274 __pblk_rb_update_l2p(rb, &rb->l2p_update, to_update);
276 spin_unlock(&rb->w_lock);
280 * Write @nr_entries to ring buffer from @data buffer if there is enough space.
281 * Typically, 4KB data chunks coming from a bio will be copied to the ring
282 * buffer, thus the write will fail if not all incoming data can be copied.
285 static void __pblk_rb_write_entry(struct pblk_rb *rb, void *data,
286 struct pblk_w_ctx w_ctx,
287 struct pblk_rb_entry *entry)
289 memcpy(entry->data, data, rb->seg_size);
291 entry->w_ctx.lba = w_ctx.lba;
292 entry->w_ctx.ppa = w_ctx.ppa;
295 void pblk_rb_write_entry_user(struct pblk_rb *rb, void *data,
296 struct pblk_w_ctx w_ctx, unsigned int ring_pos)
298 struct pblk *pblk = container_of(rb, struct pblk, rwb);
299 struct pblk_rb_entry *entry;
302 entry = &rb->entries[ring_pos];
303 flags = READ_ONCE(entry->w_ctx.flags);
304 #ifdef CONFIG_NVM_DEBUG
305 /* Caller must guarantee that the entry is free */
306 BUG_ON(!(flags & PBLK_WRITABLE_ENTRY));
309 __pblk_rb_write_entry(rb, data, w_ctx, entry);
311 pblk_update_map_cache(pblk, w_ctx.lba, entry->cacheline);
312 flags = w_ctx.flags | PBLK_WRITTEN_DATA;
314 /* Release flags on write context. Protect from writes */
315 smp_store_release(&entry->w_ctx.flags, flags);
318 void pblk_rb_write_entry_gc(struct pblk_rb *rb, void *data,
319 struct pblk_w_ctx w_ctx, struct pblk_line *gc_line,
320 unsigned int ring_pos)
322 struct pblk *pblk = container_of(rb, struct pblk, rwb);
323 struct pblk_rb_entry *entry;
326 entry = &rb->entries[ring_pos];
327 flags = READ_ONCE(entry->w_ctx.flags);
328 #ifdef CONFIG_NVM_DEBUG
329 /* Caller must guarantee that the entry is free */
330 BUG_ON(!(flags & PBLK_WRITABLE_ENTRY));
333 __pblk_rb_write_entry(rb, data, w_ctx, entry);
335 if (!pblk_update_map_gc(pblk, w_ctx.lba, entry->cacheline, gc_line))
336 entry->w_ctx.lba = ADDR_EMPTY;
338 flags = w_ctx.flags | PBLK_WRITTEN_DATA;
340 /* Release flags on write context. Protect from writes */
341 smp_store_release(&entry->w_ctx.flags, flags);
344 static int pblk_rb_sync_point_set(struct pblk_rb *rb, struct bio *bio,
347 struct pblk_rb_entry *entry;
348 unsigned int subm, sync_point;
351 subm = READ_ONCE(rb->subm);
353 #ifdef CONFIG_NVM_DEBUG
354 atomic_inc(&rb->inflight_sync_point);
360 sync_point = (pos == 0) ? (rb->nr_entries - 1) : (pos - 1);
361 entry = &rb->entries[sync_point];
363 flags = READ_ONCE(entry->w_ctx.flags);
364 flags |= PBLK_FLUSH_ENTRY;
366 /* Release flags on context. Protect from writes */
367 smp_store_release(&entry->w_ctx.flags, flags);
370 smp_store_release(&rb->sync_point, sync_point);
375 spin_lock_irq(&rb->s_lock);
376 bio_list_add(&entry->w_ctx.bios, bio);
377 spin_unlock_irq(&rb->s_lock);
382 static int __pblk_rb_may_write(struct pblk_rb *rb, unsigned int nr_entries,
388 sync = READ_ONCE(rb->sync);
389 mem = READ_ONCE(rb->mem);
391 if (pblk_rb_ring_space(rb, mem, sync, rb->nr_entries) < nr_entries)
394 if (pblk_rb_update_l2p(rb, nr_entries, mem, sync))
402 static int pblk_rb_may_write(struct pblk_rb *rb, unsigned int nr_entries,
405 if (!__pblk_rb_may_write(rb, nr_entries, pos))
408 /* Protect from read count */
409 smp_store_release(&rb->mem, (*pos + nr_entries) & (rb->nr_entries - 1));
413 void pblk_rb_flush(struct pblk_rb *rb)
415 struct pblk *pblk = container_of(rb, struct pblk, rwb);
416 unsigned int mem = READ_ONCE(rb->mem);
418 if (pblk_rb_sync_point_set(rb, NULL, mem))
421 pblk_write_should_kick(pblk);
424 static int pblk_rb_may_write_flush(struct pblk_rb *rb, unsigned int nr_entries,
425 unsigned int *pos, struct bio *bio,
430 if (!__pblk_rb_may_write(rb, nr_entries, pos))
433 mem = (*pos + nr_entries) & (rb->nr_entries - 1);
434 *io_ret = NVM_IO_DONE;
436 if (bio->bi_opf & REQ_PREFLUSH) {
437 struct pblk *pblk = container_of(rb, struct pblk, rwb);
439 #ifdef CONFIG_NVM_DEBUG
440 atomic_long_inc(&pblk->nr_flush);
442 if (pblk_rb_sync_point_set(&pblk->rwb, bio, mem))
446 /* Protect from read count */
447 smp_store_release(&rb->mem, mem);
452 * Atomically check that (i) there is space on the write buffer for the
453 * incoming I/O, and (ii) the current I/O type has enough budget in the write
454 * buffer (rate-limiter).
456 int pblk_rb_may_write_user(struct pblk_rb *rb, struct bio *bio,
457 unsigned int nr_entries, unsigned int *pos)
459 struct pblk *pblk = container_of(rb, struct pblk, rwb);
462 spin_lock(&rb->w_lock);
463 io_ret = pblk_rl_user_may_insert(&pblk->rl, nr_entries);
465 spin_unlock(&rb->w_lock);
469 if (!pblk_rb_may_write_flush(rb, nr_entries, pos, bio, &io_ret)) {
470 spin_unlock(&rb->w_lock);
471 return NVM_IO_REQUEUE;
474 pblk_rl_user_in(&pblk->rl, nr_entries);
475 spin_unlock(&rb->w_lock);
481 * Look at pblk_rb_may_write_user comment
483 int pblk_rb_may_write_gc(struct pblk_rb *rb, unsigned int nr_entries,
486 struct pblk *pblk = container_of(rb, struct pblk, rwb);
488 spin_lock(&rb->w_lock);
489 if (!pblk_rl_gc_may_insert(&pblk->rl, nr_entries)) {
490 spin_unlock(&rb->w_lock);
494 if (!pblk_rb_may_write(rb, nr_entries, pos)) {
495 spin_unlock(&rb->w_lock);
499 pblk_rl_gc_in(&pblk->rl, nr_entries);
500 spin_unlock(&rb->w_lock);
506 * The caller of this function must ensure that the backpointer will not
507 * overwrite the entries passed on the list.
509 unsigned int pblk_rb_read_to_bio_list(struct pblk_rb *rb, struct bio *bio,
510 struct list_head *list,
513 struct pblk_rb_entry *entry, *tentry;
515 unsigned int read = 0;
518 list_for_each_entry_safe(entry, tentry, list, index) {
520 pr_err("pblk: too many entries on list\n");
524 page = virt_to_page(entry->data);
526 pr_err("pblk: could not allocate write bio page\n");
530 ret = bio_add_page(bio, page, rb->seg_size, 0);
531 if (ret != rb->seg_size) {
532 pr_err("pblk: could not add page to write bio\n");
536 list_del(&entry->index);
545 * Read available entries on rb and add them to the given bio. To avoid a memory
546 * copy, a page reference to the write buffer is used to be added to the bio.
548 * This function is used by the write thread to form the write bio that will
549 * persist data on the write buffer to the media.
551 unsigned int pblk_rb_read_to_bio(struct pblk_rb *rb, struct nvm_rq *rqd,
552 struct bio *bio, unsigned int pos,
553 unsigned int nr_entries, unsigned int count)
555 struct pblk *pblk = container_of(rb, struct pblk, rwb);
556 struct request_queue *q = pblk->dev->q;
557 struct pblk_c_ctx *c_ctx = nvm_rq_to_pdu(rqd);
558 struct pblk_rb_entry *entry;
560 unsigned int pad = 0, to_read = nr_entries;
564 if (count < nr_entries) {
565 pad = nr_entries - count;
570 c_ctx->nr_valid = to_read;
571 c_ctx->nr_padded = pad;
573 for (i = 0; i < to_read; i++) {
574 entry = &rb->entries[pos];
576 /* A write has been allowed into the buffer, but data is still
577 * being copied to it. It is ok to busy wait.
580 flags = READ_ONCE(entry->w_ctx.flags);
581 if (!(flags & PBLK_WRITTEN_DATA)) {
586 page = virt_to_page(entry->data);
588 pr_err("pblk: could not allocate write bio page\n");
589 flags &= ~PBLK_WRITTEN_DATA;
590 flags |= PBLK_SUBMITTED_ENTRY;
591 /* Release flags on context. Protect from writes */
592 smp_store_release(&entry->w_ctx.flags, flags);
596 if (bio_add_pc_page(q, bio, page, rb->seg_size, 0) !=
598 pr_err("pblk: could not add page to write bio\n");
599 flags &= ~PBLK_WRITTEN_DATA;
600 flags |= PBLK_SUBMITTED_ENTRY;
601 /* Release flags on context. Protect from writes */
602 smp_store_release(&entry->w_ctx.flags, flags);
606 if (flags & PBLK_FLUSH_ENTRY) {
607 unsigned int sync_point;
609 sync_point = READ_ONCE(rb->sync_point);
610 if (sync_point == pos) {
612 smp_store_release(&rb->sync_point, EMPTY_ENTRY);
615 flags &= ~PBLK_FLUSH_ENTRY;
616 #ifdef CONFIG_NVM_DEBUG
617 atomic_dec(&rb->inflight_sync_point);
621 flags &= ~PBLK_WRITTEN_DATA;
622 flags |= PBLK_SUBMITTED_ENTRY;
624 /* Release flags on context. Protect from writes */
625 smp_store_release(&entry->w_ctx.flags, flags);
627 pos = (pos + 1) & (rb->nr_entries - 1);
631 if (pblk_bio_add_pages(pblk, bio, GFP_KERNEL, pad)) {
632 pr_err("pblk: could not pad page in write bio\n");
637 #ifdef CONFIG_NVM_DEBUG
638 atomic_long_add(pad, &((struct pblk *)
639 (container_of(rb, struct pblk, rwb)))->padded_writes);
646 * Copy to bio only if the lba matches the one on the given cache entry.
647 * Otherwise, it means that the entry has been overwritten, and the bio should
648 * be directed to disk.
650 int pblk_rb_copy_to_bio(struct pblk_rb *rb, struct bio *bio, sector_t lba,
651 u64 pos, int bio_iter)
653 struct pblk_rb_entry *entry;
654 struct pblk_w_ctx *w_ctx;
659 spin_lock(&rb->w_lock);
661 #ifdef CONFIG_NVM_DEBUG
662 /* Caller must ensure that the access will not cause an overflow */
663 BUG_ON(pos >= rb->nr_entries);
665 entry = &rb->entries[pos];
666 w_ctx = &entry->w_ctx;
667 flags = READ_ONCE(w_ctx->flags);
669 /* Check if the entry has been overwritten or is scheduled to be */
670 if (w_ctx->lba != lba || flags & PBLK_WRITABLE_ENTRY) {
675 /* Only advance the bio if it hasn't been advanced already. If advanced,
676 * this bio is at least a partial bio (i.e., it has partially been
677 * filled with data from the cache). If part of the data resides on the
678 * media, we will read later on
680 if (unlikely(!bio->bi_iter.bi_idx))
681 bio_advance(bio, bio_iter * PBLK_EXPOSED_PAGE_SIZE);
683 data = bio_data(bio);
684 memcpy(data, entry->data, rb->seg_size);
687 spin_unlock(&rb->w_lock);
691 struct pblk_w_ctx *pblk_rb_w_ctx(struct pblk_rb *rb, unsigned int pos)
693 unsigned int entry = pos & (rb->nr_entries - 1);
695 return &rb->entries[entry].w_ctx;
698 unsigned int pblk_rb_sync_init(struct pblk_rb *rb, unsigned long *flags)
699 __acquires(&rb->s_lock)
702 spin_lock_irqsave(&rb->s_lock, *flags);
704 spin_lock_irq(&rb->s_lock);
709 void pblk_rb_sync_end(struct pblk_rb *rb, unsigned long *flags)
710 __releases(&rb->s_lock)
712 lockdep_assert_held(&rb->s_lock);
715 spin_unlock_irqrestore(&rb->s_lock, *flags);
717 spin_unlock_irq(&rb->s_lock);
720 unsigned int pblk_rb_sync_advance(struct pblk_rb *rb, unsigned int nr_entries)
725 lockdep_assert_held(&rb->s_lock);
727 sync = READ_ONCE(rb->sync);
729 for (i = 0; i < nr_entries; i++)
730 sync = (sync + 1) & (rb->nr_entries - 1);
732 /* Protect from counts */
733 smp_store_release(&rb->sync, sync);
738 unsigned int pblk_rb_sync_point_count(struct pblk_rb *rb)
740 unsigned int subm, sync_point;
744 sync_point = smp_load_acquire(&rb->sync_point);
745 if (sync_point == EMPTY_ENTRY)
748 subm = READ_ONCE(rb->subm);
750 /* The sync point itself counts as a sector to sync */
751 count = pblk_rb_ring_count(sync_point, subm, rb->nr_entries) + 1;
757 * Scan from the current position of the sync pointer to find the entry that
758 * corresponds to the given ppa. This is necessary since write requests can be
759 * completed out of order. The assumption is that the ppa is close to the sync
760 * pointer thus the search will not take long.
762 * The caller of this function must guarantee that the sync pointer will no
763 * reach the entry while it is using the metadata associated with it. With this
764 * assumption in mind, there is no need to take the sync lock.
766 struct pblk_rb_entry *pblk_rb_sync_scan_entry(struct pblk_rb *rb,
767 struct ppa_addr *ppa)
769 unsigned int sync, subm, count;
772 sync = READ_ONCE(rb->sync);
773 subm = READ_ONCE(rb->subm);
774 count = pblk_rb_ring_count(subm, sync, rb->nr_entries);
776 for (i = 0; i < count; i++)
777 sync = (sync + 1) & (rb->nr_entries - 1);
782 int pblk_rb_tear_down_check(struct pblk_rb *rb)
784 struct pblk_rb_entry *entry;
788 spin_lock(&rb->w_lock);
789 spin_lock_irq(&rb->s_lock);
791 if ((rb->mem == rb->subm) && (rb->subm == rb->sync) &&
792 (rb->sync == rb->l2p_update) &&
793 (rb->sync_point == EMPTY_ENTRY)) {
802 for (i = 0; i < rb->nr_entries; i++) {
803 entry = &rb->entries[i];
812 spin_unlock(&rb->w_lock);
813 spin_unlock_irq(&rb->s_lock);
818 unsigned int pblk_rb_wrap_pos(struct pblk_rb *rb, unsigned int pos)
820 return (pos & (rb->nr_entries - 1));
823 int pblk_rb_pos_oob(struct pblk_rb *rb, u64 pos)
825 return (pos >= rb->nr_entries);
828 ssize_t pblk_rb_sysfs(struct pblk_rb *rb, char *buf)
830 struct pblk *pblk = container_of(rb, struct pblk, rwb);
831 struct pblk_c_ctx *c;
833 int queued_entries = 0;
835 spin_lock_irq(&rb->s_lock);
836 list_for_each_entry(c, &pblk->compl_list, list)
838 spin_unlock_irq(&rb->s_lock);
840 if (rb->sync_point != EMPTY_ENTRY)
841 offset = scnprintf(buf, PAGE_SIZE,
842 "%u\t%u\t%u\t%u\t%u\t%u\t%u - %u/%u/%u - %d\n",
848 #ifdef CONFIG_NVM_DEBUG
849 atomic_read(&rb->inflight_sync_point),
854 pblk_rb_read_count(rb),
856 pblk_rb_sync_point_count(rb),
859 offset = scnprintf(buf, PAGE_SIZE,
860 "%u\t%u\t%u\t%u\t%u\t%u\tNULL - %u/%u/%u - %d\n",
866 #ifdef CONFIG_NVM_DEBUG
867 atomic_read(&rb->inflight_sync_point),
871 pblk_rb_read_count(rb),
873 pblk_rb_sync_point_count(rb),