libsparse/backed_block.cpp

/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <assert.h>
#include <errno.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "backed_block.h"
#include "sparse_defs.h"

struct backed_block {
	unsigned int block;
	unsigned int len;
	enum backed_block_type type;
	union {
		struct {
			void *data;
		} data;
		struct {
			char *filename;
			int64_t offset;
		} file;
		struct {
			int fd;
			int64_t offset;
		} fd;
		struct {
			uint32_t val;
		} fill;
	};
	struct backed_block *next;
};

struct backed_block_list {
	struct backed_block *data_blocks;
	struct backed_block *last_used;
	unsigned int block_size;
};

struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
{
	return bbl->data_blocks;
}

struct backed_block *backed_block_iter_next(struct backed_block *bb)
{
	return bb->next;
}

unsigned int backed_block_len(struct backed_block *bb)
{
	return bb->len;
}

unsigned int backed_block_block(struct backed_block *bb)
{
	return bb->block;
}

void *backed_block_data(struct backed_block *bb)
{
	assert(bb->type == BACKED_BLOCK_DATA);
	return bb->data.data;
}

const char *backed_block_filename(struct backed_block *bb)
{
	assert(bb->type == BACKED_BLOCK_FILE);
	return bb->file.filename;
}

int backed_block_fd(struct backed_block *bb)
{
	assert(bb->type == BACKED_BLOCK_FD);
	return bb->fd.fd;
}

int64_t backed_block_file_offset(struct backed_block *bb)
{
	assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD);
	if (bb->type == BACKED_BLOCK_FILE) {
		return bb->file.offset;
	} else { /* bb->type == BACKED_BLOCK_FD */
		return bb->fd.offset;
	}
}

uint32_t backed_block_fill_val(struct backed_block *bb)
{
	assert(bb->type == BACKED_BLOCK_FILL);
	return bb->fill.val;
}

enum backed_block_type backed_block_type(struct backed_block *bb)
{
	return bb->type;
}

void backed_block_destroy(struct backed_block *bb)
{
	if (bb->type == BACKED_BLOCK_FILE) {
		free(bb->file.filename);
	}

	free(bb);
}

struct backed_block_list *backed_block_list_new(unsigned int block_size)
{
	struct backed_block_list *b = reinterpret_cast<backed_block_list*>(
            calloc(sizeof(struct backed_block_list), 1));
	b->block_size = block_size;
	return b;
}

void backed_block_list_destroy(struct backed_block_list *bbl)
{
	if (bbl->data_blocks) {
		struct backed_block *bb = bbl->data_blocks;
		while (bb) {
			struct backed_block *next = bb->next;
			backed_block_destroy(bb);
			bb = next;
		}
	}

	free(bbl);
}

void backed_block_list_move(struct backed_block_list *from,
		struct backed_block_list *to, struct backed_block *start,
		struct backed_block *end)
{
	struct backed_block *bb;

	if (start == NULL) {
		start = from->data_blocks;
	}

	if (!end) {
		for (end = start; end && end->next; end = end->next)
			;
	}

	if (start == NULL || end == NULL) {
		return;
	}

	from->last_used = NULL;
	to->last_used = NULL;
	if (from->data_blocks == start) {
		from->data_blocks = end->next;
	} else {
		for (bb = from->data_blocks; bb; bb = bb->next) {
			if (bb->next == start) {
				bb->next = end->next;
				break;
			}
		}
	}

	if (!to->data_blocks) {
		to->data_blocks = start;
		end->next = NULL;
	} else {
		for (bb = to->data_blocks; bb; bb = bb->next) {
			if (!bb->next || bb->next->block > start->block) {
				end->next = bb->next;
				bb->next = start;
				break;
			}
		}
	}
}

/* may free b */
static int merge_bb(struct backed_block_list *bbl,
		struct backed_block *a, struct backed_block *b)
{
	unsigned int block_len;

	/* Block doesn't exist (possible if one block is the last block) */
	if (!a || !b) {
		return -EINVAL;
	}

	assert(a->block < b->block);

	/* Blocks are of different types */
	if (a->type != b->type) {
		return -EINVAL;
	}

	/* Blocks are not adjacent */
	block_len = a->len / bbl->block_size; /* rounds down */
	if (a->block + block_len != b->block) {
		return -EINVAL;
	}

