indirect.c revision dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7
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 queue_data_block(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 queue_data_block((u8*)ind_block_data, info.block_size, ind_block); 127 int ind_block_len = min((int)aux_info.blocks_per_ind, len); 128 129 fill_indirect_block(ind_block_data, ind_block_len, alloc); 130 131 if (advance_blocks(alloc, ind_block_len)) { 132 error("failed to advance %d blocks", ind_block_len); 133 return; 134 } 135 136 len -= ind_block_len; 137 } 138} 139 140static void fill_tindirect_block(u32 *tind_block, int len, struct block_allocation *alloc) 141{ 142 int i; 143 u32 dind_block; 144 145 for (i = 0; len > 0; i++) { 146 dind_block = get_oob_block(alloc, 0); 147 if (advance_oob_blocks(alloc, 1)) { 148 error("failed to reserve oob block"); 149 return; 150 } 151 152 tind_block[i] = dind_block; 153 154 u32 *dind_block_data = calloc(info.block_size, 1); 155 queue_data_block((u8*)dind_block_data, info.block_size, 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 queue_data_block((u8*)ind_block_data, info.block_size, ind_block); 204 205 fill_indirect_block(ind_block_data, len, alloc); 206 207 if (advance_blocks(alloc, len)) { 208 error("failed to advance %d blocks", len); 209 return -1; 210 } 211 212 *block_len -= len; 213 return 0; 214} 215 216/* Given an allocation, attach as many blocks as possible to doubly indirect 217 blocks, and return the rest. 218 Assumes that the blocks necessary to hold the indirect and doubly indirect 219 blocks were included as part of the allocation */ 220static int inode_attach_dindirect_blocks(struct ext4_inode *inode, 221 struct block_allocation *alloc, u32 *block_len) 222{ 223 int len = min(*block_len, aux_info.blocks_per_dind); 224 225 int dind_block = get_oob_block(alloc, 0); 226 inode->i_block[EXT4_DIND_BLOCK] = dind_block; 227 228 if (advance_oob_blocks(alloc, 1)) { 229 error("failed to advance oob block"); 230 return -1; 231 } 232 233 u32 *dind_block_data = calloc(info.block_size, 1); 234 queue_data_block((u8*)dind_block_data, info.block_size, dind_block); 235 236 fill_dindirect_block(dind_block_data, len, alloc); 237 238 if (advance_blocks(alloc, len)) { 239 error("failed to advance %d blocks", len); 240 return -1; 241 } 242 243 *block_len -= len; 244 return 0; 245} 246 247/* Given an allocation, attach as many blocks as possible to triply indirect 248 blocks, and return the rest. 249 Assumes that the blocks necessary to hold the indirect, doubly indirect and 250 triply indirect blocks were included as part of the allocation */ 251static int inode_attach_tindirect_blocks(struct ext4_inode *inode, 252 struct block_allocation *alloc, u32 *block_len) 253{ 254 int len = min(*block_len, aux_info.blocks_per_tind); 255 256 int tind_block = get_oob_block(alloc, 0); 257 inode->i_block[EXT4_TIND_BLOCK] = tind_block; 258 259 if (advance_oob_blocks(alloc, 1)) { 260 error("failed to advance oob block"); 261 return -1; 262 } 263 264 u32 *tind_block_data = calloc(info.block_size, 1); 265 queue_data_block((u8*)tind_block_data, info.block_size, tind_block); 266 267 fill_tindirect_block(tind_block_data, len, alloc); 268 269 if (advance_blocks(alloc, len)) { 270 error("failed to advance %d blocks", len); 271 return -1; 272 } 273 274 *block_len -= len; 275 return 0; 276} 277 278static void reserve_all_indirect_blocks(struct block_allocation *alloc, u32 len) 279{ 280 if (len <= EXT4_NDIR_BLOCKS) 281 return; 282 283 len -= EXT4_NDIR_BLOCKS; 284 advance_blocks(alloc, EXT4_NDIR_BLOCKS); 285 286 u32 ind_block_len = min(aux_info.blocks_per_ind, len); 287 reserve_indirect_block(alloc, ind_block_len); 288 289 len -= ind_block_len; 290 if (len == 0) 291 return; 292 293 u32 dind_block_len = min(aux_info.blocks_per_dind, len); 294 reserve_dindirect_block(alloc, dind_block_len); 295 296 len -= dind_block_len; 297 if (len == 0) 298 return; 299 300 u32 tind_block_len = min(aux_info.blocks_per_tind, len); 301 reserve_tindirect_block(alloc, tind_block_len); 302 303 len -= tind_block_len; 304 if (len == 0) 305 return; 306 307 error("%d blocks remaining", len); 308} 309 310static u32 indirect_blocks_needed(u32 len) 311{ 312 u32 ind = 0; 313 314 if (len <= EXT4_NDIR_BLOCKS) 315 return ind; 316 317 len -= EXT4_NDIR_BLOCKS; 318 319 /* We will need an indirect block for the rest of the blocks */ 320 ind += DIV_ROUND_UP(len, aux_info.blocks_per_ind); 321 322 if (len <= aux_info.blocks_per_ind) 323 return ind; 324 325 len -= aux_info.blocks_per_ind; 326 327 ind += DIV_ROUND_UP(len, aux_info.blocks_per_dind); 328 329 if (len <= aux_info.blocks_per_dind) 330 return ind; 331 332 len -= aux_info.blocks_per_dind; 333 334 ind += DIV_ROUND_UP(len, aux_info.blocks_per_tind); 335 336 if (len <= aux_info.blocks_per_tind) 337 return ind; 338 339 critical_error("request too large"); 340 return 0; 341} 342 343static int do_inode_attach_indirect(struct ext4_inode *inode, 344 struct block_allocation *alloc, u32 block_len) 345{ 346 u32 count = block_len; 347 348 if (inode_attach_direct_blocks(inode, alloc, &count)) { 349 error("failed to attach direct blocks to inode"); 350 return -1; 351 } 352 353 if (count > 0) { 354 if (inode_attach_indirect_blocks(inode, alloc, &count)) { 355 error("failed to attach indirect blocks to inode"); 356 return -1; 357 } 358 } 359 360 if (count > 0) { 361 if (inode_attach_dindirect_blocks(inode, alloc, &count)) { 362 error("failed to attach dindirect blocks to inode"); 363 return -1; 364 } 365 } 366 367 if (count > 0) { 368 if (inode_attach_tindirect_blocks(inode, alloc, &count)) { 369 error("failed to attach tindirect blocks to inode"); 370 return -1; 371 } 372 } 373 374 if (count) { 375 error("blocks left after triply-indirect allocation"); 376 return -1; 377 } 378 379 rewind_alloc(alloc); 380 381 return 0; 382} 383 384static struct block_allocation *do_inode_allocate_indirect( 385 struct ext4_inode *inode, u32 block_len) 386{ 387 u32 indirect_len = indirect_blocks_needed(block_len); 388 389 struct block_allocation *alloc = allocate_blocks(block_len + indirect_len); 390 391 if (alloc == NULL) { 392 error("Failed to allocate %d blocks", block_len + indirect_len); 393 return NULL; 394 } 395 396 return alloc; 397} 398 399/* Allocates enough blocks to hold len bytes and connects them to an inode */ 400void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len) 401{ 402 struct block_allocation *alloc; 403 u32 block_len = DIV_ROUND_UP(len, info.block_size); 404 u32 indirect_len = indirect_blocks_needed(block_len); 405 406 alloc = do_inode_allocate_indirect(inode, block_len); 407 if (alloc == NULL) { 408 error("failed to allocate extents for %lu bytes", len); 409 return; 410 } 411 412 reserve_all_indirect_blocks(alloc, block_len); 413 rewind_alloc(alloc); 414 415 if (do_inode_attach_indirect(inode, alloc, block_len)) 416 error("failed to attach blocks to indirect inode"); 417 418 inode->i_flags = 0; 419 inode->i_blocks_lo = (block_len + indirect_len) * info.block_size / 512; 420 inode->i_size_lo = len; 421 422 free_alloc(alloc); 423} 424 425void inode_attach_resize(struct ext4_inode *inode, 426 struct block_allocation *alloc) 427{ 428 u32 block_len = block_allocation_len(alloc); 429 u32 superblocks = block_len / info.bg_desc_reserve_blocks; 430 u32 i, j; 431 u64 blocks; 432 u64 size; 433 434 if (block_len % info.bg_desc_reserve_blocks) 435 critical_error("reserved blocks not a multiple of %d", 436 info.bg_desc_reserve_blocks); 437 438 append_oob_allocation(alloc, 1); 439 u32 dind_block = get_oob_block(alloc, 0); 440 441 u32 *dind_block_data = calloc(info.block_size, 1); 442 if (!dind_block_data) 443 critical_error_errno("calloc"); 444 queue_data_block((u8 *)dind_block_data, info.block_size, dind_block); 445 446 u32 *ind_block_data = calloc(info.block_size, info.bg_desc_reserve_blocks); 447 if (!ind_block_data) 448 critical_error_errno("calloc"); 449 queue_data_block((u8 *)ind_block_data, 450 info.block_size * info.bg_desc_reserve_blocks, 451 get_block(alloc, 0)); 452 453 for (i = 0; i < info.bg_desc_reserve_blocks; i++) { 454 int r = (i - aux_info.bg_desc_blocks) % info.bg_desc_reserve_blocks; 455 if (r < 0) 456 r += info.bg_desc_reserve_blocks; 457 458 dind_block_data[i] = get_block(alloc, r); 459 460 for (j = 1; j < superblocks; j++) { 461 u32 b = j * info.bg_desc_reserve_blocks + r; 462 ind_block_data[r * aux_info.blocks_per_ind + j - 1] = get_block(alloc, b); 463 } 464 } 465 466 u32 last_block = EXT4_NDIR_BLOCKS + aux_info.blocks_per_ind + 467 aux_info.blocks_per_ind * (info.bg_desc_reserve_blocks - 1) + 468 superblocks - 2; 469 470 blocks = ((u64)block_len + 1) * info.block_size / 512; 471 size = (u64)last_block * info.block_size; 472 473 inode->i_block[EXT4_DIND_BLOCK] = dind_block; 474 inode->i_flags = 0; 475 inode->i_blocks_lo = blocks; 476 inode->osd2.linux2.l_i_blocks_high = blocks >> 32; 477 inode->i_size_lo = size; 478 inode->i_size_high = size >> 32; 479} 480 481/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data 482 buffer, and connects them to an inode. Returns a pointer to the data 483 buffer. */ 484u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len, 485 unsigned long backing_len) 486{ 487 struct block_allocation *alloc; 488 u32 block_len = DIV_ROUND_UP(len, info.block_size); 489 u8 *data = NULL; 490 491 alloc = do_inode_allocate_indirect(inode, block_len); 492 if (alloc == NULL) { 493 error("failed to allocate extents for %lu bytes", len); 494 return NULL; 495 } 496 497 if (backing_len) { 498 data = create_backing(alloc, backing_len); 499 if (!data) 500 error("failed to create backing for %lu bytes", backing_len); 501 } 502 503 rewind_alloc(alloc); 504 if (do_inode_attach_indirect(inode, alloc, block_len)) 505 error("failed to attach blocks to indirect inode"); 506 507 free_alloc(alloc); 508 509 return data; 510} 511