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 "ext4.h" 19ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "ext4_extents.h" 20ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "extent.h" 21ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 22dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross#include <sparse/sparse.h> 23dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross 2433f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdlib.h> 2533f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdio.h> 2633f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross 2733f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross 28ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Creates data buffers for the first backing_len bytes of a block allocation 29ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and queues them to be written */ 30ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic u8 *extent_create_backing(struct block_allocation *alloc, 318aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len) 32ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 33ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = calloc(backing_len, 1); 34ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 35ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 36ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 37ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *ptr = data; 38ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { 39ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 40ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 41ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 len; 42ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 43ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 44ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = min(region_len * info.block_size, backing_len); 45ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 46f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross sparse_file_add_data(info.sparse_file, ptr, len, region_block); 47ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross ptr += len; 48ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross backing_len -= len; 49ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 50ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 51ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return data; 52ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 53ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 54ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Queues each chunk of a file to be written to contiguous data block 55ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross regions */ 56ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void extent_create_backing_file(struct block_allocation *alloc, 578aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len, const char *filename) 58ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5933f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross off64_t offset = 0; 60ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { 61ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 62ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 63ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 len; 64ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 65ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 66ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = min(region_len * info.block_size, backing_len); 67ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 68f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross sparse_file_add_file(info.sparse_file, filename, offset, len, 69f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross region_block); 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross offset += len; 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross backing_len -= len; 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 73ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 74ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 75ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct block_allocation *do_inode_allocate_extents( 768aef66d2125af8de7672a12895276802fcc1948fColin Cross struct ext4_inode *inode, u64 len) 77ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 78ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block_len = DIV_ROUND_UP(len, info.block_size); 79ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = allocate_blocks(block_len + 1); 80ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 extent_block = 0; 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 file_block = 0; 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent *extent; 83ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u64 blocks; 84ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 85ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 86ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("Failed to allocate %d blocks\n", block_len + 1); 87ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 88ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 89ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 90ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int allocation_len = block_allocation_num_regions(alloc); 91ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (allocation_len <= 3) { 92ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reduce_allocation(alloc, 1); 93ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 94ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reserve_oob_blocks(alloc, 1); 95ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent_block = get_oob_block(alloc, 0); 96ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 97ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 98ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!extent_block) { 99ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_header *hdr = 1008aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_header *)&inode->i_block[0]; 101ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 102ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = allocation_len; 103ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_max = 3; 104ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 105ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 0; 106ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 107ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent = (struct ext4_extent *)&inode->i_block[3]; 108ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 109ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_header *hdr = 1108aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_header *)&inode->i_block[0]; 111ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 112ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = 1; 113ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_max = 3; 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 1; 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct ext4_extent_idx *idx = 1188aef66d2125af8de7672a12895276802fcc1948fColin Cross (struct ext4_extent_idx *)&inode->i_block[3]; 119ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_block = 0; 120ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_leaf_lo = extent_block; 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_leaf_hi = 0; 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross idx->ei_unused = 0; 123ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = calloc(info.block_size, 1); 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 127ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 128f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross sparse_file_add_data(info.sparse_file, data, info.block_size, 129f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross extent_block); 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (((int)(info.block_size - sizeof(struct ext4_extent_header) / 132ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross sizeof(struct ext4_extent))) < allocation_len) { 133ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("File size %llu is too big to fit in a single extent block\n", 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len); 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 137ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 138ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr = (struct ext4_extent_header *)data; 139ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_magic = EXT4_EXT_MAGIC; 140ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_entries = allocation_len; 1418aef66d2125af8de7672a12895276802fcc1948fColin Cross hdr->eh_max = (info.block_size - sizeof(struct ext4_extent_header)) / 1428aef66d2125af8de7672a12895276802fcc1948fColin Cross sizeof(struct ext4_extent); 143ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_generation = 0; 144ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross hdr->eh_depth = 0; 145ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1468aef66d2125af8de7672a12895276802fcc1948fColin Cross extent = (struct ext4_extent *)(data + 1478aef66d2125af8de7672a12895276802fcc1948fColin Cross sizeof(struct ext4_extent_header)); 148ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; !last_region(alloc); extent++, get_next_region(alloc)) { 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_block; 152ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 region_len; 153ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 154ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross get_region(alloc, ®ion_block, ®ion_len); 155ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_block = file_block; 156ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_len = region_len; 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_start_hi = 0; 158ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent->ee_start_lo = region_block; 159ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross file_block += region_len; 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 161ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 162ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (extent_block) 163ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block_len += 1; 164ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 165ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks = (u64)block_len * info.block_size / 512; 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_flags |= EXT4_EXTENTS_FL; 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_size_lo = len; 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_size_high = len >> 32; 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->i_blocks_lo = blocks; 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode->osd2.linux2.l_i_blocks_high = blocks >> 32; 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross rewind_alloc(alloc); 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 176ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 177ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 178ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data 179ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross buffer, and connects them to an inode. Returns a pointer to the data 180ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross buffer. */ 181ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, 1828aef66d2125af8de7672a12895276802fcc1948fColin Cross u64 backing_len) 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 185ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *data = NULL; 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 188ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate extents for %llu bytes", len); 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (backing_len) { 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross data = extent_create_backing(alloc, backing_len); 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (!data) 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to create backing for %llu bytes", backing_len); 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 199ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return data; 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes, queues them to be written 205ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross from a file, and connects them to an inode. */ 206ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid inode_allocate_file_extents(struct ext4_inode *inode, u64 len, 2078aef66d2125af8de7672a12895276802fcc1948fColin Cross const char *filename) 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 213ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate extents for %llu bytes", len); 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross extent_create_backing_file(alloc, len, filename); 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocates enough blocks to hold len bytes and connects them to an inode */ 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid inode_allocate_extents(struct ext4_inode *inode, u64 len) 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc; 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc = do_inode_allocate_extents(inode, len); 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (alloc == NULL) { 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate extents for %llu bytes", len); 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 231ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 233ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_alloc(alloc); 234ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 235