Home | History | Annotate | Download | only in libsparse
      1 /*
      2  * Copyright (C) 2010 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include <assert.h>
     18 #include <errno.h>
     19 #include <stdint.h>
     20 #include <stdlib.h>
     21 #include <string.h>
     22 
     23 #include "backed_block.h"
     24 #include "sparse_defs.h"
     25 
     26 struct backed_block {
     27 	unsigned int block;
     28 	unsigned int len;
     29 	enum backed_block_type type;
     30 	union {
     31 		struct {
     32 			void *data;
     33 		} data;
     34 		struct {
     35 			char *filename;
     36 			int64_t offset;
     37 		} file;
     38 		struct {
     39 			int fd;
     40 			int64_t offset;
     41 		} fd;
     42 		struct {
     43 			uint32_t val;
     44 		} fill;
     45 	};
     46 	struct backed_block *next;
     47 };
     48 
     49 struct backed_block_list {
     50 	struct backed_block *data_blocks;
     51 	struct backed_block *last_used;
     52 	unsigned int block_size;
     53 };
     54 
     55 struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
     56 {
     57 	return bbl->data_blocks;
     58 }
     59 
     60 struct backed_block *backed_block_iter_next(struct backed_block *bb)
     61 {
     62 	return bb->next;
     63 }
     64 
     65 unsigned int backed_block_len(struct backed_block *bb)
     66 {
     67 	return bb->len;
     68 }
     69 
     70 unsigned int backed_block_block(struct backed_block *bb)
     71 {
     72 	return bb->block;
     73 }
     74 
     75 void *backed_block_data(struct backed_block *bb)
     76 {
     77 	assert(bb->type == BACKED_BLOCK_DATA);
     78 	return bb->data.data;
     79 }
     80 
     81 const char *backed_block_filename(struct backed_block *bb)
     82 {
     83 	assert(bb->type == BACKED_BLOCK_FILE);
     84 	return bb->file.filename;
     85 }
     86 
     87 int backed_block_fd(struct backed_block *bb)
     88 {
     89 	assert(bb->type == BACKED_BLOCK_FD);
     90 	return bb->fd.fd;
     91 }
     92 
     93 int64_t backed_block_file_offset(struct backed_block *bb)
     94 {
     95 	assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD);
     96 	if (bb->type == BACKED_BLOCK_FILE) {
     97 		return bb->file.offset;
     98 	} else { /* bb->type == BACKED_BLOCK_FD */
     99 		return bb->fd.offset;
    100 	}
    101 }
    102 
    103 uint32_t backed_block_fill_val(struct backed_block *bb)
    104 {
    105 	assert(bb->type == BACKED_BLOCK_FILL);
    106 	return bb->fill.val;
    107 }
    108 
    109 enum backed_block_type backed_block_type(struct backed_block *bb)
    110 {
    111 	return bb->type;
    112 }
    113 
    114 void backed_block_destroy(struct backed_block *bb)
    115 {
    116 	if (bb->type == BACKED_BLOCK_FILE) {
    117 		free(bb->file.filename);
    118 	}
    119 
    120 	free(bb);
    121 }
    122 
    123 struct backed_block_list *backed_block_list_new(unsigned int block_size)
    124 {
    125 	struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
    126 	b->block_size = block_size;
    127 	return b;
    128 }
    129 
    130 void backed_block_list_destroy(struct backed_block_list *bbl)
    131 {
    132 	if (bbl->data_blocks) {
    133 		struct backed_block *bb = bbl->data_blocks;
    134 		while (bb) {
    135 			struct backed_block *next = bb->next;
    136 			backed_block_destroy(bb);
    137 			bb = next;
    138 		}
    139 	}
    140 
    141 	free(bbl);
    142 }
    143 
    144 void backed_block_list_move(struct backed_block_list *from,
    145 		struct backed_block_list *to, struct backed_block *start,
    146 		struct backed_block *end)
    147 {
    148 	struct backed_block *bb;
    149 
    150 	if (start == NULL) {
    151 		start = from->data_blocks;
    152 	}
    153 
    154 	if (!end) {
    155 		for (end = start; end && end->next; end = end->next)
    156 			;
    157 	}
    158 
    159 	if (start == NULL || end == NULL) {
    160 		return;
    161 	}
    162 
    163 	from->last_used = NULL;
    164 	to->last_used = NULL;
    165 	if (from->data_blocks == start) {
    166 		from->data_blocks = end->next;
    167 	} else {
    168 		for (bb = from->data_blocks; bb; bb = bb->next) {
    169 			if (bb->next == start) {
    170 				bb->next = end->next;
    171 				break;
    172 			}
    173 		}
    174 	}
    175 
    176 	if (!to->data_blocks) {
    177 		to->data_blocks = start;
    178 		end->next = NULL;
    179 	} else {
    180 		for (bb = to->data_blocks; bb; bb = bb->next) {
    181 			if (!bb->next || bb->next->block > start->block) {
    182 				end->next = bb->next;
    183 				bb->next = start;
    184 				break;
    185 			}
    186 		}
    187 	}
    188 }
    189 
    190 /* may free b */
    191 static int merge_bb(struct backed_block_list *bbl,
    192 		struct backed_block *a, struct backed_block *b)
    193 {
    194 	unsigned int block_len;
    195 
    196 	/* Block doesn't exist (possible if one block is the last block) */
    197 	if (!a || !b) {
    198 		return -EINVAL;
    199 	}
    200 
    201 	assert(a->block < b->block);
    202 
    203 	/* Blocks are of different types */
    204 	if (a->type != b->type) {
    205 		return -EINVAL;
    206 	}
    207 
    208 	/* Blocks are not adjacent */
    209 	block_len = a->len / bbl->block_size; /* rounds down */
    210 	if (a->block + block_len != b->block) {
    211 		return -EINVAL;
    212 	}
    213 
    214 	switch (a->type) {
    215 	case BACKED_BLOCK_DATA:
    216 		/* Don't support merging data for now */
    217 		return -EINVAL;
    218 	case BACKED_BLOCK_FILL:
    219 		if (a->fill.val != b->fill.val) {
    220 			return -EINVAL;
    221 		}
    222 		break;
    223 	case BACKED_BLOCK_FILE:
    224 		if (a->file.filename != b->file.filename ||
    225 				a->file.offset + a->len != b->file.offset) {
    226 			return -EINVAL;
    227 		}
    228 		break;
    229 	case BACKED_BLOCK_FD:
    230 		if (a->fd.fd != b->fd.fd ||
    231 				a->fd.offset + a->len != b->fd.offset) {
    232 			return -EINVAL;
    233 		}
    234 		break;
    235 	}
    236 
    237 	/* Blocks are compatible and adjacent, with a before b.  Merge b into a,
    238 	 * and free b */
    239 	a->len += b->len;
    240 	a->next = b->next;
    241 
    242 	backed_block_destroy(b);
    243 
    244 	return 0;
    245 }
    246 
    247 static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
    248 {
    249 	struct backed_block *bb;
    250 
    251 	if (bbl->data_blocks == NULL) {
    252 		bbl->data_blocks = new_bb;
    253 		return 0;
    254 	}
    255 
    256 	if (bbl->data_blocks->block > new_bb->block) {
    257 		new_bb->next = bbl->data_blocks;
    258 		bbl->data_blocks = new_bb;
    259 		return 0;
    260 	}
    261 
    262 	/* Optimization: blocks are mostly queued in sequence, so save the
    263 	   pointer to the last bb that was added, and start searching from
    264 	   there if the next block number is higher */
    265 	if (bbl->last_used && new_bb->block > bbl->last_used->block)
    266 		bb = bbl->last_used;
    267 	else
    268 		bb = bbl->data_blocks;
    269 	bbl->last_used = new_bb;
    270 
    271 	for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
    272 		;
    273 
    274 	if (bb->next == NULL) {
    275 		bb->next = new_bb;
    276 	} else {
    277 		new_bb->next = bb->next;
    278 		bb->next = new_bb;
    279 	}
    280 
    281 	merge_bb(bbl, new_bb, new_bb->next);
    282 	merge_bb(bbl, bb, new_bb);
    283 
    284 	return 0;
    285 }
    286 
    287 /* Queues a fill block of memory to be written to the specified data blocks */
    288 int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
    289 		unsigned int len, unsigned int block)
    290 {
    291 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
    292 	if (bb == NULL) {
    293 		return -ENOMEM;
    294 	}
    295 
    296 	bb->block = block;
    297 	bb->len = len;
    298 	bb->type = BACKED_BLOCK_FILL;
    299 	bb->fill.val = fill_val;
    300 	bb->next = NULL;
    301 
    302 	return queue_bb(bbl, bb);
    303 }
    304 
    305 /* Queues a block of memory to be written to the specified data blocks */
    306 int backed_block_add_data(struct backed_block_list *bbl, void *data,
    307 		unsigned int len, unsigned int block)
    308 {
    309 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
    310 	if (bb == NULL) {
    311 		return -ENOMEM;
    312 	}
    313 
    314 	bb->block = block;
    315 	bb->len = len;
    316 	bb->type = BACKED_BLOCK_DATA;
    317 	bb->data.data = data;
    318 	bb->next = NULL;
    319 
    320 	return queue_bb(bbl, bb);
    321 }
    322 
    323 /* Queues a chunk of a file on disk to be written to the specified data blocks */
    324 int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
    325 		int64_t offset, unsigned int len, unsigned int block)
    326 {
    327 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
    328 	if (bb == NULL) {
    329 		return -ENOMEM;
    330 	}
    331 
    332 	bb->block = block;
    333 	bb->len = len;
    334 	bb->type = BACKED_BLOCK_FILE;
    335 	bb->file.filename = strdup(filename);
    336 	bb->file.offset = offset;
    337 	bb->next = NULL;
    338 
    339 	return queue_bb(bbl, bb);
    340 }
    341 
    342 /* Queues a chunk of a fd to be written to the specified data blocks */
    343 int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset,
    344 		unsigned int len, unsigned int block)
    345 {
    346 	struct backed_block *bb = calloc(1, sizeof(struct backed_block));
    347 	if (bb == NULL) {
    348 		return -ENOMEM;
    349 	}
    350 
    351 	bb->block = block;
    352 	bb->len = len;
    353 	bb->type = BACKED_BLOCK_FD;
    354 	bb->fd.fd = fd;
    355 	bb->fd.offset = offset;
    356 	bb->next = NULL;
    357 
    358 	return queue_bb(bbl, bb);
    359 }
    360 
    361 int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb,
    362 		unsigned int max_len)
    363 {
    364 	struct backed_block *new_bb;
    365 
    366 	max_len = ALIGN_DOWN(max_len, bbl->block_size);
    367 
    368 	if (bb->len <= max_len) {
    369 		return 0;
    370 	}
    371 
    372 	new_bb = malloc(sizeof(struct backed_block));
    373 	if (new_bb == NULL) {
    374 		return -ENOMEM;
    375 	}
    376 
    377 	*new_bb = *bb;
    378 
    379 	new_bb->len = bb->len - max_len;
    380 	new_bb->block = bb->block + max_len / bbl->block_size;
    381 	new_bb->next = bb->next;
    382 	bb->next = new_bb;
    383 	bb->len = max_len;
    384 
    385 	switch (bb->type) {
    386 	case BACKED_BLOCK_DATA:
    387 		new_bb->data.data = (char *)bb->data.data + max_len;
    388 		break;
    389 	case BACKED_BLOCK_FILE:
    390 		new_bb->file.offset += max_len;
    391 		break;
    392 	case BACKED_BLOCK_FD:
    393 		new_bb->fd.offset += max_len;
    394 		break;
    395 	case BACKED_BLOCK_FILL:
    396 		break;
    397 	}
    398 
    399 	return 0;
    400 }
    401