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 "allocate.h" 19#include "indirect.h" 20#include "extent.h" 21#include "sha1.h" 22 23#include <sparse/sparse.h> 24#ifdef REAL_UUID 25#include <uuid.h> 26#endif 27 28#include <fcntl.h> 29#include <inttypes.h> 30#include <sys/stat.h> 31#include <sys/types.h> 32#include <stddef.h> 33#include <string.h> 34 35#ifdef USE_MINGW 36#include <winsock2.h> 37#else 38#include <arpa/inet.h> 39#include <sys/ioctl.h> 40#endif 41 42#if defined(__linux__) 43#include <linux/fs.h> 44#elif defined(__APPLE__) && defined(__MACH__) 45#include <sys/disk.h> 46#endif 47 48int force = 0; 49struct fs_info info; 50struct fs_aux_info aux_info; 51struct sparse_file *ext4_sparse_file; 52struct block_allocation *base_fs_allocations = NULL; 53 54jmp_buf setjmp_env; 55 56/* Definition from RFC-4122 */ 57struct uuid { 58 u32 time_low; 59 u16 time_mid; 60 u16 time_hi_and_version; 61 u8 clk_seq_hi_res; 62 u8 clk_seq_low; 63 u16 node0_1; 64 u32 node2_5; 65}; 66 67static void sha1_hash(const char *namespace, const char *name, 68 unsigned char sha1[SHA1_DIGEST_LENGTH]) 69{ 70 SHA1_CTX ctx; 71 SHA1Init(&ctx); 72 SHA1Update(&ctx, (const u8*)namespace, strlen(namespace)); 73 SHA1Update(&ctx, (const u8*)name, strlen(name)); 74 SHA1Final(sha1, &ctx); 75} 76 77static void generate_sha1_uuid(const char *namespace, const char *name, u8 result[16]) 78{ 79 unsigned char sha1[SHA1_DIGEST_LENGTH]; 80 struct uuid *uuid = (struct uuid *)result; 81 82 sha1_hash(namespace, name, (unsigned char*)sha1); 83 memcpy(uuid, sha1, sizeof(struct uuid)); 84 85 uuid->time_low = ntohl(uuid->time_low); 86 uuid->time_mid = ntohs(uuid->time_mid); 87 uuid->time_hi_and_version = ntohs(uuid->time_hi_and_version); 88 uuid->time_hi_and_version &= 0x0FFF; 89 uuid->time_hi_and_version |= (5 << 12); 90 uuid->clk_seq_hi_res &= ~(1 << 6); 91 uuid->clk_seq_hi_res |= 1 << 7; 92} 93 94/* returns 1 if a is a power of b */ 95static int is_power_of(int a, int b) 96{ 97 while (a > b) { 98 if (a % b) 99 return 0; 100 a /= b; 101 } 102 103 return (a == b) ? 1 : 0; 104} 105 106int bitmap_get_bit(u8 *bitmap, u32 bit) 107{ 108 if (bitmap[bit / 8] & (1 << (bit % 8))) 109 return 1; 110 111 return 0; 112} 113 114void bitmap_clear_bit(u8 *bitmap, u32 bit) 115{ 116 bitmap[bit / 8] &= ~(1 << (bit % 8)); 117 118 return; 119} 120 121/* Returns 1 if the bg contains a backup superblock. On filesystems with 122 the sparse_super feature, only block groups 0, 1, and powers of 3, 5, 123 and 7 have backup superblocks. Otherwise, all block groups have backup 124 superblocks */ 125int ext4_bg_has_super_block(int bg) 126{ 127 /* Without sparse_super, every block group has a superblock */ 128 if (!(info.feat_ro_compat & EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER)) 129 return 1; 130 131 if (bg == 0 || bg == 1) 132 return 1; 133 134 if (is_power_of(bg, 3) || is_power_of(bg, 5) || is_power_of(bg, 7)) 135 return 1; 136 137 return 0; 138} 139 140/* Function to read the primary superblock */ 141void read_sb(int fd, struct ext4_super_block *sb) 142{ 143 off64_t ret; 144 145 ret = lseek64(fd, 1024, SEEK_SET); 146 if (ret < 0) 147 critical_error_errno("failed to seek to superblock"); 148 149 ret = read(fd, sb, sizeof(*sb)); 150 if (ret < 0) 151 critical_error_errno("failed to read superblock"); 152 if (ret != sizeof(*sb)) 153 critical_error("failed to read all of superblock"); 154} 155 156/* Function to write a primary or backup superblock at a given offset */ 157void write_sb(int fd, unsigned long long offset, struct ext4_super_block *sb) 158{ 159 off64_t ret; 160 161 ret = lseek64(fd, offset, SEEK_SET); 162 if (ret < 0) 163 critical_error_errno("failed to seek to superblock"); 164 165 ret = write(fd, sb, sizeof(*sb)); 166 if (ret < 0) 167 critical_error_errno("failed to write superblock"); 168 if (ret != sizeof(*sb)) 169 critical_error("failed to write all of superblock"); 170} 171 172static void block_device_write_sb(int fd) 173{ 174 unsigned long long offset; 175 u32 i; 176 177 /* write out the backup superblocks */ 178 for (i = 1; i < aux_info.groups; i++) { 179 if (ext4_bg_has_super_block(i)) { 180 offset = info.block_size * (aux_info.first_data_block 181 + i * info.blocks_per_group); 182 write_sb(fd, offset, aux_info.backup_sb[i]); 183 } 184 } 185 186 /* write out the primary superblock */ 187 write_sb(fd, 1024, aux_info.sb); 188} 189 190/* Write the filesystem image to a file */ 191void write_ext4_image(int fd, int gz, int sparse, int crc) 192{ 193 sparse_file_write(ext4_sparse_file, fd, gz, sparse, crc); 194 195 if (info.block_device) 196 block_device_write_sb(fd); 197} 198 199/* Compute the rest of the parameters of the filesystem from the basic info */ 200void ext4_create_fs_aux_info() 201{ 202 aux_info.first_data_block = (info.block_size > 1024) ? 0 : 1; 203 aux_info.len_blocks = info.len / info.block_size; 204 aux_info.inode_table_blocks = DIV_ROUND_UP(info.inodes_per_group * info.inode_size, 205 info.block_size); 206 aux_info.groups = DIV_ROUND_UP(aux_info.len_blocks - aux_info.first_data_block, 207 info.blocks_per_group); 208 aux_info.blocks_per_ind = info.block_size / sizeof(u32); 209 aux_info.blocks_per_dind = aux_info.blocks_per_ind * aux_info.blocks_per_ind; 210 aux_info.blocks_per_tind = aux_info.blocks_per_dind * aux_info.blocks_per_dind; 211 212 aux_info.bg_desc_blocks = 213 DIV_ROUND_UP(aux_info.groups * sizeof(struct ext2_group_desc), 214 info.block_size); 215 216 aux_info.default_i_flags = EXT4_NOATIME_FL; 217 218 u32 last_group_size = aux_info.len_blocks % info.blocks_per_group; 219 u32 last_header_size = 2 + aux_info.inode_table_blocks; 220 if (ext4_bg_has_super_block(aux_info.groups - 1)) 221 last_header_size += 1 + aux_info.bg_desc_blocks + 222 info.bg_desc_reserve_blocks; 223 if (last_group_size > 0 && last_group_size < last_header_size) { 224 aux_info.groups--; 225 aux_info.len_blocks -= last_group_size; 226 } 227 228 /* A zero-filled superblock to be written firstly to the block 229 * device to mark the file-system as invalid 230 */ 231 aux_info.sb_zero = calloc(1, info.block_size); 232 if (!aux_info.sb_zero) 233 critical_error_errno("calloc"); 234 235 /* The write_data* functions expect only block aligned calls. 236 * This is not an issue, except when we write out the super 237 * block on a system with a block size > 1K. So, we need to 238 * deal with that here. 239 */ 240 aux_info.sb_block = calloc(1, info.block_size); 241 if (!aux_info.sb_block) 242 critical_error_errno("calloc"); 243 244 if (info.block_size > 1024) 245 aux_info.sb = (struct ext4_super_block *)((char *)aux_info.sb_block + 1024); 246 else 247 aux_info.sb = aux_info.sb_block; 248 249 /* Alloc an array to hold the pointers to the backup superblocks */ 250 aux_info.backup_sb = calloc(aux_info.groups, sizeof(char *)); 251 252 if (!aux_info.sb) 253 critical_error_errno("calloc"); 254 255 aux_info.bg_desc = calloc(info.block_size, aux_info.bg_desc_blocks); 256 if (!aux_info.bg_desc) 257 critical_error_errno("calloc"); 258 aux_info.xattrs = NULL; 259} 260 261void ext4_free_fs_aux_info() 262{ 263 unsigned int i; 264 265 for (i=0; i<aux_info.groups; i++) { 266 if (aux_info.backup_sb[i]) 267 free(aux_info.backup_sb[i]); 268 } 269 free(aux_info.sb_block); 270 free(aux_info.sb_zero); 271 free(aux_info.bg_desc); 272} 273 274/* Fill in the superblock memory buffer based on the filesystem parameters */ 275void ext4_fill_in_sb(int real_uuid) 276{ 277 unsigned int i; 278 struct ext4_super_block *sb = aux_info.sb; 279 280 sb->s_inodes_count = info.inodes_per_group * aux_info.groups; 281 sb->s_blocks_count_lo = aux_info.len_blocks; 282 sb->s_r_blocks_count_lo = 0; 283 sb->s_free_blocks_count_lo = 0; 284 sb->s_free_inodes_count = 0; 285 sb->s_first_data_block = aux_info.first_data_block; 286 sb->s_log_block_size = log_2(info.block_size / 1024); 287 sb->s_obso_log_frag_size = log_2(info.block_size / 1024); 288 sb->s_blocks_per_group = info.blocks_per_group; 289 sb->s_obso_frags_per_group = info.blocks_per_group; 290 sb->s_inodes_per_group = info.inodes_per_group; 291 sb->s_mtime = 0; 292 sb->s_wtime = 0; 293 sb->s_mnt_count = 0; 294 sb->s_max_mnt_count = 10; 295 sb->s_magic = EXT4_SUPER_MAGIC; 296 sb->s_state = EXT4_VALID_FS; 297 sb->s_errors = EXT4_ERRORS_RO; 298 sb->s_minor_rev_level = 0; 299 sb->s_lastcheck = 0; 300 sb->s_checkinterval = 0; 301 sb->s_creator_os = EXT4_OS_LINUX; 302 sb->s_rev_level = EXT4_DYNAMIC_REV; 303 sb->s_def_resuid = EXT4_DEF_RESUID; 304 sb->s_def_resgid = EXT4_DEF_RESGID; 305 306 sb->s_first_ino = EXT4_GOOD_OLD_FIRST_INO; 307 sb->s_inode_size = info.inode_size; 308 sb->s_block_group_nr = 0; 309 sb->s_feature_compat = info.feat_compat; 310 sb->s_feature_incompat = info.feat_incompat; 311 sb->s_feature_ro_compat = info.feat_ro_compat; 312 if (real_uuid == 1) { 313#ifdef REAL_UUID 314 uuid_generate(sb->s_uuid); 315#else 316 fprintf(stderr, "Not compiled with real UUID support\n"); 317 abort(); 318#endif 319 } else { 320 generate_sha1_uuid("extandroid/make_ext4fs", info.label, sb->s_uuid); 321 } 322 memset(sb->s_volume_name, 0, sizeof(sb->s_volume_name)); 323 strncpy(sb->s_volume_name, info.label, sizeof(sb->s_volume_name)); 324 memset(sb->s_last_mounted, 0, sizeof(sb->s_last_mounted)); 325 sb->s_algorithm_usage_bitmap = 0; 326 327 sb->s_reserved_gdt_blocks = info.bg_desc_reserve_blocks; 328 sb->s_prealloc_blocks = 0; 329 sb->s_prealloc_dir_blocks = 0; 330 331 //memcpy(sb->s_journal_uuid, sb->s_uuid, sizeof(sb->s_journal_uuid)); 332 if (info.feat_compat & EXT4_FEATURE_COMPAT_HAS_JOURNAL) 333 sb->s_journal_inum = EXT4_JOURNAL_INO; 334 sb->s_journal_dev = 0; 335 sb->s_last_orphan = 0; 336 sb->s_hash_seed[0] = 0; /* FIXME */ 337 sb->s_def_hash_version = DX_HASH_TEA; 338 sb->s_reserved_char_pad = EXT4_JNL_BACKUP_BLOCKS; 339 sb->s_desc_size = sizeof(struct ext2_group_desc); 340 sb->s_default_mount_opts = 0; /* FIXME */ 341 sb->s_first_meta_bg = 0; 342 sb->s_mkfs_time = 0; 343 //sb->s_jnl_blocks[17]; /* FIXME */ 344 345 sb->s_blocks_count_hi = aux_info.len_blocks >> 32; 346 sb->s_r_blocks_count_hi = 0; 347 sb->s_free_blocks_count_hi = 0; 348 sb->s_min_extra_isize = sizeof(struct ext4_inode) - 349 EXT4_GOOD_OLD_INODE_SIZE; 350 sb->s_want_extra_isize = sizeof(struct ext4_inode) - 351 EXT4_GOOD_OLD_INODE_SIZE; 352 sb->s_flags = 2; 353 sb->s_raid_stride = 0; 354 sb->s_mmp_interval = 0; 355 sb->s_mmp_block = 0; 356 sb->s_raid_stripe_width = 0; 357 sb->s_log_groups_per_flex = 0; 358 sb->s_kbytes_written = 0; 359 360 for (i = 0; i < aux_info.groups; i++) { 361 u64 group_start_block = aux_info.first_data_block + i * 362 info.blocks_per_group; 363 u32 header_size = 0; 364 if (ext4_bg_has_super_block(i)) { 365 if (i != 0) { 366 aux_info.backup_sb[i] = calloc(info.block_size, 1); 367 memcpy(aux_info.backup_sb[i], sb, sizeof(struct ext4_super_block)); 368 /* Update the block group nr of this backup superblock */ 369 aux_info.backup_sb[i]->s_block_group_nr = i; 370 ext4_queue_sb(group_start_block, info.block_device ? 371 aux_info.sb_zero : aux_info.backup_sb[i]); 372 } 373 sparse_file_add_data(ext4_sparse_file, aux_info.bg_desc, 374 aux_info.bg_desc_blocks * info.block_size, 375 group_start_block + 1); 376 header_size = 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 377 } 378 379 aux_info.bg_desc[i].bg_block_bitmap = group_start_block + header_size; 380 aux_info.bg_desc[i].bg_inode_bitmap = group_start_block + header_size + 1; 381 aux_info.bg_desc[i].bg_inode_table = group_start_block + header_size + 2; 382 383 aux_info.bg_desc[i].bg_free_blocks_count = sb->s_blocks_per_group; 384 aux_info.bg_desc[i].bg_free_inodes_count = sb->s_inodes_per_group; 385 aux_info.bg_desc[i].bg_used_dirs_count = 0; 386 } 387 388 /* Queue the primary superblock to be written out - if it's a block device, 389 * queue a zero-filled block first, the correct version of superblock will 390 * be written to the block device after all other blocks are written. 391 * 392 * The file-system on the block device will not be valid until the correct 393 * version of superblocks are written, this is to avoid the likelihood of a 394 * partially created file-system. 395 */ 396 ext4_queue_sb(aux_info.first_data_block, info.block_device ? 397 aux_info.sb_zero : aux_info.sb_block); 398} 399 400 401void ext4_queue_sb(u64 start_block, struct ext4_super_block *sb) 402{ 403 sparse_file_add_data(ext4_sparse_file, sb, info.block_size, start_block); 404} 405 406void ext4_parse_sb_info(struct ext4_super_block *sb) 407{ 408 if (sb->s_magic != EXT4_SUPER_MAGIC) 409 error("superblock magic incorrect"); 410 411 if ((sb->s_state & EXT4_VALID_FS) != EXT4_VALID_FS) 412 error("filesystem state not valid"); 413 414 ext4_parse_sb(sb, &info); 415 416 ext4_create_fs_aux_info(); 417 418 memcpy(aux_info.sb, sb, sizeof(*sb)); 419 420 if (aux_info.first_data_block != sb->s_first_data_block) 421 critical_error("first data block does not match"); 422} 423 424void ext4_create_resize_inode() 425{ 426 struct block_allocation *reserve_inode_alloc = create_allocation(); 427 u32 reserve_inode_len = 0; 428 unsigned int i; 429 430 struct ext4_inode *inode = get_inode(EXT4_RESIZE_INO); 431 if (inode == NULL) { 432 error("failed to get resize inode"); 433 return; 434 } 435 436 for (i = 0; i < aux_info.groups; i++) { 437 if (ext4_bg_has_super_block(i)) { 438 u64 group_start_block = aux_info.first_data_block + i * 439 info.blocks_per_group; 440 u32 reserved_block_start = group_start_block + 1 + 441 aux_info.bg_desc_blocks; 442 u32 reserved_block_len = info.bg_desc_reserve_blocks; 443 append_region(reserve_inode_alloc, reserved_block_start, 444 reserved_block_len, i); 445 reserve_inode_len += reserved_block_len; 446 } 447 } 448 449 inode_attach_resize(inode, reserve_inode_alloc); 450 451 inode->i_mode = S_IFREG | S_IRUSR | S_IWUSR; 452 inode->i_links_count = 1; 453 454 free_alloc(reserve_inode_alloc); 455} 456 457/* Allocate the blocks to hold a journal inode and connect them to the 458 reserved journal inode */ 459void ext4_create_journal_inode() 460{ 461 struct ext4_inode *inode = get_inode(EXT4_JOURNAL_INO); 462 if (inode == NULL) { 463 error("failed to get journal inode"); 464 return; 465 } 466 467 u8 *journal_data = inode_allocate_data_extents(inode, 468 info.journal_blocks * info.block_size, 469 info.journal_blocks * info.block_size); 470 if (!journal_data) { 471 error("failed to allocate extents for journal data"); 472 return; 473 } 474 475 inode->i_mode = S_IFREG | S_IRUSR | S_IWUSR; 476 inode->i_links_count = 1; 477 478 journal_superblock_t *jsb = (journal_superblock_t *)journal_data; 479 jsb->s_header.h_magic = htonl(JBD2_MAGIC_NUMBER); 480 jsb->s_header.h_blocktype = htonl(JBD2_SUPERBLOCK_V2); 481 jsb->s_blocksize = htonl(info.block_size); 482 jsb->s_maxlen = htonl(info.journal_blocks); 483 jsb->s_nr_users = htonl(1); 484 jsb->s_first = htonl(1); 485 jsb->s_sequence = htonl(1); 486 487 memcpy(aux_info.sb->s_jnl_blocks, &inode->i_block, sizeof(inode->i_block)); 488} 489 490/* Update the number of free blocks and inodes in the filesystem and in each 491 block group */ 492void ext4_update_free() 493{ 494 u32 i; 495 496 for (i = 0; i < aux_info.groups; i++) { 497 u32 bg_free_blocks = get_free_blocks(i); 498 u32 bg_free_inodes = get_free_inodes(i); 499 u16 crc; 500 501 aux_info.bg_desc[i].bg_free_blocks_count = bg_free_blocks; 502 aux_info.sb->s_free_blocks_count_lo += bg_free_blocks; 503 504 aux_info.bg_desc[i].bg_free_inodes_count = bg_free_inodes; 505 aux_info.sb->s_free_inodes_count += bg_free_inodes; 506 507 aux_info.bg_desc[i].bg_used_dirs_count += get_directories(i); 508 509 aux_info.bg_desc[i].bg_flags = get_bg_flags(i); 510 511 crc = ext4_crc16(~0, aux_info.sb->s_uuid, sizeof(aux_info.sb->s_uuid)); 512 crc = ext4_crc16(crc, &i, sizeof(i)); 513 crc = ext4_crc16(crc, &aux_info.bg_desc[i], offsetof(struct ext2_group_desc, bg_checksum)); 514 aux_info.bg_desc[i].bg_checksum = crc; 515 } 516} 517 518u64 get_block_device_size(int fd) 519{ 520 u64 size = 0; 521 int ret; 522 523#if defined(__linux__) 524 ret = ioctl(fd, BLKGETSIZE64, &size); 525#elif defined(__APPLE__) && defined(__MACH__) 526 ret = ioctl(fd, DKIOCGETBLOCKCOUNT, &size); 527#else 528 close(fd); 529 return 0; 530#endif 531 532 if (ret) 533 return 0; 534 535 return size; 536} 537 538int is_block_device_fd(int fd) 539{ 540#ifdef USE_MINGW 541 return 0; 542#else 543 struct stat st; 544 int ret = fstat(fd, &st); 545 if (ret < 0) 546 return 0; 547 548 return S_ISBLK(st.st_mode); 549#endif 550} 551 552u64 get_file_size(int fd) 553{ 554 struct stat buf; 555 int ret; 556 u64 reserve_len = 0; 557 s64 computed_size; 558 559 ret = fstat(fd, &buf); 560 if (ret) 561 return 0; 562 563 if (info.len < 0) 564 reserve_len = -info.len; 565 566 if (S_ISREG(buf.st_mode)) 567 computed_size = buf.st_size - reserve_len; 568 else if (S_ISBLK(buf.st_mode)) 569 computed_size = get_block_device_size(fd) - reserve_len; 570 else 571 computed_size = 0; 572 573 if (computed_size < 0) { 574 warn("Computed filesystem size less than 0"); 575 computed_size = 0; 576 } 577 578 return computed_size; 579} 580 581u64 parse_num(const char *arg) 582{ 583 char *endptr; 584 u64 num = strtoull(arg, &endptr, 10); 585 if (*endptr == 'k' || *endptr == 'K') 586 num *= 1024LL; 587 else if (*endptr == 'm' || *endptr == 'M') 588 num *= 1024LL * 1024LL; 589 else if (*endptr == 'g' || *endptr == 'G') 590 num *= 1024LL * 1024LL * 1024LL; 591 592 return num; 593} 594 595int read_ext(int fd, int verbose) 596{ 597 off64_t ret; 598 struct ext4_super_block sb; 599 600 read_sb(fd, &sb); 601 602 ext4_parse_sb_info(&sb); 603 604 ret = lseek64(fd, info.len, SEEK_SET); 605 if (ret < 0) 606 critical_error_errno("failed to seek to end of input image"); 607 608 ret = lseek64(fd, info.block_size * (aux_info.first_data_block + 1), SEEK_SET); 609 if (ret < 0) 610 critical_error_errno("failed to seek to block group descriptors"); 611 612 ret = read(fd, aux_info.bg_desc, info.block_size * aux_info.bg_desc_blocks); 613 if (ret < 0) 614 critical_error_errno("failed to read block group descriptors"); 615 if (ret != (int)info.block_size * (int)aux_info.bg_desc_blocks) 616 critical_error("failed to read all of block group descriptors"); 617 618 if (verbose) { 619 printf("Found filesystem with parameters:\n"); 620 printf(" Size: %"PRIu64"\n", info.len); 621 printf(" Block size: %d\n", info.block_size); 622 printf(" Blocks per group: %d\n", info.blocks_per_group); 623 printf(" Inodes per group: %d\n", info.inodes_per_group); 624 printf(" Inode size: %d\n", info.inode_size); 625 printf(" Label: %s\n", info.label); 626 printf(" Blocks: %"PRIu64"\n", aux_info.len_blocks); 627 printf(" Block groups: %d\n", aux_info.groups); 628 printf(" Reserved block group size: %d\n", info.bg_desc_reserve_blocks); 629 printf(" Used %d/%d inodes and %d/%d blocks\n", 630 aux_info.sb->s_inodes_count - aux_info.sb->s_free_inodes_count, 631 aux_info.sb->s_inodes_count, 632 aux_info.sb->s_blocks_count_lo - aux_info.sb->s_free_blocks_count_lo, 633 aux_info.sb->s_blocks_count_lo); 634 } 635 636 return 0; 637} 638 639