projects/linux·blob master · refs

3045 lines · 82.9 KiB

1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (C) 2012 Fusion-io All rights reserved.
4 * Copyright (C) 2012 Intel Corp. All rights reserved.
5 */
6
7#include <linux/sched.h>
8#include <linux/bio.h>
9#include <linux/slab.h>
10#include <linux/blkdev.h>
11#include <linux/raid/pq.h>
12#include <linux/hash.h>
13#include <linux/list_sort.h>
14#include <linux/raid/xor.h>
15#include <linux/mm.h>
16#include "messages.h"
17#include "ctree.h"
18#include "disk-io.h"
19#include "volumes.h"
20#include "raid56.h"
21#include "async-thread.h"
22#include "file-item.h"
23#include "btrfs_inode.h"
24
25/* set when additional merges to this rbio are not allowed */
26#define RBIO_RMW_LOCKED_BIT 1
27
28/*
29 * set when this rbio is sitting in the hash, but it is just a cache
30 * of past RMW
31 */
32#define RBIO_CACHE_BIT 2
33
34/*
35 * set when it is safe to trust the stripe_pages for caching
36 */
37#define RBIO_CACHE_READY_BIT 3
38
39#define RBIO_CACHE_SIZE 1024
40
41#define BTRFS_STRIPE_HASH_TABLE_BITS 11
42
43static void dump_bioc(const struct btrfs_fs_info *fs_info, const struct btrfs_io_context *bioc)
44{
45 if (unlikely(!bioc)) {
46 btrfs_crit(fs_info, "bioc=NULL");
47 return;
48 }
49 btrfs_crit(fs_info,
50"bioc logical=%llu full_stripe=%llu size=%llu map_type=0x%llx mirror=%u replace_nr_stripes=%u replace_stripe_src=%d num_stripes=%u",
51 bioc->logical, bioc->full_stripe_logical, bioc->size,
52 bioc->map_type, bioc->mirror_num, bioc->replace_nr_stripes,
53 bioc->replace_stripe_src, bioc->num_stripes);
54 for (int i = 0; i < bioc->num_stripes; i++) {
55 btrfs_crit(fs_info, " nr=%d devid=%llu physical=%llu",
56 i, bioc->stripes[i].dev->devid,
57 bioc->stripes[i].physical);
58 }
59}
60
61static void btrfs_dump_rbio(const struct btrfs_fs_info *fs_info,
62 const struct btrfs_raid_bio *rbio)
63{
64 if (!IS_ENABLED(CONFIG_BTRFS_ASSERT))
65 return;
66
67 dump_bioc(fs_info, rbio->bioc);
68 btrfs_crit(fs_info,
69"rbio flags=0x%lx nr_sectors=%u nr_data=%u real_stripes=%u stripe_nsectors=%u sector_nsteps=%u scrubp=%u dbitmap=0x%lx",
70 rbio->flags, rbio->nr_sectors, rbio->nr_data,
71 rbio->real_stripes, rbio->stripe_nsectors,
72 rbio->sector_nsteps, rbio->scrubp, rbio->dbitmap);
73}
74
75#define ASSERT_RBIO(expr, rbio) \
76({ \
77 if (IS_ENABLED(CONFIG_BTRFS_ASSERT) && unlikely(!(expr))) { \
78 const struct btrfs_fs_info *__fs_info = (rbio)->bioc ? \
79 (rbio)->bioc->fs_info : NULL; \
80 \
81 btrfs_dump_rbio(__fs_info, (rbio)); \
82 } \
83 ASSERT((expr)); \
84})
85
86#define ASSERT_RBIO_STRIPE(expr, rbio, stripe_nr) \
87({ \
88 if (IS_ENABLED(CONFIG_BTRFS_ASSERT) && unlikely(!(expr))) { \
89 const struct btrfs_fs_info *__fs_info = (rbio)->bioc ? \
90 (rbio)->bioc->fs_info : NULL; \
91 \
92 btrfs_dump_rbio(__fs_info, (rbio)); \
93 btrfs_crit(__fs_info, "stripe_nr=%d", (stripe_nr)); \
94 } \
95 ASSERT((expr)); \
96})
97
98#define ASSERT_RBIO_SECTOR(expr, rbio, sector_nr) \
99({ \
100 if (IS_ENABLED(CONFIG_BTRFS_ASSERT) && unlikely(!(expr))) { \
101 const struct btrfs_fs_info *__fs_info = (rbio)->bioc ? \
102 (rbio)->bioc->fs_info : NULL; \
103 \
104 btrfs_dump_rbio(__fs_info, (rbio)); \
105 btrfs_crit(__fs_info, "sector_nr=%d", (sector_nr)); \
106 } \
107 ASSERT((expr)); \
108})
109
110#define ASSERT_RBIO_LOGICAL(expr, rbio, logical) \
111({ \
112 if (IS_ENABLED(CONFIG_BTRFS_ASSERT) && unlikely(!(expr))) { \
113 const struct btrfs_fs_info *__fs_info = (rbio)->bioc ? \
114 (rbio)->bioc->fs_info : NULL; \
115 \
116 btrfs_dump_rbio(__fs_info, (rbio)); \
117 btrfs_crit(__fs_info, "logical=%llu", (logical)); \
118 } \
119 ASSERT((expr)); \
120})
121
122/* Used by the raid56 code to lock stripes for read/modify/write */
123struct btrfs_stripe_hash {
124 struct list_head hash_list;
125 spinlock_t lock;
126};
127
128/* Used by the raid56 code to lock stripes for read/modify/write */
129struct btrfs_stripe_hash_table {
130 struct list_head stripe_cache;
131 spinlock_t cache_lock;
132 int cache_size;
133 struct btrfs_stripe_hash table[];
134};
135
136/*
137 * The PFN may still be valid, but our paddrs should always be block size
138 * aligned, thus such -1 paddr is definitely not a valid one.
139 */
140#define INVALID_PADDR (~(phys_addr_t)0)
141
142static void rmw_rbio_work(struct work_struct *work);
143static void rmw_rbio_work_locked(struct work_struct *work);
144static void index_rbio_pages(struct btrfs_raid_bio *rbio);
145static int alloc_rbio_pages(struct btrfs_raid_bio *rbio);
146
147static int finish_parity_scrub(struct btrfs_raid_bio *rbio);
148static void scrub_rbio_work_locked(struct work_struct *work);
149
150static void free_raid_bio_pointers(struct btrfs_raid_bio *rbio)
151{
152 bitmap_free(rbio->error_bitmap);
153 bitmap_free(rbio->stripe_uptodate_bitmap);
154 kfree(rbio->stripe_pages);
155 kfree(rbio->bio_paddrs);
156 kfree(rbio->stripe_paddrs);
157 kfree(rbio->finish_pointers);
158}
159
160static void free_raid_bio(struct btrfs_raid_bio *rbio)
161{
162 int i;
163
164 if (!refcount_dec_and_test(&rbio->refs))
165 return;
166
167 WARN_ON(!list_empty(&rbio->stripe_cache));
168 WARN_ON(!list_empty(&rbio->hash_list));
169 WARN_ON(!bio_list_empty(&rbio->bio_list));
170
171 for (i = 0; i < rbio->nr_pages; i++) {
172 if (rbio->stripe_pages[i]) {
173 __free_page(rbio->stripe_pages[i]);
174 rbio->stripe_pages[i] = NULL;
175 }
176 }
177
178 btrfs_put_bioc(rbio->bioc);
179 free_raid_bio_pointers(rbio);
180 kfree(rbio);
181}
182
183static void start_async_work(struct btrfs_raid_bio *rbio, work_func_t work_func)
184{
185 INIT_WORK(&rbio->work, work_func);
186 queue_work(rbio->bioc->fs_info->rmw_workers, &rbio->work);
187}
188
189/*
190 * the stripe hash table is used for locking, and to collect
191 * bios in hopes of making a full stripe
192 */
193int btrfs_alloc_stripe_hash_table(struct btrfs_fs_info *info)
194{
195 struct btrfs_stripe_hash_table *table;
196 struct btrfs_stripe_hash_table *x;
197 struct btrfs_stripe_hash *cur;
198 struct btrfs_stripe_hash *h;
199 unsigned int num_entries = 1U << BTRFS_STRIPE_HASH_TABLE_BITS;
200
201 if (info->stripe_hash_table)
202 return 0;
203
204 /*
205 * The table is large, starting with order 4 and can go as high as
206 * order 7 in case lock debugging is turned on.
207 *
208 * Try harder to allocate and fallback to vmalloc to lower the chance
209 * of a failing mount.
210 */
211 table = kvzalloc_flex(*table, table, num_entries);
212 if (!table)
213 return -ENOMEM;
214
215 spin_lock_init(&table->cache_lock);
216 INIT_LIST_HEAD(&table->stripe_cache);
217
218 h = table->table;
219
220 for (unsigned int i = 0; i < num_entries; i++) {
221 cur = h + i;
222 INIT_LIST_HEAD(&cur->hash_list);
223 spin_lock_init(&cur->lock);
224 }
225
226 x = cmpxchg(&info->stripe_hash_table, NULL, table);
227 kvfree(x);
228 return 0;
229}
230
231static void memcpy_from_bio_to_stripe(struct btrfs_raid_bio *rbio, unsigned int sector_nr)
232{
233 const u32 step = min(rbio->bioc->fs_info->sectorsize, PAGE_SIZE);
234
235 ASSERT(sector_nr < rbio->nr_sectors);
236 for (int i = 0; i < rbio->sector_nsteps; i++) {
237 unsigned int index = sector_nr * rbio->sector_nsteps + i;
238 phys_addr_t dst = rbio->stripe_paddrs[index];
239 phys_addr_t src = rbio->bio_paddrs[index];
240
241 ASSERT(dst != INVALID_PADDR);
242 ASSERT(src != INVALID_PADDR);
243
244 memcpy_page(phys_to_page(dst), offset_in_page(dst),
245 phys_to_page(src), offset_in_page(src), step);
246 }
247}
248
249/*
250 * caching an rbio means to copy anything from the
251 * bio_sectors array into the stripe_pages array. We
252 * use the page uptodate bit in the stripe cache array
253 * to indicate if it has valid data
254 *
255 * once the caching is done, we set the cache ready
256 * bit.
257 */
258static void cache_rbio_pages(struct btrfs_raid_bio *rbio)
259{
260 int i;
261 int ret;
262
263 ret = alloc_rbio_pages(rbio);
264 if (ret)
265 return;
266
267 for (i = 0; i < rbio->nr_sectors; i++) {
268 /* Some range not covered by bio (partial write), skip it */
269 if (rbio->bio_paddrs[i * rbio->sector_nsteps] == INVALID_PADDR) {
270 /*
271 * Even if the sector is not covered by bio, if it is
272 * a data sector it should still be uptodate as it is
273 * read from disk.
274 */
275 if (i < rbio->nr_data * rbio->stripe_nsectors)
276 ASSERT(test_bit(i, rbio->stripe_uptodate_bitmap));
277 continue;
278 }
279
280 memcpy_from_bio_to_stripe(rbio, i);
281 set_bit(i, rbio->stripe_uptodate_bitmap);
282 }
283 set_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
284}
285
286/*
287 * we hash on the first logical address of the stripe
288 */
289static int rbio_bucket(struct btrfs_raid_bio *rbio)
290{
291 u64 num = rbio->bioc->full_stripe_logical;
292
293 /*
294 * we shift down quite a bit. We're using byte
295 * addressing, and most of the lower bits are zeros.
296 * This tends to upset hash_64, and it consistently
297 * returns just one or two different values.
298 *
299 * shifting off the lower bits fixes things.
300 */
301 return hash_64(num >> 16, BTRFS_STRIPE_HASH_TABLE_BITS);
302}
303
304/* Get the sector number of the first sector covered by @page_nr. */
305static u32 page_nr_to_sector_nr(struct btrfs_raid_bio *rbio, unsigned int page_nr)
306{
307 u32 sector_nr;
308
309 ASSERT(page_nr < rbio->nr_pages);
310
311 sector_nr = (page_nr << PAGE_SHIFT) >> rbio->bioc->fs_info->sectorsize_bits;
312 ASSERT(sector_nr < rbio->nr_sectors);
313 return sector_nr;
314}
315
316/*
317 * Get the number of sectors covered by @page_nr.
318 *
319 * For bs > ps cases, the result will always be 1.
320 * For bs <= ps cases, the result will be ps / bs.
321 */
322static u32 page_nr_to_num_sectors(struct btrfs_raid_bio *rbio, unsigned int page_nr)
323{
324 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
325 u32 nr_sectors;
326
327 ASSERT(page_nr < rbio->nr_pages);
328
329 nr_sectors = round_up(PAGE_SIZE, fs_info->sectorsize) >> fs_info->sectorsize_bits;
330 ASSERT(nr_sectors > 0);
331 return nr_sectors;
332}
333
334static __maybe_unused bool full_page_sectors_uptodate(struct btrfs_raid_bio *rbio,
335 unsigned int page_nr)
336{
337 const u32 sector_nr = page_nr_to_sector_nr(rbio, page_nr);
338 const u32 nr_bits = page_nr_to_num_sectors(rbio, page_nr);
339 int i;
340
341 ASSERT(page_nr < rbio->nr_pages);
342 ASSERT(sector_nr + nr_bits < rbio->nr_sectors);
343
344 for (i = sector_nr; i < sector_nr + nr_bits; i++) {
345 if (!test_bit(i, rbio->stripe_uptodate_bitmap))
346 return false;
347 }
348 return true;
349}
350
351/*
352 * Update the stripe_sectors[] array to use correct page and pgoff
353 *
354 * Should be called every time any page pointer in stripes_pages[] got modified.
355 */
356static void index_stripe_sectors(struct btrfs_raid_bio *rbio)
357{
358 const u32 step = min(rbio->bioc->fs_info->sectorsize, PAGE_SIZE);
359 u32 offset;
360 int i;
361
362 for (i = 0, offset = 0; i < rbio->nr_sectors * rbio->sector_nsteps;
363 i++, offset += step) {
364 int page_index = offset >> PAGE_SHIFT;
365
366 ASSERT(page_index < rbio->nr_pages);
367 if (!rbio->stripe_pages[page_index])
368 continue;
369
370 rbio->stripe_paddrs[i] = page_to_phys(rbio->stripe_pages[page_index]) +
371 offset_in_page(offset);
372 }
373}
374
375static void steal_rbio_page(struct btrfs_raid_bio *src,
376 struct btrfs_raid_bio *dest, int page_nr)
377{
378 const u32 sector_nr = page_nr_to_sector_nr(src, page_nr);
379 const u32 nr_bits = page_nr_to_num_sectors(src, page_nr);
380
381 ASSERT(page_nr < src->nr_pages);
382 ASSERT(sector_nr + nr_bits < src->nr_sectors);
383
384 if (dest->stripe_pages[page_nr])
385 __free_page(dest->stripe_pages[page_nr]);
386 dest->stripe_pages[page_nr] = src->stripe_pages[page_nr];
387 src->stripe_pages[page_nr] = NULL;
388
389 /* Also update the stripe_uptodate_bitmap bits. */
390 bitmap_set(dest->stripe_uptodate_bitmap, sector_nr, nr_bits);
391}
392
393static bool is_data_stripe_page(struct btrfs_raid_bio *rbio, int page_nr)
394{
395 const int sector_nr = page_nr_to_sector_nr(rbio, page_nr);
396
397 /*
398 * We have ensured PAGE_SIZE is aligned with sectorsize, thus
399 * we won't have a page which is half data half parity.
400 *
401 * Thus if the first sector of the page belongs to data stripes, then
402 * the full page belongs to data stripes.
403 */
404 return (sector_nr < rbio->nr_data * rbio->stripe_nsectors);
405}
406
407/*
408 * Stealing an rbio means taking all the uptodate pages from the stripe array
409 * in the source rbio and putting them into the destination rbio.
410 *
411 * This will also update the involved stripe_sectors[] which are referring to
412 * the old pages.
413 */
414static void steal_rbio(struct btrfs_raid_bio *src, struct btrfs_raid_bio *dest)
415{
416 int i;
417
418 if (!test_bit(RBIO_CACHE_READY_BIT, &src->flags))
419 return;
420
421 for (i = 0; i < dest->nr_pages; i++) {
422 struct page *p = src->stripe_pages[i];
423
424 /*
425 * We don't need to steal P/Q pages as they will always be
426 * regenerated for RMW or full write anyway.
427 */
428 if (!is_data_stripe_page(src, i))
429 continue;
430
431 /*
432 * If @src already has RBIO_CACHE_READY_BIT, it should have
433 * all data stripe pages present and uptodate.
434 */
435 ASSERT(p);
436 ASSERT(full_page_sectors_uptodate(src, i));
437 steal_rbio_page(src, dest, i);
438 }
439 index_stripe_sectors(dest);
440 index_stripe_sectors(src);
441}
442
443/*
444 * merging means we take the bio_list from the victim and
445 * splice it into the destination. The victim should
446 * be discarded afterwards.
447 *
448 * must be called with dest->rbio_list_lock held
449 */
450static void merge_rbio(struct btrfs_raid_bio *dest,
451 struct btrfs_raid_bio *victim)
452{
453 bio_list_merge_init(&dest->bio_list, &victim->bio_list);
454 dest->bio_list_bytes += victim->bio_list_bytes;
455 /* Also inherit the bitmaps from @victim. */
456 bitmap_or(&dest->dbitmap, &victim->dbitmap, &dest->dbitmap,
457 dest->stripe_nsectors);
458}
459
460/*
461 * used to prune items that are in the cache. The caller
462 * must hold the hash table lock.
463 */
464static void __remove_rbio_from_cache(struct btrfs_raid_bio *rbio)
465{
466 int bucket = rbio_bucket(rbio);
467 struct btrfs_stripe_hash_table *table;
468 struct btrfs_stripe_hash *h;
469 bool freeit = false;
470
471 /*
472 * check the bit again under the hash table lock.
473 */
474 if (!test_bit(RBIO_CACHE_BIT, &rbio->flags))
475 return;
476
477 table = rbio->bioc->fs_info->stripe_hash_table;
478 h = table->table + bucket;
479
480 /* hold the lock for the bucket because we may be
481 * removing it from the hash table
482 */
483 spin_lock(&h->lock);
484
485 /*
486 * hold the lock for the bio list because we need
487 * to make sure the bio list is empty
488 */
489 spin_lock(&rbio->bio_list_lock);
490
491 if (test_and_clear_bit(RBIO_CACHE_BIT, &rbio->flags)) {
492 list_del_init(&rbio->stripe_cache);
493 table->cache_size -= 1;
494 freeit = true;
495
496 /* if the bio list isn't empty, this rbio is
497 * still involved in an IO. We take it out
498 * of the cache list, and drop the ref that
499 * was held for the list.
500 *
501 * If the bio_list was empty, we also remove
502 * the rbio from the hash_table, and drop
503 * the corresponding ref
504 */
505 if (bio_list_empty(&rbio->bio_list)) {
506 if (!list_empty(&rbio->hash_list)) {
507 list_del_init(&rbio->hash_list);
508 refcount_dec(&rbio->refs);
509 BUG_ON(!list_empty(&rbio->plug_list));
510 }
511 }
512 }
513
514 spin_unlock(&rbio->bio_list_lock);
515 spin_unlock(&h->lock);
516
517 if (freeit)
518 free_raid_bio(rbio);
519}
520
521/*
522 * prune a given rbio from the cache
523 */
524static void remove_rbio_from_cache(struct btrfs_raid_bio *rbio)
525{
526 struct btrfs_stripe_hash_table *table;
527
528 if (!test_bit(RBIO_CACHE_BIT, &rbio->flags))
529 return;
530
531 table = rbio->bioc->fs_info->stripe_hash_table;
532
533 spin_lock(&table->cache_lock);
534 __remove_rbio_from_cache(rbio);
535 spin_unlock(&table->cache_lock);
536}
537
538/*
539 * remove everything in the cache
540 */
541static void btrfs_clear_rbio_cache(struct btrfs_fs_info *info)
542{
543 struct btrfs_stripe_hash_table *table;
544 struct btrfs_raid_bio *rbio;
545
546 table = info->stripe_hash_table;
547
548 spin_lock(&table->cache_lock);
549 while (!list_empty(&table->stripe_cache)) {
550 rbio = list_first_entry(&table->stripe_cache,
551 struct btrfs_raid_bio, stripe_cache);
552 __remove_rbio_from_cache(rbio);
553 }
554 spin_unlock(&table->cache_lock);
555}
556
557/*
558 * remove all cached entries and free the hash table
559 * used by unmount
560 */
561void btrfs_free_stripe_hash_table(struct btrfs_fs_info *info)
562{
563 if (!info->stripe_hash_table)
564 return;
565 btrfs_clear_rbio_cache(info);
566 kvfree(info->stripe_hash_table);
567 info->stripe_hash_table = NULL;
568}
569
570/*
571 * insert an rbio into the stripe cache. It
572 * must have already been prepared by calling
573 * cache_rbio_pages
574 *
575 * If this rbio was already cached, it gets
576 * moved to the front of the lru.
577 *
578 * If the size of the rbio cache is too big, we
579 * prune an item.
580 */
581static void cache_rbio(struct btrfs_raid_bio *rbio)
582{
583 struct btrfs_stripe_hash_table *table;
584
585 if (!test_bit(RBIO_CACHE_READY_BIT, &rbio->flags))
586 return;
587
588 table = rbio->bioc->fs_info->stripe_hash_table;
589
590 spin_lock(&table->cache_lock);
591 spin_lock(&rbio->bio_list_lock);
592
593 /* bump our ref if we were not in the list before */
594 if (!test_and_set_bit(RBIO_CACHE_BIT, &rbio->flags))
595 refcount_inc(&rbio->refs);
596
597 if (!list_empty(&rbio->stripe_cache)){
598 list_move(&rbio->stripe_cache, &table->stripe_cache);
599 } else {
600 list_add(&rbio->stripe_cache, &table->stripe_cache);
601 table->cache_size += 1;
602 }
603
604 spin_unlock(&rbio->bio_list_lock);
605
606 if (table->cache_size > RBIO_CACHE_SIZE) {
607 struct btrfs_raid_bio *found;
608
609 found = list_last_entry(&table->stripe_cache,
610 struct btrfs_raid_bio,
611 stripe_cache);
612
613 if (found != rbio)
614 __remove_rbio_from_cache(found);
615 }
616
617 spin_unlock(&table->cache_lock);
618}
619
620/*
621 * Returns true if the bio list inside this rbio covers an entire stripe (no
622 * rmw required).
623 */
624static int rbio_is_full(struct btrfs_raid_bio *rbio)
625{
626 unsigned long size = rbio->bio_list_bytes;
627 int ret = 1;
628
629 spin_lock(&rbio->bio_list_lock);
630 if (size != rbio->nr_data * BTRFS_STRIPE_LEN)
631 ret = 0;
632 BUG_ON(size > rbio->nr_data * BTRFS_STRIPE_LEN);
633 spin_unlock(&rbio->bio_list_lock);
634
635 return ret;
636}
637
638/*
639 * returns 1 if it is safe to merge two rbios together.
640 * The merging is safe if the two rbios correspond to
641 * the same stripe and if they are both going in the same
642 * direction (read vs write), and if neither one is
643 * locked for final IO
644 *
645 * The caller is responsible for locking such that
646 * rmw_locked is safe to test
647 */
648static int rbio_can_merge(struct btrfs_raid_bio *last,
649 struct btrfs_raid_bio *cur)
650{
651 if (test_bit(RBIO_RMW_LOCKED_BIT, &last->flags) ||
652 test_bit(RBIO_RMW_LOCKED_BIT, &cur->flags))
653 return 0;
654
655 /*
656 * we can't merge with cached rbios, since the
657 * idea is that when we merge the destination
658 * rbio is going to run our IO for us. We can
659 * steal from cached rbios though, other functions
660 * handle that.
661 */
662 if (test_bit(RBIO_CACHE_BIT, &last->flags) ||
663 test_bit(RBIO_CACHE_BIT, &cur->flags))
664 return 0;
665
666 if (last->bioc->full_stripe_logical != cur->bioc->full_stripe_logical)
667 return 0;
668
669 /* we can't merge with different operations */
670 if (last->operation != cur->operation)
671 return 0;
672 /*
673 * We've need read the full stripe from the drive.
674 * check and repair the parity and write the new results.
675 *
676 * We're not allowed to add any new bios to the
677 * bio list here, anyone else that wants to
678 * change this stripe needs to do their own rmw.
679 */
680 if (last->operation == BTRFS_RBIO_PARITY_SCRUB)
681 return 0;
682
683 if (last->operation == BTRFS_RBIO_READ_REBUILD)
684 return 0;
685
686 return 1;
687}
688
689/* Return the sector index for @stripe_nr and @sector_nr. */
690static unsigned int rbio_sector_index(const struct btrfs_raid_bio *rbio,
691 unsigned int stripe_nr,
692 unsigned int sector_nr)
693{
694 unsigned int ret;
695
696 ASSERT_RBIO_STRIPE(stripe_nr < rbio->real_stripes, rbio, stripe_nr);
697 ASSERT_RBIO_SECTOR(sector_nr < rbio->stripe_nsectors, rbio, sector_nr);
698
699 ret = stripe_nr * rbio->stripe_nsectors + sector_nr;
700 ASSERT(ret < rbio->nr_sectors);
701 return ret;
702}
703
704/* Return the paddr array index for @stripe_nr, @sector_nr and @step_nr. */
705static unsigned int rbio_paddr_index(const struct btrfs_raid_bio *rbio,
706 unsigned int stripe_nr,
707 unsigned int sector_nr,
708 unsigned int step_nr)
709{
710 unsigned int ret;
711
712 ASSERT_RBIO_SECTOR(step_nr < rbio->sector_nsteps, rbio, step_nr);
713
714 ret = rbio_sector_index(rbio, stripe_nr, sector_nr) * rbio->sector_nsteps + step_nr;
715 ASSERT(ret < rbio->nr_sectors * rbio->sector_nsteps);
716 return ret;
717}
718
719static phys_addr_t rbio_stripe_paddr(const struct btrfs_raid_bio *rbio,
720 unsigned int stripe_nr, unsigned int sector_nr,
721 unsigned int step_nr)
722{
723 return rbio->stripe_paddrs[rbio_paddr_index(rbio, stripe_nr, sector_nr, step_nr)];
724}
725
726static phys_addr_t rbio_pstripe_paddr(const struct btrfs_raid_bio *rbio,
727 unsigned int sector_nr, unsigned int step_nr)
728{
729 return rbio_stripe_paddr(rbio, rbio->nr_data, sector_nr, step_nr);
730}
731
732static phys_addr_t rbio_qstripe_paddr(const struct btrfs_raid_bio *rbio,
733 unsigned int sector_nr, unsigned int step_nr)
734{
735 if (rbio->nr_data + 1 == rbio->real_stripes)
736 return INVALID_PADDR;
737 return rbio_stripe_paddr(rbio, rbio->nr_data + 1, sector_nr, step_nr);
738}
739
740/* Return a paddr pointer into the rbio::stripe_paddrs[] for the specified sector. */
741static phys_addr_t *rbio_stripe_paddrs(const struct btrfs_raid_bio *rbio,
742 unsigned int stripe_nr, unsigned int sector_nr)
743{
744 return &rbio->stripe_paddrs[rbio_paddr_index(rbio, stripe_nr, sector_nr, 0)];
745}
746
747/*
748 * The first stripe in the table for a logical address
749 * has the lock. rbios are added in one of three ways:
750 *
751 * 1) Nobody has the stripe locked yet. The rbio is given
752 * the lock and 0 is returned. The caller must start the IO
753 * themselves.
754 *
755 * 2) Someone has the stripe locked, but we're able to merge
756 * with the lock owner. The rbio is freed and the IO will
757 * start automatically along with the existing rbio. 1 is returned.
758 *
759 * 3) Someone has the stripe locked, but we're not able to merge.
760 * The rbio is added to the lock owner's plug list, or merged into
761 * an rbio already on the plug list. When the lock owner unlocks,
762 * the next rbio on the list is run and the IO is started automatically.
763 * 1 is returned
764 *
765 * If we return 0, the caller still owns the rbio and must continue with
766 * IO submission. If we return 1, the caller must assume the rbio has
767 * already been freed.
768 */
769static noinline int lock_stripe_add(struct btrfs_raid_bio *rbio)
770{
771 struct btrfs_stripe_hash *h;
772 struct btrfs_raid_bio *cur;
773 struct btrfs_raid_bio *pending;
774 struct btrfs_raid_bio *freeit = NULL;
775 struct btrfs_raid_bio *cache_drop = NULL;
776 int ret = 0;
777
778 h = rbio->bioc->fs_info->stripe_hash_table->table + rbio_bucket(rbio);
779
780 spin_lock(&h->lock);
781 list_for_each_entry(cur, &h->hash_list, hash_list) {
782 if (cur->bioc->full_stripe_logical != rbio->bioc->full_stripe_logical)
783 continue;
784
785 spin_lock(&cur->bio_list_lock);
786
787 /* Can we steal this cached rbio's pages? */
788 if (bio_list_empty(&cur->bio_list) &&
789 list_empty(&cur->plug_list) &&
790 test_bit(RBIO_CACHE_BIT, &cur->flags) &&
791 !test_bit(RBIO_RMW_LOCKED_BIT, &cur->flags)) {
792 list_del_init(&cur->hash_list);
793 refcount_dec(&cur->refs);
794
795 steal_rbio(cur, rbio);
796 cache_drop = cur;
797 spin_unlock(&cur->bio_list_lock);
798
799 goto lockit;
800 }
801
802 /* Can we merge into the lock owner? */
803 if (rbio_can_merge(cur, rbio)) {
804 merge_rbio(cur, rbio);
805 spin_unlock(&cur->bio_list_lock);
806 freeit = rbio;
807 ret = 1;
808 goto out;
809 }
810
811
812 /*
813 * We couldn't merge with the running rbio, see if we can merge
814 * with the pending ones. We don't have to check for rmw_locked
815 * because there is no way they are inside finish_rmw right now
816 */
817 list_for_each_entry(pending, &cur->plug_list, plug_list) {
818 if (rbio_can_merge(pending, rbio)) {
819 merge_rbio(pending, rbio);
820 spin_unlock(&cur->bio_list_lock);
821 freeit = rbio;
822 ret = 1;
823 goto out;
824 }
825 }
826
827 /*
828 * No merging, put us on the tail of the plug list, our rbio
829 * will be started with the currently running rbio unlocks
830 */
831 list_add_tail(&rbio->plug_list, &cur->plug_list);
832 spin_unlock(&cur->bio_list_lock);
833 ret = 1;
834 goto out;
835 }
836lockit:
837 refcount_inc(&rbio->refs);
838 list_add(&rbio->hash_list, &h->hash_list);
839out:
840 spin_unlock(&h->lock);
841 if (cache_drop)
842 remove_rbio_from_cache(cache_drop);
843 if (freeit)
844 free_raid_bio(freeit);
845 return ret;
846}
847
848static void recover_rbio_work_locked(struct work_struct *work);
849
850/*
851 * called as rmw or parity rebuild is completed. If the plug list has more
852 * rbios waiting for this stripe, the next one on the list will be started
853 */
854static noinline void unlock_stripe(struct btrfs_raid_bio *rbio)
855{
856 int bucket;
857 struct btrfs_stripe_hash *h;
858 bool keep_cache = false;
859
860 bucket = rbio_bucket(rbio);
861 h = rbio->bioc->fs_info->stripe_hash_table->table + bucket;
862
863 if (list_empty(&rbio->plug_list))
864 cache_rbio(rbio);
865
866 spin_lock(&h->lock);
867 spin_lock(&rbio->bio_list_lock);
868
869 if (!list_empty(&rbio->hash_list)) {
870 /*
871 * if we're still cached and there is no other IO
872 * to perform, just leave this rbio here for others
873 * to steal from later
874 */
875 if (list_empty(&rbio->plug_list) &&
876 test_bit(RBIO_CACHE_BIT, &rbio->flags)) {
877 keep_cache = true;
878 clear_bit(RBIO_RMW_LOCKED_BIT, &rbio->flags);
879 BUG_ON(!bio_list_empty(&rbio->bio_list));
880 goto done;
881 }
882
883 list_del_init(&rbio->hash_list);
884 refcount_dec(&rbio->refs);
885
886 /*
887 * we use the plug list to hold all the rbios
888 * waiting for the chance to lock this stripe.
889 * hand the lock over to one of them.
890 */
891 if (!list_empty(&rbio->plug_list)) {
892 struct btrfs_raid_bio *next;
893 struct list_head *head = rbio->plug_list.next;
894
895 next = list_entry(head, struct btrfs_raid_bio,
896 plug_list);
897
898 list_del_init(&rbio->plug_list);
899
900 list_add(&next->hash_list, &h->hash_list);
901 refcount_inc(&next->refs);
902 spin_unlock(&rbio->bio_list_lock);
903 spin_unlock(&h->lock);
904
905 if (next->operation == BTRFS_RBIO_READ_REBUILD) {
906 start_async_work(next, recover_rbio_work_locked);
907 } else if (next->operation == BTRFS_RBIO_WRITE) {
908 steal_rbio(rbio, next);
909 start_async_work(next, rmw_rbio_work_locked);
910 } else if (next->operation == BTRFS_RBIO_PARITY_SCRUB) {
911 steal_rbio(rbio, next);
912 start_async_work(next, scrub_rbio_work_locked);
913 }
914
915 goto done_nolock;
916 }
917 }
918done:
919 spin_unlock(&rbio->bio_list_lock);
920 spin_unlock(&h->lock);
921
922done_nolock:
923 if (!keep_cache)
924 remove_rbio_from_cache(rbio);
925}
926
927static void rbio_endio_bio_list(struct bio *cur, blk_status_t status)
928{
929 struct bio *next;
930
931 while (cur) {
932 next = cur->bi_next;
933 cur->bi_next = NULL;
934 cur->bi_status = status;
935 bio_endio(cur);
936 cur = next;
937 }
938}
939
940/*
941 * this frees the rbio and runs through all the bios in the
942 * bio_list and calls end_io on them
943 */
944static void rbio_orig_end_io(struct btrfs_raid_bio *rbio, blk_status_t status)
945{
946 struct bio *cur = bio_list_get(&rbio->bio_list);
947 struct bio *extra;
948
949 kfree(rbio->csum_buf);
950 bitmap_free(rbio->csum_bitmap);
951 rbio->csum_buf = NULL;
952 rbio->csum_bitmap = NULL;
953
954 /*
955 * Clear the data bitmap, as the rbio may be cached for later usage.
956 * do this before unlock_stripe() so there will be no new bio
957 * for this bio.
958 */
959 bitmap_clear(&rbio->dbitmap, 0, rbio->stripe_nsectors);
960
961 /*
962 * At this moment, rbio->bio_list is empty, however since rbio does not
963 * always have RBIO_RMW_LOCKED_BIT set and rbio is still linked on the
964 * hash list, rbio may be merged with others so that rbio->bio_list
965 * becomes non-empty.
966 * Once unlock_stripe() is done, rbio->bio_list will not be updated any
967 * more and we can call bio_endio() on all queued bios.
968 */
969 unlock_stripe(rbio);
970 extra = bio_list_get(&rbio->bio_list);
971 free_raid_bio(rbio);
972
973 rbio_endio_bio_list(cur, status);
974 if (extra)
975 rbio_endio_bio_list(extra, status);
976}
977
978/*
979 * Get paddr pointer for the sector specified by its @stripe_nr and @sector_nr.
980 *
981 * @rbio: The raid bio
982 * @stripe_nr: Stripe number, valid range [0, real_stripe)
983 * @sector_nr: Sector number inside the stripe,
984 * valid range [0, stripe_nsectors)
985 * @bio_list_only: Whether to use sectors inside the bio list only.
986 *
987 * The read/modify/write code wants to reuse the original bio page as much
988 * as possible, and only use stripe_sectors as fallback.
989 *
990 * Return NULL if bio_list_only is set but the specified sector has no
991 * corresponding bio.
992 */
993static phys_addr_t *sector_paddrs_in_rbio(struct btrfs_raid_bio *rbio,
994 int stripe_nr, int sector_nr,
995 bool bio_list_only)
996{
997 phys_addr_t *ret = NULL;
998 const int index = rbio_paddr_index(rbio, stripe_nr, sector_nr, 0);
999
1000 ASSERT(index >= 0 && index < rbio->nr_sectors * rbio->sector_nsteps);
1001
1002 scoped_guard(spinlock, &rbio->bio_list_lock) {
1003 if (rbio->bio_paddrs[index] != INVALID_PADDR || bio_list_only) {
1004 /* Don't return sector without a valid page pointer */
1005 if (rbio->bio_paddrs[index] != INVALID_PADDR)
1006 ret = &rbio->bio_paddrs[index];
1007 return ret;
1008 }
1009 }
1010 return &rbio->stripe_paddrs[index];
1011}
1012
1013/*
1014 * Similar to sector_paddr_in_rbio(), but with extra consideration for
1015 * bs > ps cases, where we can have multiple steps for a fs block.
1016 */
1017static phys_addr_t sector_paddr_in_rbio(struct btrfs_raid_bio *rbio,
1018 int stripe_nr, int sector_nr, int step_nr,
1019 bool bio_list_only)
1020{
1021 phys_addr_t ret = INVALID_PADDR;
1022 const int index = rbio_paddr_index(rbio, stripe_nr, sector_nr, step_nr);
1023
1024 ASSERT(index >= 0 && index < rbio->nr_sectors * rbio->sector_nsteps);
1025
1026 scoped_guard(spinlock, &rbio->bio_list_lock) {
1027 if (rbio->bio_paddrs[index] != INVALID_PADDR || bio_list_only) {
1028 /* Don't return sector without a valid page pointer */
1029 if (rbio->bio_paddrs[index] != INVALID_PADDR)
1030 ret = rbio->bio_paddrs[index];
1031 return ret;
1032 }
1033 }
1034 return rbio->stripe_paddrs[index];
1035}
1036
1037/*
1038 * allocation and initial setup for the btrfs_raid_bio. Not
1039 * this does not allocate any pages for rbio->pages.
1040 */
1041static struct btrfs_raid_bio *alloc_rbio(struct btrfs_fs_info *fs_info,
1042 struct btrfs_io_context *bioc)
1043{
1044 const unsigned int real_stripes = bioc->num_stripes - bioc->replace_nr_stripes;
1045 const unsigned int stripe_npages = BTRFS_STRIPE_LEN >> PAGE_SHIFT;
1046 const unsigned int num_pages = stripe_npages * real_stripes;
1047 const unsigned int stripe_nsectors =
1048 BTRFS_STRIPE_LEN >> fs_info->sectorsize_bits;
1049 const unsigned int num_sectors = stripe_nsectors * real_stripes;
1050 const unsigned int step = min(fs_info->sectorsize, PAGE_SIZE);
1051 const unsigned int sector_nsteps = fs_info->sectorsize / step;
1052 struct btrfs_raid_bio *rbio;
1053
1054 /*
1055 * For bs <= ps cases, ps must be aligned to bs.
1056 * For bs > ps cases, bs must be aligned to ps.
1057 */
1058 ASSERT(IS_ALIGNED(PAGE_SIZE, fs_info->sectorsize) ||
1059 IS_ALIGNED(fs_info->sectorsize, PAGE_SIZE));
1060 /*
1061 * Our current stripe len should be fixed to 64k thus stripe_nsectors
1062 * (at most 16) should be no larger than BITS_PER_LONG.
1063 */
1064 ASSERT(stripe_nsectors <= BITS_PER_LONG);
1065
1066 /*
1067 * Real stripes must be between 2 (2 disks RAID5, aka RAID1) and 256
1068 * (limited by u8).
1069 */
1070 ASSERT(real_stripes >= 2);
1071 ASSERT(real_stripes <= U8_MAX);
1072
1073 rbio = kzalloc_obj(*rbio, GFP_NOFS);
1074 if (!rbio)
1075 return ERR_PTR(-ENOMEM);
1076 rbio->stripe_pages = kzalloc_objs(struct page *, num_pages, GFP_NOFS);
1077 rbio->bio_paddrs = kzalloc_objs(phys_addr_t,
1078 num_sectors * sector_nsteps, GFP_NOFS);
1079 rbio->stripe_paddrs = kzalloc_objs(phys_addr_t,
1080 num_sectors * sector_nsteps,
1081 GFP_NOFS);
1082 rbio->finish_pointers = kcalloc(real_stripes, sizeof(void *), GFP_NOFS);
1083 rbio->error_bitmap = bitmap_zalloc(num_sectors, GFP_NOFS);
1084 rbio->stripe_uptodate_bitmap = bitmap_zalloc(num_sectors, GFP_NOFS);
1085
1086 if (!rbio->stripe_pages || !rbio->bio_paddrs || !rbio->stripe_paddrs ||
1087 !rbio->finish_pointers || !rbio->error_bitmap || !rbio->stripe_uptodate_bitmap) {
1088 free_raid_bio_pointers(rbio);
1089 kfree(rbio);
1090 return ERR_PTR(-ENOMEM);
1091 }
1092 for (int i = 0; i < num_sectors * sector_nsteps; i++) {
1093 rbio->stripe_paddrs[i] = INVALID_PADDR;
1094 rbio->bio_paddrs[i] = INVALID_PADDR;
1095 }
1096
1097 bio_list_init(&rbio->bio_list);
1098 init_waitqueue_head(&rbio->io_wait);
1099 INIT_LIST_HEAD(&rbio->plug_list);
1100 spin_lock_init(&rbio->bio_list_lock);
1101 INIT_LIST_HEAD(&rbio->stripe_cache);
1102 INIT_LIST_HEAD(&rbio->hash_list);
1103 btrfs_get_bioc(bioc);
1104 rbio->bioc = bioc;
1105 rbio->nr_pages = num_pages;
1106 rbio->nr_sectors = num_sectors;
1107 rbio->real_stripes = real_stripes;
1108 rbio->stripe_npages = stripe_npages;
1109 rbio->stripe_nsectors = stripe_nsectors;
1110 rbio->sector_nsteps = sector_nsteps;
1111 refcount_set(&rbio->refs, 1);
1112 atomic_set(&rbio->stripes_pending, 0);
1113
1114 ASSERT(btrfs_nr_parity_stripes(bioc->map_type));
1115 rbio->nr_data = real_stripes - btrfs_nr_parity_stripes(bioc->map_type);
1116 ASSERT(rbio->nr_data > 0);
1117
1118 return rbio;
1119}
1120
1121/* allocate pages for all the stripes in the bio, including parity */
1122static int alloc_rbio_pages(struct btrfs_raid_bio *rbio)
1123{
1124 int ret;
1125
1126 ret = btrfs_alloc_page_array(rbio->nr_pages, rbio->stripe_pages, GFP_NOFS);
1127 if (ret < 0)
1128 return ret;
1129 /* Mapping all sectors */
1130 index_stripe_sectors(rbio);
1131 return 0;
1132}
1133
1134/* only allocate pages for p/q stripes */
1135static int alloc_rbio_parity_pages(struct btrfs_raid_bio *rbio)
1136{
1137 const int data_pages = rbio->nr_data * rbio->stripe_npages;
1138 int ret;
1139
1140 ret = btrfs_alloc_page_array(rbio->nr_pages - data_pages,
1141 rbio->stripe_pages + data_pages, GFP_NOFS);
1142 if (ret < 0)
1143 return ret;
1144
1145 index_stripe_sectors(rbio);
1146 return 0;
1147}
1148
1149/*
1150 * Return the total number of errors found in the vertical stripe of @sector_nr.
1151 *
1152 * @faila and @failb will also be updated to the first and second stripe
1153 * number of the errors.
1154 */
1155static int get_rbio_vertical_errors(struct btrfs_raid_bio *rbio, int sector_nr,
1156 int *faila, int *failb)
1157{
1158 int stripe_nr;
1159 int found_errors = 0;
1160
1161 if (faila || failb) {
1162 /*
1163 * Both @faila and @failb should be valid pointers if any of
1164 * them is specified.
1165 */
1166 ASSERT(faila && failb);
1167 *faila = -1;
1168 *failb = -1;
1169 }
1170
1171 for (stripe_nr = 0; stripe_nr < rbio->real_stripes; stripe_nr++) {
1172 int total_sector_nr = stripe_nr * rbio->stripe_nsectors + sector_nr;
1173
1174 if (test_bit(total_sector_nr, rbio->error_bitmap)) {
1175 found_errors++;
1176 if (faila) {
1177 /* Update faila and failb. */
1178 if (*faila < 0)
1179 *faila = stripe_nr;
1180 else if (*failb < 0)
1181 *failb = stripe_nr;
1182 }
1183 }
1184 }
1185 return found_errors;
1186}
1187
1188static int bio_add_paddrs(struct bio *bio, phys_addr_t *paddrs, unsigned int nr_steps,
1189 unsigned int step)
1190{
1191 int added = 0;
1192 int ret;
1193
1194 for (int i = 0; i < nr_steps; i++) {
1195 ret = bio_add_page(bio, phys_to_page(paddrs[i]), step,
1196 offset_in_page(paddrs[i]));
1197 if (ret != step)
1198 goto revert;
1199 added += ret;
1200 }
1201 return added;
1202revert:
1203 /*
1204 * We don't need to revert the bvec, as the bio will be submitted immediately,
1205 * as long as the size is reduced the extra bvec will not be accessed.
1206 */
1207 bio->bi_iter.bi_size -= added;
1208 return 0;
1209}
1210
1211/*
1212 * Add a single sector @sector into our list of bios for IO.
1213 *
1214 * Return 0 if everything went well.
1215 * Return <0 for error, and no byte will be added to @rbio.
1216 */
1217static int rbio_add_io_paddrs(struct btrfs_raid_bio *rbio, struct bio_list *bio_list,
1218 phys_addr_t *paddrs, unsigned int stripe_nr,
1219 unsigned int sector_nr, enum req_op op)
1220{
1221 const u32 sectorsize = rbio->bioc->fs_info->sectorsize;
1222 const u32 step = min(sectorsize, PAGE_SIZE);
1223 struct bio *last = bio_list->tail;
1224 int ret;
1225 struct bio *bio;
1226 struct btrfs_io_stripe *stripe;
1227 u64 disk_start;
1228
1229 /*
1230 * Note: here stripe_nr has taken device replace into consideration,
1231 * thus it can be larger than rbio->real_stripe.
1232 * So here we check against bioc->num_stripes, not rbio->real_stripes.
1233 */
1234 ASSERT_RBIO_STRIPE(stripe_nr >= 0 && stripe_nr < rbio->bioc->num_stripes,
1235 rbio, stripe_nr);
1236 ASSERT_RBIO_SECTOR(sector_nr >= 0 && sector_nr < rbio->stripe_nsectors,
1237 rbio, sector_nr);
1238 ASSERT(paddrs != NULL);
1239
1240 stripe = &rbio->bioc->stripes[stripe_nr];
1241 disk_start = stripe->physical + sector_nr * sectorsize;
1242
1243 /* if the device is missing, just fail this stripe */
1244 if (!stripe->dev->bdev) {
1245 int found_errors;
1246
1247 set_bit(stripe_nr * rbio->stripe_nsectors + sector_nr,
1248 rbio->error_bitmap);
1249
1250 /* Check if we have reached tolerance early. */
1251 found_errors = get_rbio_vertical_errors(rbio, sector_nr,
1252 NULL, NULL);
1253 if (unlikely(found_errors > rbio->bioc->max_errors))
1254 return -EIO;
1255 return 0;
1256 }
1257
1258 /* see if we can add this page onto our existing bio */
1259 if (last) {
1260 u64 last_end = last->bi_iter.bi_sector << SECTOR_SHIFT;
1261 last_end += last->bi_iter.bi_size;
1262
1263 /*
1264 * we can't merge these if they are from different
1265 * devices or if they are not contiguous
1266 */
1267 if (last_end == disk_start && !last->bi_status &&
1268 last->bi_bdev == stripe->dev->bdev) {
1269 ret = bio_add_paddrs(last, paddrs, rbio->sector_nsteps, step);
1270 if (ret == sectorsize)
1271 return 0;
1272 }
1273 }
1274
1275 /* put a new bio on the list */
1276 bio = bio_alloc(stripe->dev->bdev,
1277 max(BTRFS_STRIPE_LEN >> PAGE_SHIFT, 1),
1278 op, GFP_NOFS);
1279 bio->bi_iter.bi_sector = disk_start >> SECTOR_SHIFT;
1280 bio->bi_private = rbio;
1281
1282 ret = bio_add_paddrs(bio, paddrs, rbio->sector_nsteps, step);
1283 ASSERT(ret == sectorsize);
1284 bio_list_add(bio_list, bio);
1285 return 0;
1286}
1287
1288static void index_one_bio(struct btrfs_raid_bio *rbio, struct bio *bio)
1289{
1290 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
1291 const u32 step = min(fs_info->sectorsize, PAGE_SIZE);
1292 const u32 step_bits = min(fs_info->sectorsize_bits, PAGE_SHIFT);
1293 struct bvec_iter iter = bio->bi_iter;
1294 phys_addr_t paddr;
1295 u32 offset = (bio->bi_iter.bi_sector << SECTOR_SHIFT) -
1296 rbio->bioc->full_stripe_logical;
1297
1298 btrfs_bio_for_each_block(paddr, bio, &iter, step) {
1299 unsigned int index = (offset >> step_bits);
1300
1301 rbio->bio_paddrs[index] = paddr;
1302 offset += step;
1303 }
1304}
1305
1306/*
1307 * helper function to walk our bio list and populate the bio_pages array with
1308 * the result. This seems expensive, but it is faster than constantly
1309 * searching through the bio list as we setup the IO in finish_rmw or stripe
1310 * reconstruction.
1311 *
1312 * This must be called before you trust the answers from page_in_rbio
1313 */
1314static void index_rbio_pages(struct btrfs_raid_bio *rbio)
1315{
1316 struct bio *bio;
1317
1318 spin_lock(&rbio->bio_list_lock);
1319 bio_list_for_each(bio, &rbio->bio_list)
1320 index_one_bio(rbio, bio);
1321
1322 spin_unlock(&rbio->bio_list_lock);
1323}
1324
1325static void bio_get_trace_info(struct btrfs_raid_bio *rbio, struct bio *bio,
1326 struct raid56_bio_trace_info *trace_info)
1327{
1328 const struct btrfs_io_context *bioc = rbio->bioc;
1329 int i;
1330
1331 ASSERT(bioc);
1332
1333 /* We rely on bio->bi_bdev to find the stripe number. */
1334 if (!bio->bi_bdev)
1335 goto not_found;
1336
1337 for (i = 0; i < bioc->num_stripes; i++) {
1338 if (bio->bi_bdev != bioc->stripes[i].dev->bdev)
1339 continue;
1340 trace_info->stripe_nr = i;
1341 trace_info->devid = bioc->stripes[i].dev->devid;
1342 trace_info->offset = (bio->bi_iter.bi_sector << SECTOR_SHIFT) -
1343 bioc->stripes[i].physical;
1344 return;
1345 }
1346
1347not_found:
1348 trace_info->devid = -1;
1349 trace_info->offset = -1;
1350 trace_info->stripe_nr = -1;
1351}
1352
1353static inline void bio_list_put(struct bio_list *bio_list)
1354{
1355 struct bio *bio;
1356
1357 while ((bio = bio_list_pop(bio_list)))
1358 bio_put(bio);
1359}
1360
1361static void assert_rbio(struct btrfs_raid_bio *rbio)
1362{
1363 if (!IS_ENABLED(CONFIG_BTRFS_ASSERT))
1364 return;
1365
1366 /*
1367 * At least two stripes (2 disks RAID5), and since real_stripes is U8,
1368 * we won't go beyond 256 disks anyway.
1369 */
1370 ASSERT_RBIO(rbio->real_stripes >= 2, rbio);
1371 ASSERT_RBIO(rbio->nr_data > 0, rbio);
1372
1373 /*
1374 * This is another check to make sure nr data stripes is smaller
1375 * than total stripes.
1376 */
1377 ASSERT_RBIO(rbio->nr_data < rbio->real_stripes, rbio);
1378}
1379
1380static inline void *kmap_local_paddr(phys_addr_t paddr)
1381{
1382 /* The sector pointer must have a page mapped to it. */
1383 ASSERT(paddr != INVALID_PADDR);
1384
1385 return kmap_local_page(phys_to_page(paddr)) + offset_in_page(paddr);
1386}
1387
1388static void generate_pq_vertical_step(struct btrfs_raid_bio *rbio, unsigned int sector_nr,
1389 unsigned int step_nr)
1390{
1391 void **pointers = rbio->finish_pointers;
1392 const u32 step = min(rbio->bioc->fs_info->sectorsize, PAGE_SIZE);
1393 int stripe;
1394 const bool has_qstripe = rbio->bioc->map_type & BTRFS_BLOCK_GROUP_RAID6;
1395
1396 /* First collect one sector from each data stripe */
1397 for (stripe = 0; stripe < rbio->nr_data; stripe++)
1398 pointers[stripe] = kmap_local_paddr(
1399 sector_paddr_in_rbio(rbio, stripe, sector_nr, step_nr, 0));
1400
1401 /* Then add the parity stripe */
1402 pointers[stripe++] = kmap_local_paddr(rbio_pstripe_paddr(rbio, sector_nr, step_nr));
1403
1404 if (has_qstripe) {
1405 /*
1406 * RAID6, add the qstripe and call the library function
1407 * to fill in our p/q
1408 */
1409 pointers[stripe++] = kmap_local_paddr(
1410 rbio_qstripe_paddr(rbio, sector_nr, step_nr));
1411
1412 assert_rbio(rbio);
1413 raid6_gen_syndrome(rbio->real_stripes, step, pointers);
1414 } else {
1415 /* raid5 */
1416 memcpy(pointers[rbio->nr_data], pointers[0], step);
1417 xor_gen(pointers[rbio->nr_data], pointers + 1, rbio->nr_data - 1,
1418 step);
1419 }
1420 for (stripe = stripe - 1; stripe >= 0; stripe--)
1421 kunmap_local(pointers[stripe]);
1422}
1423
1424/* Generate PQ for one vertical stripe. */
1425static void generate_pq_vertical(struct btrfs_raid_bio *rbio, int sectornr)
1426{
1427 const bool has_qstripe = (rbio->bioc->map_type & BTRFS_BLOCK_GROUP_RAID6);
1428
1429 for (int i = 0; i < rbio->sector_nsteps; i++)
1430 generate_pq_vertical_step(rbio, sectornr, i);
1431
1432 set_bit(rbio_sector_index(rbio, rbio->nr_data, sectornr),
1433 rbio->stripe_uptodate_bitmap);
1434 if (has_qstripe)
1435 set_bit(rbio_sector_index(rbio, rbio->nr_data + 1, sectornr),
1436 rbio->stripe_uptodate_bitmap);
1437}
1438
1439static int rmw_assemble_write_bios(struct btrfs_raid_bio *rbio,
1440 struct bio_list *bio_list)
1441{
1442 /* The total sector number inside the full stripe. */
1443 int total_sector_nr;
1444 int sectornr;
1445 int stripe;
1446 int ret;
1447
1448 ASSERT(bio_list_size(bio_list) == 0);
1449
1450 /* We should have at least one data sector. */
1451 ASSERT(bitmap_weight(&rbio->dbitmap, rbio->stripe_nsectors));
1452
1453 /* Reset errors, as we may have errors inherited from degraded write. */
1454 bitmap_clear(rbio->error_bitmap, 0, rbio->nr_sectors);
1455
1456 /*
1457 * Start assembly. Make bios for everything from the higher layers (the
1458 * bio_list in our rbio) and our P/Q. Ignore everything else.
1459 */
1460 for (total_sector_nr = 0; total_sector_nr < rbio->nr_sectors;
1461 total_sector_nr++) {
1462 phys_addr_t *paddrs;
1463
1464 stripe = total_sector_nr / rbio->stripe_nsectors;
1465 sectornr = total_sector_nr % rbio->stripe_nsectors;
1466
1467 /* This vertical stripe has no data, skip it. */
1468 if (!test_bit(sectornr, &rbio->dbitmap))
1469 continue;
1470
1471 if (stripe < rbio->nr_data) {
1472 paddrs = sector_paddrs_in_rbio(rbio, stripe, sectornr, 1);
1473 if (paddrs == NULL)
1474 continue;
1475 } else {
1476 paddrs = rbio_stripe_paddrs(rbio, stripe, sectornr);
1477 }
1478
1479 ret = rbio_add_io_paddrs(rbio, bio_list, paddrs, stripe,
1480 sectornr, REQ_OP_WRITE);
1481 if (ret)
1482 goto error;
1483 }
1484
1485 if (likely(!rbio->bioc->replace_nr_stripes))
1486 return 0;
1487
1488 /*
1489 * Make a copy for the replace target device.
1490 *
1491 * Thus the source stripe number (in replace_stripe_src) should be valid.
1492 */
1493 ASSERT(rbio->bioc->replace_stripe_src >= 0);
1494
1495 for (total_sector_nr = 0; total_sector_nr < rbio->nr_sectors;
1496 total_sector_nr++) {
1497 phys_addr_t *paddrs;
1498
1499 stripe = total_sector_nr / rbio->stripe_nsectors;
1500 sectornr = total_sector_nr % rbio->stripe_nsectors;
1501
1502 /*
1503 * For RAID56, there is only one device that can be replaced,
1504 * and replace_stripe_src[0] indicates the stripe number we
1505 * need to copy from.
1506 */
1507 if (stripe != rbio->bioc->replace_stripe_src) {
1508 /*
1509 * We can skip the whole stripe completely, note
1510 * total_sector_nr will be increased by one anyway.
1511 */
1512 ASSERT(sectornr == 0);
1513 total_sector_nr += rbio->stripe_nsectors - 1;
1514 continue;
1515 }
1516
1517 /* This vertical stripe has no data, skip it. */
1518 if (!test_bit(sectornr, &rbio->dbitmap))
1519 continue;
1520
1521 if (stripe < rbio->nr_data) {
1522 paddrs = sector_paddrs_in_rbio(rbio, stripe, sectornr, 1);
1523 if (paddrs == NULL)
1524 continue;
1525 } else {
1526 paddrs = rbio_stripe_paddrs(rbio, stripe, sectornr);
1527 }
1528
1529 ret = rbio_add_io_paddrs(rbio, bio_list, paddrs,
1530 rbio->real_stripes,
1531 sectornr, REQ_OP_WRITE);
1532 if (ret)
1533 goto error;
1534 }
1535
1536 return 0;
1537error:
1538 bio_list_put(bio_list);
1539 return -EIO;
1540}
1541
1542static void set_rbio_range_error(struct btrfs_raid_bio *rbio, struct bio *bio)
1543{
1544 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
1545 u32 offset = (bio->bi_iter.bi_sector << SECTOR_SHIFT) -
1546 rbio->bioc->full_stripe_logical;
1547 int total_nr_sector = offset >> fs_info->sectorsize_bits;
1548
1549 ASSERT(total_nr_sector < rbio->nr_data * rbio->stripe_nsectors);
1550
1551 bitmap_set(rbio->error_bitmap, total_nr_sector,
1552 bio->bi_iter.bi_size >> fs_info->sectorsize_bits);
1553
1554 /*
1555 * Special handling for raid56_alloc_missing_rbio() used by
1556 * scrub/replace. Unlike call path in raid56_parity_recover(), they
1557 * pass an empty bio here. Thus we have to find out the missing device
1558 * and mark the stripe error instead.
1559 */
1560 if (bio->bi_iter.bi_size == 0) {
1561 bool found_missing = false;
1562 int stripe_nr;
1563
1564 for (stripe_nr = 0; stripe_nr < rbio->real_stripes; stripe_nr++) {
1565 if (!rbio->bioc->stripes[stripe_nr].dev->bdev) {
1566 found_missing = true;
1567 bitmap_set(rbio->error_bitmap,
1568 stripe_nr * rbio->stripe_nsectors,
1569 rbio->stripe_nsectors);
1570 }
1571 }
1572 ASSERT(found_missing);
1573 }
1574}
1575
1576/*
1577 * Return the index inside the rbio->stripe_sectors[] array.
1578 *
1579 * Return -1 if not found.
1580 */
1581static int find_stripe_sector_nr(struct btrfs_raid_bio *rbio, phys_addr_t paddr)
1582{
1583 for (int i = 0; i < rbio->nr_sectors; i++) {
1584 if (rbio->stripe_paddrs[i * rbio->sector_nsteps] == paddr)
1585 return i;
1586 }
1587 return -1;
1588}
1589
1590/*
1591 * this sets each page in the bio uptodate. It should only be used on private
1592 * rbio pages, nothing that comes in from the higher layers
1593 */
1594static void set_bio_pages_uptodate(struct btrfs_raid_bio *rbio, struct bio *bio)
1595{
1596 const u32 sectorsize = rbio->bioc->fs_info->sectorsize;
1597 const u32 step = min(sectorsize, PAGE_SIZE);
1598 u32 offset = 0;
1599 phys_addr_t paddr;
1600
1601 ASSERT(!bio_flagged(bio, BIO_CLONED));
1602
1603 btrfs_bio_for_each_block_all(paddr, bio, step) {
1604 /* Hitting the first step of a sector. */
1605 if (IS_ALIGNED(offset, sectorsize)) {
1606 int sector_nr = find_stripe_sector_nr(rbio, paddr);
1607
1608 ASSERT(sector_nr >= 0);
1609 if (sector_nr >= 0)
1610 set_bit(sector_nr, rbio->stripe_uptodate_bitmap);
1611 }
1612 offset += step;
1613 }
1614}
1615
1616static int get_bio_sector_nr(struct btrfs_raid_bio *rbio, struct bio *bio)
1617{
1618 phys_addr_t bvec_paddr = bvec_phys(bio_first_bvec_all(bio));
1619 int i;
1620
1621 for (i = 0; i < rbio->nr_sectors; i++) {
1622 if (rbio->stripe_paddrs[i * rbio->sector_nsteps] == bvec_paddr)
1623 break;
1624 if (rbio->bio_paddrs[i * rbio->sector_nsteps] == bvec_paddr)
1625 break;
1626 }
1627 ASSERT(i < rbio->nr_sectors);
1628 return i;
1629}
1630
1631static void rbio_update_error_bitmap(struct btrfs_raid_bio *rbio, struct bio *bio)
1632{
1633 int total_sector_nr = get_bio_sector_nr(rbio, bio);
1634 const u32 bio_size = bio_get_size(bio);
1635
1636 /*
1637 * Since we can have multiple bios touching the error_bitmap, we cannot
1638 * call bitmap_set() without protection.
1639 *
1640 * Instead use set_bit() for each bit, as set_bit() itself is atomic.
1641 */
1642 for (int i = total_sector_nr; i < total_sector_nr +
1643 (bio_size >> rbio->bioc->fs_info->sectorsize_bits); i++)
1644 set_bit(i, rbio->error_bitmap);
1645}
1646
1647/* Verify the data sectors at read time. */
1648static void verify_bio_data_sectors(struct btrfs_raid_bio *rbio,
1649 struct bio *bio)
1650{
1651 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
1652 int total_sector_nr = get_bio_sector_nr(rbio, bio);
1653
1654 /* No data csum for the whole stripe, no need to verify. */
1655 if (!rbio->csum_bitmap || !rbio->csum_buf)
1656 return;
1657
1658 /* P/Q stripes, they have no data csum to verify against. */
1659 if (total_sector_nr >= rbio->nr_data * rbio->stripe_nsectors)
1660 return;
1661
1662 for (struct bvec_iter iter = init_bvec_iter_for_bio(bio);
1663 iter.bi_size;
1664 bio_advance_iter(bio, &iter, fs_info->sectorsize), total_sector_nr++) {
1665 u8 csum_buf[BTRFS_CSUM_SIZE];
1666 u8 *expected_csum;
1667
1668 /* No csum for this sector, skip to the next sector. */
1669 if (!test_bit(total_sector_nr, rbio->csum_bitmap))
1670 continue;
1671
1672 expected_csum = rbio->csum_buf + total_sector_nr * fs_info->csum_size;
1673 btrfs_csum_one_bio_block(fs_info, bio, &iter, csum_buf);
1674 if (unlikely(memcmp(csum_buf, expected_csum, fs_info->csum_size) != 0))
1675 set_bit(total_sector_nr, rbio->error_bitmap);
1676 }
1677}
1678
1679static void raid_wait_read_end_io(struct bio *bio)
1680{
1681 struct btrfs_raid_bio *rbio = bio->bi_private;
1682
1683 if (bio->bi_status) {
1684 rbio_update_error_bitmap(rbio, bio);
1685 } else {
1686 set_bio_pages_uptodate(rbio, bio);
1687 verify_bio_data_sectors(rbio, bio);
1688 }
1689
1690 bio_put(bio);
1691 if (atomic_dec_and_test(&rbio->stripes_pending))
1692 wake_up(&rbio->io_wait);
1693}
1694
1695static void submit_read_wait_bio_list(struct btrfs_raid_bio *rbio,
1696 struct bio_list *bio_list)
1697{
1698 struct bio *bio;
1699
1700 atomic_set(&rbio->stripes_pending, bio_list_size(bio_list));
1701 while ((bio = bio_list_pop(bio_list))) {
1702 bio->bi_end_io = raid_wait_read_end_io;
1703
1704 if (trace_raid56_read_enabled()) {
1705 struct raid56_bio_trace_info trace_info = { 0 };
1706
1707 bio_get_trace_info(rbio, bio, &trace_info);
1708 trace_call__raid56_read(rbio, bio, &trace_info);
1709 }
1710 submit_bio(bio);
1711 }
1712
1713 wait_event(rbio->io_wait, atomic_read(&rbio->stripes_pending) == 0);
1714}
1715
1716static int alloc_rbio_data_pages(struct btrfs_raid_bio *rbio)
1717{
1718 const int data_pages = rbio->nr_data * rbio->stripe_npages;
1719 int ret;
1720
1721 ret = btrfs_alloc_page_array(data_pages, rbio->stripe_pages, GFP_NOFS);
1722 if (ret < 0)
1723 return ret;
1724
1725 index_stripe_sectors(rbio);
1726 return 0;
1727}
1728
1729/*
1730 * We use plugging call backs to collect full stripes.
1731 * Any time we get a partial stripe write while plugged
1732 * we collect it into a list. When the unplug comes down,
1733 * we sort the list by logical block number and merge
1734 * everything we can into the same rbios
1735 */
1736struct btrfs_plug_cb {
1737 struct blk_plug_cb cb;
1738 struct btrfs_fs_info *info;
1739 struct list_head rbio_list;
1740};
1741
1742/*
1743 * rbios on the plug list are sorted for easier merging.
1744 */
1745static int plug_cmp(void *priv, const struct list_head *a,
1746 const struct list_head *b)
1747{
1748 const struct btrfs_raid_bio *ra = container_of(a, struct btrfs_raid_bio,
1749 plug_list);
1750 const struct btrfs_raid_bio *rb = container_of(b, struct btrfs_raid_bio,
1751 plug_list);
1752 u64 a_sector = ra->bio_list.head->bi_iter.bi_sector;
1753 u64 b_sector = rb->bio_list.head->bi_iter.bi_sector;
1754
1755 if (a_sector < b_sector)
1756 return -1;
1757 if (a_sector > b_sector)
1758 return 1;
1759 return 0;
1760}
1761
1762static void raid_unplug(struct blk_plug_cb *cb, bool from_schedule)
1763{
1764 struct btrfs_plug_cb *plug = container_of(cb, struct btrfs_plug_cb, cb);
1765 struct btrfs_raid_bio *cur;
1766 struct btrfs_raid_bio *last = NULL;
1767
1768 list_sort(NULL, &plug->rbio_list, plug_cmp);
1769
1770 while (!list_empty(&plug->rbio_list)) {
1771 cur = list_first_entry(&plug->rbio_list,
1772 struct btrfs_raid_bio, plug_list);
1773 list_del_init(&cur->plug_list);
1774
1775 if (rbio_is_full(cur)) {
1776 /* We have a full stripe, queue it down. */
1777 start_async_work(cur, rmw_rbio_work);
1778 continue;
1779 }
1780 if (last) {
1781 if (rbio_can_merge(last, cur)) {
1782 merge_rbio(last, cur);
1783 free_raid_bio(cur);
1784 continue;
1785 }
1786 start_async_work(last, rmw_rbio_work);
1787 }
1788 last = cur;
1789 }
1790 if (last)
1791 start_async_work(last, rmw_rbio_work);
1792 kfree(plug);
1793}
1794
1795/* Add the original bio into rbio->bio_list, and update rbio::dbitmap. */
1796static void rbio_add_bio(struct btrfs_raid_bio *rbio, struct bio *orig_bio)
1797{
1798 const struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
1799 const u64 orig_logical = orig_bio->bi_iter.bi_sector << SECTOR_SHIFT;
1800 const u64 full_stripe_start = rbio->bioc->full_stripe_logical;
1801 const u32 orig_len = orig_bio->bi_iter.bi_size;
1802 const u32 sectorsize = fs_info->sectorsize;
1803 u64 cur_logical;
1804
1805 ASSERT_RBIO_LOGICAL(orig_logical >= full_stripe_start &&
1806 orig_logical + orig_len <= full_stripe_start +
1807 rbio->nr_data * BTRFS_STRIPE_LEN,
1808 rbio, orig_logical);
1809
1810 bio_list_add(&rbio->bio_list, orig_bio);
1811 rbio->bio_list_bytes += orig_bio->bi_iter.bi_size;
1812
1813 /* Update the dbitmap. */
1814 for (cur_logical = orig_logical; cur_logical < orig_logical + orig_len;
1815 cur_logical += sectorsize) {
1816 int bit = ((u32)(cur_logical - full_stripe_start) >>
1817 fs_info->sectorsize_bits) % rbio->stripe_nsectors;
1818
1819 set_bit(bit, &rbio->dbitmap);
1820 }
1821}
1822
1823/*
1824 * our main entry point for writes from the rest of the FS.
1825 */
1826void raid56_parity_write(struct bio *bio, struct btrfs_io_context *bioc)
1827{
1828 struct btrfs_fs_info *fs_info = bioc->fs_info;
1829 struct btrfs_raid_bio *rbio;
1830 struct btrfs_plug_cb *plug = NULL;
1831 struct blk_plug_cb *cb;
1832
1833 rbio = alloc_rbio(fs_info, bioc);
1834 if (IS_ERR(rbio)) {
1835 bio->bi_status = errno_to_blk_status(PTR_ERR(rbio));
1836 bio_endio(bio);
1837 return;
1838 }
1839 rbio->operation = BTRFS_RBIO_WRITE;
1840 rbio_add_bio(rbio, bio);
1841
1842 /*
1843 * Don't plug on full rbios, just get them out the door
1844 * as quickly as we can
1845 */
1846 if (!rbio_is_full(rbio)) {
1847 cb = blk_check_plugged(raid_unplug, fs_info, sizeof(*plug));
1848 if (cb) {
1849 plug = container_of(cb, struct btrfs_plug_cb, cb);
1850 if (!plug->info) {
1851 plug->info = fs_info;
1852 INIT_LIST_HEAD(&plug->rbio_list);
1853 }
1854 list_add_tail(&rbio->plug_list, &plug->rbio_list);
1855 return;
1856 }
1857 }
1858
1859 /*
1860 * Either we don't have any existing plug, or we're doing a full stripe,
1861 * queue the rmw work now.
1862 */
1863 start_async_work(rbio, rmw_rbio_work);
1864}
1865
1866static void calculate_block_csum_paddrs(struct btrfs_fs_info *fs_info,
1867 const phys_addr_t paddrs[], u8 *dest)
1868{
1869 const u32 blocksize = fs_info->sectorsize;
1870 const u32 step = min(blocksize, PAGE_SIZE);
1871 const u32 nr_steps = blocksize / step;
1872 struct btrfs_csum_ctx csum;
1873
1874 btrfs_csum_init(&csum, fs_info->csum_type);
1875 for (int i = 0; i < nr_steps; i++) {
1876 const phys_addr_t paddr = paddrs[i];
1877 void *kaddr;
1878
1879 ASSERT(offset_in_page(paddr) + step <= PAGE_SIZE);
1880 kaddr = kmap_local_page(phys_to_page(paddr)) + offset_in_page(paddr);
1881 btrfs_csum_update(&csum, kaddr, step);
1882 kunmap_local(kaddr);
1883 }
1884 btrfs_csum_final(&csum, dest);
1885}
1886
1887static int verify_one_sector(struct btrfs_raid_bio *rbio,
1888 int stripe_nr, int sector_nr)
1889{
1890 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
1891 phys_addr_t *paddrs;
1892 const unsigned int total_sector_nr =
1893 stripe_nr * rbio->stripe_nsectors + sector_nr;
1894 u8 csum_buf[BTRFS_CSUM_SIZE];
1895 u8 *csum_expected;
1896
1897 if (!rbio->csum_bitmap || !rbio->csum_buf)
1898 return 0;
1899
1900 /* No way to verify P/Q as they are not covered by data csum. */
1901 if (stripe_nr >= rbio->nr_data)
1902 return 0;
1903
1904 /* No data checksum for this sector. */
1905 if (!test_bit(total_sector_nr, rbio->csum_bitmap))
1906 return 0;
1907
1908 /*
1909 * If we're rebuilding a read, we have to use pages from the
1910 * bio list if possible.
1911 */
1912 if (rbio->operation == BTRFS_RBIO_READ_REBUILD) {
1913 paddrs = sector_paddrs_in_rbio(rbio, stripe_nr, sector_nr, 0);
1914 } else {
1915 paddrs = rbio_stripe_paddrs(rbio, stripe_nr, sector_nr);
1916 }
1917
1918 csum_expected = rbio->csum_buf + total_sector_nr * fs_info->csum_size;
1919 calculate_block_csum_paddrs(fs_info, paddrs, csum_buf);
1920 if (unlikely(memcmp(csum_buf, csum_expected, fs_info->csum_size) != 0))
1921 return -EIO;
1922 return 0;
1923}
1924
1925static void recover_vertical_step(struct btrfs_raid_bio *rbio,
1926 unsigned int sector_nr,
1927 unsigned int step_nr,
1928 int faila, int failb,
1929 void **pointers, void **unmap_array)
1930{
1931 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
1932 const u32 step = min(fs_info->sectorsize, PAGE_SIZE);
1933 int stripe_nr;
1934
1935 ASSERT(step_nr < rbio->sector_nsteps);
1936 ASSERT(sector_nr < rbio->stripe_nsectors);
1937
1938 /*
1939 * Setup our array of pointers with sectors from each stripe
1940 *
1941 * NOTE: store a duplicate array of pointers to preserve the
1942 * pointer order.
1943 */
1944 for (stripe_nr = 0; stripe_nr < rbio->real_stripes; stripe_nr++) {
1945 phys_addr_t paddr;
1946
1947 /*
1948 * If we're rebuilding a read, we have to use pages from the
1949 * bio list if possible.
1950 */
1951 if (rbio->operation == BTRFS_RBIO_READ_REBUILD) {
1952 paddr = sector_paddr_in_rbio(rbio, stripe_nr, sector_nr, step_nr, 0);
1953 } else {
1954 paddr = rbio_stripe_paddr(rbio, stripe_nr, sector_nr, step_nr);
1955 }
1956 pointers[stripe_nr] = kmap_local_paddr(paddr);
1957 unmap_array[stripe_nr] = pointers[stripe_nr];
1958 }
1959
1960 /* All raid6 handling here */
1961 if (rbio->bioc->map_type & BTRFS_BLOCK_GROUP_RAID6) {
1962 /* Single failure, rebuild from parity raid5 style */
1963 if (failb < 0) {
1964 if (faila == rbio->nr_data)
1965 /*
1966 * Just the P stripe has failed, without
1967 * a bad data or Q stripe.
1968 * We have nothing to do, just skip the
1969 * recovery for this stripe.
1970 */
1971 goto cleanup;
1972 /*
1973 * a single failure in raid6 is rebuilt
1974 * in the pstripe code below
1975 */
1976 goto pstripe;
1977 }
1978
1979 /*
1980 * If the q stripe is failed, do a pstripe reconstruction from
1981 * the xors.
1982 * If both the q stripe and the P stripe are failed, we're
1983 * here due to a crc mismatch and we can't give them the
1984 * data they want.
1985 */
1986 if (failb == rbio->real_stripes - 1) {
1987 if (faila == rbio->real_stripes - 2)
1988 /*
1989 * Only P and Q are corrupted.
1990 * We only care about data stripes recovery,
1991 * can skip this vertical stripe.
1992 */
1993 goto cleanup;
1994 /*
1995 * Otherwise we have one bad data stripe and
1996 * a good P stripe. raid5!
1997 */
1998 goto pstripe;
1999 }
2000
2001 if (failb == rbio->real_stripes - 2) {
2002 raid6_recov_datap(rbio->real_stripes, step,
2003 faila, pointers);
2004 } else {
2005 raid6_recov_2data(rbio->real_stripes, step,
2006 faila, failb, pointers);
2007 }
2008 } else {
2009 void *p;
2010
2011 /* Rebuild from P stripe here (raid5 or raid6). */
2012 ASSERT(failb == -1);
2013pstripe:
2014 /* Copy parity block into failed block to start with */
2015 memcpy(pointers[faila], pointers[rbio->nr_data], step);
2016
2017 /* Rearrange the pointer array */
2018 p = pointers[faila];
2019 for (stripe_nr = faila; stripe_nr < rbio->nr_data - 1;
2020 stripe_nr++)
2021 pointers[stripe_nr] = pointers[stripe_nr + 1];
2022 pointers[rbio->nr_data - 1] = p;
2023
2024 /* Xor in the rest */
2025 xor_gen(p, pointers, rbio->nr_data - 1, step);
2026 }
2027
2028cleanup:
2029 for (stripe_nr = rbio->real_stripes - 1; stripe_nr >= 0; stripe_nr--)
2030 kunmap_local(unmap_array[stripe_nr]);
2031}
2032
2033/*
2034 * Recover a vertical stripe specified by @sector_nr.
2035 * @*pointers are the pre-allocated pointers by the caller, so we don't
2036 * need to allocate/free the pointers again and again.
2037 */
2038static int recover_vertical(struct btrfs_raid_bio *rbio, int sector_nr,
2039 void **pointers, void **unmap_array)
2040{
2041 int found_errors;
2042 int faila;
2043 int failb;
2044 int ret = 0;
2045
2046 /*
2047 * Now we just use bitmap to mark the horizontal stripes in
2048 * which we have data when doing parity scrub.
2049 */
2050 if (rbio->operation == BTRFS_RBIO_PARITY_SCRUB &&
2051 !test_bit(sector_nr, &rbio->dbitmap))
2052 return 0;
2053
2054 found_errors = get_rbio_vertical_errors(rbio, sector_nr, &faila,
2055 &failb);
2056 /*
2057 * No errors in the vertical stripe, skip it. Can happen for recovery
2058 * which only part of a stripe failed csum check.
2059 */
2060 if (!found_errors)
2061 return 0;
2062
2063 if (unlikely(found_errors > rbio->bioc->max_errors))
2064 return -EIO;
2065
2066 for (int i = 0; i < rbio->sector_nsteps; i++)
2067 recover_vertical_step(rbio, sector_nr, i, faila, failb,
2068 pointers, unmap_array);
2069 if (faila >= 0) {
2070 ret = verify_one_sector(rbio, faila, sector_nr);
2071 if (ret < 0)
2072 return ret;
2073
2074 set_bit(rbio_sector_index(rbio, faila, sector_nr),
2075 rbio->stripe_uptodate_bitmap);
2076 }
2077 if (failb >= 0) {
2078 ret = verify_one_sector(rbio, failb, sector_nr);
2079 if (ret < 0)
2080 return ret;
2081
2082 set_bit(rbio_sector_index(rbio, failb, sector_nr),
2083 rbio->stripe_uptodate_bitmap);
2084 }
2085 return ret;
2086}
2087
2088static int recover_sectors(struct btrfs_raid_bio *rbio)
2089{
2090 void **pointers = NULL;
2091 void **unmap_array = NULL;
2092 int sectornr;
2093 int ret = 0;
2094
2095 /*
2096 * @pointers array stores the pointer for each sector.
2097 *
2098 * @unmap_array stores copy of pointers that does not get reordered
2099 * during reconstruction so that kunmap_local works.
2100 */
2101 pointers = kzalloc_objs(void *, rbio->real_stripes, GFP_NOFS);
2102 unmap_array = kzalloc_objs(void *, rbio->real_stripes, GFP_NOFS);
2103 if (!pointers || !unmap_array) {
2104 ret = -ENOMEM;
2105 goto out;
2106 }
2107
2108 if (rbio->operation == BTRFS_RBIO_READ_REBUILD) {
2109 spin_lock(&rbio->bio_list_lock);
2110 set_bit(RBIO_RMW_LOCKED_BIT, &rbio->flags);
2111 spin_unlock(&rbio->bio_list_lock);
2112 }
2113
2114 index_rbio_pages(rbio);
2115
2116 for (sectornr = 0; sectornr < rbio->stripe_nsectors; sectornr++) {
2117 ret = recover_vertical(rbio, sectornr, pointers, unmap_array);
2118 if (ret < 0)
2119 break;
2120 }
2121
2122out:
2123 kfree(pointers);
2124 kfree(unmap_array);
2125 return ret;
2126}
2127
2128static void recover_rbio(struct btrfs_raid_bio *rbio)
2129{
2130 struct bio_list bio_list = BIO_EMPTY_LIST;
2131 int total_sector_nr;
2132 int ret = 0;
2133
2134 /*
2135 * Either we're doing recover for a read failure or degraded write,
2136 * caller should have set error bitmap correctly.
2137 */
2138 ASSERT(bitmap_weight(rbio->error_bitmap, rbio->nr_sectors));
2139
2140 /* For recovery, we need to read all sectors including P/Q. */
2141 ret = alloc_rbio_pages(rbio);
2142 if (ret < 0)
2143 goto out;
2144
2145 index_rbio_pages(rbio);
2146
2147 /*
2148 * Read everything that hasn't failed. However this time we will
2149 * not trust any cached sector.
2150 * As we may read out some stale data but higher layer is not reading
2151 * that stale part.
2152 *
2153 * So here we always re-read everything in recovery path.
2154 */
2155 for (total_sector_nr = 0; total_sector_nr < rbio->nr_sectors;
2156 total_sector_nr++) {
2157 int stripe = total_sector_nr / rbio->stripe_nsectors;
2158 int sectornr = total_sector_nr % rbio->stripe_nsectors;
2159 phys_addr_t *paddrs;
2160
2161 /*
2162 * Skip the range which has error. It can be a range which is
2163 * marked error (for csum mismatch), or it can be a missing
2164 * device.
2165 */
2166 if (!rbio->bioc->stripes[stripe].dev->bdev ||
2167 test_bit(total_sector_nr, rbio->error_bitmap)) {
2168 /*
2169 * Also set the error bit for missing device, which
2170 * may not yet have its error bit set.
2171 */
2172 set_bit(total_sector_nr, rbio->error_bitmap);
2173 continue;
2174 }
2175
2176 paddrs = rbio_stripe_paddrs(rbio, stripe, sectornr);
2177 ret = rbio_add_io_paddrs(rbio, &bio_list, paddrs, stripe,
2178 sectornr, REQ_OP_READ);
2179 if (ret < 0) {
2180 bio_list_put(&bio_list);
2181 goto out;
2182 }
2183 }
2184
2185 submit_read_wait_bio_list(rbio, &bio_list);
2186 ret = recover_sectors(rbio);
2187out:
2188 rbio_orig_end_io(rbio, errno_to_blk_status(ret));
2189}
2190
2191static void recover_rbio_work(struct work_struct *work)
2192{
2193 struct btrfs_raid_bio *rbio;
2194
2195 rbio = container_of(work, struct btrfs_raid_bio, work);
2196 if (!lock_stripe_add(rbio))
2197 recover_rbio(rbio);
2198}
2199
2200static void recover_rbio_work_locked(struct work_struct *work)
2201{
2202 recover_rbio(container_of(work, struct btrfs_raid_bio, work));
2203}
2204
2205static void set_rbio_raid6_extra_error(struct btrfs_raid_bio *rbio, int mirror_num)
2206{
2207 bool found = false;
2208 int sector_nr;
2209
2210 /*
2211 * This is for RAID6 extra recovery tries, thus mirror number should
2212 * be large than 2.
2213 * Mirror 1 means read from data stripes. Mirror 2 means rebuild using
2214 * RAID5 methods.
2215 */
2216 ASSERT(mirror_num > 2);
2217 for (sector_nr = 0; sector_nr < rbio->stripe_nsectors; sector_nr++) {
2218 int found_errors;
2219 int faila;
2220 int failb;
2221
2222 found_errors = get_rbio_vertical_errors(rbio, sector_nr,
2223 &faila, &failb);
2224 /* This vertical stripe doesn't have errors. */
2225 if (!found_errors)
2226 continue;
2227
2228 /*
2229 * If we found errors, there should be only one error marked
2230 * by previous set_rbio_range_error().
2231 */
2232 ASSERT(found_errors == 1);
2233 found = true;
2234
2235 /* Now select another stripe to mark as error. */
2236 failb = rbio->real_stripes - (mirror_num - 1);
2237 if (failb <= faila)
2238 failb--;
2239
2240 /* Set the extra bit in error bitmap. */
2241 if (failb >= 0)
2242 set_bit(failb * rbio->stripe_nsectors + sector_nr,
2243 rbio->error_bitmap);
2244 }
2245
2246 /* We should found at least one vertical stripe with error.*/
2247 ASSERT(found);
2248}
2249
2250/*
2251 * the main entry point for reads from the higher layers. This
2252 * is really only called when the normal read path had a failure,
2253 * so we assume the bio they send down corresponds to a failed part
2254 * of the drive.
2255 */
2256void raid56_parity_recover(struct bio *bio, struct btrfs_io_context *bioc,
2257 int mirror_num)
2258{
2259 struct btrfs_fs_info *fs_info = bioc->fs_info;
2260 struct btrfs_raid_bio *rbio;
2261
2262 rbio = alloc_rbio(fs_info, bioc);
2263 if (IS_ERR(rbio)) {
2264 bio->bi_status = errno_to_blk_status(PTR_ERR(rbio));
2265 bio_endio(bio);
2266 return;
2267 }
2268
2269 rbio->operation = BTRFS_RBIO_READ_REBUILD;
2270 rbio_add_bio(rbio, bio);
2271
2272 set_rbio_range_error(rbio, bio);
2273
2274 /*
2275 * Loop retry:
2276 * for 'mirror == 2', reconstruct from all other stripes.
2277 * for 'mirror_num > 2', select a stripe to fail on every retry.
2278 */
2279 if (mirror_num > 2)
2280 set_rbio_raid6_extra_error(rbio, mirror_num);
2281
2282 start_async_work(rbio, recover_rbio_work);
2283}
2284
2285static void fill_data_csums(struct btrfs_raid_bio *rbio)
2286{
2287 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
2288 struct btrfs_root *csum_root;
2289 const u64 start = rbio->bioc->full_stripe_logical;
2290 const u32 len = (rbio->nr_data * rbio->stripe_nsectors) <<
2291 fs_info->sectorsize_bits;
2292 int ret;
2293
2294 /* The rbio should not have its csum buffer initialized. */
2295 ASSERT(!rbio->csum_buf && !rbio->csum_bitmap);
2296
2297 /*
2298 * Skip the csum search if:
2299 *
2300 * - The rbio doesn't belong to data block groups
2301 * Then we are doing IO for tree blocks, no need to search csums.
2302 *
2303 * - The rbio belongs to mixed block groups
2304 * This is to avoid deadlock, as we're already holding the full
2305 * stripe lock, if we trigger a metadata read, and it needs to do
2306 * raid56 recovery, we will deadlock.
2307 */
2308 if (!(rbio->bioc->map_type & BTRFS_BLOCK_GROUP_DATA) ||
2309 rbio->bioc->map_type & BTRFS_BLOCK_GROUP_METADATA)
2310 return;
2311
2312 rbio->csum_buf = kzalloc(rbio->nr_data * rbio->stripe_nsectors *
2313 fs_info->csum_size, GFP_NOFS);
2314 rbio->csum_bitmap = bitmap_zalloc(rbio->nr_data * rbio->stripe_nsectors,
2315 GFP_NOFS);
2316 if (!rbio->csum_buf || !rbio->csum_bitmap) {
2317 ret = -ENOMEM;
2318 goto error;
2319 }
2320
2321 csum_root = btrfs_csum_root(fs_info, rbio->bioc->full_stripe_logical);
2322 if (unlikely(!csum_root)) {
2323 btrfs_err(fs_info,
2324 "missing csum root for extent at bytenr %llu",
2325 rbio->bioc->full_stripe_logical);
2326 ret = -EUCLEAN;
2327 goto error;
2328 }
2329
2330 ret = btrfs_lookup_csums_bitmap(csum_root, NULL, start, start + len - 1,
2331 rbio->csum_buf, rbio->csum_bitmap);
2332 if (ret < 0)
2333 goto error;
2334 if (bitmap_empty(rbio->csum_bitmap, len >> fs_info->sectorsize_bits))
2335 goto no_csum;
2336 return;
2337
2338error:
2339 /*
2340 * We failed to allocate memory or grab the csum, but it's not fatal,
2341 * we can still continue. But better to warn users that RMW is no
2342 * longer safe for this particular sub-stripe write.
2343 */
2344 btrfs_warn_rl(fs_info,
2345"sub-stripe write for full stripe %llu is not safe, failed to get csum: %d",
2346 rbio->bioc->full_stripe_logical, ret);
2347no_csum:
2348 kfree(rbio->csum_buf);
2349 bitmap_free(rbio->csum_bitmap);
2350 rbio->csum_buf = NULL;
2351 rbio->csum_bitmap = NULL;
2352}
2353
2354static int rmw_read_wait_recover(struct btrfs_raid_bio *rbio)
2355{
2356 struct bio_list bio_list = BIO_EMPTY_LIST;
2357 int total_sector_nr;
2358 int ret = 0;
2359
2360 /*
2361 * Fill the data csums we need for data verification. We need to fill
2362 * the csum_bitmap/csum_buf first, as our endio function will try to
2363 * verify the data sectors.
2364 */
2365 fill_data_csums(rbio);
2366
2367 /*
2368 * Build a list of bios to read all sectors (including data and P/Q).
2369 *
2370 * This behavior is to compensate the later csum verification and recovery.
2371 */
2372 for (total_sector_nr = 0; total_sector_nr < rbio->nr_sectors;
2373 total_sector_nr++) {
2374 int stripe = total_sector_nr / rbio->stripe_nsectors;
2375 int sectornr = total_sector_nr % rbio->stripe_nsectors;
2376 phys_addr_t *paddrs;
2377
2378 paddrs = rbio_stripe_paddrs(rbio, stripe, sectornr);
2379 ret = rbio_add_io_paddrs(rbio, &bio_list, paddrs, stripe,
2380 sectornr, REQ_OP_READ);
2381 if (ret) {
2382 bio_list_put(&bio_list);
2383 return ret;
2384 }
2385 }
2386
2387 /*
2388 * We may or may not have any corrupted sectors (including missing dev
2389 * and csum mismatch), just let recover_sectors() to handle them all.
2390 */
2391 submit_read_wait_bio_list(rbio, &bio_list);
2392 return recover_sectors(rbio);
2393}
2394
2395static void raid_wait_write_end_io(struct bio *bio)
2396{
2397 struct btrfs_raid_bio *rbio = bio->bi_private;
2398
2399 if (bio->bi_status)
2400 rbio_update_error_bitmap(rbio, bio);
2401 bio_put(bio);
2402 if (atomic_dec_and_test(&rbio->stripes_pending))
2403 wake_up(&rbio->io_wait);
2404}
2405
2406static void submit_write_bios(struct btrfs_raid_bio *rbio,
2407 struct bio_list *bio_list)
2408{
2409 struct bio *bio;
2410
2411 atomic_set(&rbio->stripes_pending, bio_list_size(bio_list));
2412 while ((bio = bio_list_pop(bio_list))) {
2413 bio->bi_end_io = raid_wait_write_end_io;
2414
2415 if (trace_raid56_write_enabled()) {
2416 struct raid56_bio_trace_info trace_info = { 0 };
2417
2418 bio_get_trace_info(rbio, bio, &trace_info);
2419 trace_call__raid56_write(rbio, bio, &trace_info);
2420 }
2421 submit_bio(bio);
2422 }
2423}
2424
2425/*
2426 * To determine if we need to read any sector from the disk.
2427 * Should only be utilized in RMW path, to skip cached rbio.
2428 */
2429static bool need_read_stripe_sectors(struct btrfs_raid_bio *rbio)
2430{
2431 int i;
2432
2433 for (i = 0; i < rbio->nr_data * rbio->stripe_nsectors; i++) {
2434 phys_addr_t paddr = rbio->stripe_paddrs[i * rbio->sector_nsteps];
2435
2436 /*
2437 * We have a sector which doesn't have page nor uptodate,
2438 * thus this rbio can not be cached one, as cached one must
2439 * have all its data sectors present and uptodate.
2440 */
2441 if (paddr == INVALID_PADDR ||
2442 !test_bit(i, rbio->stripe_uptodate_bitmap))
2443 return true;
2444 }
2445 return false;
2446}
2447
2448static void rmw_rbio(struct btrfs_raid_bio *rbio)
2449{
2450 struct bio_list bio_list;
2451 int sectornr;
2452 int ret = 0;
2453
2454 /*
2455 * Allocate the pages for parity first, as P/Q pages will always be
2456 * needed for both full-stripe and sub-stripe writes.
2457 */
2458 ret = alloc_rbio_parity_pages(rbio);
2459 if (ret < 0)
2460 goto out;
2461
2462 /*
2463 * Either full stripe write, or we have every data sector already
2464 * cached, can go to write path immediately.
2465 */
2466 if (!rbio_is_full(rbio) && need_read_stripe_sectors(rbio)) {
2467 /*
2468 * Now we're doing sub-stripe write, also need all data stripes
2469 * to do the full RMW.
2470 */
2471 ret = alloc_rbio_data_pages(rbio);
2472 if (ret < 0)
2473 goto out;
2474
2475 index_rbio_pages(rbio);
2476
2477 ret = rmw_read_wait_recover(rbio);
2478 if (ret < 0)
2479 goto out;
2480 }
2481
2482 /*
2483 * At this stage we're not allowed to add any new bios to the
2484 * bio list any more, anyone else that wants to change this stripe
2485 * needs to do their own rmw.
2486 */
2487 spin_lock(&rbio->bio_list_lock);
2488 set_bit(RBIO_RMW_LOCKED_BIT, &rbio->flags);
2489 spin_unlock(&rbio->bio_list_lock);
2490
2491 bitmap_clear(rbio->error_bitmap, 0, rbio->nr_sectors);
2492
2493 index_rbio_pages(rbio);
2494
2495 /*
2496 * We don't cache full rbios because we're assuming
2497 * the higher layers are unlikely to use this area of
2498 * the disk again soon. If they do use it again,
2499 * hopefully they will send another full bio.
2500 */
2501 if (!rbio_is_full(rbio))
2502 cache_rbio_pages(rbio);
2503 else
2504 clear_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
2505
2506 for (sectornr = 0; sectornr < rbio->stripe_nsectors; sectornr++)
2507 generate_pq_vertical(rbio, sectornr);
2508
2509 bio_list_init(&bio_list);
2510 ret = rmw_assemble_write_bios(rbio, &bio_list);
2511 if (ret < 0)
2512 goto out;
2513
2514 /* We should have at least one bio assembled. */
2515 ASSERT(bio_list_size(&bio_list));
2516 submit_write_bios(rbio, &bio_list);
2517 wait_event(rbio->io_wait, atomic_read(&rbio->stripes_pending) == 0);
2518
2519 /* We may have more errors than our tolerance during the read. */
2520 for (sectornr = 0; sectornr < rbio->stripe_nsectors; sectornr++) {
2521 int found_errors;
2522
2523 found_errors = get_rbio_vertical_errors(rbio, sectornr, NULL, NULL);
2524 if (unlikely(found_errors > rbio->bioc->max_errors)) {
2525 ret = -EIO;
2526 break;
2527 }
2528 }
2529out:
2530 rbio_orig_end_io(rbio, errno_to_blk_status(ret));
2531}
2532
2533static void rmw_rbio_work(struct work_struct *work)
2534{
2535 struct btrfs_raid_bio *rbio;
2536
2537 rbio = container_of(work, struct btrfs_raid_bio, work);
2538 if (lock_stripe_add(rbio) == 0)
2539 rmw_rbio(rbio);
2540}
2541
2542static void rmw_rbio_work_locked(struct work_struct *work)
2543{
2544 rmw_rbio(container_of(work, struct btrfs_raid_bio, work));
2545}
2546
2547/*
2548 * The following code is used to scrub/replace the parity stripe
2549 *
2550 * Caller must have already increased bio_counter for getting @bioc.
2551 *
2552 * Note: We need make sure all the pages that add into the scrub/replace
2553 * raid bio are correct and not be changed during the scrub/replace. That
2554 * is those pages just hold metadata or file data with checksum.
2555 */
2556
2557struct btrfs_raid_bio *raid56_parity_alloc_scrub_rbio(struct bio *bio,
2558 struct btrfs_io_context *bioc,
2559 struct btrfs_device *scrub_dev,
2560 unsigned long *dbitmap, int stripe_nsectors)
2561{
2562 struct btrfs_fs_info *fs_info = bioc->fs_info;
2563 struct btrfs_raid_bio *rbio;
2564 int i;
2565
2566 rbio = alloc_rbio(fs_info, bioc);
2567 if (IS_ERR(rbio))
2568 return NULL;
2569 bio_list_add(&rbio->bio_list, bio);
2570 /*
2571 * This is a special bio which is used to hold the completion handler
2572 * and make the scrub rbio is similar to the other types
2573 */
2574 ASSERT(!bio->bi_iter.bi_size);
2575 rbio->operation = BTRFS_RBIO_PARITY_SCRUB;
2576
2577 /*
2578 * After mapping bioc with BTRFS_MAP_WRITE, parities have been sorted
2579 * to the end position, so this search can start from the first parity
2580 * stripe.
2581 */
2582 for (i = rbio->nr_data; i < rbio->real_stripes; i++) {
2583 if (bioc->stripes[i].dev == scrub_dev) {
2584 rbio->scrubp = i;
2585 break;
2586 }
2587 }
2588 ASSERT_RBIO_STRIPE(i < rbio->real_stripes, rbio, i);
2589
2590 bitmap_copy(&rbio->dbitmap, dbitmap, stripe_nsectors);
2591 return rbio;
2592}
2593
2594static int alloc_rbio_sector_pages(struct btrfs_raid_bio *rbio,
2595 int sector_nr)
2596{
2597 const u32 step = min(PAGE_SIZE, rbio->bioc->fs_info->sectorsize);
2598 const u32 base = sector_nr * rbio->sector_nsteps;
2599
2600 for (int i = base; i < base + rbio->sector_nsteps; i++) {
2601 const unsigned int page_index = (i * step) >> PAGE_SHIFT;
2602 struct page *page;
2603
2604 if (rbio->stripe_pages[page_index])
2605 continue;
2606 page = alloc_page(GFP_NOFS);
2607 if (!page)
2608 return -ENOMEM;
2609 rbio->stripe_pages[page_index] = page;
2610 }
2611 return 0;
2612}
2613
2614/*
2615 * We just scrub the parity that we have correct data on the same horizontal,
2616 * so we needn't allocate all pages for all the stripes.
2617 */
2618static int alloc_rbio_essential_pages(struct btrfs_raid_bio *rbio)
2619{
2620 int total_sector_nr;
2621
2622 for (total_sector_nr = 0; total_sector_nr < rbio->nr_sectors;
2623 total_sector_nr++) {
2624 int sectornr = total_sector_nr % rbio->stripe_nsectors;
2625 int ret;
2626
2627 if (!test_bit(sectornr, &rbio->dbitmap))
2628 continue;
2629 ret = alloc_rbio_sector_pages(rbio, total_sector_nr);
2630 if (ret < 0)
2631 return ret;
2632 }
2633 index_stripe_sectors(rbio);
2634 return 0;
2635}
2636
2637/* Return true if the content of the step matches the calculated one. */
2638static bool verify_one_parity_step(struct btrfs_raid_bio *rbio,
2639 void *pointers[], unsigned int sector_nr,
2640 unsigned int step_nr)
2641{
2642 const unsigned int nr_data = rbio->nr_data;
2643 const bool has_qstripe = (rbio->real_stripes - rbio->nr_data == 2);
2644 const u32 step = min(rbio->bioc->fs_info->sectorsize, PAGE_SIZE);
2645 void *parity;
2646 bool ret = false;
2647
2648 ASSERT(step_nr < rbio->sector_nsteps);
2649
2650 /* First collect one page from each data stripe. */
2651 for (int stripe = 0; stripe < nr_data; stripe++)
2652 pointers[stripe] = kmap_local_paddr(
2653 sector_paddr_in_rbio(rbio, stripe, sector_nr,
2654 step_nr, 0));
2655
2656 if (has_qstripe) {
2657 assert_rbio(rbio);
2658 /* RAID6, call the library function to fill in our P/Q. */
2659 raid6_gen_syndrome(rbio->real_stripes, step, pointers);
2660 } else {
2661 /* RAID5. */
2662 memcpy(pointers[nr_data], pointers[0], step);
2663 xor_gen(pointers[nr_data], pointers + 1, nr_data - 1, step);
2664 }
2665
2666 /* Check scrubbing parity and repair it. */
2667 parity = kmap_local_paddr(rbio_stripe_paddr(rbio, rbio->scrubp, sector_nr, step_nr));
2668 if (memcmp(parity, pointers[rbio->scrubp], step) != 0)
2669 memcpy(parity, pointers[rbio->scrubp], step);
2670 else
2671 ret = true;
2672 kunmap_local(parity);
2673
2674 for (int stripe = nr_data - 1; stripe >= 0; stripe--)
2675 kunmap_local(pointers[stripe]);
2676 return ret;
2677}
2678
2679/*
2680 * The @pointers array should have the P/Q parity already mapped.
2681 */
2682static void verify_one_parity_sector(struct btrfs_raid_bio *rbio,
2683 void *pointers[], unsigned int sector_nr)
2684{
2685 bool found_error = false;
2686
2687 for (int step_nr = 0; step_nr < rbio->sector_nsteps; step_nr++) {
2688 bool match;
2689
2690 match = verify_one_parity_step(rbio, pointers, sector_nr, step_nr);
2691 if (!match)
2692 found_error = true;
2693 }
2694 if (!found_error)
2695 bitmap_clear(&rbio->dbitmap, sector_nr, 1);
2696}
2697
2698static int finish_parity_scrub(struct btrfs_raid_bio *rbio)
2699{
2700 struct btrfs_io_context *bioc = rbio->bioc;
2701 void **pointers = rbio->finish_pointers;
2702 unsigned long *pbitmap = &rbio->finish_pbitmap;
2703 int nr_data = rbio->nr_data;
2704 int sectornr;
2705 bool has_qstripe;
2706 struct page *page;
2707 phys_addr_t p_paddr = INVALID_PADDR;
2708 phys_addr_t q_paddr = INVALID_PADDR;
2709 struct bio_list bio_list;
2710 bool is_replace = false;
2711 int ret;
2712
2713 bio_list_init(&bio_list);
2714
2715 if (rbio->real_stripes - rbio->nr_data == 1)
2716 has_qstripe = false;
2717 else if (rbio->real_stripes - rbio->nr_data == 2)
2718 has_qstripe = true;
2719 else
2720 BUG();
2721
2722 /*
2723 * Replace is running and our P/Q stripe is being replaced, then we
2724 * need to duplicate the final write to replace target.
2725 */
2726 if (bioc->replace_nr_stripes && bioc->replace_stripe_src == rbio->scrubp) {
2727 is_replace = true;
2728 bitmap_copy(pbitmap, &rbio->dbitmap, rbio->stripe_nsectors);
2729 }
2730
2731 /*
2732 * Because the higher layers(scrubber) are unlikely to
2733 * use this area of the disk again soon, so don't cache
2734 * it.
2735 */
2736 clear_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
2737
2738 page = alloc_page(GFP_NOFS);
2739 if (!page)
2740 return -ENOMEM;
2741 p_paddr = page_to_phys(page);
2742 page = NULL;
2743 pointers[nr_data] = kmap_local_paddr(p_paddr);
2744
2745 if (has_qstripe) {
2746 /* RAID6, allocate and map temp space for the Q stripe */
2747 page = alloc_page(GFP_NOFS);
2748 if (!page) {
2749 __free_page(phys_to_page(p_paddr));
2750 p_paddr = INVALID_PADDR;
2751 return -ENOMEM;
2752 }
2753 q_paddr = page_to_phys(page);
2754 page = NULL;
2755 pointers[rbio->real_stripes - 1] = kmap_local_paddr(q_paddr);
2756 }
2757
2758 bitmap_clear(rbio->error_bitmap, 0, rbio->nr_sectors);
2759
2760 /* Map the parity stripe just once */
2761
2762 for_each_set_bit(sectornr, &rbio->dbitmap, rbio->stripe_nsectors)
2763 verify_one_parity_sector(rbio, pointers, sectornr);
2764
2765 kunmap_local(pointers[nr_data]);
2766 __free_page(phys_to_page(p_paddr));
2767 p_paddr = INVALID_PADDR;
2768 if (q_paddr != INVALID_PADDR) {
2769 __free_page(phys_to_page(q_paddr));
2770 q_paddr = INVALID_PADDR;
2771 }
2772
2773 /*
2774 * time to start writing. Make bios for everything from the
2775 * higher layers (the bio_list in our rbio) and our p/q. Ignore
2776 * everything else.
2777 */
2778 for_each_set_bit(sectornr, &rbio->dbitmap, rbio->stripe_nsectors) {
2779 phys_addr_t *paddrs;
2780
2781 paddrs = rbio_stripe_paddrs(rbio, rbio->scrubp, sectornr);
2782 ret = rbio_add_io_paddrs(rbio, &bio_list, paddrs, rbio->scrubp,
2783 sectornr, REQ_OP_WRITE);
2784 if (ret)
2785 goto cleanup;
2786 }
2787
2788 if (!is_replace)
2789 goto submit_write;
2790
2791 /*
2792 * Replace is running and our parity stripe needs to be duplicated to
2793 * the target device. Check we have a valid source stripe number.
2794 */
2795 ASSERT_RBIO(rbio->bioc->replace_stripe_src >= 0, rbio);
2796 for_each_set_bit(sectornr, pbitmap, rbio->stripe_nsectors) {
2797 phys_addr_t *paddrs;
2798
2799 paddrs = rbio_stripe_paddrs(rbio, rbio->scrubp, sectornr);
2800 ret = rbio_add_io_paddrs(rbio, &bio_list, paddrs, rbio->real_stripes,
2801 sectornr, REQ_OP_WRITE);
2802 if (ret)
2803 goto cleanup;
2804 }
2805
2806submit_write:
2807 submit_write_bios(rbio, &bio_list);
2808 return 0;
2809
2810cleanup:
2811 bio_list_put(&bio_list);
2812 return ret;
2813}
2814
2815static inline int is_data_stripe(struct btrfs_raid_bio *rbio, int stripe)
2816{
2817 if (stripe >= 0 && stripe < rbio->nr_data)
2818 return 1;
2819 return 0;
2820}
2821
2822static int recover_scrub_rbio(struct btrfs_raid_bio *rbio)
2823{
2824 void **pointers = NULL;
2825 void **unmap_array = NULL;
2826 int sector_nr;
2827 int ret = 0;
2828
2829 /*
2830 * @pointers array stores the pointer for each sector.
2831 *
2832 * @unmap_array stores copy of pointers that does not get reordered
2833 * during reconstruction so that kunmap_local works.
2834 */
2835 pointers = kzalloc_objs(void *, rbio->real_stripes, GFP_NOFS);
2836 unmap_array = kzalloc_objs(void *, rbio->real_stripes, GFP_NOFS);
2837 if (!pointers || !unmap_array) {
2838 ret = -ENOMEM;
2839 goto out;
2840 }
2841
2842 for (sector_nr = 0; sector_nr < rbio->stripe_nsectors; sector_nr++) {
2843 int dfail = 0, failp = -1;
2844 int faila;
2845 int failb;
2846 int found_errors;
2847
2848 found_errors = get_rbio_vertical_errors(rbio, sector_nr,
2849 &faila, &failb);
2850 if (unlikely(found_errors > rbio->bioc->max_errors)) {
2851 ret = -EIO;
2852 goto out;
2853 }
2854 if (found_errors == 0)
2855 continue;
2856
2857 /* We should have at least one error here. */
2858 ASSERT(faila >= 0 || failb >= 0);
2859
2860 if (is_data_stripe(rbio, faila))
2861 dfail++;
2862 else if (is_parity_stripe(faila))
2863 failp = faila;
2864
2865 if (is_data_stripe(rbio, failb))
2866 dfail++;
2867 else if (is_parity_stripe(failb))
2868 failp = failb;
2869 /*
2870 * Because we can not use a scrubbing parity to repair the
2871 * data, so the capability of the repair is declined. (In the
2872 * case of RAID5, we can not repair anything.)
2873 */
2874 if (unlikely(dfail > rbio->bioc->max_errors - 1)) {
2875 ret = -EIO;
2876 goto out;
2877 }
2878 /*
2879 * If all data is good, only parity is correctly, just repair
2880 * the parity, no need to recover data stripes.
2881 */
2882 if (dfail == 0)
2883 continue;
2884
2885 /*
2886 * Here means we got one corrupted data stripe and one
2887 * corrupted parity on RAID6, if the corrupted parity is
2888 * scrubbing parity, luckily, use the other one to repair the
2889 * data, or we can not repair the data stripe.
2890 */
2891 if (unlikely(failp != rbio->scrubp)) {
2892 ret = -EIO;
2893 goto out;
2894 }
2895
2896 ret = recover_vertical(rbio, sector_nr, pointers, unmap_array);
2897 if (ret < 0)
2898 goto out;
2899 }
2900out:
2901 kfree(pointers);
2902 kfree(unmap_array);
2903 return ret;
2904}
2905
2906static int scrub_assemble_read_bios(struct btrfs_raid_bio *rbio)
2907{
2908 struct bio_list bio_list = BIO_EMPTY_LIST;
2909 int total_sector_nr;
2910 int ret = 0;
2911
2912 /* Build a list of bios to read all the missing parts. */
2913 for (total_sector_nr = 0; total_sector_nr < rbio->nr_sectors;
2914 total_sector_nr++) {
2915 int sectornr = total_sector_nr % rbio->stripe_nsectors;
2916 int stripe = total_sector_nr / rbio->stripe_nsectors;
2917 phys_addr_t *paddrs;
2918
2919 /* No data in the vertical stripe, no need to read. */
2920 if (!test_bit(sectornr, &rbio->dbitmap))
2921 continue;
2922
2923 /*
2924 * A parity-scrub rbio carries no data in its bio list: the
2925 * only bio there is the empty completion bio added by
2926 * raid56_parity_alloc_scrub_rbio(). Every sector is read
2927 * from the stripe, so only assert that invariant here.
2928 */
2929 ASSERT(!sector_paddrs_in_rbio(rbio, stripe, sectornr, 1));
2930
2931 paddrs = rbio_stripe_paddrs(rbio, stripe, sectornr);
2932 /*
2933 * The bio cache may have handed us an uptodate sector. If so,
2934 * use it.
2935 */
2936 if (test_bit(rbio_sector_index(rbio, stripe, sectornr),
2937 rbio->stripe_uptodate_bitmap))
2938 continue;
2939
2940 ret = rbio_add_io_paddrs(rbio, &bio_list, paddrs, stripe,
2941 sectornr, REQ_OP_READ);
2942 if (ret) {
2943 bio_list_put(&bio_list);
2944 return ret;
2945 }
2946 }
2947
2948 submit_read_wait_bio_list(rbio, &bio_list);
2949 return 0;
2950}
2951
2952static void scrub_rbio(struct btrfs_raid_bio *rbio)
2953{
2954 int sector_nr;
2955 int ret;
2956
2957 ret = alloc_rbio_essential_pages(rbio);
2958 if (ret)
2959 goto out;
2960
2961 bitmap_clear(rbio->error_bitmap, 0, rbio->nr_sectors);
2962
2963 ret = scrub_assemble_read_bios(rbio);
2964 if (ret < 0)
2965 goto out;
2966
2967 /* We may have some failures, recover the failed sectors first. */
2968 ret = recover_scrub_rbio(rbio);
2969 if (ret < 0)
2970 goto out;
2971
2972 /*
2973 * We have every sector properly prepared. Can finish the scrub
2974 * and writeback the good content.
2975 */
2976 ret = finish_parity_scrub(rbio);
2977 wait_event(rbio->io_wait, atomic_read(&rbio->stripes_pending) == 0);
2978 for (sector_nr = 0; sector_nr < rbio->stripe_nsectors; sector_nr++) {
2979 int found_errors;
2980
2981 found_errors = get_rbio_vertical_errors(rbio, sector_nr, NULL, NULL);
2982 if (unlikely(found_errors > rbio->bioc->max_errors)) {
2983 ret = -EIO;
2984 break;
2985 }
2986 }
2987out:
2988 rbio_orig_end_io(rbio, errno_to_blk_status(ret));
2989}
2990
2991static void scrub_rbio_work_locked(struct work_struct *work)
2992{
2993 scrub_rbio(container_of(work, struct btrfs_raid_bio, work));
2994}
2995
2996void raid56_parity_submit_scrub_rbio(struct btrfs_raid_bio *rbio)
2997{
2998 if (!lock_stripe_add(rbio))
2999 start_async_work(rbio, scrub_rbio_work_locked);
3000}
3001
3002/*
3003 * This is for scrub call sites where we already have correct data contents.
3004 * This allows us to avoid reading data stripes again.
3005 *
3006 * Unfortunately here we have to do folio copy, other than reusing the pages.
3007 * This is due to the fact rbio has its own page management for its cache.
3008 */
3009void raid56_parity_cache_data_folios(struct btrfs_raid_bio *rbio,
3010 void *vaddr, u64 data_logical)
3011{
3012 struct btrfs_fs_info *fs_info = rbio->bioc->fs_info;
3013 const u64 offset_in_full_stripe = data_logical -
3014 rbio->bioc->full_stripe_logical;
3015 int ret;
3016
3017 /*
3018 * If we hit ENOMEM temporarily, but later at
3019 * raid56_parity_submit_scrub_rbio() time it succeeded, we just do
3020 * the extra read, not a big deal.
3021 *
3022 * If we hit ENOMEM later at raid56_parity_submit_scrub_rbio() time,
3023 * the bio would got proper error number set.
3024 */
3025 ret = alloc_rbio_data_pages(rbio);
3026 if (ret < 0)
3027 return;
3028
3029 /* data_logical must be at stripe boundary and inside the full stripe. */
3030 ASSERT(IS_ALIGNED(offset_in_full_stripe, BTRFS_STRIPE_LEN));
3031 ASSERT(offset_in_full_stripe < (rbio->nr_data << BTRFS_STRIPE_LEN_SHIFT));
3032
3033 for (unsigned int cur_off = offset_in_full_stripe;
3034 cur_off < offset_in_full_stripe + BTRFS_STRIPE_LEN;
3035 cur_off += PAGE_SIZE) {
3036 const unsigned int pindex = cur_off >> PAGE_SHIFT;
3037
3038 ASSERT(cur_off - offset_in_full_stripe + PAGE_SIZE <= BTRFS_STRIPE_LEN);
3039 memcpy_to_page(rbio->stripe_pages[pindex], 0,
3040 vaddr + cur_off - offset_in_full_stripe, PAGE_SIZE);
3041 }
3042 bitmap_set(rbio->stripe_uptodate_bitmap,
3043 offset_in_full_stripe >> fs_info->sectorsize_bits,
3044 BTRFS_STRIPE_LEN >> fs_info->sectorsize_bits);
3045}