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 "ext4_utils.h" 18ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "extent.h" 19ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 20dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross#include <sparse/sparse.h> 21dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross 22af0723439af552c170425416ee8e35f4f20bbe67Colin Cross#include <inttypes.h> 2333f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdlib.h> 2433f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdio.h> 2533f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross 2633f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin 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 45782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, 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{ 5833f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross off64_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 67782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_file(ext4_sparse_file, filename, offset, len, 68f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross region_block); 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross offset += len; 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross backing_len -= len; 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 73ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 74ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct block_allocation *do_inode_allocate_extents( 758aef66d2125af8de7672a12895276802fcc1948fColin Cross struct ext4_inode *inode, u64 len) 76ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 77ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block_len = DIV_ROUND_UP(len, info.block_size); 78ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = allocate_blocks(block_len + 1); 79ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 extent_block = 0; 80ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 file_block = 0; 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent *extent; 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u64 blocks; 83ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 84ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 85ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("Failed to allocate %d blocks\n", block_len + 1); 86ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 87ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 88ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 89ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int allocation_len = block_allocation_num_regions(alloc); 90ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (allocation_len <= 3) { 91ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reduce_allocation(alloc, 1); 92ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 93ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reserve_oob_blocks(alloc, 1); 94ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent_block = get_oob_block(alloc, 0); 95ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 96ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 97ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!extent_block) { 98ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_header *hdr = 998aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_header *)&inode->i_block[0]; 100ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 101ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = allocation_len; 102ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_max = 3; 103ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 104ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 0; 105ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 106ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent = (struct ext4_extent *)&inode->i_block[3]; 107ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 108ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_header *hdr = 1098aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_header *)&inode->i_block[0]; 110ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 111ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = 1; 112ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_max = 3; 113ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 1; 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_idx *idx = 1178aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_idx *)&inode->i_block[3]; 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_block = 0; 119ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_leaf_lo = extent_block; 120ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_leaf_hi = 0; 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_unused = 0; 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 123ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = calloc(info.block_size, 1); 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 127782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, data, info.block_size, 128f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross extent_block); 129ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (((int)(info.block_size - sizeof(struct ext4_extent_header) / 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross sizeof(struct ext4_extent))) < allocation_len) { 132af0723439af552c170425416ee8e35f4f20bbe67Colin Cross error("File size %"PRIu64" is too big to fit in a single extent block\n", 133ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len); 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 137ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr = (struct ext4_extent_header *)data; 138ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 139ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = allocation_len; 1408aef66d2125af8de7672a12895276802fcc1948fColin Cross hdr->eh_max = (info.block_size - sizeof(struct ext4_extent_header)) / 1418aef66d2125af8de7672a12895276802fcc1948fColin Cross sizeof(struct ext4_extent); 142ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 143ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 0; 144ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1458aef66d2125af8de7672a12895276802fcc1948fColin Cross extent = (struct ext4_extent *)(data + 1468aef66d2125af8de7672a12895276802fcc1948fColin Cross sizeof(struct ext4_extent_header)); 147ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 148ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; !last_region(alloc); extent++, get_next_region(alloc)) { 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 152ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 153ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 154ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_block = file_block; 155ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_len = region_len; 156ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_start_hi = 0; 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_start_lo = region_block; 158ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross file_block += region_len; 159ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 161ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (extent_block) 162ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block_len += 1; 163ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 164ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks = (u64)block_len * info.block_size / 512; 165ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_flags |= EXT4_EXTENTS_FL; 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_size_lo = len; 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_size_high = len >> 32; 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_blocks_lo = blocks; 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->osd2.linux2.l_i_blocks_high = blocks >> 32; 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross rewind_alloc(alloc); 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 176ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 177ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data 178ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross buffer, and connects them to an inode. Returns a pointer to the data 179ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross buffer. */ 180ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, 1818aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len) 182ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = NULL; 185ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 188af0723439af552c170425416ee8e35f4f20bbe67Colin Cross error("failed to allocate extents for %"PRIu64" bytes", len); 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (backing_len) { 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross data = extent_create_backing(alloc, backing_len); 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 195af0723439af552c170425416ee8e35f4f20bbe67Colin Cross error("failed to create backing for %"PRIu64" bytes", backing_len); 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 199ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return data; 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes, queues them to be written 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross from a file, and connects them to an inode. */ 205bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongkerstruct block_allocation* inode_allocate_file_extents(struct ext4_inode *inode, u64 len, 2068aef66d2125af8de7672a12895276802fcc1948fColin Cross const char *filename) 207ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 212af0723439af552c170425416ee8e35f4f20bbe67Colin Cross error("failed to allocate extents for %"PRIu64" bytes", len); 2139922135de65b717267d8173f61e360fbb9cf1ebdDoug Zongker return NULL; 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent_create_backing_file(alloc, len, filename); 2179922135de65b717267d8173f61e360fbb9cf1ebdDoug Zongker return alloc; 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes and connects them to an inode */ 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid inode_allocate_extents(struct ext4_inode *inode, u64 len) 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 227af0723439af552c170425416ee8e35f4f20bbe67Colin Cross error("failed to allocate extents for %"PRIu64" bytes", len); 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 231ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 233