4 * Copyright (C) 2012-2014 Nodalink, EURL.
7 * BenoƮt Canet <benoit.canet@irqsave.net>
9 * Based on the design and code of blkverify.c (Copyright (C) 2010 IBM, Corp)
10 * and blkmirror.c (Copyright (C) 2011 Red Hat, Inc).
12 * This work is licensed under the terms of the GNU GPL, version 2 or later.
13 * See the COPYING file in the top-level directory.
16 #include <gnutls/gnutls.h>
17 #include <gnutls/crypto.h>
18 #include "block/block_int.h"
19 #include "qapi/qmp/qjson.h"
20 #include "qapi-event.h"
22 #define HASH_LENGTH 32
24 #define QUORUM_OPT_VOTE_THRESHOLD "vote-threshold"
25 #define QUORUM_OPT_BLKVERIFY "blkverify"
27 /* This union holds a vote hash value */
28 typedef union QuorumVoteValue
{
29 char h
[HASH_LENGTH
]; /* SHA-256 hash */
30 int64_t l
; /* simpler 64 bits hash */
34 typedef struct QuorumVoteItem
{
36 QLIST_ENTRY(QuorumVoteItem
) next
;
39 /* this structure is a vote version. A version is the set of votes sharing the
41 * The set of votes will be tracked with the items field and its cardinality is
44 typedef struct QuorumVoteVersion
{
45 QuorumVoteValue value
;
48 QLIST_HEAD(, QuorumVoteItem
) items
;
49 QLIST_ENTRY(QuorumVoteVersion
) next
;
52 /* this structure holds a group of vote versions together */
53 typedef struct QuorumVotes
{
54 QLIST_HEAD(, QuorumVoteVersion
) vote_list
;
55 bool (*compare
)(QuorumVoteValue
*a
, QuorumVoteValue
*b
);
58 /* the following structure holds the state of one quorum instance */
59 typedef struct BDRVQuorumState
{
60 BlockDriverState
**bs
; /* children BlockDriverStates */
61 int num_children
; /* children count */
62 int threshold
; /* if less than threshold children reads gave the
63 * same result a quorum error occurs.
65 bool is_blkverify
; /* true if the driver is in blkverify mode
66 * Writes are mirrored on two children devices.
67 * On reads the two children devices' contents are
68 * compared and if a difference is spotted its
69 * location is printed and the code aborts.
70 * It is useful to debug other block drivers by
71 * comparing them with a reference one.
75 typedef struct QuorumAIOCB QuorumAIOCB
;
77 /* Quorum will create one instance of the following structure per operation it
78 * performs on its children.
79 * So for each read/write operation coming from the upper layer there will be
80 * $children_count QuorumChildRequest.
82 typedef struct QuorumChildRequest
{
83 BlockDriverAIOCB
*aiocb
;
90 /* Quorum will use the following structure to track progress of each read/write
91 * operation received by the upper layer.
92 * This structure hold pointers to the QuorumChildRequest structures instances
93 * used to do operations on each children and track overall progress.
96 BlockDriverAIOCB common
;
98 /* Request metadata */
102 QEMUIOVector
*qiov
; /* calling IOV */
104 QuorumChildRequest
*qcrs
; /* individual child requests */
105 int count
; /* number of completed AIOCB */
106 int success_count
; /* number of successfully completed AIOCB */
114 static void quorum_vote(QuorumAIOCB
*acb
);
116 static void quorum_aio_cancel(BlockDriverAIOCB
*blockacb
)
118 QuorumAIOCB
*acb
= container_of(blockacb
, QuorumAIOCB
, common
);
119 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
122 /* cancel all callbacks */
123 for (i
= 0; i
< s
->num_children
; i
++) {
124 bdrv_aio_cancel(acb
->qcrs
[i
].aiocb
);
128 qemu_aio_release(acb
);
131 static AIOCBInfo quorum_aiocb_info
= {
132 .aiocb_size
= sizeof(QuorumAIOCB
),
133 .cancel
= quorum_aio_cancel
,
136 static void quorum_aio_finalize(QuorumAIOCB
*acb
)
138 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
145 acb
->common
.cb(acb
->common
.opaque
, ret
);
148 for (i
= 0; i
< s
->num_children
; i
++) {
149 qemu_vfree(acb
->qcrs
[i
].buf
);
150 qemu_iovec_destroy(&acb
->qcrs
[i
].qiov
);
155 qemu_aio_release(acb
);
158 static bool quorum_sha256_compare(QuorumVoteValue
*a
, QuorumVoteValue
*b
)
160 return !memcmp(a
->h
, b
->h
, HASH_LENGTH
);
163 static bool quorum_64bits_compare(QuorumVoteValue
*a
, QuorumVoteValue
*b
)
168 static QuorumAIOCB
*quorum_aio_get(BDRVQuorumState
*s
,
169 BlockDriverState
*bs
,
173 BlockDriverCompletionFunc
*cb
,
176 QuorumAIOCB
*acb
= qemu_aio_get(&quorum_aiocb_info
, bs
, cb
, opaque
);
179 acb
->common
.bs
->opaque
= s
;
180 acb
->sector_num
= sector_num
;
181 acb
->nb_sectors
= nb_sectors
;
183 acb
->qcrs
= g_new0(QuorumChildRequest
, s
->num_children
);
185 acb
->success_count
= 0;
186 acb
->votes
.compare
= quorum_sha256_compare
;
187 QLIST_INIT(&acb
->votes
.vote_list
);
188 acb
->is_read
= false;
191 for (i
= 0; i
< s
->num_children
; i
++) {
192 acb
->qcrs
[i
].buf
= NULL
;
193 acb
->qcrs
[i
].ret
= 0;
194 acb
->qcrs
[i
].parent
= acb
;
200 static void quorum_report_bad(QuorumAIOCB
*acb
, char *node_name
, int ret
)
202 const char *msg
= NULL
;
204 msg
= strerror(-ret
);
206 qapi_event_send_quorum_report_bad(!!msg
, msg
, node_name
,
207 acb
->sector_num
, acb
->nb_sectors
, &error_abort
);
210 static void quorum_report_failure(QuorumAIOCB
*acb
)
212 const char *reference
= acb
->common
.bs
->device_name
[0] ?
213 acb
->common
.bs
->device_name
:
214 acb
->common
.bs
->node_name
;
216 qapi_event_send_quorum_failure(reference
, acb
->sector_num
,
217 acb
->nb_sectors
, &error_abort
);
220 static int quorum_vote_error(QuorumAIOCB
*acb
);
222 static bool quorum_has_too_much_io_failed(QuorumAIOCB
*acb
)
224 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
226 if (acb
->success_count
< s
->threshold
) {
227 acb
->vote_ret
= quorum_vote_error(acb
);
228 quorum_report_failure(acb
);
235 static void quorum_aio_cb(void *opaque
, int ret
)
237 QuorumChildRequest
*sacb
= opaque
;
238 QuorumAIOCB
*acb
= sacb
->parent
;
239 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
244 acb
->success_count
++;
246 quorum_report_bad(acb
, sacb
->aiocb
->bs
->node_name
, ret
);
248 assert(acb
->count
<= s
->num_children
);
249 assert(acb
->success_count
<= s
->num_children
);
250 if (acb
->count
< s
->num_children
) {
254 /* Do the vote on read */
258 quorum_has_too_much_io_failed(acb
);
261 quorum_aio_finalize(acb
);
264 static void quorum_report_bad_versions(BDRVQuorumState
*s
,
266 QuorumVoteValue
*value
)
268 QuorumVoteVersion
*version
;
269 QuorumVoteItem
*item
;
271 QLIST_FOREACH(version
, &acb
->votes
.vote_list
, next
) {
272 if (acb
->votes
.compare(&version
->value
, value
)) {
275 QLIST_FOREACH(item
, &version
->items
, next
) {
276 quorum_report_bad(acb
, s
->bs
[item
->index
]->node_name
, 0);
281 static void quorum_copy_qiov(QEMUIOVector
*dest
, QEMUIOVector
*source
)
284 assert(dest
->niov
== source
->niov
);
285 assert(dest
->size
== source
->size
);
286 for (i
= 0; i
< source
->niov
; i
++) {
287 assert(dest
->iov
[i
].iov_len
== source
->iov
[i
].iov_len
);
288 memcpy(dest
->iov
[i
].iov_base
,
289 source
->iov
[i
].iov_base
,
290 source
->iov
[i
].iov_len
);
294 static void quorum_count_vote(QuorumVotes
*votes
,
295 QuorumVoteValue
*value
,
298 QuorumVoteVersion
*v
= NULL
, *version
= NULL
;
299 QuorumVoteItem
*item
;
301 /* look if we have something with this hash */
302 QLIST_FOREACH(v
, &votes
->vote_list
, next
) {
303 if (votes
->compare(&v
->value
, value
)) {
309 /* It's a version not yet in the list add it */
311 version
= g_new0(QuorumVoteVersion
, 1);
312 QLIST_INIT(&version
->items
);
313 memcpy(&version
->value
, value
, sizeof(version
->value
));
314 version
->index
= index
;
315 version
->vote_count
= 0;
316 QLIST_INSERT_HEAD(&votes
->vote_list
, version
, next
);
319 version
->vote_count
++;
321 item
= g_new0(QuorumVoteItem
, 1);
323 QLIST_INSERT_HEAD(&version
->items
, item
, next
);
326 static void quorum_free_vote_list(QuorumVotes
*votes
)
328 QuorumVoteVersion
*version
, *next_version
;
329 QuorumVoteItem
*item
, *next_item
;
331 QLIST_FOREACH_SAFE(version
, &votes
->vote_list
, next
, next_version
) {
332 QLIST_REMOVE(version
, next
);
333 QLIST_FOREACH_SAFE(item
, &version
->items
, next
, next_item
) {
334 QLIST_REMOVE(item
, next
);
341 static int quorum_compute_hash(QuorumAIOCB
*acb
, int i
, QuorumVoteValue
*hash
)
344 gnutls_hash_hd_t dig
;
345 QEMUIOVector
*qiov
= &acb
->qcrs
[i
].qiov
;
347 ret
= gnutls_hash_init(&dig
, GNUTLS_DIG_SHA256
);
353 for (j
= 0; j
< qiov
->niov
; j
++) {
354 ret
= gnutls_hash(dig
, qiov
->iov
[j
].iov_base
, qiov
->iov
[j
].iov_len
);
360 gnutls_hash_deinit(dig
, (void *) hash
);
364 static QuorumVoteVersion
*quorum_get_vote_winner(QuorumVotes
*votes
)
367 QuorumVoteVersion
*candidate
, *winner
= NULL
;
369 QLIST_FOREACH(candidate
, &votes
->vote_list
, next
) {
370 if (candidate
->vote_count
> max
) {
371 max
= candidate
->vote_count
;
379 /* qemu_iovec_compare is handy for blkverify mode because it returns the first
380 * differing byte location. Yet it is handcoded to compare vectors one byte
381 * after another so it does not benefit from the libc SIMD optimizations.
382 * quorum_iovec_compare is written for speed and should be used in the non
383 * blkverify mode of quorum.
385 static bool quorum_iovec_compare(QEMUIOVector
*a
, QEMUIOVector
*b
)
390 assert(a
->niov
== b
->niov
);
391 for (i
= 0; i
< a
->niov
; i
++) {
392 assert(a
->iov
[i
].iov_len
== b
->iov
[i
].iov_len
);
393 result
= memcmp(a
->iov
[i
].iov_base
,
404 static void GCC_FMT_ATTR(2, 3) quorum_err(QuorumAIOCB
*acb
,
405 const char *fmt
, ...)
410 fprintf(stderr
, "quorum: sector_num=%" PRId64
" nb_sectors=%d ",
411 acb
->sector_num
, acb
->nb_sectors
);
412 vfprintf(stderr
, fmt
, ap
);
413 fprintf(stderr
, "\n");
418 static bool quorum_compare(QuorumAIOCB
*acb
,
422 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
425 /* This driver will replace blkverify in this particular case */
426 if (s
->is_blkverify
) {
427 offset
= qemu_iovec_compare(a
, b
);
429 quorum_err(acb
, "contents mismatch in sector %" PRId64
,
431 (uint64_t)(offset
/ BDRV_SECTOR_SIZE
));
436 return quorum_iovec_compare(a
, b
);
439 /* Do a vote to get the error code */
440 static int quorum_vote_error(QuorumAIOCB
*acb
)
442 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
443 QuorumVoteVersion
*winner
= NULL
;
444 QuorumVotes error_votes
;
445 QuorumVoteValue result_value
;
449 QLIST_INIT(&error_votes
.vote_list
);
450 error_votes
.compare
= quorum_64bits_compare
;
452 for (i
= 0; i
< s
->num_children
; i
++) {
453 ret
= acb
->qcrs
[i
].ret
;
456 result_value
.l
= ret
;
457 quorum_count_vote(&error_votes
, &result_value
, i
);
462 winner
= quorum_get_vote_winner(&error_votes
);
463 ret
= winner
->value
.l
;
466 quorum_free_vote_list(&error_votes
);
471 static void quorum_vote(QuorumAIOCB
*acb
)
475 QuorumVoteValue hash
;
476 BDRVQuorumState
*s
= acb
->common
.bs
->opaque
;
477 QuorumVoteVersion
*winner
;
479 if (quorum_has_too_much_io_failed(acb
)) {
483 /* get the index of the first successful read */
484 for (i
= 0; i
< s
->num_children
; i
++) {
485 if (!acb
->qcrs
[i
].ret
) {
490 assert(i
< s
->num_children
);
492 /* compare this read with all other successful reads stopping at quorum
495 for (j
= i
+ 1; j
< s
->num_children
; j
++) {
496 if (acb
->qcrs
[j
].ret
) {
499 quorum
= quorum_compare(acb
, &acb
->qcrs
[i
].qiov
, &acb
->qcrs
[j
].qiov
);
505 /* Every successful read agrees */
507 quorum_copy_qiov(acb
->qiov
, &acb
->qcrs
[i
].qiov
);
511 /* compute hashes for each successful read, also store indexes */
512 for (i
= 0; i
< s
->num_children
; i
++) {
513 if (acb
->qcrs
[i
].ret
) {
516 ret
= quorum_compute_hash(acb
, i
, &hash
);
517 /* if ever the hash computation failed */
522 quorum_count_vote(&acb
->votes
, &hash
, i
);
525 /* vote to select the most represented version */
526 winner
= quorum_get_vote_winner(&acb
->votes
);
528 /* if the winner count is smaller than threshold the read fails */
529 if (winner
->vote_count
< s
->threshold
) {
530 quorum_report_failure(acb
);
531 acb
->vote_ret
= -EIO
;
535 /* we have a winner: copy it */
536 quorum_copy_qiov(acb
->qiov
, &acb
->qcrs
[winner
->index
].qiov
);
538 /* some versions are bad print them */
539 quorum_report_bad_versions(s
, acb
, &winner
->value
);
543 quorum_free_vote_list(&acb
->votes
);
546 static BlockDriverAIOCB
*quorum_aio_readv(BlockDriverState
*bs
,
550 BlockDriverCompletionFunc
*cb
,
553 BDRVQuorumState
*s
= bs
->opaque
;
554 QuorumAIOCB
*acb
= quorum_aio_get(s
, bs
, qiov
, sector_num
,
555 nb_sectors
, cb
, opaque
);
560 for (i
= 0; i
< s
->num_children
; i
++) {
561 acb
->qcrs
[i
].buf
= qemu_blockalign(s
->bs
[i
], qiov
->size
);
562 qemu_iovec_init(&acb
->qcrs
[i
].qiov
, qiov
->niov
);
563 qemu_iovec_clone(&acb
->qcrs
[i
].qiov
, qiov
, acb
->qcrs
[i
].buf
);
566 for (i
= 0; i
< s
->num_children
; i
++) {
567 bdrv_aio_readv(s
->bs
[i
], sector_num
, &acb
->qcrs
[i
].qiov
, nb_sectors
,
568 quorum_aio_cb
, &acb
->qcrs
[i
]);
574 static BlockDriverAIOCB
*quorum_aio_writev(BlockDriverState
*bs
,
578 BlockDriverCompletionFunc
*cb
,
581 BDRVQuorumState
*s
= bs
->opaque
;
582 QuorumAIOCB
*acb
= quorum_aio_get(s
, bs
, qiov
, sector_num
, nb_sectors
,
586 for (i
= 0; i
< s
->num_children
; i
++) {
587 acb
->qcrs
[i
].aiocb
= bdrv_aio_writev(s
->bs
[i
], sector_num
, qiov
,
588 nb_sectors
, &quorum_aio_cb
,
595 static int64_t quorum_getlength(BlockDriverState
*bs
)
597 BDRVQuorumState
*s
= bs
->opaque
;
601 /* check that all file have the same length */
602 result
= bdrv_getlength(s
->bs
[0]);
606 for (i
= 1; i
< s
->num_children
; i
++) {
607 int64_t value
= bdrv_getlength(s
->bs
[i
]);
611 if (value
!= result
) {
619 static void quorum_invalidate_cache(BlockDriverState
*bs
, Error
**errp
)
621 BDRVQuorumState
*s
= bs
->opaque
;
622 Error
*local_err
= NULL
;
625 for (i
= 0; i
< s
->num_children
; i
++) {
626 bdrv_invalidate_cache(s
->bs
[i
], &local_err
);
628 error_propagate(errp
, local_err
);
634 static coroutine_fn
int quorum_co_flush(BlockDriverState
*bs
)
636 BDRVQuorumState
*s
= bs
->opaque
;
637 QuorumVoteVersion
*winner
= NULL
;
638 QuorumVotes error_votes
;
639 QuorumVoteValue result_value
;
643 QLIST_INIT(&error_votes
.vote_list
);
644 error_votes
.compare
= quorum_64bits_compare
;
646 for (i
= 0; i
< s
->num_children
; i
++) {
647 result
= bdrv_co_flush(s
->bs
[i
]);
648 result_value
.l
= result
;
649 quorum_count_vote(&error_votes
, &result_value
, i
);
652 winner
= quorum_get_vote_winner(&error_votes
);
653 result
= winner
->value
.l
;
655 quorum_free_vote_list(&error_votes
);
660 static bool quorum_recurse_is_first_non_filter(BlockDriverState
*bs
,
661 BlockDriverState
*candidate
)
663 BDRVQuorumState
*s
= bs
->opaque
;
666 for (i
= 0; i
< s
->num_children
; i
++) {
667 bool perm
= bdrv_recurse_is_first_non_filter(s
->bs
[i
],
677 static int quorum_valid_threshold(int threshold
, int num_children
, Error
**errp
)
681 error_set(errp
, QERR_INVALID_PARAMETER_VALUE
,
682 "vote-threshold", "value >= 1");
686 if (threshold
> num_children
) {
687 error_setg(errp
, "threshold may not exceed children count");
694 static QemuOptsList quorum_runtime_opts
= {
696 .head
= QTAILQ_HEAD_INITIALIZER(quorum_runtime_opts
.head
),
699 .name
= QUORUM_OPT_VOTE_THRESHOLD
,
700 .type
= QEMU_OPT_NUMBER
,
701 .help
= "The number of vote needed for reaching quorum",
704 .name
= QUORUM_OPT_BLKVERIFY
,
705 .type
= QEMU_OPT_BOOL
,
706 .help
= "Trigger block verify mode if set",
708 { /* end of list */ }
712 static int quorum_open(BlockDriverState
*bs
, QDict
*options
, int flags
,
715 BDRVQuorumState
*s
= bs
->opaque
;
716 Error
*local_err
= NULL
;
721 const QListEntry
*lentry
;
725 qdict_flatten(options
);
726 qdict_extract_subqdict(options
, &sub
, "children.");
727 qdict_array_split(sub
, &list
);
729 if (qdict_size(sub
)) {
730 error_setg(&local_err
, "Invalid option children.%s",
731 qdict_first(sub
)->key
);
736 /* count how many different children are present */
737 s
->num_children
= qlist_size(list
);
738 if (s
->num_children
< 2) {
739 error_setg(&local_err
,
740 "Number of provided children must be greater than 1");
745 opts
= qemu_opts_create(&quorum_runtime_opts
, NULL
, 0, &error_abort
);
746 qemu_opts_absorb_qdict(opts
, options
, &local_err
);
752 s
->threshold
= qemu_opt_get_number(opts
, QUORUM_OPT_VOTE_THRESHOLD
, 0);
754 /* and validate it against s->num_children */
755 ret
= quorum_valid_threshold(s
->threshold
, s
->num_children
, &local_err
);
760 /* is the driver in blkverify mode */
761 if (qemu_opt_get_bool(opts
, QUORUM_OPT_BLKVERIFY
, false) &&
762 s
->num_children
== 2 && s
->threshold
== 2) {
763 s
->is_blkverify
= true;
764 } else if (qemu_opt_get_bool(opts
, QUORUM_OPT_BLKVERIFY
, false)) {
765 fprintf(stderr
, "blkverify mode is set by setting blkverify=on "
766 "and using two files with vote_threshold=2\n");
769 /* allocate the children BlockDriverState array */
770 s
->bs
= g_new0(BlockDriverState
*, s
->num_children
);
771 opened
= g_new0(bool, s
->num_children
);
773 for (i
= 0, lentry
= qlist_first(list
); lentry
;
774 lentry
= qlist_next(lentry
), i
++) {
778 switch (qobject_type(lentry
->value
))
780 /* List of options */
782 d
= qobject_to_qdict(lentry
->value
);
784 ret
= bdrv_open(&s
->bs
[i
], NULL
, NULL
, d
, flags
, NULL
,
790 string
= qobject_to_qstring(lentry
->value
);
791 ret
= bdrv_open(&s
->bs
[i
], NULL
, qstring_get_str(string
), NULL
,
792 flags
, NULL
, &local_err
);
796 error_setg(&local_err
, "Specification of child block device %i "
811 /* cleanup on error */
812 for (i
= 0; i
< s
->num_children
; i
++) {
816 bdrv_unref(s
->bs
[i
]);
821 /* propagate error */
823 error_propagate(errp
, local_err
);
830 static void quorum_close(BlockDriverState
*bs
)
832 BDRVQuorumState
*s
= bs
->opaque
;
835 for (i
= 0; i
< s
->num_children
; i
++) {
836 bdrv_unref(s
->bs
[i
]);
842 static void quorum_detach_aio_context(BlockDriverState
*bs
)
844 BDRVQuorumState
*s
= bs
->opaque
;
847 for (i
= 0; i
< s
->num_children
; i
++) {
848 bdrv_detach_aio_context(s
->bs
[i
]);
852 static void quorum_attach_aio_context(BlockDriverState
*bs
,
853 AioContext
*new_context
)
855 BDRVQuorumState
*s
= bs
->opaque
;
858 for (i
= 0; i
< s
->num_children
; i
++) {
859 bdrv_attach_aio_context(s
->bs
[i
], new_context
);
863 static BlockDriver bdrv_quorum
= {
864 .format_name
= "quorum",
865 .protocol_name
= "quorum",
867 .instance_size
= sizeof(BDRVQuorumState
),
869 .bdrv_file_open
= quorum_open
,
870 .bdrv_close
= quorum_close
,
872 .bdrv_co_flush_to_disk
= quorum_co_flush
,
874 .bdrv_getlength
= quorum_getlength
,
876 .bdrv_aio_readv
= quorum_aio_readv
,
877 .bdrv_aio_writev
= quorum_aio_writev
,
878 .bdrv_invalidate_cache
= quorum_invalidate_cache
,
880 .bdrv_detach_aio_context
= quorum_detach_aio_context
,
881 .bdrv_attach_aio_context
= quorum_attach_aio_context
,
884 .bdrv_recurse_is_first_non_filter
= quorum_recurse_is_first_non_filter
,
887 static void bdrv_quorum_init(void)
889 bdrv_register(&bdrv_quorum
);
892 block_init(bdrv_quorum_init
);