Read QCow2 file using C (data recovery part 3)

28 Nov 2020
#Virtualization#Linux#Qemu#Programming#C

Time to write some code but I will not go into all the details on how to write C code. I will only reference some of the C code specific to reading the actual QCow2 file.

  1. Failed at backup…
  2. QCow2 file format

Big endian/Little endian

Before we start reading anything in our QCow2 file we should know that data is stored in big endian format. All x86 based machines are little endian, so we need to convert the endianess when we read data. The actual data clusters does not need to be changed (assuming your host and guest are x86 machines).

I am using the __be32_to_cpu & __be64_to_cpu functions found in <asm/byteorder.h> to convert from big endian to the CPU endian, so I suppose this would compile and run fine on a big endian machine as well.

Open file

The file will be opened in binary mode and the first step after this has been done is to read and verify the QCow2 header data and calculate some extra meta data.

Verify file header and calculate some meta data

As I wrote earlier the first cluster is dedicated for header data. But the actual header is a lot smaller than a cluster in size.

This is the C struct for the header data

#define QCOW2_MAGIC (('Q' << 24) | ('F' << 16) | ('I' << 8) | 0xfb)

typedef struct QCow2Header {
  uint32_t magic;
  uint32_t version;

  uint64_t backing_file_offset;
  uint32_t backing_file_size;

  uint32_t cluster_bits;
  uint64_t size;                 /* file size in bytes */
  uint32_t crypt_method;

  uint32_t l1_size;
  uint64_t l1_table_offset;

  uint64_t refcount_table_offset;
  uint32_t refcount_table_clusters;

  uint32_t nb_snapshots;
  uint64_t snapshots_offset;

  /* Version >= 3 extended header */
  uint64_t incompatible_features;
  uint64_t compatible_features;
  uint64_t autoclear_features;

  uint32_t refcount_order;
  uint32_t header_length;

  uint8_t compression_type;

  /* padding to make header multiple of 8 */
  uint8_t padding[7];
} QCow2Header;

This makes it easy to just fread it, super convenient. After reading the header block we need to convert everything from big endian to CPU endian.

void qcow2_readHeader(FILE *fp, QCow2Header *header) {
  fread(header, sizeof(QCow2Header), 1, fp);
  
    // convert from big endian to CPU endian
  header->magic                   = __be32_to_cpu(header->magic);
  header->version                 = __be32_to_cpu(header->version);
  header->backing_file_offset     = __be64_to_cpu(header->backing_file_offset);
  header->backing_file_size       = __be32_to_cpu(header->backing_file_size);
  header->cluster_bits            = __be32_to_cpu(header->cluster_bits);
  header->size                    = __be64_to_cpu(header->size);
  header->crypt_method            = __be32_to_cpu(header->crypt_method);
  header->l1_size                 = __be32_to_cpu(header->l1_size);
  header->l1_table_offset         = __be64_to_cpu(header->l1_table_offset);
  header->refcount_table_offset   = __be64_to_cpu(header->refcount_table_offset);
  header->refcount_table_clusters = __be32_to_cpu(header->refcount_table_clusters);
  header->nb_snapshots            = __be32_to_cpu(header->nb_snapshots);
  header->snapshots_offset        = __be64_to_cpu(header->snapshots_offset);
}

Now when the header has been read and the data is endian converted. We can verify the header magic and version to make sure it is a QCow2 file.

  if( header->magic != QCOW2_MAGIC ) {
    printf("Error loading file, bad header.\n");
    return 1;
  }
  if( header->version < 2 || header->version > 3 ) {
    printf("Unsupported QCow2 version %" PRIu32 "\n", header->version);
    return 1;
  }

Calculate Cluster size

cluster_size = 1 << cluster_bits; // equals 1 * 2^cluster_bits

By default cluster_bits is 16, and this will shift bit 1 to the left 16 times. This would be the same as 2^16 and the result is 65536. And as a coincident the default cluster_size is 65536.

