ext4_utils/indirect.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 "indirect.h"
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21
  22 #include <sparse/sparse.h>
  23
  24 #include "allocate.h"
  25 #include "ext4_utils/ext4_utils.h"
  26
  27
  28 /* Creates data buffers for the first backing_len bytes of a block allocation
  29    and queues them to be written */
  30 static u8 *create_backing(struct block_allocation *alloc,
  31                 unsigned long backing_len)
  32 {
  33         if (DIV_ROUND_UP(backing_len, info.block_size) > EXT4_NDIR_BLOCKS)
  34                 critical_error("indirect backing larger than %d blocks", EXT4_NDIR_BLOCKS);
  35
  36         u8 *data = calloc(backing_len, 1);
  37         if (!data)
  38                 critical_error_errno("calloc");
  39
  40         u8 *ptr = data;
  41         for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) {
  42                 u32 region_block;
  43                 u32 region_len;
  44                 u32 len;
  45                 get_region(alloc, &region_block, &region_len);
  46
  47                 len = min(region_len * info.block_size, backing_len);
  48
  49                 sparse_file_add_data(ext4_sparse_file, ptr, len, region_block);
  50                 ptr += len;
  51                 backing_len -= len;
  52         }
  53
  54         return data;
  55 }
  56
  57 static void reserve_indirect_block(struct block_allocation *alloc, int len)
  58 {
  59         if (reserve_oob_blocks(alloc, 1)) {
  60                 error("failed to reserve oob block");
  61                 return;
  62         }
  63
  64         if (advance_blocks(alloc, len)) {
  65                 error("failed to advance %d blocks", len);
  66                 return;
  67         }
  68 }
  69
  70 static void reserve_dindirect_block(struct block_allocation *alloc, int len)
  71 {
  72         if (reserve_oob_blocks(alloc, 1)) {
  73                 error("failed to reserve oob block");
  74                 return;
  75         }
  76
  77         while (len > 0) {
  78                 int ind_block_len = min((int)aux_info.blocks_per_ind, len);
  79
  80                 reserve_indirect_block(alloc, ind_block_len);
  81
  82                 len -= ind_block_len;
  83         }
  84
  85 }
  86
  87 static void reserve_tindirect_block(struct block_allocation *alloc, int len)
  88 {
  89         if (reserve_oob_blocks(alloc, 1)) {
  90                 error("failed to reserve oob block");
  91                 return;
  92         }
  93
  94         while (len > 0) {
  95                 int dind_block_len = min((int)aux_info.blocks_per_dind, len);
  96
  97                 reserve_dindirect_block(alloc, dind_block_len);
  98
  99                 len -= dind_block_len;
 100         }
 101 }
 102
 103 static void fill_indirect_block(u32 *ind_block, int len, struct block_allocation *alloc)
 104 {
 105         int i;
 106         for (i = 0; i < len; i++) {
 107                 ind_block[i] = get_block(alloc, i);
 108         }
 109 }
 110
 111 static void fill_dindirect_block(u32 *dind_block, int len, struct block_allocation *alloc)
 112 {
 113         int i;
 114         u32 ind_block;
 115
 116         for (i = 0; len >  0; i++) {
 117                 ind_block = get_oob_block(alloc, 0);
 118                 if (advance_oob_blocks(alloc, 1)) {
 119                         error("failed to reserve oob block");
 120                         return;
 121                 }
 122
 123                 dind_block[i] = ind_block;
 124
 125                 u32 *ind_block_data = calloc(info.block_size, 1);
 126                 sparse_file_add_data(ext4_sparse_file, ind_block_data, info.block_size,
 127                                 ind_block);
 128                 int ind_block_len = min((int)aux_info.blocks_per_ind, len);
 129
 130                 fill_indirect_block(ind_block_data, ind_block_len, alloc);
 131
 132                 if (advance_blocks(alloc, ind_block_len)) {
 133                         error("failed to advance %d blocks", ind_block_len);
 134                         return;
 135                 }
 136
 137                 len -= ind_block_len;
 138         }
 139 }
 140
 141 static void fill_tindirect_block(u32 *tind_block, int len, struct block_allocation *alloc)
 142 {
 143         int i;
 144         u32 dind_block;
 145
 146         for (i = 0; len > 0; i++) {
 147                 dind_block = get_oob_block(alloc, 0);
 148                 if (advance_oob_blocks(alloc, 1)) {
 149                         error("failed to reserve oob block");
 150                         return;
 151                 }
 152
 153                 tind_block[i] = dind_block;
 154
 155                 u32 *dind_block_data = calloc(info.block_size, 1);
 156                 sparse_file_add_data(ext4_sparse_file, dind_block_data, info.block_size,
 157                                 dind_block);
 158                 int dind_block_len = min((int)aux_info.blocks_per_dind, len);
 159
 160                 fill_dindirect_block(dind_block_data, dind_block_len, alloc);
 161
 162                 len -= dind_block_len;
 163         }
 164 }
 165
 166 /* Given an allocation, attach as many blocks as possible to direct inode
 167    blocks, and return the rest */
 168 static int inode_attach_direct_blocks(struct ext4_inode *inode,
 169                 struct block_allocation *alloc, u32 *block_len)
 170 {
 171         int len = min(*block_len, EXT4_NDIR_BLOCKS);
 172         int i;
 173
 174         for (i = 0; i < len; i++) {
 175                 inode->i_block[i] = get_block(alloc, i);
 176         }
 177
 178         if (advance_blocks(alloc, len)) {
 179                 error("failed to advance %d blocks", len);
 180                 return -1;
 181         }
 182
 183         *block_len -= len;
 184         return 0;
 185 }
 186
 187 /* Given an allocation, attach as many blocks as possible to indirect blocks,
 188    and return the rest
 189    Assumes that the blocks necessary to hold the indirect blocks were included
 190    as part of the allocation */
 191 static int inode_attach_indirect_blocks(struct ext4_inode *inode,
 192                 struct block_allocation *alloc, u32 *block_len)
 193 {
 194         int len = min(*block_len, aux_info.blocks_per_ind);
 195
 196         int ind_block = get_oob_block(alloc, 0);
 197         inode->i_block[EXT4_IND_BLOCK] = ind_block;
 198
 199         if (advance_oob_blocks(alloc, 1)) {
 200                 error("failed to advance oob block");
 201                 return -1;
 202         }
 203
 204         u32 *ind_block_data = calloc(info.block_size, 1);
 205         sparse_file_add_data(ext4_sparse_file, ind_block_data, info.block_size,
 206                         ind_block);
 207
 208         fill_indirect_block(ind_block_data, len, alloc);
 209
 210         if (advance_blocks(alloc, len)) {
 211                 error("failed to advance %d blocks", len);
 212                 return -1;
 213         }
 214
 215         *block_len -= len;
 216         return 0;
 217 }
 218
 219 /* Given an allocation, attach as many blocks as possible to doubly indirect
 220    blocks, and return the rest.
 221    Assumes that the blocks necessary to hold the indirect and doubly indirect
 222    blocks were included as part of the allocation */
 223 static int inode_attach_dindirect_blocks(struct ext4_inode *inode,
 224                 struct block_allocation *alloc, u32 *block_len)
 225 {
 226         int len = min(*block_len, aux_info.blocks_per_dind);
 227
 228         int dind_block = get_oob_block(alloc, 0);
 229         inode->i_block[EXT4_DIND_BLOCK] = dind_block;
 230
 231         if (advance_oob_blocks(alloc, 1)) {
 232                 error("failed to advance oob block");
 233                 return -1;
 234         }
 235
 236         u32 *dind_block_data = calloc(info.block_size, 1);
 237         sparse_file_add_data(ext4_sparse_file, dind_block_data, info.block_size,
 238                         dind_block);
 239
 240         fill_dindirect_block(dind_block_data, len, alloc);
 241
 242         if (advance_blocks(alloc, len)) {
 243                 error("failed to advance %d blocks", len);
 244                 return -1;
 245         }
 246
 247         *block_len -= len;
 248         return 0;
 249 }
 250
 251 /* Given an allocation, attach as many blocks as possible to triply indirect
 252    blocks, and return the rest.
 253    Assumes that the blocks necessary to hold the indirect, doubly indirect and
 254    triply indirect blocks were included as part of the allocation */
 255 static int inode_attach_tindirect_blocks(struct ext4_inode *inode,
 256                 struct block_allocation *alloc, u32 *block_len)
 257 {
 258         int len = min(*block_len, aux_info.blocks_per_tind);
 259
 260         int tind_block = get_oob_block(alloc, 0);
 261         inode->i_block[EXT4_TIND_BLOCK] = tind_block;
 262
 263         if (advance_oob_blocks(alloc, 1)) {
 264                 error("failed to advance oob block");
 265                 return -1;
 266         }
 267
 268         u32 *tind_block_data = calloc(info.block_size, 1);
 269         sparse_file_add_data(ext4_sparse_file, tind_block_data, info.block_size,
 270                         tind_block);
 271
 272         fill_tindirect_block(tind_block_data, len, alloc);
 273
 274         if (advance_blocks(alloc, len)) {
 275                 error("failed to advance %d blocks", len);
 276                 return -1;
 277         }
 278
 279         *block_len -= len;
 280         return 0;
 281 }
 282
 283 static void reserve_all_indirect_blocks(struct block_allocation *alloc, u32 len)
 284 {
 285         if (len <= EXT4_NDIR_BLOCKS)
 286                 return;
 287
 288         len -= EXT4_NDIR_BLOCKS;
 289         advance_blocks(alloc, EXT4_NDIR_BLOCKS);
 290
 291         u32 ind_block_len = min(aux_info.blocks_per_ind, len);
 292         reserve_indirect_block(alloc, ind_block_len);
 293
 294         len -= ind_block_len;
 295         if (len == 0)
 296                 return;
 297
 298         u32 dind_block_len = min(aux_info.blocks_per_dind, len);
 299         reserve_dindirect_block(alloc, dind_block_len);
 300
 301         len -= dind_block_len;
 302         if (len == 0)
 303                 return;
 304
 305         u32 tind_block_len = min(aux_info.blocks_per_tind, len);
 306         reserve_tindirect_block(alloc, tind_block_len);
 307
 308         len -= tind_block_len;
 309         if (len == 0)
 310                 return;
 311
 312         error("%d blocks remaining", len);
 313 }
 314
 315 static u32 indirect_blocks_needed(u32 len)
 316 {
 317         u32 ind = 0;
 318
 319         if (len <= EXT4_NDIR_BLOCKS)
 320                 return ind;
 321
 322         len -= EXT4_NDIR_BLOCKS;
 323
 324         /* We will need an indirect block for the rest of the blocks */
 325         ind += DIV_ROUND_UP(len, aux_info.blocks_per_ind);
 326
 327         if (len <= aux_info.blocks_per_ind)
 328                 return ind;
 329
 330         len -= aux_info.blocks_per_ind;
 331
 332         ind += DIV_ROUND_UP(len, aux_info.blocks_per_dind);
 333
 334         if (len <= aux_info.blocks_per_dind)
 335                 return ind;
 336
 337         len -= aux_info.blocks_per_dind;
 338
 339         ind += DIV_ROUND_UP(len, aux_info.blocks_per_tind);
 340
 341         if (len <= aux_info.blocks_per_tind)
 342                 return ind;
 343
 344         critical_error("request too large");
 345         return 0;
 346 }
 347
 348 static int do_inode_attach_indirect(struct ext4_inode *inode,
 349                 struct block_allocation *alloc, u32 block_len)
 350 {
 351         u32 count = block_len;
 352
 353         if (inode_attach_direct_blocks(inode, alloc, &count)) {
 354                 error("failed to attach direct blocks to inode");
 355                 return -1;
 356         }
 357
 358         if (count > 0) {
 359                 if (inode_attach_indirect_blocks(inode, alloc, &count)) {
 360                         error("failed to attach indirect blocks to inode");
 361                         return -1;
 362                 }
 363         }
 364
 365         if (count > 0) {
 366                 if (inode_attach_dindirect_blocks(inode, alloc, &count)) {
 367                         error("failed to attach dindirect blocks to inode");
 368                         return -1;
 369                 }
 370         }
 371
 372         if (count > 0) {
 373                 if (inode_attach_tindirect_blocks(inode, alloc, &count)) {
 374                         error("failed to attach tindirect blocks to inode");
 375                         return -1;
 376                 }
 377         }
 378
 379         if (count) {
 380                 error("blocks left after triply-indirect allocation");
 381                 return -1;
 382         }
 383
 384         rewind_alloc(alloc);
 385
 386         return 0;
 387 }
 388
 389 static struct block_allocation *do_inode_allocate_indirect(
 390                 u32 block_len)
 391 {
 392         u32 indirect_len = indirect_blocks_needed(block_len);
 393
 394         struct block_allocation *alloc = allocate_blocks(block_len + indirect_len);
 395
 396         if (alloc == NULL) {
 397                 error("Failed to allocate %d blocks", block_len + indirect_len);
 398                 return NULL;
 399         }
 400
 401         return alloc;
 402 }
 403
 404 /* Allocates enough blocks to hold len bytes and connects them to an inode */
 405 void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len)
 406 {
 407         struct block_allocation *alloc;
 408         u32 block_len = DIV_ROUND_UP(len, info.block_size);
 409         u32 indirect_len = indirect_blocks_needed(block_len);
 410
 411         alloc = do_inode_allocate_indirect(block_len);
 412         if (alloc == NULL) {
 413                 error("failed to allocate extents for %lu bytes", len);
 414                 return;
 415         }
 416
 417         reserve_all_indirect_blocks(alloc, block_len);
 418         rewind_alloc(alloc);
 419
 420         if (do_inode_attach_indirect(inode, alloc, block_len))
 421                 error("failed to attach blocks to indirect inode");
 422
 423         inode->i_flags = 0;
 424         inode->i_blocks_lo = (block_len + indirect_len) * info.block_size / 512;
 425         inode->i_size_lo = len;
 426
 427         free_alloc(alloc);
 428 }
 429
 430 void inode_attach_resize(struct ext4_inode *inode,
 431                 struct block_allocation *alloc)
 432 {
 433         u32 block_len = block_allocation_len(alloc);
 434         u32 superblocks = block_len / info.bg_desc_reserve_blocks;
 435         u32 i, j;
 436         u64 blocks;
 437         u64 size;
 438
 439         if (block_len % info.bg_desc_reserve_blocks)
 440                 critical_error("reserved blocks not a multiple of %d",
 441                                 info.bg_desc_reserve_blocks);
 442
 443         append_oob_allocation(alloc, 1);
 444         u32 dind_block = get_oob_block(alloc, 0);
 445
 446         u32 *dind_block_data = calloc(info.block_size, 1);
 447         if (!dind_block_data)
 448                 critical_error_errno("calloc");
 449         sparse_file_add_data(ext4_sparse_file, dind_block_data, info.block_size,
 450                         dind_block);
 451
 452         u32 *ind_block_data = calloc(info.block_size, info.bg_desc_reserve_blocks);
 453         if (!ind_block_data)
 454                 critical_error_errno("calloc");
 455         sparse_file_add_data(ext4_sparse_file, ind_block_data,
 456                         info.block_size * info.bg_desc_reserve_blocks,
 457                         get_block(alloc, 0));
 458
 459         for (i = 0; i < info.bg_desc_reserve_blocks; i++) {
 460                 int r = (i - aux_info.bg_desc_blocks) % info.bg_desc_reserve_blocks;
 461                 if (r < 0)
 462                         r += info.bg_desc_reserve_blocks;
 463
 464                 dind_block_data[i] = get_block(alloc, r);
 465
 466                 for (j = 1; j < superblocks; j++) {
 467                         u32 b = j * info.bg_desc_reserve_blocks + r;
 468                         ind_block_data[r * aux_info.blocks_per_ind + j - 1] = get_block(alloc, b);
 469                 }
 470         }
 471
 472         u32 last_block = EXT4_NDIR_BLOCKS + aux_info.blocks_per_ind +
 473                         aux_info.blocks_per_ind * (info.bg_desc_reserve_blocks - 1) +
 474                         superblocks - 2;
 475
 476         blocks = ((u64)block_len + 1) * info.block_size / 512;
 477         size = (u64)last_block * info.block_size;
 478
 479         inode->i_block[EXT4_DIND_BLOCK] = dind_block;
 480         inode->i_flags = 0;
 481         inode->i_blocks_lo = blocks;
 482         inode->osd2.linux2.l_i_blocks_high = blocks >> 32;
 483         inode->i_size_lo = size;
 484         inode->i_size_high = size >> 32;
 485 }
 486
 487 /* Allocates enough blocks to hold len bytes, with backing_len bytes in a data
 488    buffer, and connects them to an inode.  Returns a pointer to the data
 489    buffer. */
 490 u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len,
 491                 unsigned long backing_len)
 492 {
 493         struct block_allocation *alloc;
 494         u32 block_len = DIV_ROUND_UP(len, info.block_size);
 495         u8 *data = NULL;
 496
 497         alloc = do_inode_allocate_indirect(block_len);
 498         if (alloc == NULL) {
 499                 error("failed to allocate extents for %lu bytes", len);
 500                 return NULL;
 501         }
 502
 503         if (backing_len) {
 504                 data = create_backing(alloc, backing_len);
 505                 if (!data)
 506                         error("failed to create backing for %lu bytes", backing_len);
 507         }
 508
 509         rewind_alloc(alloc);
 510         if (do_inode_attach_indirect(inode, alloc, block_len))
 511                 error("failed to attach blocks to indirect inode");
 512
 513         free_alloc(alloc);
 514
 515         return data;
 516 }