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