	switch (a->type) {
	case BACKED_BLOCK_DATA:
		/* Don't support merging data for now */
		return -EINVAL;
	case BACKED_BLOCK_FILL:
		if (a->fill.val != b->fill.val) {
			return -EINVAL;
		}
		break;
	case BACKED_BLOCK_FILE:
		/* Already make sure b->type is BACKED_BLOCK_FILE */
		if (strcmp(a->file.filename, b->file.filename) ||
				a->file.offset + a->len != b->file.offset) {
			return -EINVAL;
		}
		break;
	case BACKED_BLOCK_FD:
		if (a->fd.fd != b->fd.fd ||
				a->fd.offset + a->len != b->fd.offset) {
			return -EINVAL;
		}
		break;
	}

	/* Blocks are compatible and adjacent, with a before b.  Merge b into a,
	 * and free b */
	a->len += b->len;
	a->next = b->next;

	backed_block_destroy(b);

	return 0;
}

static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
{
	struct backed_block *bb;

	if (bbl->data_blocks == NULL) {
		bbl->data_blocks = new_bb;
		return 0;
	}

	if (bbl->data_blocks->block > new_bb->block) {
		new_bb->next = bbl->data_blocks;
		bbl->data_blocks = new_bb;
		return 0;
	}

	/* Optimization: blocks are mostly queued in sequence, so save the
	   pointer to the last bb that was added, and start searching from
	   there if the next block number is higher */
	if (bbl->last_used && new_bb->block > bbl->last_used->block)
		bb = bbl->last_used;
	else
		bb = bbl->data_blocks;
	bbl->last_used = new_bb;

	for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
		;

	if (bb->next == NULL) {
		bb->next = new_bb;
	} else {
		new_bb->next = bb->next;
		bb->next = new_bb;
	}

	merge_bb(bbl, new_bb, new_bb->next);
	if (!merge_bb(bbl, bb, new_bb)) {
		/* new_bb destroyed, point to retained as last_used */
		bbl->last_used = bb;
	}

	return 0;
}

/* Queues a fill block of memory to be written to the specified data blocks */
int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
		unsigned int len, unsigned int block)
{
	struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
	if (bb == NULL) {
		return -ENOMEM;
	}

	bb->block = block;
	bb->len = len;
	bb->type = BACKED_BLOCK_FILL;
	bb->fill.val = fill_val;
	bb->next = NULL;

	return queue_bb(bbl, bb);
}

/* Queues a block of memory to be written to the specified data blocks */
int backed_block_add_data(struct backed_block_list *bbl, void *data,
		unsigned int len, unsigned int block)
{
	struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
	if (bb == NULL) {
		return -ENOMEM;
	}

	bb->block = block;
	bb->len = len;
	bb->type = BACKED_BLOCK_DATA;
	bb->data.data = data;
	bb->next = NULL;

	return queue_bb(bbl, bb);
}

/* Queues a chunk of a file on disk to be written to the specified data blocks */
int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
		int64_t offset, unsigned int len, unsigned int block)
{
	struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
	if (bb == NULL) {
		return -ENOMEM;
	}

	bb->block = block;
	bb->len = len;
	bb->type = BACKED_BLOCK_FILE;
	bb->file.filename = strdup(filename);
	bb->file.offset = offset;
	bb->next = NULL;

	return queue_bb(bbl, bb);
}

/* Queues a chunk of a fd to be written to the specified data blocks */
int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset,
		unsigned int len, unsigned int block)
{
	struct backed_block *bb = reinterpret_cast<backed_block*>(calloc(1, sizeof(struct backed_block)));
	if (bb == NULL) {
		return -ENOMEM;
	}

	bb->block = block;
	bb->len = len;
	bb->type = BACKED_BLOCK_FD;
	bb->fd.fd = fd;
	bb->fd.offset = offset;
	bb->next = NULL;

	return queue_bb(bbl, bb);
}

int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb,
		unsigned int max_len)
{
	struct backed_block *new_bb;

	max_len = ALIGN_DOWN(max_len, bbl->block_size);

	if (bb->len <= max_len) {
		return 0;
	}

	new_bb = reinterpret_cast<backed_block*>(malloc(sizeof(struct backed_block)));
	if (new_bb == NULL) {
		return -ENOMEM;
	}

	*new_bb = *bb;

	new_bb->len = bb->len - max_len;
	new_bb->block = bb->block + max_len / bbl->block_size;
	new_bb->next = bb->next;
	bb->next = new_bb;
	bb->len = max_len;

	switch (bb->type) {
	case BACKED_BLOCK_DATA:
		new_bb->data.data = (char *)bb->data.data + max_len;
		break;
	case BACKED_BLOCK_FILE:
		new_bb->file.offset += max_len;
		break;
	case BACKED_BLOCK_FD:
		new_bb->fd.offset += max_len;
		break;
	case BACKED_BLOCK_FILL:
		break;
	}

	return 0;
}