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" 24be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross#include "sparse_defs.h" 25b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 26b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstruct backed_block { 27b55dceea986ab24f8b836b5116b389ed619c816eColin Cross unsigned int block; 28b55dceea986ab24f8b836b5116b389ed619c816eColin Cross unsigned int len; 29b55dceea986ab24f8b836b5116b389ed619c816eColin Cross enum backed_block_type type; 30b55dceea986ab24f8b836b5116b389ed619c816eColin Cross union { 31b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct { 32b55dceea986ab24f8b836b5116b389ed619c816eColin Cross void *data; 33b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } data; 34b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct { 35b55dceea986ab24f8b836b5116b389ed619c816eColin Cross char *filename; 36b55dceea986ab24f8b836b5116b389ed619c816eColin Cross int64_t offset; 37b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } file; 38b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct { 399e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross int fd; 409e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross int64_t offset; 419e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross } fd; 429e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross struct { 43b55dceea986ab24f8b836b5116b389ed619c816eColin Cross uint32_t val; 44b55dceea986ab24f8b836b5116b389ed619c816eColin Cross } fill; 45b55dceea986ab24f8b836b5116b389ed619c816eColin Cross }; 46b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *next; 4728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross}; 4828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 49411619e921904b896eddae81c086c1f687c8304dColin Crossstruct backed_block_list { 50b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *data_blocks; 51b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *last_used; 52be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross unsigned int block_size; 53411619e921904b896eddae81c086c1f687c8304dColin Cross}; 54411619e921904b896eddae81c086c1f687c8304dColin Cross 55b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstruct backed_block *backed_block_iter_new(struct backed_block_list *bbl) 56b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 57b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bbl->data_blocks; 58b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 59b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 60b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstruct backed_block *backed_block_iter_next(struct backed_block *bb) 61b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 62b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->next; 63b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 64b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 65b55dceea986ab24f8b836b5116b389ed619c816eColin Crossunsigned int backed_block_len(struct backed_block *bb) 66b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 67b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->len; 68b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 69b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 70b55dceea986ab24f8b836b5116b389ed619c816eColin Crossunsigned int backed_block_block(struct backed_block *bb) 71b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 72b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->block; 73b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 74b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 75b55dceea986ab24f8b836b5116b389ed619c816eColin Crossvoid *backed_block_data(struct backed_block *bb) 76b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 77b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_DATA); 78b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->data.data; 79b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 80b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 81b55dceea986ab24f8b836b5116b389ed619c816eColin Crossconst char *backed_block_filename(struct backed_block *bb) 82b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 83b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_FILE); 84b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->file.filename; 85b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 86b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 879e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Crossint backed_block_fd(struct backed_block *bb) 889e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross{ 899e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross assert(bb->type == BACKED_BLOCK_FD); 909e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross return bb->fd.fd; 919e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross} 929e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross 93b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint64_t backed_block_file_offset(struct backed_block *bb) 94b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 959e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD); 969e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross if (bb->type == BACKED_BLOCK_FILE) { 979e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross return bb->file.offset; 989e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross } else { /* bb->type == BACKED_BLOCK_FD */ 999e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross return bb->fd.offset; 1009e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross } 101b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 102b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 103b55dceea986ab24f8b836b5116b389ed619c816eColin Crossuint32_t backed_block_fill_val(struct backed_block *bb) 104b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 105b55dceea986ab24f8b836b5116b389ed619c816eColin Cross assert(bb->type == BACKED_BLOCK_FILL); 106b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->fill.val; 107b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 108b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 109b55dceea986ab24f8b836b5116b389ed619c816eColin Crossenum backed_block_type backed_block_type(struct backed_block *bb) 110b55dceea986ab24f8b836b5116b389ed619c816eColin Cross{ 111b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return bb->type; 112b55dceea986ab24f8b836b5116b389ed619c816eColin Cross} 113b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 114be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Crossvoid backed_block_destroy(struct backed_block *bb) 115411619e921904b896eddae81c086c1f687c8304dColin Cross{ 116be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (bb->type == BACKED_BLOCK_FILE) { 117be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross free(bb->file.filename); 118be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 119411619e921904b896eddae81c086c1f687c8304dColin Cross 120be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross free(bb); 121be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross} 122be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 123be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Crossstruct backed_block_list *backed_block_list_new(unsigned int block_size) 124be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross{ 125be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1); 126be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross b->block_size = block_size; 127411619e921904b896eddae81c086c1f687c8304dColin Cross return b; 128411619e921904b896eddae81c086c1f687c8304dColin Cross} 12928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 130b55dceea986ab24f8b836b5116b389ed619c816eColin Crossvoid backed_block_list_destroy(struct backed_block_list *bbl) 131411619e921904b896eddae81c086c1f687c8304dColin Cross{ 132b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->data_blocks) { 133b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = bbl->data_blocks; 134b55dceea986ab24f8b836b5116b389ed619c816eColin Cross while (bb) { 135b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *next = bb->next; 136be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross backed_block_destroy(bb); 137b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb = next; 138411619e921904b896eddae81c086c1f687c8304dColin Cross } 139411619e921904b896eddae81c086c1f687c8304dColin Cross } 140411619e921904b896eddae81c086c1f687c8304dColin Cross 141b55dceea986ab24f8b836b5116b389ed619c816eColin Cross free(bbl); 142411619e921904b896eddae81c086c1f687c8304dColin Cross} 143411619e921904b896eddae81c086c1f687c8304dColin Cross 144bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Crossvoid backed_block_list_move(struct backed_block_list *from, 145bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross struct backed_block_list *to, struct backed_block *start, 146bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross struct backed_block *end) 147bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross{ 148bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross struct backed_block *bb; 149bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 150bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (start == NULL) { 151bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross start = from->data_blocks; 152bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 153bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 154bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (!end) { 155bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross for (end = start; end && end->next; end = end->next) 156bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross ; 157bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 158bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 159bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (start == NULL || end == NULL) { 160bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross return; 161bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 162bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 163bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross from->last_used = NULL; 164bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross to->last_used = NULL; 165bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (from->data_blocks == start) { 166bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross from->data_blocks = end->next; 167bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } else { 168bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross for (bb = from->data_blocks; bb; bb = bb->next) { 169bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (bb->next == start) { 170bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross bb->next = end->next; 171bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross break; 172bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 173bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 174bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 175bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 176bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (!to->data_blocks) { 177bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross to->data_blocks = start; 178bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross end->next = NULL; 179bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } else { 180bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross for (bb = to->data_blocks; bb; bb = bb->next) { 181bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (!bb->next || bb->next->block > start->block) { 182bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross end->next = bb->next; 183bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross bb->next = start; 184bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross break; 185bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 186bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 187bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 188bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross} 189bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 190be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross/* may free b */ 191be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Crossstatic int merge_bb(struct backed_block_list *bbl, 192be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross struct backed_block *a, struct backed_block *b) 193be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross{ 194be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross unsigned int block_len; 195be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 196be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross /* Block doesn't exist (possible if one block is the last block) */ 197be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (!a || !b) { 198be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 199be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 200be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 201be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross assert(a->block < b->block); 202be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 203be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross /* Blocks are of different types */ 204be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (a->type != b->type) { 205be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 206be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 207be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 208be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross /* Blocks are not adjacent */ 209be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross block_len = a->len / bbl->block_size; /* rounds down */ 210be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (a->block + block_len != b->block) { 211be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 212be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 213be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 214be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross switch (a->type) { 215be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross case BACKED_BLOCK_DATA: 216be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross /* Don't support merging data for now */ 217be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 218be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross case BACKED_BLOCK_FILL: 219be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (a->fill.val != b->fill.val) { 220be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 221be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 222be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross break; 223be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross case BACKED_BLOCK_FILE: 224be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (a->file.filename != b->file.filename || 225be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross a->file.offset + a->len != b->file.offset) { 226be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 227be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 228be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross break; 229be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross case BACKED_BLOCK_FD: 230be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross if (a->fd.fd != b->fd.fd || 231be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross a->fd.offset + a->len != b->fd.offset) { 232be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return -EINVAL; 233be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 234be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross break; 235be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross } 236be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 237be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross /* Blocks are compatible and adjacent, with a before b. Merge b into a, 238be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross * and free b */ 239be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross a->len += b->len; 240be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross a->next = b->next; 241be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 242be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross backed_block_destroy(b); 243be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 244be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross return 0; 245be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross} 246be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 247b55dceea986ab24f8b836b5116b389ed619c816eColin Crossstatic int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb) 24828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 249b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb; 25028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 251b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->data_blocks == NULL) { 252b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bbl->data_blocks = new_bb; 253b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return 0; 25428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 25528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 256b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->data_blocks->block > new_bb->block) { 257b55dceea986ab24f8b836b5116b389ed619c816eColin Cross new_bb->next = bbl->data_blocks; 258b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bbl->data_blocks = new_bb; 259b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return 0; 26028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 26128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 26228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross /* Optimization: blocks are mostly queued in sequence, so save the 263b55dceea986ab24f8b836b5116b389ed619c816eColin Cross pointer to the last bb that was added, and start searching from 26428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross there if the next block number is higher */ 265b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bbl->last_used && new_bb->block > bbl->last_used->block) 266b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb = bbl->last_used; 26728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross else 268b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb = bbl->data_blocks; 269b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bbl->last_used = new_bb; 27028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 271b55dceea986ab24f8b836b5116b389ed619c816eColin Cross for (; bb->next && bb->next->block < new_bb->block; bb = bb->next) 27228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross ; 27328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 274b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb->next == NULL) { 275b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = new_bb; 27628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } else { 277b55dceea986ab24f8b836b5116b389ed619c816eColin Cross new_bb->next = bb->next; 278b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = new_bb; 27928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 280b55dceea986ab24f8b836b5116b389ed619c816eColin Cross 281be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross merge_bb(bbl, new_bb, new_bb->next); 282be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross merge_bb(bbl, bb, new_bb); 283be8ddcb35a459481c0bcf5bfe645c1fefe963f5cColin Cross 284b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return 0; 28528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 28628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 28728fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a fill block of memory to be written to the specified data blocks */ 288b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val, 289411619e921904b896eddae81c086c1f687c8304dColin Cross unsigned int len, unsigned int block) 29028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 291b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 292b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb == NULL) { 293b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return -ENOMEM; 29428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 29528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 296b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->block = block; 297b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->len = len; 298b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->type = BACKED_BLOCK_FILL; 299b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->fill.val = fill_val; 300b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = NULL; 30128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 302b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return queue_bb(bbl, bb); 30328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 30428fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 30528fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a block of memory to be written to the specified data blocks */ 306b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint backed_block_add_data(struct backed_block_list *bbl, void *data, 307b55dceea986ab24f8b836b5116b389ed619c816eColin Cross unsigned int len, unsigned int block) 30828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 309b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 310b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb == NULL) { 311b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return -ENOMEM; 31228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 31328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 314b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->block = block; 315b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->len = len; 316b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->type = BACKED_BLOCK_DATA; 317b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->data.data = data; 318b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = NULL; 31928fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 320b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return queue_bb(bbl, bb); 32128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 32228fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 32328fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross/* Queues a chunk of a file on disk to be written to the specified data blocks */ 324b55dceea986ab24f8b836b5116b389ed619c816eColin Crossint backed_block_add_file(struct backed_block_list *bbl, const char *filename, 325411619e921904b896eddae81c086c1f687c8304dColin Cross int64_t offset, unsigned int len, unsigned int block) 32628fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross{ 327b55dceea986ab24f8b836b5116b389ed619c816eColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 328b55dceea986ab24f8b836b5116b389ed619c816eColin Cross if (bb == NULL) { 329b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return -ENOMEM; 33028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross } 33128fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 332b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->block = block; 333b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->len = len; 334b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->type = BACKED_BLOCK_FILE; 335b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->file.filename = strdup(filename); 336b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->file.offset = offset; 337b55dceea986ab24f8b836b5116b389ed619c816eColin Cross bb->next = NULL; 33828fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross 339b55dceea986ab24f8b836b5116b389ed619c816eColin Cross return queue_bb(bbl, bb); 34028fa5bc347390480fe190294c6c385b6a9f0d68bColin Cross} 3419e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross 3429e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross/* Queues a chunk of a fd to be written to the specified data blocks */ 3439e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Crossint backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset, 3449e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross unsigned int len, unsigned int block) 3459e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross{ 3469e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 3479e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross if (bb == NULL) { 3489e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross return -ENOMEM; 3499e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross } 3509e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross 3519e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross bb->block = block; 3529e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross bb->len = len; 3539e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross bb->type = BACKED_BLOCK_FD; 3549e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross bb->fd.fd = fd; 3559e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross bb->fd.offset = offset; 3569e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross bb->next = NULL; 3579e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross 3589e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross return queue_bb(bbl, bb); 3599e1f17e926fa20255c5f4b4d2f68aa98a964253aColin Cross} 360bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 361bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Crossint backed_block_split(struct backed_block_list *bbl, struct backed_block *bb, 362bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross unsigned int max_len) 363bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross{ 364bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross struct backed_block *new_bb; 365bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 366bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross max_len = ALIGN_DOWN(max_len, bbl->block_size); 367bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 368bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (bb->len <= max_len) { 369bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross return 0; 370bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 371bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 372bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb = malloc(sizeof(struct backed_block)); 373bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross if (bb == NULL) { 374bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross return -ENOMEM; 375bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 376bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 377bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross *new_bb = *bb; 378bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 379bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb->len = bb->len - max_len; 380bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb->block = bb->block + max_len / bbl->block_size; 381bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb->next = bb->next; 382bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross bb->next = new_bb; 383bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross bb->len = max_len; 384bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 385bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross switch (bb->type) { 386bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross case BACKED_BLOCK_DATA: 387bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb->data.data = (char *)bb->data.data + max_len; 388bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross break; 389bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross case BACKED_BLOCK_FILE: 390bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb->file.offset += max_len; 391bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross break; 392bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross case BACKED_BLOCK_FD: 393bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross new_bb->fd.offset += max_len; 394bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross break; 395bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross case BACKED_BLOCK_FILL: 396bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross break; 397bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross } 398bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross 399bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross return 0; 400bdc6d39ed6c09199a5d806f29b71b44cbb27c5c2Colin Cross} 401