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 */ 28static 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, ®ion_block, ®ion_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 55static 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 68static 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 85static 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 101static 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 109static 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 139static 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 */ 166static 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 */ 189static 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 */ 221static 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 */ 253static 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 281static 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 313static 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 346static 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 387static 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 */ 403void 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 428void 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. */ 488u8 *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} 515