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