summaryrefslogtreecommitdiff
path: root/ext2fs
diff options
context:
space:
mode:
authorMiles Bader <miles@gnu.org>1995-04-11 02:25:14 +0000
committerMiles Bader <miles@gnu.org>1995-04-11 02:25:14 +0000
commit445d60d75f81a7428f80e29bdb59a4c2745a8bd5 (patch)
tree9185ef90be6c6302c31bf8099b77d801f25ab06c /ext2fs
parent54ab36c50603b0e85ed1fe7af348a31cd3714c97 (diff)
Initial revision
Diffstat (limited to 'ext2fs')
-rw-r--r--ext2fs/Makefile31
-rw-r--r--ext2fs/balloc.c583
-rw-r--r--ext2fs/bitmap.c26
-rw-r--r--ext2fs/ext2_fs.h505
-rw-r--r--ext2fs/ext2_fs_i.h40
-rw-r--r--ext2fs/ialloc.c555
-rw-r--r--ext2fs/truncate.c370
7 files changed, 2110 insertions, 0 deletions
diff --git a/ext2fs/Makefile b/ext2fs/Makefile
new file mode 100644
index 00000000..599f2ad8
--- /dev/null
+++ b/ext2fs/Makefile
@@ -0,0 +1,31 @@
+#
+# Makefile for the linux ext2-filesystem routines.
+#
+# Note! Dependencies are done automagically by 'make dep', which also
+# removes any old dependencies. DON'T put your own dependencies here
+# unless it's something special (ie not a .c file).
+#
+# Note 2! The CFLAGS definitions are now in the main makefile...
+
+.c.s:
+ $(CC) $(CFLAGS) -S $<
+.c.o:
+ $(CC) $(CFLAGS) -c $<
+.s.o:
+ $(AS) -o $*.o $<
+
+OBJS= acl.o balloc.o bitmap.o dir.o file.o fsync.o ialloc.o \
+ inode.o ioctl.o namei.o super.o symlink.o truncate.o
+
+ext2.o: $(OBJS)
+ $(LD) -r -o ext2.o $(OBJS)
+
+dep:
+ $(CPP) -M *.c > .depend
+
+#
+# include a dependency file if one exists
+#
+ifeq (.depend,$(wildcard .depend))
+include .depend
+endif
diff --git a/ext2fs/balloc.c b/ext2fs/balloc.c
new file mode 100644
index 00000000..c476fa2b
--- /dev/null
+++ b/ext2fs/balloc.c
@@ -0,0 +1,583 @@
+/*
+ * linux/fs/ext2/balloc.c
+ *
+ * Copyright (C) 1992, 1993, 1994, 1995
+ * Remy Card (card@masi.ibp.fr)
+ * Laboratoire MASI - Institut Blaise Pascal
+ * Universite Pierre et Marie Curie (Paris VI)
+ *
+ * Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
+ */
+
+/*
+ * balloc.c contains the blocks allocation and deallocation routines
+ */
+
+/*
+ * The free blocks are managed by bitmaps. A file system contains several
+ * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
+ * block for inodes, N blocks for the inode table and data blocks.
+ *
+ * The file system contains group descriptors which are located after the
+ * super block. Each descriptor contains the number of the bitmap block and
+ * the free blocks count in the block. The descriptors are loaded in memory
+ * when a file system is mounted (see ext2_read_super).
+ */
+
+#include <linux/fs.h>
+#include <linux/ext2_fs.h>
+#include <linux/stat.h>
+#include <linux/sched.h>
+#include <linux/string.h>
+#include <linux/locks.h>
+
+#include <asm/bitops.h>
+
+#define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
+
+static struct ext2_group_desc * get_group_desc (struct super_block * sb,
+ unsigned int block_group,
+ struct buffer_head ** bh)
+{
+ unsigned long group_desc;
+ unsigned long desc;
+ struct ext2_group_desc * gdp;
+
+ if (block_group >= sb->u.ext2_sb.s_groups_count)
+ ext2_panic (sb, "get_group_desc",
+ "block_group >= groups_count - "
+ "block_group = %d, groups_count = %lu",
+ block_group, sb->u.ext2_sb.s_groups_count);
+
+ group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
+ desc = block_group % EXT2_DESC_PER_BLOCK(sb);
+ if (!sb->u.ext2_sb.s_group_desc[group_desc])
+ ext2_panic (sb, "get_group_desc",
+ "Group descriptor not loaded - "
+ "block_group = %d, group_desc = %lu, desc = %lu",
+ block_group, group_desc, desc);
+ gdp = (struct ext2_group_desc *)
+ sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
+ if (bh)
+ *bh = sb->u.ext2_sb.s_group_desc[group_desc];
+ return gdp + desc;
+}
+
+static void read_block_bitmap (struct super_block * sb,
+ unsigned int block_group,
+ unsigned long bitmap_nr)
+{
+ struct ext2_group_desc * gdp;
+ struct buffer_head * bh;
+
+ gdp = get_group_desc (sb, block_group, NULL);
+ bh = bread (sb->s_dev, gdp->bg_block_bitmap, sb->s_blocksize);
+ if (!bh)
+ ext2_panic (sb, "read_block_bitmap",
+ "Cannot read block bitmap - "
+ "block_group = %d, block_bitmap = %lu",
+ block_group, (unsigned long) gdp->bg_block_bitmap);
+ sb->u.ext2_sb.s_block_bitmap_number[bitmap_nr] = block_group;
+ sb->u.ext2_sb.s_block_bitmap[bitmap_nr] = bh;
+}
+
+/*
+ * load_block_bitmap loads the block bitmap for a blocks group
+ *
+ * It maintains a cache for the last bitmaps loaded. This cache is managed
+ * with a LRU algorithm.
+ *
+ * Notes:
+ * 1/ There is one cache per mounted file system.
+ * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
+ * this function reads the bitmap without maintaining a LRU cache.
+ */
+static int load__block_bitmap (struct super_block * sb,
+ unsigned int block_group)
+{
+ int i, j;
+ unsigned long block_bitmap_number;
+ struct buffer_head * block_bitmap;
+
+ if (block_group >= sb->u.ext2_sb.s_groups_count)
+ ext2_panic (sb, "load_block_bitmap",
+ "block_group >= groups_count - "
+ "block_group = %d, groups_count = %lu",
+ block_group, sb->u.ext2_sb.s_groups_count);
+
+ if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
+ if (sb->u.ext2_sb.s_block_bitmap[block_group]) {
+ if (sb->u.ext2_sb.s_block_bitmap_number[block_group] !=
+ block_group)
+ ext2_panic (sb, "load_block_bitmap",
+ "block_group != block_bitmap_number");
+ else
+ return block_group;
+ } else {
+ read_block_bitmap (sb, block_group, block_group);
+ return block_group;
+ }
+ }
+
+ for (i = 0; i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
+ sb->u.ext2_sb.s_block_bitmap_number[i] != block_group; i++)
+ ;
+ if (i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
+ sb->u.ext2_sb.s_block_bitmap_number[i] == block_group) {
+ block_bitmap_number = sb->u.ext2_sb.s_block_bitmap_number[i];
+ block_bitmap = sb->u.ext2_sb.s_block_bitmap[i];
+ for (j = i; j > 0; j--) {
+ sb->u.ext2_sb.s_block_bitmap_number[j] =
+ sb->u.ext2_sb.s_block_bitmap_number[j - 1];
+ sb->u.ext2_sb.s_block_bitmap[j] =
+ sb->u.ext2_sb.s_block_bitmap[j - 1];
+ }
+ sb->u.ext2_sb.s_block_bitmap_number[0] = block_bitmap_number;
+ sb->u.ext2_sb.s_block_bitmap[0] = block_bitmap;
+ } else {
+ if (sb->u.ext2_sb.s_loaded_block_bitmaps < EXT2_MAX_GROUP_LOADED)
+ sb->u.ext2_sb.s_loaded_block_bitmaps++;
+ else
+ brelse (sb->u.ext2_sb.s_block_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
+ for (j = sb->u.ext2_sb.s_loaded_block_bitmaps - 1; j > 0; j--) {
+ sb->u.ext2_sb.s_block_bitmap_number[j] =
+ sb->u.ext2_sb.s_block_bitmap_number[j - 1];
+ sb->u.ext2_sb.s_block_bitmap[j] =
+ sb->u.ext2_sb.s_block_bitmap[j - 1];
+ }
+ read_block_bitmap (sb, block_group, 0);
+ }
+ return 0;
+}
+
+static inline int load_block_bitmap (struct super_block * sb,
+ unsigned int block_group)
+{
+ if (sb->u.ext2_sb.s_loaded_block_bitmaps > 0 &&
+ sb->u.ext2_sb.s_block_bitmap_number[0] == block_group)
+ return 0;
+
+ if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED &&
+ sb->u.ext2_sb.s_block_bitmap_number[block_group] == block_group &&
+ sb->u.ext2_sb.s_block_bitmap[block_group])
+ return block_group;
+
+ return load__block_bitmap (sb, block_group);
+}
+
+void ext2_free_blocks (struct super_block * sb, unsigned long block,
+ unsigned long count)
+{
+ struct buffer_head * bh;
+ struct buffer_head * bh2;
+ unsigned long block_group;
+ unsigned long bit;
+ unsigned long i;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ struct ext2_super_block * es;
+
+ if (!sb) {
+ printk ("ext2_free_blocks: nonexistent device");
+ return;
+ }
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+ if (block < es->s_first_data_block ||
+ (block + count) > es->s_blocks_count) {
+ ext2_error (sb, "ext2_free_blocks",
+ "Freeing blocks not in datazone - "
+ "block = %lu, count = %lu", block, count);
+ unlock_super (sb);
+ return;
+ }
+
+ ext2_debug ("freeing block %lu\n", block);
+
+ block_group = (block - es->s_first_data_block) /
+ EXT2_BLOCKS_PER_GROUP(sb);
+ bit = (block - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb);
+ if (bit + count > EXT2_BLOCKS_PER_GROUP(sb))
+ ext2_panic (sb, "ext2_free_blocks",
+ "Freeing blocks across group boundary - "
+ "Block = %lu, count = %lu",
+ block, count);
+ bitmap_nr = load_block_bitmap (sb, block_group);
+ bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
+ gdp = get_group_desc (sb, block_group, &bh2);
+
+ if (test_opt (sb, CHECK_STRICT) &&
+ (in_range (gdp->bg_block_bitmap, block, count) ||
+ in_range (gdp->bg_inode_bitmap, block, count) ||
+ in_range (block, gdp->bg_inode_table,
+ sb->u.ext2_sb.s_itb_per_group) ||
+ in_range (block + count - 1, gdp->bg_inode_table,
+ sb->u.ext2_sb.s_itb_per_group)))
+ ext2_panic (sb, "ext2_free_blocks",
+ "Freeing blocks in system zones - "
+ "Block = %lu, count = %lu",
+ block, count);
+
+ for (i = 0; i < count; i++) {
+ if (!clear_bit (bit + i, bh->b_data))
+ ext2_warning (sb, "ext2_free_blocks",
+ "bit already cleared for block %lu",
+ block);
+ else {
+ gdp->bg_free_blocks_count++;
+ es->s_free_blocks_count++;
+ }
+ }
+
+ mark_buffer_dirty(bh2, 1);
+ mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
+
+ mark_buffer_dirty(bh, 1);
+ if (sb->s_flags & MS_SYNCHRONOUS) {
+ ll_rw_block (WRITE, 1, &bh);
+ wait_on_buffer (bh);
+ }
+ sb->s_dirt = 1;
+ unlock_super (sb);
+ return;
+}
+
+/*
+ * ext2_new_block uses a goal block to assist allocation. If the goal is
+ * free, or there is a free block within 32 blocks of the goal, that block
+ * is allocated. Otherwise a forward search is made for a free block; within
+ * each block group the search first looks for an entire free byte in the block
+ * bitmap, and then for any free bit if that fails.
+ */
+int ext2_new_block (struct super_block * sb, unsigned long goal,
+ u32 * prealloc_count,
+ u32 * prealloc_block)
+{
+ struct buffer_head * bh;
+ struct buffer_head * bh2;
+ char * p, * r;
+ int i, j, k, tmp;
+ unsigned long lmap;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ struct ext2_super_block * es;
+
+#ifdef EXT2FS_DEBUG
+ static int goal_hits = 0, goal_attempts = 0;
+#endif
+ if (!sb) {
+ printk ("ext2_new_block: nonexistent device");
+ return 0;
+ }
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+ if (es->s_free_blocks_count <= es->s_r_blocks_count &&
+ (!fsuser() && (sb->u.ext2_sb.s_resuid != current->fsuid) &&
+ (sb->u.ext2_sb.s_resgid == 0 ||
+ !in_group_p (sb->u.ext2_sb.s_resgid)))) {
+ unlock_super (sb);
+ return 0;
+ }
+
+ ext2_debug ("goal=%lu.\n", goal);
+
+repeat:
+ /*
+ * First, test whether the goal block is free.
+ */
+ if (goal < es->s_first_data_block || goal >= es->s_blocks_count)
+ goal = es->s_first_data_block;
+ i = (goal - es->s_first_data_block) / EXT2_BLOCKS_PER_GROUP(sb);
+ gdp = get_group_desc (sb, i, &bh2);
+ if (gdp->bg_free_blocks_count > 0) {
+ j = ((goal - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb));
+#ifdef EXT2FS_DEBUG
+ if (j)
+ goal_attempts++;
+#endif
+ bitmap_nr = load_block_bitmap (sb, i);
+ bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
+
+ ext2_debug ("goal is at %d:%d.\n", i, j);
+
+ if (!test_bit(j, bh->b_data)) {
+#ifdef EXT2FS_DEBUG
+ goal_hits++;
+ ext2_debug ("goal bit allocated.\n");
+#endif
+ goto got_block;
+ }
+ if (j) {
+ /*
+ * The goal was occupied; search forward for a free
+ * block within the next 32 blocks
+ */
+ lmap = ((((unsigned long *) bh->b_data)[j >> 5]) >>
+ ((j & 31) + 1));
+ if (j < EXT2_BLOCKS_PER_GROUP(sb) - 32)
+ lmap |= (((unsigned long *) bh->b_data)[(j >> 5) + 1]) <<
+ (31 - (j & 31));
+ else
+ lmap |= 0xffffffff << (31 - (j & 31));
+ if (lmap != 0xffffffffl) {
+ k = ffz(lmap) + 1;
+ if ((j + k) < EXT2_BLOCKS_PER_GROUP(sb)) {
+ j += k;
+ goto got_block;
+ }
+ }
+ }
+
+ ext2_debug ("Bit not found near goal\n");
+
+ /*
+ * There has been no free block found in the near vicinity
+ * of the goal: do a search forward through the block groups,
+ * searching in each group first for an entire free byte in
+ * the bitmap and then for any free bit.
+ *
+ * Search first in the remainder of the current group; then,
+ * cyclicly search through the rest of the groups.
+ */
+ p = ((char *) bh->b_data) + (j >> 3);
+ r = memscan(p, 0, (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
+ k = (r - ((char *) bh->b_data)) << 3;
+ if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
+ j = k;
+ goto search_back;
+ }
+ k = find_next_zero_bit ((unsigned long *) bh->b_data,
+ EXT2_BLOCKS_PER_GROUP(sb),
+ j);
+ if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
+ j = k;
+ goto got_block;
+ }
+ }
+
+ ext2_debug ("Bit not found in block group %d.\n", i);
+
+ /*
+ * Now search the rest of the groups. We assume that
+ * i and gdp correctly point to the last group visited.
+ */
+ for (k = 0; k < sb->u.ext2_sb.s_groups_count; k++) {
+ i++;
+ if (i >= sb->u.ext2_sb.s_groups_count)
+ i = 0;
+ gdp = get_group_desc (sb, i, &bh2);
+ if (gdp->bg_free_blocks_count > 0)
+ break;
+ }
+ if (k >= sb->u.ext2_sb.s_groups_count) {
+ unlock_super (sb);
+ return 0;
+ }
+ bitmap_nr = load_block_bitmap (sb, i);
+ bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
+ r = memscan(bh->b_data, 0, EXT2_BLOCKS_PER_GROUP(sb) >> 3);
+ j = (r - bh->b_data) << 3;
+ if (j < EXT2_BLOCKS_PER_GROUP(sb))
+ goto search_back;
+ else
+ j = find_first_zero_bit ((unsigned long *) bh->b_data,
+ EXT2_BLOCKS_PER_GROUP(sb));
+ if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
+ ext2_error (sb, "ext2_new_block",
+ "Free blocks count corrupted for block group %d", i);
+ unlock_super (sb);
+ return 0;
+ }
+
+search_back:
+ /*
+ * We have succeeded in finding a free byte in the block
+ * bitmap. Now search backwards up to 7 bits to find the
+ * start of this group of free blocks.
+ */
+ for (k = 0; k < 7 && j > 0 && !test_bit (j - 1, bh->b_data); k++, j--);
+
+got_block:
+
+ ext2_debug ("using block group %d(%d)\n", i, gdp->bg_free_blocks_count);
+
+ tmp = j + i * EXT2_BLOCKS_PER_GROUP(sb) + es->s_first_data_block;
+
+ if (test_opt (sb, CHECK_STRICT) &&
+ (tmp == gdp->bg_block_bitmap ||
+ tmp == gdp->bg_inode_bitmap ||
+ in_range (tmp, gdp->bg_inode_table, sb->u.ext2_sb.s_itb_per_group)))
+ ext2_panic (sb, "ext2_new_block",
+ "Allocating block in system zone - "
+ "block = %u", tmp);
+
+ if (set_bit (j, bh->b_data)) {
+ ext2_warning (sb, "ext2_new_block",
+ "bit already set for block %d", j);
+ goto repeat;
+ }
+
+ ext2_debug ("found bit %d\n", j);
+
+ /*
+ * Do block preallocation now if required.
+ */
+#ifdef EXT2_PREALLOCATE
+ if (prealloc_block) {
+ *prealloc_count = 0;
+ *prealloc_block = tmp + 1;
+ for (k = 1;
+ k < 8 && (j + k) < EXT2_BLOCKS_PER_GROUP(sb); k++) {
+ if (set_bit (j + k, bh->b_data))
+ break;
+ (*prealloc_count)++;
+ }
+ gdp->bg_free_blocks_count -= *prealloc_count;
+ es->s_free_blocks_count -= *prealloc_count;
+ ext2_debug ("Preallocated a further %lu bits.\n",
+ *prealloc_count);
+ }
+#endif
+
+ j = tmp;
+
+ mark_buffer_dirty(bh, 1);
+ if (sb->s_flags & MS_SYNCHRONOUS) {
+ ll_rw_block (WRITE, 1, &bh);
+ wait_on_buffer (bh);
+ }
+
+ if (j >= es->s_blocks_count) {
+ ext2_error (sb, "ext2_new_block",
+ "block >= blocks count - "
+ "block_group = %d, block=%d", i, j);
+ unlock_super (sb);
+ return 0;
+ }
+ if (!(bh = getblk (sb->s_dev, j, sb->s_blocksize))) {
+ ext2_error (sb, "ext2_new_block", "cannot get block %d", j);
+ unlock_super (sb);
+ return 0;
+ }
+ memset(bh->b_data, 0, sb->s_blocksize);
+ bh->b_uptodate = 1;
+ mark_buffer_dirty(bh, 1);
+ brelse (bh);
+
+ ext2_debug ("allocating block %d. "
+ "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
+
+ gdp->bg_free_blocks_count--;
+ mark_buffer_dirty(bh2, 1);
+ es->s_free_blocks_count--;
+ mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
+ sb->s_dirt = 1;
+ unlock_super (sb);
+ return j;
+}
+
+unsigned long ext2_count_free_blocks (struct super_block * sb)
+{
+#ifdef EXT2FS_DEBUG
+ struct ext2_super_block * es;
+ unsigned long desc_count, bitmap_count, x;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ int i;
+
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+ desc_count = 0;
+ bitmap_count = 0;
+ gdp = NULL;
+ for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
+ gdp = get_group_desc (sb, i, NULL);
+ desc_count += gdp->bg_free_blocks_count;
+ bitmap_nr = load_block_bitmap (sb, i);
+ x = ext2_count_free (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
+ sb->s_blocksize);
+ printk ("group %d: stored = %d, counted = %lu\n",
+ i, gdp->bg_free_blocks_count, x);
+ bitmap_count += x;
+ }
+ printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n",
+ es->s_free_blocks_count, desc_count, bitmap_count);
+ unlock_super (sb);
+ return bitmap_count;
+#else
+ return sb->u.ext2_sb.s_es->s_free_blocks_count;
+#endif
+}
+
+static inline int block_in_use (unsigned long block,
+ struct super_block * sb,
+ unsigned char * map)
+{
+ return test_bit ((block - sb->u.ext2_sb.s_es->s_first_data_block) %
+ EXT2_BLOCKS_PER_GROUP(sb), map);
+}
+
+void ext2_check_blocks_bitmap (struct super_block * sb)
+{
+ struct buffer_head * bh;
+ struct ext2_super_block * es;
+ unsigned long desc_count, bitmap_count, x;
+ unsigned long desc_blocks;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ int i, j;
+
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+ desc_count = 0;
+ bitmap_count = 0;
+ gdp = NULL;
+ desc_blocks = (sb->u.ext2_sb.s_groups_count + EXT2_DESC_PER_BLOCK(sb) - 1) /
+ EXT2_DESC_PER_BLOCK(sb);
+ for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
+ gdp = get_group_desc (sb, i, NULL);
+ desc_count += gdp->bg_free_blocks_count;
+ bitmap_nr = load_block_bitmap (sb, i);
+ bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
+
+ if (!test_bit (0, bh->b_data))
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Superblock in group %d is marked free", i);
+
+ for (j = 0; j < desc_blocks; j++)
+ if (!test_bit (j + 1, bh->b_data))
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Descriptor block #%d in group "
+ "%d is marked free", j, i);
+
+ if (!block_in_use (gdp->bg_block_bitmap, sb, bh->b_data))
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Block bitmap for group %d is marked free",
+ i);
+
+ if (!block_in_use (gdp->bg_inode_bitmap, sb, bh->b_data))
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Inode bitmap for group %d is marked free",
+ i);
+
+ for (j = 0; j < sb->u.ext2_sb.s_itb_per_group; j++)
+ if (!block_in_use (gdp->bg_inode_table + j, sb, bh->b_data))
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Block #%d of the inode table in "
+ "group %d is marked free", j, i);
+
+ x = ext2_count_free (bh, sb->s_blocksize);
+ if (gdp->bg_free_blocks_count != x)
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Wrong free blocks count for group %d, "
+ "stored = %d, counted = %lu", i,
+ gdp->bg_free_blocks_count, x);
+ bitmap_count += x;
+ }
+ if (es->s_free_blocks_count != bitmap_count)
+ ext2_error (sb, "ext2_check_blocks_bitmap",
+ "Wrong free blocks count in super block, "
+ "stored = %lu, counted = %lu",
+ (unsigned long) es->s_free_blocks_count, bitmap_count);
+ unlock_super (sb);
+}
diff --git a/ext2fs/bitmap.c b/ext2fs/bitmap.c
new file mode 100644
index 00000000..8b9b5d23
--- /dev/null
+++ b/ext2fs/bitmap.c
@@ -0,0 +1,26 @@
+/*
+ * linux/fs/ext2/bitmap.c
+ *
+ * Copyright (C) 1992, 1993, 1994, 1995
+ * Remy Card (card@masi.ibp.fr)
+ * Laboratoire MASI - Institut Blaise Pascal
+ * Universite Pierre et Marie Curie (Paris VI)
+ */
+
+#include <linux/fs.h>
+#include <linux/ext2_fs.h>
+
+static int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
+
+unsigned long ext2_count_free (struct buffer_head * map, unsigned int numchars)
+{
+ unsigned int i;
+ unsigned long sum = 0;
+
+ if (!map)
+ return (0);
+ for (i = 0; i < numchars; i++)
+ sum += nibblemap[map->b_data[i] & 0xf] +
+ nibblemap[(map->b_data[i] >> 4) & 0xf];
+ return (sum);
+}
diff --git a/ext2fs/ext2_fs.h b/ext2fs/ext2_fs.h
new file mode 100644
index 00000000..1129d1cf
--- /dev/null
+++ b/ext2fs/ext2_fs.h
@@ -0,0 +1,505 @@
+/*
+ * linux/include/linux/ext2_fs.h
+ *
+ * Copyright (C) 1992, 1993, 1994, 1995
+ * Remy Card (card@masi.ibp.fr)
+ * Laboratoire MASI - Institut Blaise Pascal
+ * Universite Pierre et Marie Curie (Paris VI)
+ *
+ * from
+ *
+ * linux/include/linux/minix_fs.h
+ *
+ * Copyright (C) 1991, 1992 Linus Torvalds
+ */
+
+#ifndef _LINUX_EXT2_FS_H
+#define _LINUX_EXT2_FS_H
+
+#include <linux/types.h>
+
+/*
+ * The second extended filesystem constants/structures
+ */
+
+/*
+ * Define EXT2FS_DEBUG to produce debug messages
+ */
+#undef EXT2FS_DEBUG
+
+/*
+ * Define EXT2FS_DEBUG_CACHE to produce cache debug messages
+ */
+#undef EXT2FS_DEBUG_CACHE
+
+/*
+ * Define EXT2FS_CHECK_CACHE to add some checks to the name cache code
+ */
+#undef EXT2FS_CHECK_CACHE
+
+/*
+ * Define EXT2FS_PRE_02B_COMPAT to convert ext 2 fs prior to 0.2b
+ */
+#undef EXT2FS_PRE_02B_COMPAT
+
+/*
+ * Define EXT2_PREALLOCATE to preallocate data blocks for expanding files
+ */
+#define EXT2_PREALLOCATE
+
+/*
+ * The second extended file system version
+ */
+#define EXT2FS_DATE "95/03/19"
+#define EXT2FS_VERSION "0.5a"
+
+/*
+ * Debug code
+ */
+#ifdef EXT2FS_DEBUG
+# define ext2_debug(f, a...) { \
+ printk ("EXT2-fs DEBUG (%s, %d): %s:", \
+ __FILE__, __LINE__, __FUNCTION__); \
+ printk (f, ## a); \
+ }
+#else
+# define ext2_debug(f, a...) /**/
+#endif
+
+/*
+ * Special inodes numbers
+ */
+#define EXT2_BAD_INO 1 /* Bad blocks inode */
+#define EXT2_ROOT_INO 2 /* Root inode */
+#define EXT2_ACL_IDX_INO 3 /* ACL inode */
+#define EXT2_ACL_DATA_INO 4 /* ACL inode */
+#define EXT2_BOOT_LOADER_INO 5 /* Boot loader inode */
+#define EXT2_UNDEL_DIR_INO 6 /* Undelete directory inode */
+#define EXT2_FIRST_INO 11 /* First non reserved inode */
+
+/*
+ * The second extended file system magic number
+ */
+#define EXT2_PRE_02B_MAGIC 0xEF51
+#define EXT2_SUPER_MAGIC 0xEF53
+
+/*
+ * Maximal count of links to a file
+ */
+#define EXT2_LINK_MAX 32000
+
+/*
+ * Macro-instructions used to manage several block sizes
+ */
+#define EXT2_MIN_BLOCK_SIZE 1024
+#define EXT2_MAX_BLOCK_SIZE 4096
+#define EXT2_MIN_BLOCK_LOG_SIZE 10
+#ifdef __KERNEL__
+# define EXT2_BLOCK_SIZE(s) ((s)->s_blocksize)
+#else
+# define EXT2_BLOCK_SIZE(s) (EXT2_MIN_BLOCK_SIZE << (s)->s_log_block_size)
+#endif
+#define EXT2_ACLE_PER_BLOCK(s) (EXT2_BLOCK_SIZE(s) / sizeof (struct ext2_acl_entry))
+#define EXT2_ADDR_PER_BLOCK(s) (EXT2_BLOCK_SIZE(s) / sizeof (__u32))
+#ifdef __KERNEL__
+# define EXT2_BLOCK_SIZE_BITS(s) ((s)->u.ext2_sb.s_es->s_log_block_size + 10)
+#else
+# define EXT2_BLOCK_SIZE_BITS(s) ((s)->s_log_block_size + 10)
+#endif
+#define EXT2_INODES_PER_BLOCK(s) (EXT2_BLOCK_SIZE(s) / sizeof (struct ext2_inode))
+
+/*
+ * Macro-instructions used to manage fragments
+ */
+#define EXT2_MIN_FRAG_SIZE 1024
+#define EXT2_MAX_FRAG_SIZE 4096
+#define EXT2_MIN_FRAG_LOG_SIZE 10
+#ifdef __KERNEL__
+# define EXT2_FRAG_SIZE(s) ((s)->u.ext2_sb.s_frag_size)
+# define EXT2_FRAGS_PER_BLOCK(s) ((s)->u.ext2_sb.s_frags_per_block)
+#else
+# define EXT2_FRAG_SIZE(s) (EXT2_MIN_FRAG_SIZE << (s)->s_log_frag_size)
+# define EXT2_FRAGS_PER_BLOCK(s) (EXT2_BLOCK_SIZE(s) / EXT2_FRAG_SIZE(s))
+#endif
+
+/*
+ * ACL structures
+ */
+struct ext2_acl_header /* Header of Access Control Lists */
+{
+ __u32 aclh_size;
+ __u32 aclh_file_count;
+ __u32 aclh_acle_count;
+ __u32 aclh_first_acle;
+};
+
+struct ext2_acl_entry /* Access Control List Entry */
+{
+ __u32 acle_size;
+ __u16 acle_perms; /* Access permissions */
+ __u16 acle_type; /* Type of entry */
+ __u16 acle_tag; /* User or group identity */
+ __u16 acle_pad1;
+ __u32 acle_next; /* Pointer on next entry for the */
+ /* same inode or on next free entry */
+};
+
+/*
+ * Structure of a blocks group descriptor
+ */
+struct ext2_old_group_desc
+{
+ __u32 bg_block_bitmap; /* Blocks bitmap block */
+ __u32 bg_inode_bitmap; /* Inodes bitmap block */
+ __u32 bg_inode_table; /* Inodes table block */
+ __u16 bg_free_blocks_count; /* Free blocks count */
+ __u16 bg_free_inodes_count; /* Free inodes count */
+};
+
+struct ext2_group_desc
+{
+ __u32 bg_block_bitmap; /* Blocks bitmap block */
+ __u32 bg_inode_bitmap; /* Inodes bitmap block */
+ __u32 bg_inode_table; /* Inodes table block */
+ __u16 bg_free_blocks_count; /* Free blocks count */
+ __u16 bg_free_inodes_count; /* Free inodes count */
+ __u16 bg_used_dirs_count; /* Directories count */
+ __u16 bg_pad;
+ __u32 bg_reserved[3];
+};
+
+/*
+ * Macro-instructions used to manage group descriptors
+ */
+#ifdef __KERNEL__
+# define EXT2_BLOCKS_PER_GROUP(s) ((s)->u.ext2_sb.s_blocks_per_group)
+# define EXT2_DESC_PER_BLOCK(s) ((s)->u.ext2_sb.s_desc_per_block)
+# define EXT2_INODES_PER_GROUP(s) ((s)->u.ext2_sb.s_inodes_per_group)
+#else
+# define EXT2_BLOCKS_PER_GROUP(s) ((s)->s_blocks_per_group)
+# define EXT2_DESC_PER_BLOCK(s) (EXT2_BLOCK_SIZE(s) / sizeof (struct ext2_group_desc))
+# define EXT2_INODES_PER_GROUP(s) ((s)->s_inodes_per_group)
+#endif
+
+/*
+ * Constants relative to the data blocks
+ */
+#define EXT2_NDIR_BLOCKS 12
+#define EXT2_IND_BLOCK EXT2_NDIR_BLOCKS
+#define EXT2_DIND_BLOCK (EXT2_IND_BLOCK + 1)
+#define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK + 1)
+#define EXT2_N_BLOCKS (EXT2_TIND_BLOCK + 1)
+
+/*
+ * Inode flags
+ */
+#define EXT2_SECRM_FL 0x00000001 /* Secure deletion */
+#define EXT2_UNRM_FL 0x00000002 /* Undelete */
+#define EXT2_COMPR_FL 0x00000004 /* Compress file */
+#define EXT2_SYNC_FL 0x00000008 /* Synchronous updates */
+#define EXT2_IMMUTABLE_FL 0x00000010 /* Immutable file */
+#define EXT2_APPEND_FL 0x00000020 /* writes to file may only append */
+#define EXT2_NODUMP_FL 0x00000040 /* do not dump file */
+
+/*
+ * ioctl commands
+ */
+#define EXT2_IOC_GETFLAGS _IOR('f', 1, long)
+#define EXT2_IOC_SETFLAGS _IOW('f', 2, long)
+#define EXT2_IOC_GETVERSION _IOR('v', 1, long)
+#define EXT2_IOC_SETVERSION _IOW('v', 2, long)
+
+/*
+ * Structure of an inode on the disk
+ */
+struct ext2_inode {
+ __u16 i_mode; /* File mode */
+ __u16 i_uid; /* Owner Uid */
+ __u32 i_size; /* Size in bytes */
+ __u32 i_atime; /* Access time */
+ __u32 i_ctime; /* Creation time */
+ __u32 i_mtime; /* Modification time */
+ __u32 i_dtime; /* Deletion Time */
+ __u16 i_gid; /* Group Id */
+ __u16 i_links_count; /* Links count */
+ __u32 i_blocks; /* Blocks count */
+ __u32 i_flags; /* File flags */
+ union {
+ struct {
+ __u32 l_i_reserved1;
+ } linux1;
+ struct {
+ __u32 h_i_translator;
+ } hurd1;
+ struct {
+ __u32 m_i_reserved1;
+ } masix1;
+ } osd1; /* OS dependent 1 */
+ __u32 i_block[EXT2_N_BLOCKS];/* Pointers to blocks */
+ __u32 i_version; /* File version (for NFS) */
+ __u32 i_file_acl; /* File ACL */
+ __u32 i_dir_acl; /* Directory ACL */
+ __u32 i_faddr; /* Fragment address */
+ union {
+ struct {
+ __u8 l_i_frag; /* Fragment number */
+ __u8 l_i_fsize; /* Fragment size */
+ __u16 i_pad1;
+ __u32 l_i_reserved2[2];
+ } linux2;
+ struct {
+ __u8 h_i_frag; /* Fragment number */
+ __u8 h_i_fsize; /* Fragment size */
+ __u16 h_i_mode_high;
+ __u16 h_i_uid_high;
+ __u16 h_i_gid_high;
+ __u32 h_i_author;
+ } hurd2;
+ struct {
+ __u8 m_i_frag; /* Fragment number */
+ __u8 m_i_fsize; /* Fragment size */
+ __u16 m_pad1;
+ __u32 m_i_reserved2[2];
+ } masix2;
+ } osd2; /* OS dependent 2 */
+};
+
+#if defined(__KERNEL__) || defined(__linux__)
+#define i_reserved1 osd1.linux1.l_i_reserved1
+#define i_frag osd2.linux2.l_i_frag
+#define i_fsize osd2.linux2.l_i_fsize
+#define i_reserved2 osd2.linux2.l_i_reserved2
+#endif
+
+#ifdef __hurd__
+#define i_translator osd1.hurd1.h_i_translator
+#define i_frag osd2.hurd2.h_i_frag;
+#define i_fsize osd2.hurd2.h_i_fsize;
+#define i_uid_high osd2.hurd2.h_i_uid_high
+#define i_gid_high osd2.hurd2.h_i_gid_high
+#define i_author osd2.hurd2.h_i_author
+#endif
+
+#ifdef __masix__
+#define i_reserved1 osd1.masix1.m_i_reserved1
+#define i_frag osd2.masix2.m_i_frag
+#define i_fsize osd2.masix2.m_i_fsize
+#define i_reserved2 osd2.masix2.m_i_reserved2
+#endif
+
+/*
+ * File system states
+ */
+#define EXT2_VALID_FS 0x0001 /* Unmounted cleanly */
+#define EXT2_ERROR_FS 0x0002 /* Errors detected */
+
+/*
+ * Mount flags
+ */
+#define EXT2_MOUNT_CHECK_NORMAL 0x0001 /* Do some more checks */
+#define EXT2_MOUNT_CHECK_STRICT 0x0002 /* Do again more checks */
+#define EXT2_MOUNT_CHECK (EXT2_MOUNT_CHECK_NORMAL | \
+ EXT2_MOUNT_CHECK_STRICT)
+#define EXT2_MOUNT_GRPID 0x0004 /* Create files with directory's group */
+#define EXT2_MOUNT_DEBUG 0x0008 /* Some debugging messages */
+#define EXT2_MOUNT_ERRORS_CONT 0x0010 /* Continue on errors */
+#define EXT2_MOUNT_ERRORS_RO 0x0020 /* Remount fs ro on errors */
+#define EXT2_MOUNT_ERRORS_PANIC 0x0040 /* Panic on errors */
+#define EXT2_MOUNT_MINIX_DF 0x0080 /* Mimics the Minix statfs */
+
+#define clear_opt(o, opt) o &= ~EXT2_MOUNT_##opt
+#define set_opt(o, opt) o |= EXT2_MOUNT_##opt
+#define test_opt(sb, opt) ((sb)->u.ext2_sb.s_mount_opt & \
+ EXT2_MOUNT_##opt)
+/*
+ * Maximal mount counts between two filesystem checks
+ */
+#define EXT2_DFL_MAX_MNT_COUNT 20 /* Allow 20 mounts */
+#define EXT2_DFL_CHECKINTERVAL 0 /* Don't use interval check */
+
+/*
+ * Behaviour when detecting errors
+ */
+#define EXT2_ERRORS_CONTINUE 1 /* Continue execution */
+#define EXT2_ERRORS_RO 2 /* Remount fs read-only */
+#define EXT2_ERRORS_PANIC 3 /* Panic */
+#define EXT2_ERRORS_DEFAULT EXT2_ERRORS_CONTINUE
+
+/*
+ * Structure of the super block
+ */
+struct ext2_super_block {
+ __u32 s_inodes_count; /* Inodes count */
+ __u32 s_blocks_count; /* Blocks count */
+ __u32 s_r_blocks_count; /* Reserved blocks count */
+ __u32 s_free_blocks_count; /* Free blocks count */
+ __u32 s_free_inodes_count; /* Free inodes count */
+ __u32 s_first_data_block; /* First Data Block */
+ __u32 s_log_block_size; /* Block size */
+ __s32 s_log_frag_size; /* Fragment size */
+ __u32 s_blocks_per_group; /* # Blocks per group */
+ __u32 s_frags_per_group; /* # Fragments per group */
+ __u32 s_inodes_per_group; /* # Inodes per group */
+ __u32 s_mtime; /* Mount time */
+ __u32 s_wtime; /* Write time */
+ __u16 s_mnt_count; /* Mount count */
+ __s16 s_max_mnt_count; /* Maximal mount count */
+ __u16 s_magic; /* Magic signature */
+ __u16 s_state; /* File system state */
+ __u16 s_errors; /* Behaviour when detecting errors */
+ __u16 s_pad;
+ __u32 s_lastcheck; /* time of last check */
+ __u32 s_checkinterval; /* max. time between checks */
+ __u32 s_creator_os; /* OS */
+ __u32 s_rev_level; /* Revision level */
+ __u16 s_def_resuid; /* Default uid for reserved blocks */
+ __u16 s_def_resgid; /* Default gid for reserved blocks */
+ __u32 s_reserved[235]; /* Padding to the end of the block */
+};
+
+#define EXT2_OS_LINUX 0
+#define EXT2_OS_HURD 1
+#define EXT2_OS_MASIX 2
+
+#define EXT2_CURRENT_REV 0
+
+#define EXT2_DEF_RESUID 0
+#define EXT2_DEF_RESGID 0
+
+/*
+ * Structure of a directory entry
+ */
+#define EXT2_NAME_LEN 255
+
+struct ext2_dir_entry {
+ __u32 inode; /* Inode number */
+ __u16 rec_len; /* Directory entry length */
+ __u16 name_len; /* Name length */
+ char name[EXT2_NAME_LEN]; /* File name */
+};
+
+/*
+ * EXT2_DIR_PAD defines the directory entries boundaries
+ *
+ * NOTE: It must be a multiple of 4
+ */
+#define EXT2_DIR_PAD 4
+#define EXT2_DIR_ROUND (EXT2_DIR_PAD - 1)
+#define EXT2_DIR_REC_LEN(name_len) (((name_len) + 8 + EXT2_DIR_ROUND) & \
+ ~EXT2_DIR_ROUND)
+
+#ifdef __KERNEL__
+/*
+ * Function prototypes
+ */
+
+/*
+ * Ok, these declarations are also in <linux/kernel.h> but none of the
+ * ext2 source programs needs to include it so they are duplicated here.
+ */
+#if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 5)
+# define NORET_TYPE __volatile__
+# define ATTRIB_NORET /**/
+# define NORET_AND /**/
+#else
+# define NORET_TYPE /**/
+# define ATTRIB_NORET __attribute__((noreturn))
+# define NORET_AND noreturn,
+#endif
+
+/* acl.c */
+extern int ext2_permission (struct inode *, int);
+
+/* balloc.c */
+extern int ext2_new_block (struct super_block *, unsigned long,
+ __u32 *, __u32 *);
+extern void ext2_free_blocks (struct super_block *, unsigned long,
+ unsigned long);
+extern unsigned long ext2_count_free_blocks (struct super_block *);
+extern void ext2_check_blocks_bitmap (struct super_block *);
+
+/* bitmap.c */
+extern unsigned long ext2_count_free (struct buffer_head *, unsigned);
+
+/* dir.c */
+extern int ext2_check_dir_entry (char *, struct inode *,
+ struct ext2_dir_entry *, struct buffer_head *,
+ unsigned long);
+
+/* file.c */
+extern int ext2_read (struct inode *, struct file *, char *, int);
+extern int ext2_write (struct inode *, struct file *, char *, int);
+
+/* fsync.c */
+extern int ext2_sync_file (struct inode *, struct file *);
+
+/* ialloc.c */
+extern struct inode * ext2_new_inode (const struct inode *, int);
+extern void ext2_free_inode (struct inode *);
+extern unsigned long ext2_count_free_inodes (struct super_block *);
+extern void ext2_check_inodes_bitmap (struct super_block *);
+
+/* inode.c */
+extern int ext2_bmap (struct inode *, int);
+
+extern struct buffer_head * ext2_getblk (struct inode *, long, int, int *);
+extern struct buffer_head * ext2_bread (struct inode *, int, int, int *);
+
+extern int ext2_getcluster (struct inode * inode, long block);
+extern void ext2_read_inode (struct inode *);
+extern void ext2_write_inode (struct inode *);
+extern void ext2_put_inode (struct inode *);
+extern int ext2_sync_inode (struct inode *);
+extern void ext2_discard_prealloc (struct inode *);
+
+/* ioctl.c */
+extern int ext2_ioctl (struct inode *, struct file *, unsigned int,
+ unsigned long);
+
+/* namei.c */
+extern void ext2_release (struct inode *, struct file *);
+extern int ext2_lookup (struct inode *,const char *, int, struct inode **);
+extern int ext2_create (struct inode *,const char *, int, int,
+ struct inode **);
+extern int ext2_mkdir (struct inode *, const char *, int, int);
+extern int ext2_rmdir (struct inode *, const char *, int);
+extern int ext2_unlink (struct inode *, const char *, int);
+extern int ext2_symlink (struct inode *, const char *, int, const char *);
+extern int ext2_link (struct inode *, struct inode *, const char *, int);
+extern int ext2_mknod (struct inode *, const char *, int, int, int);
+extern int ext2_rename (struct inode *, const char *, int,
+ struct inode *, const char *, int);
+
+/* super.c */
+extern void ext2_error (struct super_block *, const char *, const char *, ...)
+ __attribute__ ((format (printf, 3, 4)));
+extern NORET_TYPE void ext2_panic (struct super_block *, const char *,
+ const char *, ...)
+ __attribute__ ((NORET_AND format (printf, 3, 4)));
+extern void ext2_warning (struct super_block *, const char *, const char *, ...)
+ __attribute__ ((format (printf, 3, 4)));
+extern void ext2_put_super (struct super_block *);
+extern void ext2_write_super (struct super_block *);
+extern int ext2_remount (struct super_block *, int *, char *);
+extern struct super_block * ext2_read_super (struct super_block *,void *,int);
+extern void ext2_statfs (struct super_block *, struct statfs *);
+
+/* truncate.c */
+extern void ext2_truncate (struct inode *);
+
+/*
+ * Inodes and files operations
+ */
+
+/* dir.c */
+extern struct inode_operations ext2_dir_inode_operations;
+
+/* file.c */
+extern struct inode_operations ext2_file_inode_operations;
+
+/* symlink.c */
+extern struct inode_operations ext2_symlink_inode_operations;
+
+#endif /* __KERNEL__ */
+
+#endif /* _LINUX_EXT2_FS_H */
diff --git a/ext2fs/ext2_fs_i.h b/ext2fs/ext2_fs_i.h
new file mode 100644
index 00000000..f3eca448
--- /dev/null
+++ b/ext2fs/ext2_fs_i.h
@@ -0,0 +1,40 @@
+/*
+ * linux/include/linux/ext2_fs_i.h
+ *
+ * Copyright (C) 1992, 1993, 1994, 1995
+ * Remy Card (card@masi.ibp.fr)
+ * Laboratoire MASI - Institut Blaise Pascal
+ * Universite Pierre et Marie Curie (Paris VI)
+ *
+ * from
+ *
+ * linux/include/linux/minix_fs_i.h
+ *
+ * Copyright (C) 1991, 1992 Linus Torvalds
+ */
+
+#ifndef _LINUX_EXT2_FS_I
+#define _LINUX_EXT2_FS_I
+
+/*
+ * second extended file system inode data in memory
+ */
+struct ext2_inode_info {
+ __u32 i_data[15];
+ __u32 i_flags;
+ __u32 i_faddr;
+ __u8 i_frag_no;
+ __u8 i_frag_size;
+ __u16 i_osync;
+ __u32 i_file_acl;
+ __u32 i_dir_acl;
+ __u32 i_dtime;
+ __u32 i_version;
+ __u32 i_block_group;
+ __u32 i_next_alloc_block;
+ __u32 i_next_alloc_goal;
+ __u32 i_prealloc_block;
+ __u32 i_prealloc_count;
+};
+
+#endif /* _LINUX_EXT2_FS_I */
diff --git a/ext2fs/ialloc.c b/ext2fs/ialloc.c
new file mode 100644
index 00000000..9102d02b
--- /dev/null
+++ b/ext2fs/ialloc.c
@@ -0,0 +1,555 @@
+/*
+ * linux/fs/ext2/ialloc.c
+ *
+ * Copyright (C) 1992, 1993, 1994, 1995
+ * Remy Card (card@masi.ibp.fr)
+ * Laboratoire MASI - Institut Blaise Pascal
+ * Universite Pierre et Marie Curie (Paris VI)
+ *
+ * BSD ufs-inspired inode and directory allocation by
+ * Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
+ */
+
+/*
+ * ialloc.c contains the inodes allocation and deallocation routines
+ */
+
+/*
+ * The free inodes are managed by bitmaps. A file system contains several
+ * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
+ * block for inodes, N blocks for the inode table and data blocks.
+ *
+ * The file system contains group descriptors which are located after the
+ * super block. Each descriptor contains the number of the bitmap block and
+ * the free blocks count in the block. The descriptors are loaded in memory
+ * when a file system is mounted (see ext2_read_super).
+ */
+
+#include <linux/fs.h>
+#include <linux/ext2_fs.h>
+#include <linux/sched.h>
+#include <linux/stat.h>
+#include <linux/string.h>
+#include <linux/locks.h>
+
+#include <asm/bitops.h>
+
+static struct ext2_group_desc * get_group_desc (struct super_block * sb,
+ unsigned int block_group,
+ struct buffer_head ** bh)
+{
+ unsigned long group_desc;
+ unsigned long desc;
+ struct ext2_group_desc * gdp;
+
+ if (block_group >= sb->u.ext2_sb.s_groups_count)
+ ext2_panic (sb, "get_group_desc",
+ "block_group >= groups_count - "
+ "block_group = %d, groups_count = %lu",
+ block_group, sb->u.ext2_sb.s_groups_count);
+
+ group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
+ desc = block_group % EXT2_DESC_PER_BLOCK(sb);
+ if (!sb->u.ext2_sb.s_group_desc[group_desc])
+ ext2_panic (sb, "get_group_desc",
+ "Group descriptor not loaded - "
+ "block_group = %d, group_desc = %lu, desc = %lu",
+ block_group, group_desc, desc);
+ gdp = (struct ext2_group_desc *)
+ sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
+ if (bh)
+ *bh = sb->u.ext2_sb.s_group_desc[group_desc];
+ return gdp + desc;
+}
+
+static void read_inode_bitmap (struct super_block * sb,
+ unsigned long block_group,
+ unsigned int bitmap_nr)
+{
+ struct ext2_group_desc * gdp;
+ struct buffer_head * bh;
+
+ gdp = get_group_desc (sb, block_group, NULL);
+ bh = bread (sb->s_dev, gdp->bg_inode_bitmap, sb->s_blocksize);
+ if (!bh)
+ ext2_panic (sb, "read_inode_bitmap",
+ "Cannot read inode bitmap - "
+ "block_group = %lu, inode_bitmap = %lu",
+ block_group, (unsigned long) gdp->bg_inode_bitmap);
+ sb->u.ext2_sb.s_inode_bitmap_number[bitmap_nr] = block_group;
+ sb->u.ext2_sb.s_inode_bitmap[bitmap_nr] = bh;
+}
+
+/*
+ * load_inode_bitmap loads the inode bitmap for a blocks group
+ *
+ * It maintains a cache for the last bitmaps loaded. This cache is managed
+ * with a LRU algorithm.
+ *
+ * Notes:
+ * 1/ There is one cache per mounted file system.
+ * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
+ * this function reads the bitmap without maintaining a LRU cache.
+ */
+static int load_inode_bitmap (struct super_block * sb,
+ unsigned int block_group)
+{
+ int i, j;
+ unsigned long inode_bitmap_number;
+ struct buffer_head * inode_bitmap;
+
+ if (block_group >= sb->u.ext2_sb.s_groups_count)
+ ext2_panic (sb, "load_inode_bitmap",
+ "block_group >= groups_count - "
+ "block_group = %d, groups_count = %lu",
+ block_group, sb->u.ext2_sb.s_groups_count);
+ if (sb->u.ext2_sb.s_loaded_inode_bitmaps > 0 &&
+ sb->u.ext2_sb.s_inode_bitmap_number[0] == block_group)
+ return 0;
+ if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
+ if (sb->u.ext2_sb.s_inode_bitmap[block_group]) {
+ if (sb->u.ext2_sb.s_inode_bitmap_number[block_group] != block_group)
+ ext2_panic (sb, "load_inode_bitmap",
+ "block_group != inode_bitmap_number");
+ else
+ return block_group;
+ } else {
+ read_inode_bitmap (sb, block_group, block_group);
+ return block_group;
+ }
+ }
+
+ for (i = 0; i < sb->u.ext2_sb.s_loaded_inode_bitmaps &&
+ sb->u.ext2_sb.s_inode_bitmap_number[i] != block_group;
+ i++)
+ ;
+ if (i < sb->u.ext2_sb.s_loaded_inode_bitmaps &&
+ sb->u.ext2_sb.s_inode_bitmap_number[i] == block_group) {
+ inode_bitmap_number = sb->u.ext2_sb.s_inode_bitmap_number[i];
+ inode_bitmap = sb->u.ext2_sb.s_inode_bitmap[i];
+ for (j = i; j > 0; j--) {
+ sb->u.ext2_sb.s_inode_bitmap_number[j] =
+ sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
+ sb->u.ext2_sb.s_inode_bitmap[j] =
+ sb->u.ext2_sb.s_inode_bitmap[j - 1];
+ }
+ sb->u.ext2_sb.s_inode_bitmap_number[0] = inode_bitmap_number;
+ sb->u.ext2_sb.s_inode_bitmap[0] = inode_bitmap;
+ } else {
+ if (sb->u.ext2_sb.s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
+ sb->u.ext2_sb.s_loaded_inode_bitmaps++;
+ else
+ brelse (sb->u.ext2_sb.s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
+ for (j = sb->u.ext2_sb.s_loaded_inode_bitmaps - 1; j > 0; j--) {
+ sb->u.ext2_sb.s_inode_bitmap_number[j] =
+ sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
+ sb->u.ext2_sb.s_inode_bitmap[j] =
+ sb->u.ext2_sb.s_inode_bitmap[j - 1];
+ }
+ read_inode_bitmap (sb, block_group, 0);
+ }
+ return 0;
+}
+
+/*
+ * This function sets the deletion time for the inode
+ *
+ * This may be used one day by an 'undelete' program
+ */
+static void set_inode_dtime (struct inode * inode,
+ struct ext2_group_desc * gdp)
+{
+ unsigned long inode_block;
+ struct buffer_head * bh;
+ struct ext2_inode * raw_inode;
+
+ inode_block = gdp->bg_inode_table + (((inode->i_ino - 1) %
+ EXT2_INODES_PER_GROUP(inode->i_sb)) /
+ EXT2_INODES_PER_BLOCK(inode->i_sb));
+ bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
+ if (!bh)
+ ext2_panic (inode->i_sb, "set_inode_dtime",
+ "Cannot load inode table block - "
+ "inode=%lu, inode_block=%lu",
+ inode->i_ino, inode_block);
+ raw_inode = ((struct ext2_inode *) bh->b_data) +
+ (((inode->i_ino - 1) %
+ EXT2_INODES_PER_GROUP(inode->i_sb)) %
+ EXT2_INODES_PER_BLOCK(inode->i_sb));
+ raw_inode->i_links_count = 0;
+ raw_inode->i_dtime = CURRENT_TIME;
+ mark_buffer_dirty(bh, 1);
+ if (IS_SYNC(inode)) {
+ ll_rw_block (WRITE, 1, &bh);
+ wait_on_buffer (bh);
+ }
+ brelse (bh);
+}
+
+void ext2_free_inode (struct inode * inode)
+{
+ struct super_block * sb;
+ struct buffer_head * bh;
+ struct buffer_head * bh2;
+ unsigned long block_group;
+ unsigned long bit;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ struct ext2_super_block * es;
+
+ if (!inode)
+ return;
+ if (!inode->i_dev) {
+ printk ("ext2_free_inode: inode has no device\n");
+ return;
+ }
+ if (inode->i_count > 1) {
+ printk ("ext2_free_inode: inode has count=%d\n",
+ inode->i_count);
+ return;
+ }
+ if (inode->i_nlink) {
+ printk ("ext2_free_inode: inode has nlink=%d\n",
+ inode->i_nlink);
+ return;
+ }
+ if (!inode->i_sb) {
+ printk("ext2_free_inode: inode on nonexistent device\n");
+ return;
+ }
+
+ ext2_debug ("freeing inode %lu\n", inode->i_ino);
+
+ sb = inode->i_sb;
+ lock_super (sb);
+ if (inode->i_ino < EXT2_FIRST_INO ||
+ inode->i_ino > sb->u.ext2_sb.s_es->s_inodes_count) {
+ ext2_error (sb, "free_inode",
+ "reserved inode or nonexistent inode");
+ unlock_super (sb);
+ return;
+ }
+ es = sb->u.ext2_sb.s_es;
+ block_group = (inode->i_ino - 1) / EXT2_INODES_PER_GROUP(sb);
+ bit = (inode->i_ino - 1) % EXT2_INODES_PER_GROUP(sb);
+ bitmap_nr = load_inode_bitmap (sb, block_group);
+ bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
+ if (!clear_bit (bit, bh->b_data))
+ ext2_warning (sb, "ext2_free_inode",
+ "bit already cleared for inode %lu", inode->i_ino);
+ else {
+ gdp = get_group_desc (sb, block_group, &bh2);
+ gdp->bg_free_inodes_count++;
+ if (S_ISDIR(inode->i_mode))
+ gdp->bg_used_dirs_count--;
+ mark_buffer_dirty(bh2, 1);
+ es->s_free_inodes_count++;
+ mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
+ set_inode_dtime (inode, gdp);
+ }
+ mark_buffer_dirty(bh, 1);
+ if (sb->s_flags & MS_SYNCHRONOUS) {
+ ll_rw_block (WRITE, 1, &bh);
+ wait_on_buffer (bh);
+ }
+
+ sb->s_dirt = 1;
+ clear_inode (inode);
+ unlock_super (sb);
+}
+
+/*
+ * This function increments the inode version number
+ *
+ * This may be used one day by the NFS server
+ */
+static void inc_inode_version (struct inode * inode,
+ struct ext2_group_desc *gdp,
+ int mode)
+{
+ unsigned long inode_block;
+ struct buffer_head * bh;
+ struct ext2_inode * raw_inode;
+
+ inode_block = gdp->bg_inode_table + (((inode->i_ino - 1) %
+ EXT2_INODES_PER_GROUP(inode->i_sb)) /
+ EXT2_INODES_PER_BLOCK(inode->i_sb));
+ bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
+ if (!bh) {
+ ext2_error (inode->i_sb, "inc_inode_version",
+ "Cannot load inode table block - "
+ "inode=%lu, inode_block=%lu\n",
+ inode->i_ino, inode_block);
+ inode->u.ext2_i.i_version = 1;
+ return;
+ }
+ raw_inode = ((struct ext2_inode *) bh->b_data) +
+ (((inode->i_ino - 1) %
+ EXT2_INODES_PER_GROUP(inode->i_sb)) %
+ EXT2_INODES_PER_BLOCK(inode->i_sb));
+ raw_inode->i_version++;
+ inode->u.ext2_i.i_version = raw_inode->i_version;
+ mark_buffer_dirty(bh, 1);
+ brelse (bh);
+}
+
+/*
+ * There are two policies for allocating an inode. If the new inode is
+ * a directory, then a forward search is made for a block group with both
+ * free space and a low directory-to-inode ratio; if that fails, then of
+ * the groups with above-average free space, that group with the fewest
+ * directories already is chosen.
+ *
+ * For other inodes, search forward from the parent directory\'s block
+ * group to find a free inode.
+ */
+struct inode * ext2_new_inode (const struct inode * dir, int mode)
+{
+ struct super_block * sb;
+ struct buffer_head * bh;
+ struct buffer_head * bh2;
+ int i, j, avefreei;
+ struct inode * inode;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ struct ext2_group_desc * tmp;
+ struct ext2_super_block * es;
+
+ if (!dir || !(inode = get_empty_inode ()))
+ return NULL;
+ sb = dir->i_sb;
+ inode->i_sb = sb;
+ inode->i_flags = sb->s_flags;
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+repeat:
+ gdp = NULL; i=0;
+
+ if (S_ISDIR(mode)) {
+ avefreei = es->s_free_inodes_count /
+ sb->u.ext2_sb.s_groups_count;
+/* I am not yet convinced that this next bit is necessary.
+ i = dir->u.ext2_i.i_block_group;
+ for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
+ tmp = get_group_desc (sb, i, &bh2);
+ if ((tmp->bg_used_dirs_count << 8) <
+ tmp->bg_free_inodes_count) {
+ gdp = tmp;
+ break;
+ }
+ else
+ i = ++i % sb->u.ext2_sb.s_groups_count;
+ }
+*/
+ if (!gdp) {
+ for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
+ tmp = get_group_desc (sb, j, &bh2);
+ if (tmp->bg_free_inodes_count &&
+ tmp->bg_free_inodes_count >= avefreei) {
+ if (!gdp ||
+ (tmp->bg_free_blocks_count >
+ gdp->bg_free_blocks_count)) {
+ i = j;
+ gdp = tmp;
+ }
+ }
+ }
+ }
+ }
+ else
+ {
+ /*
+ * Try to place the inode in its parent directory
+ */
+ i = dir->u.ext2_i.i_block_group;
+ tmp = get_group_desc (sb, i, &bh2);
+ if (tmp->bg_free_inodes_count)
+ gdp = tmp;
+ else
+ {
+ /*
+ * Use a quadratic hash to find a group with a
+ * free inode
+ */
+ for (j = 1; j < sb->u.ext2_sb.s_groups_count; j <<= 1) {
+ i += j;
+ if (i >= sb->u.ext2_sb.s_groups_count)
+ i -= sb->u.ext2_sb.s_groups_count;
+ tmp = get_group_desc (sb, i, &bh2);
+ if (tmp->bg_free_inodes_count) {
+ gdp = tmp;
+ break;
+ }
+ }
+ }
+ if (!gdp) {
+ /*
+ * That failed: try linear search for a free inode
+ */
+ i = dir->u.ext2_i.i_block_group + 1;
+ for (j = 2; j < sb->u.ext2_sb.s_groups_count; j++) {
+ if (++i >= sb->u.ext2_sb.s_groups_count)
+ i = 0;
+ tmp = get_group_desc (sb, i, &bh2);
+ if (tmp->bg_free_inodes_count) {
+ gdp = tmp;
+ break;
+ }
+ }
+ }
+ }
+
+ if (!gdp) {
+ unlock_super (sb);
+ iput(inode);
+ return NULL;
+ }
+ bitmap_nr = load_inode_bitmap (sb, i);
+ bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
+ if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
+ EXT2_INODES_PER_GROUP(sb))) <
+ EXT2_INODES_PER_GROUP(sb)) {
+ if (set_bit (j, bh->b_data)) {
+ ext2_warning (sb, "ext2_new_inode",
+ "bit already set for inode %d", j);
+ goto repeat;
+ }
+ mark_buffer_dirty(bh, 1);
+ if (sb->s_flags & MS_SYNCHRONOUS) {
+ ll_rw_block (WRITE, 1, &bh);
+ wait_on_buffer (bh);
+ }
+ } else {
+ if (gdp->bg_free_inodes_count != 0) {
+ ext2_error (sb, "ext2_new_inode",
+ "Free inodes count corrupted in group %d",
+ i);
+ unlock_super (sb);
+ iput (inode);
+ return NULL;
+ }
+ goto repeat;
+ }
+ j += i * EXT2_INODES_PER_GROUP(sb) + 1;
+ if (j < EXT2_FIRST_INO || j > es->s_inodes_count) {
+ ext2_error (sb, "ext2_new_inode",
+ "reserved inode or inode > inodes count - "
+ "block_group = %d,inode=%d", i, j);
+ unlock_super (sb);
+ iput (inode);
+ return NULL;
+ }
+ gdp->bg_free_inodes_count--;
+ if (S_ISDIR(mode))
+ gdp->bg_used_dirs_count++;
+ mark_buffer_dirty(bh2, 1);
+ es->s_free_inodes_count--;
+ mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
+ sb->s_dirt = 1;
+ inode->i_mode = mode;
+ inode->i_sb = sb;
+ inode->i_count = 1;
+ inode->i_nlink = 1;
+ inode->i_dev = sb->s_dev;
+ inode->i_uid = current->fsuid;
+ if (test_opt (sb, GRPID))
+ inode->i_gid = dir->i_gid;
+ else if (dir->i_mode & S_ISGID) {
+ inode->i_gid = dir->i_gid;
+ if (S_ISDIR(mode))
+ mode |= S_ISGID;
+ } else
+ inode->i_gid = current->fsgid;
+ inode->i_dirt = 1;
+ inode->i_ino = j;
+ inode->i_blksize = sb->s_blocksize;
+ inode->i_blocks = 0;
+ inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
+ inode->u.ext2_i.i_flags = dir->u.ext2_i.i_flags;
+ if (S_ISLNK(mode))
+ inode->u.ext2_i.i_flags &= ~(EXT2_IMMUTABLE_FL | EXT2_APPEND_FL);
+ inode->u.ext2_i.i_faddr = 0;
+ inode->u.ext2_i.i_frag_no = 0;
+ inode->u.ext2_i.i_frag_size = 0;
+ inode->u.ext2_i.i_file_acl = 0;
+ inode->u.ext2_i.i_dir_acl = 0;
+ inode->u.ext2_i.i_dtime = 0;
+ inode->u.ext2_i.i_block_group = i;
+ inode->i_op = NULL;
+ if (inode->u.ext2_i.i_flags & EXT2_SYNC_FL)
+ inode->i_flags |= MS_SYNCHRONOUS;
+ insert_inode_hash(inode);
+ inc_inode_version (inode, gdp, mode);
+
+ ext2_debug ("allocating inode %lu\n", inode->i_ino);
+
+ unlock_super (sb);
+ return inode;
+}
+
+unsigned long ext2_count_free_inodes (struct super_block * sb)
+{
+#ifdef EXT2FS_DEBUG
+ struct ext2_super_block * es;
+ unsigned long desc_count, bitmap_count, x;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ int i;
+
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+ desc_count = 0;
+ bitmap_count = 0;
+ gdp = NULL;
+ for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
+ gdp = get_group_desc (sb, i, NULL);
+ desc_count += gdp->bg_free_inodes_count;
+ bitmap_nr = load_inode_bitmap (sb, i);
+ x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
+ EXT2_INODES_PER_GROUP(sb) / 8);
+ printk ("group %d: stored = %d, counted = %lu\n",
+ i, gdp->bg_free_inodes_count, x);
+ bitmap_count += x;
+ }
+ printk("ext2_count_free_inodes: stored = %lu, computed = %lu, %lu\n",
+ es->s_free_inodes_count, desc_count, bitmap_count);
+ unlock_super (sb);
+ return desc_count;
+#else
+ return sb->u.ext2_sb.s_es->s_free_inodes_count;
+#endif
+}
+
+void ext2_check_inodes_bitmap (struct super_block * sb)
+{
+ struct ext2_super_block * es;
+ unsigned long desc_count, bitmap_count, x;
+ int bitmap_nr;
+ struct ext2_group_desc * gdp;
+ int i;
+
+ lock_super (sb);
+ es = sb->u.ext2_sb.s_es;
+ desc_count = 0;
+ bitmap_count = 0;
+ gdp = NULL;
+ for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
+ gdp = get_group_desc (sb, i, NULL);
+ desc_count += gdp->bg_free_inodes_count;
+ bitmap_nr = load_inode_bitmap (sb, i);
+ x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
+ EXT2_INODES_PER_GROUP(sb) / 8);
+ if (gdp->bg_free_inodes_count != x)
+ ext2_error (sb, "ext2_check_inodes_bitmap",
+ "Wrong free inodes count in group %d, "
+ "stored = %d, counted = %lu", i,
+ gdp->bg_free_inodes_count, x);
+ bitmap_count += x;
+ }
+ if (es->s_free_inodes_count != bitmap_count)
+ ext2_error (sb, "ext2_check_inodes_bitmap",
+ "Wrong free inodes count in super block, "
+ "stored = %lu, counted = %lu",
+ (unsigned long) es->s_free_inodes_count, bitmap_count);
+ unlock_super (sb);
+}
diff --git a/ext2fs/truncate.c b/ext2fs/truncate.c
new file mode 100644
index 00000000..94a64f3e
--- /dev/null
+++ b/ext2fs/truncate.c
@@ -0,0 +1,370 @@
+/*
+ * linux/fs/ext2/truncate.c
+ *
+ * Copyright (C) 1992, 1993, 1994, 1995
+ * Remy Card (card@masi.ibp.fr)
+ * Laboratoire MASI - Institut Blaise Pascal
+ * Universite Pierre et Marie Curie (Paris VI)
+ *
+ * from
+ *
+ * linux/fs/minix/truncate.c
+ *
+ * Copyright (C) 1991, 1992 Linus Torvalds
+ */
+
+/*
+ * Real random numbers for secure rm added 94/02/18
+ * Idea from Pierre del Perugia <delperug@gla.ecoledoc.ibp.fr>
+ */
+
+#include <linux/errno.h>
+#include <linux/fs.h>
+#include <linux/ext2_fs.h>
+#include <linux/fcntl.h>
+#include <linux/sched.h>
+#include <linux/stat.h>
+#include <linux/locks.h>
+#include <linux/string.h>
+
+static int ext2_secrm_seed = 152; /* Random generator base */
+
+#define RANDOM_INT (ext2_secrm_seed = ext2_secrm_seed * 69069l +1)
+
+/*
+ * Truncate has the most races in the whole filesystem: coding it is
+ * a pain in the a**. Especially as I don't do any locking...
+ *
+ * The code may look a bit weird, but that's just because I've tried to
+ * handle things like file-size changes in a somewhat graceful manner.
+ * Anyway, truncating a file at the same time somebody else writes to it
+ * is likely to result in pretty weird behaviour...
+ *
+ * The new code handles normal truncates (size = 0) as well as the more
+ * general case (size = XXX). I hope.
+ */
+
+static int trunc_direct (struct inode * inode)
+{
+ u32 * p;
+ int i, tmp;
+ struct buffer_head * bh;
+ unsigned long block_to_free = 0;
+ unsigned long free_count = 0;
+ int retry = 0;
+ int blocks = inode->i_sb->s_blocksize / 512;
+#define DIRECT_BLOCK ((inode->i_size + inode->i_sb->s_blocksize - 1) / \
+ inode->i_sb->s_blocksize)
+ int direct_block = DIRECT_BLOCK;
+
+repeat:
+ for (i = direct_block ; i < EXT2_NDIR_BLOCKS ; i++) {
+ p = inode->u.ext2_i.i_data + i;
+ tmp = *p;
+ if (!tmp)
+ continue;
+ if (inode->u.ext2_i.i_flags & EXT2_SECRM_FL)
+ bh = getblk (inode->i_dev, tmp,
+ inode->i_sb->s_blocksize);
+ else
+ bh = get_hash_table (inode->i_dev, tmp,
+ inode->i_sb->s_blocksize);
+ if (i < direct_block) {
+ brelse (bh);
+ goto repeat;
+ }
+ if ((bh && bh->b_count != 1) || tmp != *p) {
+ retry = 1;
+ brelse (bh);
+ continue;
+ }
+ *p = 0;
+ inode->i_blocks -= blocks;
+ inode->i_dirt = 1;
+ if (inode->u.ext2_i.i_flags & EXT2_SECRM_FL) {
+ memset(bh->b_data, RANDOM_INT, inode->i_sb->s_blocksize);
+ mark_buffer_dirty(bh, 1);
+ }
+ brelse (bh);
+ if (free_count == 0) {
+ block_to_free = tmp;
+ free_count++;
+ } else if (free_count > 0 && block_to_free == tmp - free_count)
+ free_count++;
+ else {
+ ext2_free_blocks (inode->i_sb, block_to_free, free_count);
+ block_to_free = tmp;
+ free_count = 1;
+ }
+/* ext2_free_blocks (inode->i_sb, tmp, 1); */
+ }
+ if (free_count > 0)
+ ext2_free_blocks (inode->i_sb, block_to_free, free_count);
+ return retry;
+}
+
+static int trunc_indirect (struct inode * inode, int offset, u32 * p)
+{
+ int i, tmp;
+ struct buffer_head * bh;
+ struct buffer_head * ind_bh;
+ u32 * ind;
+ unsigned long block_to_free = 0;
+ unsigned long free_count = 0;
+ int retry = 0;
+ int addr_per_block = EXT2_ADDR_PER_BLOCK(inode->i_sb);
+ int blocks = inode->i_sb->s_blocksize / 512;
+#define INDIRECT_BLOCK ((int)DIRECT_BLOCK - offset)
+ int indirect_block = INDIRECT_BLOCK;
+
+ tmp = *p;
+ if (!tmp)
+ return 0;
+ ind_bh = bread (inode->i_dev, tmp, inode->i_sb->s_blocksize);
+ if (tmp != *p) {
+ brelse (ind_bh);
+ return 1;
+ }
+ if (!ind_bh) {
+ *p = 0;
+ return 0;
+ }
+repeat:
+ for (i = indirect_block ; i < addr_per_block ; i++) {
+ if (i < 0)
+ i = 0;
+ if (i < indirect_block)
+ goto repeat;
+ ind = i + (u32 *) ind_bh->b_data;
+ tmp = *ind;
+ if (!tmp)
+ continue;
+ if (inode->u.ext2_i.i_flags & EXT2_SECRM_FL)
+ bh = getblk (inode->i_dev, tmp,
+ inode->i_sb->s_blocksize);
+ else
+ bh = get_hash_table (inode->i_dev, tmp,
+ inode->i_sb->s_blocksize);
+ if (i < indirect_block) {
+ brelse (bh);
+ goto repeat;
+ }
+ if ((bh && bh->b_count != 1) || tmp != *ind) {
+ retry = 1;
+ brelse (bh);
+ continue;
+ }
+ *ind = 0;
+ mark_buffer_dirty(ind_bh, 1);
+ if (inode->u.ext2_i.i_flags & EXT2_SECRM_FL) {
+ memset(bh->b_data, RANDOM_INT, inode->i_sb->s_blocksize);
+ mark_buffer_dirty(bh, 1);
+ }
+ brelse (bh);
+ if (free_count == 0) {
+ block_to_free = tmp;
+ free_count++;
+ } else if (free_count > 0 && block_to_free == tmp - free_count)
+ free_count++;
+ else {
+ ext2_free_blocks (inode->i_sb, block_to_free, free_count);
+ block_to_free = tmp;
+ free_count = 1;
+ }
+/* ext2_free_blocks (inode->i_sb, tmp, 1); */
+ inode->i_blocks -= blocks;
+ inode->i_dirt = 1;
+ }
+ if (free_count > 0)
+ ext2_free_blocks (inode->i_sb, block_to_free, free_count);
+ ind = (u32 *) ind_bh->b_data;
+ for (i = 0; i < addr_per_block; i++)
+ if (*(ind++))
+ break;
+ if (i >= addr_per_block)
+ if (ind_bh->b_count != 1)
+ retry = 1;
+ else {
+ tmp = *p;
+ *p = 0;
+ inode->i_blocks -= blocks;
+ inode->i_dirt = 1;
+ ext2_free_blocks (inode->i_sb, tmp, 1);
+ }
+ if (IS_SYNC(inode) && ind_bh->b_dirt) {
+ ll_rw_block (WRITE, 1, &ind_bh);
+ wait_on_buffer (ind_bh);
+ }
+ brelse (ind_bh);
+ return retry;
+}
+
+static int trunc_dindirect (struct inode * inode, int offset,
+ u32 * p)
+{
+ int i, tmp;
+ struct buffer_head * dind_bh;
+ u32 * dind;
+ int retry = 0;
+ int addr_per_block = EXT2_ADDR_PER_BLOCK(inode->i_sb);
+ int blocks = inode->i_sb->s_blocksize / 512;
+#define DINDIRECT_BLOCK (((int)DIRECT_BLOCK - offset) / addr_per_block)
+ int dindirect_block = DINDIRECT_BLOCK;
+
+ tmp = *p;
+ if (!tmp)
+ return 0;
+ dind_bh = bread (inode->i_dev, tmp, inode->i_sb->s_blocksize);
+ if (tmp != *p) {
+ brelse (dind_bh);
+ return 1;
+ }
+ if (!dind_bh) {
+ *p = 0;
+ return 0;
+ }
+repeat:
+ for (i = dindirect_block ; i < addr_per_block ; i++) {
+ if (i < 0)
+ i = 0;
+ if (i < dindirect_block)
+ goto repeat;
+ dind = i + (u32 *) dind_bh->b_data;
+ tmp = *dind;
+ if (!tmp)
+ continue;
+ retry |= trunc_indirect (inode, offset + (i * addr_per_block),
+ dind);
+ mark_buffer_dirty(dind_bh, 1);
+ }
+ dind = (u32 *) dind_bh->b_data;
+ for (i = 0; i < addr_per_block; i++)
+ if (*(dind++))
+ break;
+ if (i >= addr_per_block)
+ if (dind_bh->b_count != 1)
+ retry = 1;
+ else {
+ tmp = *p;
+ *p = 0;
+ inode->i_blocks -= blocks;
+ inode->i_dirt = 1;
+ ext2_free_blocks (inode->i_sb, tmp, 1);
+ }
+ if (IS_SYNC(inode) && dind_bh->b_dirt) {
+ ll_rw_block (WRITE, 1, &dind_bh);
+ wait_on_buffer (dind_bh);
+ }
+ brelse (dind_bh);
+ return retry;
+}
+
+static int trunc_tindirect (struct inode * inode)
+{
+ int i, tmp;
+ struct buffer_head * tind_bh;
+ u32 * tind, * p;
+ int retry = 0;
+ int addr_per_block = EXT2_ADDR_PER_BLOCK(inode->i_sb);
+ int blocks = inode->i_sb->s_blocksize / 512;
+#define TINDIRECT_BLOCK (((int)DIRECT_BLOCK - (addr_per_block * addr_per_block + \
+ addr_per_block + EXT2_NDIR_BLOCKS)) / \
+ (addr_per_block * addr_per_block))
+ int tindirect_block = TINDIRECT_BLOCK;
+
+ p = inode->u.ext2_i.i_data + EXT2_TIND_BLOCK;
+ if (!(tmp = *p))
+ return 0;
+ tind_bh = bread (inode->i_dev, tmp, inode->i_sb->s_blocksize);
+ if (tmp != *p) {
+ brelse (tind_bh);
+ return 1;
+ }
+ if (!tind_bh) {
+ *p = 0;
+ return 0;
+ }
+repeat:
+ for (i = tindirect_block ; i < addr_per_block ; i++) {
+ if (i < 0)
+ i = 0;
+ if (i < tindirect_block)
+ goto repeat;
+ tind = i + (u32 *) tind_bh->b_data;
+ retry |= trunc_dindirect(inode, EXT2_NDIR_BLOCKS +
+ addr_per_block + (i + 1) * addr_per_block * addr_per_block,
+ tind);
+ mark_buffer_dirty(tind_bh, 1);
+ }
+ tind = (u32 *) tind_bh->b_data;
+ for (i = 0; i < addr_per_block; i++)
+ if (*(tind++))
+ break;
+ if (i >= addr_per_block)
+ if (tind_bh->b_count != 1)
+ retry = 1;
+ else {
+ tmp = *p;
+ *p = 0;
+ inode->i_blocks -= blocks;
+ inode->i_dirt = 1;
+ ext2_free_blocks (inode->i_sb, tmp, 1);
+ }
+ if (IS_SYNC(inode) && tind_bh->b_dirt) {
+ ll_rw_block (WRITE, 1, &tind_bh);
+ wait_on_buffer (tind_bh);
+ }
+ brelse (tind_bh);
+ return retry;
+}
+
+void ext2_truncate (struct inode * inode)
+{
+ int retry;
+ struct buffer_head * bh;
+ int err;
+ int offset;
+
+ if (!(S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
+ S_ISLNK(inode->i_mode)))
+ return;
+ if (IS_APPEND(inode) || IS_IMMUTABLE(inode))
+ return;
+ ext2_discard_prealloc(inode);
+ while (1) {
+ down(&inode->i_sem);
+ retry = trunc_direct(inode);
+ retry |= trunc_indirect (inode, EXT2_IND_BLOCK,
+ (u32 *) &inode->u.ext2_i.i_data[EXT2_IND_BLOCK]);
+ retry |= trunc_dindirect (inode, EXT2_IND_BLOCK +
+ EXT2_ADDR_PER_BLOCK(inode->i_sb),
+ (u32 *) &inode->u.ext2_i.i_data[EXT2_DIND_BLOCK]);
+ retry |= trunc_tindirect (inode);
+ up(&inode->i_sem);
+ if (!retry)
+ break;
+ if (IS_SYNC(inode) && inode->i_dirt)
+ ext2_sync_inode (inode);
+ current->counter = 0;
+ schedule ();
+ }
+ /*
+ * If the file is not being truncated to a block boundary, the
+ * contents of the partial block following the end of the file must be
+ * zeroed in case it ever becomes accessible again because of
+ * subsequent file growth.
+ */
+ offset = inode->i_size % inode->i_sb->s_blocksize;
+ if (offset) {
+ bh = ext2_bread (inode, inode->i_size / inode->i_sb->s_blocksize,
+ 0, &err);
+ if (bh) {
+ memset (bh->b_data + offset, 0,
+ inode->i_sb->s_blocksize - offset);
+ mark_buffer_dirty (bh, 0);
+ brelse (bh);
+ }
+ }
+ inode->i_mtime = inode->i_ctime = CURRENT_TIME;
+ inode->i_dirt = 1;
+}