source: mainline/uspace/srv/bd/hr/parity_stripe.c

Last change on this file was c1c1c41, checked in by Miroslav Cimerman <mc@…>, 11 days ago

hr: add author's email address to RAID 5 files
  • Property mode set to 100644
File size: 23.2 KB
Line 
1/*
2 * Copyright (c) 2025 Miroslav Cimerman <mc@doas.su>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup hr
30 * @{
31 */
32/**
33 * @file
34 */
35
36#include <stdlib.h>
37#include <stdio.h>
38#include <str.h>
39
40#include "io.h"
41#include "parity_stripe.h"
42#include "util.h"
43#include "var.h"
44
45static void hr_execute_write_stripe_degraded_mixed(hr_stripe_t *, size_t);
46static void hr_execute_write_stripe_degraded(hr_stripe_t *, size_t);
47static void hr_execute_write_stripe_optimal_reconstruct(hr_stripe_t *);
48static void hr_execute_write_stripe_subtract(hr_stripe_t *, size_t);
49static void hr_execute_write_stripe(hr_stripe_t *, size_t);
50static void hr_execute_read_stripe(hr_stripe_t *, size_t);
51static bool hr_stripe_range_non_extension(const range_t *, const range_t *,
52 range_t *);
53static size_t hr_stripe_merge_extent_spans(hr_stripe_t *, size_t, range_t [2]);
54static void hr_stripe_extend_range(range_t *, const range_t *);
55static bool hr_ranges_overlap(const range_t *, const range_t *, range_t *);
56
57hr_stripe_t *hr_create_stripes(hr_volume_t *vol, uint64_t strip_size,
58 size_t cnt, bool write)
59{
60 hr_stripe_t *stripes = hr_calloc_waitok(cnt, sizeof(*stripes));
61
62 for (size_t i = 0; i < cnt; i++) {
63 fibril_mutex_initialize(&stripes[i].parity_lock);
64 fibril_condvar_initialize(&stripes[i].ps_added_cv);
65 stripes[i].vol = vol;
66 stripes[i].write = write;
67 stripes[i].parity = hr_calloc_waitok(1, strip_size);
68 stripes[i].parity_size = strip_size;
69 stripes[i].extent_span = hr_calloc_waitok(vol->extent_no,
70 sizeof(*stripes[i].extent_span));
71 }
72
73 return stripes;
74}
75
76void hr_destroy_stripes(hr_stripe_t *stripes, size_t cnt)
77{
78 if (stripes == NULL)
79 return;
80
81 for (size_t i = 0; i < cnt; i++) {
82 if (stripes[i].parity != NULL)
83 free(stripes[i].parity);
84 if (stripes[i].extent_span != NULL)
85 free(stripes[i].extent_span);
86 }
87
88 free(stripes);
89}
90
91void hr_reset_stripe(hr_stripe_t *stripe)
92{
93 memset(stripe->parity, 0, stripe->parity_size);
94 stripe->ps_added = 0;
95 stripe->ps_to_be_added = 0;
96 stripe->p_count_final = false;
97
98 stripe->rc = EOK;
99 stripe->abort = false;
100 stripe->done = false;
101}
102
103void hr_stripe_commit_parity(hr_stripe_t *stripe, uint64_t strip_off,
104 const void *data, uint64_t size)
105{
106 fibril_mutex_lock(&stripe->parity_lock);
107 hr_raid5_xor(stripe->parity + strip_off, data, size);
108 stripe->ps_added++;
109 fibril_condvar_broadcast(&stripe->ps_added_cv);
110 fibril_mutex_unlock(&stripe->parity_lock);
111}
112
113void hr_stripe_wait_for_parity_commits(hr_stripe_t *stripe)
114{
115 fibril_mutex_lock(&stripe->parity_lock);
116 while ((!stripe->p_count_final ||
117 stripe->ps_added < stripe->ps_to_be_added) && !stripe->abort) {
118 fibril_condvar_wait(&stripe->ps_added_cv, &stripe->parity_lock);
119 }
120 fibril_mutex_unlock(&stripe->parity_lock);
121}
122
123void hr_stripe_parity_abort(hr_stripe_t *stripe)
124{
125 fibril_mutex_lock(&stripe->parity_lock);
126 stripe->abort = true;
127 fibril_condvar_broadcast(&stripe->ps_added_cv);
128 fibril_mutex_unlock(&stripe->parity_lock);
129}
130
131void hr_execute_stripe(hr_stripe_t *stripe, size_t bad_extent)
132{
133 if (stripe->write)
134 hr_execute_write_stripe(stripe, bad_extent);
135 else
136 hr_execute_read_stripe(stripe, bad_extent);
137}
138
139void hr_wait_for_stripe(hr_stripe_t *stripe)
140{
141 stripe->rc = hr_fgroup_wait(stripe->worker_group, NULL, NULL);
142 if (stripe->rc == EAGAIN)
143 hr_reset_stripe(stripe);
144 else
145 stripe->done = true;
146}
147
148static void hr_execute_write_stripe_degraded_mixed(hr_stripe_t *stripe,
149 size_t bad_extent)
150{
151 hr_volume_t *vol = stripe->vol;
152
153 stripe->range_count = hr_stripe_merge_extent_spans(stripe,
154 vol->extent_no, stripe->total_height);
155
156 size_t worker_cnt = (vol->extent_no - 2) * 3 + 3; /* upper bound */
157 stripe->worker_group = hr_fgroup_create(vol->fge, worker_cnt);
158
159 stripe->ps_to_be_added = 1;
160
161 hr_io_raid5_t *nop_write = hr_fgroup_alloc(stripe->worker_group);
162 nop_write->ba = stripe->extent_span[bad_extent].range.start;
163 nop_write->cnt = stripe->extent_span[bad_extent].cnt;
164 nop_write->strip_off =
165 stripe->extent_span[bad_extent].strip_off * vol->bsize;
166 nop_write->data_write = stripe->extent_span[bad_extent].data_write;
167 nop_write->vol = vol;
168 nop_write->stripe = stripe;
169
170 hr_fgroup_submit(stripe->worker_group, hr_io_raid5_noop_writer,
171 nop_write);
172
173 for (size_t e = 0; e < vol->extent_no; e++) {
174 if (e == bad_extent || e == stripe->p_extent)
175 continue;
176
177 range_t uncommon = { 0, 0 };
178 bool has_uncommon;
179 has_uncommon = hr_stripe_range_non_extension(
180 &stripe->extent_span[bad_extent].range,
181 &stripe->extent_span[e].range,
182 &uncommon);
183
184 if (stripe->extent_span[e].cnt == 0 || has_uncommon) {
185 stripe->ps_to_be_added++;
186
187 hr_io_raid5_t *io =
188 hr_fgroup_alloc(stripe->worker_group);
189 io->extent = e;
190 if (stripe->extent_span[bad_extent].cnt == 0) {
191 io->ba =
192 stripe->extent_span[bad_extent].range.start;
193 io->cnt = stripe->extent_span[bad_extent].cnt;
194 } else {
195 io->ba = uncommon.start;
196 io->cnt = uncommon.end - uncommon.start + 1;
197 }
198 io->strip_off =
199 stripe->extent_span[bad_extent].strip_off *
200 vol->bsize;
201 io->vol = vol;
202 io->stripe = stripe;
203
204 hr_fgroup_submit(stripe->worker_group,
205 hr_io_raid5_reconstruct_reader, io);
206
207 if (stripe->extent_span[e].cnt == 0)
208 continue;
209 }
210
211 range_t overlap_range;
212 bool overlap_up = true;
213 if (hr_ranges_overlap(&stripe->extent_span[e].range,
214 &stripe->extent_span[bad_extent].range,
215 &overlap_range)) {
216 stripe->ps_to_be_added++;
217
218 hr_io_raid5_t *io =
219 hr_fgroup_alloc(stripe->worker_group);
220 io->extent = e;
221 io->ba = overlap_range.start;
222 io->cnt = overlap_range.end - overlap_range.start + 1;
223
224 size_t diff = overlap_range.start -
225 stripe->extent_span[e].range.start;
226
227 io->strip_off =
228 (stripe->extent_span[e].strip_off + diff) *
229 vol->bsize;
230
231 io->data_write = stripe->extent_span[e].data_write;
232 io->data_write += diff * vol->bsize;
233 if (diff == 0)
234 overlap_up = false;
235
236 io->vol = vol;
237 io->stripe = stripe;
238
239 hr_fgroup_submit(stripe->worker_group,
240 hr_io_raid5_writer, io);
241 }
242
243 bool has_independent;
244 range_t independent = { 0, 0 };
245 has_independent = hr_stripe_range_non_extension(
246 &stripe->extent_span[e].range,
247 &stripe->extent_span[bad_extent].range,
248 &independent);
249 if (has_independent) {
250 stripe->ps_to_be_added++;
251
252 hr_io_raid5_t *io =
253 hr_fgroup_alloc(stripe->worker_group);
254 io->extent = e;
255 io->ba = independent.start;
256 io->cnt = independent.end - independent.start + 1;
257 size_t diff = 0;
258 if (!overlap_up) {
259 diff = overlap_range.end -
260 overlap_range.start + 1;
261 }
262 io->strip_off =
263 (stripe->extent_span[e].strip_off + diff) *
264 vol->bsize;
265 io->data_write = stripe->extent_span[e].data_write;
266 io->data_write += diff * vol->bsize;
267 io->vol = vol;
268 io->stripe = stripe;
269
270 hr_fgroup_submit(stripe->worker_group,
271 hr_io_raid5_subtract_writer, io);
272 }
273 }
274
275 bool has_independent = false;
276 range_t independent = { 0, 0 };
277 for (size_t r = 0; r < stripe->range_count; r++) {
278 has_independent = hr_stripe_range_non_extension(
279 &stripe->total_height[r],
280 &stripe->extent_span[bad_extent].range,
281 &independent);
282 if (has_independent) {
283 stripe->ps_to_be_added++;
284
285 hr_io_raid5_t *io =
286 hr_fgroup_alloc(stripe->worker_group);
287 io->extent = stripe->p_extent;
288 io->ba = independent.start;
289 io->cnt = independent.end - independent.start + 1;
290
291 io->strip_off = io->ba;
292 hr_sub_data_offset(vol, &io->strip_off);
293 io->strip_off %= vol->strip_size / vol->bsize;
294 io->strip_off *= vol->bsize;
295
296 io->vol = vol;
297 io->stripe = stripe;
298
299 hr_fgroup_submit(stripe->worker_group,
300 hr_io_raid5_reconstruct_reader, io);
301 }
302
303 hr_io_raid5_t *pio = hr_fgroup_alloc(stripe->worker_group);
304 pio->extent = stripe->p_extent;
305 pio->ba = stripe->total_height[r].start;
306 pio->cnt = stripe->total_height[r].end -
307 stripe->total_height[r].start + 1;
308 pio->strip_off = pio->ba;
309 hr_sub_data_offset(vol, &pio->strip_off);
310 pio->strip_off %= vol->strip_size / vol->bsize;
311 pio->strip_off *= vol->bsize;
312 pio->vol = vol;
313 pio->stripe = stripe;
314
315 hr_fgroup_submit(stripe->worker_group,
316 hr_io_raid5_parity_writer, pio);
317 }
318
319 stripe->p_count_final = true;
320 fibril_condvar_broadcast(&stripe->ps_added_cv);
321}
322
323static void hr_execute_write_stripe_degraded(hr_stripe_t *stripe,
324 size_t bad_extent)
325{
326 hr_volume_t *vol = stripe->vol;
327
328 /* parity is bad, issue non-redundant writes */
329 if (bad_extent == stripe->p_extent) {
330 stripe->worker_group =
331 hr_fgroup_create(vol->fge, stripe->strips_touched);
332
333 for (size_t e = 0; e < vol->extent_no; e++) {
334 if (e == bad_extent)
335 continue;
336 if (stripe->extent_span[e].cnt == 0)
337 continue;
338
339 hr_io_raid5_t *io =
340 hr_fgroup_alloc(stripe->worker_group);
341 io->extent = e;
342 io->data_write = stripe->extent_span[e].data_write;
343 io->ba = stripe->extent_span[e].range.start;
344 io->cnt = stripe->extent_span[e].cnt;
345 io->strip_off =
346 stripe->extent_span[e].strip_off * vol->bsize;
347 io->vol = vol;
348 io->stripe = stripe;
349
350 hr_fgroup_submit(stripe->worker_group,
351 hr_io_raid5_basic_writer, io);
352 }
353
354 return;
355 }
356
357 if (stripe->extent_span[bad_extent].cnt > 0)
358 hr_execute_write_stripe_degraded_mixed(stripe, bad_extent);
359 else
360 hr_execute_write_stripe_subtract(stripe, bad_extent);
361}
362
363static void hr_execute_write_stripe_optimal_reconstruct(hr_stripe_t *stripe)
364{
365 hr_volume_t *vol = stripe->vol;
366
367 stripe->range_count = hr_stripe_merge_extent_spans(stripe,
368 vol->extent_no, stripe->total_height);
369
370 bool full_stripe = false;
371 size_t worker_cnt;
372 if (stripe->strips_touched == vol->extent_no - 1 &&
373 stripe->partial_strips_touched == 0) {
374 /* full-stripe */
375 worker_cnt = stripe->strips_touched; /* writers */
376 worker_cnt += 1; /* parity writer */
377
378 stripe->ps_to_be_added = stripe->strips_touched;
379 stripe->p_count_final = true;
380
381 full_stripe = true;
382 } else {
383 worker_cnt = stripe->strips_touched; /* writers */
384
385 /* readers (upper bound) */
386 worker_cnt += ((vol->extent_no - 1) - stripe->strips_touched) *
387 stripe->range_count;
388 worker_cnt += stripe->partial_strips_touched;
389
390 worker_cnt += stripe->range_count; /* parity writer(s) */
391
392 stripe->ps_to_be_added = stripe->strips_touched; /* writers */
393 }
394
395 stripe->worker_group = hr_fgroup_create(vol->fge, worker_cnt);
396
397 for (size_t e = 0; e < vol->extent_no; e++) {
398 if (e == stripe->p_extent)
399 continue;
400
401 if (stripe->extent_span[e].cnt == 0)
402 continue;
403
404 hr_io_raid5_t *io = hr_fgroup_alloc(stripe->worker_group);
405 io->extent = e;
406 io->data_write = stripe->extent_span[e].data_write;
407 io->ba = stripe->extent_span[e].range.start;
408 io->cnt = stripe->extent_span[e].cnt;
409 io->strip_off = stripe->extent_span[e].strip_off * vol->bsize;
410 io->vol = vol;
411 io->stripe = stripe;
412
413 hr_fgroup_submit(stripe->worker_group, hr_io_raid5_writer, io);
414 }
415
416 for (size_t r = 0; r < stripe->range_count; r++) {
417 if (full_stripe)
418 goto skip_readers;
419 for (size_t e = 0; e < vol->extent_no; e++) {
420 if (e == stripe->p_extent)
421 continue;
422
423 range_t range_extension = { 0, 0 };
424
425 bool need_reader = false;
426 if (stripe->extent_span[e].cnt == 0) {
427 range_extension = stripe->total_height[r];
428 need_reader = true;
429 } else {
430 need_reader = hr_stripe_range_non_extension(
431 &stripe->total_height[r],
432 &stripe->extent_span[e].range,
433 &range_extension);
434 }
435
436 if (need_reader) {
437 stripe->ps_to_be_added++;
438
439 hr_io_raid5_t *io =
440 hr_fgroup_alloc(stripe->worker_group);
441 io->extent = e;
442 io->ba = range_extension.start;
443 io->cnt = range_extension.end -
444 range_extension.start + 1;
445 io->vol = vol;
446 io->stripe = stripe;
447
448 io->strip_off = io->ba;
449 hr_sub_data_offset(vol, &io->strip_off);
450 io->strip_off %= vol->strip_size / vol->bsize;
451 io->strip_off *= vol->bsize;
452
453 hr_fgroup_submit(stripe->worker_group,
454 hr_io_raid5_reconstruct_reader, io);
455 }
456 }
457
458 stripe->p_count_final = true;
459 fibril_condvar_broadcast(&stripe->ps_added_cv);
460
461 skip_readers:
462
463 /* parity writer */
464 hr_io_raid5_t *io = hr_fgroup_alloc(stripe->worker_group);
465 io->extent = stripe->p_extent;
466 io->ba = stripe->total_height[r].start;
467 io->cnt = stripe->total_height[r].end -
468 stripe->total_height[r].start + 1;
469 io->vol = vol;
470 io->stripe = stripe;
471
472 io->strip_off = io->ba;
473 hr_sub_data_offset(vol, &io->strip_off);
474 io->strip_off %= vol->strip_size / vol->bsize;
475 io->strip_off *= vol->bsize;
476
477 hr_fgroup_submit(stripe->worker_group,
478 hr_io_raid5_parity_writer, io);
479 }
480}
481
482static void hr_execute_write_stripe_subtract(hr_stripe_t *stripe, size_t bad)
483{
484 hr_volume_t *vol = stripe->vol;
485
486 stripe->range_count = hr_stripe_merge_extent_spans(stripe,
487 vol->extent_no, stripe->total_height);
488
489 size_t worker_cnt;
490 worker_cnt = stripe->strips_touched; /* writers */
491 worker_cnt += stripe->range_count * 2; /* parity readers & writers */
492
493 stripe->ps_to_be_added = stripe->strips_touched; /* writers */
494 stripe->ps_to_be_added += stripe->range_count; /* parity readers */
495 stripe->p_count_final = true;
496
497 stripe->worker_group = hr_fgroup_create(vol->fge, worker_cnt);
498
499 for (size_t e = 0; e < vol->extent_no; e++) {
500 if (e == bad || e == stripe->p_extent)
501 continue;
502
503 if (stripe->extent_span[e].cnt == 0)
504 continue;
505
506 hr_io_raid5_t *io = hr_fgroup_alloc(stripe->worker_group);
507 io->extent = e;
508 io->data_write = stripe->extent_span[e].data_write;
509 io->ba = stripe->extent_span[e].range.start;
510 io->cnt = stripe->extent_span[e].cnt;
511 io->strip_off = stripe->extent_span[e].strip_off * vol->bsize;
512 io->vol = vol;
513 io->stripe = stripe;
514
515 hr_fgroup_submit(stripe->worker_group,
516 hr_io_raid5_subtract_writer, io);
517 }
518
519 for (size_t r = 0; r < stripe->range_count; r++) {
520 hr_io_raid5_t *p_reader = hr_fgroup_alloc(stripe->worker_group);
521 p_reader->extent = stripe->p_extent;
522 p_reader->ba = stripe->total_height[r].start;
523 p_reader->cnt = stripe->total_height[r].end -
524 stripe->total_height[r].start + 1;
525 p_reader->vol = vol;
526 p_reader->stripe = stripe;
527
528 p_reader->strip_off = p_reader->ba;
529 hr_sub_data_offset(vol, &p_reader->strip_off);
530 p_reader->strip_off %= vol->strip_size / vol->bsize;
531 p_reader->strip_off *= vol->bsize;
532
533 hr_fgroup_submit(stripe->worker_group,
534 hr_io_raid5_reconstruct_reader, p_reader);
535
536 hr_io_raid5_t *p_writer = hr_fgroup_alloc(stripe->worker_group);
537 p_writer->extent = stripe->p_extent;
538 p_writer->ba = stripe->total_height[r].start;
539 p_writer->cnt = stripe->total_height[r].end -
540 stripe->total_height[r].start + 1;
541 p_writer->vol = vol;
542 p_writer->stripe = stripe;
543
544 p_writer->strip_off = p_writer->ba;
545 hr_sub_data_offset(vol, &p_writer->strip_off);
546 p_writer->strip_off %= vol->strip_size / vol->bsize;
547 p_writer->strip_off *= vol->bsize;
548
549 hr_fgroup_submit(stripe->worker_group,
550 hr_io_raid5_parity_writer, p_writer);
551 }
552
553}
554
555static void hr_execute_write_stripe(hr_stripe_t *stripe, size_t bad_extent)
556{
557 hr_volume_t *vol = stripe->vol;
558
559 if (bad_extent < vol->extent_no) {
560 hr_execute_write_stripe_degraded(stripe, bad_extent);
561 return;
562 }
563
564 if (stripe->subtract)
565 hr_execute_write_stripe_subtract(stripe, vol->extent_no);
566 else
567 hr_execute_write_stripe_optimal_reconstruct(stripe);
568}
569
570static void hr_execute_read_stripe(hr_stripe_t *stripe, size_t bad_extent)
571{
572 hr_volume_t *vol = stripe->vol;
573
574 /* no parity involved */
575 if (bad_extent == vol->extent_no ||
576 bad_extent == stripe->p_extent ||
577 stripe->extent_span[bad_extent].cnt == 0) {
578 stripe->worker_group =
579 hr_fgroup_create(vol->fge, stripe->strips_touched);
580 for (size_t e = 0; e < vol->extent_no; e++) {
581 if (e == bad_extent || e == stripe->p_extent)
582 continue;
583 if (stripe->extent_span[e].cnt == 0)
584 continue;
585
586 hr_io_raid5_t *io =
587 hr_fgroup_alloc(stripe->worker_group);
588 io->extent = e;
589 io->data_read = stripe->extent_span[e].data_read;
590 io->ba = stripe->extent_span[e].range.start;
591 io->cnt = stripe->extent_span[e].cnt;
592 io->strip_off =
593 stripe->extent_span[e].strip_off * vol->bsize;
594 io->vol = vol;
595 io->stripe = stripe;
596
597 hr_fgroup_submit(stripe->worker_group,
598 hr_io_raid5_basic_reader, io);
599 }
600
601 return;
602 }
603
604 /* parity involved */
605
606 size_t worker_cnt = (vol->extent_no - 2) * 2 + 1; /* upper bound */
607 stripe->worker_group = hr_fgroup_create(vol->fge, worker_cnt);
608
609 stripe->ps_to_be_added = 0;
610
611 for (size_t e = 0; e < vol->extent_no; e++) {
612 if (e == bad_extent || e == stripe->p_extent)
613 continue;
614
615 range_t uncommon = { 0, 0 };
616 bool has_uncommon;
617 has_uncommon = hr_stripe_range_non_extension(
618 &stripe->extent_span[bad_extent].range,
619 &stripe->extent_span[e].range,
620 &uncommon);
621
622 if (stripe->extent_span[e].cnt == 0 || has_uncommon) {
623
624 stripe->ps_to_be_added++;
625
626 hr_io_raid5_t *io =
627 hr_fgroup_alloc(stripe->worker_group);
628 io->extent = e;
629 if (stripe->extent_span[bad_extent].cnt == 0) {
630 io->ba =
631 stripe->extent_span[bad_extent].range.start;
632 io->cnt = stripe->extent_span[bad_extent].cnt;
633 } else {
634 io->ba = uncommon.start;
635 io->cnt = uncommon.end - uncommon.start + 1;
636 }
637 io->strip_off =
638 stripe->extent_span[bad_extent].strip_off *
639 vol->bsize;
640 io->vol = vol;
641 io->stripe = stripe;
642
643 hr_fgroup_submit(stripe->worker_group,
644 hr_io_raid5_reconstruct_reader, io);
645
646 if (stripe->extent_span[e].cnt == 0)
647 continue;
648 }
649
650 range_t overlap_range;
651 bool overlap_up = true;
652 if (hr_ranges_overlap(&stripe->extent_span[e].range,
653 &stripe->extent_span[bad_extent].range,
654 &overlap_range)) {
655
656 stripe->ps_to_be_added++;
657
658 hr_io_raid5_t *io =
659 hr_fgroup_alloc(stripe->worker_group);
660 io->extent = e;
661 io->ba = overlap_range.start;
662 io->cnt = overlap_range.end - overlap_range.start + 1;
663
664 size_t diff = overlap_range.start -
665 stripe->extent_span[e].range.start;
666 io->strip_off =
667 (stripe->extent_span[e].strip_off + diff) *
668 vol->bsize;
669
670 io->data_read = stripe->extent_span[e].data_read;
671 io->data_read += diff * vol->bsize;
672 if (diff == 0)
673 overlap_up = false;
674
675 io->vol = vol;
676 io->stripe = stripe;
677
678 hr_fgroup_submit(stripe->worker_group,
679 hr_io_raid5_reader, io);
680 }
681
682 bool has_independent;
683 range_t independent = { 0, 0 };
684 has_independent = hr_stripe_range_non_extension(
685 &stripe->extent_span[e].range,
686 &uncommon,
687 &independent);
688 if (has_independent) {
689 hr_io_raid5_t *io =
690 hr_fgroup_alloc(stripe->worker_group);
691 io->extent = e;
692 io->ba = independent.start;
693 io->cnt = independent.end - independent.start + 1;
694 size_t diff = 0;
695 if (!overlap_up) {
696 diff =
697 overlap_range.end - overlap_range.start + 1;
698 }
699 io->strip_off =
700 (stripe->extent_span[e].strip_off + diff) *
701 vol->bsize;
702 io->data_read = stripe->extent_span[e].data_read;
703 io->data_read += diff * vol->bsize;
704 io->vol = vol;
705 io->stripe = stripe;
706
707 hr_fgroup_submit(stripe->worker_group,
708 hr_io_raid5_basic_reader, io);
709 }
710 }
711
712 stripe->ps_to_be_added++;
713
714 hr_io_raid5_t *io = hr_fgroup_alloc(stripe->worker_group);
715 io->extent = stripe->p_extent;
716 io->ba = stripe->extent_span[bad_extent].range.start;
717 io->cnt = stripe->extent_span[bad_extent].cnt;
718 io->strip_off = stripe->extent_span[bad_extent].strip_off * vol->bsize;
719 io->vol = vol;
720 io->stripe = stripe;
721
722 hr_fgroup_submit(stripe->worker_group, hr_io_raid5_reconstruct_reader,
723 io);
724
725 stripe->p_count_final = true;
726 fibril_condvar_broadcast(&stripe->ps_added_cv);
727
728 hr_io_raid5_t *pcopier_io = hr_fgroup_alloc(stripe->worker_group);
729 pcopier_io->cnt = stripe->extent_span[bad_extent].cnt;
730 pcopier_io->strip_off =
731 stripe->extent_span[bad_extent].strip_off * vol->bsize;
732 pcopier_io->data_read = stripe->extent_span[bad_extent].data_read;
733 pcopier_io->vol = vol;
734 pcopier_io->stripe = stripe;
735
736 hr_fgroup_submit(stripe->worker_group, hr_io_raid5_parity_getter,
737 pcopier_io);
738}
739
740/** Get non-overlapping part of 2 ranges.
741 *
742 * Return part of @param r1 not in @param r2.
743 *
744 * @param r1 Main range.
745 * @param r2 Queried range.
746 * @param out Place to store resulting range.
747 *
748 * @return true if output range is non-empty, else false.
749 */
750static bool hr_stripe_range_non_extension(const range_t *r1, const range_t *r2,
751 range_t *out)
752{
753 if (r1->end < r2->start) {
754 *out = *r1;
755 return true;
756 }
757
758 if (r1->start > r2->end) {
759 *out = *r1;
760 return true;
761 }
762
763 if (r1->start < r2->start && r1->end >= r2->start) {
764 out->start = r1->start;
765 out->end = r2->start - 1;
766 return out->start <= out->end;
767 }
768
769 if (r1->start <= r2->end && r1->end > r2->end) {
770 out->start = r2->end + 1;
771 out->end = r1->end;
772 return out->start <= out->end;
773 }
774
775 return false;
776}
777
778/** Merge adjascent or overlapping extent spans.
779 *
780 * @param s Stripe.
781 * @param extent_no Number of extents.
782 * @param out Place to store resulting ranges.
783 *
784 * @return Number of resulting ranges.
785 */
786static size_t hr_stripe_merge_extent_spans(hr_stripe_t *s, size_t extent_no,
787 range_t out[2])
788{
789 size_t out_count = 0;
790
791 for (size_t i = 0; i < extent_no; i++) {
792 if (s->extent_span[i].cnt == 0)
793 continue;
794 const range_t *r = &s->extent_span[i].range;
795 bool merged = false;
796
797 for (size_t j = 0; j < out_count; j++) {
798 if (hr_ranges_overlap(&out[j], r, NULL)) {
799 hr_stripe_extend_range(&out[j], r);
800 merged = true;
801
802 if (out_count == 2 &&
803 hr_ranges_overlap(&out[0], &out[1], NULL)) {
804 hr_stripe_extend_range(&out[0], &out[1]);
805 out_count = 1;
806 }
807
808 break;
809 }
810 }
811
812 if (!merged) {
813 assert(out_count < 2);
814 out[out_count++] = *r;
815 }
816 }
817
818 return out_count;
819}
820
821/** Extend a range.
822 *
823 * @param r1 Output range.
824 * @param r2 Range to extend the output one with.
825 *
826 */
827static void hr_stripe_extend_range(range_t *r1, const range_t *r2)
828{
829 if (r2->start < r1->start)
830 r1->start = r2->start;
831 if (r2->end > r1->end)
832 r1->end = r2->end;
833}
834
835static bool hr_ranges_overlap(const range_t *a, const range_t *b, range_t *out)
836{
837 uint64_t start = a->start > b->start ? a->start : b->start;
838 uint64_t end = a->end < b->end ? a->end : b->end;
839
840 if (start <= end) {
841 if (out != NULL) {
842 out->start = start;
843 out->end = end;
844 }
845
846 return true;
847 }
848
849 return false;
850}
851
852/** @}
853 */
Note: See TracBrowser for help on using the repository browser.