2 * Copyright (C) 2010 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include "ext4_utils.h"
19 #include "ext4_extents.h"
20 #include "backed_block.h"
27 /* Creates data buffers for the first backing_len bytes of a block allocation
28 and queues them to be written */
29 static u8 *create_backing(struct block_allocation *alloc,
30 unsigned long backing_len)
32 if (DIV_ROUND_UP(backing_len, info.block_size) > EXT4_NDIR_BLOCKS)
33 critical_error("indirect backing larger than %d blocks", EXT4_NDIR_BLOCKS);
35 u8 *data = calloc(backing_len, 1);
37 critical_error_errno("calloc");
40 for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) {
44 get_region(alloc, ®ion_block, ®ion_len);
46 len = min(region_len * info.block_size, backing_len);
48 queue_data_block(ptr, len, region_block);
56 static void reserve_indirect_block(struct block_allocation *alloc, int len)
58 if (reserve_oob_blocks(alloc, 1)) {
59 error("failed to reserve oob block");
63 if (advance_blocks(alloc, len)) {
64 error("failed to advance %d blocks", len);
69 static void reserve_dindirect_block(struct block_allocation *alloc, int len)
71 if (reserve_oob_blocks(alloc, 1)) {
72 error("failed to reserve oob block");
77 int ind_block_len = min((int)aux_info.blocks_per_ind, len);
79 reserve_indirect_block(alloc, ind_block_len);
86 static void reserve_tindirect_block(struct block_allocation *alloc, int len)
88 if (reserve_oob_blocks(alloc, 1)) {
89 error("failed to reserve oob block");
94 int dind_block_len = min((int)aux_info.blocks_per_dind, len);
96 reserve_dindirect_block(alloc, dind_block_len);
98 len -= dind_block_len;
102 static void fill_indirect_block(u32 *ind_block, int len, struct block_allocation *alloc)
105 for (i = 0; i < len; i++) {
106 ind_block[i] = get_block(alloc, i);
110 static void fill_dindirect_block(u32 *dind_block, int len, struct block_allocation *alloc)
115 for (i = 0; len > 0; i++) {
116 ind_block = get_oob_block(alloc, 0);
117 if (advance_oob_blocks(alloc, 1)) {
118 error("failed to reserve oob block");
122 dind_block[i] = ind_block;
124 u32 *ind_block_data = calloc(info.block_size, 1);
125 queue_data_block((u8*)ind_block_data, info.block_size, ind_block);
126 int ind_block_len = min((int)aux_info.blocks_per_ind, len);
128 fill_indirect_block(ind_block_data, ind_block_len, alloc);
130 if (advance_blocks(alloc, ind_block_len)) {
131 error("failed to advance %d blocks", ind_block_len);
135 len -= ind_block_len;
139 static void fill_tindirect_block(u32 *tind_block, int len, struct block_allocation *alloc)
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");
151 tind_block[i] = dind_block;
153 u32 *dind_block_data = calloc(info.block_size, 1);
154 queue_data_block((u8*)dind_block_data, info.block_size, dind_block);
155 int dind_block_len = min((int)aux_info.blocks_per_dind, len);
157 fill_dindirect_block(dind_block_data, dind_block_len, alloc);
159 len -= dind_block_len;
163 /* Given an allocation, attach as many blocks as possible to direct inode
164 blocks, and return the rest */
165 static int inode_attach_direct_blocks(struct ext4_inode *inode,
166 struct block_allocation *alloc, u32 *block_len)
168 int len = min(*block_len, EXT4_NDIR_BLOCKS);
171 for (i = 0; i < len; i++) {
172 inode->i_block[i] = get_block(alloc, i);
175 if (advance_blocks(alloc, len)) {
176 error("failed to advance %d blocks", len);
184 /* Given an allocation, attach as many blocks as possible to indirect blocks,
186 Assumes that the blocks necessary to hold the indirect blocks were included
187 as part of the allocation */
188 static int inode_attach_indirect_blocks(struct ext4_inode *inode,
189 struct block_allocation *alloc, u32 *block_len)
191 int len = min(*block_len, aux_info.blocks_per_ind);
193 int ind_block = get_oob_block(alloc, 0);
194 inode->i_block[EXT4_IND_BLOCK] = ind_block;
196 if (advance_oob_blocks(alloc, 1)) {
197 error("failed to advance oob block");
201 u32 *ind_block_data = calloc(info.block_size, 1);
202 queue_data_block((u8*)ind_block_data, info.block_size, ind_block);
204 fill_indirect_block(ind_block_data, len, alloc);
206 if (advance_blocks(alloc, len)) {
207 error("failed to advance %d blocks", len);
215 /* Given an allocation, attach as many blocks as possible to doubly indirect
216 blocks, and return the rest.
217 Assumes that the blocks necessary to hold the indirect and doubly indirect
218 blocks were included as part of the allocation */
219 static int inode_attach_dindirect_blocks(struct ext4_inode *inode,
220 struct block_allocation *alloc, u32 *block_len)
222 int len = min(*block_len, aux_info.blocks_per_dind);
224 int dind_block = get_oob_block(alloc, 0);
225 inode->i_block[EXT4_DIND_BLOCK] = dind_block;
227 if (advance_oob_blocks(alloc, 1)) {
228 error("failed to advance oob block");
232 u32 *dind_block_data = calloc(info.block_size, 1);
233 queue_data_block((u8*)dind_block_data, info.block_size, dind_block);
235 fill_dindirect_block(dind_block_data, len, alloc);
237 if (advance_blocks(alloc, len)) {
238 error("failed to advance %d blocks", len);
246 /* Given an allocation, attach as many blocks as possible to triply indirect
247 blocks, and return the rest.
248 Assumes that the blocks necessary to hold the indirect, doubly indirect and
249 triply indirect blocks were included as part of the allocation */
250 static int inode_attach_tindirect_blocks(struct ext4_inode *inode,
251 struct block_allocation *alloc, u32 *block_len)
253 int len = min(*block_len, aux_info.blocks_per_tind);
255 int tind_block = get_oob_block(alloc, 0);
256 inode->i_block[EXT4_TIND_BLOCK] = tind_block;
258 if (advance_oob_blocks(alloc, 1)) {
259 error("failed to advance oob block");
263 u32 *tind_block_data = calloc(info.block_size, 1);
264 queue_data_block((u8*)tind_block_data, info.block_size, tind_block);
266 fill_tindirect_block(tind_block_data, len, alloc);
268 if (advance_blocks(alloc, len)) {
269 error("failed to advance %d blocks", len);
277 static void reserve_all_indirect_blocks(struct block_allocation *alloc, u32 len)
279 if (len <= EXT4_NDIR_BLOCKS)
282 len -= EXT4_NDIR_BLOCKS;
283 advance_blocks(alloc, EXT4_NDIR_BLOCKS);
285 u32 ind_block_len = min(aux_info.blocks_per_ind, len);
286 reserve_indirect_block(alloc, ind_block_len);
288 len -= ind_block_len;
292 u32 dind_block_len = min(aux_info.blocks_per_dind, len);
293 reserve_dindirect_block(alloc, dind_block_len);
295 len -= dind_block_len;
299 u32 tind_block_len = min(aux_info.blocks_per_tind, len);
300 reserve_tindirect_block(alloc, tind_block_len);
302 len -= tind_block_len;
306 error("%d blocks remaining", len);
309 static u32 indirect_blocks_needed(u32 len)
313 if (len <= EXT4_NDIR_BLOCKS)
316 len -= EXT4_NDIR_BLOCKS;
318 /* We will need an indirect block for the rest of the blocks */
319 ind += DIV_ROUND_UP(len, aux_info.blocks_per_ind);
321 if (len <= aux_info.blocks_per_ind)
324 len -= aux_info.blocks_per_ind;
326 ind += DIV_ROUND_UP(len, aux_info.blocks_per_dind);
328 if (len <= aux_info.blocks_per_dind)
331 len -= aux_info.blocks_per_dind;
333 ind += DIV_ROUND_UP(len, aux_info.blocks_per_tind);
335 if (len <= aux_info.blocks_per_tind)
338 critical_error("request too large");
342 static int do_inode_attach_indirect(struct ext4_inode *inode,
343 struct block_allocation *alloc, u32 block_len)
345 u32 count = block_len;
347 if (inode_attach_direct_blocks(inode, alloc, &count)) {
348 error("failed to attach direct blocks to inode");
353 if (inode_attach_indirect_blocks(inode, alloc, &count)) {
354 error("failed to attach indirect blocks to inode");
360 if (inode_attach_dindirect_blocks(inode, alloc, &count)) {
361 error("failed to attach dindirect blocks to inode");
367 if (inode_attach_tindirect_blocks(inode, alloc, &count)) {
368 error("failed to attach tindirect blocks to inode");
374 error("blocks left after triply-indirect allocation");
383 static struct block_allocation *do_inode_allocate_indirect(
384 struct ext4_inode *inode, u32 block_len)
386 u32 indirect_len = indirect_blocks_needed(block_len);
388 struct block_allocation *alloc = allocate_blocks(block_len + indirect_len);
391 error("Failed to allocate %d blocks", block_len + indirect_len);
398 /* Allocates enough blocks to hold len bytes and connects them to an inode */
399 void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len)
401 struct block_allocation *alloc;
402 u32 block_len = DIV_ROUND_UP(len, info.block_size);
403 u32 indirect_len = indirect_blocks_needed(block_len);
405 alloc = do_inode_allocate_indirect(inode, block_len);
407 error("failed to allocate extents for %lu bytes", len);
411 reserve_all_indirect_blocks(alloc, block_len);
414 if (do_inode_attach_indirect(inode, alloc, block_len))
415 error("failed to attach blocks to indirect inode");
418 inode->i_blocks_lo = (block_len + indirect_len) * info.block_size / 512;
419 inode->i_size_lo = len;
424 void inode_attach_resize(struct ext4_inode *inode,
425 struct block_allocation *alloc)
427 u32 block_len = block_allocation_len(alloc);
428 u32 superblocks = block_len / info.bg_desc_reserve_blocks;
433 if (block_len % info.bg_desc_reserve_blocks)
434 critical_error("reserved blocks not a multiple of %d",
435 info.bg_desc_reserve_blocks);
437 append_oob_allocation(alloc, 1);
438 u32 dind_block = get_oob_block(alloc, 0);
440 u32 *dind_block_data = calloc(info.block_size, 1);
441 if (!dind_block_data)
442 critical_error_errno("calloc");
443 queue_data_block((u8 *)dind_block_data, info.block_size, dind_block);
445 u32 *ind_block_data = calloc(info.block_size, info.bg_desc_reserve_blocks);
447 critical_error_errno("calloc");
448 queue_data_block((u8 *)ind_block_data,
449 info.block_size * info.bg_desc_reserve_blocks,
450 get_block(alloc, 0));
452 for (i = 0; i < info.bg_desc_reserve_blocks; i++) {
453 int r = (i - aux_info.bg_desc_blocks) % info.bg_desc_reserve_blocks;
455 r += info.bg_desc_reserve_blocks;
457 dind_block_data[i] = get_block(alloc, r);
459 for (j = 1; j < superblocks; j++) {
460 u32 b = j * info.bg_desc_reserve_blocks + r;
461 ind_block_data[r * aux_info.blocks_per_ind + j - 1] = get_block(alloc, b);
465 u32 last_block = EXT4_NDIR_BLOCKS + aux_info.blocks_per_ind +
466 aux_info.blocks_per_ind * (info.bg_desc_reserve_blocks - 1) +
469 blocks = ((u64)block_len + 1) * info.block_size / 512;
470 size = (u64)last_block * info.block_size;
472 inode->i_block[EXT4_DIND_BLOCK] = dind_block;
474 inode->i_blocks_lo = blocks;
475 inode->osd2.linux2.l_i_blocks_high = blocks >> 32;
476 inode->i_size_lo = size;
477 inode->i_size_high = size >> 32;
480 /* Allocates enough blocks to hold len bytes, with backing_len bytes in a data
481 buffer, and connects them to an inode. Returns a pointer to the data
483 u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len,
484 unsigned long backing_len)
486 struct block_allocation *alloc;
489 alloc = do_inode_allocate_indirect(inode, len);
491 error("failed to allocate extents for %lu bytes", len);
496 data = create_backing(alloc, backing_len);
498 error("failed to create backing for %lu bytes", backing_len);