libsparse/backed_block.c

   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 }