[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [RFC V7 07/11] quorum: Add quorum mechanism.
From: |
Benoît Canet |
Subject: |
[Qemu-devel] [RFC V7 07/11] quorum: Add quorum mechanism. |
Date: |
Fri, 18 Jan 2013 18:30:40 +0100 |
Use gnutls's SHA-256 to compare versions.
Signed-off-by: Benoit Canet <address@hidden>
---
block/quorum.c | 303 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
configure | 22 ++++
2 files changed, 324 insertions(+), 1 deletion(-)
diff --git a/block/quorum.c b/block/quorum.c
index 7194809..e2b5208 100644
--- a/block/quorum.c
+++ b/block/quorum.c
@@ -13,8 +13,30 @@
* See the COPYING file in the top-level directory.
*/
+#include <gnutls/gnutls.h>
+#include <gnutls/crypto.h>
#include "block/block_int.h"
+#define HASH_LENGTH 32
+
+typedef union QuorumVoteValue {
+ char h[HASH_LENGTH]; /* SHA-256 hash */
+ unsigned long l; /* simpler hash */
+} QuorumVoteValue;
+
+typedef struct QuorumVoteItem {
+ int index;
+ QLIST_ENTRY(QuorumVoteItem) next;
+} QuorumVoteItem;
+
+typedef struct QuorumVoteVersion {
+ QuorumVoteValue value;
+ int index;
+ int vote_count;
+ QLIST_HEAD(, QuorumVoteItem) items;
+ QLIST_ENTRY(QuorumVoteVersion) next;
+} QuorumVoteVersion;
+
typedef struct {
BlockDriverState **bs;
unsigned long long threshold;
@@ -31,6 +53,11 @@ typedef struct QuorumSingleAIOCB {
QuorumAIOCB *parent;
} QuorumSingleAIOCB;
+typedef struct QuorumVotes {
+ QLIST_HEAD(, QuorumVoteVersion) vote_list;
+ int (*compare)(QuorumVoteValue *a, QuorumVoteValue *b);
+} QuorumVotes;
+
struct QuorumAIOCB {
BlockDriverAIOCB common;
BDRVQuorumState *bqs;
@@ -48,6 +75,8 @@ struct QuorumAIOCB {
int success_count; /* number of successfully completed AIOCB */
bool *finished; /* completion signal for cancel */
+ QuorumVotes votes;
+
void (*vote)(QuorumAIOCB *acb);
int vote_ret;
};
@@ -236,6 +265,11 @@ static void quorum_aio_bh(void *opaque)
}
qemu_bh_delete(acb->bh);
+
+ if (acb->vote_ret) {
+ ret = acb->vote_ret;
+ }
+
acb->common.cb(acb->common.opaque, ret);
if (acb->finished) {
*acb->finished = true;
@@ -248,6 +282,11 @@ static void quorum_aio_bh(void *opaque)
qemu_aio_release(acb);
}
+static int quorum_sha256_compare(QuorumVoteValue *a, QuorumVoteValue *b)
+{
+ return memcmp(a, b, HASH_LENGTH);
+}
+
static QuorumAIOCB *quorum_aio_get(BDRVQuorumState *s,
BlockDriverState *bs,
QEMUIOVector *qiov,
@@ -272,6 +311,8 @@ static QuorumAIOCB *quorum_aio_get(BDRVQuorumState *s,
acb->vote = NULL;
acb->vote_ret = 0;
acb->finished = NULL;
+ acb->votes.compare = quorum_sha256_compare;
+ QLIST_INIT(&acb->votes.vote_list);
for (i = 0; i < s->total; i++) {
acb->aios[i].buf = NULL;
@@ -299,10 +340,268 @@ static void quorum_aio_cb(void *opaque, int ret)
return;
}
+ /* Do the vote */
+ if (acb->vote) {
+ acb->vote(acb);
+ }
+
acb->bh = qemu_bh_new(quorum_aio_bh, acb);
qemu_bh_schedule(acb->bh);
}
+static void quorum_print_bad(QuorumAIOCB *acb, const char *filename)
+{
+ fprintf(stderr, "quorum: corrected error in quorum file %s: sector_num=%"
+ PRId64 " nb_sectors=%i\n", filename, acb->sector_num,
+ acb->nb_sectors);
+}
+
+static void quorum_print_failure(QuorumAIOCB *acb)
+{
+ fprintf(stderr, "quorum: failure sector_num=%" PRId64 " nb_sectors=%i\n",
+ acb->sector_num, acb->nb_sectors);
+}
+
+static void quorum_print_bad_versions(QuorumAIOCB *acb,
+ QuorumVoteValue *value)
+{
+ QuorumVoteVersion *version;
+ QuorumVoteItem *item;
+ BDRVQuorumState *s = acb->bqs;
+
+ QLIST_FOREACH(version, &acb->votes.vote_list, next) {
+ if (!acb->votes.compare(&version->value, value)) {
+ continue;
+ }
+ QLIST_FOREACH(item, &version->items, next) {
+ quorum_print_bad(acb, s->filenames[item->index]);
+ }
+ }
+}
+
+static void quorum_copy_qiov(QEMUIOVector *dest, QEMUIOVector *source)
+{
+ int i;
+ assert(dest->niov == source->niov);
+ assert(dest->size == source->size);
+ for (i = 0; i < source->niov; i++) {
+ assert(dest->iov[i].iov_len == source->iov[i].iov_len);
+ memcpy(dest->iov[i].iov_base,
+ source->iov[i].iov_base,
+ source->iov[i].iov_len);
+ }
+}
+
+static void quorum_count_vote(QuorumVotes *votes,
+ QuorumVoteValue *value,
+ int index)
+{
+ QuorumVoteVersion *v = NULL, *version = NULL;
+ QuorumVoteItem *item;
+
+ /* look if we have something with this hash */
+ QLIST_FOREACH(v, &votes->vote_list, next) {
+ if (!votes->compare(&v->value, value)) {
+ version = v;
+ break;
+ }
+ }
+
+ /* It's a version not yet in the list add it */
+ if (!version) {
+ version = g_new0(QuorumVoteVersion, 1);
+ QLIST_INIT(&version->items);
+ memcpy(&version->value, value, sizeof(version->value));
+ version->index = index;
+ version->vote_count = 0;
+ QLIST_INSERT_HEAD(&votes->vote_list, version, next);
+ }
+
+ version->vote_count++;
+
+ item = g_new0(QuorumVoteItem, 1);
+ item->index = index;
+ QLIST_INSERT_HEAD(&version->items, item, next);
+}
+
+static void quorum_free_vote_list(QuorumVotes *votes)
+{
+ QuorumVoteVersion *version, *next_version;
+ QuorumVoteItem *item, *next_item;
+
+ QLIST_FOREACH_SAFE(version, &votes->vote_list, next, next_version) {
+ QLIST_REMOVE(version, next);
+ QLIST_FOREACH_SAFE(item, &version->items, next, next_item) {
+ QLIST_REMOVE(item, next);
+ g_free(item);
+ }
+ g_free(version);
+ }
+}
+
+static int quorum_compute_hash(QuorumAIOCB *acb, int i, QuorumVoteValue *hash)
+{
+ int j, ret;
+ gnutls_hash_hd_t dig;
+ QEMUIOVector *qiov = &acb->qiovs[i];
+
+ ret = gnutls_hash_init(&dig, GNUTLS_DIG_SHA256);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ for (j = 0; j < qiov->niov; j++) {
+ ret = gnutls_hash(dig, qiov->iov[j].iov_base, qiov->iov[j].iov_len);
+ if (ret < 0) {
+ return ret;
+ }
+ }
+
+ gnutls_hash_deinit(dig, (void *) hash);
+
+ return 0;
+}
+
+static QuorumVoteVersion *quorum_get_vote_winner(QuorumVotes *votes)
+{
+ int i = 0;
+ QuorumVoteVersion *candidate, *winner = NULL;
+
+ QLIST_FOREACH(candidate, &votes->vote_list, next) {
+ if (candidate->vote_count > i) {
+ i = candidate->vote_count;
+ winner = candidate;
+ }
+ }
+
+ return winner;
+}
+
+static bool quorum_iovec_compare(QEMUIOVector *a, QEMUIOVector *b)
+{
+ int i;
+ int result;
+
+ assert(a->niov == b->niov);
+ for (i = 0; i < a->niov; i++) {
+ assert(a->iov[i].iov_len == b->iov[i].iov_len);
+ result = memcmp(a->iov[i].iov_base,
+ b->iov[i].iov_base,
+ a->iov[i].iov_len);
+ if (result) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+static void GCC_FMT_ATTR(2, 3) quorum_err(QuorumAIOCB *acb,
+ const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ fprintf(stderr, "quorum: sector_num=%" PRId64 " nb_sectors=%d ",
+ acb->sector_num, acb->nb_sectors);
+ vfprintf(stderr, fmt, ap);
+ fprintf(stderr, "\n");
+ va_end(ap);
+ exit(1);
+}
+
+static bool quorum_compare(QuorumAIOCB *acb,
+ QEMUIOVector *a,
+ QEMUIOVector *b)
+{
+ BDRVQuorumState *s = acb->bqs;
+ bool blkverify = false;
+ ssize_t offset;
+
+ if (s->total == 2 && s->threshold == 2) {
+ blkverify = true;
+ }
+
+ if (blkverify) {
+ offset = qemu_iovec_compare(a, b);
+ if (offset != -1) {
+ quorum_err(acb, "contents mismatch in sector %" PRId64,
+ acb->sector_num +
+ (uint64_t)(offset / BDRV_SECTOR_SIZE));
+ }
+ return true;
+ }
+
+ return quorum_iovec_compare(a, b);
+}
+
+
+static void quorum_vote(QuorumAIOCB *acb)
+{
+ bool quorum = true;
+ int i, j, ret;
+ QuorumVoteValue hash;
+ BDRVQuorumState *s = acb->bqs;
+ QuorumVoteVersion *winner;
+
+ /* get the index of the first successful read */
+ for (i = 0; i < s->total; i++) {
+ if (!acb->aios[i].ret) {
+ break;
+ }
+ }
+
+ /* compare this read with all other successful read looking for quorum */
+ for (j = i + 1; j < s->total; j++) {
+ if (acb->aios[j].ret) {
+ continue;
+ }
+ quorum = quorum_compare(acb, &acb->qiovs[i], &acb->qiovs[j]);
+ if (!quorum) {
+ break;
+ }
+ }
+
+ /* Every successful read agrees -> Quorum */
+ if (quorum) {
+ quorum_copy_qiov(acb->qiov, &acb->qiovs[i]);
+ return;
+ }
+
+ /* compute hashs for each successful read, also store indexes */
+ for (i = 0; i < s->total; i++) {
+ if (acb->aios[i].ret) {
+ continue;
+ }
+ ret = quorum_compute_hash(acb, i, &hash);
+ assert(ret == 0);
+ quorum_count_vote(&acb->votes, &hash, i);
+ }
+
+ /* vote to select the most represented version */
+ winner = quorum_get_vote_winner(&acb->votes);
+ assert(winner != NULL);
+
+ /* if the winner count is smaller than threshold read fail */
+ if (winner->vote_count < s->threshold) {
+ quorum_print_failure(acb);
+ acb->vote_ret = -EIO;
+ fprintf(stderr, "quorum: vote result inferior to threshold\n");
+ goto free_exit;
+ }
+
+ /* we have a winner: copy it */
+ quorum_copy_qiov(acb->qiov, &acb->qiovs[winner->index]);
+
+ /* some versions are bad print them */
+ quorum_print_bad_versions(acb, &winner->value);
+
+free_exit:
+ /* free lists */
+ quorum_free_vote_list(&acb->votes);
+}
+
static BlockDriverAIOCB *quorum_aio_readv(BlockDriverState *bs,
int64_t sector_num,
QEMUIOVector *qiov,
@@ -315,6 +614,8 @@ static BlockDriverAIOCB *quorum_aio_readv(BlockDriverState
*bs,
nb_sectors, cb, opaque);
int i;
+ acb->vote = quorum_vote;
+
for (i = 0; i < s->total; i++) {
acb->aios[i].buf = qemu_blockalign(bs->file, qiov->size);
qemu_iovec_init(&acb->qiovs[i], qiov->niov);
@@ -322,7 +623,7 @@ static BlockDriverAIOCB *quorum_aio_readv(BlockDriverState
*bs,
}
for (i = 0; i < s->total; i++) {
- bdrv_aio_readv(s->bs[i], sector_num, qiov, nb_sectors,
+ bdrv_aio_readv(s->bs[i], sector_num, &acb->qiovs[i], nb_sectors,
quorum_aio_cb, &acb->aios[i]);
}
diff --git a/configure b/configure
index 4ebb60d..0832d26 100755
--- a/configure
+++ b/configure
@@ -1733,6 +1733,28 @@ EOF
fi
##########################################
+# Quorum gnutls detection
+cat > $TMPC <<EOF
+#include <gnutls/gnutls.h>
+#include <gnutls/crypto.h>
+int main(void) {char data[4096], digest[32];
+gnutls_hash_fast(GNUTLS_DIG_SHA256, data, 4096, digest);
+return 0;
+}
+EOF
+qcow_tls_cflags=`$pkg_config --cflags gnutls 2> /dev/null`
+qcow_tls_libs=`$pkg_config --libs gnutls 2> /dev/null`
+if compile_prog "$qcow_tls_cflags" "$qcow_tls_libs" ; then
+ qcow_tls=yes
+ libs_softmmu="$qcow_tls_libs $libs_softmmu"
+ libs_tools="$qcow_tls_libs $libs_softmmu"
+ QEMU_CFLAGS="$QEMU_CFLAGS $qcow_tls_cflags"
+else
+ echo "gnutls > 2.10.0 required to compile QEMU"
+ exit 1
+fi
+
+##########################################
# VNC SASL detection
if test "$vnc" = "yes" -a "$vnc_sasl" != "no" ; then
cat > $TMPC <<EOF
--
1.7.10.4
- [Qemu-devel] [RFC V7 02/11] quorum: Create BDRVQuorumState and BlkDriver and do init., (continued)
- [Qemu-devel] [RFC V7 02/11] quorum: Create BDRVQuorumState and BlkDriver and do init., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 01/11] quorum: Create quorum .c, add QuorumSingleAIOCB and QuorumAIOCB., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 04/11] quorum: Add quorum_aio_writev and its dependencies., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 03/11] quorum: Add quorum_open() and quorum_close()., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 06/11] quorum: Add quorum_aio_readv., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 05/11] blkverify: Extract qemu_iovec_clone() and qemu_iovec_compare() from blkverify., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 08/11] quorum: Add quorum_getlength()., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 09/11] quorum: Add quorum_invalidate_cache()., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 10/11] quorum: Add quorum_co_is_allocated., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 11/11] quorum: Add quorum_co_flush()., Benoît Canet, 2013/01/18
- [Qemu-devel] [RFC V7 07/11] quorum: Add quorum mechanism.,
Benoît Canet <=
- Re: [Qemu-devel] [RFC V7 00/11] Quorum block filter, Zhi Yong Wu, 2013/01/21