| blob | 499620afb44b259184d3a04ba73fb5a1e7d2c724 |
1 /*
2 * raid10.c : Multiple Devices driver for Linux
3 *
4 * Copyright (C) 2000-2004 Neil Brown
5 *
6 * RAID-10 support for md.
7 *
8 * Base on code in raid1.c. See raid1.c for futher copyright information.
9 *
10 *
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2, or (at your option)
14 * any later version.
15 *
16 * You should have received a copy of the GNU General Public License
17 * (for example /usr/src/linux/COPYING); if not, write to the Free
18 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
21 #include <linux/delay.h>
22 #include <linux/blkdev.h>
23 #include <linux/seq_file.h>
28 /*
29 * RAID10 provides a combination of RAID0 and RAID1 functionality.
30 * The layout of data is defined by
31 * chunk_size
32 * raid_disks
33 * near_copies (stored in low byte of layout)
34 * far_copies (stored in second byte of layout)
35 * far_offset (stored in bit 16 of layout )
36 *
37 * The data to be stored is divided into chunks using chunksize.
38 * Each device is divided into far_copies sections.
39 * In each section, chunks are laid out in a style similar to raid0, but
40 * near_copies copies of each chunk is stored (each on a different drive).
41 * The starting device for each section is offset near_copies from the starting
42 * device of the previous section.
43 * Thus they are (near_copies*far_copies) of each chunk, and each is on a different
44 * drive.
45 * near_copies and far_copies must be at least one, and their product is at most
46 * raid_disks.
47 *
48 * If far_offset is true, then the far_copies are handled a bit differently.
49 * The copies are still in different stripes, but instead of be very far apart
50 * on disk, there are adjacent stripes.
51 */
53 /*
54 * Number of guaranteed r10bios in case of extreme VM load:
55 */
56 #define NR_RAID10_BIOS 256
64 {
69 /* allocate a r10bio with room for raid_disks entries in the bios array */
75 }
78 {
80 }
82 /* Maximum size of each resync request */
83 #define RESYNC_BLOCK_SIZE (64*1024)
84 #define RESYNC_PAGES ((RESYNC_BLOCK_SIZE + PAGE_SIZE-1) / PAGE_SIZE)
85 /* amount of memory to reserve for resync requests */
86 #define RESYNC_WINDOW (1024*1024)
87 /* maximum number of concurrent requests, memory permitting */
88 #define RESYNC_DEPTH (32*1024*1024/RESYNC_BLOCK_SIZE)
90 /*
91 * When performing a resync, we need to read and compare, so
92 * we need as many pages are there are copies.
93 * When performing a recovery, we need 2 bios, one for read,
94 * one for write (we recover only one drive per r10buf)
95 *
96 */
98 {
110 }
114 else
117 /*
118 * Allocate bios.
119 */
125 }
126 /*
127 * Allocate RESYNC_PAGES data pages and attach them
128 * where needed.
129 */
138 }
139 }
143 out_free_pages:
150 out_free_bio:
155 }
158 {
170 }
172 }
173 }
175 }
178 {
186 }
187 }
190 {
193 /*
194 * Wake up any possible resync thread that waits for the device
195 * to go idle.
196 */
201 }
204 {
210 }
213 {
223 /* wake up frozen array... */
227 }
229 /*
230 * raid_end_bio_io() is called when we have finished servicing a mirrored
231 * operation and are ready to return a success/failure code to the buffer
232 * cache layer.
233 */
235 {
241 }
243 /*
244 * Update disk head position estimator based on IRQ completion info.
245 */
247 {
252 }
255 {
264 /*
265 * this branch is our 'one mirror IO has finished' event handler:
266 */
270 /*
271 * Set R10BIO_Uptodate in our master bio, so that
272 * we will return a good error code to the higher
273 * levels even if IO on some other mirrored buffer fails.
274 *
275 * The 'master' represents the composite IO operation to
276 * user-side. So if something waits for IO, then it will
277 * wait for the 'master' bio.
278 */
282 /*
283 * oops, read error:
284 */
290 }
293 }
296 {
307 /*
308 * this branch is our 'one mirror IO has finished' event handler:
309 */
312 /* an I/O failed, we can't clear the bitmap */
315 /*
316 * Set R10BIO_Uptodate in our master bio, so that
317 * we will return a good error code for to the higher
318 * levels even if IO on some other mirrored buffer fails.
319 *
320 * The 'master' represents the composite IO operation to
321 * user-side. So if something waits for IO, then it will
322 * wait for the 'master' bio.
323 */
328 /*
329 *
330 * Let's see if all mirrored write operations have finished
331 * already.
332 */
334 /* clear the bitmap if all writes complete successfully */
341 }
344 }
347 /*
348 * RAID10 layout manager
349 * Aswell as the chunksize and raid_disks count, there are two
350 * parameters: near_copies and far_copies.
351 * near_copies * far_copies must be <= raid_disks.
352 * Normally one of these will be 1.
353 * If both are 1, we get raid0.
354 * If near_copies == raid_disks, we get raid1.
355 *
356 * Chunks are layed out in raid0 style with near_copies copies of the
357 * first chunk, followed by near_copies copies of the next chunk and
358 * so on.
359 * If far_copies > 1, then after 1/far_copies of the array has been assigned
360 * as described above, we start again with a device offset of near_copies.
361 * So we effectively have another copy of the whole array further down all
362 * the drives, but with blocks on different drives.
363 * With this layout, and block is never stored twice on the one device.
364 *
365 * raid10_find_phys finds the sector offset of a given virtual sector
366 * on each device that it is on.
367 *
368 * raid10_find_virt does the reverse mapping, from a device and a
369 * sector offset to a virtual address
370 */
373 {
375 sector_t sector;
376 sector_t chunk;
377 sector_t stripe;
382 /* now calculate first sector/dev */
394 /* and calculate all the others */
400 slot++;
409 slot++;
410 }
411 dev++;
415 }
416 }
418 }
421 {
437 else
439 }
441 }
445 }
447 /**
448 * raid10_mergeable_bvec -- tell bio layer if a two requests can be merged
449 * @q: request queue
450 * @bvm: properties of new bio
451 * @biovec: the request that could be merged to it.
452 *
453 * Return amount of bytes we can accept at this offset
454 * If near_copies == raid_disk, there are no striping issues,
455 * but in that case, the function isn't called at all.
456 */
460 {
471 else
473 }
475 /*
476 * This routine returns the disk from which the requested read should
477 * be done. There is a per-array 'next expected sequential IO' sector
478 * number - if this matches on the next IO then we use the last disk.
479 * There is also a per-disk 'last know head position' sector that is
480 * maintained from IRQ contexts, both the normal and the resync IO
481 * completion handlers update this position correctly. If there is no
482 * perfect sequential match then we pick the disk whose head is closest.
483 *
484 * If there are 2 mirrors in the same 2 devices, performance degrades
485 * because position is mirror, not device based.
486 *
487 * The rdev for the device selected will have nr_pending incremented.
488 */
490 /*
491 * FIXME: possibly should rethink readbalancing and do it differently
492 * depending on near_copies / far_copies geometry.
493 */
495 {
504 /*
505 * Check if we can balance. We can balance on the whole
506 * device if no resync is going on (recovery is ok), or below
507 * the resync window. We take the first readable disk when
508 * above the resync window.
509 */
512 /* make sure that disk is operational */
519 slot++;
524 }
526 }
528 }
531 /* make sure the disk is operational */
537 slot ++;
541 }
543 }
549 /* Find the disk whose head is closest,
550 * or - for far > 1 - find the closest to partition beginning */
561 /* This optimisation is debatable, and completely destroys
562 * sequential read speed for 'far copies' arrays. So only
563 * keep it for 'near' arrays, and review those later.
564 */
569 }
571 /* for far > 1 always use the lowest address */
574 else
581 }
582 }
584 rb_out:
586 /* conf->next_seq_sect = this_sector + sectors;*/
590 else
595 }
598 {
615 }
616 }
618 }
621 {
626 }
629 {
641 }
642 }
645 }
648 {
649 /* Any writes that have been queued but are awaiting
650 * bitmap updates get flushed here.
651 * We return 1 if any requests were actually submitted.
652 */
662 /* flush any pending bitmap writes to disk
663 * before proceeding w/ I/O */
671 }
676 }
677 /* Barriers....
678 * Sometimes we need to suspend IO while we do something else,
679 * either some resync/recovery, or reconfigure the array.
680 * To do this we raise a 'barrier'.
681 * The 'barrier' is a counter that can be raised multiple times
682 * to count how many activities are happening which preclude
683 * normal IO.
684 * We can only raise the barrier if there is no pending IO.
685 * i.e. if nr_pending == 0.
686 * We choose only to raise the barrier if no-one is waiting for the
687 * barrier to go down. This means that as soon as an IO request
688 * is ready, no other operations which require a barrier will start
689 * until the IO request has had a chance.
690 *
691 * So: regular IO calls 'wait_barrier'. When that returns there
692 * is no backgroup IO happening, It must arrange to call
693 * allow_barrier when it has finished its IO.
694 * backgroup IO calls must call raise_barrier. Once that returns
695 * there is no normal IO happeing. It must arrange to call
696 * lower_barrier when the particular background IO completes.
697 */
700 {
704 /* Wait until no block IO is waiting (unless 'force') */
709 /* block any new IO from starting */
712 /* No wait for all pending IO to complete */
719 }
722 {
728 }
731 {
739 }
742 }
745 {
751 }
754 {
755 /* stop syncio and normal IO and wait for everything to
756 * go quiet.
757 * We increment barrier and nr_waiting, and then
758 * wait until nr_pending match nr_queued+1
759 * This is called in the context of one normal IO request
760 * that has failed. Thus any sync request that might be pending
761 * will be blocked by nr_pending, and we need to wait for
762 * pending IO requests to complete or be queued for re-try.
763 * Thus the number queued (nr_queued) plus this request (1)
764 * must match the number of pending IOs (nr_pending) before
765 * we continue.
766 */
776 }
779 {
780 /* reverse the effect of the freeze */
786 }
789 {
807 }
809 /* If this request crosses a chunk boundary, we need to
810 * split it. This will only happen for 1 PAGE (or less) requests.
811 */
816 /* Sanity check -- queue functions should prevent this happening */
820 /* This is a one page bio that upper layers
821 * refuse to split for us, so we need to split it.
822 */
832 bad_map:
839 }
843 /*
844 * Register the new request and wait if the reconstruction
845 * thread has put up a bar for new requests.
846 * Continue immediately if no resync is active currently.
847 */
866 /*
867 * read balancing logic:
868 */
874 }
890 }
892 /*
893 * WRITE:
894 */
895 /* first select target devices under rcu_lock and
896 * inc refcount on their rdev. Record them by setting
897 * bios[x] to bio
898 */
900 retry_write:
910 }
917 }
918 }
922 /* Have to wait for this device to get unblocked, then retry */
930 }
935 }
958 }
961 /* the array is dead */
965 }
973 /* In case raid10d snuck in to freeze_array */
980 }
983 {
994 else
996 }
1004 }
1007 {
1011 /*
1012 * If it is not operational, then we have already marked it as dead
1013 * else if it is the last working disks, ignore the error, let the
1014 * next level up know.
1015 * else mark the drive as failed
1016 */
1019 /*
1020 * Don't fail the drive, just return an IO error.
1021 * The test should really be more sophisticated than
1022 * "working_disks == 1", but it isn't critical, and
1023 * can wait until we do more sophisticated "is the drive
1024 * really dead" tests...
1025 */
1032 /*
1033 * if recovery is running, make sure it aborts.
1034 */
1036 }
1042 }
1045 {
1053 }
1065 }
1066 }
1069 {
1075 }
1077 /* check if there are enough drives for
1078 * every block to appear on atleast one
1079 */
1081 {
1089 cnt++;
1091 }
1096 }
1099 {
1104 /*
1105 * Find all non-in_sync disks within the RAID10 configuration
1106 * and mark them in_sync
1107 */
1117 }
1118 }
1122 }
1126 {
1135 /* only hot-add to in-sync arrays, as recovery is
1136 * very different from resync
1137 */
1149 else
1156 /* as we don't honour merge_bvec_fn, we must never risk
1157 * violating it, so limit ->max_sector to one PAGE, as
1158 * a one page request is never in violation.
1159 */
1171 }
1175 }
1178 {
1191 }
1192 /* Only remove faulty devices in recovery
1193 * is not possible.
1194 */
1199 }
1203 /* lost the race, try later */
1206 }
1207 }
1208 abort:
1212 }
1216 {
1236 }
1238 /* for reconstruct, we always reschedule after a read.
1239 * for resync, only after all reads
1240 */
1244 /* we have read all the blocks,
1245 * do the comparison in process context in raid10d
1246 */
1248 }
1249 }
1252 {
1272 /* the primary of several recovery bios */
1281 }
1282 }
1283 }
1285 /*
1286 * Note: sync and recover and handled very differently for raid10
1287 * This code is for resync.
1288 * For resync, we read through virtual addresses and read all blocks.
1289 * If there is any error, we schedule a write. The lowest numbered
1290 * drive is authoritative.
1291 * However requests come for physical address, so we need to map.
1292 * For every physical address there are raid_disks/copies virtual addresses,
1293 * which is always are least one, but is not necessarly an integer.
1294 * This means that a physical address can span multiple chunks, so we may
1295 * have to submit multiple io requests for a single sync request.
1296 */
1297 /*
1298 * We check if all blocks are in-sync and only write to blocks that
1299 * aren't in sync
1300 */
1302 {
1309 /* find the first device with a block */
1320 /* now find blocks with errors */
1332 /* We know that the bi_io_vec layout is the same for
1333 * both 'first' and 'i', so we just compare them.
1334 * All vec entries are PAGE_SIZE;
1335 */
1339 PAGE_SIZE))
1344 }
1346 /* Don't fix anything. */
1348 /* Ok, we need to write this bio
1349 * First we need to fixup bv_offset, bv_len and
1350 * bi_vecs, as the read request might have corrupted these
1351 */
1369 PAGE_SIZE);
1370 }
1381 }
1383 done:
1387 }
1388 }
1390 /*
1391 * Now for the recovery code.
1392 * Recovery happens across physical sectors.
1393 * We recover all non-is_sync drives by finding the virtual address of
1394 * each, and then choose a working drive that also has that virt address.
1395 * There is a separate r10_bio for each non-in_sync drive.
1396 * Only the first two slots are in use. The first for reading,
1397 * The second for writing.
1398 *
1399 */
1402 {
1408 /* move the pages across to the second bio
1409 * and submit the write request
1410 */
1417 }
1424 else
1426 }
1429 /*
1430 * This is a kernel thread which:
1431 *
1432 * 1. Retries failed read operations on working mirrors.
1433 * 2. Updates the raid superblock when problems encounter.
1434 * 3. Performs writes following reads for array synchronising.
1435 */
1438 {
1468 }
1469 sl++;
1476 /* Cannot read from anywhere -- bye bye array */
1480 }
1483 /* write it back and re-read */
1489 sl--;
1502 /* Well, this device is dead */
1506 }
1507 }
1513 sl--;
1525 /* Well, this device is dead */
1527 else
1529 "raid10:%s: read error corrected"
1538 }
1539 }
1544 }
1545 }
1548 {
1568 }
1584 /* we got a read error. Maybe the drive is bad. Maybe just
1585 * the block and we can fix it.
1586 * We freeze all other IO, and try reading the block from
1587 * other devices. When we find one, we re-write
1588 * and check it that fixes the read error.
1589 * This is all done synchronously while the array is
1590 * frozen.
1591 */
1596 }
1628 }
1629 }
1630 }
1633 }
1637 {
1647 }
1649 /*
1650 * perform a "sync" on one "block"
1651 *
1652 * We need to make sure that no normal I/O request - particularly write
1653 * requests - conflict with active sync requests.
1654 *
1655 * This is achieved by tracking pending requests and a 'barrier' concept
1656 * that can be installed to exclude normal IO requests.
1657 *
1658 * Resync and recovery are handled very differently.
1659 * We differentiate by looking at MD_RECOVERY_SYNC in mddev->recovery.
1660 *
1661 * For resync, we iterate over virtual addresses, read all copies,
1662 * and update if there are differences. If only one copy is live,
1663 * skip it.
1664 * For recovery, we iterate over physical addresses, read a good
1665 * value for each non-in_sync drive, and over-write.
1666 *
1667 * So, for recovery we may have several outstanding complex requests for a
1668 * given address, one for each out-of-sync device. We model this by allocating
1669 * a number of r10_bio structures, one for each out-of-sync device.
1670 * As we setup these structures, we collect all bio's together into a list
1671 * which we then process collectively to add pages, and then process again
1672 * to pass to generic_make_request.
1673 *
1674 * The r10_bio structures are linked using a borrowed master_bio pointer.
1675 * This link is counted in ->remaining. When the r10_bio that points to NULL
1676 * has its remaining count decremented to 0, the whole complex operation
1677 * is complete.
1678 *
1679 */
1682 {
1699 skipped:
1704 /* If we aborted, we need to abort the
1705 * sync on the 'current' bitmap chucks (there can
1706 * be several when recovering multiple devices).
1707 * as we may have started syncing it but not finished.
1708 * We can find the current address in
1709 * mddev->curr_resync, but for recovery,
1710 * we need to convert that to several
1711 * virtual addresses.
1712 */
1718 sector_t sect =
1722 }
1730 }
1732 /* if there has been nothing to do on any drive,
1733 * then there is nothing to do at all..
1734 */
1737 }
1742 /* make sure whole request will fit in a chunk - if chunks
1743 * are meaningful
1744 */
1748 /*
1749 * If there is non-resync activity waiting for us then
1750 * put in a delay to throttle resync.
1751 */
1755 /* Again, very different code for resync and recovery.
1756 * Both must result in an r10bio with a list of bios that
1757 * have bi_end_io, bi_sector, bi_bdev set,
1758 * and bi_private set to the r10bio.
1759 * For recovery, we may actually create several r10bios
1760 * with 2 bios in each, that correspond to the bios in the main one.
1761 * In this case, the subordinate r10bios link back through a
1762 * borrowed master_bio pointer, and the counter in the master
1763 * includes a ref from each subordinate.
1764 */
1765 /* First, we decide what to do and set ->bi_end_io
1766 * To end_sync_read if we want to read, and
1767 * end_sync_write if we will want to write.
1768 */
1772 /* recovery... the complicated one */
1780 /* want to reconstruct this device */
1784 /* Unless we are doing a full sync, we only need
1785 * to recover the block if it is set in the bitmap
1786 */
1793 /* yep, skip the sync_blocks here, but don't assume
1794 * that there will never be anything to do here
1795 */
1798 }
1813 /* Need to check if the array will still be
1814 * degraded
1815 */
1821 }
1830 /* This is where we read from */
1842 /* and we write to 'i' */
1862 }
1863 }
1865 /* Cannot recover, so abort the recovery */
1875 }
1876 }
1883 }
1885 }
1887 /* resync. Schedule a read for every block at this virt offset */
1895 /* We can skip this block */
1898 }
1932 count++;
1933 }
1940 }
1944 }
1945 }
1956 }
1972 /* stop here */
1976 /* remove last page from this bio */
1980 }
1982 }
1984 }
1988 bio_full:
2002 }
2003 }
2006 /* pretend they weren't skipped, it makes
2007 * no important difference in this case
2008 */
2012 giveup:
2013 /* There is nowhere to write, so all non-sync
2014 * drives must be failed, so try the next chunk...
2015 */
2020 chunks_skipped ++;
2023 }
2025 static sector_t
2027 {
2028 sector_t size;
2042 }
2045 {
2057 }
2067 }
2068 /*
2069 * copy the already verified devices into our private RAID10
2070 * bookkeeping area. [whatever we allocate in run(),
2071 * should be freed in stop()]
2072 */
2079 }
2081 GFP_KERNEL);
2086 }
2104 /* 'size' is now the number of chunks in the array */
2105 /* calculate "used chunks per device" in 'stride' */
2108 /* We need to round up when dividing by raid_disks to
2109 * get the stride size.
2110 */
2117 else
2127 }
2143 /* as we don't honour merge_bvec_fn, we must never risk
2144 * violating it, so limit ->max_sector to one PAGE, as
2145 * a one page request is never in violation.
2146 */
2152 }
2158 /* need to check that every block has at least one working mirror */
2163 }
2176 }
2177 }
2186 }
2192 /*
2193 * Ok, everything is just fine now
2194 */
2202 /* Calculate max read-ahead size.
2203 * We need to readahead at least twice a whole stripe....
2204 * maybe...
2205 */
2206 {
2211 }
2217 out_free_conf:
2224 out:
2226 }
2229 {
2244 }
2247 {
2257 }
2261 else
2264 }
2265 }
2268 {
2283 };
2286 {
2288 }
2291 {
2293 }