block/qed-cluster.c

   1 /*
   2  * QEMU Enhanced Disk Format Cluster functions
   3  *
   4  * Copyright IBM, Corp. 2010
   5  *
   6  * Authors:
   7  *  Stefan Hajnoczi   <stefanha@linux.vnet.ibm.com>
   8  *  Anthony Liguori   <aliguori@us.ibm.com>
   9  *
  10  * This work is licensed under the terms of the GNU LGPL, version 2 or later.
  11  * See the COPYING.LIB file in the top-level directory.
  12  *
  13  */
  14
  15 #include "qemu/osdep.h"
  16 #include "qed.h"
  17
  18 /**
  19  * Count the number of contiguous data clusters
  20  *
  21  * @s:              QED state
  22  * @table:          L2 table
  23  * @index:          First cluster index
  24  * @n:              Maximum number of clusters
  25  * @offset:         Set to first cluster offset
  26  *
  27  * This function scans tables for contiguous clusters.  A contiguous run of
  28  * clusters may be allocated, unallocated, or zero.
  29  */
  30 static unsigned int qed_count_contiguous_clusters(BDRVQEDState *s,
  31                                                   QEDTable *table,
  32                                                   unsigned int index,
  33                                                   unsigned int n,
  34                                                   uint64_t *offset)
  35 {
  36     unsigned int end = MIN(index + n, s->table_nelems);
  37     uint64_t last = table->offsets[index];
  38     unsigned int i;
  39
  40     *offset = last;
  41
  42     for (i = index + 1; i < end; i++) {
  43         if (qed_offset_is_unalloc_cluster(last)) {
  44             /* Counting unallocated clusters */
  45             if (!qed_offset_is_unalloc_cluster(table->offsets[i])) {
  46                 break;
  47             }
  48         } else if (qed_offset_is_zero_cluster(last)) {
  49             /* Counting zero clusters */
  50             if (!qed_offset_is_zero_cluster(table->offsets[i])) {
  51                 break;
  52             }
  53         } else {
  54             /* Counting allocated clusters */
  55             if (table->offsets[i] != last + s->header.cluster_size) {
  56                 break;
  57             }
  58             last = table->offsets[i];
  59         }
  60     }
  61     return i - index;
  62 }
  63
  64 /**
  65  * Find the offset of a data cluster
  66  *
  67  * @s:          QED state
  68  * @request:    L2 cache entry
  69  * @pos:        Byte position in device
  70  * @len:        Number of bytes (may be shortened on return)
  71  * @img_offset: Contains offset in the image file on success
  72  *
  73  * This function translates a position in the block device to an offset in the
  74  * image file. The translated offset or unallocated range in the image file is
  75  * reported back in *img_offset and *len.
  76  *
  77  * If the L2 table exists, request->l2_table points to the L2 table cache entry
  78  * and the caller must free the reference when they are finished.  The cache
  79  * entry is exposed in this way to avoid callers having to read the L2 table
  80  * again later during request processing.  If request->l2_table is non-NULL it
  81  * will be unreferenced before taking on the new cache entry.
  82  *
  83  * On success QED_CLUSTER_FOUND is returned and img_offset/len are a contiguous
  84  * range in the image file.
  85  *
  86  * On failure QED_CLUSTER_L2 or QED_CLUSTER_L1 is returned for missing L2 or L1
  87  * table offset, respectively. len is number of contiguous unallocated bytes.
  88  *
  89  * Called with table_lock held.
  90  */
  91 int coroutine_fn qed_find_cluster(BDRVQEDState *s, QEDRequest *request,
  92                                   uint64_t pos, size_t *len,
  93                                   uint64_t *img_offset)
  94 {
  95     uint64_t l2_offset;
  96     uint64_t offset = 0;
  97     unsigned int index;
  98     unsigned int n;
  99     int ret;
 100
 101     /* Limit length to L2 boundary.  Requests are broken up at the L2 boundary
 102      * so that a request acts on one L2 table at a time.
 103      */
 104     *len = MIN(*len, (((pos >> s->l1_shift) + 1) << s->l1_shift) - pos);
 105
 106     l2_offset = s->l1_table->offsets[qed_l1_index(s, pos)];
 107     if (qed_offset_is_unalloc_cluster(l2_offset)) {
 108         *img_offset = 0;
 109         return QED_CLUSTER_L1;
 110     }
 111     if (!qed_check_table_offset(s, l2_offset)) {
 112         *img_offset = *len = 0;
 113         return -EINVAL;
 114     }
 115
 116     ret = qed_read_l2_table(s, request, l2_offset);
 117     if (ret) {
 118         goto out;
 119     }
 120
 121     index = qed_l2_index(s, pos);
 122     n = qed_bytes_to_clusters(s, qed_offset_into_cluster(s, pos) + *len);
 123     n = qed_count_contiguous_clusters(s, request->l2_table->table,
 124                                       index, n, &offset);
 125
 126     if (qed_offset_is_unalloc_cluster(offset)) {
 127         ret = QED_CLUSTER_L2;
 128     } else if (qed_offset_is_zero_cluster(offset)) {
 129         ret = QED_CLUSTER_ZERO;
 130     } else if (qed_check_cluster_offset(s, offset)) {
 131         ret = QED_CLUSTER_FOUND;
 132     } else {
 133         ret = -EINVAL;
 134     }
 135
 136     *len = MIN(*len,
 137                n * s->header.cluster_size - qed_offset_into_cluster(s, pos));
 138
 139 out:
 140     *img_offset = offset;
 141     return ret;
 142 }