1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * linux/fs/ext4/ialloc.c 4 * 5 * Copyright (C) 1992, 1993, 1994, 1995 6 * Remy Card (card@masi.ibp.fr) 7 * Laboratoire MASI - Institut Blaise Pascal 8 * Universite Pierre et Marie Curie (Paris VI) 9 * 10 * BSD ufs-inspired inode and directory allocation by 11 * Stephen Tweedie (sct@redhat.com), 1993 12 * Big-endian to little-endian byte-swapping/bitmaps by 13 * David S. Miller (davem@caip.rutgers.edu), 1995 14 */ 15 16 #include <linux/time.h> 17 #include <linux/fs.h> 18 #include <linux/stat.h> 19 #include <linux/string.h> 20 #include <linux/quotaops.h> 21 #include <linux/buffer_head.h> 22 #include <linux/random.h> 23 #include <linux/bitops.h> 24 #include <linux/blkdev.h> 25 #include <linux/cred.h> 26 27 #include <asm/byteorder.h> 28 29 #include "ext4.h" 30 #include "ext4_jbd2.h" 31 #include "xattr.h" 32 #include "acl.h" 33 34 #include <trace/events/ext4.h> 35 36 /* 37 * ialloc.c contains the inodes allocation and deallocation routines 38 */ 39 40 /* 41 * The free inodes are managed by bitmaps. A file system contains several 42 * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap 43 * block for inodes, N blocks for the inode table and data blocks. 44 * 45 * The file system contains group descriptors which are located after the 46 * super block. Each descriptor contains the number of the bitmap block and 47 * the free blocks count in the block. 48 */ 49 50 /* 51 * To avoid calling the atomic setbit hundreds or thousands of times, we only 52 * need to use it within a single byte (to ensure we get endianness right). 53 * We can use memset for the rest of the bitmap as there are no other users. 54 */ 55 void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap) 56 { 57 int i; 58 59 if (start_bit >= end_bit) 60 return; 61 62 ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit); 63 for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++) 64 ext4_set_bit(i, bitmap); 65 if (i < end_bit) 66 memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3); 67 } 68 69 void ext4_end_bitmap_read(struct buffer_head *bh, int uptodate) 70 { 71 if (uptodate) { 72 set_buffer_uptodate(bh); 73 set_bitmap_uptodate(bh); 74 } 75 unlock_buffer(bh); 76 put_bh(bh); 77 } 78 79 static int ext4_validate_inode_bitmap(struct super_block *sb, 80 struct ext4_group_desc *desc, 81 ext4_group_t block_group, 82 struct buffer_head *bh) 83 { 84 ext4_fsblk_t blk; 85 struct ext4_group_info *grp; 86 87 if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY) 88 return 0; 89 90 grp = ext4_get_group_info(sb, block_group); 91 92 if (buffer_verified(bh)) 93 return 0; 94 if (!grp || EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) 95 return -EFSCORRUPTED; 96 97 ext4_lock_group(sb, block_group); 98 if (buffer_verified(bh)) 99 goto verified; 100 blk = ext4_inode_bitmap(sb, desc); 101 if (!ext4_inode_bitmap_csum_verify(sb, desc, bh, 102 EXT4_INODES_PER_GROUP(sb) / 8) || 103 ext4_simulate_fail(sb, EXT4_SIM_IBITMAP_CRC)) { 104 ext4_unlock_group(sb, block_group); 105 ext4_error(sb, "Corrupt inode bitmap - block_group = %u, " 106 "inode_bitmap = %llu", block_group, blk); 107 ext4_mark_group_bitmap_corrupted(sb, block_group, 108 EXT4_GROUP_INFO_IBITMAP_CORRUPT); 109 return -EFSBADCRC; 110 } 111 set_buffer_verified(bh); 112 verified: 113 ext4_unlock_group(sb, block_group); 114 return 0; 115 } 116 117 /* 118 * Read the inode allocation bitmap for a given block_group, reading 119 * into the specified slot in the superblock's bitmap cache. 120 * 121 * Return buffer_head of bitmap on success, or an ERR_PTR on error. 122 */ 123 static struct buffer_head * 124 ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group) 125 { 126 struct ext4_group_desc *desc; 127 struct ext4_sb_info *sbi = EXT4_SB(sb); 128 struct buffer_head *bh = NULL; 129 ext4_fsblk_t bitmap_blk; 130 int err; 131 132 desc = ext4_get_group_desc(sb, block_group, NULL); 133 if (!desc) 134 return ERR_PTR(-EFSCORRUPTED); 135 136 bitmap_blk = ext4_inode_bitmap(sb, desc); 137 if ((bitmap_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) || 138 (bitmap_blk >= ext4_blocks_count(sbi->s_es))) { 139 ext4_error(sb, "Invalid inode bitmap blk %llu in " 140 "block_group %u", bitmap_blk, block_group); 141 ext4_mark_group_bitmap_corrupted(sb, block_group, 142 EXT4_GROUP_INFO_IBITMAP_CORRUPT); 143 return ERR_PTR(-EFSCORRUPTED); 144 } 145 bh = sb_getblk(sb, bitmap_blk); 146 if (unlikely(!bh)) { 147 ext4_warning(sb, "Cannot read inode bitmap - " 148 "block_group = %u, inode_bitmap = %llu", 149 block_group, bitmap_blk); 150 return ERR_PTR(-ENOMEM); 151 } 152 if (bitmap_uptodate(bh)) 153 goto verify; 154 155 lock_buffer(bh); 156 if (bitmap_uptodate(bh)) { 157 unlock_buffer(bh); 158 goto verify; 159 } 160 161 ext4_lock_group(sb, block_group); 162 if (ext4_has_group_desc_csum(sb) && 163 (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT))) { 164 if (block_group == 0) { 165 ext4_unlock_group(sb, block_group); 166 unlock_buffer(bh); 167 ext4_error(sb, "Inode bitmap for bg 0 marked " 168 "uninitialized"); 169 err = -EFSCORRUPTED; 170 goto out; 171 } 172 memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8); 173 ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb), 174 sb->s_blocksize * 8, bh->b_data); 175 set_bitmap_uptodate(bh); 176 set_buffer_uptodate(bh); 177 set_buffer_verified(bh); 178 ext4_unlock_group(sb, block_group); 179 unlock_buffer(bh); 180 return bh; 181 } 182 ext4_unlock_group(sb, block_group); 183 184 if (buffer_uptodate(bh)) { 185 /* 186 * if not uninit if bh is uptodate, 187 * bitmap is also uptodate 188 */ 189 set_bitmap_uptodate(bh); 190 unlock_buffer(bh); 191 goto verify; 192 } 193 /* 194 * submit the buffer_head for reading 195 */ 196 trace_ext4_load_inode_bitmap(sb, block_group); 197 ext4_read_bh(bh, REQ_META | REQ_PRIO, ext4_end_bitmap_read); 198 ext4_simulate_fail_bh(sb, bh, EXT4_SIM_IBITMAP_EIO); 199 if (!buffer_uptodate(bh)) { 200 put_bh(bh); 201 ext4_error_err(sb, EIO, "Cannot read inode bitmap - " 202 "block_group = %u, inode_bitmap = %llu", 203 block_group, bitmap_blk); 204 ext4_mark_group_bitmap_corrupted(sb, block_group, 205 EXT4_GROUP_INFO_IBITMAP_CORRUPT); 206 return ERR_PTR(-EIO); 207 } 208 209 verify: 210 err = ext4_validate_inode_bitmap(sb, desc, block_group, bh); 211 if (err) 212 goto out; 213 return bh; 214 out: 215 put_bh(bh); 216 return ERR_PTR(err); 217 } 218 219 /* 220 * NOTE! When we get the inode, we're the only people 221 * that have access to it, and as such there are no 222 * race conditions we have to worry about. The inode 223 * is not on the hash-lists, and it cannot be reached 224 * through the filesystem because the directory entry 225 * has been deleted earlier. 226 * 227 * HOWEVER: we must make sure that we get no aliases, 228 * which means that we have to call "clear_inode()" 229 * _before_ we mark the inode not in use in the inode 230 * bitmaps. Otherwise a newly created file might use 231 * the same inode number (not actually the same pointer 232 * though), and then we'd have two inodes sharing the 233 * same inode number and space on the harddisk. 234 */ 235 void ext4_free_inode(handle_t *handle, struct inode *inode) 236 { 237 struct super_block *sb = inode->i_sb; 238 int is_directory; 239 unsigned long ino; 240 struct buffer_head *bitmap_bh = NULL; 241 struct buffer_head *bh2; 242 ext4_group_t block_group; 243 unsigned long bit; 244 struct ext4_group_desc *gdp; 245 struct ext4_super_block *es; 246 struct ext4_sb_info *sbi; 247 int fatal = 0, err, count, cleared; 248 struct ext4_group_info *grp; 249 250 if (!sb) { 251 printk(KERN_ERR "EXT4-fs: %s:%d: inode on " 252 "nonexistent device\n", __func__, __LINE__); 253 return; 254 } 255 if (atomic_read(&inode->i_count) > 1) { 256 ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: count=%d", 257 __func__, __LINE__, inode->i_ino, 258 atomic_read(&inode->i_count)); 259 return; 260 } 261 if (inode->i_nlink) { 262 ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: nlink=%d\n", 263 __func__, __LINE__, inode->i_ino, inode->i_nlink); 264 return; 265 } 266 sbi = EXT4_SB(sb); 267 268 ino = inode->i_ino; 269 ext4_debug("freeing inode %lu\n", ino); 270 trace_ext4_free_inode(inode); 271 272 dquot_initialize(inode); 273 dquot_free_inode(inode); 274 275 is_directory = S_ISDIR(inode->i_mode); 276 277 /* Do this BEFORE marking the inode not in use or returning an error */ 278 ext4_clear_inode(inode); 279 280 es = sbi->s_es; 281 if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) { 282 ext4_error(sb, "reserved or nonexistent inode %lu", ino); 283 goto error_return; 284 } 285 block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb); 286 bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb); 287 bitmap_bh = ext4_read_inode_bitmap(sb, block_group); 288 /* Don't bother if the inode bitmap is corrupt. */ 289 if (IS_ERR(bitmap_bh)) { 290 fatal = PTR_ERR(bitmap_bh); 291 bitmap_bh = NULL; 292 goto error_return; 293 } 294 if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) { 295 grp = ext4_get_group_info(sb, block_group); 296 if (!grp || unlikely(EXT4_MB_GRP_IBITMAP_CORRUPT(grp))) { 297 fatal = -EFSCORRUPTED; 298 goto error_return; 299 } 300 } 301 302 BUFFER_TRACE(bitmap_bh, "get_write_access"); 303 fatal = ext4_journal_get_write_access(handle, sb, bitmap_bh, 304 EXT4_JTR_NONE); 305 if (fatal) 306 goto error_return; 307 308 fatal = -ESRCH; 309 gdp = ext4_get_group_desc(sb, block_group, &bh2); 310 if (gdp) { 311 BUFFER_TRACE(bh2, "get_write_access"); 312 fatal = ext4_journal_get_write_access(handle, sb, bh2, 313 EXT4_JTR_NONE); 314 } 315 ext4_lock_group(sb, block_group); 316 cleared = ext4_test_and_clear_bit(bit, bitmap_bh->b_data); 317 if (fatal || !cleared) { 318 ext4_unlock_group(sb, block_group); 319 goto out; 320 } 321 322 count = ext4_free_inodes_count(sb, gdp) + 1; 323 ext4_free_inodes_set(sb, gdp, count); 324 if (is_directory) { 325 count = ext4_used_dirs_count(sb, gdp) - 1; 326 ext4_used_dirs_set(sb, gdp, count); 327 if (percpu_counter_initialized(&sbi->s_dirs_counter)) 328 percpu_counter_dec(&sbi->s_dirs_counter); 329 } 330 ext4_inode_bitmap_csum_set(sb, gdp, bitmap_bh, 331 EXT4_INODES_PER_GROUP(sb) / 8); 332 ext4_group_desc_csum_set(sb, block_group, gdp); 333 ext4_unlock_group(sb, block_group); 334 335 if (percpu_counter_initialized(&sbi->s_freeinodes_counter)) 336 percpu_counter_inc(&sbi->s_freeinodes_counter); 337 if (sbi->s_log_groups_per_flex) { 338 struct flex_groups *fg; 339 340 fg = sbi_array_rcu_deref(sbi, s_flex_groups, 341 ext4_flex_group(sbi, block_group)); 342 atomic_inc(&fg->free_inodes); 343 if (is_directory) 344 atomic_dec(&fg->used_dirs); 345 } 346 BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata"); 347 fatal = ext4_handle_dirty_metadata(handle, NULL, bh2); 348 out: 349 if (cleared) { 350 BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata"); 351 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh); 352 if (!fatal) 353 fatal = err; 354 } else { 355 ext4_error(sb, "bit already cleared for inode %lu", ino); 356 ext4_mark_group_bitmap_corrupted(sb, block_group, 357 EXT4_GROUP_INFO_IBITMAP_CORRUPT); 358 } 359 360 error_return: 361 brelse(bitmap_bh); 362 ext4_std_error(sb, fatal); 363 } 364 365 struct orlov_stats { 366 __u64 free_clusters; 367 __u32 free_inodes; 368 __u32 used_dirs; 369 }; 370 371 /* 372 * Helper function for Orlov's allocator; returns critical information 373 * for a particular block group or flex_bg. If flex_size is 1, then g 374 * is a block group number; otherwise it is flex_bg number. 375 */ 376 static void get_orlov_stats(struct super_block *sb, ext4_group_t g, 377 int flex_size, struct orlov_stats *stats) 378 { 379 struct ext4_group_desc *desc; 380 381 if (flex_size > 1) { 382 struct flex_groups *fg = sbi_array_rcu_deref(EXT4_SB(sb), 383 s_flex_groups, g); 384 stats->free_inodes = atomic_read(&fg->free_inodes); 385 stats->free_clusters = atomic64_read(&fg->free_clusters); 386 stats->used_dirs = atomic_read(&fg->used_dirs); 387 return; 388 } 389 390 desc = ext4_get_group_desc(sb, g, NULL); 391 if (desc) { 392 stats->free_inodes = ext4_free_inodes_count(sb, desc); 393 stats->free_clusters = ext4_free_group_clusters(sb, desc); 394 stats->used_dirs = ext4_used_dirs_count(sb, desc); 395 } else { 396 stats->free_inodes = 0; 397 stats->free_clusters = 0; 398 stats->used_dirs = 0; 399 } 400 } 401 402 /* 403 * Orlov's allocator for directories. 404 * 405 * We always try to spread first-level directories. 406 * 407 * If there are blockgroups with both free inodes and free clusters counts 408 * not worse than average we return one with smallest directory count. 409 * Otherwise we simply return a random group. 410 * 411 * For the rest rules look so: 412 * 413 * It's OK to put directory into a group unless 414 * it has too many directories already (max_dirs) or 415 * it has too few free inodes left (min_inodes) or 416 * it has too few free clusters left (min_clusters) or 417 * Parent's group is preferred, if it doesn't satisfy these 418 * conditions we search cyclically through the rest. If none 419 * of the groups look good we just look for a group with more 420 * free inodes than average (starting at parent's group). 421 */ 422 423 static int find_group_orlov(struct super_block *sb, struct inode *parent, 424 ext4_group_t *group, umode_t mode, 425 const struct qstr *qstr) 426 { 427 ext4_group_t parent_group = EXT4_I(parent)->i_block_group; 428 struct ext4_sb_info *sbi = EXT4_SB(sb); 429 ext4_group_t real_ngroups = ext4_get_groups_count(sb); 430 int inodes_per_group = EXT4_INODES_PER_GROUP(sb); 431 unsigned int freei, avefreei, grp_free; 432 ext4_fsblk_t freec, avefreec; 433 unsigned int ndirs; 434 int max_dirs, min_inodes; 435 ext4_grpblk_t min_clusters; 436 ext4_group_t i, grp, g, ngroups; 437 struct ext4_group_desc *desc; 438 struct orlov_stats stats; 439 int flex_size = ext4_flex_bg_size(sbi); 440 struct dx_hash_info hinfo; 441 442 ngroups = real_ngroups; 443 if (flex_size > 1) { 444 ngroups = (real_ngroups + flex_size - 1) >> 445 sbi->s_log_groups_per_flex; 446 parent_group >>= sbi->s_log_groups_per_flex; 447 } 448 449 freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter); 450 avefreei = freei / ngroups; 451 freec = percpu_counter_read_positive(&sbi->s_freeclusters_counter); 452 avefreec = freec; 453 do_div(avefreec, ngroups); 454 ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter); 455 456 if (S_ISDIR(mode) && 457 ((parent == d_inode(sb->s_root)) || 458 (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) { 459 int best_ndir = inodes_per_group; 460 int ret = -1; 461 462 if (qstr) { 463 hinfo.hash_version = DX_HASH_HALF_MD4; 464 hinfo.seed = sbi->s_hash_seed; 465 ext4fs_dirhash(parent, qstr->name, qstr->len, &hinfo); 466 parent_group = hinfo.hash % ngroups; 467 } else 468 parent_group = get_random_u32_below(ngroups); 469 for (i = 0; i < ngroups; i++) { 470 g = (parent_group + i) % ngroups; 471 get_orlov_stats(sb, g, flex_size, &stats); 472 if (!stats.free_inodes) 473 continue; 474 if (stats.used_dirs >= best_ndir) 475 continue; 476 if (stats.free_inodes < avefreei) 477 continue; 478 if (stats.free_clusters < avefreec) 479 continue; 480 grp = g; 481 ret = 0; 482 best_ndir = stats.used_dirs; 483 } 484 if (ret) 485 goto fallback; 486 found_flex_bg: 487 if (flex_size == 1) { 488 *group = grp; 489 return 0; 490 } 491 492 /* 493 * We pack inodes at the beginning of the flexgroup's 494 * inode tables. Block allocation decisions will do 495 * something similar, although regular files will 496 * start at 2nd block group of the flexgroup. See 497 * ext4_ext_find_goal() and ext4_find_near(). 498 */ 499 grp *= flex_size; 500 for (i = 0; i < flex_size; i++) { 501 if (grp+i >= real_ngroups) 502 break; 503 desc = ext4_get_group_desc(sb, grp+i, NULL); 504 if (desc && ext4_free_inodes_count(sb, desc)) { 505 *group = grp+i; 506 return 0; 507 } 508 } 509 goto fallback; 510 } 511 512 max_dirs = ndirs / ngroups + inodes_per_group*flex_size / 16; 513 min_inodes = avefreei - inodes_per_group*flex_size / 4; 514 if (min_inodes < 1) 515 min_inodes = 1; 516 min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4; 517 518 /* 519 * Start looking in the flex group where we last allocated an 520 * inode for this parent directory 521 */ 522 if (EXT4_I(parent)->i_last_alloc_group != ~0) { 523 parent_group = EXT4_I(parent)->i_last_alloc_group; 524 if (flex_size > 1) 525 parent_group >>= sbi->s_log_groups_per_flex; 526 } 527 528 for (i = 0; i < ngroups; i++) { 529 grp = (parent_group + i) % ngroups; 530 get_orlov_stats(sb, grp, flex_size, &stats); 531 if (stats.used_dirs >= max_dirs) 532 continue; 533 if (stats.free_inodes < min_inodes) 534 continue; 535 if (stats.free_clusters < min_clusters) 536 continue; 537 goto found_flex_bg; 538 } 539 540 fallback: 541 ngroups = real_ngroups; 542 avefreei = freei / ngroups; 543 fallback_retry: 544 parent_group = EXT4_I(parent)->i_block_group; 545 for (i = 0; i < ngroups; i++) { 546 grp = (parent_group + i) % ngroups; 547 desc = ext4_get_group_desc(sb, grp, NULL); 548 if (desc) { 549 grp_free = ext4_free_inodes_count(sb, desc); 550 if (grp_free && grp_free >= avefreei) { 551 *group = grp; 552 return 0; 553 } 554 } 555 } 556 557 if (avefreei) { 558 /* 559 * The free-inodes counter is approximate, and for really small 560 * filesystems the above test can fail to find any blockgroups 561 */ 562 avefreei = 0; 563 goto fallback_retry; 564 } 565 566 return -1; 567 } 568 569 static int find_group_other(struct super_block *sb, struct inode *parent, 570 ext4_group_t *group, umode_t mode) 571 { 572 ext4_group_t parent_group = EXT4_I(parent)->i_block_group; 573 ext4_group_t i, last, ngroups = ext4_get_groups_count(sb); 574 struct ext4_group_desc *desc; 575 int flex_size = ext4_flex_bg_size(EXT4_SB(sb)); 576 577 /* 578 * Try to place the inode is the same flex group as its 579 * parent. If we can't find space, use the Orlov algorithm to 580 * find another flex group, and store that information in the 581 * parent directory's inode information so that use that flex 582 * group for future allocations. 583 */ 584 if (flex_size > 1) { 585 int retry = 0; 586 587 try_again: 588 parent_group &= ~(flex_size-1); 589 last = parent_group + flex_size; 590 if (last > ngroups) 591 last = ngroups; 592 for (i = parent_group; i < last; i++) { 593 desc = ext4_get_group_desc(sb, i, NULL); 594 if (desc && ext4_free_inodes_count(sb, desc)) { 595 *group = i; 596 return 0; 597 } 598 } 599 if (!retry && EXT4_I(parent)->i_last_alloc_group != ~0) { 600 retry = 1; 601 parent_group = EXT4_I(parent)->i_last_alloc_group; 602 goto try_again; 603 } 604 /* 605 * If this didn't work, use the Orlov search algorithm 606 * to find a new flex group; we pass in the mode to 607 * avoid the topdir algorithms. 608 */ 609 *group = parent_group + flex_size; 610 if (*group > ngroups) 611 *group = 0; 612 return find_group_orlov(sb, parent, group, mode, NULL); 613 } 614 615 /* 616 * Try to place the inode in its parent directory 617 */ 618 *group = parent_group; 619 desc = ext4_get_group_desc(sb, *group, NULL); 620 if (desc && ext4_free_inodes_count(sb, desc) && 621 ext4_free_group_clusters(sb, desc)) 622 return 0; 623 624 /* 625 * We're going to place this inode in a different blockgroup from its 626 * parent. We want to cause files in a common directory to all land in 627 * the same blockgroup. But we want files which are in a different 628 * directory which shares a blockgroup with our parent to land in a 629 * different blockgroup. 630 * 631 * So add our directory's i_ino into the starting point for the hash. 632 */ 633 *group = (*group + parent->i_ino) % ngroups; 634 635 /* 636 * Use a quadratic hash to find a group with a free inode and some free 637 * blocks. 638 */ 639 for (i = 1; i < ngroups; i <<= 1) { 640 *group += i; 641 if (*group >= ngroups) 642 *group -= ngroups; 643 desc = ext4_get_group_desc(sb, *group, NULL); 644 if (desc && ext4_free_inodes_count(sb, desc) && 645 ext4_free_group_clusters(sb, desc)) 646 return 0; 647 } 648 649 /* 650 * That failed: try linear search for a free inode, even if that group 651 * has no free blocks. 652 */ 653 *group = parent_group; 654 for (i = 0; i < ngroups; i++) { 655 if (++*group >= ngroups) 656 *group = 0; 657 desc = ext4_get_group_desc(sb, *group, NULL); 658 if (desc && ext4_free_inodes_count(sb, desc)) 659 return 0; 660 } 661 662 return -1; 663 } 664 665 /* 666 * In no journal mode, if an inode has recently been deleted, we want 667 * to avoid reusing it until we're reasonably sure the inode table 668 * block has been written back to disk. (Yes, these values are 669 * somewhat arbitrary...) 670 */ 671 #define RECENTCY_MIN 60 672 #define RECENTCY_DIRTY 300 673 674 static int recently_deleted(struct super_block *sb, ext4_group_t group, int ino) 675 { 676 struct ext4_group_desc *gdp; 677 struct ext4_inode *raw_inode; 678 struct buffer_head *bh; 679 int inodes_per_block = EXT4_SB(sb)->s_inodes_per_block; 680 int offset, ret = 0; 681 int recentcy = RECENTCY_MIN; 682 u32 dtime, now; 683 684 gdp = ext4_get_group_desc(sb, group, NULL); 685 if (unlikely(!gdp)) 686 return 0; 687 688 bh = sb_find_get_block(sb, ext4_inode_table(sb, gdp) + 689 (ino / inodes_per_block)); 690 if (!bh || !buffer_uptodate(bh)) 691 /* 692 * If the block is not in the buffer cache, then it 693 * must have been written out. 694 */ 695 goto out; 696 697 offset = (ino % inodes_per_block) * EXT4_INODE_SIZE(sb); 698 raw_inode = (struct ext4_inode *) (bh->b_data + offset); 699 700 /* i_dtime is only 32 bits on disk, but we only care about relative 701 * times in the range of a few minutes (i.e. long enough to sync a 702 * recently-deleted inode to disk), so using the low 32 bits of the 703 * clock (a 68 year range) is enough, see time_before32() */ 704 dtime = le32_to_cpu(raw_inode->i_dtime); 705 now = ktime_get_real_seconds(); 706 if (buffer_dirty(bh)) 707 recentcy += RECENTCY_DIRTY; 708 709 if (dtime && time_before32(dtime, now) && 710 time_before32(now, dtime + recentcy)) 711 ret = 1; 712 out: 713 brelse(bh); 714 return ret; 715 } 716 717 static int find_inode_bit(struct super_block *sb, ext4_group_t group, 718 struct buffer_head *bitmap, unsigned long *ino) 719 { 720 bool check_recently_deleted = EXT4_SB(sb)->s_journal == NULL; 721 unsigned long recently_deleted_ino = EXT4_INODES_PER_GROUP(sb); 722 723 next: 724 *ino = ext4_find_next_zero_bit((unsigned long *) 725 bitmap->b_data, 726 EXT4_INODES_PER_GROUP(sb), *ino); 727 if (*ino >= EXT4_INODES_PER_GROUP(sb)) 728 goto not_found; 729 730 if (check_recently_deleted && recently_deleted(sb, group, *ino)) { 731 recently_deleted_ino = *ino; 732 *ino = *ino + 1; 733 if (*ino < EXT4_INODES_PER_GROUP(sb)) 734 goto next; 735 goto not_found; 736 } 737 return 1; 738 not_found: 739 if (recently_deleted_ino >= EXT4_INODES_PER_GROUP(sb)) 740 return 0; 741 /* 742 * Not reusing recently deleted inodes is mostly a preference. We don't 743 * want to report ENOSPC or skew allocation patterns because of that. 744 * So return even recently deleted inode if we could find better in the 745 * given range. 746 */ 747 *ino = recently_deleted_ino; 748 return 1; 749 } 750 751 int ext4_mark_inode_used(struct super_block *sb, int ino) 752 { 753 unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count); 754 struct buffer_head *inode_bitmap_bh = NULL, *group_desc_bh = NULL; 755 struct ext4_group_desc *gdp; 756 ext4_group_t group; 757 int bit; 758 int err = -EFSCORRUPTED; 759 760 if (ino < EXT4_FIRST_INO(sb) || ino > max_ino) 761 goto out; 762 763 group = (ino - 1) / EXT4_INODES_PER_GROUP(sb); 764 bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb); 765 inode_bitmap_bh = ext4_read_inode_bitmap(sb, group); 766 if (IS_ERR(inode_bitmap_bh)) 767 return PTR_ERR(inode_bitmap_bh); 768 769 if (ext4_test_bit(bit, inode_bitmap_bh->b_data)) { 770 err = 0; 771 goto out; 772 } 773 774 gdp = ext4_get_group_desc(sb, group, &group_desc_bh); 775 if (!gdp || !group_desc_bh) { 776 err = -EINVAL; 777 goto out; 778 } 779 780 ext4_set_bit(bit, inode_bitmap_bh->b_data); 781 782 BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata"); 783 err = ext4_handle_dirty_metadata(NULL, NULL, inode_bitmap_bh); 784 if (err) { 785 ext4_std_error(sb, err); 786 goto out; 787 } 788 err = sync_dirty_buffer(inode_bitmap_bh); 789 if (err) { 790 ext4_std_error(sb, err); 791 goto out; 792 } 793 794 /* We may have to initialize the block bitmap if it isn't already */ 795 if (ext4_has_group_desc_csum(sb) && 796 gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) { 797 struct buffer_head *block_bitmap_bh; 798 799 block_bitmap_bh = ext4_read_block_bitmap(sb, group); 800 if (IS_ERR(block_bitmap_bh)) { 801 err = PTR_ERR(block_bitmap_bh); 802 goto out; 803 } 804 805 BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap"); 806 err = ext4_handle_dirty_metadata(NULL, NULL, block_bitmap_bh); 807 sync_dirty_buffer(block_bitmap_bh); 808 809 /* recheck and clear flag under lock if we still need to */ 810 ext4_lock_group(sb, group); 811 if (ext4_has_group_desc_csum(sb) && 812 (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) { 813 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT); 814 ext4_free_group_clusters_set(sb, gdp, 815 ext4_free_clusters_after_init(sb, group, gdp)); 816 ext4_block_bitmap_csum_set(sb, gdp, block_bitmap_bh); 817 ext4_group_desc_csum_set(sb, group, gdp); 818 } 819 ext4_unlock_group(sb, group); 820 brelse(block_bitmap_bh); 821 822 if (err) { 823 ext4_std_error(sb, err); 824 goto out; 825 } 826 } 827 828 /* Update the relevant bg descriptor fields */ 829 if (ext4_has_group_desc_csum(sb)) { 830 int free; 831 832 ext4_lock_group(sb, group); /* while we modify the bg desc */ 833 free = EXT4_INODES_PER_GROUP(sb) - 834 ext4_itable_unused_count(sb, gdp); 835 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) { 836 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT); 837 free = 0; 838 } 839 840 /* 841 * Check the relative inode number against the last used 842 * relative inode number in this group. if it is greater 843 * we need to update the bg_itable_unused count 844 */ 845 if (bit >= free) 846 ext4_itable_unused_set(sb, gdp, 847 (EXT4_INODES_PER_GROUP(sb) - bit - 1)); 848 } else { 849 ext4_lock_group(sb, group); 850 } 851 852 ext4_free_inodes_set(sb, gdp, ext4_free_inodes_count(sb, gdp) - 1); 853 if (ext4_has_group_desc_csum(sb)) { 854 ext4_inode_bitmap_csum_set(sb, gdp, inode_bitmap_bh, 855 EXT4_INODES_PER_GROUP(sb) / 8); 856 ext4_group_desc_csum_set(sb, group, gdp); 857 } 858 859 ext4_unlock_group(sb, group); 860 err = ext4_handle_dirty_metadata(NULL, NULL, group_desc_bh); 861 sync_dirty_buffer(group_desc_bh); 862 out: 863 return err; 864 } 865 866 static int ext4_xattr_credits_for_new_inode(struct inode *dir, mode_t mode, 867 bool encrypt) 868 { 869 struct super_block *sb = dir->i_sb; 870 int nblocks = 0; 871 #ifdef CONFIG_EXT4_FS_POSIX_ACL 872 struct posix_acl *p = get_inode_acl(dir, ACL_TYPE_DEFAULT); 873 874 if (IS_ERR(p)) 875 return PTR_ERR(p); 876 if (p) { 877 int acl_size = p->a_count * sizeof(ext4_acl_entry); 878 879 nblocks += (S_ISDIR(mode) ? 2 : 1) * 880 __ext4_xattr_set_credits(sb, NULL /* inode */, 881 NULL /* block_bh */, acl_size, 882 true /* is_create */); 883 posix_acl_release(p); 884 } 885 #endif 886 887 #ifdef CONFIG_SECURITY 888 { 889 int num_security_xattrs = 1; 890 891 #ifdef CONFIG_INTEGRITY 892 num_security_xattrs++; 893 #endif 894 /* 895 * We assume that security xattrs are never more than 1k. 896 * In practice they are under 128 bytes. 897 */ 898 nblocks += num_security_xattrs * 899 __ext4_xattr_set_credits(sb, NULL /* inode */, 900 NULL /* block_bh */, 1024, 901 true /* is_create */); 902 } 903 #endif 904 if (encrypt) 905 nblocks += __ext4_xattr_set_credits(sb, 906 NULL /* inode */, 907 NULL /* block_bh */, 908 FSCRYPT_SET_CONTEXT_MAX_SIZE, 909 true /* is_create */); 910 return nblocks; 911 } 912 913 /* 914 * There are two policies for allocating an inode. If the new inode is 915 * a directory, then a forward search is made for a block group with both 916 * free space and a low directory-to-inode ratio; if that fails, then of 917 * the groups with above-average free space, that group with the fewest 918 * directories already is chosen. 919 * 920 * For other inodes, search forward from the parent directory's block 921 * group to find a free inode. 922 */ 923 struct inode *__ext4_new_inode(struct mnt_idmap *idmap, 924 handle_t *handle, struct inode *dir, 925 umode_t mode, const struct qstr *qstr, 926 __u32 goal, uid_t *owner, __u32 i_flags, 927 int handle_type, unsigned int line_no, 928 int nblocks) 929 { 930 struct super_block *sb; 931 struct buffer_head *inode_bitmap_bh = NULL; 932 struct buffer_head *group_desc_bh; 933 ext4_group_t ngroups, group = 0; 934 unsigned long ino = 0; 935 struct inode *inode; 936 struct ext4_group_desc *gdp = NULL; 937 struct ext4_inode_info *ei; 938 struct ext4_sb_info *sbi; 939 int ret2, err; 940 struct inode *ret; 941 ext4_group_t i; 942 ext4_group_t flex_group; 943 struct ext4_group_info *grp = NULL; 944 bool encrypt = false; 945 946 /* Cannot create files in a deleted directory */ 947 if (!dir || !dir->i_nlink) 948 return ERR_PTR(-EPERM); 949 950 sb = dir->i_sb; 951 sbi = EXT4_SB(sb); 952 953 if (unlikely(ext4_forced_shutdown(sb))) 954 return ERR_PTR(-EIO); 955 956 ngroups = ext4_get_groups_count(sb); 957 trace_ext4_request_inode(dir, mode); 958 inode = new_inode(sb); 959 if (!inode) 960 return ERR_PTR(-ENOMEM); 961 ei = EXT4_I(inode); 962 963 /* 964 * Initialize owners and quota early so that we don't have to account 965 * for quota initialization worst case in standard inode creating 966 * transaction 967 */ 968 if (owner) { 969 inode->i_mode = mode; 970 i_uid_write(inode, owner[0]); 971 i_gid_write(inode, owner[1]); 972 } else if (test_opt(sb, GRPID)) { 973 inode->i_mode = mode; 974 inode_fsuid_set(inode, idmap); 975 inode->i_gid = dir->i_gid; 976 } else 977 inode_init_owner(idmap, inode, dir, mode); 978 979 if (ext4_has_feature_project(sb) && 980 ext4_test_inode_flag(dir, EXT4_INODE_PROJINHERIT)) 981 ei->i_projid = EXT4_I(dir)->i_projid; 982 else 983 ei->i_projid = make_kprojid(&init_user_ns, EXT4_DEF_PROJID); 984 985 if (!(i_flags & EXT4_EA_INODE_FL)) { 986 err = fscrypt_prepare_new_inode(dir, inode, &encrypt); 987 if (err) 988 goto out; 989 } 990 991 err = dquot_initialize(inode); 992 if (err) 993 goto out; 994 995 if (!handle && sbi->s_journal && !(i_flags & EXT4_EA_INODE_FL)) { 996 ret2 = ext4_xattr_credits_for_new_inode(dir, mode, encrypt); 997 if (ret2 < 0) { 998 err = ret2; 999 goto out; 1000 } 1001 nblocks += ret2; 1002 } 1003 1004 if (!goal) 1005 goal = sbi->s_inode_goal; 1006 1007 if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) { 1008 group = (goal - 1) / EXT4_INODES_PER_GROUP(sb); 1009 ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb); 1010 ret2 = 0; 1011 goto got_group; 1012 } 1013 1014 if (S_ISDIR(mode)) 1015 ret2 = find_group_orlov(sb, dir, &group, mode, qstr); 1016 else 1017 ret2 = find_group_other(sb, dir, &group, mode); 1018 1019 got_group: 1020 EXT4_I(dir)->i_last_alloc_group = group; 1021 err = -ENOSPC; 1022 if (ret2 == -1) 1023 goto out; 1024 1025 /* 1026 * Normally we will only go through one pass of this loop, 1027 * unless we get unlucky and it turns out the group we selected 1028 * had its last inode grabbed by someone else. 1029 */ 1030 for (i = 0; i < ngroups; i++, ino = 0) { 1031 err = -EIO; 1032 1033 gdp = ext4_get_group_desc(sb, group, &group_desc_bh); 1034 if (!gdp) 1035 goto out; 1036 1037 /* 1038 * Check free inodes count before loading bitmap. 1039 */ 1040 if (ext4_free_inodes_count(sb, gdp) == 0) 1041 goto next_group; 1042 1043 if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) { 1044 grp = ext4_get_group_info(sb, group); 1045 /* 1046 * Skip groups with already-known suspicious inode 1047 * tables 1048 */ 1049 if (!grp || EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) 1050 goto next_group; 1051 } 1052 1053 brelse(inode_bitmap_bh); 1054 inode_bitmap_bh = ext4_read_inode_bitmap(sb, group); 1055 /* Skip groups with suspicious inode tables */ 1056 if (((!(sbi->s_mount_state & EXT4_FC_REPLAY)) 1057 && EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) || 1058 IS_ERR(inode_bitmap_bh)) { 1059 inode_bitmap_bh = NULL; 1060 goto next_group; 1061 } 1062 1063 repeat_in_this_group: 1064 ret2 = find_inode_bit(sb, group, inode_bitmap_bh, &ino); 1065 if (!ret2) 1066 goto next_group; 1067 1068 if (group == 0 && (ino + 1) < EXT4_FIRST_INO(sb)) { 1069 ext4_error(sb, "reserved inode found cleared - " 1070 "inode=%lu", ino + 1); 1071 ext4_mark_group_bitmap_corrupted(sb, group, 1072 EXT4_GROUP_INFO_IBITMAP_CORRUPT); 1073 goto next_group; 1074 } 1075 1076 if ((!(sbi->s_mount_state & EXT4_FC_REPLAY)) && !handle) { 1077 BUG_ON(nblocks <= 0); 1078 handle = __ext4_journal_start_sb(NULL, dir->i_sb, 1079 line_no, handle_type, nblocks, 0, 1080 ext4_trans_default_revoke_credits(sb)); 1081 if (IS_ERR(handle)) { 1082 err = PTR_ERR(handle); 1083 ext4_std_error(sb, err); 1084 goto out; 1085 } 1086 } 1087 BUFFER_TRACE(inode_bitmap_bh, "get_write_access"); 1088 err = ext4_journal_get_write_access(handle, sb, inode_bitmap_bh, 1089 EXT4_JTR_NONE); 1090 if (err) { 1091 ext4_std_error(sb, err); 1092 goto out; 1093 } 1094 ext4_lock_group(sb, group); 1095 ret2 = ext4_test_and_set_bit(ino, inode_bitmap_bh->b_data); 1096 if (ret2) { 1097 /* Someone already took the bit. Repeat the search 1098 * with lock held. 1099 */ 1100 ret2 = find_inode_bit(sb, group, inode_bitmap_bh, &ino); 1101 if (ret2) { 1102 ext4_set_bit(ino, inode_bitmap_bh->b_data); 1103 ret2 = 0; 1104 } else { 1105 ret2 = 1; /* we didn't grab the inode */ 1106 } 1107 } 1108 ext4_unlock_group(sb, group); 1109 ino++; /* the inode bitmap is zero-based */ 1110 if (!ret2) 1111 goto got; /* we grabbed the inode! */ 1112 1113 if (ino < EXT4_INODES_PER_GROUP(sb)) 1114 goto repeat_in_this_group; 1115 next_group: 1116 if (++group == ngroups) 1117 group = 0; 1118 } 1119 err = -ENOSPC; 1120 goto out; 1121 1122 got: 1123 BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata"); 1124 err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh); 1125 if (err) { 1126 ext4_std_error(sb, err); 1127 goto out; 1128 } 1129 1130 BUFFER_TRACE(group_desc_bh, "get_write_access"); 1131 err = ext4_journal_get_write_access(handle, sb, group_desc_bh, 1132 EXT4_JTR_NONE); 1133 if (err) { 1134 ext4_std_error(sb, err); 1135 goto out; 1136 } 1137 1138 /* We may have to initialize the block bitmap if it isn't already */ 1139 if (ext4_has_group_desc_csum(sb) && 1140 gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) { 1141 struct buffer_head *block_bitmap_bh; 1142 1143 block_bitmap_bh = ext4_read_block_bitmap(sb, group); 1144 if (IS_ERR(block_bitmap_bh)) { 1145 err = PTR_ERR(block_bitmap_bh); 1146 goto out; 1147 } 1148 BUFFER_TRACE(block_bitmap_bh, "get block bitmap access"); 1149 err = ext4_journal_get_write_access(handle, sb, block_bitmap_bh, 1150 EXT4_JTR_NONE); 1151 if (err) { 1152 brelse(block_bitmap_bh); 1153 ext4_std_error(sb, err); 1154 goto out; 1155 } 1156 1157 BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap"); 1158 err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh); 1159 1160 /* recheck and clear flag under lock if we still need to */ 1161 ext4_lock_group(sb, group); 1162 if (ext4_has_group_desc_csum(sb) && 1163 (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) { 1164 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT); 1165 ext4_free_group_clusters_set(sb, gdp, 1166 ext4_free_clusters_after_init(sb, group, gdp)); 1167 ext4_block_bitmap_csum_set(sb, gdp, block_bitmap_bh); 1168 ext4_group_desc_csum_set(sb, group, gdp); 1169 } 1170 ext4_unlock_group(sb, group); 1171 brelse(block_bitmap_bh); 1172 1173 if (err) { 1174 ext4_std_error(sb, err); 1175 goto out; 1176 } 1177 } 1178 1179 /* Update the relevant bg descriptor fields */ 1180 if (ext4_has_group_desc_csum(sb)) { 1181 int free; 1182 struct ext4_group_info *grp = NULL; 1183 1184 if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) { 1185 grp = ext4_get_group_info(sb, group); 1186 if (!grp) { 1187 err = -EFSCORRUPTED; 1188 goto out; 1189 } 1190 down_read(&grp->alloc_sem); /* 1191 * protect vs itable 1192 * lazyinit 1193 */ 1194 } 1195 ext4_lock_group(sb, group); /* while we modify the bg desc */ 1196 free = EXT4_INODES_PER_GROUP(sb) - 1197 ext4_itable_unused_count(sb, gdp); 1198 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) { 1199 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT); 1200 free = 0; 1201 } 1202 /* 1203 * Check the relative inode number against the last used 1204 * relative inode number in this group. if it is greater 1205 * we need to update the bg_itable_unused count 1206 */ 1207 if (ino > free) 1208 ext4_itable_unused_set(sb, gdp, 1209 (EXT4_INODES_PER_GROUP(sb) - ino)); 1210 if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) 1211 up_read(&grp->alloc_sem); 1212 } else { 1213 ext4_lock_group(sb, group); 1214 } 1215 1216 ext4_free_inodes_set(sb, gdp, ext4_free_inodes_count(sb, gdp) - 1); 1217 if (S_ISDIR(mode)) { 1218 ext4_used_dirs_set(sb, gdp, ext4_used_dirs_count(sb, gdp) + 1); 1219 if (sbi->s_log_groups_per_flex) { 1220 ext4_group_t f = ext4_flex_group(sbi, group); 1221 1222 atomic_inc(&sbi_array_rcu_deref(sbi, s_flex_groups, 1223 f)->used_dirs); 1224 } 1225 } 1226 if (ext4_has_group_desc_csum(sb)) { 1227 ext4_inode_bitmap_csum_set(sb, gdp, inode_bitmap_bh, 1228 EXT4_INODES_PER_GROUP(sb) / 8); 1229 ext4_group_desc_csum_set(sb, group, gdp); 1230 } 1231 ext4_unlock_group(sb, group); 1232 1233 BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata"); 1234 err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh); 1235 if (err) { 1236 ext4_std_error(sb, err); 1237 goto out; 1238 } 1239 1240 percpu_counter_dec(&sbi->s_freeinodes_counter); 1241 if (S_ISDIR(mode)) 1242 percpu_counter_inc(&sbi->s_dirs_counter); 1243 1244 if (sbi->s_log_groups_per_flex) { 1245 flex_group = ext4_flex_group(sbi, group); 1246 atomic_dec(&sbi_array_rcu_deref(sbi, s_flex_groups, 1247 flex_group)->free_inodes); 1248 } 1249 1250 inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb); 1251 /* This is the optimal IO size (for stat), not the fs block size */ 1252 inode->i_blocks = 0; 1253 simple_inode_init_ts(inode); 1254 ei->i_crtime = inode_get_mtime(inode); 1255 1256 memset(ei->i_data, 0, sizeof(ei->i_data)); 1257 ei->i_dir_start_lookup = 0; 1258 ei->i_disksize = 0; 1259 1260 /* Don't inherit extent flag from directory, amongst others. */ 1261 ei->i_flags = 1262 ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED); 1263 ei->i_flags |= i_flags; 1264 ei->i_file_acl = 0; 1265 ei->i_dtime = 0; 1266 ei->i_block_group = group; 1267 ei->i_last_alloc_group = ~0; 1268 1269 ext4_set_inode_flags(inode, true); 1270 if (IS_DIRSYNC(inode)) 1271 ext4_handle_sync(handle); 1272 if (insert_inode_locked(inode) < 0) { 1273 /* 1274 * Likely a bitmap corruption causing inode to be allocated 1275 * twice. 1276 */ 1277 err = -EIO; 1278 ext4_error(sb, "failed to insert inode %lu: doubly allocated?", 1279 inode->i_ino); 1280 ext4_mark_group_bitmap_corrupted(sb, group, 1281 EXT4_GROUP_INFO_IBITMAP_CORRUPT); 1282 goto out; 1283 } 1284 inode->i_generation = get_random_u32(); 1285 1286 /* Precompute checksum seed for inode metadata */ 1287 if (ext4_has_metadata_csum(sb)) { 1288 __u32 csum; 1289 __le32 inum = cpu_to_le32(inode->i_ino); 1290 __le32 gen = cpu_to_le32(inode->i_generation); 1291 csum = ext4_chksum(sbi, sbi->s_csum_seed, (__u8 *)&inum, 1292 sizeof(inum)); 1293 ei->i_csum_seed = ext4_chksum(sbi, csum, (__u8 *)&gen, 1294 sizeof(gen)); 1295 } 1296 1297 ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */ 1298 ext4_set_inode_state(inode, EXT4_STATE_NEW); 1299 1300 ei->i_extra_isize = sbi->s_want_extra_isize; 1301 ei->i_inline_off = 0; 1302 if (ext4_has_feature_inline_data(sb) && 1303 (!(ei->i_flags & EXT4_DAX_FL) || S_ISDIR(mode))) 1304 ext4_set_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA); 1305 ret = inode; 1306 err = dquot_alloc_inode(inode); 1307 if (err) 1308 goto fail_drop; 1309 1310 /* 1311 * Since the encryption xattr will always be unique, create it first so 1312 * that it's less likely to end up in an external xattr block and 1313 * prevent its deduplication. 1314 */ 1315 if (encrypt) { 1316 err = fscrypt_set_context(inode, handle); 1317 if (err) 1318 goto fail_free_drop; 1319 } 1320 1321 if (!(ei->i_flags & EXT4_EA_INODE_FL)) { 1322 err = ext4_init_acl(handle, inode, dir); 1323 if (err) 1324 goto fail_free_drop; 1325 1326 err = ext4_init_security(handle, inode, dir, qstr); 1327 if (err) 1328 goto fail_free_drop; 1329 } 1330 1331 if (ext4_has_feature_extents(sb)) { 1332 /* set extent flag only for directory, file and normal symlink*/ 1333 if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) { 1334 ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS); 1335 ext4_ext_tree_init(handle, inode); 1336 } 1337 } 1338 1339 ext4_update_inode_fsync_trans(handle, inode, 1); 1340 1341 err = ext4_mark_inode_dirty(handle, inode); 1342 if (err) { 1343 ext4_std_error(sb, err); 1344 goto fail_free_drop; 1345 } 1346 1347 ext4_debug("allocating inode %lu\n", inode->i_ino); 1348 trace_ext4_allocate_inode(inode, dir, mode); 1349 brelse(inode_bitmap_bh); 1350 return ret; 1351 1352 fail_free_drop: 1353 dquot_free_inode(inode); 1354 fail_drop: 1355 clear_nlink(inode); 1356 unlock_new_inode(inode); 1357 out: 1358 dquot_drop(inode); 1359 inode->i_flags |= S_NOQUOTA; 1360 iput(inode); 1361 brelse(inode_bitmap_bh); 1362 return ERR_PTR(err); 1363 } 1364 1365 /* Verify that we are loading a valid orphan from disk */ 1366 struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino) 1367 { 1368 unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count); 1369 ext4_group_t block_group; 1370 int bit; 1371 struct buffer_head *bitmap_bh = NULL; 1372 struct inode *inode = NULL; 1373 int err = -EFSCORRUPTED; 1374 1375 if (ino < EXT4_FIRST_INO(sb) || ino > max_ino) 1376 goto bad_orphan; 1377 1378 block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb); 1379 bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb); 1380 bitmap_bh = ext4_read_inode_bitmap(sb, block_group); 1381 if (IS_ERR(bitmap_bh)) 1382 return ERR_CAST(bitmap_bh); 1383 1384 /* Having the inode bit set should be a 100% indicator that this 1385 * is a valid orphan (no e2fsck run on fs). Orphans also include 1386 * inodes that were being truncated, so we can't check i_nlink==0. 1387 */ 1388 if (!ext4_test_bit(bit, bitmap_bh->b_data)) 1389 goto bad_orphan; 1390 1391 inode = ext4_iget(sb, ino, EXT4_IGET_NORMAL); 1392 if (IS_ERR(inode)) { 1393 err = PTR_ERR(inode); 1394 ext4_error_err(sb, -err, 1395 "couldn't read orphan inode %lu (err %d)", 1396 ino, err); 1397 brelse(bitmap_bh); 1398 return inode; 1399 } 1400 1401 /* 1402 * If the orphans has i_nlinks > 0 then it should be able to 1403 * be truncated, otherwise it won't be removed from the orphan 1404 * list during processing and an infinite loop will result. 1405 * Similarly, it must not be a bad inode. 1406 */ 1407 if ((inode->i_nlink && !ext4_can_truncate(inode)) || 1408 is_bad_inode(inode)) 1409 goto bad_orphan; 1410 1411 if (NEXT_ORPHAN(inode) > max_ino) 1412 goto bad_orphan; 1413 brelse(bitmap_bh); 1414 return inode; 1415 1416 bad_orphan: 1417 ext4_error(sb, "bad orphan inode %lu", ino); 1418 if (bitmap_bh) 1419 printk(KERN_ERR "ext4_test_bit(bit=%d, block=%llu) = %d\n", 1420 bit, (unsigned long long)bitmap_bh->b_blocknr, 1421 ext4_test_bit(bit, bitmap_bh->b_data)); 1422 if (inode) { 1423 printk(KERN_ERR "is_bad_inode(inode)=%d\n", 1424 is_bad_inode(inode)); 1425 printk(KERN_ERR "NEXT_ORPHAN(inode)=%u\n", 1426 NEXT_ORPHAN(inode)); 1427 printk(KERN_ERR "max_ino=%lu\n", max_ino); 1428 printk(KERN_ERR "i_nlink=%u\n", inode->i_nlink); 1429 /* Avoid freeing blocks if we got a bad deleted inode */ 1430 if (inode->i_nlink == 0) 1431 inode->i_blocks = 0; 1432 iput(inode); 1433 } 1434 brelse(bitmap_bh); 1435 return ERR_PTR(err); 1436 } 1437 1438 unsigned long ext4_count_free_inodes(struct super_block *sb) 1439 { 1440 unsigned long desc_count; 1441 struct ext4_group_desc *gdp; 1442 ext4_group_t i, ngroups = ext4_get_groups_count(sb); 1443 #ifdef EXT4FS_DEBUG 1444 struct ext4_super_block *es; 1445 unsigned long bitmap_count, x; 1446 struct buffer_head *bitmap_bh = NULL; 1447 1448 es = EXT4_SB(sb)->s_es; 1449 desc_count = 0; 1450 bitmap_count = 0; 1451 gdp = NULL; 1452 for (i = 0; i < ngroups; i++) { 1453 gdp = ext4_get_group_desc(sb, i, NULL); 1454 if (!gdp) 1455 continue; 1456 desc_count += ext4_free_inodes_count(sb, gdp); 1457 brelse(bitmap_bh); 1458 bitmap_bh = ext4_read_inode_bitmap(sb, i); 1459 if (IS_ERR(bitmap_bh)) { 1460 bitmap_bh = NULL; 1461 continue; 1462 } 1463 1464 x = ext4_count_free(bitmap_bh->b_data, 1465 EXT4_INODES_PER_GROUP(sb) / 8); 1466 printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n", 1467 (unsigned long) i, ext4_free_inodes_count(sb, gdp), x); 1468 bitmap_count += x; 1469 } 1470 brelse(bitmap_bh); 1471 printk(KERN_DEBUG "ext4_count_free_inodes: " 1472 "stored = %u, computed = %lu, %lu\n", 1473 le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count); 1474 return desc_count; 1475 #else 1476 desc_count = 0; 1477 for (i = 0; i < ngroups; i++) { 1478 gdp = ext4_get_group_desc(sb, i, NULL); 1479 if (!gdp) 1480 continue; 1481 desc_count += ext4_free_inodes_count(sb, gdp); 1482 cond_resched(); 1483 } 1484 return desc_count; 1485 #endif 1486 } 1487 1488 /* Called at mount-time, super-block is locked */ 1489 unsigned long ext4_count_dirs(struct super_block * sb) 1490 { 1491 unsigned long count = 0; 1492 ext4_group_t i, ngroups = ext4_get_groups_count(sb); 1493 1494 for (i = 0; i < ngroups; i++) { 1495 struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL); 1496 if (!gdp) 1497 continue; 1498 count += ext4_used_dirs_count(sb, gdp); 1499 } 1500 return count; 1501 } 1502 1503 /* 1504 * Zeroes not yet zeroed inode table - just write zeroes through the whole 1505 * inode table. Must be called without any spinlock held. The only place 1506 * where it is called from on active part of filesystem is ext4lazyinit 1507 * thread, so we do not need any special locks, however we have to prevent 1508 * inode allocation from the current group, so we take alloc_sem lock, to 1509 * block ext4_new_inode() until we are finished. 1510 */ 1511 int ext4_init_inode_table(struct super_block *sb, ext4_group_t group, 1512 int barrier) 1513 { 1514 struct ext4_group_info *grp = ext4_get_group_info(sb, group); 1515 struct ext4_sb_info *sbi = EXT4_SB(sb); 1516 struct ext4_group_desc *gdp = NULL; 1517 struct buffer_head *group_desc_bh; 1518 handle_t *handle; 1519 ext4_fsblk_t blk; 1520 int num, ret = 0, used_blks = 0; 1521 unsigned long used_inos = 0; 1522 1523 gdp = ext4_get_group_desc(sb, group, &group_desc_bh); 1524 if (!gdp || !grp) 1525 goto out; 1526 1527 /* 1528 * We do not need to lock this, because we are the only one 1529 * handling this flag. 1530 */ 1531 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_ZEROED)) 1532 goto out; 1533 1534 handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1); 1535 if (IS_ERR(handle)) { 1536 ret = PTR_ERR(handle); 1537 goto out; 1538 } 1539 1540 down_write(&grp->alloc_sem); 1541 /* 1542 * If inode bitmap was already initialized there may be some 1543 * used inodes so we need to skip blocks with used inodes in 1544 * inode table. 1545 */ 1546 if (!(gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT))) { 1547 used_inos = EXT4_INODES_PER_GROUP(sb) - 1548 ext4_itable_unused_count(sb, gdp); 1549 used_blks = DIV_ROUND_UP(used_inos, sbi->s_inodes_per_block); 1550 1551 /* Bogus inode unused count? */ 1552 if (used_blks < 0 || used_blks > sbi->s_itb_per_group) { 1553 ext4_error(sb, "Something is wrong with group %u: " 1554 "used itable blocks: %d; " 1555 "itable unused count: %u", 1556 group, used_blks, 1557 ext4_itable_unused_count(sb, gdp)); 1558 ret = 1; 1559 goto err_out; 1560 } 1561 1562 used_inos += group * EXT4_INODES_PER_GROUP(sb); 1563 /* 1564 * Are there some uninitialized inodes in the inode table 1565 * before the first normal inode? 1566 */ 1567 if ((used_blks != sbi->s_itb_per_group) && 1568 (used_inos < EXT4_FIRST_INO(sb))) { 1569 ext4_error(sb, "Something is wrong with group %u: " 1570 "itable unused count: %u; " 1571 "itables initialized count: %ld", 1572 group, ext4_itable_unused_count(sb, gdp), 1573 used_inos); 1574 ret = 1; 1575 goto err_out; 1576 } 1577 } 1578 1579 blk = ext4_inode_table(sb, gdp) + used_blks; 1580 num = sbi->s_itb_per_group - used_blks; 1581 1582 BUFFER_TRACE(group_desc_bh, "get_write_access"); 1583 ret = ext4_journal_get_write_access(handle, sb, group_desc_bh, 1584 EXT4_JTR_NONE); 1585 if (ret) 1586 goto err_out; 1587 1588 /* 1589 * Skip zeroout if the inode table is full. But we set the ZEROED 1590 * flag anyway, because obviously, when it is full it does not need 1591 * further zeroing. 1592 */ 1593 if (unlikely(num == 0)) 1594 goto skip_zeroout; 1595 1596 ext4_debug("going to zero out inode table in group %d\n", 1597 group); 1598 ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS); 1599 if (ret < 0) 1600 goto err_out; 1601 if (barrier) 1602 blkdev_issue_flush(sb->s_bdev); 1603 1604 skip_zeroout: 1605 ext4_lock_group(sb, group); 1606 gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED); 1607 ext4_group_desc_csum_set(sb, group, gdp); 1608 ext4_unlock_group(sb, group); 1609 1610 BUFFER_TRACE(group_desc_bh, 1611 "call ext4_handle_dirty_metadata"); 1612 ret = ext4_handle_dirty_metadata(handle, NULL, 1613 group_desc_bh); 1614 1615 err_out: 1616 up_write(&grp->alloc_sem); 1617 ext4_journal_stop(handle); 1618 out: 1619 return ret; 1620 } 1621