libsparse/sparse.c - android-core - Git at Google

 /*
  * Copyright (C) 2012 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 <stdlib.h>

 #include <sparse/sparse.h>

 #include "defs.h"
 #include "sparse_file.h"

 #include "output_file.h"
 #include "backed_block.h"
 #include "sparse_defs.h"
 #include "sparse_format.h"

 struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len)
 {
 	struct sparse_file *s = calloc(sizeof(struct sparse_file), 1);
 	if (!s) {
 		return NULL;
 	}

 	s->backed_block_list = backed_block_list_new(block_size);
 	if (!s->backed_block_list) {
 		free(s);
 		return NULL;
 	}

 	s->block_size = block_size;
 	s->len = len;

 	return s;
 }

 void sparse_file_destroy(struct sparse_file *s)
 {
 	backed_block_list_destroy(s->backed_block_list);
 	free(s);
 }

 int sparse_file_add_data(struct sparse_file *s,
 		void *data, unsigned int len, unsigned int block)
 {
 	return backed_block_add_data(s->backed_block_list, data, len, block);
 }

 int sparse_file_add_fill(struct sparse_file *s,
 		uint32_t fill_val, unsigned int len, unsigned int block)
 {
 	return backed_block_add_fill(s->backed_block_list, fill_val, len, block);
 }

 int sparse_file_add_file(struct sparse_file *s,
 		const char *filename, int64_t file_offset, unsigned int len,
 		unsigned int block)
 {
 	return backed_block_add_file(s->backed_block_list, filename, file_offset,
 			len, block);
 }

 int sparse_file_add_fd(struct sparse_file *s,
 		int fd, int64_t file_offset, unsigned int len, unsigned int block)
 {
 	return backed_block_add_fd(s->backed_block_list, fd, file_offset,
 			len, block);
 }
 unsigned int sparse_count_chunks(struct sparse_file *s)
 {
 	struct backed_block *bb;
 	unsigned int last_block = 0;
 	unsigned int chunks = 0;

 	for (bb = backed_block_iter_new(s->backed_block_list); bb;
 			bb = backed_block_iter_next(bb)) {
 		if (backed_block_block(bb) > last_block) {
 			/* If there is a gap between chunks, add a skip chunk */
 			chunks++;
 		}
 		chunks++;
 		last_block = backed_block_block(bb) +
 				DIV_ROUND_UP(backed_block_len(bb), s->block_size);
 	}
 	if (last_block < DIV_ROUND_UP(s->len, s->block_size)) {
 		chunks++;
 	}

 	return chunks;
 }

 static int sparse_file_write_block(struct output_file *out,
 		struct backed_block *bb)
 {
 	int ret = -EINVAL;

 	switch (backed_block_type(bb)) {
 	case BACKED_BLOCK_DATA:
 		ret = write_data_chunk(out, backed_block_len(bb), backed_block_data(bb));
 		break;
 	case BACKED_BLOCK_FILE:
 		ret = write_file_chunk(out, backed_block_len(bb),
 				       backed_block_filename(bb),
 				       backed_block_file_offset(bb));
 		break;
 	case BACKED_BLOCK_FD:
 		ret = write_fd_chunk(out, backed_block_len(bb),
 				     backed_block_fd(bb),
 				     backed_block_file_offset(bb));
 		break;
 	case BACKED_BLOCK_FILL:
 		ret = write_fill_chunk(out, backed_block_len(bb),
 				       backed_block_fill_val(bb));
 		break;
 	}

 	return ret;
 }

 static int write_all_blocks(struct sparse_file *s, struct output_file *out)
 {
 	struct backed_block *bb;
 	unsigned int last_block = 0;
 	int64_t pad;
 	int ret = 0;

 	for (bb = backed_block_iter_new(s->backed_block_list); bb;
 			bb = backed_block_iter_next(bb)) {
 		if (backed_block_block(bb) > last_block) {
 			unsigned int blocks = backed_block_block(bb) - last_block;
 			write_skip_chunk(out, (int64_t)blocks * s->block_size);
 		}
 		ret = sparse_file_write_block(out, bb);
 		if (ret)
 			return ret;
 		last_block = backed_block_block(bb) +
 				DIV_ROUND_UP(backed_block_len(bb), s->block_size);
 	}

 	pad = s->len - (int64_t)last_block * s->block_size;
 	assert(pad >= 0);
 	if (pad > 0) {
 		write_skip_chunk(out, pad);
 	}

 	return 0;
 }

 int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
 		bool crc)
 {
 	int ret;
 	int chunks;
 	struct output_file *out;

 	chunks = sparse_count_chunks(s);
 	out = output_file_open_fd(fd, s->block_size, s->len, gz, sparse, chunks, crc);

 	if (!out)
 		return -ENOMEM;

 	ret = write_all_blocks(s, out);

 	output_file_close(out);

 	return ret;
 }

 int sparse_file_callback(struct sparse_file *s, bool sparse, bool crc,
 		int (*write)(void *priv, const void *data, int len), void *priv)
 {
 	int ret;
 	int chunks;
 	struct output_file *out;

 	chunks = sparse_count_chunks(s);
 	out = output_file_open_callback(write, priv, s->block_size, s->len, false,
 			sparse, chunks, crc);

 	if (!out)
 		return -ENOMEM;

 	ret = write_all_blocks(s, out);

 	output_file_close(out);

 	return ret;
 }

 struct chunk_data {
 	void		*priv;
 	unsigned int	block;
 	unsigned int	nr_blocks;
 	int (*write)(void *priv, const void *data, int len, unsigned int block,
 		     unsigned int nr_blocks);
 };

 static int foreach_chunk_write(void *priv, const void *data, int len)
 {
 	struct chunk_data *chk = priv;

 	return chk->write(chk->priv, data, len, chk->block, chk->nr_blocks);
 }

 int sparse_file_foreach_chunk(struct sparse_file *s, bool sparse, bool crc,
 	int (*write)(void *priv, const void *data, int len, unsigned int block,
 		     unsigned int nr_blocks),
 	void *priv)
 {
 	int ret;
 	int chunks;
 	struct chunk_data chk;
 	struct output_file *out;
 	struct backed_block *bb;

 	chk.priv = priv;
 	chk.write = write;
 	chk.block = chk.nr_blocks = 0;
 	chunks = sparse_count_chunks(s);
 	out = output_file_open_callback(foreach_chunk_write, &chk,
 					s->block_size, s->len, false, sparse,
 					chunks, crc);

 	if (!out)
 		return -ENOMEM;

 	for (bb = backed_block_iter_new(s->backed_block_list); bb;
 			bb = backed_block_iter_next(bb)) {
 		chk.block = backed_block_block(bb);
 		chk.nr_blocks = (backed_block_len(bb) - 1) / s->block_size + 1;
 		ret = sparse_file_write_block(out, bb);
 		if (ret)
 			return ret;
 	}

 	output_file_close(out);

 	return ret;
 }

 static int out_counter_write(void *priv, const void *data __unused, int len)
 {
 	int64_t *count = priv;
 	*count += len;
 	return 0;
 }

 int64_t sparse_file_len(struct sparse_file *s, bool sparse, bool crc)
 {
 	int ret;
 	int chunks = sparse_count_chunks(s);
 	int64_t count = 0;
 	struct output_file *out;

 	out = output_file_open_callback(out_counter_write, &count,
 			s->block_size, s->len, false, sparse, chunks, crc);
 	if (!out) {
 		return -1;
 	}

 	ret = write_all_blocks(s, out);

 	output_file_close(out);

 	if (ret < 0) {
 		return -1;
 	}

 	return count;
 }

 unsigned int sparse_file_block_size(struct sparse_file *s)
 {
 	return s->block_size;
 }

 static struct backed_block *move_chunks_up_to_len(struct sparse_file *from,
 		struct sparse_file *to, unsigned int len)
 {
 	int64_t count = 0;
 	struct output_file *out_counter;
 	struct backed_block *last_bb = NULL;
 	struct backed_block *bb;
 	struct backed_block *start;
 	unsigned int last_block = 0;
 	int64_t file_len = 0;
 	int ret;

 	/*
 	 * overhead is sparse file header, the potential end skip
 	 * chunk and crc chunk.
 	 */
 	int overhead = sizeof(sparse_header_t) + 2 * sizeof(chunk_header_t) +
 			sizeof(uint32_t);
 	len -= overhead;

 	start = backed_block_iter_new(from->backed_block_list);
 	out_counter = output_file_open_callback(out_counter_write, &count,
 			to->block_size, to->len, false, true, 0, false);
 	if (!out_counter) {
 		return NULL;
 	}

 	for (bb = start; bb; bb = backed_block_iter_next(bb)) {
 		count = 0;
 		if (backed_block_block(bb) > last_block)
 			count += sizeof(chunk_header_t);
 		last_block = backed_block_block(bb) +
 				DIV_ROUND_UP(backed_block_len(bb), to->block_size);

 		/* will call out_counter_write to update count */
 		ret = sparse_file_write_block(out_counter, bb);
 		if (ret) {
 			bb = NULL;
 			goto out;
 		}
 		if (file_len + count > len) {
 			/*
 			 * If the remaining available size is more than 1/8th of the
 			 * requested size, split the chunk.  Results in sparse files that
 			 * are at least 7/8ths of the requested size
 			 */
 			file_len += sizeof(chunk_header_t);
 			if (!last_bb || (len - file_len > (len / 8))) {
 				backed_block_split(from->backed_block_list, bb, len - file_len);
 				last_bb = bb;
 			}
 			goto move;
 		}
 		file_len += count;
 		last_bb = bb;
 	}

 move:
 	backed_block_list_move(from->backed_block_list,
 		to->backed_block_list, start, last_bb);

 out:
 	output_file_close(out_counter);

 	return bb;
 }

 int sparse_file_resparse(struct sparse_file *in_s, unsigned int max_len,
 		struct sparse_file **out_s, int out_s_count)
 {
 	struct backed_block *bb;
 	struct sparse_file *s;
 	struct sparse_file *tmp;
 	int c = 0;

 	tmp = sparse_file_new(in_s->block_size, in_s->len);
 	if (!tmp) {
 		return -ENOMEM;
 	}

 	do {
 		s = sparse_file_new(in_s->block_size, in_s->len);

 		bb = move_chunks_up_to_len(in_s, s, max_len);

 		if (c < out_s_count) {
 			out_s[c] = s;
 		} else {
 			backed_block_list_move(s->backed_block_list, tmp->backed_block_list,
 					NULL, NULL);
 			sparse_file_destroy(s);
 		}
 		c++;
 	} while (bb);

 	backed_block_list_move(tmp->backed_block_list, in_s->backed_block_list,
 			NULL, NULL);

 	sparse_file_destroy(tmp);

 	return c;
 }

 void sparse_file_verbose(struct sparse_file *s)
 {
 	s->verbose = true;
 }
	/*
	* Copyright (C) 2012 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 <stdlib.h>

	#include <sparse/sparse.h>

	#include "defs.h"
	#include "sparse_file.h"

	#include "output_file.h"
	#include "backed_block.h"
	#include "sparse_defs.h"
	#include "sparse_format.h"

	struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len)
	{
	struct sparse_file *s = calloc(sizeof(struct sparse_file), 1);
	if (!s) {
	return NULL;
	}

	s->backed_block_list = backed_block_list_new(block_size);
	if (!s->backed_block_list) {
	free(s);
	return NULL;
	}

	s->block_size = block_size;
	s->len = len;

	return s;
	}

	void sparse_file_destroy(struct sparse_file *s)
	{
	backed_block_list_destroy(s->backed_block_list);
	free(s);
	}

	int sparse_file_add_data(struct sparse_file *s,
	void *data, unsigned int len, unsigned int block)
	{
	return backed_block_add_data(s->backed_block_list, data, len, block);
	}

	int sparse_file_add_fill(struct sparse_file *s,
	uint32_t fill_val, unsigned int len, unsigned int block)
	{
	return backed_block_add_fill(s->backed_block_list, fill_val, len, block);
	}

	int sparse_file_add_file(struct sparse_file *s,
	const char *filename, int64_t file_offset, unsigned int len,
	unsigned int block)
	{
	return backed_block_add_file(s->backed_block_list, filename, file_offset,
	len, block);
	}

	int sparse_file_add_fd(struct sparse_file *s,
	int fd, int64_t file_offset, unsigned int len, unsigned int block)
	{
	return backed_block_add_fd(s->backed_block_list, fd, file_offset,
	len, block);
	}
	unsigned int sparse_count_chunks(struct sparse_file *s)
	{
	struct backed_block *bb;
	unsigned int last_block = 0;
	unsigned int chunks = 0;

	for (bb = backed_block_iter_new(s->backed_block_list); bb;
	bb = backed_block_iter_next(bb)) {
	if (backed_block_block(bb) > last_block) {
	/* If there is a gap between chunks, add a skip chunk */
	chunks++;
	}
	chunks++;
	last_block = backed_block_block(bb) +
	DIV_ROUND_UP(backed_block_len(bb), s->block_size);
	}
	if (last_block < DIV_ROUND_UP(s->len, s->block_size)) {
	chunks++;
	}

	return chunks;
	}

	static int sparse_file_write_block(struct output_file *out,
	struct backed_block *bb)
	{
	int ret = -EINVAL;

	switch (backed_block_type(bb)) {
	case BACKED_BLOCK_DATA:
	ret = write_data_chunk(out, backed_block_len(bb), backed_block_data(bb));
	break;
	case BACKED_BLOCK_FILE:
	ret = write_file_chunk(out, backed_block_len(bb),
	backed_block_filename(bb),
	backed_block_file_offset(bb));
	break;
	case BACKED_BLOCK_FD:
	ret = write_fd_chunk(out, backed_block_len(bb),
	backed_block_fd(bb),
	backed_block_file_offset(bb));
	break;
	case BACKED_BLOCK_FILL:
	ret = write_fill_chunk(out, backed_block_len(bb),
	backed_block_fill_val(bb));
	break;
	}

	return ret;
	}

	static int write_all_blocks(struct sparse_file s, struct output_file out)
	{
	struct backed_block *bb;
	unsigned int last_block = 0;
	int64_t pad;
	int ret = 0;

	for (bb = backed_block_iter_new(s->backed_block_list); bb;
	bb = backed_block_iter_next(bb)) {
	if (backed_block_block(bb) > last_block) {
	unsigned int blocks = backed_block_block(bb) - last_block;
	write_skip_chunk(out, (int64_t)blocks * s->block_size);
	}
	ret = sparse_file_write_block(out, bb);
	if (ret)
	return ret;
	last_block = backed_block_block(bb) +
	DIV_ROUND_UP(backed_block_len(bb), s->block_size);
	}

	pad = s->len - (int64_t)last_block * s->block_size;
	assert(pad >= 0);
	if (pad > 0) {
	write_skip_chunk(out, pad);
	}

	return 0;
	}

	int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
	bool crc)
	{
	int ret;
	int chunks;
	struct output_file *out;

	chunks = sparse_count_chunks(s);
	out = output_file_open_fd(fd, s->block_size, s->len, gz, sparse, chunks, crc);

	if (!out)
	return -ENOMEM;

	ret = write_all_blocks(s, out);

	output_file_close(out);

	return ret;
	}

	int sparse_file_callback(struct sparse_file *s, bool sparse, bool crc,
	int (write)(void priv, const void data, int len), void priv)
	{
	int ret;
	int chunks;
	struct output_file *out;

	chunks = sparse_count_chunks(s);
	out = output_file_open_callback(write, priv, s->block_size, s->len, false,
	sparse, chunks, crc);

	if (!out)
	return -ENOMEM;

	ret = write_all_blocks(s, out);

	output_file_close(out);

	return ret;
	}

	struct chunk_data {
	void *priv;
	unsigned int block;
	unsigned int nr_blocks;
	int (write)(void priv, const void *data, int len, unsigned int block,
	unsigned int nr_blocks);
	};

	static int foreach_chunk_write(void priv, const void data, int len)
	{
	struct chunk_data *chk = priv;

	return chk->write(chk->priv, data, len, chk->block, chk->nr_blocks);
	}

	int sparse_file_foreach_chunk(struct sparse_file *s, bool sparse, bool crc,
	int (write)(void priv, const void *data, int len, unsigned int block,
	unsigned int nr_blocks),
	void *priv)
	{
	int ret;
	int chunks;
	struct chunk_data chk;
	struct output_file *out;
	struct backed_block *bb;

	chk.priv = priv;
	chk.write = write;
	chk.block = chk.nr_blocks = 0;
	chunks = sparse_count_chunks(s);
	out = output_file_open_callback(foreach_chunk_write, &chk,
	s->block_size, s->len, false, sparse,
	chunks, crc);

	if (!out)
	return -ENOMEM;

	for (bb = backed_block_iter_new(s->backed_block_list); bb;
	bb = backed_block_iter_next(bb)) {
	chk.block = backed_block_block(bb);
	chk.nr_blocks = (backed_block_len(bb) - 1) / s->block_size + 1;
	ret = sparse_file_write_block(out, bb);
	if (ret)
	return ret;
	}

	output_file_close(out);

	return ret;
	}

	static int out_counter_write(void priv, const void data __unused, int len)
	{
	int64_t *count = priv;
	*count += len;
	return 0;
	}

	int64_t sparse_file_len(struct sparse_file *s, bool sparse, bool crc)
	{
	int ret;
	int chunks = sparse_count_chunks(s);
	int64_t count = 0;
	struct output_file *out;

	out = output_file_open_callback(out_counter_write, &count,
	s->block_size, s->len, false, sparse, chunks, crc);
	if (!out) {
	return -1;
	}

	ret = write_all_blocks(s, out);

	output_file_close(out);

	if (ret < 0) {
	return -1;
	}

	return count;
	}

	unsigned int sparse_file_block_size(struct sparse_file *s)
	{
	return s->block_size;
	}

	static struct backed_block move_chunks_up_to_len(struct sparse_file from,
	struct sparse_file *to, unsigned int len)
	{
	int64_t count = 0;
	struct output_file *out_counter;
	struct backed_block *last_bb = NULL;
	struct backed_block *bb;
	struct backed_block *start;
	unsigned int last_block = 0;
	int64_t file_len = 0;
	int ret;

	/*
	* overhead is sparse file header, the potential end skip
	* chunk and crc chunk.
	*/
	int overhead = sizeof(sparse_header_t) + 2 * sizeof(chunk_header_t) +
	sizeof(uint32_t);
	len -= overhead;

	start = backed_block_iter_new(from->backed_block_list);
	out_counter = output_file_open_callback(out_counter_write, &count,
	to->block_size, to->len, false, true, 0, false);
	if (!out_counter) {
	return NULL;
	}

	for (bb = start; bb; bb = backed_block_iter_next(bb)) {
	count = 0;
	if (backed_block_block(bb) > last_block)
	count += sizeof(chunk_header_t);
	last_block = backed_block_block(bb) +
	DIV_ROUND_UP(backed_block_len(bb), to->block_size);

	/* will call out_counter_write to update count */
	ret = sparse_file_write_block(out_counter, bb);
	if (ret) {
	bb = NULL;
	goto out;
	}
	if (file_len + count > len) {
	/*
	* If the remaining available size is more than 1/8th of the
	* requested size, split the chunk. Results in sparse files that
	* are at least 7/8ths of the requested size
	*/
	file_len += sizeof(chunk_header_t);
	if (!last_bb \|\| (len - file_len > (len / 8))) {
	backed_block_split(from->backed_block_list, bb, len - file_len);
	last_bb = bb;
	}
	goto move;
	}
	file_len += count;
	last_bb = bb;
	}

	move:
	backed_block_list_move(from->backed_block_list,
	to->backed_block_list, start, last_bb);

	out:
	output_file_close(out_counter);

	return bb;
	}

	int sparse_file_resparse(struct sparse_file *in_s, unsigned int max_len,
	struct sparse_file **out_s, int out_s_count)
	{
	struct backed_block *bb;
	struct sparse_file *s;
	struct sparse_file *tmp;
	int c = 0;

	tmp = sparse_file_new(in_s->block_size, in_s->len);
	if (!tmp) {
	return -ENOMEM;
	}

	do {
	s = sparse_file_new(in_s->block_size, in_s->len);

	bb = move_chunks_up_to_len(in_s, s, max_len);

	if (c < out_s_count) {
	out_s[c] = s;
	} else {
	backed_block_list_move(s->backed_block_list, tmp->backed_block_list,
	NULL, NULL);
	sparse_file_destroy(s);
	}
	c++;
	} while (bb);

	backed_block_list_move(tmp->backed_block_list, in_s->backed_block_list,
	NULL, NULL);

	sparse_file_destroy(tmp);

	return c;
	}

	void sparse_file_verbose(struct sparse_file *s)
	{
	s->verbose = true;
	}