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 "ext4.h" 19#include "ext4_extents.h" 20#include "indirect.h" 21#include "allocate.h" 22 23#include <sparse/sparse.h> 24 25#include <stdlib.h> 26#include <stdio.h> 27 28/* Creates data buffers for the first backing_len bytes of a block allocation 29 and queues them to be written */ 30static 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, ®ion_block, ®ion_len); 46 47 len = min(region_len * info.block_size, backing_len); 48 49 sparse_file_add_data(info.sparse_file, ptr, len, region_block); 50 ptr += len; 51 backing_len -= len; 52 } 53 54 return data; 55} 56 57static 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 70static 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 87static 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 103static 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 111static 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(info.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 141static 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(info.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 */ 168static 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 */ 191static 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(info.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 */ 223static 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(info.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 */ 255static 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(info.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 283static 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 315static 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 348static 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 389static struct block_allocation *do_inode_allocate_indirect( 390 struct ext4_inode *inode, 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 */ 405void 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(inode, 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 430void 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(info.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(info.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. */ 490u8 *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(inode, 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} 517