ext4_utils/extent.c

   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 */
  30 static 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, &region_block, &region_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 */
  56 static 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, &region_block, &region_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
  75 static 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, &region_block, &region_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. */
 201 u8 *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. */
 226 struct 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 */
 259 void 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 }