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