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