From: Theodore Ts'o <tytso@mit.edu>
To: Ext4 Developers List <linux-ext4@vger.kernel.org>
Cc: Theodore Ts'o <tytso@mit.edu>
Subject: [PATCH 09/12] libext2: optimize ext2fs_new_block2()
Date: Mon, 20 Jan 2014 00:54:11 -0500 [thread overview]
Message-ID: <1390197254-14583-10-git-send-email-tytso@mit.edu> (raw)
In-Reply-To: <1390197254-14583-1-git-send-email-tytso@mit.edu>
If there are hundreds of thousands of blocks which are in use before
the first free block, it is much, MUCH faster to use
ext2fs_find_first_zero_block_bitmap2() instead of searching the
allocation bitmap bit by bit.
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
lib/ext2fs/alloc.c | 34 +++++++++++++++++-----------------
1 file changed, 17 insertions(+), 17 deletions(-)
diff --git a/lib/ext2fs/alloc.c b/lib/ext2fs/alloc.c
index 91637dd..7dcfd3c 100644
--- a/lib/ext2fs/alloc.c
+++ b/lib/ext2fs/alloc.c
@@ -137,8 +137,8 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal,
ext2fs_block_bitmap map, blk64_t *ret)
{
- blk64_t i;
- int c_ratio;
+ errcode_t retval;
+ blk64_t b;
EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
@@ -148,21 +148,21 @@ errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal,
return EXT2_ET_NO_BLOCK_BITMAP;
if (!goal || (goal >= ext2fs_blocks_count(fs->super)))
goal = fs->super->s_first_data_block;
- i = goal;
- c_ratio = 1 << ext2fs_get_bitmap_granularity(map);
- if (c_ratio > 1)
- goal &= ~EXT2FS_CLUSTER_MASK(fs);
- do {
- if (!ext2fs_fast_test_block_bitmap2(map, i)) {
- clear_block_uninit(fs, ext2fs_group_of_blk2(fs, i));
- *ret = i;
- return 0;
- }
- i = (i + c_ratio) & ~(c_ratio - 1);
- if (i >= ext2fs_blocks_count(fs->super))
- i = fs->super->s_first_data_block;
- } while (i != goal);
- return EXT2_ET_BLOCK_ALLOC_FAIL;
+ goal &= ~EXT2FS_CLUSTER_MASK(fs);
+
+ retval = ext2fs_find_first_zero_block_bitmap2(map,
+ goal, ext2fs_blocks_count(fs->super) - 1, &b);
+ if ((retval == ENOENT) && (goal != fs->super->s_first_data_block))
+ retval = ext2fs_find_first_zero_block_bitmap2(map,
+ fs->super->s_first_data_block, goal - 1, &b);
+ if (retval == ENOENT)
+ return EXT2_ET_BLOCK_ALLOC_FAIL;
+ if (retval)
+ return retval;
+
+ clear_block_uninit(fs, ext2fs_group_of_blk2(fs, b));
+ *ret = b;
+ return 0;
}
errcode_t ext2fs_new_block(ext2_filsys fs, blk_t goal,
--
1.8.5.rc3.362.gdf10213
next prev parent reply other threads:[~2014-01-20 5:54 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-01-20 5:54 [PATCH 00/12] e2fsprogs mke2fs optimizations and new features Theodore Ts'o
2014-01-20 5:54 ` [PATCH 01/12] libext2fs: fix off-by-one bug in ext2fs_extent_insert() Theodore Ts'o
2014-01-20 5:54 ` [PATCH 02/12] libext2fs: clean up generic handling of ext2fs_find_first_{set,zero}_*() Theodore Ts'o
2014-01-20 5:54 ` [PATCH 03/12] libext2fs: build tst_bitmaps with rep invariants checking enabled Theodore Ts'o
2014-01-20 5:54 ` [PATCH 04/12] libext: optimize find_first_set() for bitarray-based bitmaps Theodore Ts'o
2014-01-20 5:54 ` [PATCH 05/12] libext2fs: optimize find_first_{zero,set}() for red-black tree based bitmaps Theodore Ts'o
2014-01-20 5:54 ` [PATCH 06/12] libext2fs: further clean up and rename check_block_uninit Theodore Ts'o
2014-01-20 20:17 ` Darrick J. Wong
2014-01-20 5:54 ` [PATCH 07/12] libext2fs: add ext2fs_block_alloc_stats_range() Theodore Ts'o
2014-02-13 21:50 ` Darrick J. Wong
2014-01-20 5:54 ` [PATCH 08/12] libext2fs: optimize ext2fs_allocate_group_table() Theodore Ts'o
2014-01-20 5:54 ` Theodore Ts'o [this message]
2014-01-20 21:52 ` [PATCH 09/12] libext2: optimize ext2fs_new_block2() Andreas Dilger
2014-01-21 15:54 ` Theodore Ts'o
2014-01-20 5:54 ` [PATCH 10/12] mke2fs: optimize fix_cluster_bg_counts() Theodore Ts'o
2014-01-20 5:54 ` [PATCH 11/12] Add support for new compat feature "sparse_super2" Theodore Ts'o
2014-01-20 21:49 ` Andreas Dilger
[not found] ` <alpine.DEB.2.10.1402051559390.16807@tglase.lan.tarent.de>
2014-02-05 16:17 ` Theodore Ts'o
2014-01-20 5:54 ` [PATCH 12/12] mke2fs: allow metadata blocks to be at the beginning of the file system Theodore Ts'o
2014-01-20 16:30 ` Theodore Ts'o
2014-01-20 23:25 ` Andreas Dilger
2014-01-21 6:23 ` Theodore Ts'o
2014-01-23 21:28 ` Andreas Dilger
2014-01-20 16:30 ` [PATCH 00/12] e2fsprogs mke2fs optimizations and new features Theodore Ts'o
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1390197254-14583-10-git-send-email-tytso@mit.edu \
--to=tytso@mit.edu \
--cc=linux-ext4@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).