Calculate L2 Entry size & number of entreis

/* Size of normal and extended L2 entries */
#define L2E_SIZE_NORMAL   (sizeof(uint64_t))
#define L2E_SIZE_EXTENDED (sizeof(uint64_t) * 2)

/* Incompatible feature bits */
#define QCOW2_INCOMPAT_EXTL2 1 << 4

if( header->incompatible_features & QCOW2_INCOMPAT_EXTL2 ) {
 l2_entry_size = L2E_EXTENDED_SIZE;
else
 l2_entry_size = L2E_SIZE_NORMAL;
 
 l2_size = header->cluster_size / l2_entry_size;

By default one L2 entry is one 64 bit value, 8 bytes. But if bit 4 flag is set in the incompatible_features one L2 entry is 2x64 bit value, 16 bytes.

The number of entries in one L2 cluster is cluster_size / l2_entry_size with the default cluster_size of 65k and l2_entry_size of 8 bytes allows for 8192 L2 entries in one L2 cluster.

Calculate L2 bits

Now when we now the L2 entry size we can calculate how many bits is needed to represent one L2 index, by default 8192 entries (0-8191). So how can we calculate how many bits is needed for the maximum value of 8191?

Well if you know your binary, you may recognize that 8192 is exacatly one bit of it. If you set bit 14 you will get 8192 (10 0000 0000 0000). This means if we would type 8191 in binary it would be 13 ones (1 1111 1111 1111). If you didn’t notice, but all the zeros in the first binary number are now ones and the one is a zero. This is great because there is a function that will count trailing zeros on a binary number

l2_bits = __builtin_ctz(l2_entries);

Read L1 table

Before we start reading data from the QCow2 file we need the L1 table. This is just a simple fread because everything we need is in the header

fseek(fp, header->l1_table_offset, SEEK_SET);
fread(l1_table, header->l1_size, 1, fp);

Read data in QCow2 file

Finally we are ready to actually start reading some data from the QCow2 file. But there are some limits, when you read data from a QCow2 file you can only read a contigious chunks of  data that is less than cluster_size - *offset_in_cluster. *If offset_in_cluster is 64k and cluster_size is 65k you can only read 1Kb of data from this cluster. If you need more data you need to continue to read another chunk in another cluster.

To read more data than one cluster_size it would be something like this:

int qcow2_read(uint64_t offset, uint64_t bytes, char *buf) {
  int bytes_read = 0;
  do {
    bytes_read = qcow2_readChunk(offset, bytes, buf);
    bytes -= bytes_read;
    offset += bytes_read;
    buf += bytes_read;
  } while(bytes > 0);
}

To read one chunk of data you need to:

  1. Calculate L1_index
  2. Retrive the L2_offset from the L1 table
  3. Calculate the L2_index
  4. Load the L2 table
  5. Retrive the data cluster_offset from the L2 table
  6. Calculate the offset_in_cluster
  7. Calculate num_bytes you can read for this chunk at the current offset in cluster
  8. Read num_bytes from cluster_offset + offset_in_cluster in the QCow2 file
  9. If num_bytes is less than you need, repeat the process with the new offset = offset + num_bytes

Calculate the L1 index

The L1 index is the top part of the guest offset, so if we remove the cluster bits and l2_bits. This can easily be done by shifting the offset to the right l2_bits + cluster_bits.

l1_index = offset >> (l2_bits + cluster_bits);

Retrive the L2 offset from the L1 table

Because L1 table entries only use bits 9-55 we use a mask operator to and the entry with. This will remove all unwanted bits from the L1 entry.

#define L1_OFFSET_MASK 0x00ffffffffffff00ULL // L1 Offset only use bits 9-55

l2_offset = l1_table[l1_index] & L1_OFFSET_MASK;

If L2_offset is 0 there is no data for the current offset stored in this file. Either because the data is stored in the backing file or beacuse no data has been written to this location.

For my data recovery purpose I just pretend I could read only 1 byte and that was a 0.

Load the L2 table

We just got the *l2_offset *so now we know where it is in the QCow2 file.

uint64_t *l2_table = malloc(cluster_size); // Remember to free() it, or cache it for later use
fseek(fp, l2_offset, SEEK_SET);
fread(l2_table, cluster_size, 1, fp);

Calculate the L2 index

This is similar to calculating the L1 index, but now we want the middle part. So we remove the cluster_bits part and use a bit mask to extract the bits we want

l2_index = (offset >> cluster_bits) & (l2_size - 1);

Retrive the data cluster offset from the L2 table

Once again pretty similar to what we already have done when we retrived the L2 offset. This time we want bits 0-61, so another bit mask is used.

#define L2_OFFSET_MASK 0x3fffffffffffffffULL // L2 Offset use bits 0-61

cluster_offset = l2_table[l2_index] & L2_OFFSET_MASK;

If cluster_offset is 0 there is no data for the current offset stored in this file. Either because the data is stored in the backing file or beacuse no data has been written to this location.

For my data recovery purpose I just pretend I could read only 1 byte and that was a 0.

Calculate the offset_in_cluster

To find out how far into an cluster our data is, we need the lower parts of the offset and as before we use a bit mask to remove the unwanted bits. This time we don’t need to shift anything because we want the lowest bits.

offset_in_cluster = offset & (cluster_size - 1)

Calculate num_bytes you can read for this chunk at the current offset

We know the maximum size of one cluster is cluster_size and we know that the data is located at offset_in_cluster so then we can calculate how many bytes we can read. But if the actual amount of bytes we want is less, we only need to read what we need.

int num_bytes = cluster_size - offset_in_cluster;
num_bytes = (bytes < num_bytes) ? bytes : num_bytes;

Finally read the data

char *data = malloc(num_bytes);
fseek(fp, cluster_offset, SEEK_SET);
fread(data, num_bytes, 1, fp);

To sum it all up, the qcow2_readChunk would be something like this:

#define L1_OFFSET_MASK 0x00ffffffffffff00ULL // L1 Offset only use bits 9-55
#define L2_OFFSET_MASK 0x3fffffffffffffffULL // L2 Offset use bits 0-61

// Previously calculated variables needed
uint16_t l2_bits;
uint32_t cluster_bits;
uint64_t *l1_table;
uint16_t l2_size;
uint32_t cluster_size;
FILE *fp;

int qcow2_readChunk(uint64_t offset, uint64_t bytes, char *buf) {
  uint64_t l1_index = offset >> (l2_bits + cluster_bits);
  uint64_t l2_offset = l1_table[l1_index] & L1_OFFSET_MASK;
  uint16_t l2_index = (offset >> cluster_bits) & (l2_size - 1);
  
  if( l2_offset == 0 ) {
    // There is no data stored at this location, pretend we found a 0
     buf[0] = 0;
    return 1;
  }
  
  uint64_t *l2_table = malloc(cluster_size);
  fseek(fp, l2_offset, SEEK_SET);
  fread(l2_table, cluster_size, 1, fp);
  
  uint64_t cluster_offset = l2_table[l2_index] & L2_OFFSET_MASK;
  
  free(l2_table);
  
  if( cluster_offset == 0) {
    // There is no data stored at this location, pretend we found a 0
    buf[0] = 0;
    return 1;
   }
  
  uint16_t offset_in_cluster = offset & (cluster_size - 1);
  
  int num_bytes = cluster_size - offset_in_cluster;
  num_bytes = (bytes < num_bytes) ? bytes : num_bytes;
  
  fseek(fp, cluster_offset, SEEK_SET);
  fread(buf, num_bytes, 1, fp);
}

Source Code

You can find the source code for my read_qcow2 project over at Github: https://github.com/Raddinox/read_qcow2

Up next is data recovery time

Now we can read data from the QCow2 file and this means we can create an IMG file.

Restore data from QCow2 missing backing file (data recovery part 4)

Raddinox © 2024 - Powered by