btrfs: use copy_page for copying pages instead of memcpy
[sfrench/cifs-2.6.git] / fs / btrfs / raid56.c
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/wait.h>
9 #include <linux/bio.h>
10 #include <linux/slab.h>
11 #include <linux/buffer_head.h>
12 #include <linux/blkdev.h>
13 #include <linux/random.h>
14 #include <linux/iocontext.h>
15 #include <linux/capability.h>
16 #include <linux/ratelimit.h>
17 #include <linux/kthread.h>
18 #include <linux/raid/pq.h>
19 #include <linux/hash.h>
20 #include <linux/list_sort.h>
21 #include <linux/raid/xor.h>
22 #include <linux/mm.h>
23 #include <asm/div64.h>
24 #include "ctree.h"
25 #include "extent_map.h"
26 #include "disk-io.h"
27 #include "transaction.h"
28 #include "print-tree.h"
29 #include "volumes.h"
30 #include "raid56.h"
31 #include "async-thread.h"
32 #include "check-integrity.h"
33 #include "rcu-string.h"
34
35 /* set when additional merges to this rbio are not allowed */
36 #define RBIO_RMW_LOCKED_BIT     1
37
38 /*
39  * set when this rbio is sitting in the hash, but it is just a cache
40  * of past RMW
41  */
42 #define RBIO_CACHE_BIT          2
43
44 /*
45  * set when it is safe to trust the stripe_pages for caching
46  */
47 #define RBIO_CACHE_READY_BIT    3
48
49 #define RBIO_CACHE_SIZE 1024
50
51 enum btrfs_rbio_ops {
52         BTRFS_RBIO_WRITE,
53         BTRFS_RBIO_READ_REBUILD,
54         BTRFS_RBIO_PARITY_SCRUB,
55         BTRFS_RBIO_REBUILD_MISSING,
56 };
57
58 struct btrfs_raid_bio {
59         struct btrfs_fs_info *fs_info;
60         struct btrfs_bio *bbio;
61
62         /* while we're doing rmw on a stripe
63          * we put it into a hash table so we can
64          * lock the stripe and merge more rbios
65          * into it.
66          */
67         struct list_head hash_list;
68
69         /*
70          * LRU list for the stripe cache
71          */
72         struct list_head stripe_cache;
73
74         /*
75          * for scheduling work in the helper threads
76          */
77         struct btrfs_work work;
78
79         /*
80          * bio list and bio_list_lock are used
81          * to add more bios into the stripe
82          * in hopes of avoiding the full rmw
83          */
84         struct bio_list bio_list;
85         spinlock_t bio_list_lock;
86
87         /* also protected by the bio_list_lock, the
88          * plug list is used by the plugging code
89          * to collect partial bios while plugged.  The
90          * stripe locking code also uses it to hand off
91          * the stripe lock to the next pending IO
92          */
93         struct list_head plug_list;
94
95         /*
96          * flags that tell us if it is safe to
97          * merge with this bio
98          */
99         unsigned long flags;
100
101         /* size of each individual stripe on disk */
102         int stripe_len;
103
104         /* number of data stripes (no p/q) */
105         int nr_data;
106
107         int real_stripes;
108
109         int stripe_npages;
110         /*
111          * set if we're doing a parity rebuild
112          * for a read from higher up, which is handled
113          * differently from a parity rebuild as part of
114          * rmw
115          */
116         enum btrfs_rbio_ops operation;
117
118         /* first bad stripe */
119         int faila;
120
121         /* second bad stripe (for raid6 use) */
122         int failb;
123
124         int scrubp;
125         /*
126          * number of pages needed to represent the full
127          * stripe
128          */
129         int nr_pages;
130
131         /*
132          * size of all the bios in the bio_list.  This
133          * helps us decide if the rbio maps to a full
134          * stripe or not
135          */
136         int bio_list_bytes;
137
138         int generic_bio_cnt;
139
140         refcount_t refs;
141
142         atomic_t stripes_pending;
143
144         atomic_t error;
145         /*
146          * these are two arrays of pointers.  We allocate the
147          * rbio big enough to hold them both and setup their
148          * locations when the rbio is allocated
149          */
150
151         /* pointers to pages that we allocated for
152          * reading/writing stripes directly from the disk (including P/Q)
153          */
154         struct page **stripe_pages;
155
156         /*
157          * pointers to the pages in the bio_list.  Stored
158          * here for faster lookup
159          */
160         struct page **bio_pages;
161
162         /*
163          * bitmap to record which horizontal stripe has data
164          */
165         unsigned long *dbitmap;
166
167         /* allocated with real_stripes-many pointers for finish_*() calls */
168         void **finish_pointers;
169
170         /* allocated with stripe_npages-many bits for finish_*() calls */
171         unsigned long *finish_pbitmap;
172 };
173
174 static int __raid56_parity_recover(struct btrfs_raid_bio *rbio);
175 static noinline void finish_rmw(struct btrfs_raid_bio *rbio);
176 static void rmw_work(struct btrfs_work *work);
177 static void read_rebuild_work(struct btrfs_work *work);
178 static void async_rmw_stripe(struct btrfs_raid_bio *rbio);
179 static void async_read_rebuild(struct btrfs_raid_bio *rbio);
180 static int fail_bio_stripe(struct btrfs_raid_bio *rbio, struct bio *bio);
181 static int fail_rbio_index(struct btrfs_raid_bio *rbio, int failed);
182 static void __free_raid_bio(struct btrfs_raid_bio *rbio);
183 static void index_rbio_pages(struct btrfs_raid_bio *rbio);
184 static int alloc_rbio_pages(struct btrfs_raid_bio *rbio);
185
186 static noinline void finish_parity_scrub(struct btrfs_raid_bio *rbio,
187                                          int need_check);
188 static void async_scrub_parity(struct btrfs_raid_bio *rbio);
189
190 /*
191  * the stripe hash table is used for locking, and to collect
192  * bios in hopes of making a full stripe
193  */
194 int btrfs_alloc_stripe_hash_table(struct btrfs_fs_info *info)
195 {
196         struct btrfs_stripe_hash_table *table;
197         struct btrfs_stripe_hash_table *x;
198         struct btrfs_stripe_hash *cur;
199         struct btrfs_stripe_hash *h;
200         int num_entries = 1 << BTRFS_STRIPE_HASH_TABLE_BITS;
201         int i;
202         int table_size;
203
204         if (info->stripe_hash_table)
205                 return 0;
206
207         /*
208          * The table is large, starting with order 4 and can go as high as
209          * order 7 in case lock debugging is turned on.
210          *
211          * Try harder to allocate and fallback to vmalloc to lower the chance
212          * of a failing mount.
213          */
214         table_size = sizeof(*table) + sizeof(*h) * num_entries;
215         table = kvzalloc(table_size, GFP_KERNEL);
216         if (!table)
217                 return -ENOMEM;
218
219         spin_lock_init(&table->cache_lock);
220         INIT_LIST_HEAD(&table->stripe_cache);
221
222         h = table->table;
223
224         for (i = 0; i < num_entries; i++) {
225                 cur = h + i;
226                 INIT_LIST_HEAD(&cur->hash_list);
227                 spin_lock_init(&cur->lock);
228         }
229
230         x = cmpxchg(&info->stripe_hash_table, NULL, table);
231         if (x)
232                 kvfree(x);
233         return 0;
234 }
235
236 /*
237  * caching an rbio means to copy anything from the
238  * bio_pages array into the stripe_pages array.  We
239  * use the page uptodate bit in the stripe cache array
240  * to indicate if it has valid data
241  *
242  * once the caching is done, we set the cache ready
243  * bit.
244  */
245 static void cache_rbio_pages(struct btrfs_raid_bio *rbio)
246 {
247         int i;
248         char *s;
249         char *d;
250         int ret;
251
252         ret = alloc_rbio_pages(rbio);
253         if (ret)
254                 return;
255
256         for (i = 0; i < rbio->nr_pages; i++) {
257                 if (!rbio->bio_pages[i])
258                         continue;
259
260                 s = kmap(rbio->bio_pages[i]);
261                 d = kmap(rbio->stripe_pages[i]);
262
263                 copy_page(d, s);
264
265                 kunmap(rbio->bio_pages[i]);
266                 kunmap(rbio->stripe_pages[i]);
267                 SetPageUptodate(rbio->stripe_pages[i]);
268         }
269         set_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
270 }
271
272 /*
273  * we hash on the first logical address of the stripe
274  */
275 static int rbio_bucket(struct btrfs_raid_bio *rbio)
276 {
277         u64 num = rbio->bbio->raid_map[0];
278
279         /*
280          * we shift down quite a bit.  We're using byte
281          * addressing, and most of the lower bits are zeros.
282          * This tends to upset hash_64, and it consistently
283          * returns just one or two different values.
284          *
285          * shifting off the lower bits fixes things.
286          */
287         return hash_64(num >> 16, BTRFS_STRIPE_HASH_TABLE_BITS);
288 }
289
290 /*
291  * stealing an rbio means taking all the uptodate pages from the stripe
292  * array in the source rbio and putting them into the destination rbio
293  */
294 static void steal_rbio(struct btrfs_raid_bio *src, struct btrfs_raid_bio *dest)
295 {
296         int i;
297         struct page *s;
298         struct page *d;
299
300         if (!test_bit(RBIO_CACHE_READY_BIT, &src->flags))
301                 return;
302
303         for (i = 0; i < dest->nr_pages; i++) {
304                 s = src->stripe_pages[i];
305                 if (!s || !PageUptodate(s)) {
306                         continue;
307                 }
308
309                 d = dest->stripe_pages[i];
310                 if (d)
311                         __free_page(d);
312
313                 dest->stripe_pages[i] = s;
314                 src->stripe_pages[i] = NULL;
315         }
316 }
317
318 /*
319  * merging means we take the bio_list from the victim and
320  * splice it into the destination.  The victim should
321  * be discarded afterwards.
322  *
323  * must be called with dest->rbio_list_lock held
324  */
325 static void merge_rbio(struct btrfs_raid_bio *dest,
326                        struct btrfs_raid_bio *victim)
327 {
328         bio_list_merge(&dest->bio_list, &victim->bio_list);
329         dest->bio_list_bytes += victim->bio_list_bytes;
330         dest->generic_bio_cnt += victim->generic_bio_cnt;
331         bio_list_init(&victim->bio_list);
332 }
333
334 /*
335  * used to prune items that are in the cache.  The caller
336  * must hold the hash table lock.
337  */
338 static void __remove_rbio_from_cache(struct btrfs_raid_bio *rbio)
339 {
340         int bucket = rbio_bucket(rbio);
341         struct btrfs_stripe_hash_table *table;
342         struct btrfs_stripe_hash *h;
343         int freeit = 0;
344
345         /*
346          * check the bit again under the hash table lock.
347          */
348         if (!test_bit(RBIO_CACHE_BIT, &rbio->flags))
349                 return;
350
351         table = rbio->fs_info->stripe_hash_table;
352         h = table->table + bucket;
353
354         /* hold the lock for the bucket because we may be
355          * removing it from the hash table
356          */
357         spin_lock(&h->lock);
358
359         /*
360          * hold the lock for the bio list because we need
361          * to make sure the bio list is empty
362          */
363         spin_lock(&rbio->bio_list_lock);
364
365         if (test_and_clear_bit(RBIO_CACHE_BIT, &rbio->flags)) {
366                 list_del_init(&rbio->stripe_cache);
367                 table->cache_size -= 1;
368                 freeit = 1;
369
370                 /* if the bio list isn't empty, this rbio is
371                  * still involved in an IO.  We take it out
372                  * of the cache list, and drop the ref that
373                  * was held for the list.
374                  *
375                  * If the bio_list was empty, we also remove
376                  * the rbio from the hash_table, and drop
377                  * the corresponding ref
378                  */
379                 if (bio_list_empty(&rbio->bio_list)) {
380                         if (!list_empty(&rbio->hash_list)) {
381                                 list_del_init(&rbio->hash_list);
382                                 refcount_dec(&rbio->refs);
383                                 BUG_ON(!list_empty(&rbio->plug_list));
384                         }
385                 }
386         }
387
388         spin_unlock(&rbio->bio_list_lock);
389         spin_unlock(&h->lock);
390
391         if (freeit)
392                 __free_raid_bio(rbio);
393 }
394
395 /*
396  * prune a given rbio from the cache
397  */
398 static void remove_rbio_from_cache(struct btrfs_raid_bio *rbio)
399 {
400         struct btrfs_stripe_hash_table *table;
401         unsigned long flags;
402
403         if (!test_bit(RBIO_CACHE_BIT, &rbio->flags))
404                 return;
405
406         table = rbio->fs_info->stripe_hash_table;
407
408         spin_lock_irqsave(&table->cache_lock, flags);
409         __remove_rbio_from_cache(rbio);
410         spin_unlock_irqrestore(&table->cache_lock, flags);
411 }
412
413 /*
414  * remove everything in the cache
415  */
416 static void btrfs_clear_rbio_cache(struct btrfs_fs_info *info)
417 {
418         struct btrfs_stripe_hash_table *table;
419         unsigned long flags;
420         struct btrfs_raid_bio *rbio;
421
422         table = info->stripe_hash_table;
423
424         spin_lock_irqsave(&table->cache_lock, flags);
425         while (!list_empty(&table->stripe_cache)) {
426                 rbio = list_entry(table->stripe_cache.next,
427                                   struct btrfs_raid_bio,
428                                   stripe_cache);
429                 __remove_rbio_from_cache(rbio);
430         }
431         spin_unlock_irqrestore(&table->cache_lock, flags);
432 }
433
434 /*
435  * remove all cached entries and free the hash table
436  * used by unmount
437  */
438 void btrfs_free_stripe_hash_table(struct btrfs_fs_info *info)
439 {
440         if (!info->stripe_hash_table)
441                 return;
442         btrfs_clear_rbio_cache(info);
443         kvfree(info->stripe_hash_table);
444         info->stripe_hash_table = NULL;
445 }
446
447 /*
448  * insert an rbio into the stripe cache.  It
449  * must have already been prepared by calling
450  * cache_rbio_pages
451  *
452  * If this rbio was already cached, it gets
453  * moved to the front of the lru.
454  *
455  * If the size of the rbio cache is too big, we
456  * prune an item.
457  */
458 static void cache_rbio(struct btrfs_raid_bio *rbio)
459 {
460         struct btrfs_stripe_hash_table *table;
461         unsigned long flags;
462
463         if (!test_bit(RBIO_CACHE_READY_BIT, &rbio->flags))
464                 return;
465
466         table = rbio->fs_info->stripe_hash_table;
467
468         spin_lock_irqsave(&table->cache_lock, flags);
469         spin_lock(&rbio->bio_list_lock);
470
471         /* bump our ref if we were not in the list before */
472         if (!test_and_set_bit(RBIO_CACHE_BIT, &rbio->flags))
473                 refcount_inc(&rbio->refs);
474
475         if (!list_empty(&rbio->stripe_cache)){
476                 list_move(&rbio->stripe_cache, &table->stripe_cache);
477         } else {
478                 list_add(&rbio->stripe_cache, &table->stripe_cache);
479                 table->cache_size += 1;
480         }
481
482         spin_unlock(&rbio->bio_list_lock);
483
484         if (table->cache_size > RBIO_CACHE_SIZE) {
485                 struct btrfs_raid_bio *found;
486
487                 found = list_entry(table->stripe_cache.prev,
488                                   struct btrfs_raid_bio,
489                                   stripe_cache);
490
491                 if (found != rbio)
492                         __remove_rbio_from_cache(found);
493         }
494
495         spin_unlock_irqrestore(&table->cache_lock, flags);
496 }
497
498 /*
499  * helper function to run the xor_blocks api.  It is only
500  * able to do MAX_XOR_BLOCKS at a time, so we need to
501  * loop through.
502  */
503 static void run_xor(void **pages, int src_cnt, ssize_t len)
504 {
505         int src_off = 0;
506         int xor_src_cnt = 0;
507         void *dest = pages[src_cnt];
508
509         while(src_cnt > 0) {
510                 xor_src_cnt = min(src_cnt, MAX_XOR_BLOCKS);
511                 xor_blocks(xor_src_cnt, len, dest, pages + src_off);
512
513                 src_cnt -= xor_src_cnt;
514                 src_off += xor_src_cnt;
515         }
516 }
517
518 /*
519  * returns true if the bio list inside this rbio
520  * covers an entire stripe (no rmw required).
521  * Must be called with the bio list lock held, or
522  * at a time when you know it is impossible to add
523  * new bios into the list
524  */
525 static int __rbio_is_full(struct btrfs_raid_bio *rbio)
526 {
527         unsigned long size = rbio->bio_list_bytes;
528         int ret = 1;
529
530         if (size != rbio->nr_data * rbio->stripe_len)
531                 ret = 0;
532
533         BUG_ON(size > rbio->nr_data * rbio->stripe_len);
534         return ret;
535 }
536
537 static int rbio_is_full(struct btrfs_raid_bio *rbio)
538 {
539         unsigned long flags;
540         int ret;
541
542         spin_lock_irqsave(&rbio->bio_list_lock, flags);
543         ret = __rbio_is_full(rbio);
544         spin_unlock_irqrestore(&rbio->bio_list_lock, flags);
545         return ret;
546 }
547
548 /*
549  * returns 1 if it is safe to merge two rbios together.
550  * The merging is safe if the two rbios correspond to
551  * the same stripe and if they are both going in the same
552  * direction (read vs write), and if neither one is
553  * locked for final IO
554  *
555  * The caller is responsible for locking such that
556  * rmw_locked is safe to test
557  */
558 static int rbio_can_merge(struct btrfs_raid_bio *last,
559                           struct btrfs_raid_bio *cur)
560 {
561         if (test_bit(RBIO_RMW_LOCKED_BIT, &last->flags) ||
562             test_bit(RBIO_RMW_LOCKED_BIT, &cur->flags))
563                 return 0;
564
565         /*
566          * we can't merge with cached rbios, since the
567          * idea is that when we merge the destination
568          * rbio is going to run our IO for us.  We can
569          * steal from cached rbios though, other functions
570          * handle that.
571          */
572         if (test_bit(RBIO_CACHE_BIT, &last->flags) ||
573             test_bit(RBIO_CACHE_BIT, &cur->flags))
574                 return 0;
575
576         if (last->bbio->raid_map[0] !=
577             cur->bbio->raid_map[0])
578                 return 0;
579
580         /* we can't merge with different operations */
581         if (last->operation != cur->operation)
582                 return 0;
583         /*
584          * We've need read the full stripe from the drive.
585          * check and repair the parity and write the new results.
586          *
587          * We're not allowed to add any new bios to the
588          * bio list here, anyone else that wants to
589          * change this stripe needs to do their own rmw.
590          */
591         if (last->operation == BTRFS_RBIO_PARITY_SCRUB)
592                 return 0;
593
594         if (last->operation == BTRFS_RBIO_REBUILD_MISSING)
595                 return 0;
596
597         if (last->operation == BTRFS_RBIO_READ_REBUILD) {
598                 int fa = last->faila;
599                 int fb = last->failb;
600                 int cur_fa = cur->faila;
601                 int cur_fb = cur->failb;
602
603                 if (last->faila >= last->failb) {
604                         fa = last->failb;
605                         fb = last->faila;
606                 }
607
608                 if (cur->faila >= cur->failb) {
609                         cur_fa = cur->failb;
610                         cur_fb = cur->faila;
611                 }
612
613                 if (fa != cur_fa || fb != cur_fb)
614                         return 0;
615         }
616         return 1;
617 }
618
619 static int rbio_stripe_page_index(struct btrfs_raid_bio *rbio, int stripe,
620                                   int index)
621 {
622         return stripe * rbio->stripe_npages + index;
623 }
624
625 /*
626  * these are just the pages from the rbio array, not from anything
627  * the FS sent down to us
628  */
629 static struct page *rbio_stripe_page(struct btrfs_raid_bio *rbio, int stripe,
630                                      int index)
631 {
632         return rbio->stripe_pages[rbio_stripe_page_index(rbio, stripe, index)];
633 }
634
635 /*
636  * helper to index into the pstripe
637  */
638 static struct page *rbio_pstripe_page(struct btrfs_raid_bio *rbio, int index)
639 {
640         return rbio_stripe_page(rbio, rbio->nr_data, index);
641 }
642
643 /*
644  * helper to index into the qstripe, returns null
645  * if there is no qstripe
646  */
647 static struct page *rbio_qstripe_page(struct btrfs_raid_bio *rbio, int index)
648 {
649         if (rbio->nr_data + 1 == rbio->real_stripes)
650                 return NULL;
651         return rbio_stripe_page(rbio, rbio->nr_data + 1, index);
652 }
653
654 /*
655  * The first stripe in the table for a logical address
656  * has the lock.  rbios are added in one of three ways:
657  *
658  * 1) Nobody has the stripe locked yet.  The rbio is given
659  * the lock and 0 is returned.  The caller must start the IO
660  * themselves.
661  *
662  * 2) Someone has the stripe locked, but we're able to merge
663  * with the lock owner.  The rbio is freed and the IO will
664  * start automatically along with the existing rbio.  1 is returned.
665  *
666  * 3) Someone has the stripe locked, but we're not able to merge.
667  * The rbio is added to the lock owner's plug list, or merged into
668  * an rbio already on the plug list.  When the lock owner unlocks,
669  * the next rbio on the list is run and the IO is started automatically.
670  * 1 is returned
671  *
672  * If we return 0, the caller still owns the rbio and must continue with
673  * IO submission.  If we return 1, the caller must assume the rbio has
674  * already been freed.
675  */
676 static noinline int lock_stripe_add(struct btrfs_raid_bio *rbio)
677 {
678         int bucket = rbio_bucket(rbio);
679         struct btrfs_stripe_hash *h = rbio->fs_info->stripe_hash_table->table + bucket;
680         struct btrfs_raid_bio *cur;
681         struct btrfs_raid_bio *pending;
682         unsigned long flags;
683         struct btrfs_raid_bio *freeit = NULL;
684         struct btrfs_raid_bio *cache_drop = NULL;
685         int ret = 0;
686
687         spin_lock_irqsave(&h->lock, flags);
688         list_for_each_entry(cur, &h->hash_list, hash_list) {
689                 if (cur->bbio->raid_map[0] == rbio->bbio->raid_map[0]) {
690                         spin_lock(&cur->bio_list_lock);
691
692                         /* can we steal this cached rbio's pages? */
693                         if (bio_list_empty(&cur->bio_list) &&
694                             list_empty(&cur->plug_list) &&
695                             test_bit(RBIO_CACHE_BIT, &cur->flags) &&
696                             !test_bit(RBIO_RMW_LOCKED_BIT, &cur->flags)) {
697                                 list_del_init(&cur->hash_list);
698                                 refcount_dec(&cur->refs);
699
700                                 steal_rbio(cur, rbio);
701                                 cache_drop = cur;
702                                 spin_unlock(&cur->bio_list_lock);
703
704                                 goto lockit;
705                         }
706
707                         /* can we merge into the lock owner? */
708                         if (rbio_can_merge(cur, rbio)) {
709                                 merge_rbio(cur, rbio);
710                                 spin_unlock(&cur->bio_list_lock);
711                                 freeit = rbio;
712                                 ret = 1;
713                                 goto out;
714                         }
715
716
717                         /*
718                          * we couldn't merge with the running
719                          * rbio, see if we can merge with the
720                          * pending ones.  We don't have to
721                          * check for rmw_locked because there
722                          * is no way they are inside finish_rmw
723                          * right now
724                          */
725                         list_for_each_entry(pending, &cur->plug_list,
726                                             plug_list) {
727                                 if (rbio_can_merge(pending, rbio)) {
728                                         merge_rbio(pending, rbio);
729                                         spin_unlock(&cur->bio_list_lock);
730                                         freeit = rbio;
731                                         ret = 1;
732                                         goto out;
733                                 }
734                         }
735
736                         /* no merging, put us on the tail of the plug list,
737                          * our rbio will be started with the currently
738                          * running rbio unlocks
739                          */
740                         list_add_tail(&rbio->plug_list, &cur->plug_list);
741                         spin_unlock(&cur->bio_list_lock);
742                         ret = 1;
743                         goto out;
744                 }
745         }
746 lockit:
747         refcount_inc(&rbio->refs);
748         list_add(&rbio->hash_list, &h->hash_list);
749 out:
750         spin_unlock_irqrestore(&h->lock, flags);
751         if (cache_drop)
752                 remove_rbio_from_cache(cache_drop);
753         if (freeit)
754                 __free_raid_bio(freeit);
755         return ret;
756 }
757
758 /*
759  * called as rmw or parity rebuild is completed.  If the plug list has more
760  * rbios waiting for this stripe, the next one on the list will be started
761  */
762 static noinline void unlock_stripe(struct btrfs_raid_bio *rbio)
763 {
764         int bucket;
765         struct btrfs_stripe_hash *h;
766         unsigned long flags;
767         int keep_cache = 0;
768
769         bucket = rbio_bucket(rbio);
770         h = rbio->fs_info->stripe_hash_table->table + bucket;
771
772         if (list_empty(&rbio->plug_list))
773                 cache_rbio(rbio);
774
775         spin_lock_irqsave(&h->lock, flags);
776         spin_lock(&rbio->bio_list_lock);
777
778         if (!list_empty(&rbio->hash_list)) {
779                 /*
780                  * if we're still cached and there is no other IO
781                  * to perform, just leave this rbio here for others
782                  * to steal from later
783                  */
784                 if (list_empty(&rbio->plug_list) &&
785                     test_bit(RBIO_CACHE_BIT, &rbio->flags)) {
786                         keep_cache = 1;
787                         clear_bit(RBIO_RMW_LOCKED_BIT, &rbio->flags);
788                         BUG_ON(!bio_list_empty(&rbio->bio_list));
789                         goto done;
790                 }
791
792                 list_del_init(&rbio->hash_list);
793                 refcount_dec(&rbio->refs);
794
795                 /*
796                  * we use the plug list to hold all the rbios
797                  * waiting for the chance to lock this stripe.
798                  * hand the lock over to one of them.
799                  */
800                 if (!list_empty(&rbio->plug_list)) {
801                         struct btrfs_raid_bio *next;
802                         struct list_head *head = rbio->plug_list.next;
803
804                         next = list_entry(head, struct btrfs_raid_bio,
805                                           plug_list);
806
807                         list_del_init(&rbio->plug_list);
808
809                         list_add(&next->hash_list, &h->hash_list);
810                         refcount_inc(&next->refs);
811                         spin_unlock(&rbio->bio_list_lock);
812                         spin_unlock_irqrestore(&h->lock, flags);
813
814                         if (next->operation == BTRFS_RBIO_READ_REBUILD)
815                                 async_read_rebuild(next);
816                         else if (next->operation == BTRFS_RBIO_REBUILD_MISSING) {
817                                 steal_rbio(rbio, next);
818                                 async_read_rebuild(next);
819                         } else if (next->operation == BTRFS_RBIO_WRITE) {
820                                 steal_rbio(rbio, next);
821                                 async_rmw_stripe(next);
822                         } else if (next->operation == BTRFS_RBIO_PARITY_SCRUB) {
823                                 steal_rbio(rbio, next);
824                                 async_scrub_parity(next);
825                         }
826
827                         goto done_nolock;
828                 }
829         }
830 done:
831         spin_unlock(&rbio->bio_list_lock);
832         spin_unlock_irqrestore(&h->lock, flags);
833
834 done_nolock:
835         if (!keep_cache)
836                 remove_rbio_from_cache(rbio);
837 }
838
839 static void __free_raid_bio(struct btrfs_raid_bio *rbio)
840 {
841         int i;
842
843         if (!refcount_dec_and_test(&rbio->refs))
844                 return;
845
846         WARN_ON(!list_empty(&rbio->stripe_cache));
847         WARN_ON(!list_empty(&rbio->hash_list));
848         WARN_ON(!bio_list_empty(&rbio->bio_list));
849
850         for (i = 0; i < rbio->nr_pages; i++) {
851                 if (rbio->stripe_pages[i]) {
852                         __free_page(rbio->stripe_pages[i]);
853                         rbio->stripe_pages[i] = NULL;
854                 }
855         }
856
857         btrfs_put_bbio(rbio->bbio);
858         kfree(rbio);
859 }
860
861 static void rbio_endio_bio_list(struct bio *cur, blk_status_t err)
862 {
863         struct bio *next;
864
865         while (cur) {
866                 next = cur->bi_next;
867                 cur->bi_next = NULL;
868                 cur->bi_status = err;
869                 bio_endio(cur);
870                 cur = next;
871         }
872 }
873
874 /*
875  * this frees the rbio and runs through all the bios in the
876  * bio_list and calls end_io on them
877  */
878 static void rbio_orig_end_io(struct btrfs_raid_bio *rbio, blk_status_t err)
879 {
880         struct bio *cur = bio_list_get(&rbio->bio_list);
881         struct bio *extra;
882
883         if (rbio->generic_bio_cnt)
884                 btrfs_bio_counter_sub(rbio->fs_info, rbio->generic_bio_cnt);
885
886         /*
887          * At this moment, rbio->bio_list is empty, however since rbio does not
888          * always have RBIO_RMW_LOCKED_BIT set and rbio is still linked on the
889          * hash list, rbio may be merged with others so that rbio->bio_list
890          * becomes non-empty.
891          * Once unlock_stripe() is done, rbio->bio_list will not be updated any
892          * more and we can call bio_endio() on all queued bios.
893          */
894         unlock_stripe(rbio);
895         extra = bio_list_get(&rbio->bio_list);
896         __free_raid_bio(rbio);
897
898         rbio_endio_bio_list(cur, err);
899         if (extra)
900                 rbio_endio_bio_list(extra, err);
901 }
902
903 /*
904  * end io function used by finish_rmw.  When we finally
905  * get here, we've written a full stripe
906  */
907 static void raid_write_end_io(struct bio *bio)
908 {
909         struct btrfs_raid_bio *rbio = bio->bi_private;
910         blk_status_t err = bio->bi_status;
911         int max_errors;
912
913         if (err)
914                 fail_bio_stripe(rbio, bio);
915
916         bio_put(bio);
917
918         if (!atomic_dec_and_test(&rbio->stripes_pending))
919                 return;
920
921         err = BLK_STS_OK;
922
923         /* OK, we have read all the stripes we need to. */
924         max_errors = (rbio->operation == BTRFS_RBIO_PARITY_SCRUB) ?
925                      0 : rbio->bbio->max_errors;
926         if (atomic_read(&rbio->error) > max_errors)
927                 err = BLK_STS_IOERR;
928
929         rbio_orig_end_io(rbio, err);
930 }
931
932 /*
933  * the read/modify/write code wants to use the original bio for
934  * any pages it included, and then use the rbio for everything
935  * else.  This function decides if a given index (stripe number)
936  * and page number in that stripe fall inside the original bio
937  * or the rbio.
938  *
939  * if you set bio_list_only, you'll get a NULL back for any ranges
940  * that are outside the bio_list
941  *
942  * This doesn't take any refs on anything, you get a bare page pointer
943  * and the caller must bump refs as required.
944  *
945  * You must call index_rbio_pages once before you can trust
946  * the answers from this function.
947  */
948 static struct page *page_in_rbio(struct btrfs_raid_bio *rbio,
949                                  int index, int pagenr, int bio_list_only)
950 {
951         int chunk_page;
952         struct page *p = NULL;
953
954         chunk_page = index * (rbio->stripe_len >> PAGE_SHIFT) + pagenr;
955
956         spin_lock_irq(&rbio->bio_list_lock);
957         p = rbio->bio_pages[chunk_page];
958         spin_unlock_irq(&rbio->bio_list_lock);
959
960         if (p || bio_list_only)
961                 return p;
962
963         return rbio->stripe_pages[chunk_page];
964 }
965
966 /*
967  * number of pages we need for the entire stripe across all the
968  * drives
969  */
970 static unsigned long rbio_nr_pages(unsigned long stripe_len, int nr_stripes)
971 {
972         return DIV_ROUND_UP(stripe_len, PAGE_SIZE) * nr_stripes;
973 }
974
975 /*
976  * allocation and initial setup for the btrfs_raid_bio.  Not
977  * this does not allocate any pages for rbio->pages.
978  */
979 static struct btrfs_raid_bio *alloc_rbio(struct btrfs_fs_info *fs_info,
980                                          struct btrfs_bio *bbio,
981                                          u64 stripe_len)
982 {
983         struct btrfs_raid_bio *rbio;
984         int nr_data = 0;
985         int real_stripes = bbio->num_stripes - bbio->num_tgtdevs;
986         int num_pages = rbio_nr_pages(stripe_len, real_stripes);
987         int stripe_npages = DIV_ROUND_UP(stripe_len, PAGE_SIZE);
988         void *p;
989
990         rbio = kzalloc(sizeof(*rbio) +
991                        sizeof(*rbio->stripe_pages) * num_pages +
992                        sizeof(*rbio->bio_pages) * num_pages +
993                        sizeof(*rbio->finish_pointers) * real_stripes +
994                        sizeof(*rbio->dbitmap) * BITS_TO_LONGS(stripe_npages) +
995                        sizeof(*rbio->finish_pbitmap) *
996                                 BITS_TO_LONGS(stripe_npages),
997                        GFP_NOFS);
998         if (!rbio)
999                 return ERR_PTR(-ENOMEM);
1000
1001         bio_list_init(&rbio->bio_list);
1002         INIT_LIST_HEAD(&rbio->plug_list);
1003         spin_lock_init(&rbio->bio_list_lock);
1004         INIT_LIST_HEAD(&rbio->stripe_cache);
1005         INIT_LIST_HEAD(&rbio->hash_list);
1006         rbio->bbio = bbio;
1007         rbio->fs_info = fs_info;
1008         rbio->stripe_len = stripe_len;
1009         rbio->nr_pages = num_pages;
1010         rbio->real_stripes = real_stripes;
1011         rbio->stripe_npages = stripe_npages;
1012         rbio->faila = -1;
1013         rbio->failb = -1;
1014         refcount_set(&rbio->refs, 1);
1015         atomic_set(&rbio->error, 0);
1016         atomic_set(&rbio->stripes_pending, 0);
1017
1018         /*
1019          * the stripe_pages, bio_pages, etc arrays point to the extra
1020          * memory we allocated past the end of the rbio
1021          */
1022         p = rbio + 1;
1023 #define CONSUME_ALLOC(ptr, count)       do {                            \
1024                 ptr = p;                                                \
1025                 p = (unsigned char *)p + sizeof(*(ptr)) * (count);      \
1026         } while (0)
1027         CONSUME_ALLOC(rbio->stripe_pages, num_pages);
1028         CONSUME_ALLOC(rbio->bio_pages, num_pages);
1029         CONSUME_ALLOC(rbio->finish_pointers, real_stripes);
1030         CONSUME_ALLOC(rbio->dbitmap, BITS_TO_LONGS(stripe_npages));
1031         CONSUME_ALLOC(rbio->finish_pbitmap, BITS_TO_LONGS(stripe_npages));
1032 #undef  CONSUME_ALLOC
1033
1034         if (bbio->map_type & BTRFS_BLOCK_GROUP_RAID5)
1035                 nr_data = real_stripes - 1;
1036         else if (bbio->map_type & BTRFS_BLOCK_GROUP_RAID6)
1037                 nr_data = real_stripes - 2;
1038         else
1039                 BUG();
1040
1041         rbio->nr_data = nr_data;
1042         return rbio;
1043 }
1044
1045 /* allocate pages for all the stripes in the bio, including parity */
1046 static int alloc_rbio_pages(struct btrfs_raid_bio *rbio)
1047 {
1048         int i;
1049         struct page *page;
1050
1051         for (i = 0; i < rbio->nr_pages; i++) {
1052                 if (rbio->stripe_pages[i])
1053                         continue;
1054                 page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
1055                 if (!page)
1056                         return -ENOMEM;
1057                 rbio->stripe_pages[i] = page;
1058         }
1059         return 0;
1060 }
1061
1062 /* only allocate pages for p/q stripes */
1063 static int alloc_rbio_parity_pages(struct btrfs_raid_bio *rbio)
1064 {
1065         int i;
1066         struct page *page;
1067
1068         i = rbio_stripe_page_index(rbio, rbio->nr_data, 0);
1069
1070         for (; i < rbio->nr_pages; i++) {
1071                 if (rbio->stripe_pages[i])
1072                         continue;
1073                 page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
1074                 if (!page)
1075                         return -ENOMEM;
1076                 rbio->stripe_pages[i] = page;
1077         }
1078         return 0;
1079 }
1080
1081 /*
1082  * add a single page from a specific stripe into our list of bios for IO
1083  * this will try to merge into existing bios if possible, and returns
1084  * zero if all went well.
1085  */
1086 static int rbio_add_io_page(struct btrfs_raid_bio *rbio,
1087                             struct bio_list *bio_list,
1088                             struct page *page,
1089                             int stripe_nr,
1090                             unsigned long page_index,
1091                             unsigned long bio_max_len)
1092 {
1093         struct bio *last = bio_list->tail;
1094         u64 last_end = 0;
1095         int ret;
1096         struct bio *bio;
1097         struct btrfs_bio_stripe *stripe;
1098         u64 disk_start;
1099
1100         stripe = &rbio->bbio->stripes[stripe_nr];
1101         disk_start = stripe->physical + (page_index << PAGE_SHIFT);
1102
1103         /* if the device is missing, just fail this stripe */
1104         if (!stripe->dev->bdev)
1105                 return fail_rbio_index(rbio, stripe_nr);
1106
1107         /* see if we can add this page onto our existing bio */
1108         if (last) {
1109                 last_end = (u64)last->bi_iter.bi_sector << 9;
1110                 last_end += last->bi_iter.bi_size;
1111
1112                 /*
1113                  * we can't merge these if they are from different
1114                  * devices or if they are not contiguous
1115                  */
1116                 if (last_end == disk_start && stripe->dev->bdev &&
1117                     !last->bi_status &&
1118                     last->bi_disk == stripe->dev->bdev->bd_disk &&
1119                     last->bi_partno == stripe->dev->bdev->bd_partno) {
1120                         ret = bio_add_page(last, page, PAGE_SIZE, 0);
1121                         if (ret == PAGE_SIZE)
1122                                 return 0;
1123                 }
1124         }
1125
1126         /* put a new bio on the list */
1127         bio = btrfs_io_bio_alloc(bio_max_len >> PAGE_SHIFT ?: 1);
1128         bio->bi_iter.bi_size = 0;
1129         bio_set_dev(bio, stripe->dev->bdev);
1130         bio->bi_iter.bi_sector = disk_start >> 9;
1131
1132         bio_add_page(bio, page, PAGE_SIZE, 0);
1133         bio_list_add(bio_list, bio);
1134         return 0;
1135 }
1136
1137 /*
1138  * while we're doing the read/modify/write cycle, we could
1139  * have errors in reading pages off the disk.  This checks
1140  * for errors and if we're not able to read the page it'll
1141  * trigger parity reconstruction.  The rmw will be finished
1142  * after we've reconstructed the failed stripes
1143  */
1144 static void validate_rbio_for_rmw(struct btrfs_raid_bio *rbio)
1145 {
1146         if (rbio->faila >= 0 || rbio->failb >= 0) {
1147                 BUG_ON(rbio->faila == rbio->real_stripes - 1);
1148                 __raid56_parity_recover(rbio);
1149         } else {
1150                 finish_rmw(rbio);
1151         }
1152 }
1153
1154 /*
1155  * helper function to walk our bio list and populate the bio_pages array with
1156  * the result.  This seems expensive, but it is faster than constantly
1157  * searching through the bio list as we setup the IO in finish_rmw or stripe
1158  * reconstruction.
1159  *
1160  * This must be called before you trust the answers from page_in_rbio
1161  */
1162 static void index_rbio_pages(struct btrfs_raid_bio *rbio)
1163 {
1164         struct bio *bio;
1165         u64 start;
1166         unsigned long stripe_offset;
1167         unsigned long page_index;
1168
1169         spin_lock_irq(&rbio->bio_list_lock);
1170         bio_list_for_each(bio, &rbio->bio_list) {
1171                 struct bio_vec bvec;
1172                 struct bvec_iter iter;
1173                 int i = 0;
1174
1175                 start = (u64)bio->bi_iter.bi_sector << 9;
1176                 stripe_offset = start - rbio->bbio->raid_map[0];
1177                 page_index = stripe_offset >> PAGE_SHIFT;
1178
1179                 if (bio_flagged(bio, BIO_CLONED))
1180                         bio->bi_iter = btrfs_io_bio(bio)->iter;
1181
1182                 bio_for_each_segment(bvec, bio, iter) {
1183                         rbio->bio_pages[page_index + i] = bvec.bv_page;
1184                         i++;
1185                 }
1186         }
1187         spin_unlock_irq(&rbio->bio_list_lock);
1188 }
1189
1190 /*
1191  * this is called from one of two situations.  We either
1192  * have a full stripe from the higher layers, or we've read all
1193  * the missing bits off disk.
1194  *
1195  * This will calculate the parity and then send down any
1196  * changed blocks.
1197  */
1198 static noinline void finish_rmw(struct btrfs_raid_bio *rbio)
1199 {
1200         struct btrfs_bio *bbio = rbio->bbio;
1201         void **pointers = rbio->finish_pointers;
1202         int nr_data = rbio->nr_data;
1203         int stripe;
1204         int pagenr;
1205         int p_stripe = -1;
1206         int q_stripe = -1;
1207         struct bio_list bio_list;
1208         struct bio *bio;
1209         int ret;
1210
1211         bio_list_init(&bio_list);
1212
1213         if (rbio->real_stripes - rbio->nr_data == 1) {
1214                 p_stripe = rbio->real_stripes - 1;
1215         } else if (rbio->real_stripes - rbio->nr_data == 2) {
1216                 p_stripe = rbio->real_stripes - 2;
1217                 q_stripe = rbio->real_stripes - 1;
1218         } else {
1219                 BUG();
1220         }
1221
1222         /* at this point we either have a full stripe,
1223          * or we've read the full stripe from the drive.
1224          * recalculate the parity and write the new results.
1225          *
1226          * We're not allowed to add any new bios to the
1227          * bio list here, anyone else that wants to
1228          * change this stripe needs to do their own rmw.
1229          */
1230         spin_lock_irq(&rbio->bio_list_lock);
1231         set_bit(RBIO_RMW_LOCKED_BIT, &rbio->flags);
1232         spin_unlock_irq(&rbio->bio_list_lock);
1233
1234         atomic_set(&rbio->error, 0);
1235
1236         /*
1237          * now that we've set rmw_locked, run through the
1238          * bio list one last time and map the page pointers
1239          *
1240          * We don't cache full rbios because we're assuming
1241          * the higher layers are unlikely to use this area of
1242          * the disk again soon.  If they do use it again,
1243          * hopefully they will send another full bio.
1244          */
1245         index_rbio_pages(rbio);
1246         if (!rbio_is_full(rbio))
1247                 cache_rbio_pages(rbio);
1248         else
1249                 clear_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
1250
1251         for (pagenr = 0; pagenr < rbio->stripe_npages; pagenr++) {
1252                 struct page *p;
1253                 /* first collect one page from each data stripe */
1254                 for (stripe = 0; stripe < nr_data; stripe++) {
1255                         p = page_in_rbio(rbio, stripe, pagenr, 0);
1256                         pointers[stripe] = kmap(p);
1257                 }
1258
1259                 /* then add the parity stripe */
1260                 p = rbio_pstripe_page(rbio, pagenr);
1261                 SetPageUptodate(p);
1262                 pointers[stripe++] = kmap(p);
1263
1264                 if (q_stripe != -1) {
1265
1266                         /*
1267                          * raid6, add the qstripe and call the
1268                          * library function to fill in our p/q
1269                          */
1270                         p = rbio_qstripe_page(rbio, pagenr);
1271                         SetPageUptodate(p);
1272                         pointers[stripe++] = kmap(p);
1273
1274                         raid6_call.gen_syndrome(rbio->real_stripes, PAGE_SIZE,
1275                                                 pointers);
1276                 } else {
1277                         /* raid5 */
1278                         copy_page(pointers[nr_data], pointers[0]);
1279                         run_xor(pointers + 1, nr_data - 1, PAGE_SIZE);
1280                 }
1281
1282
1283                 for (stripe = 0; stripe < rbio->real_stripes; stripe++)
1284                         kunmap(page_in_rbio(rbio, stripe, pagenr, 0));
1285         }
1286
1287         /*
1288          * time to start writing.  Make bios for everything from the
1289          * higher layers (the bio_list in our rbio) and our p/q.  Ignore
1290          * everything else.
1291          */
1292         for (stripe = 0; stripe < rbio->real_stripes; stripe++) {
1293                 for (pagenr = 0; pagenr < rbio->stripe_npages; pagenr++) {
1294                         struct page *page;
1295                         if (stripe < rbio->nr_data) {
1296                                 page = page_in_rbio(rbio, stripe, pagenr, 1);
1297                                 if (!page)
1298                                         continue;
1299                         } else {
1300                                page = rbio_stripe_page(rbio, stripe, pagenr);
1301                         }
1302
1303                         ret = rbio_add_io_page(rbio, &bio_list,
1304                                        page, stripe, pagenr, rbio->stripe_len);
1305                         if (ret)
1306                                 goto cleanup;
1307                 }
1308         }
1309
1310         if (likely(!bbio->num_tgtdevs))
1311                 goto write_data;
1312
1313         for (stripe = 0; stripe < rbio->real_stripes; stripe++) {
1314                 if (!bbio->tgtdev_map[stripe])
1315                         continue;
1316
1317                 for (pagenr = 0; pagenr < rbio->stripe_npages; pagenr++) {
1318                         struct page *page;
1319                         if (stripe < rbio->nr_data) {
1320                                 page = page_in_rbio(rbio, stripe, pagenr, 1);
1321                                 if (!page)
1322                                         continue;
1323                         } else {
1324                                page = rbio_stripe_page(rbio, stripe, pagenr);
1325                         }
1326
1327                         ret = rbio_add_io_page(rbio, &bio_list, page,
1328                                                rbio->bbio->tgtdev_map[stripe],
1329                                                pagenr, rbio->stripe_len);
1330                         if (ret)
1331                                 goto cleanup;
1332                 }
1333         }
1334
1335 write_data:
1336         atomic_set(&rbio->stripes_pending, bio_list_size(&bio_list));
1337         BUG_ON(atomic_read(&rbio->stripes_pending) == 0);
1338
1339         while (1) {
1340                 bio = bio_list_pop(&bio_list);
1341                 if (!bio)
1342                         break;
1343
1344                 bio->bi_private = rbio;
1345                 bio->bi_end_io = raid_write_end_io;
1346                 bio_set_op_attrs(bio, REQ_OP_WRITE, 0);
1347
1348                 submit_bio(bio);
1349         }
1350         return;
1351
1352 cleanup:
1353         rbio_orig_end_io(rbio, BLK_STS_IOERR);
1354
1355         while ((bio = bio_list_pop(&bio_list)))
1356                 bio_put(bio);
1357 }
1358
1359 /*
1360  * helper to find the stripe number for a given bio.  Used to figure out which
1361  * stripe has failed.  This expects the bio to correspond to a physical disk,
1362  * so it looks up based on physical sector numbers.
1363  */
1364 static int find_bio_stripe(struct btrfs_raid_bio *rbio,
1365                            struct bio *bio)
1366 {
1367         u64 physical = bio->bi_iter.bi_sector;
1368         u64 stripe_start;
1369         int i;
1370         struct btrfs_bio_stripe *stripe;
1371
1372         physical <<= 9;
1373
1374         for (i = 0; i < rbio->bbio->num_stripes; i++) {
1375                 stripe = &rbio->bbio->stripes[i];
1376                 stripe_start = stripe->physical;
1377                 if (physical >= stripe_start &&
1378                     physical < stripe_start + rbio->stripe_len &&
1379                     stripe->dev->bdev &&
1380                     bio->bi_disk == stripe->dev->bdev->bd_disk &&
1381                     bio->bi_partno == stripe->dev->bdev->bd_partno) {
1382                         return i;
1383                 }
1384         }
1385         return -1;
1386 }
1387
1388 /*
1389  * helper to find the stripe number for a given
1390  * bio (before mapping).  Used to figure out which stripe has
1391  * failed.  This looks up based on logical block numbers.
1392  */
1393 static int find_logical_bio_stripe(struct btrfs_raid_bio *rbio,
1394                                    struct bio *bio)
1395 {
1396         u64 logical = bio->bi_iter.bi_sector;
1397         u64 stripe_start;
1398         int i;
1399
1400         logical <<= 9;
1401
1402         for (i = 0; i < rbio->nr_data; i++) {
1403                 stripe_start = rbio->bbio->raid_map[i];
1404                 if (logical >= stripe_start &&
1405                     logical < stripe_start + rbio->stripe_len) {
1406                         return i;
1407                 }
1408         }
1409         return -1;
1410 }
1411
1412 /*
1413  * returns -EIO if we had too many failures
1414  */
1415 static int fail_rbio_index(struct btrfs_raid_bio *rbio, int failed)
1416 {
1417         unsigned long flags;
1418         int ret = 0;
1419
1420         spin_lock_irqsave(&rbio->bio_list_lock, flags);
1421
1422         /* we already know this stripe is bad, move on */
1423         if (rbio->faila == failed || rbio->failb == failed)
1424                 goto out;
1425
1426         if (rbio->faila == -1) {
1427                 /* first failure on this rbio */
1428                 rbio->faila = failed;
1429                 atomic_inc(&rbio->error);
1430         } else if (rbio->failb == -1) {
1431                 /* second failure on this rbio */
1432                 rbio->failb = failed;
1433                 atomic_inc(&rbio->error);
1434         } else {
1435                 ret = -EIO;
1436         }
1437 out:
1438         spin_unlock_irqrestore(&rbio->bio_list_lock, flags);
1439
1440         return ret;
1441 }
1442
1443 /*
1444  * helper to fail a stripe based on a physical disk
1445  * bio.
1446  */
1447 static int fail_bio_stripe(struct btrfs_raid_bio *rbio,
1448                            struct bio *bio)
1449 {
1450         int failed = find_bio_stripe(rbio, bio);
1451
1452         if (failed < 0)
1453                 return -EIO;
1454
1455         return fail_rbio_index(rbio, failed);
1456 }
1457
1458 /*
1459  * this sets each page in the bio uptodate.  It should only be used on private
1460  * rbio pages, nothing that comes in from the higher layers
1461  */
1462 static void set_bio_pages_uptodate(struct bio *bio)
1463 {
1464         struct bio_vec *bvec;
1465         int i;
1466
1467         ASSERT(!bio_flagged(bio, BIO_CLONED));
1468
1469         bio_for_each_segment_all(bvec, bio, i)
1470                 SetPageUptodate(bvec->bv_page);
1471 }
1472
1473 /*
1474  * end io for the read phase of the rmw cycle.  All the bios here are physical
1475  * stripe bios we've read from the disk so we can recalculate the parity of the
1476  * stripe.
1477  *
1478  * This will usually kick off finish_rmw once all the bios are read in, but it
1479  * may trigger parity reconstruction if we had any errors along the way
1480  */
1481 static void raid_rmw_end_io(struct bio *bio)
1482 {
1483         struct btrfs_raid_bio *rbio = bio->bi_private;
1484
1485         if (bio->bi_status)
1486                 fail_bio_stripe(rbio, bio);
1487         else
1488                 set_bio_pages_uptodate(bio);
1489
1490         bio_put(bio);
1491
1492         if (!atomic_dec_and_test(&rbio->stripes_pending))
1493                 return;
1494
1495         if (atomic_read(&rbio->error) > rbio->bbio->max_errors)
1496                 goto cleanup;
1497
1498         /*
1499          * this will normally call finish_rmw to start our write
1500          * but if there are any failed stripes we'll reconstruct
1501          * from parity first
1502          */
1503         validate_rbio_for_rmw(rbio);
1504         return;
1505
1506 cleanup:
1507
1508         rbio_orig_end_io(rbio, BLK_STS_IOERR);
1509 }
1510
1511 static void async_rmw_stripe(struct btrfs_raid_bio *rbio)
1512 {
1513         btrfs_init_work(&rbio->work, btrfs_rmw_helper, rmw_work, NULL, NULL);
1514         btrfs_queue_work(rbio->fs_info->rmw_workers, &rbio->work);
1515 }
1516
1517 static void async_read_rebuild(struct btrfs_raid_bio *rbio)
1518 {
1519         btrfs_init_work(&rbio->work, btrfs_rmw_helper,
1520                         read_rebuild_work, NULL, NULL);
1521
1522         btrfs_queue_work(rbio->fs_info->rmw_workers, &rbio->work);
1523 }
1524
1525 /*
1526  * the stripe must be locked by the caller.  It will
1527  * unlock after all the writes are done
1528  */
1529 static int raid56_rmw_stripe(struct btrfs_raid_bio *rbio)
1530 {
1531         int bios_to_read = 0;
1532         struct bio_list bio_list;
1533         int ret;
1534         int pagenr;
1535         int stripe;
1536         struct bio *bio;
1537
1538         bio_list_init(&bio_list);
1539
1540         ret = alloc_rbio_pages(rbio);
1541         if (ret)
1542                 goto cleanup;
1543
1544         index_rbio_pages(rbio);
1545
1546         atomic_set(&rbio->error, 0);
1547         /*
1548          * build a list of bios to read all the missing parts of this
1549          * stripe
1550          */
1551         for (stripe = 0; stripe < rbio->nr_data; stripe++) {
1552                 for (pagenr = 0; pagenr < rbio->stripe_npages; pagenr++) {
1553                         struct page *page;
1554                         /*
1555                          * we want to find all the pages missing from
1556                          * the rbio and read them from the disk.  If
1557                          * page_in_rbio finds a page in the bio list
1558                          * we don't need to read it off the stripe.
1559                          */
1560                         page = page_in_rbio(rbio, stripe, pagenr, 1);
1561                         if (page)
1562                                 continue;
1563
1564                         page = rbio_stripe_page(rbio, stripe, pagenr);
1565                         /*
1566                          * the bio cache may have handed us an uptodate
1567                          * page.  If so, be happy and use it
1568                          */
1569                         if (PageUptodate(page))
1570                                 continue;
1571
1572                         ret = rbio_add_io_page(rbio, &bio_list, page,
1573                                        stripe, pagenr, rbio->stripe_len);
1574                         if (ret)
1575                                 goto cleanup;
1576                 }
1577         }
1578
1579         bios_to_read = bio_list_size(&bio_list);
1580         if (!bios_to_read) {
1581                 /*
1582                  * this can happen if others have merged with
1583                  * us, it means there is nothing left to read.
1584                  * But if there are missing devices it may not be
1585                  * safe to do the full stripe write yet.
1586                  */
1587                 goto finish;
1588         }
1589
1590         /*
1591          * the bbio may be freed once we submit the last bio.  Make sure
1592          * not to touch it after that
1593          */
1594         atomic_set(&rbio->stripes_pending, bios_to_read);
1595         while (1) {
1596                 bio = bio_list_pop(&bio_list);
1597                 if (!bio)
1598                         break;
1599
1600                 bio->bi_private = rbio;
1601                 bio->bi_end_io = raid_rmw_end_io;
1602                 bio_set_op_attrs(bio, REQ_OP_READ, 0);
1603
1604                 btrfs_bio_wq_end_io(rbio->fs_info, bio, BTRFS_WQ_ENDIO_RAID56);
1605
1606                 submit_bio(bio);
1607         }
1608         /* the actual write will happen once the reads are done */
1609         return 0;
1610
1611 cleanup:
1612         rbio_orig_end_io(rbio, BLK_STS_IOERR);
1613
1614         while ((bio = bio_list_pop(&bio_list)))
1615                 bio_put(bio);
1616
1617         return -EIO;
1618
1619 finish:
1620         validate_rbio_for_rmw(rbio);
1621         return 0;
1622 }
1623
1624 /*
1625  * if the upper layers pass in a full stripe, we thank them by only allocating
1626  * enough pages to hold the parity, and sending it all down quickly.
1627  */
1628 static int full_stripe_write(struct btrfs_raid_bio *rbio)
1629 {
1630         int ret;
1631
1632         ret = alloc_rbio_parity_pages(rbio);
1633         if (ret) {
1634                 __free_raid_bio(rbio);
1635                 return ret;
1636         }
1637
1638         ret = lock_stripe_add(rbio);
1639         if (ret == 0)
1640                 finish_rmw(rbio);
1641         return 0;
1642 }
1643
1644 /*
1645  * partial stripe writes get handed over to async helpers.
1646  * We're really hoping to merge a few more writes into this
1647  * rbio before calculating new parity
1648  */
1649 static int partial_stripe_write(struct btrfs_raid_bio *rbio)
1650 {
1651         int ret;
1652
1653         ret = lock_stripe_add(rbio);
1654         if (ret == 0)
1655                 async_rmw_stripe(rbio);
1656         return 0;
1657 }
1658
1659 /*
1660  * sometimes while we were reading from the drive to
1661  * recalculate parity, enough new bios come into create
1662  * a full stripe.  So we do a check here to see if we can
1663  * go directly to finish_rmw
1664  */
1665 static int __raid56_parity_write(struct btrfs_raid_bio *rbio)
1666 {
1667         /* head off into rmw land if we don't have a full stripe */
1668         if (!rbio_is_full(rbio))
1669                 return partial_stripe_write(rbio);
1670         return full_stripe_write(rbio);
1671 }
1672
1673 /*
1674  * We use plugging call backs to collect full stripes.
1675  * Any time we get a partial stripe write while plugged
1676  * we collect it into a list.  When the unplug comes down,
1677  * we sort the list by logical block number and merge
1678  * everything we can into the same rbios
1679  */
1680 struct btrfs_plug_cb {
1681         struct blk_plug_cb cb;
1682         struct btrfs_fs_info *info;
1683         struct list_head rbio_list;
1684         struct btrfs_work work;
1685 };
1686
1687 /*
1688  * rbios on the plug list are sorted for easier merging.
1689  */
1690 static int plug_cmp(void *priv, struct list_head *a, struct list_head *b)
1691 {
1692         struct btrfs_raid_bio *ra = container_of(a, struct btrfs_raid_bio,
1693                                                  plug_list);
1694         struct btrfs_raid_bio *rb = container_of(b, struct btrfs_raid_bio,
1695                                                  plug_list);
1696         u64 a_sector = ra->bio_list.head->bi_iter.bi_sector;
1697         u64 b_sector = rb->bio_list.head->bi_iter.bi_sector;
1698
1699         if (a_sector < b_sector)
1700                 return -1;
1701         if (a_sector > b_sector)
1702                 return 1;
1703         return 0;
1704 }
1705
1706 static void run_plug(struct btrfs_plug_cb *plug)
1707 {
1708         struct btrfs_raid_bio *cur;
1709         struct btrfs_raid_bio *last = NULL;
1710
1711         /*
1712          * sort our plug list then try to merge
1713          * everything we can in hopes of creating full
1714          * stripes.
1715          */
1716         list_sort(NULL, &plug->rbio_list, plug_cmp);
1717         while (!list_empty(&plug->rbio_list)) {
1718                 cur = list_entry(plug->rbio_list.next,
1719                                  struct btrfs_raid_bio, plug_list);
1720                 list_del_init(&cur->plug_list);
1721
1722                 if (rbio_is_full(cur)) {
1723                         /* we have a full stripe, send it down */
1724                         full_stripe_write(cur);
1725                         continue;
1726                 }
1727                 if (last) {
1728                         if (rbio_can_merge(last, cur)) {
1729                                 merge_rbio(last, cur);
1730                                 __free_raid_bio(cur);
1731                                 continue;
1732
1733                         }
1734                         __raid56_parity_write(last);
1735                 }
1736                 last = cur;
1737         }
1738         if (last) {
1739                 __raid56_parity_write(last);
1740         }
1741         kfree(plug);
1742 }
1743
1744 /*
1745  * if the unplug comes from schedule, we have to push the
1746  * work off to a helper thread
1747  */
1748 static void unplug_work(struct btrfs_work *work)
1749 {
1750         struct btrfs_plug_cb *plug;
1751         plug = container_of(work, struct btrfs_plug_cb, work);
1752         run_plug(plug);
1753 }
1754
1755 static void btrfs_raid_unplug(struct blk_plug_cb *cb, bool from_schedule)
1756 {
1757         struct btrfs_plug_cb *plug;
1758         plug = container_of(cb, struct btrfs_plug_cb, cb);
1759
1760         if (from_schedule) {
1761                 btrfs_init_work(&plug->work, btrfs_rmw_helper,
1762                                 unplug_work, NULL, NULL);
1763                 btrfs_queue_work(plug->info->rmw_workers,
1764                                  &plug->work);
1765                 return;
1766         }
1767         run_plug(plug);
1768 }
1769
1770 /*
1771  * our main entry point for writes from the rest of the FS.
1772  */
1773 int raid56_parity_write(struct btrfs_fs_info *fs_info, struct bio *bio,
1774                         struct btrfs_bio *bbio, u64 stripe_len)
1775 {
1776         struct btrfs_raid_bio *rbio;
1777         struct btrfs_plug_cb *plug = NULL;
1778         struct blk_plug_cb *cb;
1779         int ret;
1780
1781         rbio = alloc_rbio(fs_info, bbio, stripe_len);
1782         if (IS_ERR(rbio)) {
1783                 btrfs_put_bbio(bbio);
1784                 return PTR_ERR(rbio);
1785         }
1786         bio_list_add(&rbio->bio_list, bio);
1787         rbio->bio_list_bytes = bio->bi_iter.bi_size;
1788         rbio->operation = BTRFS_RBIO_WRITE;
1789
1790         btrfs_bio_counter_inc_noblocked(fs_info);
1791         rbio->generic_bio_cnt = 1;
1792
1793         /*
1794          * don't plug on full rbios, just get them out the door
1795          * as quickly as we can
1796          */
1797         if (rbio_is_full(rbio)) {
1798                 ret = full_stripe_write(rbio);
1799                 if (ret)
1800                         btrfs_bio_counter_dec(fs_info);
1801                 return ret;
1802         }
1803
1804         cb = blk_check_plugged(btrfs_raid_unplug, fs_info, sizeof(*plug));
1805         if (cb) {
1806                 plug = container_of(cb, struct btrfs_plug_cb, cb);
1807                 if (!plug->info) {
1808                         plug->info = fs_info;
1809                         INIT_LIST_HEAD(&plug->rbio_list);
1810                 }
1811                 list_add_tail(&rbio->plug_list, &plug->rbio_list);
1812                 ret = 0;
1813         } else {
1814                 ret = __raid56_parity_write(rbio);
1815                 if (ret)
1816                         btrfs_bio_counter_dec(fs_info);
1817         }
1818         return ret;
1819 }
1820
1821 /*
1822  * all parity reconstruction happens here.  We've read in everything
1823  * we can find from the drives and this does the heavy lifting of
1824  * sorting the good from the bad.
1825  */
1826 static void __raid_recover_end_io(struct btrfs_raid_bio *rbio)
1827 {
1828         int pagenr, stripe;
1829         void **pointers;
1830         int faila = -1, failb = -1;
1831         struct page *page;
1832         blk_status_t err;
1833         int i;
1834
1835         pointers = kcalloc(rbio->real_stripes, sizeof(void *), GFP_NOFS);
1836         if (!pointers) {
1837                 err = BLK_STS_RESOURCE;
1838                 goto cleanup_io;
1839         }
1840
1841         faila = rbio->faila;
1842         failb = rbio->failb;
1843
1844         if (rbio->operation == BTRFS_RBIO_READ_REBUILD ||
1845             rbio->operation == BTRFS_RBIO_REBUILD_MISSING) {
1846                 spin_lock_irq(&rbio->bio_list_lock);
1847                 set_bit(RBIO_RMW_LOCKED_BIT, &rbio->flags);
1848                 spin_unlock_irq(&rbio->bio_list_lock);
1849         }
1850
1851         index_rbio_pages(rbio);
1852
1853         for (pagenr = 0; pagenr < rbio->stripe_npages; pagenr++) {
1854                 /*
1855                  * Now we just use bitmap to mark the horizontal stripes in
1856                  * which we have data when doing parity scrub.
1857                  */
1858                 if (rbio->operation == BTRFS_RBIO_PARITY_SCRUB &&
1859                     !test_bit(pagenr, rbio->dbitmap))
1860                         continue;
1861
1862                 /* setup our array of pointers with pages
1863                  * from each stripe
1864                  */
1865                 for (stripe = 0; stripe < rbio->real_stripes; stripe++) {
1866                         /*
1867                          * if we're rebuilding a read, we have to use
1868                          * pages from the bio list
1869                          */
1870                         if ((rbio->operation == BTRFS_RBIO_READ_REBUILD ||
1871                              rbio->operation == BTRFS_RBIO_REBUILD_MISSING) &&
1872                             (stripe == faila || stripe == failb)) {
1873                                 page = page_in_rbio(rbio, stripe, pagenr, 0);
1874                         } else {
1875                                 page = rbio_stripe_page(rbio, stripe, pagenr);
1876                         }
1877                         pointers[stripe] = kmap(page);
1878                 }
1879
1880                 /* all raid6 handling here */
1881                 if (rbio->bbio->map_type & BTRFS_BLOCK_GROUP_RAID6) {
1882                         /*
1883                          * single failure, rebuild from parity raid5
1884                          * style
1885                          */
1886                         if (failb < 0) {
1887                                 if (faila == rbio->nr_data) {
1888                                         /*
1889                                          * Just the P stripe has failed, without
1890                                          * a bad data or Q stripe.
1891                                          * TODO, we should redo the xor here.
1892                                          */
1893                                         err = BLK_STS_IOERR;
1894                                         goto cleanup;
1895                                 }
1896                                 /*
1897                                  * a single failure in raid6 is rebuilt
1898                                  * in the pstripe code below
1899                                  */
1900                                 goto pstripe;
1901                         }
1902
1903                         /* make sure our ps and qs are in order */
1904                         if (faila > failb) {
1905                                 int tmp = failb;
1906                                 failb = faila;
1907                                 faila = tmp;
1908                         }
1909
1910                         /* if the q stripe is failed, do a pstripe reconstruction
1911                          * from the xors.
1912                          * If both the q stripe and the P stripe are failed, we're
1913                          * here due to a crc mismatch and we can't give them the
1914                          * data they want
1915                          */
1916                         if (rbio->bbio->raid_map[failb] == RAID6_Q_STRIPE) {
1917                                 if (rbio->bbio->raid_map[faila] ==
1918                                     RAID5_P_STRIPE) {
1919                                         err = BLK_STS_IOERR;
1920                                         goto cleanup;
1921                                 }
1922                                 /*
1923                                  * otherwise we have one bad data stripe and
1924                                  * a good P stripe.  raid5!
1925                                  */
1926                                 goto pstripe;
1927                         }
1928
1929                         if (rbio->bbio->raid_map[failb] == RAID5_P_STRIPE) {
1930                                 raid6_datap_recov(rbio->real_stripes,
1931                                                   PAGE_SIZE, faila, pointers);
1932                         } else {
1933                                 raid6_2data_recov(rbio->real_stripes,
1934                                                   PAGE_SIZE, faila, failb,
1935                                                   pointers);
1936                         }
1937                 } else {
1938                         void *p;
1939
1940                         /* rebuild from P stripe here (raid5 or raid6) */
1941                         BUG_ON(failb != -1);
1942 pstripe:
1943                         /* Copy parity block into failed block to start with */
1944                         copy_page(pointers[faila], pointers[rbio->nr_data]);
1945
1946                         /* rearrange the pointer array */
1947                         p = pointers[faila];
1948                         for (stripe = faila; stripe < rbio->nr_data - 1; stripe++)
1949                                 pointers[stripe] = pointers[stripe + 1];
1950                         pointers[rbio->nr_data - 1] = p;
1951
1952                         /* xor in the rest */
1953                         run_xor(pointers, rbio->nr_data - 1, PAGE_SIZE);
1954                 }
1955                 /* if we're doing this rebuild as part of an rmw, go through
1956                  * and set all of our private rbio pages in the
1957                  * failed stripes as uptodate.  This way finish_rmw will
1958                  * know they can be trusted.  If this was a read reconstruction,
1959                  * other endio functions will fiddle the uptodate bits
1960                  */
1961                 if (rbio->operation == BTRFS_RBIO_WRITE) {
1962                         for (i = 0;  i < rbio->stripe_npages; i++) {
1963                                 if (faila != -1) {
1964                                         page = rbio_stripe_page(rbio, faila, i);
1965                                         SetPageUptodate(page);
1966                                 }
1967                                 if (failb != -1) {
1968                                         page = rbio_stripe_page(rbio, failb, i);
1969                                         SetPageUptodate(page);
1970                                 }
1971                         }
1972                 }
1973                 for (stripe = 0; stripe < rbio->real_stripes; stripe++) {
1974                         /*
1975                          * if we're rebuilding a read, we have to use
1976                          * pages from the bio list
1977                          */
1978                         if ((rbio->operation == BTRFS_RBIO_READ_REBUILD ||
1979                              rbio->operation == BTRFS_RBIO_REBUILD_MISSING) &&
1980                             (stripe == faila || stripe == failb)) {
1981                                 page = page_in_rbio(rbio, stripe, pagenr, 0);
1982                         } else {
1983                                 page = rbio_stripe_page(rbio, stripe, pagenr);
1984                         }
1985                         kunmap(page);
1986                 }
1987         }
1988
1989         err = BLK_STS_OK;
1990 cleanup:
1991         kfree(pointers);
1992
1993 cleanup_io:
1994         /*
1995          * Similar to READ_REBUILD, REBUILD_MISSING at this point also has a
1996          * valid rbio which is consistent with ondisk content, thus such a
1997          * valid rbio can be cached to avoid further disk reads.
1998          */
1999         if (rbio->operation == BTRFS_RBIO_READ_REBUILD ||
2000             rbio->operation == BTRFS_RBIO_REBUILD_MISSING) {
2001                 /*
2002                  * - In case of two failures, where rbio->failb != -1:
2003                  *
2004                  *   Do not cache this rbio since the above read reconstruction
2005                  *   (raid6_datap_recov() or raid6_2data_recov()) may have
2006                  *   changed some content of stripes which are not identical to
2007                  *   on-disk content any more, otherwise, a later write/recover
2008                  *   may steal stripe_pages from this rbio and end up with
2009                  *   corruptions or rebuild failures.
2010                  *
2011                  * - In case of single failure, where rbio->failb == -1:
2012                  *
2013                  *   Cache this rbio iff the above read reconstruction is
2014                  *   excuted without problems.
2015                  */
2016                 if (err == BLK_STS_OK && rbio->failb < 0)
2017                         cache_rbio_pages(rbio);
2018                 else
2019                         clear_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
2020
2021                 rbio_orig_end_io(rbio, err);
2022         } else if (err == BLK_STS_OK) {
2023                 rbio->faila = -1;
2024                 rbio->failb = -1;
2025
2026                 if (rbio->operation == BTRFS_RBIO_WRITE)
2027                         finish_rmw(rbio);
2028                 else if (rbio->operation == BTRFS_RBIO_PARITY_SCRUB)
2029                         finish_parity_scrub(rbio, 0);
2030                 else
2031                         BUG();
2032         } else {
2033                 rbio_orig_end_io(rbio, err);
2034         }
2035 }
2036
2037 /*
2038  * This is called only for stripes we've read from disk to
2039  * reconstruct the parity.
2040  */
2041 static void raid_recover_end_io(struct bio *bio)
2042 {
2043         struct btrfs_raid_bio *rbio = bio->bi_private;
2044
2045         /*
2046          * we only read stripe pages off the disk, set them
2047          * up to date if there were no errors
2048          */
2049         if (bio->bi_status)
2050                 fail_bio_stripe(rbio, bio);
2051         else
2052                 set_bio_pages_uptodate(bio);
2053         bio_put(bio);
2054
2055         if (!atomic_dec_and_test(&rbio->stripes_pending))
2056                 return;
2057
2058         if (atomic_read(&rbio->error) > rbio->bbio->max_errors)
2059                 rbio_orig_end_io(rbio, BLK_STS_IOERR);
2060         else
2061                 __raid_recover_end_io(rbio);
2062 }
2063
2064 /*
2065  * reads everything we need off the disk to reconstruct
2066  * the parity. endio handlers trigger final reconstruction
2067  * when the IO is done.
2068  *
2069  * This is used both for reads from the higher layers and for
2070  * parity construction required to finish a rmw cycle.
2071  */
2072 static int __raid56_parity_recover(struct btrfs_raid_bio *rbio)
2073 {
2074         int bios_to_read = 0;
2075         struct bio_list bio_list;
2076         int ret;
2077         int pagenr;
2078         int stripe;
2079         struct bio *bio;
2080
2081         bio_list_init(&bio_list);
2082
2083         ret = alloc_rbio_pages(rbio);
2084         if (ret)
2085                 goto cleanup;
2086
2087         atomic_set(&rbio->error, 0);
2088
2089         /*
2090          * read everything that hasn't failed.  Thanks to the
2091          * stripe cache, it is possible that some or all of these
2092          * pages are going to be uptodate.
2093          */
2094         for (stripe = 0; stripe < rbio->real_stripes; stripe++) {
2095                 if (rbio->faila == stripe || rbio->failb == stripe) {
2096                         atomic_inc(&rbio->error);
2097                         continue;
2098                 }
2099
2100                 for (pagenr = 0; pagenr < rbio->stripe_npages; pagenr++) {
2101                         struct page *p;
2102
2103                         /*
2104                          * the rmw code may have already read this
2105                          * page in
2106                          */
2107                         p = rbio_stripe_page(rbio, stripe, pagenr);
2108                         if (PageUptodate(p))
2109                                 continue;
2110
2111                         ret = rbio_add_io_page(rbio, &bio_list,
2112                                        rbio_stripe_page(rbio, stripe, pagenr),
2113                                        stripe, pagenr, rbio->stripe_len);
2114                         if (ret < 0)
2115                                 goto cleanup;
2116                 }
2117         }
2118
2119         bios_to_read = bio_list_size(&bio_list);
2120         if (!bios_to_read) {
2121                 /*
2122                  * we might have no bios to read just because the pages
2123                  * were up to date, or we might have no bios to read because
2124                  * the devices were gone.
2125                  */
2126                 if (atomic_read(&rbio->error) <= rbio->bbio->max_errors) {
2127                         __raid_recover_end_io(rbio);
2128                         goto out;
2129                 } else {
2130                         goto cleanup;
2131                 }
2132         }
2133
2134         /*
2135          * the bbio may be freed once we submit the last bio.  Make sure
2136          * not to touch it after that
2137          */
2138         atomic_set(&rbio->stripes_pending, bios_to_read);
2139         while (1) {
2140                 bio = bio_list_pop(&bio_list);
2141                 if (!bio)
2142                         break;
2143
2144                 bio->bi_private = rbio;
2145                 bio->bi_end_io = raid_recover_end_io;
2146                 bio_set_op_attrs(bio, REQ_OP_READ, 0);
2147
2148                 btrfs_bio_wq_end_io(rbio->fs_info, bio, BTRFS_WQ_ENDIO_RAID56);
2149
2150                 submit_bio(bio);
2151         }
2152 out:
2153         return 0;
2154
2155 cleanup:
2156         if (rbio->operation == BTRFS_RBIO_READ_REBUILD ||
2157             rbio->operation == BTRFS_RBIO_REBUILD_MISSING)
2158                 rbio_orig_end_io(rbio, BLK_STS_IOERR);
2159
2160         while ((bio = bio_list_pop(&bio_list)))
2161                 bio_put(bio);
2162
2163         return -EIO;
2164 }
2165
2166 /*
2167  * the main entry point for reads from the higher layers.  This
2168  * is really only called when the normal read path had a failure,
2169  * so we assume the bio they send down corresponds to a failed part
2170  * of the drive.
2171  */
2172 int raid56_parity_recover(struct btrfs_fs_info *fs_info, struct bio *bio,
2173                           struct btrfs_bio *bbio, u64 stripe_len,
2174                           int mirror_num, int generic_io)
2175 {
2176         struct btrfs_raid_bio *rbio;
2177         int ret;
2178
2179         if (generic_io) {
2180                 ASSERT(bbio->mirror_num == mirror_num);
2181                 btrfs_io_bio(bio)->mirror_num = mirror_num;
2182         }
2183
2184         rbio = alloc_rbio(fs_info, bbio, stripe_len);
2185         if (IS_ERR(rbio)) {
2186                 if (generic_io)
2187                         btrfs_put_bbio(bbio);
2188                 return PTR_ERR(rbio);
2189         }
2190
2191         rbio->operation = BTRFS_RBIO_READ_REBUILD;
2192         bio_list_add(&rbio->bio_list, bio);
2193         rbio->bio_list_bytes = bio->bi_iter.bi_size;
2194
2195         rbio->faila = find_logical_bio_stripe(rbio, bio);
2196         if (rbio->faila == -1) {
2197                 btrfs_warn(fs_info,
2198         "%s could not find the bad stripe in raid56 so that we cannot recover any more (bio has logical %llu len %llu, bbio has map_type %llu)",
2199                            __func__, (u64)bio->bi_iter.bi_sector << 9,
2200                            (u64)bio->bi_iter.bi_size, bbio->map_type);
2201                 if (generic_io)
2202                         btrfs_put_bbio(bbio);
2203                 kfree(rbio);
2204                 return -EIO;
2205         }
2206
2207         if (generic_io) {
2208                 btrfs_bio_counter_inc_noblocked(fs_info);
2209                 rbio->generic_bio_cnt = 1;
2210         } else {
2211                 btrfs_get_bbio(bbio);
2212         }
2213
2214         /*
2215          * Loop retry:
2216          * for 'mirror == 2', reconstruct from all other stripes.
2217          * for 'mirror_num > 2', select a stripe to fail on every retry.
2218          */
2219         if (mirror_num > 2) {
2220                 /*
2221                  * 'mirror == 3' is to fail the p stripe and
2222                  * reconstruct from the q stripe.  'mirror > 3' is to
2223                  * fail a data stripe and reconstruct from p+q stripe.
2224                  */
2225                 rbio->failb = rbio->real_stripes - (mirror_num - 1);
2226                 ASSERT(rbio->failb > 0);
2227                 if (rbio->failb <= rbio->faila)
2228                         rbio->failb--;
2229         }
2230
2231         ret = lock_stripe_add(rbio);
2232
2233         /*
2234          * __raid56_parity_recover will end the bio with
2235          * any errors it hits.  We don't want to return
2236          * its error value up the stack because our caller
2237          * will end up calling bio_endio with any nonzero
2238          * return
2239          */
2240         if (ret == 0)
2241                 __raid56_parity_recover(rbio);
2242         /*
2243          * our rbio has been added to the list of
2244          * rbios that will be handled after the
2245          * currently lock owner is done
2246          */
2247         return 0;
2248
2249 }
2250
2251 static void rmw_work(struct btrfs_work *work)
2252 {
2253         struct btrfs_raid_bio *rbio;
2254
2255         rbio = container_of(work, struct btrfs_raid_bio, work);
2256         raid56_rmw_stripe(rbio);
2257 }
2258
2259 static void read_rebuild_work(struct btrfs_work *work)
2260 {
2261         struct btrfs_raid_bio *rbio;
2262
2263         rbio = container_of(work, struct btrfs_raid_bio, work);
2264         __raid56_parity_recover(rbio);
2265 }
2266
2267 /*
2268  * The following code is used to scrub/replace the parity stripe
2269  *
2270  * Caller must have already increased bio_counter for getting @bbio.
2271  *
2272  * Note: We need make sure all the pages that add into the scrub/replace
2273  * raid bio are correct and not be changed during the scrub/replace. That
2274  * is those pages just hold metadata or file data with checksum.
2275  */
2276
2277 struct btrfs_raid_bio *
2278 raid56_parity_alloc_scrub_rbio(struct btrfs_fs_info *fs_info, struct bio *bio,
2279                                struct btrfs_bio *bbio, u64 stripe_len,
2280                                struct btrfs_device *scrub_dev,
2281                                unsigned long *dbitmap, int stripe_nsectors)
2282 {
2283         struct btrfs_raid_bio *rbio;
2284         int i;
2285
2286         rbio = alloc_rbio(fs_info, bbio, stripe_len);
2287         if (IS_ERR(rbio))
2288                 return NULL;
2289         bio_list_add(&rbio->bio_list, bio);
2290         /*
2291          * This is a special bio which is used to hold the completion handler
2292          * and make the scrub rbio is similar to the other types
2293          */
2294         ASSERT(!bio->bi_iter.bi_size);
2295         rbio->operation = BTRFS_RBIO_PARITY_SCRUB;
2296
2297         /*
2298          * After mapping bbio with BTRFS_MAP_WRITE, parities have been sorted
2299          * to the end position, so this search can start from the first parity
2300          * stripe.
2301          */
2302         for (i = rbio->nr_data; i < rbio->real_stripes; i++) {
2303                 if (bbio->stripes[i].dev == scrub_dev) {
2304                         rbio->scrubp = i;
2305                         break;
2306                 }
2307         }
2308         ASSERT(i < rbio->real_stripes);
2309
2310         /* Now we just support the sectorsize equals to page size */
2311         ASSERT(fs_info->sectorsize == PAGE_SIZE);
2312         ASSERT(rbio->stripe_npages == stripe_nsectors);
2313         bitmap_copy(rbio->dbitmap, dbitmap, stripe_nsectors);
2314
2315         /*
2316          * We have already increased bio_counter when getting bbio, record it
2317          * so we can free it at rbio_orig_end_io().
2318          */
2319         rbio->generic_bio_cnt = 1;
2320
2321         return rbio;
2322 }
2323
2324 /* Used for both parity scrub and missing. */
2325 void raid56_add_scrub_pages(struct btrfs_raid_bio *rbio, struct page *page,
2326                             u64 logical)
2327 {
2328         int stripe_offset;
2329         int index;
2330
2331         ASSERT(logical >= rbio->bbio->raid_map[0]);
2332         ASSERT(logical + PAGE_SIZE <= rbio->bbio->raid_map[0] +
2333                                 rbio->stripe_len * rbio->nr_data);
2334         stripe_offset = (int)(logical - rbio->bbio->raid_map[0]);
2335         index = stripe_offset >> PAGE_SHIFT;
2336         rbio->bio_pages[index] = page;
2337 }
2338
2339 /*
2340  * We just scrub the parity that we have correct data on the same horizontal,
2341  * so we needn't allocate all pages for all the stripes.
2342  */
2343 static int alloc_rbio_essential_pages(struct btrfs_raid_bio *rbio)
2344 {
2345         int i;
2346         int bit;
2347         int index;
2348         struct page *page;
2349
2350         for_each_set_bit(bit, rbio->dbitmap, rbio->stripe_npages) {
2351                 for (i = 0; i < rbio->real_stripes; i++) {
2352                         index = i * rbio->stripe_npages + bit;
2353                         if (rbio->stripe_pages[index])
2354                                 continue;
2355
2356                         page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
2357                         if (!page)
2358                                 return -ENOMEM;
2359                         rbio->stripe_pages[index] = page;
2360                 }
2361         }
2362         return 0;
2363 }
2364
2365 static noinline void finish_parity_scrub(struct btrfs_raid_bio *rbio,
2366                                          int need_check)
2367 {
2368         struct btrfs_bio *bbio = rbio->bbio;
2369         void **pointers = rbio->finish_pointers;
2370         unsigned long *pbitmap = rbio->finish_pbitmap;
2371         int nr_data = rbio->nr_data;
2372         int stripe;
2373         int pagenr;
2374         int p_stripe = -1;
2375         int q_stripe = -1;
2376         struct page *p_page = NULL;
2377         struct page *q_page = NULL;
2378         struct bio_list bio_list;
2379         struct bio *bio;
2380         int is_replace = 0;
2381         int ret;
2382
2383         bio_list_init(&bio_list);
2384
2385         if (rbio->real_stripes - rbio->nr_data == 1) {
2386                 p_stripe = rbio->real_stripes - 1;
2387         } else if (rbio->real_stripes - rbio->nr_data == 2) {
2388                 p_stripe = rbio->real_stripes - 2;
2389                 q_stripe = rbio->real_stripes - 1;
2390         } else {
2391                 BUG();
2392         }
2393
2394         if (bbio->num_tgtdevs && bbio->tgtdev_map[rbio->scrubp]) {
2395                 is_replace = 1;
2396                 bitmap_copy(pbitmap, rbio->dbitmap, rbio->stripe_npages);
2397         }
2398
2399         /*
2400          * Because the higher layers(scrubber) are unlikely to
2401          * use this area of the disk again soon, so don't cache
2402          * it.
2403          */
2404         clear_bit(RBIO_CACHE_READY_BIT, &rbio->flags);
2405
2406         if (!need_check)
2407                 goto writeback;
2408
2409         p_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
2410         if (!p_page)
2411                 goto cleanup;
2412         SetPageUptodate(p_page);
2413
2414         if (q_stripe != -1) {
2415                 q_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM);
2416                 if (!q_page) {
2417                         __free_page(p_page);
2418                         goto cleanup;
2419                 }
2420                 SetPageUptodate(q_page);
2421         }
2422
2423         atomic_set(&rbio->error, 0);
2424
2425         for_each_set_bit(pagenr, rbio->dbitmap, rbio->stripe_npages) {
2426                 struct page *p;
2427                 void *parity;
2428                 /* first collect one page from each data stripe */
2429                 for (stripe = 0; stripe < nr_data; stripe++) {
2430                         p = page_in_rbio(rbio, stripe, pagenr, 0);
2431                         pointers[stripe] = kmap(p);
2432                 }
2433
2434                 /* then add the parity stripe */
2435                 pointers[stripe++] = kmap(p_page);
2436
2437                 if (q_stripe != -1) {
2438
2439                         /*
2440                          * raid6, add the qstripe and call the
2441                          * library function to fill in our p/q
2442                          */
2443                         pointers[stripe++] = kmap(q_page);
2444
2445                         raid6_call.gen_syndrome(rbio->real_stripes, PAGE_SIZE,
2446                                                 pointers);
2447                 } else {
2448                         /* raid5 */
2449                         copy_page(pointers[nr_data], pointers[0]);
2450                         run_xor(pointers + 1, nr_data - 1, PAGE_SIZE);
2451                 }
2452
2453                 /* Check scrubbing parity and repair it */
2454                 p = rbio_stripe_page(rbio, rbio->scrubp, pagenr);
2455                 parity = kmap(p);
2456                 if (memcmp(parity, pointers[rbio->scrubp], PAGE_SIZE))
2457                         copy_page(parity, pointers[rbio->scrubp]);
2458                 else
2459                         /* Parity is right, needn't writeback */
2460                         bitmap_clear(rbio->dbitmap, pagenr, 1);
2461                 kunmap(p);
2462
2463                 for (stripe = 0; stripe < rbio->real_stripes; stripe++)
2464                         kunmap(page_in_rbio(rbio, stripe, pagenr, 0));
2465         }
2466
2467         __free_page(p_page);
2468         if (q_page)
2469                 __free_page(q_page);
2470
2471 writeback:
2472         /*
2473          * time to start writing.  Make bios for everything from the
2474          * higher layers (the bio_list in our rbio) and our p/q.  Ignore
2475          * everything else.
2476          */
2477         for_each_set_bit(pagenr, rbio->dbitmap, rbio->stripe_npages) {
2478                 struct page *page;
2479
2480                 page = rbio_stripe_page(rbio, rbio->scrubp, pagenr);
2481                 ret = rbio_add_io_page(rbio, &bio_list,
2482                                page, rbio->scrubp, pagenr, rbio->stripe_len);
2483                 if (ret)
2484                         goto cleanup;
2485         }
2486
2487         if (!is_replace)
2488                 goto submit_write;
2489
2490         for_each_set_bit(pagenr, pbitmap, rbio->stripe_npages) {
2491                 struct page *page;
2492
2493                 page = rbio_stripe_page(rbio, rbio->scrubp, pagenr);
2494                 ret = rbio_add_io_page(rbio, &bio_list, page,
2495                                        bbio->tgtdev_map[rbio->scrubp],
2496                                        pagenr, rbio->stripe_len);
2497                 if (ret)
2498                         goto cleanup;
2499         }
2500
2501 submit_write:
2502         nr_data = bio_list_size(&bio_list);
2503         if (!nr_data) {
2504                 /* Every parity is right */
2505                 rbio_orig_end_io(rbio, BLK_STS_OK);
2506                 return;
2507         }
2508
2509         atomic_set(&rbio->stripes_pending, nr_data);
2510
2511         while (1) {
2512                 bio = bio_list_pop(&bio_list);
2513                 if (!bio)
2514                         break;
2515
2516                 bio->bi_private = rbio;
2517                 bio->bi_end_io = raid_write_end_io;
2518                 bio_set_op_attrs(bio, REQ_OP_WRITE, 0);
2519
2520                 submit_bio(bio);
2521         }
2522         return;
2523
2524 cleanup:
2525         rbio_orig_end_io(rbio, BLK_STS_IOERR);
2526
2527         while ((bio = bio_list_pop(&bio_list)))
2528                 bio_put(bio);
2529 }
2530
2531 static inline int is_data_stripe(struct btrfs_raid_bio *rbio, int stripe)
2532 {
2533         if (stripe >= 0 && stripe < rbio->nr_data)
2534                 return 1;
2535         return 0;
2536 }
2537
2538 /*
2539  * While we're doing the parity check and repair, we could have errors
2540  * in reading pages off the disk.  This checks for errors and if we're
2541  * not able to read the page it'll trigger parity reconstruction.  The
2542  * parity scrub will be finished after we've reconstructed the failed
2543  * stripes
2544  */
2545 static void validate_rbio_for_parity_scrub(struct btrfs_raid_bio *rbio)
2546 {
2547         if (atomic_read(&rbio->error) > rbio->bbio->max_errors)
2548                 goto cleanup;
2549
2550         if (rbio->faila >= 0 || rbio->failb >= 0) {
2551                 int dfail = 0, failp = -1;
2552
2553                 if (is_data_stripe(rbio, rbio->faila))
2554                         dfail++;
2555                 else if (is_parity_stripe(rbio->faila))
2556                         failp = rbio->faila;
2557
2558                 if (is_data_stripe(rbio, rbio->failb))
2559                         dfail++;
2560                 else if (is_parity_stripe(rbio->failb))
2561                         failp = rbio->failb;
2562
2563                 /*
2564                  * Because we can not use a scrubbing parity to repair
2565                  * the data, so the capability of the repair is declined.
2566                  * (In the case of RAID5, we can not repair anything)
2567                  */
2568                 if (dfail > rbio->bbio->max_errors - 1)
2569                         goto cleanup;
2570
2571                 /*
2572                  * If all data is good, only parity is correctly, just
2573                  * repair the parity.
2574                  */
2575                 if (dfail == 0) {
2576                         finish_parity_scrub(rbio, 0);
2577                         return;
2578                 }
2579
2580                 /*
2581                  * Here means we got one corrupted data stripe and one
2582                  * corrupted parity on RAID6, if the corrupted parity
2583                  * is scrubbing parity, luckily, use the other one to repair
2584                  * the data, or we can not repair the data stripe.
2585                  */
2586                 if (failp != rbio->scrubp)
2587                         goto cleanup;
2588
2589                 __raid_recover_end_io(rbio);
2590         } else {
2591                 finish_parity_scrub(rbio, 1);
2592         }
2593         return;
2594
2595 cleanup:
2596         rbio_orig_end_io(rbio, BLK_STS_IOERR);
2597 }
2598
2599 /*
2600  * end io for the read phase of the rmw cycle.  All the bios here are physical
2601  * stripe bios we've read from the disk so we can recalculate the parity of the
2602  * stripe.
2603  *
2604  * This will usually kick off finish_rmw once all the bios are read in, but it
2605  * may trigger parity reconstruction if we had any errors along the way
2606  */
2607 static void raid56_parity_scrub_end_io(struct bio *bio)
2608 {
2609         struct btrfs_raid_bio *rbio = bio->bi_private;
2610
2611         if (bio->bi_status)
2612                 fail_bio_stripe(rbio, bio);
2613         else
2614                 set_bio_pages_uptodate(bio);
2615
2616         bio_put(bio);
2617
2618         if (!atomic_dec_and_test(&rbio->stripes_pending))
2619                 return;
2620
2621         /*
2622          * this will normally call finish_rmw to start our write
2623          * but if there are any failed stripes we'll reconstruct
2624          * from parity first
2625          */
2626         validate_rbio_for_parity_scrub(rbio);
2627 }
2628
2629 static void raid56_parity_scrub_stripe(struct btrfs_raid_bio *rbio)
2630 {
2631         int bios_to_read = 0;
2632         struct bio_list bio_list;
2633         int ret;
2634         int pagenr;
2635         int stripe;
2636         struct bio *bio;
2637
2638         bio_list_init(&bio_list);
2639
2640         ret = alloc_rbio_essential_pages(rbio);
2641         if (ret)
2642                 goto cleanup;
2643
2644         atomic_set(&rbio->error, 0);
2645         /*
2646          * build a list of bios to read all the missing parts of this
2647          * stripe
2648          */
2649         for (stripe = 0; stripe < rbio->real_stripes; stripe++) {
2650                 for_each_set_bit(pagenr, rbio->dbitmap, rbio->stripe_npages) {
2651                         struct page *page;
2652                         /*
2653                          * we want to find all the pages missing from
2654                          * the rbio and read them from the disk.  If
2655                          * page_in_rbio finds a page in the bio list
2656                          * we don't need to read it off the stripe.
2657                          */
2658                         page = page_in_rbio(rbio, stripe, pagenr, 1);
2659                         if (page)
2660                                 continue;
2661
2662                         page = rbio_stripe_page(rbio, stripe, pagenr);
2663                         /*
2664                          * the bio cache may have handed us an uptodate
2665                          * page.  If so, be happy and use it
2666                          */
2667                         if (PageUptodate(page))
2668                                 continue;
2669
2670                         ret = rbio_add_io_page(rbio, &bio_list, page,
2671                                        stripe, pagenr, rbio->stripe_len);
2672                         if (ret)
2673                                 goto cleanup;
2674                 }
2675         }
2676
2677         bios_to_read = bio_list_size(&bio_list);
2678         if (!bios_to_read) {
2679                 /*
2680                  * this can happen if others have merged with
2681                  * us, it means there is nothing left to read.
2682                  * But if there are missing devices it may not be
2683                  * safe to do the full stripe write yet.
2684                  */
2685                 goto finish;
2686         }
2687
2688         /*
2689          * the bbio may be freed once we submit the last bio.  Make sure
2690          * not to touch it after that
2691          */
2692         atomic_set(&rbio->stripes_pending, bios_to_read);
2693         while (1) {
2694                 bio = bio_list_pop(&bio_list);
2695                 if (!bio)
2696                         break;
2697
2698                 bio->bi_private = rbio;
2699                 bio->bi_end_io = raid56_parity_scrub_end_io;
2700                 bio_set_op_attrs(bio, REQ_OP_READ, 0);
2701
2702                 btrfs_bio_wq_end_io(rbio->fs_info, bio, BTRFS_WQ_ENDIO_RAID56);
2703
2704                 submit_bio(bio);
2705         }
2706         /* the actual write will happen once the reads are done */
2707         return;
2708
2709 cleanup:
2710         rbio_orig_end_io(rbio, BLK_STS_IOERR);
2711
2712         while ((bio = bio_list_pop(&bio_list)))
2713                 bio_put(bio);
2714
2715         return;
2716
2717 finish:
2718         validate_rbio_for_parity_scrub(rbio);
2719 }
2720
2721 static void scrub_parity_work(struct btrfs_work *work)
2722 {
2723         struct btrfs_raid_bio *rbio;
2724
2725         rbio = container_of(work, struct btrfs_raid_bio, work);
2726         raid56_parity_scrub_stripe(rbio);
2727 }
2728
2729 static void async_scrub_parity(struct btrfs_raid_bio *rbio)
2730 {
2731         btrfs_init_work(&rbio->work, btrfs_rmw_helper,
2732                         scrub_parity_work, NULL, NULL);
2733
2734         btrfs_queue_work(rbio->fs_info->rmw_workers, &rbio->work);
2735 }
2736
2737 void raid56_parity_submit_scrub_rbio(struct btrfs_raid_bio *rbio)
2738 {
2739         if (!lock_stripe_add(rbio))
2740                 async_scrub_parity(rbio);
2741 }
2742
2743 /* The following code is used for dev replace of a missing RAID 5/6 device. */
2744
2745 struct btrfs_raid_bio *
2746 raid56_alloc_missing_rbio(struct btrfs_fs_info *fs_info, struct bio *bio,
2747                           struct btrfs_bio *bbio, u64 length)
2748 {
2749         struct btrfs_raid_bio *rbio;
2750
2751         rbio = alloc_rbio(fs_info, bbio, length);
2752         if (IS_ERR(rbio))
2753                 return NULL;
2754
2755         rbio->operation = BTRFS_RBIO_REBUILD_MISSING;
2756         bio_list_add(&rbio->bio_list, bio);
2757         /*
2758          * This is a special bio which is used to hold the completion handler
2759          * and make the scrub rbio is similar to the other types
2760          */
2761         ASSERT(!bio->bi_iter.bi_size);
2762
2763         rbio->faila = find_logical_bio_stripe(rbio, bio);
2764         if (rbio->faila == -1) {
2765                 BUG();
2766                 kfree(rbio);
2767                 return NULL;
2768         }
2769
2770         /*
2771          * When we get bbio, we have already increased bio_counter, record it
2772          * so we can free it at rbio_orig_end_io()
2773          */
2774         rbio->generic_bio_cnt = 1;
2775
2776         return rbio;
2777 }
2778
2779 void raid56_submit_missing_rbio(struct btrfs_raid_bio *rbio)
2780 {
2781         if (!lock_stripe_add(rbio))
2782                 async_read_rebuild(rbio);
2783 }