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 "extent.h" 18 19#include <inttypes.h> 20#include <stdlib.h> 21#include <stdio.h> 22 23#include <sparse/sparse.h> 24 25#include "allocate.h" 26#include "ext4_utils/ext4_utils.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 *extent_create_backing(struct block_allocation *alloc, 31 u64 backing_len) 32{ 33 u8 *data = calloc(backing_len, 1); 34 if (!data) 35 critical_error_errno("calloc"); 36 37 u8 *ptr = data; 38 for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { 39 u32 region_block; 40 u32 region_len; 41 u32 len; 42 get_region(alloc, ®ion_block, ®ion_len); 43 44 len = min(region_len * info.block_size, backing_len); 45 46 sparse_file_add_data(ext4_sparse_file, ptr, len, region_block); 47 ptr += len; 48 backing_len -= len; 49 } 50 51 return data; 52} 53 54/* Queues each chunk of a file to be written to contiguous data block 55 regions */ 56static void extent_create_backing_file(struct block_allocation *alloc, 57 u64 backing_len, const char *filename) 58{ 59 off64_t offset = 0; 60 for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { 61 u32 region_block; 62 u32 region_len; 63 u32 len; 64 get_region(alloc, ®ion_block, ®ion_len); 65 66 len = min(region_len * info.block_size, backing_len); 67 68 sparse_file_add_file(ext4_sparse_file, filename, offset, len, 69 region_block); 70 offset += len; 71 backing_len -= len; 72 } 73} 74 75static struct block_allocation *do_inode_allocate_extents( 76 struct ext4_inode *inode, u64 len, struct block_allocation *prealloc) 77{ 78 u32 block_len = DIV_ROUND_UP(len, info.block_size), prealloc_block_len; 79 struct block_allocation *alloc; 80 u32 extent_block = 0; 81 u32 file_block = 0; 82 struct ext4_extent *extent; 83 u64 blocks; 84 85 if (!prealloc) { 86 alloc = allocate_blocks(block_len + 1); 87 if (alloc == NULL) { 88 error("Failed to allocate %d blocks\n", block_len + 1); 89 return NULL; 90 } 91 } else { 92 prealloc_block_len = block_allocation_len(prealloc); 93 if (block_len + 1 > prealloc_block_len) { 94 alloc = allocate_blocks(block_len + 1 - prealloc_block_len); 95 if (alloc == NULL) { 96 error("Failed to allocate %d blocks\n", 97 block_len + 1 - prealloc_block_len); 98 return NULL; 99 } 100 region_list_merge(&prealloc->list, &alloc->list); 101 free(alloc); 102 } 103 alloc = prealloc; 104 } 105 106 int allocation_len = block_allocation_num_regions(alloc); 107 if (allocation_len <= 3) { 108 reduce_allocation(alloc, 1); 109 // IMPORTANT: reduce_allocation may have changed allocation 110 // length, otherwise file corruption happens when fs thinks 111 // a block is missing from extent header. 112 allocation_len = block_allocation_num_regions(alloc); 113 } else { 114 reserve_oob_blocks(alloc, 1); 115 extent_block = get_oob_block(alloc, 0); 116 } 117 118 if (!extent_block) { 119 struct ext4_extent_header *hdr = 120 (struct ext4_extent_header *)&inode->i_block[0]; 121 hdr->eh_magic = EXT4_EXT_MAGIC; 122 hdr->eh_entries = allocation_len; 123 hdr->eh_max = 3; 124 hdr->eh_generation = 0; 125 hdr->eh_depth = 0; 126 127 extent = (struct ext4_extent *)&inode->i_block[3]; 128 } else { 129 struct ext4_extent_header *hdr = 130 (struct ext4_extent_header *)&inode->i_block[0]; 131 hdr->eh_magic = EXT4_EXT_MAGIC; 132 hdr->eh_entries = 1; 133 hdr->eh_max = 3; 134 hdr->eh_generation = 0; 135 hdr->eh_depth = 1; 136 137 struct ext4_extent_idx *idx = 138 (struct ext4_extent_idx *)&inode->i_block[3]; 139 idx->ei_block = 0; 140 idx->ei_leaf_lo = extent_block; 141 idx->ei_leaf_hi = 0; 142 idx->ei_unused = 0; 143 144 u8 *data = calloc(info.block_size, 1); 145 if (!data) 146 critical_error_errno("calloc"); 147 148 sparse_file_add_data(ext4_sparse_file, data, info.block_size, 149 extent_block); 150 151 if (((int)(info.block_size - sizeof(struct ext4_extent_header) / 152 sizeof(struct ext4_extent))) < allocation_len) { 153 error("File size %"PRIu64" is too big to fit in a single extent block\n", 154 len); 155 return NULL; 156 } 157 158 hdr = (struct ext4_extent_header *)data; 159 hdr->eh_magic = EXT4_EXT_MAGIC; 160 hdr->eh_entries = allocation_len; 161 hdr->eh_max = (info.block_size - sizeof(struct ext4_extent_header)) / 162 sizeof(struct ext4_extent); 163 hdr->eh_generation = 0; 164 hdr->eh_depth = 0; 165 166 extent = (struct ext4_extent *)(data + 167 sizeof(struct ext4_extent_header)); 168 } 169 170 for (; !last_region(alloc); extent++, get_next_region(alloc)) { 171 u32 region_block; 172 u32 region_len; 173 174 get_region(alloc, ®ion_block, ®ion_len); 175 extent->ee_block = file_block; 176 extent->ee_len = region_len; 177 extent->ee_start_hi = 0; 178 extent->ee_start_lo = region_block; 179 file_block += region_len; 180 } 181 182 if (extent_block) 183 block_len += 1; 184 185 blocks = (u64)block_len * info.block_size / 512; 186 187 inode->i_flags |= EXT4_EXTENTS_FL; 188 inode->i_size_lo = len; 189 inode->i_size_high = len >> 32; 190 inode->i_blocks_lo = blocks; 191 inode->osd2.linux2.l_i_blocks_high = blocks >> 32; 192 193 rewind_alloc(alloc); 194 195 return alloc; 196} 197 198/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data 199 buffer, and connects them to an inode. Returns a pointer to the data 200 buffer. */ 201u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, 202 u64 backing_len) 203{ 204 struct block_allocation *alloc; 205 u8 *data = NULL; 206 207 alloc = do_inode_allocate_extents(inode, len, NULL); 208 if (alloc == NULL) { 209 error("failed to allocate extents for %"PRIu64" bytes", len); 210 return NULL; 211 } 212 213 if (backing_len) { 214 data = extent_create_backing(alloc, backing_len); 215 if (!data) 216 error("failed to create backing for %"PRIu64" bytes", backing_len); 217 } 218 219 free_alloc(alloc); 220 221 return data; 222} 223 224/* Allocates enough blocks to hold len bytes, queues them to be written 225 from a file, and connects them to an inode. */ 226struct block_allocation* inode_allocate_file_extents(struct ext4_inode *inode, u64 len, 227 const char *filename) 228{ 229 struct block_allocation *alloc, *prealloc = base_fs_allocations, *prev_prealloc = NULL; 230 // TODO(mkayyash): base_fs_allocations is sorted by filename, consider 231 // storing it in an array and then binary searching for a filename match instead 232 while (prealloc && prealloc->filename != NULL) { 233 if (!strcmp(filename, prealloc->filename)) { 234 break; 235 } 236 prev_prealloc = prealloc; 237 prealloc = prealloc->next; 238 } 239 if (prealloc) { 240 if (!prev_prealloc) { 241 base_fs_allocations = base_fs_allocations->next; 242 } else { 243 prev_prealloc->next = prealloc->next; 244 } 245 prealloc->next = NULL; 246 } 247 248 alloc = do_inode_allocate_extents(inode, len, prealloc); 249 if (alloc == NULL) { 250 error("failed to allocate extents for %"PRIu64" bytes", len); 251 return NULL; 252 } 253 254 extent_create_backing_file(alloc, len, filename); 255 return alloc; 256} 257 258/* Allocates enough blocks to hold len bytes and connects them to an inode */ 259void inode_allocate_extents(struct ext4_inode *inode, u64 len) 260{ 261 struct block_allocation *alloc; 262 263 alloc = do_inode_allocate_extents(inode, len, NULL); 264 if (alloc == NULL) { 265 error("failed to allocate extents for %"PRIu64" bytes", len); 266 return; 267 } 268 269 free_alloc(alloc); 270} 271