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