backed_block.c revision b55dceea986ab24f8b836b5116b389ed619c816e
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 17b55dceea986ab24f8b836b5116b389ed619c816eColin Cross#include <assert.h> 18b55dceea986ab24f8b836b5116b389ed619c816eColin Cross#include <errno.h> 19b55dceea986ab24f8b836b5116b389ed619c816eColin Cross#include <stdint.h> 2028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include <stdlib.h> 2128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include <string.h> 2228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 2328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross#include "backed_block.h" 24b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 25b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstruct backed_block { 26b55dceea986ab24f8b836b5116b389ed619c816eColin Cross unsigned int block; 27b55dceea986ab24f8b836b5116b389ed619c816eColin Cross unsigned int len; 28b55dceea986ab24f8b836b5116b389ed619c816eColin Cross enum backed_block_type type; 29b55dceea986ab24f8b836b5116b389ed619c816eColin Cross union { 30b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct { 31b55dceea986ab24f8b836b5116b389ed619c816eColin Cross void *data; 32b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } data; 33b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct { 34b55dceea986ab24f8b836b5116b389ed619c816eColin Cross char *filename; 35b55dceea986ab24f8b836b5116b389ed619c816eColin Cross int64_t offset; 36b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } file; 37b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct { 38b55dceea986ab24f8b836b5116b389ed619c816eColin Cross uint32_t val; 39b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } fill; 40b55dceea986ab24f8b836b5116b389ed619c816eColin Cross }; 41b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *next; 4228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross}; 4328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 44411619e921904b896eddae81c086c1f687c8304dColin Crossstruct backed_block_list { 45b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *data_blocks; 46b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *last_used; 47411619e921904b896eddae81c086c1f687c8304dColin Cross}; 48411619e921904b896eddae81c086c1f687c8304dColin Cross 49b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstruct backed_block *backed_block_iter_new(struct backed_block_list *bbl) 50b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 51b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bbl->data_blocks; 52b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 53b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 54b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstruct backed_block *backed_block_iter_next(struct backed_block *bb) 55b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 56b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->next; 57b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 58b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 59b55dceea986ab24f8b836b5116b389ed619c816eColin Crossunsigned int backed_block_len(struct backed_block *bb) 60b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 61b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->len; 62b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 63b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 64b55dceea986ab24f8b836b5116b389ed619c816eColin Crossunsigned int backed_block_block(struct backed_block *bb) 65b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 66b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->block; 67b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 68b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 69b55dceea986ab24f8b836b5116b389ed619c816eColin Crossvoid *backed_block_data(struct backed_block *bb) 70b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 71b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_DATA); 72b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->data.data; 73b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 74b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 75b55dceea986ab24f8b836b5116b389ed619c816eColin Crossconst char *backed_block_filename(struct backed_block *bb) 76b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 77b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_FILE); 78b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->file.filename; 79b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 80b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 81b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint64_t backed_block_file_offset(struct backed_block *bb) 82b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 83b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_FILE); 84b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->file.offset; 85b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 86b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 87b55dceea986ab24f8b836b5116b389ed619c816eColin Crossuint32_t backed_block_fill_val(struct backed_block *bb) 88b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 89b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_FILL); 90b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->fill.val; 91b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 92b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 93b55dceea986ab24f8b836b5116b389ed619c816eColin Crossenum backed_block_type backed_block_type(struct backed_block *bb) 94b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 95b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->type; 96b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 97b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 98411619e921904b896eddae81c086c1f687c8304dColin Crossstruct backed_block_list *backed_block_list_new(void) 99411619e921904b896eddae81c086c1f687c8304dColin Cross{ 100411619e921904b896eddae81c086c1f687c8304dColin Cross struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1); 101411619e921904b896eddae81c086c1f687c8304dColin Cross 102411619e921904b896eddae81c086c1f687c8304dColin Cross return b; 103411619e921904b896eddae81c086c1f687c8304dColin Cross} 10428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 105b55dceea986ab24f8b836b5116b389ed619c816eColin Crossvoid backed_block_list_destroy(struct backed_block_list *bbl) 106411619e921904b896eddae81c086c1f687c8304dColin Cross{ 107b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->data_blocks) { 108b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = bbl->data_blocks; 109b55dceea986ab24f8b836b5116b389ed619c816eColin Cross while (bb) { 110b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *next = bb->next; 111b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb->type == BACKED_BLOCK_FILE) { 112b55dceea986ab24f8b836b5116b389ed619c816eColin Cross free(bb->file.filename); 113b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } 114b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 115b55dceea986ab24f8b836b5116b389ed619c816eColin Cross free(bb); 116b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb = next; 117411619e921904b896eddae81c086c1f687c8304dColin Cross } 118411619e921904b896eddae81c086c1f687c8304dColin Cross } 119411619e921904b896eddae81c086c1f687c8304dColin Cross 120b55dceea986ab24f8b836b5116b389ed619c816eColin Cross free(bbl); 121411619e921904b896eddae81c086c1f687c8304dColin Cross} 122411619e921904b896eddae81c086c1f687c8304dColin Cross 123b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstatic int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb) 12428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 125b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb; 12628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 127b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->data_blocks == NULL) { 128b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bbl->data_blocks = new_bb; 129b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return 0; 13028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 13128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 132b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->data_blocks->block > new_bb->block) { 133b55dceea986ab24f8b836b5116b389ed619c816eColin Cross new_bb->next = bbl->data_blocks; 134b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bbl->data_blocks = new_bb; 135b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return 0; 13628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 13728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 13828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross /* Optimization: blocks are mostly queued in sequence, so save the 139b55dceea986ab24f8b836b5116b389ed619c816eColin Cross pointer to the last bb that was added, and start searching from 14028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross there if the next block number is higher */ 141b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->last_used && new_bb->block > bbl->last_used->block) 142b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb = bbl->last_used; 14328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross else 144b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb = bbl->data_blocks; 145b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bbl->last_used = new_bb; 14628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 147b55dceea986ab24f8b836b5116b389ed619c816eColin Cross for (; bb->next && bb->next->block < new_bb->block; bb = bb->next) 14828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross ; 14928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 150b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb->next == NULL) { 151b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = new_bb; 15228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } else { 153b55dceea986ab24f8b836b5116b389ed619c816eColin Cross new_bb->next = bb->next; 154b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = new_bb; 15528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 156b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 157b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return 0; 15828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 15928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 16028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a fill block of memory to be written to the specified data blocks */ 161b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val, 162411619e921904b896eddae81c086c1f687c8304dColin Cross unsigned int len, unsigned int block) 16328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 164b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 165b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb == NULL) { 166b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return -ENOMEM; 16728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 16828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 169b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->block = block; 170b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->len = len; 171b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->type = BACKED_BLOCK_FILL; 172b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->fill.val = fill_val; 173b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = NULL; 17428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 175b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return queue_bb(bbl, bb); 17628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 17728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 17828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a block of memory to be written to the specified data blocks */ 179b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint backed_block_add_data(struct backed_block_list *bbl, void *data, 180b55dceea986ab24f8b836b5116b389ed619c816eColin Cross unsigned int len, unsigned int block) 18128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 182b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 183b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb == NULL) { 184b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return -ENOMEM; 18528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 18628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 187b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->block = block; 188b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->len = len; 189b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->type = BACKED_BLOCK_DATA; 190b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->data.data = data; 191b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = NULL; 19228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 193b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return queue_bb(bbl, bb); 19428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 19528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 19628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a chunk of a file on disk to be written to the specified data blocks */ 197b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint backed_block_add_file(struct backed_block_list *bbl, const char *filename, 198411619e921904b896eddae81c086c1f687c8304dColin Cross int64_t offset, unsigned int len, unsigned int block) 19928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 200b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 201b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb == NULL) { 202b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return -ENOMEM; 20328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 20428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 205b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->block = block; 206b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->len = len; 207b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->type = BACKED_BLOCK_FILE; 208b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->file.filename = strdup(filename); 209b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->file.offset = offset; 210b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = NULL; 21128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 212b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return queue_bb(bbl, bb); 21328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 214