extent.c revision 8aef66d2125af8de7672a12895276802fcc1948f
1ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 2ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Copyright (C) 2010 The Android Open Source Project 3ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 4ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Licensed under the Apache License, Version 2.0 (the "License"); 5ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * you may not use this file except in compliance with the License. 6ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * You may obtain a copy of the License at 7ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 8ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * http://www.apache.org/licenses/LICENSE-2.0 9ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 10ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Unless required by applicable law or agreed to in writing, software 11ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * distributed under the License is distributed on an "AS IS" BASIS, 12ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * See the License for the specific language governing permissions and 14ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * limitations under the License. 15ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 16ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 17ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include <stdlib.h> 18ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include <stdio.h> 19ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 20ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "ext4_utils.h" 21ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "ext4.h" 22ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "ext4_extents.h" 23ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "backed_block.h" 24ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 25ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "extent.h" 26ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 27ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Creates data buffers for the first backing_len bytes of a block allocation 28ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and queues them to be written */ 29ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic u8 *extent_create_backing(struct block_allocation *alloc, 308aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len) 31ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 32ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = calloc(backing_len, 1); 33ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 34ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 35ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 36ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *ptr = data; 37ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { 38ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 39ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 40ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 len; 41ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 42ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 43ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = min(region_len * info.block_size, backing_len); 44ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 45ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross queue_data_block(ptr, len, region_block); 46ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr += len; 47ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross backing_len -= len; 48ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 49ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 50ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return data; 51ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 52ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 53ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Queues each chunk of a file to be written to contiguous data block 54ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross regions */ 55ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void extent_create_backing_file(struct block_allocation *alloc, 568aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len, const char *filename) 57ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 58ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross off_t offset = 0; 59ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { 60ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 61ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 62ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 len; 63ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 64ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 65ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = min(region_len * info.block_size, backing_len); 66ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 67ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross queue_data_file(filename, offset, len, region_block); 68ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross offset += len; 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross backing_len -= len; 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 73ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct block_allocation *do_inode_allocate_extents( 748aef66d2125af8de7672a12895276802fcc1948fColin Cross struct ext4_inode *inode, u64 len) 75ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 76ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block_len = DIV_ROUND_UP(len, info.block_size); 77ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = allocate_blocks(block_len + 1); 78ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 extent_block = 0; 79ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 file_block = 0; 80ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent *extent; 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u64 blocks; 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 83ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 84ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("Failed to allocate %d blocks\n", block_len + 1); 85ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 86ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 87ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 88ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int allocation_len = block_allocation_num_regions(alloc); 89ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (allocation_len <= 3) { 90ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reduce_allocation(alloc, 1); 91ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 92ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reserve_oob_blocks(alloc, 1); 93ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent_block = get_oob_block(alloc, 0); 94ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 95ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 96ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!extent_block) { 97ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_header *hdr = 988aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_header *)&inode->i_block[0]; 99ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 100ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = allocation_len; 101ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_max = 3; 102ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 103ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 0; 104ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 105ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent = (struct ext4_extent *)&inode->i_block[3]; 106ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 107ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_header *hdr = 1088aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_header *)&inode->i_block[0]; 109ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 110ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = 1; 111ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_max = 3; 112ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 113ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 1; 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_idx *idx = 1168aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_idx *)&inode->i_block[3]; 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_block = 0; 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_leaf_lo = extent_block; 119ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_leaf_hi = 0; 120ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_unused = 0; 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = calloc(info.block_size, 1); 123ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross queue_data_block(data, info.block_size, extent_block); 127ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 128ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (((int)(info.block_size - sizeof(struct ext4_extent_header) / 129ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross sizeof(struct ext4_extent))) < allocation_len) { 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("File size %llu is too big to fit in a single extent block\n", 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len); 132ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 133ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr = (struct ext4_extent_header *)data; 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 137ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = allocation_len; 1388aef66d2125af8de7672a12895276802fcc1948fColin Cross hdr->eh_max = (info.block_size - sizeof(struct ext4_extent_header)) / 1398aef66d2125af8de7672a12895276802fcc1948fColin Cross sizeof(struct ext4_extent); 140ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 141ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 0; 142ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1438aef66d2125af8de7672a12895276802fcc1948fColin Cross extent = (struct ext4_extent *)(data + 1448aef66d2125af8de7672a12895276802fcc1948fColin Cross sizeof(struct ext4_extent_header)); 145ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 146ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 147ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; !last_region(alloc); extent++, get_next_region(alloc)) { 148ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 152ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_block = file_block; 153ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_len = region_len; 154ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_start_hi = 0; 155ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_start_lo = region_block; 156ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross file_block += region_len; 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 158ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 159ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (extent_block) 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block_len += 1; 161ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 162ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks = (u64)block_len * info.block_size / 512; 163ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 164ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_flags |= EXT4_EXTENTS_FL; 165ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_size_lo = len; 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_size_high = len >> 32; 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_blocks_lo = blocks; 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->osd2.linux2.l_i_blocks_high = blocks >> 32; 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross rewind_alloc(alloc); 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data 176ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross buffer, and connects them to an inode. Returns a pointer to the data 177ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross buffer. */ 178ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, 1798aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len) 180ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 181ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 182ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = NULL; 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 185ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate extents for %llu bytes", len); 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 188ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (backing_len) { 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross data = extent_create_backing(alloc, backing_len); 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to create backing for %llu bytes", backing_len); 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return data; 199ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes, queues them to be written 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross from a file, and connects them to an inode. */ 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid inode_allocate_file_extents(struct ext4_inode *inode, u64 len, 2048aef66d2125af8de7672a12895276802fcc1948fColin Cross const char *filename) 205ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 206ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 207ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate extents for %llu bytes", len); 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 213ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent_create_backing_file(alloc, len, filename); 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes and connects them to an inode */ 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid inode_allocate_extents(struct ext4_inode *inode, u64 len) 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate extents for %llu bytes", len); 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 231ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 232