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 if (a->file.filename != b->file.filename || 225 a->file.offset + a->len != b->file.offset) { 226 return -EINVAL; 227 } 228 break; 229 case BACKED_BLOCK_FD: 230 if (a->fd.fd != b->fd.fd || 231 a->fd.offset + a->len != b->fd.offset) { 232 return -EINVAL; 233 } 234 break; 235 } 236 237 /* Blocks are compatible and adjacent, with a before b. Merge b into a, 238 * and free b */ 239 a->len += b->len; 240 a->next = b->next; 241 242 backed_block_destroy(b); 243 244 return 0; 245 } 246 247 static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb) 248 { 249 struct backed_block *bb; 250 251 if (bbl->data_blocks == NULL) { 252 bbl->data_blocks = new_bb; 253 return 0; 254 } 255 256 if (bbl->data_blocks->block > new_bb->block) { 257 new_bb->next = bbl->data_blocks; 258 bbl->data_blocks = new_bb; 259 return 0; 260 } 261 262 /* Optimization: blocks are mostly queued in sequence, so save the 263 pointer to the last bb that was added, and start searching from 264 there if the next block number is higher */ 265 if (bbl->last_used && new_bb->block > bbl->last_used->block) 266 bb = bbl->last_used; 267 else 268 bb = bbl->data_blocks; 269 bbl->last_used = new_bb; 270 271 for (; bb->next && bb->next->block < new_bb->block; bb = bb->next) 272 ; 273 274 if (bb->next == NULL) { 275 bb->next = new_bb; 276 } else { 277 new_bb->next = bb->next; 278 bb->next = new_bb; 279 } 280 281 merge_bb(bbl, new_bb, new_bb->next); 282 merge_bb(bbl, bb, new_bb); 283 284 return 0; 285 } 286 287 /* Queues a fill block of memory to be written to the specified data blocks */ 288 int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val, 289 unsigned int len, unsigned int block) 290 { 291 struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 292 if (bb == NULL) { 293 return -ENOMEM; 294 } 295 296 bb->block = block; 297 bb->len = len; 298 bb->type = BACKED_BLOCK_FILL; 299 bb->fill.val = fill_val; 300 bb->next = NULL; 301 302 return queue_bb(bbl, bb); 303 } 304 305 /* Queues a block of memory to be written to the specified data blocks */ 306 int backed_block_add_data(struct backed_block_list *bbl, void *data, 307 unsigned int len, unsigned int block) 308 { 309 struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 310 if (bb == NULL) { 311 return -ENOMEM; 312 } 313 314 bb->block = block; 315 bb->len = len; 316 bb->type = BACKED_BLOCK_DATA; 317 bb->data.data = data; 318 bb->next = NULL; 319 320 return queue_bb(bbl, bb); 321 } 322 323 /* Queues a chunk of a file on disk to be written to the specified data blocks */ 324 int backed_block_add_file(struct backed_block_list *bbl, const char *filename, 325 int64_t offset, unsigned int len, unsigned int block) 326 { 327 struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 328 if (bb == NULL) { 329 return -ENOMEM; 330 } 331 332 bb->block = block; 333 bb->len = len; 334 bb->type = BACKED_BLOCK_FILE; 335 bb->file.filename = strdup(filename); 336 bb->file.offset = offset; 337 bb->next = NULL; 338 339 return queue_bb(bbl, bb); 340 } 341 342 /* Queues a chunk of a fd to be written to the specified data blocks */ 343 int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset, 344 unsigned int len, unsigned int block) 345 { 346 struct backed_block *bb = calloc(1, sizeof(struct backed_block)); 347 if (bb == NULL) { 348 return -ENOMEM; 349 } 350 351 bb->block = block; 352 bb->len = len; 353 bb->type = BACKED_BLOCK_FD; 354 bb->fd.fd = fd; 355 bb->fd.offset = offset; 356 bb->next = NULL; 357 358 return queue_bb(bbl, bb); 359 } 360 361 int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb, 362 unsigned int max_len) 363 { 364 struct backed_block *new_bb; 365 366 max_len = ALIGN_DOWN(max_len, bbl->block_size); 367 368 if (bb->len <= max_len) { 369 return 0; 370 } 371 372 new_bb = malloc(sizeof(struct backed_block)); 373 if (new_bb == NULL) { 374 return -ENOMEM; 375 } 376 377 *new_bb = *bb; 378 379 new_bb->len = bb->len - max_len; 380 new_bb->block = bb->block + max_len / bbl->block_size; 381 new_bb->next = bb->next; 382 bb->next = new_bb; 383 bb->len = max_len; 384 385 switch (bb->type) { 386 case BACKED_BLOCK_DATA: 387 new_bb->data.data = (char *)bb->data.data + max_len; 388 break; 389 case BACKED_BLOCK_FILE: 390 new_bb->file.offset += max_len; 391 break; 392 case BACKED_BLOCK_FD: 393 new_bb->fd.offset += max_len; 394 break; 395 case BACKED_BLOCK_FILL: 396 break; 397 } 398 399 return 0; 400 } 401
