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