backed_block.c revision 411619e921904b896eddae81c086c1f687c8304d
128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* 228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * Copyright (C) 2010 The Android Open Source Project 328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * Licensed under the Apache License, Version 2.0 (the "License"); 528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * you may not use this file except in compliance with the License. 628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * You may obtain a copy of the License at 728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * http://www.apache.org/licenses/LICENSE-2.0 928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * 1028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * Unless required by applicable law or agreed to in writing, software 1128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * distributed under the License is distributed on an "AS IS" BASIS, 1228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * See the License for the specific language governing permissions and 1428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross * limitations under the License. 1528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross */ 1628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 1728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include <stdlib.h> 1828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include <string.h> 1928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 2028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include "backed_block.h" 2128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include "sparse_defs.h" 2228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 2328fa5bc347390480fe190294c6c385b6a9f0d68bColin Crossstruct data_block { 2428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u32 block; 2528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u32 len; 2628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross void *data; 2728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross const char *filename; 2828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross int64_t offset; 2928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross struct data_block *next; 3028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u32 fill_val; 3128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u8 fill; 3228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u8 pad1; 3328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u16 pad2; 3428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross}; 3528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 36411619e921904b896eddae81c086c1f687c8304dColin Crossstruct backed_block_list { 37411619e921904b896eddae81c086c1f687c8304dColin Cross struct data_block *data_blocks; 38411619e921904b896eddae81c086c1f687c8304dColin Cross struct data_block *last_used; 39411619e921904b896eddae81c086c1f687c8304dColin Cross}; 40411619e921904b896eddae81c086c1f687c8304dColin Cross 41411619e921904b896eddae81c086c1f687c8304dColin Crossstruct backed_block_list *backed_block_list_new(void) 42411619e921904b896eddae81c086c1f687c8304dColin Cross{ 43411619e921904b896eddae81c086c1f687c8304dColin Cross struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1); 44411619e921904b896eddae81c086c1f687c8304dColin Cross 45411619e921904b896eddae81c086c1f687c8304dColin Cross return b; 46411619e921904b896eddae81c086c1f687c8304dColin Cross} 4728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 48411619e921904b896eddae81c086c1f687c8304dColin Crossvoid backed_block_list_destroy(struct backed_block_list *b) 49411619e921904b896eddae81c086c1f687c8304dColin Cross{ 50411619e921904b896eddae81c086c1f687c8304dColin Cross if (b->data_blocks) { 51411619e921904b896eddae81c086c1f687c8304dColin Cross struct data_block *db = b->data_blocks; 52411619e921904b896eddae81c086c1f687c8304dColin Cross while (db) { 53411619e921904b896eddae81c086c1f687c8304dColin Cross struct data_block *next = db->next; 54411619e921904b896eddae81c086c1f687c8304dColin Cross free((void*)db->filename); 55411619e921904b896eddae81c086c1f687c8304dColin Cross 56411619e921904b896eddae81c086c1f687c8304dColin Cross free(db); 57411619e921904b896eddae81c086c1f687c8304dColin Cross db = next; 58411619e921904b896eddae81c086c1f687c8304dColin Cross } 59411619e921904b896eddae81c086c1f687c8304dColin Cross } 60411619e921904b896eddae81c086c1f687c8304dColin Cross 61411619e921904b896eddae81c086c1f687c8304dColin Cross free(b); 62411619e921904b896eddae81c086c1f687c8304dColin Cross} 63411619e921904b896eddae81c086c1f687c8304dColin Cross 64411619e921904b896eddae81c086c1f687c8304dColin Crossstatic void queue_db(struct backed_block_list *b, struct data_block *new_db) 6528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 6628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross struct data_block *db; 6728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 68411619e921904b896eddae81c086c1f687c8304dColin Cross if (b->data_blocks == NULL) { 69411619e921904b896eddae81c086c1f687c8304dColin Cross b->data_blocks = new_db; 7028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross return; 7128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 7228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 73411619e921904b896eddae81c086c1f687c8304dColin Cross if (b->data_blocks->block > new_db->block) { 74411619e921904b896eddae81c086c1f687c8304dColin Cross new_db->next = b->data_blocks; 75411619e921904b896eddae81c086c1f687c8304dColin Cross b->data_blocks = new_db; 7628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross return; 7728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 7828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 7928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross /* Optimization: blocks are mostly queued in sequence, so save the 8028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross pointer to the last db that was added, and start searching from 8128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross there if the next block number is higher */ 82411619e921904b896eddae81c086c1f687c8304dColin Cross if (b->last_used && new_db->block > b->last_used->block) 83411619e921904b896eddae81c086c1f687c8304dColin Cross db = b->last_used; 8428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross else 85411619e921904b896eddae81c086c1f687c8304dColin Cross db = b->data_blocks; 86411619e921904b896eddae81c086c1f687c8304dColin Cross b->last_used = new_db; 8728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 8828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross for (; db->next && db->next->block < new_db->block; db = db->next) 8928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross ; 9028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 9128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross if (db->next == NULL) { 9228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->next = new_db; 9328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } else { 9428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross new_db->next = db->next; 9528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->next = new_db; 9628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 9728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 9828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 9928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a fill block of memory to be written to the specified data blocks */ 100411619e921904b896eddae81c086c1f687c8304dColin Crossvoid queue_fill_block(struct backed_block_list *b, unsigned int fill_val, 101411619e921904b896eddae81c086c1f687c8304dColin Cross unsigned int len, unsigned int block) 10228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 103411619e921904b896eddae81c086c1f687c8304dColin Cross struct data_block *db = calloc(1, sizeof(struct data_block)); 10428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross if (db == NULL) { 10528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross error_errno("malloc"); 10628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross return; 10728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 10828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 10928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->block = block; 11028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->len = len; 11128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->fill = 1; 11228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->fill_val = fill_val; 11328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->data = NULL; 11428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->filename = NULL; 11528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->next = NULL; 11628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 117411619e921904b896eddae81c086c1f687c8304dColin Cross queue_db(b, db); 11828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 11928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 12028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a block of memory to be written to the specified data blocks */ 121411619e921904b896eddae81c086c1f687c8304dColin Crossvoid queue_data_block(struct backed_block_list *b, void *data, unsigned int len, 122411619e921904b896eddae81c086c1f687c8304dColin Cross unsigned int block) 12328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 12428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross struct data_block *db = malloc(sizeof(struct data_block)); 12528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross if (db == NULL) { 12628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross error_errno("malloc"); 12728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross return; 12828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 12928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 13028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->block = block; 13128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->len = len; 13228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->data = data; 13328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->filename = NULL; 13428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->fill = 0; 13528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->next = NULL; 13628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 137411619e921904b896eddae81c086c1f687c8304dColin Cross queue_db(b, db); 13828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 13928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 14028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a chunk of a file on disk to be written to the specified data blocks */ 141411619e921904b896eddae81c086c1f687c8304dColin Crossvoid queue_data_file(struct backed_block_list *b, const char *filename, 142411619e921904b896eddae81c086c1f687c8304dColin Cross int64_t offset, unsigned int len, unsigned int block) 14328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 14428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross struct data_block *db = malloc(sizeof(struct data_block)); 14528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross if (db == NULL) { 14628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross error_errno("malloc"); 14728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross return; 14828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 14928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 15028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->block = block; 15128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->len = len; 15228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->filename = strdup(filename); 15328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->offset = offset; 15428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->data = NULL; 15528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->fill = 0; 15628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross db->next = NULL; 15728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 158411619e921904b896eddae81c086c1f687c8304dColin Cross queue_db(b, db); 15928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 16028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 16128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Iterates over the queued data blocks, calling data_func for each contiguous 16228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross data block, and file_func for each contiguous file block */ 163411619e921904b896eddae81c086c1f687c8304dColin Crossvoid for_each_data_block(struct backed_block_list *b, 164411619e921904b896eddae81c086c1f687c8304dColin Cross data_block_callback_t data_func, 16528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross data_block_file_callback_t file_func, 166411619e921904b896eddae81c086c1f687c8304dColin Cross data_block_fill_callback_t fill_func, 167411619e921904b896eddae81c086c1f687c8304dColin Cross void *priv, unsigned int block_size) 16828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 16928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross struct data_block *db; 17028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross u32 last_block = 0; 17128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 172411619e921904b896eddae81c086c1f687c8304dColin Cross for (db = b->data_blocks; db; db = db->next) { 17328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross if (db->block < last_block) 17428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross error("data blocks out of order: %u < %u", db->block, last_block); 17528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross last_block = db->block + DIV_ROUND_UP(db->len, block_size) - 1; 17628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 17728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross if (db->filename) 17828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross file_func(priv, (u64)db->block * block_size, db->filename, db->offset, db->len); 17928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross else if (db->fill) 18028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross fill_func(priv, (u64)db->block * block_size, db->fill_val, db->len); 18128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross else 18228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross data_func(priv, (u64)db->block * block_size, db->data, db->len); 18328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 18428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 185