From 62f1003e7ae0d6292246f461299988ccaee34926 Mon Sep 17 00:00:00 2001 From: Stefan Hajnoczi Date: Mon, 6 Dec 2010 16:08:01 +0000 Subject: [PATCH] qed: Table, L2 cache, and cluster functions This patch adds code to look up data cluster offsets in the image via the L1/L2 tables. The L2 tables are writethrough cached in memory for performance (each read/write requires a lookup so it is essential to cache the tables). With cluster lookup code in place it is possible to implement bdrv_is_allocated() to query the number of contiguous allocated/unallocated clusters. Signed-off-by: Stefan Hajnoczi Signed-off-by: Kevin Wolf --- Makefile.objs | 2 +- block/qed-cluster.c | 154 +++++++++++++++++++++++++ block/qed-gencb.c | 32 ++++++ block/qed-l2-cache.c | 173 ++++++++++++++++++++++++++++ block/qed-table.c | 319 +++++++++++++++++++++++++++++++++++++++++++++++++++ block/qed.c | 54 ++++++++- block/qed.h | 123 ++++++++++++++++++++ trace-events | 11 ++ 8 files changed, 866 insertions(+), 2 deletions(-) create mode 100644 block/qed-cluster.c create mode 100644 block/qed-gencb.c create mode 100644 block/qed-l2-cache.c create mode 100644 block/qed-table.c diff --git a/Makefile.objs b/Makefile.objs index 50b91e8..1860152 100644 --- a/Makefile.objs +++ b/Makefile.objs @@ -20,7 +20,7 @@ block-obj-$(CONFIG_LINUX_AIO) += linux-aio.o block-nested-y += raw.o cow.o qcow.o vdi.o vmdk.o cloop.o dmg.o bochs.o vpc.o vvfat.o block-nested-y += qcow2.o qcow2-refcount.o qcow2-cluster.o qcow2-snapshot.o -block-nested-y += qed.o +block-nested-y += qed.o qed-gencb.o qed-l2-cache.o qed-table.o qed-cluster.o block-nested-y += parallels.o nbd.o blkdebug.o sheepdog.o blkverify.o block-nested-$(CONFIG_WIN32) += raw-win32.o block-nested-$(CONFIG_POSIX) += raw-posix.o diff --git a/block/qed-cluster.c b/block/qed-cluster.c new file mode 100644 index 0000000..0ec864b --- /dev/null +++ b/block/qed-cluster.c @@ -0,0 +1,154 @@ +/* + * QEMU Enhanced Disk Format Cluster functions + * + * Copyright IBM, Corp. 2010 + * + * Authors: + * Stefan Hajnoczi + * Anthony Liguori + * + * This work is licensed under the terms of the GNU LGPL, version 2 or later. + * See the COPYING.LIB file in the top-level directory. + * + */ + +#include "qed.h" + +/** + * Count the number of contiguous data clusters + * + * @s: QED state + * @table: L2 table + * @index: First cluster index + * @n: Maximum number of clusters + * @offset: Set to first cluster offset + * + * This function scans tables for contiguous allocated or free clusters. + */ +static unsigned int qed_count_contiguous_clusters(BDRVQEDState *s, + QEDTable *table, + unsigned int index, + unsigned int n, + uint64_t *offset) +{ + unsigned int end = MIN(index + n, s->table_nelems); + uint64_t last = table->offsets[index]; + unsigned int i; + + *offset = last; + + for (i = index + 1; i < end; i++) { + if (last == 0) { + /* Counting free clusters */ + if (table->offsets[i] != 0) { + break; + } + } else { + /* Counting allocated clusters */ + if (table->offsets[i] != last + s->header.cluster_size) { + break; + } + last = table->offsets[i]; + } + } + return i - index; +} + +typedef struct { + BDRVQEDState *s; + uint64_t pos; + size_t len; + + QEDRequest *request; + + /* User callback */ + QEDFindClusterFunc *cb; + void *opaque; +} QEDFindClusterCB; + +static void qed_find_cluster_cb(void *opaque, int ret) +{ + QEDFindClusterCB *find_cluster_cb = opaque; + BDRVQEDState *s = find_cluster_cb->s; + QEDRequest *request = find_cluster_cb->request; + uint64_t offset = 0; + size_t len = 0; + unsigned int index; + unsigned int n; + + if (ret) { + goto out; + } + + index = qed_l2_index(s, find_cluster_cb->pos); + n = qed_bytes_to_clusters(s, + qed_offset_into_cluster(s, find_cluster_cb->pos) + + find_cluster_cb->len); + n = qed_count_contiguous_clusters(s, request->l2_table->table, + index, n, &offset); + + ret = offset ? QED_CLUSTER_FOUND : QED_CLUSTER_L2; + len = MIN(find_cluster_cb->len, n * s->header.cluster_size - + qed_offset_into_cluster(s, find_cluster_cb->pos)); + + if (offset && !qed_check_cluster_offset(s, offset)) { + ret = -EINVAL; + } + +out: + find_cluster_cb->cb(find_cluster_cb->opaque, ret, offset, len); + qemu_free(find_cluster_cb); +} + +/** + * Find the offset of a data cluster + * + * @s: QED state + * @request: L2 cache entry + * @pos: Byte position in device + * @len: Number of bytes + * @cb: Completion function + * @opaque: User data for completion function + * + * This function translates a position in the block device to an offset in the + * image file. It invokes the cb completion callback to report back the + * translated offset or unallocated range in the image file. + * + * If the L2 table exists, request->l2_table points to the L2 table cache entry + * and the caller must free the reference when they are finished. The cache + * entry is exposed in this way to avoid callers having to read the L2 table + * again later during request processing. If request->l2_table is non-NULL it + * will be unreferenced before taking on the new cache entry. + */ +void qed_find_cluster(BDRVQEDState *s, QEDRequest *request, uint64_t pos, + size_t len, QEDFindClusterFunc *cb, void *opaque) +{ + QEDFindClusterCB *find_cluster_cb; + uint64_t l2_offset; + + /* Limit length to L2 boundary. Requests are broken up at the L2 boundary + * so that a request acts on one L2 table at a time. + */ + len = MIN(len, (((pos >> s->l1_shift) + 1) << s->l1_shift) - pos); + + l2_offset = s->l1_table->offsets[qed_l1_index(s, pos)]; + if (!l2_offset) { + cb(opaque, QED_CLUSTER_L1, 0, len); + return; + } + if (!qed_check_table_offset(s, l2_offset)) { + cb(opaque, -EINVAL, 0, 0); + return; + } + + find_cluster_cb = qemu_malloc(sizeof(*find_cluster_cb)); + find_cluster_cb->s = s; + find_cluster_cb->pos = pos; + find_cluster_cb->len = len; + find_cluster_cb->cb = cb; + find_cluster_cb->opaque = opaque; + find_cluster_cb->request = request; + + qed_read_l2_table(s, request, l2_offset, + qed_find_cluster_cb, find_cluster_cb); +} diff --git a/block/qed-gencb.c b/block/qed-gencb.c new file mode 100644 index 0000000..1513dc6 --- /dev/null +++ b/block/qed-gencb.c @@ -0,0 +1,32 @@ +/* + * QEMU Enhanced Disk Format + * + * Copyright IBM, Corp. 2010 + * + * Authors: + * Stefan Hajnoczi + * + * This work is licensed under the terms of the GNU LGPL, version 2 or later. + * See the COPYING.LIB file in the top-level directory. + * + */ + +#include "qed.h" + +void *gencb_alloc(size_t len, BlockDriverCompletionFunc *cb, void *opaque) +{ + GenericCB *gencb = qemu_malloc(len); + gencb->cb = cb; + gencb->opaque = opaque; + return gencb; +} + +void gencb_complete(void *opaque, int ret) +{ + GenericCB *gencb = opaque; + BlockDriverCompletionFunc *cb = gencb->cb; + void *user_opaque = gencb->opaque; + + qemu_free(gencb); + cb(user_opaque, ret); +} diff --git a/block/qed-l2-cache.c b/block/qed-l2-cache.c new file mode 100644 index 0000000..57518a4 --- /dev/null +++ b/block/qed-l2-cache.c @@ -0,0 +1,173 @@ +/* + * QEMU Enhanced Disk Format L2 Cache + * + * Copyright IBM, Corp. 2010 + * + * Authors: + * Anthony Liguori + * + * This work is licensed under the terms of the GNU LGPL, version 2 or later. + * See the COPYING.LIB file in the top-level directory. + * + */ + +/* + * L2 table cache usage is as follows: + * + * An open image has one L2 table cache that is used to avoid accessing the + * image file for recently referenced L2 tables. + * + * Cluster offset lookup translates the logical offset within the block device + * to a cluster offset within the image file. This is done by indexing into + * the L1 and L2 tables which store cluster offsets. It is here where the L2 + * table cache serves up recently referenced L2 tables. + * + * If there is a cache miss, that L2 table is read from the image file and + * committed to the cache. Subsequent accesses to that L2 table will be served + * from the cache until the table is evicted from the cache. + * + * L2 tables are also committed to the cache when new L2 tables are allocated + * in the image file. Since the L2 table cache is write-through, the new L2 + * table is first written out to the image file and then committed to the + * cache. + * + * Multiple I/O requests may be using an L2 table cache entry at any given + * time. That means an entry may be in use across several requests and + * reference counting is needed to free the entry at the correct time. In + * particular, an entry evicted from the cache will only be freed once all + * references are dropped. + * + * An in-flight I/O request will hold a reference to a L2 table cache entry for + * the period during which it needs to access the L2 table. This includes + * cluster offset lookup, L2 table allocation, and L2 table update when a new + * data cluster has been allocated. + * + * An interesting case occurs when two requests need to access an L2 table that + * is not in the cache. Since the operation to read the table from the image + * file takes some time to complete, both requests may see a cache miss and + * start reading the L2 table from the image file. The first to finish will + * commit its L2 table into the cache. When the second tries to commit its + * table will be deleted in favor of the existing cache entry. + */ + +#include "trace.h" +#include "qed.h" + +/* Each L2 holds 2GB so this let's us fully cache a 100GB disk */ +#define MAX_L2_CACHE_SIZE 50 + +/** + * Initialize the L2 cache + */ +void qed_init_l2_cache(L2TableCache *l2_cache) +{ + QTAILQ_INIT(&l2_cache->entries); + l2_cache->n_entries = 0; +} + +/** + * Free the L2 cache + */ +void qed_free_l2_cache(L2TableCache *l2_cache) +{ + CachedL2Table *entry, *next_entry; + + QTAILQ_FOREACH_SAFE(entry, &l2_cache->entries, node, next_entry) { + qemu_vfree(entry->table); + qemu_free(entry); + } +} + +/** + * Allocate an uninitialized entry from the cache + * + * The returned entry has a reference count of 1 and is owned by the caller. + * The caller must allocate the actual table field for this entry and it must + * be freeable using qemu_vfree(). + */ +CachedL2Table *qed_alloc_l2_cache_entry(L2TableCache *l2_cache) +{ + CachedL2Table *entry; + + entry = qemu_mallocz(sizeof(*entry)); + entry->ref++; + + trace_qed_alloc_l2_cache_entry(l2_cache, entry); + + return entry; +} + +/** + * Decrease an entry's reference count and free if necessary when the reference + * count drops to zero. + */ +void qed_unref_l2_cache_entry(CachedL2Table *entry) +{ + if (!entry) { + return; + } + + entry->ref--; + trace_qed_unref_l2_cache_entry(entry, entry->ref); + if (entry->ref == 0) { + qemu_vfree(entry->table); + qemu_free(entry); + } +} + +/** + * Find an entry in the L2 cache. This may return NULL and it's up to the + * caller to satisfy the cache miss. + * + * For a cached entry, this function increases the reference count and returns + * the entry. + */ +CachedL2Table *qed_find_l2_cache_entry(L2TableCache *l2_cache, uint64_t offset) +{ + CachedL2Table *entry; + + QTAILQ_FOREACH(entry, &l2_cache->entries, node) { + if (entry->offset == offset) { + trace_qed_find_l2_cache_entry(l2_cache, entry, offset, entry->ref); + entry->ref++; + return entry; + } + } + return NULL; +} + +/** + * Commit an L2 cache entry into the cache. This is meant to be used as part of + * the process to satisfy a cache miss. A caller would allocate an entry which + * is not actually in the L2 cache and then once the entry was valid and + * present on disk, the entry can be committed into the cache. + * + * Since the cache is write-through, it's important that this function is not + * called until the entry is present on disk and the L1 has been updated to + * point to the entry. + * + * N.B. This function steals a reference to the l2_table from the caller so the + * caller must obtain a new reference by issuing a call to + * qed_find_l2_cache_entry(). + */ +void qed_commit_l2_cache_entry(L2TableCache *l2_cache, CachedL2Table *l2_table) +{ + CachedL2Table *entry; + + entry = qed_find_l2_cache_entry(l2_cache, l2_table->offset); + if (entry) { + qed_unref_l2_cache_entry(entry); + qed_unref_l2_cache_entry(l2_table); + return; + } + + if (l2_cache->n_entries >= MAX_L2_CACHE_SIZE) { + entry = QTAILQ_FIRST(&l2_cache->entries); + QTAILQ_REMOVE(&l2_cache->entries, entry, node); + l2_cache->n_entries--; + qed_unref_l2_cache_entry(entry); + } + + l2_cache->n_entries++; + QTAILQ_INSERT_TAIL(&l2_cache->entries, l2_table, node); +} diff --git a/block/qed-table.c b/block/qed-table.c new file mode 100644 index 0000000..d38c673 --- /dev/null +++ b/block/qed-table.c @@ -0,0 +1,319 @@ +/* + * QEMU Enhanced Disk Format Table I/O + * + * Copyright IBM, Corp. 2010 + * + * Authors: + * Stefan Hajnoczi + * Anthony Liguori + * + * This work is licensed under the terms of the GNU LGPL, version 2 or later. + * See the COPYING.LIB file in the top-level directory. + * + */ + +#include "trace.h" +#include "qemu_socket.h" /* for EINPROGRESS on Windows */ +#include "qed.h" + +typedef struct { + GenericCB gencb; + BDRVQEDState *s; + QEDTable *table; + + struct iovec iov; + QEMUIOVector qiov; +} QEDReadTableCB; + +static void qed_read_table_cb(void *opaque, int ret) +{ + QEDReadTableCB *read_table_cb = opaque; + QEDTable *table = read_table_cb->table; + int noffsets = read_table_cb->iov.iov_len / sizeof(uint64_t); + int i; + + /* Handle I/O error */ + if (ret) { + goto out; + } + + /* Byteswap offsets */ + for (i = 0; i < noffsets; i++) { + table->offsets[i] = le64_to_cpu(table->offsets[i]); + } + +out: + /* Completion */ + trace_qed_read_table_cb(read_table_cb->s, read_table_cb->table, ret); + gencb_complete(&read_table_cb->gencb, ret); +} + +static void qed_read_table(BDRVQEDState *s, uint64_t offset, QEDTable *table, + BlockDriverCompletionFunc *cb, void *opaque) +{ + QEDReadTableCB *read_table_cb = gencb_alloc(sizeof(*read_table_cb), + cb, opaque); + QEMUIOVector *qiov = &read_table_cb->qiov; + BlockDriverAIOCB *aiocb; + + trace_qed_read_table(s, offset, table); + + read_table_cb->s = s; + read_table_cb->table = table; + read_table_cb->iov.iov_base = table->offsets, + read_table_cb->iov.iov_len = s->header.cluster_size * s->header.table_size, + + qemu_iovec_init_external(qiov, &read_table_cb->iov, 1); + aiocb = bdrv_aio_readv(s->bs->file, offset / BDRV_SECTOR_SIZE, qiov, + read_table_cb->iov.iov_len / BDRV_SECTOR_SIZE, + qed_read_table_cb, read_table_cb); + if (!aiocb) { + qed_read_table_cb(read_table_cb, -EIO); + } +} + +typedef struct { + GenericCB gencb; + BDRVQEDState *s; + QEDTable *orig_table; + QEDTable *table; + bool flush; /* flush after write? */ + + struct iovec iov; + QEMUIOVector qiov; +} QEDWriteTableCB; + +static void qed_write_table_cb(void *opaque, int ret) +{ + QEDWriteTableCB *write_table_cb = opaque; + + trace_qed_write_table_cb(write_table_cb->s, + write_table_cb->orig_table, + write_table_cb->flush, + ret); + + if (ret) { + goto out; + } + + if (write_table_cb->flush) { + /* We still need to flush first */ + write_table_cb->flush = false; + bdrv_aio_flush(write_table_cb->s->bs, qed_write_table_cb, + write_table_cb); + return; + } + +out: + qemu_vfree(write_table_cb->table); + gencb_complete(&write_table_cb->gencb, ret); + return; +} + +/** + * Write out an updated part or all of a table + * + * @s: QED state + * @offset: Offset of table in image file, in bytes + * @table: Table + * @index: Index of first element + * @n: Number of elements + * @flush: Whether or not to sync to disk + * @cb: Completion function + * @opaque: Argument for completion function + */ +static void qed_write_table(BDRVQEDState *s, uint64_t offset, QEDTable *table, + unsigned int index, unsigned int n, bool flush, + BlockDriverCompletionFunc *cb, void *opaque) +{ + QEDWriteTableCB *write_table_cb; + BlockDriverAIOCB *aiocb; + unsigned int sector_mask = BDRV_SECTOR_SIZE / sizeof(uint64_t) - 1; + unsigned int start, end, i; + size_t len_bytes; + + trace_qed_write_table(s, offset, table, index, n); + + /* Calculate indices of the first and one after last elements */ + start = index & ~sector_mask; + end = (index + n + sector_mask) & ~sector_mask; + + len_bytes = (end - start) * sizeof(uint64_t); + + write_table_cb = gencb_alloc(sizeof(*write_table_cb), cb, opaque); + write_table_cb->s = s; + write_table_cb->orig_table = table; + write_table_cb->flush = flush; + write_table_cb->table = qemu_blockalign(s->bs, len_bytes); + write_table_cb->iov.iov_base = write_table_cb->table->offsets; + write_table_cb->iov.iov_len = len_bytes; + qemu_iovec_init_external(&write_table_cb->qiov, &write_table_cb->iov, 1); + + /* Byteswap table */ + for (i = start; i < end; i++) { + uint64_t le_offset = cpu_to_le64(table->offsets[i]); + write_table_cb->table->offsets[i - start] = le_offset; + } + + /* Adjust for offset into table */ + offset += start * sizeof(uint64_t); + + aiocb = bdrv_aio_writev(s->bs->file, offset / BDRV_SECTOR_SIZE, + &write_table_cb->qiov, + write_table_cb->iov.iov_len / BDRV_SECTOR_SIZE, + qed_write_table_cb, write_table_cb); + if (!aiocb) { + qed_write_table_cb(write_table_cb, -EIO); + } +} + +/** + * Propagate return value from async callback + */ +static void qed_sync_cb(void *opaque, int ret) +{ + *(int *)opaque = ret; +} + +int qed_read_l1_table_sync(BDRVQEDState *s) +{ + int ret = -EINPROGRESS; + + async_context_push(); + + qed_read_table(s, s->header.l1_table_offset, + s->l1_table, qed_sync_cb, &ret); + while (ret == -EINPROGRESS) { + qemu_aio_wait(); + } + + async_context_pop(); + + return ret; +} + +void qed_write_l1_table(BDRVQEDState *s, unsigned int index, unsigned int n, + BlockDriverCompletionFunc *cb, void *opaque) +{ + BLKDBG_EVENT(s->bs->file, BLKDBG_L1_UPDATE); + qed_write_table(s, s->header.l1_table_offset, + s->l1_table, index, n, false, cb, opaque); +} + +int qed_write_l1_table_sync(BDRVQEDState *s, unsigned int index, + unsigned int n) +{ + int ret = -EINPROGRESS; + + async_context_push(); + + qed_write_l1_table(s, index, n, qed_sync_cb, &ret); + while (ret == -EINPROGRESS) { + qemu_aio_wait(); + } + + async_context_pop(); + + return ret; +} + +typedef struct { + GenericCB gencb; + BDRVQEDState *s; + uint64_t l2_offset; + QEDRequest *request; +} QEDReadL2TableCB; + +static void qed_read_l2_table_cb(void *opaque, int ret) +{ + QEDReadL2TableCB *read_l2_table_cb = opaque; + QEDRequest *request = read_l2_table_cb->request; + BDRVQEDState *s = read_l2_table_cb->s; + CachedL2Table *l2_table = request->l2_table; + + if (ret) { + /* can't trust loaded L2 table anymore */ + qed_unref_l2_cache_entry(l2_table); + request->l2_table = NULL; + } else { + l2_table->offset = read_l2_table_cb->l2_offset; + + qed_commit_l2_cache_entry(&s->l2_cache, l2_table); + + /* This is guaranteed to succeed because we just committed the entry + * to the cache. + */ + request->l2_table = qed_find_l2_cache_entry(&s->l2_cache, + l2_table->offset); + assert(request->l2_table != NULL); + } + + gencb_complete(&read_l2_table_cb->gencb, ret); +} + +void qed_read_l2_table(BDRVQEDState *s, QEDRequest *request, uint64_t offset, + BlockDriverCompletionFunc *cb, void *opaque) +{ + QEDReadL2TableCB *read_l2_table_cb; + + qed_unref_l2_cache_entry(request->l2_table); + + /* Check for cached L2 entry */ + request->l2_table = qed_find_l2_cache_entry(&s->l2_cache, offset); + if (request->l2_table) { + cb(opaque, 0); + return; + } + + request->l2_table = qed_alloc_l2_cache_entry(&s->l2_cache); + request->l2_table->table = qed_alloc_table(s); + + read_l2_table_cb = gencb_alloc(sizeof(*read_l2_table_cb), cb, opaque); + read_l2_table_cb->s = s; + read_l2_table_cb->l2_offset = offset; + read_l2_table_cb->request = request; + + BLKDBG_EVENT(s->bs->file, BLKDBG_L2_LOAD); + qed_read_table(s, offset, request->l2_table->table, + qed_read_l2_table_cb, read_l2_table_cb); +} + +int qed_read_l2_table_sync(BDRVQEDState *s, QEDRequest *request, uint64_t offset) +{ + int ret = -EINPROGRESS; + + async_context_push(); + + qed_read_l2_table(s, request, offset, qed_sync_cb, &ret); + while (ret == -EINPROGRESS) { + qemu_aio_wait(); + } + + async_context_pop(); + return ret; +} + +void qed_write_l2_table(BDRVQEDState *s, QEDRequest *request, + unsigned int index, unsigned int n, bool flush, + BlockDriverCompletionFunc *cb, void *opaque) +{ + BLKDBG_EVENT(s->bs->file, BLKDBG_L2_UPDATE); + qed_write_table(s, request->l2_table->offset, + request->l2_table->table, index, n, flush, cb, opaque); +} + +int qed_write_l2_table_sync(BDRVQEDState *s, QEDRequest *request, + unsigned int index, unsigned int n, bool flush) +{ + int ret = -EINPROGRESS; + + async_context_push(); + + qed_write_l2_table(s, request, index, n, flush, qed_sync_cb, &ret); + while (ret == -EINPROGRESS) { + qemu_aio_wait(); + } + + async_context_pop(); + return ret; +} diff --git a/block/qed.c b/block/qed.c index 1436ac4..cd1bead 100644 --- a/block/qed.c +++ b/block/qed.c @@ -155,6 +155,13 @@ static int qed_read_string(BlockDriverState *file, uint64_t offset, size_t n, return 0; } +QEDTable *qed_alloc_table(BDRVQEDState *s) +{ + /* Honor O_DIRECT memory alignment requirements */ + return qemu_blockalign(s->bs, + s->header.cluster_size * s->header.table_size); +} + static int bdrv_qed_open(BlockDriverState *bs, int flags) { BDRVQEDState *s = bs->opaque; @@ -244,11 +251,23 @@ static int bdrv_qed_open(BlockDriverState *bs, int flags) bdrv_flush(bs->file); } + s->l1_table = qed_alloc_table(s); + qed_init_l2_cache(&s->l2_cache); + + ret = qed_read_l1_table_sync(s); + if (ret) { + qed_free_l2_cache(&s->l2_cache); + qemu_vfree(s->l1_table); + } return ret; } static void bdrv_qed_close(BlockDriverState *bs) { + BDRVQEDState *s = bs->opaque; + + qed_free_l2_cache(&s->l2_cache); + qemu_vfree(s->l1_table); } static int bdrv_qed_flush(BlockDriverState *bs) @@ -368,10 +387,43 @@ static int bdrv_qed_create(const char *filename, QEMUOptionParameter *options) backing_file, backing_fmt); } +typedef struct { + int is_allocated; + int *pnum; +} QEDIsAllocatedCB; + +static void qed_is_allocated_cb(void *opaque, int ret, uint64_t offset, size_t len) +{ + QEDIsAllocatedCB *cb = opaque; + *cb->pnum = len / BDRV_SECTOR_SIZE; + cb->is_allocated = ret == QED_CLUSTER_FOUND; +} + static int bdrv_qed_is_allocated(BlockDriverState *bs, int64_t sector_num, int nb_sectors, int *pnum) { - return -ENOTSUP; + BDRVQEDState *s = bs->opaque; + uint64_t pos = (uint64_t)sector_num * BDRV_SECTOR_SIZE; + size_t len = (size_t)nb_sectors * BDRV_SECTOR_SIZE; + QEDIsAllocatedCB cb = { + .is_allocated = -1, + .pnum = pnum, + }; + QEDRequest request = { .l2_table = NULL }; + + async_context_push(); + + qed_find_cluster(s, &request, pos, len, qed_is_allocated_cb, &cb); + + while (cb.is_allocated == -1) { + qemu_aio_wait(); + } + + async_context_pop(); + + qed_unref_l2_cache_entry(request.l2_table); + + return cb.is_allocated; } static int bdrv_qed_make_empty(BlockDriverState *bs) diff --git a/block/qed.h b/block/qed.h index 1f8a125..6d49a4d 100644 --- a/block/qed.h +++ b/block/qed.h @@ -96,16 +96,118 @@ typedef struct { } QEDHeader; typedef struct { + uint64_t offsets[0]; /* in bytes */ +} QEDTable; + +/* The L2 cache is a simple write-through cache for L2 structures */ +typedef struct CachedL2Table { + QEDTable *table; + uint64_t offset; /* offset=0 indicates an invalidate entry */ + QTAILQ_ENTRY(CachedL2Table) node; + int ref; +} CachedL2Table; + +typedef struct { + QTAILQ_HEAD(, CachedL2Table) entries; + unsigned int n_entries; +} L2TableCache; + +typedef struct QEDRequest { + CachedL2Table *l2_table; +} QEDRequest; + +typedef struct { BlockDriverState *bs; /* device */ uint64_t file_size; /* length of image file, in bytes */ QEDHeader header; /* always cpu-endian */ + QEDTable *l1_table; + L2TableCache l2_cache; /* l2 table cache */ uint32_t table_nelems; uint32_t l1_shift; uint32_t l2_shift; uint32_t l2_mask; } BDRVQEDState; +enum { + QED_CLUSTER_FOUND, /* cluster found */ + QED_CLUSTER_L2, /* cluster missing in L2 */ + QED_CLUSTER_L1, /* cluster missing in L1 */ +}; + +/** + * qed_find_cluster() completion callback + * + * @opaque: User data for completion callback + * @ret: QED_CLUSTER_FOUND Success + * QED_CLUSTER_L2 Data cluster unallocated in L2 + * QED_CLUSTER_L1 L2 unallocated in L1 + * -errno POSIX error occurred + * @offset: Data cluster offset + * @len: Contiguous bytes starting from cluster offset + * + * This function is invoked when qed_find_cluster() completes. + * + * On success ret is QED_CLUSTER_FOUND and offset/len are a contiguous range + * in the image file. + * + * On failure ret is QED_CLUSTER_L2 or QED_CLUSTER_L1 for missing L2 or L1 + * table offset, respectively. len is number of contiguous unallocated bytes. + */ +typedef void QEDFindClusterFunc(void *opaque, int ret, uint64_t offset, size_t len); + +/** + * Generic callback for chaining async callbacks + */ +typedef struct { + BlockDriverCompletionFunc *cb; + void *opaque; +} GenericCB; + +void *gencb_alloc(size_t len, BlockDriverCompletionFunc *cb, void *opaque); +void gencb_complete(void *opaque, int ret); + +/** + * L2 cache functions + */ +void qed_init_l2_cache(L2TableCache *l2_cache); +void qed_free_l2_cache(L2TableCache *l2_cache); +CachedL2Table *qed_alloc_l2_cache_entry(L2TableCache *l2_cache); +void qed_unref_l2_cache_entry(CachedL2Table *entry); +CachedL2Table *qed_find_l2_cache_entry(L2TableCache *l2_cache, uint64_t offset); +void qed_commit_l2_cache_entry(L2TableCache *l2_cache, CachedL2Table *l2_table); + +/** + * Table I/O functions + */ +int qed_read_l1_table_sync(BDRVQEDState *s); +void qed_write_l1_table(BDRVQEDState *s, unsigned int index, unsigned int n, + BlockDriverCompletionFunc *cb, void *opaque); +int qed_write_l1_table_sync(BDRVQEDState *s, unsigned int index, + unsigned int n); +int qed_read_l2_table_sync(BDRVQEDState *s, QEDRequest *request, + uint64_t offset); +void qed_read_l2_table(BDRVQEDState *s, QEDRequest *request, uint64_t offset, + BlockDriverCompletionFunc *cb, void *opaque); +void qed_write_l2_table(BDRVQEDState *s, QEDRequest *request, + unsigned int index, unsigned int n, bool flush, + BlockDriverCompletionFunc *cb, void *opaque); +int qed_write_l2_table_sync(BDRVQEDState *s, QEDRequest *request, + unsigned int index, unsigned int n, bool flush); + +/** + * Cluster functions + */ +void qed_find_cluster(BDRVQEDState *s, QEDRequest *request, uint64_t pos, + size_t len, QEDFindClusterFunc *cb, void *opaque); + +/** + * Consistency check + */ +int qed_check(BDRVQEDState *s, BdrvCheckResult *result, bool fix); + +QEDTable *qed_alloc_table(BDRVQEDState *s); + /** * Round down to the start of a cluster */ @@ -114,6 +216,27 @@ static inline uint64_t qed_start_of_cluster(BDRVQEDState *s, uint64_t offset) return offset & ~(uint64_t)(s->header.cluster_size - 1); } +static inline uint64_t qed_offset_into_cluster(BDRVQEDState *s, uint64_t offset) +{ + return offset & (s->header.cluster_size - 1); +} + +static inline unsigned int qed_bytes_to_clusters(BDRVQEDState *s, size_t bytes) +{ + return qed_start_of_cluster(s, bytes + (s->header.cluster_size - 1)) / + (s->header.cluster_size - 1); +} + +static inline unsigned int qed_l1_index(BDRVQEDState *s, uint64_t pos) +{ + return pos >> s->l1_shift; +} + +static inline unsigned int qed_l2_index(BDRVQEDState *s, uint64_t pos) +{ + return (pos >> s->l2_shift) & s->l2_mask; +} + /** * Test if a cluster offset is valid */ diff --git a/trace-events b/trace-events index da03d4b..59f97a2 100644 --- a/trace-events +++ b/trace-events @@ -192,3 +192,14 @@ disable sun4m_iommu_bad_addr(uint64_t addr) "bad addr %"PRIx64"" # vl.c disable vm_state_notify(int running, int reason) "running %d reason %d" + +# block/qed-l2-cache.c +disable qed_alloc_l2_cache_entry(void *l2_cache, void *entry) "l2_cache %p entry %p" +disable qed_unref_l2_cache_entry(void *entry, int ref) "entry %p ref %d" +disable qed_find_l2_cache_entry(void *l2_cache, void *entry, uint64_t offset, int ref) "l2_cache %p entry %p offset %"PRIu64" ref %d" + +# block/qed-table.c +disable qed_read_table(void *s, uint64_t offset, void *table) "s %p offset %"PRIu64" table %p" +disable qed_read_table_cb(void *s, void *table, int ret) "s %p table %p ret %d" +disable qed_write_table(void *s, uint64_t offset, void *table, unsigned int index, unsigned int n) "s %p offset %"PRIu64" table %p index %u n %u" +disable qed_write_table_cb(void *s, void *table, int flush, int ret) "s %p table %p flush %d ret %d" -- 2.7.4