ialloc.c (717d50e4971b81b96c0199c91cdf0039a8cb181a) ialloc.c (fd2d42912f9f09e5250cb3b024ee0625704e9cb7)
1/*
2 * linux/fs/ext4/ialloc.c
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 *

--- 50 unchanged lines hidden (view full) ---

59 ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
60 for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
61 ext4_set_bit(i, bitmap);
62 if (i < end_bit)
63 memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
64}
65
66/* Initializes an uninitialized inode bitmap */
1/*
2 * linux/fs/ext4/ialloc.c
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 *

--- 50 unchanged lines hidden (view full) ---

59 ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
60 for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
61 ext4_set_bit(i, bitmap);
62 if (i < end_bit)
63 memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
64}
65
66/* Initializes an uninitialized inode bitmap */
67unsigned ext4_init_inode_bitmap(struct super_block *sb,
68 struct buffer_head *bh, int block_group,
67unsigned ext4_init_inode_bitmap(struct super_block *sb, struct buffer_head *bh,
68 ext4_group_t block_group,
69 struct ext4_group_desc *gdp)
70{
71 struct ext4_sb_info *sbi = EXT4_SB(sb);
72
73 J_ASSERT_BH(bh, buffer_locked(bh));
74
75 /* If checksum is bad mark all blocks and inodes use to prevent
76 * allocation, essentially implementing a per-group read-only flag. */
77 if (!ext4_group_desc_csum_verify(sbi, block_group, gdp)) {
69 struct ext4_group_desc *gdp)
70{
71 struct ext4_sb_info *sbi = EXT4_SB(sb);
72
73 J_ASSERT_BH(bh, buffer_locked(bh));
74
75 /* If checksum is bad mark all blocks and inodes use to prevent
76 * allocation, essentially implementing a per-group read-only flag. */
77 if (!ext4_group_desc_csum_verify(sbi, block_group, gdp)) {
78 ext4_error(sb, __FUNCTION__, "Checksum bad for group %u\n",
78 ext4_error(sb, __FUNCTION__, "Checksum bad for group %lu\n",
79 block_group);
80 gdp->bg_free_blocks_count = 0;
81 gdp->bg_free_inodes_count = 0;
82 gdp->bg_itable_unused = 0;
83 memset(bh->b_data, 0xff, sb->s_blocksize);
84 return 0;
85 }
86

--- 6 unchanged lines hidden (view full) ---

93
94/*
95 * Read the inode allocation bitmap for a given block_group, reading
96 * into the specified slot in the superblock's bitmap cache.
97 *
98 * Return buffer_head of bitmap on success or NULL.
99 */
100static struct buffer_head *
79 block_group);
80 gdp->bg_free_blocks_count = 0;
81 gdp->bg_free_inodes_count = 0;
82 gdp->bg_itable_unused = 0;
83 memset(bh->b_data, 0xff, sb->s_blocksize);
84 return 0;
85 }
86

--- 6 unchanged lines hidden (view full) ---

93
94/*
95 * Read the inode allocation bitmap for a given block_group, reading
96 * into the specified slot in the superblock's bitmap cache.
97 *
98 * Return buffer_head of bitmap on success or NULL.
99 */
100static struct buffer_head *
101read_inode_bitmap(struct super_block * sb, unsigned long block_group)
101read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
102{
103 struct ext4_group_desc *desc;
104 struct buffer_head *bh = NULL;
105
106 desc = ext4_get_group_desc(sb, block_group, NULL);
107 if (!desc)
108 goto error_out;
109 if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {

--- 37 unchanged lines hidden (view full) ---

147 */
148void ext4_free_inode (handle_t *handle, struct inode * inode)
149{
150 struct super_block * sb = inode->i_sb;
151 int is_directory;
152 unsigned long ino;
153 struct buffer_head *bitmap_bh = NULL;
154 struct buffer_head *bh2;
102{
103 struct ext4_group_desc *desc;
104 struct buffer_head *bh = NULL;
105
106 desc = ext4_get_group_desc(sb, block_group, NULL);
107 if (!desc)
108 goto error_out;
109 if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {

--- 37 unchanged lines hidden (view full) ---

147 */
148void ext4_free_inode (handle_t *handle, struct inode * inode)
149{
150 struct super_block * sb = inode->i_sb;
151 int is_directory;
152 unsigned long ino;
153 struct buffer_head *bitmap_bh = NULL;
154 struct buffer_head *bh2;
155 unsigned long block_group;
155 ext4_group_t block_group;
156 unsigned long bit;
157 struct ext4_group_desc * gdp;
158 struct ext4_super_block * es;
159 struct ext4_sb_info *sbi;
160 int fatal = 0, err;
161
162 if (atomic_read(&inode->i_count) > 1) {
163 printk ("ext4_free_inode: inode has count=%d\n",

--- 91 unchanged lines hidden (view full) ---

255 * a directory, then a forward search is made for a block group with both
256 * free space and a low directory-to-inode ratio; if that fails, then of
257 * the groups with above-average free space, that group with the fewest
258 * directories already is chosen.
259 *
260 * For other inodes, search forward from the parent directory\'s block
261 * group to find a free inode.
262 */
156 unsigned long bit;
157 struct ext4_group_desc * gdp;
158 struct ext4_super_block * es;
159 struct ext4_sb_info *sbi;
160 int fatal = 0, err;
161
162 if (atomic_read(&inode->i_count) > 1) {
163 printk ("ext4_free_inode: inode has count=%d\n",

--- 91 unchanged lines hidden (view full) ---

255 * a directory, then a forward search is made for a block group with both
256 * free space and a low directory-to-inode ratio; if that fails, then of
257 * the groups with above-average free space, that group with the fewest
258 * directories already is chosen.
259 *
260 * For other inodes, search forward from the parent directory\'s block
261 * group to find a free inode.
262 */
263static int find_group_dir(struct super_block *sb, struct inode *parent)
263static ext4_group_t find_group_dir(struct super_block *sb, struct inode *parent)
264{
264{
265 int ngroups = EXT4_SB(sb)->s_groups_count;
265 ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
266 unsigned int freei, avefreei;
267 struct ext4_group_desc *desc, *best_desc = NULL;
266 unsigned int freei, avefreei;
267 struct ext4_group_desc *desc, *best_desc = NULL;
268 int group, best_group = -1;
268 ext4_group_t group, best_group = -1;
269
270 freei = percpu_counter_read_positive(&EXT4_SB(sb)->s_freeinodes_counter);
271 avefreei = freei / ngroups;
272
273 for (group = 0; group < ngroups; group++) {
274 desc = ext4_get_group_desc (sb, group, NULL);
275 if (!desc || !desc->bg_free_inodes_count)
276 continue;

--- 32 unchanged lines hidden (view full) ---

309 *
310 * Debt is incremented each time we allocate a directory and decremented
311 * when we allocate an inode, within 0--255.
312 */
313
314#define INODE_COST 64
315#define BLOCK_COST 256
316
269
270 freei = percpu_counter_read_positive(&EXT4_SB(sb)->s_freeinodes_counter);
271 avefreei = freei / ngroups;
272
273 for (group = 0; group < ngroups; group++) {
274 desc = ext4_get_group_desc (sb, group, NULL);
275 if (!desc || !desc->bg_free_inodes_count)
276 continue;

--- 32 unchanged lines hidden (view full) ---

309 *
310 * Debt is incremented each time we allocate a directory and decremented
311 * when we allocate an inode, within 0--255.
312 */
313
314#define INODE_COST 64
315#define BLOCK_COST 256
316
317static int find_group_orlov(struct super_block *sb, struct inode *parent)
317static ext4_group_t find_group_orlov(struct super_block *sb,
318 struct inode *parent)
318{
319{
319 int parent_group = EXT4_I(parent)->i_block_group;
320 ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
320 struct ext4_sb_info *sbi = EXT4_SB(sb);
321 struct ext4_super_block *es = sbi->s_es;
321 struct ext4_sb_info *sbi = EXT4_SB(sb);
322 struct ext4_super_block *es = sbi->s_es;
322 int ngroups = sbi->s_groups_count;
323 ext4_group_t ngroups = sbi->s_groups_count;
323 int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
324 unsigned int freei, avefreei;
325 ext4_fsblk_t freeb, avefreeb;
326 ext4_fsblk_t blocks_per_dir;
327 unsigned int ndirs;
328 int max_debt, max_dirs, min_inodes;
329 ext4_grpblk_t min_blocks;
324 int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
325 unsigned int freei, avefreei;
326 ext4_fsblk_t freeb, avefreeb;
327 ext4_fsblk_t blocks_per_dir;
328 unsigned int ndirs;
329 int max_debt, max_dirs, min_inodes;
330 ext4_grpblk_t min_blocks;
330 int group = -1, i;
331 ext4_group_t group = -1, i;
331 struct ext4_group_desc *desc;
332
333 freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
334 avefreei = freei / ngroups;
335 freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
336 avefreeb = freeb;
337 do_div(avefreeb, ngroups);
338 ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
339
340 if ((parent == sb->s_root->d_inode) ||
341 (EXT4_I(parent)->i_flags & EXT4_TOPDIR_FL)) {
342 int best_ndir = inodes_per_group;
332 struct ext4_group_desc *desc;
333
334 freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
335 avefreei = freei / ngroups;
336 freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
337 avefreeb = freeb;
338 do_div(avefreeb, ngroups);
339 ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
340
341 if ((parent == sb->s_root->d_inode) ||
342 (EXT4_I(parent)->i_flags & EXT4_TOPDIR_FL)) {
343 int best_ndir = inodes_per_group;
343 int best_group = -1;
344 ext4_group_t best_group = -1;
344
345 get_random_bytes(&group, sizeof(group));
346 parent_group = (unsigned)group % ngroups;
347 for (i = 0; i < ngroups; i++) {
348 group = (parent_group + i) % ngroups;
349 desc = ext4_get_group_desc (sb, group, NULL);
350 if (!desc || !desc->bg_free_inodes_count)
351 continue;

--- 58 unchanged lines hidden (view full) ---

410 */
411 avefreei = 0;
412 goto fallback;
413 }
414
415 return -1;
416}
417
345
346 get_random_bytes(&group, sizeof(group));
347 parent_group = (unsigned)group % ngroups;
348 for (i = 0; i < ngroups; i++) {
349 group = (parent_group + i) % ngroups;
350 desc = ext4_get_group_desc (sb, group, NULL);
351 if (!desc || !desc->bg_free_inodes_count)
352 continue;

--- 58 unchanged lines hidden (view full) ---

411 */
412 avefreei = 0;
413 goto fallback;
414 }
415
416 return -1;
417}
418
418static int find_group_other(struct super_block *sb, struct inode *parent)
419static ext4_group_t find_group_other(struct super_block *sb,
420 struct inode *parent)
419{
421{
420 int parent_group = EXT4_I(parent)->i_block_group;
421 int ngroups = EXT4_SB(sb)->s_groups_count;
422 ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
423 ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
422 struct ext4_group_desc *desc;
424 struct ext4_group_desc *desc;
423 int group, i;
425 ext4_group_t group, i;
424
425 /*
426 * Try to place the inode in its parent directory
427 */
428 group = parent_group;
429 desc = ext4_get_group_desc (sb, group, NULL);
430 if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
431 le16_to_cpu(desc->bg_free_blocks_count))

--- 50 unchanged lines hidden (view full) ---

482 * For other inodes, search forward from the parent directory's block
483 * group to find a free inode.
484 */
485struct inode *ext4_new_inode(handle_t *handle, struct inode * dir, int mode)
486{
487 struct super_block *sb;
488 struct buffer_head *bitmap_bh = NULL;
489 struct buffer_head *bh2;
426
427 /*
428 * Try to place the inode in its parent directory
429 */
430 group = parent_group;
431 desc = ext4_get_group_desc (sb, group, NULL);
432 if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
433 le16_to_cpu(desc->bg_free_blocks_count))

--- 50 unchanged lines hidden (view full) ---

484 * For other inodes, search forward from the parent directory's block
485 * group to find a free inode.
486 */
487struct inode *ext4_new_inode(handle_t *handle, struct inode * dir, int mode)
488{
489 struct super_block *sb;
490 struct buffer_head *bitmap_bh = NULL;
491 struct buffer_head *bh2;
490 int group;
492 ext4_group_t group;
491 unsigned long ino = 0;
492 struct inode * inode;
493 struct ext4_group_desc * gdp = NULL;
494 struct ext4_super_block * es;
495 struct ext4_inode_info *ei;
496 struct ext4_sb_info *sbi;
497 int err = 0;
498 struct inode *ret;

--- 79 unchanged lines hidden (view full) ---

578 goto out;
579
580got:
581 ino++;
582 if ((group == 0 && ino < EXT4_FIRST_INO(sb)) ||
583 ino > EXT4_INODES_PER_GROUP(sb)) {
584 ext4_error(sb, __FUNCTION__,
585 "reserved inode or inode > inodes count - "
493 unsigned long ino = 0;
494 struct inode * inode;
495 struct ext4_group_desc * gdp = NULL;
496 struct ext4_super_block * es;
497 struct ext4_inode_info *ei;
498 struct ext4_sb_info *sbi;
499 int err = 0;
500 struct inode *ret;

--- 79 unchanged lines hidden (view full) ---

580 goto out;
581
582got:
583 ino++;
584 if ((group == 0 && ino < EXT4_FIRST_INO(sb)) ||
585 ino > EXT4_INODES_PER_GROUP(sb)) {
586 ext4_error(sb, __FUNCTION__,
587 "reserved inode or inode > inodes count - "
586 "block_group = %d, inode=%lu", group,
588 "block_group = %lu, inode=%lu", group,
587 ino + group * EXT4_INODES_PER_GROUP(sb));
588 err = -EIO;
589 goto fail;
590 }
591
592 BUFFER_TRACE(bh2, "get_write_access");
593 err = ext4_journal_get_write_access(handle, bh2);
594 if (err) goto fail;

--- 177 unchanged lines hidden (view full) ---

772 brelse(bitmap_bh);
773 return ERR_PTR(err);
774}
775
776/* Verify that we are loading a valid orphan from disk */
777struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
778{
779 unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
589 ino + group * EXT4_INODES_PER_GROUP(sb));
590 err = -EIO;
591 goto fail;
592 }
593
594 BUFFER_TRACE(bh2, "get_write_access");
595 err = ext4_journal_get_write_access(handle, bh2);
596 if (err) goto fail;

--- 177 unchanged lines hidden (view full) ---

774 brelse(bitmap_bh);
775 return ERR_PTR(err);
776}
777
778/* Verify that we are loading a valid orphan from disk */
779struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
780{
781 unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
780 unsigned long block_group;
782 ext4_group_t block_group;
781 int bit;
782 struct buffer_head *bitmap_bh = NULL;
783 struct inode *inode = NULL;
784
785 /* Error cases - e2fsck has already cleaned up for us */
786 if (ino > max_ino) {
787 ext4_warning(sb, __FUNCTION__,
788 "bad orphan ino %lu! e2fsck was run?", ino);

--- 39 unchanged lines hidden (view full) ---

828 brelse(bitmap_bh);
829 return inode;
830}
831
832unsigned long ext4_count_free_inodes (struct super_block * sb)
833{
834 unsigned long desc_count;
835 struct ext4_group_desc *gdp;
783 int bit;
784 struct buffer_head *bitmap_bh = NULL;
785 struct inode *inode = NULL;
786
787 /* Error cases - e2fsck has already cleaned up for us */
788 if (ino > max_ino) {
789 ext4_warning(sb, __FUNCTION__,
790 "bad orphan ino %lu! e2fsck was run?", ino);

--- 39 unchanged lines hidden (view full) ---

830 brelse(bitmap_bh);
831 return inode;
832}
833
834unsigned long ext4_count_free_inodes (struct super_block * sb)
835{
836 unsigned long desc_count;
837 struct ext4_group_desc *gdp;
836 int i;
838 ext4_group_t i;
837#ifdef EXT4FS_DEBUG
838 struct ext4_super_block *es;
839 unsigned long bitmap_count, x;
840 struct buffer_head *bitmap_bh = NULL;
841
842 es = EXT4_SB(sb)->s_es;
843 desc_count = 0;
844 bitmap_count = 0;

--- 29 unchanged lines hidden (view full) ---

874 return desc_count;
875#endif
876}
877
878/* Called at mount-time, super-block is locked */
879unsigned long ext4_count_dirs (struct super_block * sb)
880{
881 unsigned long count = 0;
839#ifdef EXT4FS_DEBUG
840 struct ext4_super_block *es;
841 unsigned long bitmap_count, x;
842 struct buffer_head *bitmap_bh = NULL;
843
844 es = EXT4_SB(sb)->s_es;
845 desc_count = 0;
846 bitmap_count = 0;

--- 29 unchanged lines hidden (view full) ---

876 return desc_count;
877#endif
878}
879
880/* Called at mount-time, super-block is locked */
881unsigned long ext4_count_dirs (struct super_block * sb)
882{
883 unsigned long count = 0;
882 int i;
884 ext4_group_t i;
883
884 for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
885 struct ext4_group_desc *gdp = ext4_get_group_desc (sb, i, NULL);
886 if (!gdp)
887 continue;
888 count += le16_to_cpu(gdp->bg_used_dirs_count);
889 }
890 return count;
891}
892
885
886 for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
887 struct ext4_group_desc *gdp = ext4_get_group_desc (sb, i, NULL);
888 if (!gdp)
889 continue;
890 count += le16_to_cpu(gdp->bg_used_dirs_count);
891 }
892 return count;
893}
894