summaryrefslogtreecommitdiffstats
path: root/kernel/fs/reiserfs/bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'kernel/fs/reiserfs/bitmap.c')
-rw-r--r--kernel/fs/reiserfs/bitmap.c1468
1 files changed, 1468 insertions, 0 deletions
diff --git a/kernel/fs/reiserfs/bitmap.c b/kernel/fs/reiserfs/bitmap.c
new file mode 100644
index 000000000..dc198bc64
--- /dev/null
+++ b/kernel/fs/reiserfs/bitmap.c
@@ -0,0 +1,1468 @@
+/*
+ * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
+ */
+/* Reiserfs block (de)allocator, bitmap-based. */
+
+#include <linux/time.h>
+#include "reiserfs.h"
+#include <linux/errno.h>
+#include <linux/buffer_head.h>
+#include <linux/kernel.h>
+#include <linux/pagemap.h>
+#include <linux/vmalloc.h>
+#include <linux/quotaops.h>
+#include <linux/seq_file.h>
+
+#define PREALLOCATION_SIZE 9
+
+/* different reiserfs block allocator options */
+
+#define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)
+
+#define _ALLOC_concentrating_formatted_nodes 0
+#define _ALLOC_displacing_large_files 1
+#define _ALLOC_displacing_new_packing_localities 2
+#define _ALLOC_old_hashed_relocation 3
+#define _ALLOC_new_hashed_relocation 4
+#define _ALLOC_skip_busy 5
+#define _ALLOC_displace_based_on_dirid 6
+#define _ALLOC_hashed_formatted_nodes 7
+#define _ALLOC_old_way 8
+#define _ALLOC_hundredth_slices 9
+#define _ALLOC_dirid_groups 10
+#define _ALLOC_oid_groups 11
+#define _ALLOC_packing_groups 12
+
+#define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
+#define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
+#define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
+
+#define SET_OPTION(optname) \
+ do { \
+ reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \
+ set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
+ } while(0)
+#define TEST_OPTION(optname, s) \
+ test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
+
+static inline void get_bit_address(struct super_block *s,
+ b_blocknr_t block,
+ unsigned int *bmap_nr,
+ unsigned int *offset)
+{
+ /*
+ * It is in the bitmap block number equal to the block
+ * number divided by the number of bits in a block.
+ */
+ *bmap_nr = block >> (s->s_blocksize_bits + 3);
+ /* Within that bitmap block it is located at bit offset *offset. */
+ *offset = block & ((s->s_blocksize << 3) - 1);
+}
+
+int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value)
+{
+ unsigned int bmap, offset;
+ unsigned int bmap_count = reiserfs_bmap_count(s);
+
+ if (block == 0 || block >= SB_BLOCK_COUNT(s)) {
+ reiserfs_error(s, "vs-4010",
+ "block number is out of range %lu (%u)",
+ block, SB_BLOCK_COUNT(s));
+ return 0;
+ }
+
+ get_bit_address(s, block, &bmap, &offset);
+
+ /*
+ * Old format filesystem? Unlikely, but the bitmaps are all
+ * up front so we need to account for it.
+ */
+ if (unlikely(test_bit(REISERFS_OLD_FORMAT,
+ &REISERFS_SB(s)->s_properties))) {
+ b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1;
+ if (block >= bmap1 &&
+ block <= bmap1 + bmap_count) {
+ reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) "
+ "can't be freed or reused",
+ block, bmap_count);
+ return 0;
+ }
+ } else {
+ if (offset == 0) {
+ reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) "
+ "can't be freed or reused",
+ block, bmap_count);
+ return 0;
+ }
+ }
+
+ if (bmap >= bmap_count) {
+ reiserfs_error(s, "vs-4030", "bitmap for requested block "
+ "is out of range: block=%lu, bitmap_nr=%u",
+ block, bmap);
+ return 0;
+ }
+
+ if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) {
+ reiserfs_error(s, "vs-4050", "this is root block (%u), "
+ "it must be busy", SB_ROOT_BLOCK(s));
+ return 0;
+ }
+
+ return 1;
+}
+
+/*
+ * Searches in journal structures for a given block number (bmap, off).
+ * If block is found in reiserfs journal it suggests next free block
+ * candidate to test.
+ */
+static inline int is_block_in_journal(struct super_block *s, unsigned int bmap,
+ int off, int *next)
+{
+ b_blocknr_t tmp;
+
+ if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) {
+ if (tmp) { /* hint supplied */
+ *next = tmp;
+ PROC_INFO_INC(s, scan_bitmap.in_journal_hint);
+ } else {
+ (*next) = off + 1; /* inc offset to avoid looping. */
+ PROC_INFO_INC(s, scan_bitmap.in_journal_nohint);
+ }
+ PROC_INFO_INC(s, scan_bitmap.retry);
+ return 1;
+ }
+ return 0;
+}
+
+/*
+ * Searches for a window of zero bits with given minimum and maximum
+ * lengths in one bitmap block
+ */
+static int scan_bitmap_block(struct reiserfs_transaction_handle *th,
+ unsigned int bmap_n, int *beg, int boundary,
+ int min, int max, int unfm)
+{
+ struct super_block *s = th->t_super;
+ struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n];
+ struct buffer_head *bh;
+ int end, next;
+ int org = *beg;
+
+ BUG_ON(!th->t_trans_id);
+ RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of "
+ "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1);
+ PROC_INFO_INC(s, scan_bitmap.bmap);
+
+ if (!bi) {
+ reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer "
+ "for bitmap %d", bmap_n);
+ return 0;
+ }
+
+ bh = reiserfs_read_bitmap_block(s, bmap_n);
+ if (bh == NULL)
+ return 0;
+
+ while (1) {
+cont:
+ if (bi->free_count < min) {
+ brelse(bh);
+ return 0; /* No free blocks in this bitmap */
+ }
+
+ /* search for a first zero bit -- beginning of a window */
+ *beg = reiserfs_find_next_zero_le_bit
+ ((unsigned long *)(bh->b_data), boundary, *beg);
+
+ /*
+ * search for a zero bit fails or the rest of bitmap block
+ * cannot contain a zero window of minimum size
+ */
+ if (*beg + min > boundary) {
+ brelse(bh);
+ return 0;
+ }
+
+ if (unfm && is_block_in_journal(s, bmap_n, *beg, beg))
+ continue;
+ /* first zero bit found; we check next bits */
+ for (end = *beg + 1;; end++) {
+ if (end >= *beg + max || end >= boundary
+ || reiserfs_test_le_bit(end, bh->b_data)) {
+ next = end;
+ break;
+ }
+
+ /*
+ * finding the other end of zero bit window requires
+ * looking into journal structures (in case of
+ * searching for free blocks for unformatted nodes)
+ */
+ if (unfm && is_block_in_journal(s, bmap_n, end, &next))
+ break;
+ }
+
+ /*
+ * now (*beg) points to beginning of zero bits window,
+ * (end) points to one bit after the window end
+ */
+
+ /* found window of proper size */
+ if (end - *beg >= min) {
+ int i;
+ reiserfs_prepare_for_journal(s, bh, 1);
+ /*
+ * try to set all blocks used checking are
+ * they still free
+ */
+ for (i = *beg; i < end; i++) {
+ /* Don't check in journal again. */
+ if (reiserfs_test_and_set_le_bit
+ (i, bh->b_data)) {
+ /*
+ * bit was set by another process while
+ * we slept in prepare_for_journal()
+ */
+ PROC_INFO_INC(s, scan_bitmap.stolen);
+
+ /*
+ * we can continue with smaller set
+ * of allocated blocks, if length of
+ * this set is more or equal to `min'
+ */
+ if (i >= *beg + min) {
+ end = i;
+ break;
+ }
+
+ /*
+ * otherwise we clear all bit
+ * were set ...
+ */
+ while (--i >= *beg)
+ reiserfs_clear_le_bit
+ (i, bh->b_data);
+ reiserfs_restore_prepared_buffer(s, bh);
+ *beg = org;
+
+ /*
+ * Search again in current block
+ * from beginning
+ */
+ goto cont;
+ }
+ }
+ bi->free_count -= (end - *beg);
+ journal_mark_dirty(th, bh);
+ brelse(bh);
+
+ /* free block count calculation */
+ reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s),
+ 1);
+ PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
+ journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
+
+ return end - (*beg);
+ } else {
+ *beg = next;
+ }
+ }
+}
+
+static int bmap_hash_id(struct super_block *s, u32 id)
+{
+ char *hash_in = NULL;
+ unsigned long hash;
+ unsigned bm;
+
+ if (id <= 2) {
+ bm = 1;
+ } else {
+ hash_in = (char *)(&id);
+ hash = keyed_hash(hash_in, 4);
+ bm = hash % reiserfs_bmap_count(s);
+ if (!bm)
+ bm = 1;
+ }
+ /* this can only be true when SB_BMAP_NR = 1 */
+ if (bm >= reiserfs_bmap_count(s))
+ bm = 0;
+ return bm;
+}
+
+/*
+ * hashes the id and then returns > 0 if the block group for the
+ * corresponding hash is full
+ */
+static inline int block_group_used(struct super_block *s, u32 id)
+{
+ int bm = bmap_hash_id(s, id);
+ struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm];
+
+ /*
+ * If we don't have cached information on this bitmap block, we're
+ * going to have to load it later anyway. Loading it here allows us
+ * to make a better decision. This favors long-term performance gain
+ * with a better on-disk layout vs. a short term gain of skipping the
+ * read and potentially having a bad placement.
+ */
+ if (info->free_count == UINT_MAX) {
+ struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm);
+ brelse(bh);
+ }
+
+ if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) {
+ return 0;
+ }
+ return 1;
+}
+
+/*
+ * the packing is returned in disk byte order
+ */
+__le32 reiserfs_choose_packing(struct inode * dir)
+{
+ __le32 packing;
+ if (TEST_OPTION(packing_groups, dir->i_sb)) {
+ u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
+ /*
+ * some versions of reiserfsck expect packing locality 1 to be
+ * special
+ */
+ if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir))
+ packing = INODE_PKEY(dir)->k_objectid;
+ else
+ packing = INODE_PKEY(dir)->k_dir_id;
+ } else
+ packing = INODE_PKEY(dir)->k_objectid;
+ return packing;
+}
+
+/*
+ * Tries to find contiguous zero bit window (given size) in given region of
+ * bitmap and place new blocks there. Returns number of allocated blocks.
+ */
+static int scan_bitmap(struct reiserfs_transaction_handle *th,
+ b_blocknr_t * start, b_blocknr_t finish,
+ int min, int max, int unfm, sector_t file_block)
+{
+ int nr_allocated = 0;
+ struct super_block *s = th->t_super;
+ unsigned int bm, off;
+ unsigned int end_bm, end_off;
+ unsigned int off_max = s->s_blocksize << 3;
+
+ BUG_ON(!th->t_trans_id);
+ PROC_INFO_INC(s, scan_bitmap.call);
+
+ /* No point in looking for more free blocks */
+ if (SB_FREE_BLOCKS(s) <= 0)
+ return 0;
+
+ get_bit_address(s, *start, &bm, &off);
+ get_bit_address(s, finish, &end_bm, &end_off);
+ if (bm > reiserfs_bmap_count(s))
+ return 0;
+ if (end_bm > reiserfs_bmap_count(s))
+ end_bm = reiserfs_bmap_count(s);
+
+ /*
+ * When the bitmap is more than 10% free, anyone can allocate.
+ * When it's less than 10% free, only files that already use the
+ * bitmap are allowed. Once we pass 80% full, this restriction
+ * is lifted.
+ *
+ * We do this so that files that grow later still have space close to
+ * their original allocation. This improves locality, and presumably
+ * performance as a result.
+ *
+ * This is only an allocation policy and does not make up for getting a
+ * bad hint. Decent hinting must be implemented for this to work well.
+ */
+ if (TEST_OPTION(skip_busy, s)
+ && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) {
+ for (; bm < end_bm; bm++, off = 0) {
+ if ((off && (!unfm || (file_block != 0)))
+ || SB_AP_BITMAP(s)[bm].free_count >
+ (s->s_blocksize << 3) / 10)
+ nr_allocated =
+ scan_bitmap_block(th, bm, &off, off_max,
+ min, max, unfm);
+ if (nr_allocated)
+ goto ret;
+ }
+ /* we know from above that start is a reasonable number */
+ get_bit_address(s, *start, &bm, &off);
+ }
+
+ for (; bm < end_bm; bm++, off = 0) {
+ nr_allocated =
+ scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
+ if (nr_allocated)
+ goto ret;
+ }
+
+ nr_allocated =
+ scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
+
+ret:
+ *start = bm * off_max + off;
+ return nr_allocated;
+
+}
+
+static void _reiserfs_free_block(struct reiserfs_transaction_handle *th,
+ struct inode *inode, b_blocknr_t block,
+ int for_unformatted)
+{
+ struct super_block *s = th->t_super;
+ struct reiserfs_super_block *rs;
+ struct buffer_head *sbh, *bmbh;
+ struct reiserfs_bitmap_info *apbi;
+ unsigned int nr, offset;
+
+ BUG_ON(!th->t_trans_id);
+ PROC_INFO_INC(s, free_block);
+ rs = SB_DISK_SUPER_BLOCK(s);
+ sbh = SB_BUFFER_WITH_SB(s);
+ apbi = SB_AP_BITMAP(s);
+
+ get_bit_address(s, block, &nr, &offset);
+
+ if (nr >= reiserfs_bmap_count(s)) {
+ reiserfs_error(s, "vs-4075", "block %lu is out of range",
+ block);
+ return;
+ }
+
+ bmbh = reiserfs_read_bitmap_block(s, nr);
+ if (!bmbh)
+ return;
+
+ reiserfs_prepare_for_journal(s, bmbh, 1);
+
+ /* clear bit for the given block in bit map */
+ if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) {
+ reiserfs_error(s, "vs-4080",
+ "block %lu: bit already cleared", block);
+ }
+ apbi[nr].free_count++;
+ journal_mark_dirty(th, bmbh);
+ brelse(bmbh);
+
+ reiserfs_prepare_for_journal(s, sbh, 1);
+ /* update super block */
+ set_sb_free_blocks(rs, sb_free_blocks(rs) + 1);
+
+ journal_mark_dirty(th, sbh);
+ if (for_unformatted) {
+ int depth = reiserfs_write_unlock_nested(s);
+ dquot_free_block_nodirty(inode, 1);
+ reiserfs_write_lock_nested(s, depth);
+ }
+}
+
+void reiserfs_free_block(struct reiserfs_transaction_handle *th,
+ struct inode *inode, b_blocknr_t block,
+ int for_unformatted)
+{
+ struct super_block *s = th->t_super;
+
+ BUG_ON(!th->t_trans_id);
+ RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
+ if (!is_reusable(s, block, 1))
+ return;
+
+ if (block > sb_block_count(REISERFS_SB(s)->s_rs)) {
+ reiserfs_error(th->t_super, "bitmap-4072",
+ "Trying to free block outside file system "
+ "boundaries (%lu > %lu)",
+ block, sb_block_count(REISERFS_SB(s)->s_rs));
+ return;
+ }
+ /* mark it before we clear it, just in case */
+ journal_mark_freed(th, s, block);
+ _reiserfs_free_block(th, inode, block, for_unformatted);
+}
+
+/* preallocated blocks don't need to be run through journal_mark_freed */
+static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th,
+ struct inode *inode, b_blocknr_t block)
+{
+ BUG_ON(!th->t_trans_id);
+ RFALSE(!th->t_super,
+ "vs-4060: trying to free block on nonexistent device");
+ if (!is_reusable(th->t_super, block, 1))
+ return;
+ _reiserfs_free_block(th, inode, block, 1);
+}
+
+static void __discard_prealloc(struct reiserfs_transaction_handle *th,
+ struct reiserfs_inode_info *ei)
+{
+ unsigned long save = ei->i_prealloc_block;
+ int dirty = 0;
+ struct inode *inode = &ei->vfs_inode;
+
+ BUG_ON(!th->t_trans_id);
+#ifdef CONFIG_REISERFS_CHECK
+ if (ei->i_prealloc_count < 0)
+ reiserfs_error(th->t_super, "zam-4001",
+ "inode has negative prealloc blocks count.");
+#endif
+ while (ei->i_prealloc_count > 0) {
+ reiserfs_free_prealloc_block(th, inode, ei->i_prealloc_block);
+ ei->i_prealloc_block++;
+ ei->i_prealloc_count--;
+ dirty = 1;
+ }
+ if (dirty)
+ reiserfs_update_sd(th, inode);
+ ei->i_prealloc_block = save;
+ list_del_init(&ei->i_prealloc_list);
+}
+
+/* FIXME: It should be inline function */
+void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th,
+ struct inode *inode)
+{
+ struct reiserfs_inode_info *ei = REISERFS_I(inode);
+
+ BUG_ON(!th->t_trans_id);
+ if (ei->i_prealloc_count)
+ __discard_prealloc(th, ei);
+}
+
+void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th)
+{
+ struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
+
+ BUG_ON(!th->t_trans_id);
+ while (!list_empty(plist)) {
+ struct reiserfs_inode_info *ei;
+ ei = list_entry(plist->next, struct reiserfs_inode_info,
+ i_prealloc_list);
+#ifdef CONFIG_REISERFS_CHECK
+ if (!ei->i_prealloc_count) {
+ reiserfs_error(th->t_super, "zam-4001",
+ "inode is in prealloc list but has "
+ "no preallocated blocks.");
+ }
+#endif
+ __discard_prealloc(th, ei);
+ }
+}
+
+void reiserfs_init_alloc_options(struct super_block *s)
+{
+ set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s));
+ set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s));
+ set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s));
+}
+
+/* block allocator related options are parsed here */
+int reiserfs_parse_alloc_options(struct super_block *s, char *options)
+{
+ char *this_char, *value;
+
+ /* clear default settings */
+ REISERFS_SB(s)->s_alloc_options.bits = 0;
+
+ while ((this_char = strsep(&options, ":")) != NULL) {
+ if ((value = strchr(this_char, '=')) != NULL)
+ *value++ = 0;
+
+ if (!strcmp(this_char, "concentrating_formatted_nodes")) {
+ int temp;
+ SET_OPTION(concentrating_formatted_nodes);
+ temp = (value
+ && *value) ? simple_strtoul(value, &value,
+ 0) : 10;
+ if (temp <= 0 || temp > 100) {
+ REISERFS_SB(s)->s_alloc_options.border = 10;
+ } else {
+ REISERFS_SB(s)->s_alloc_options.border =
+ 100 / temp;
+ }
+ continue;
+ }
+ if (!strcmp(this_char, "displacing_large_files")) {
+ SET_OPTION(displacing_large_files);
+ REISERFS_SB(s)->s_alloc_options.large_file_size =
+ (value
+ && *value) ? simple_strtoul(value, &value, 0) : 16;
+ continue;
+ }
+ if (!strcmp(this_char, "displacing_new_packing_localities")) {
+ SET_OPTION(displacing_new_packing_localities);
+ continue;
+ }
+
+ if (!strcmp(this_char, "old_hashed_relocation")) {
+ SET_OPTION(old_hashed_relocation);
+ continue;
+ }
+
+ if (!strcmp(this_char, "new_hashed_relocation")) {
+ SET_OPTION(new_hashed_relocation);
+ continue;
+ }
+
+ if (!strcmp(this_char, "dirid_groups")) {
+ SET_OPTION(dirid_groups);
+ continue;
+ }
+ if (!strcmp(this_char, "oid_groups")) {
+ SET_OPTION(oid_groups);
+ continue;
+ }
+ if (!strcmp(this_char, "packing_groups")) {
+ SET_OPTION(packing_groups);
+ continue;
+ }
+ if (!strcmp(this_char, "hashed_formatted_nodes")) {
+ SET_OPTION(hashed_formatted_nodes);
+ continue;
+ }
+
+ if (!strcmp(this_char, "skip_busy")) {
+ SET_OPTION(skip_busy);
+ continue;
+ }
+
+ if (!strcmp(this_char, "hundredth_slices")) {
+ SET_OPTION(hundredth_slices);
+ continue;
+ }
+
+ if (!strcmp(this_char, "old_way")) {
+ SET_OPTION(old_way);
+ continue;
+ }
+
+ if (!strcmp(this_char, "displace_based_on_dirid")) {
+ SET_OPTION(displace_based_on_dirid);
+ continue;
+ }
+
+ if (!strcmp(this_char, "preallocmin")) {
+ REISERFS_SB(s)->s_alloc_options.preallocmin =
+ (value
+ && *value) ? simple_strtoul(value, &value, 0) : 4;
+ continue;
+ }
+
+ if (!strcmp(this_char, "preallocsize")) {
+ REISERFS_SB(s)->s_alloc_options.preallocsize =
+ (value
+ && *value) ? simple_strtoul(value, &value,
+ 0) :
+ PREALLOCATION_SIZE;
+ continue;
+ }
+
+ reiserfs_warning(s, "zam-4001", "unknown option - %s",
+ this_char);
+ return 1;
+ }
+
+ reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
+ return 0;
+}
+
+static void print_sep(struct seq_file *seq, int *first)
+{
+ if (!*first)
+ seq_puts(seq, ":");
+ else
+ *first = 0;
+}
+
+void show_alloc_options(struct seq_file *seq, struct super_block *s)
+{
+ int first = 1;
+
+ if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) |
+ (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups)))
+ return;
+
+ seq_puts(seq, ",alloc=");
+
+ if (TEST_OPTION(concentrating_formatted_nodes, s)) {
+ print_sep(seq, &first);
+ if (REISERFS_SB(s)->s_alloc_options.border != 10) {
+ seq_printf(seq, "concentrating_formatted_nodes=%d",
+ 100 / REISERFS_SB(s)->s_alloc_options.border);
+ } else
+ seq_puts(seq, "concentrating_formatted_nodes");
+ }
+ if (TEST_OPTION(displacing_large_files, s)) {
+ print_sep(seq, &first);
+ if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) {
+ seq_printf(seq, "displacing_large_files=%lu",
+ REISERFS_SB(s)->s_alloc_options.large_file_size);
+ } else
+ seq_puts(seq, "displacing_large_files");
+ }
+ if (TEST_OPTION(displacing_new_packing_localities, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "displacing_new_packing_localities");
+ }
+ if (TEST_OPTION(old_hashed_relocation, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "old_hashed_relocation");
+ }
+ if (TEST_OPTION(new_hashed_relocation, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "new_hashed_relocation");
+ }
+ if (TEST_OPTION(dirid_groups, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "dirid_groups");
+ }
+ if (TEST_OPTION(oid_groups, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "oid_groups");
+ }
+ if (TEST_OPTION(packing_groups, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "packing_groups");
+ }
+ if (TEST_OPTION(hashed_formatted_nodes, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "hashed_formatted_nodes");
+ }
+ if (TEST_OPTION(skip_busy, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "skip_busy");
+ }
+ if (TEST_OPTION(hundredth_slices, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "hundredth_slices");
+ }
+ if (TEST_OPTION(old_way, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "old_way");
+ }
+ if (TEST_OPTION(displace_based_on_dirid, s)) {
+ print_sep(seq, &first);
+ seq_puts(seq, "displace_based_on_dirid");
+ }
+ if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) {
+ print_sep(seq, &first);
+ seq_printf(seq, "preallocmin=%d",
+ REISERFS_SB(s)->s_alloc_options.preallocmin);
+ }
+ if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) {
+ print_sep(seq, &first);
+ seq_printf(seq, "preallocsize=%d",
+ REISERFS_SB(s)->s_alloc_options.preallocsize);
+ }
+}
+
+static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint)
+{
+ char *hash_in;
+
+ if (hint->formatted_node) {
+ hash_in = (char *)&hint->key.k_dir_id;
+ } else {
+ if (!hint->inode) {
+ /*hint->search_start = hint->beg;*/
+ hash_in = (char *)&hint->key.k_dir_id;
+ } else
+ if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
+ hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
+ else
+ hash_in =
+ (char *)(&INODE_PKEY(hint->inode)->k_objectid);
+ }
+
+ hint->search_start =
+ hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
+}
+
+/*
+ * Relocation based on dirid, hashing them into a given bitmap block
+ * files. Formatted nodes are unaffected, a separate policy covers them
+ */
+static void dirid_groups(reiserfs_blocknr_hint_t * hint)
+{
+ unsigned long hash;
+ __u32 dirid = 0;
+ int bm = 0;
+ struct super_block *sb = hint->th->t_super;
+
+ if (hint->inode)
+ dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
+ else if (hint->formatted_node)
+ dirid = hint->key.k_dir_id;
+
+ if (dirid) {
+ bm = bmap_hash_id(sb, dirid);
+ hash = bm * (sb->s_blocksize << 3);
+ /* give a portion of the block group to metadata */
+ if (hint->inode)
+ hash += sb->s_blocksize / 2;
+ hint->search_start = hash;
+ }
+}
+
+/*
+ * Relocation based on oid, hashing them into a given bitmap block
+ * files. Formatted nodes are unaffected, a separate policy covers them
+ */
+static void oid_groups(reiserfs_blocknr_hint_t * hint)
+{
+ if (hint->inode) {
+ unsigned long hash;
+ __u32 oid;
+ __u32 dirid;
+ int bm;
+
+ dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
+
+ /*
+ * keep the root dir and it's first set of subdirs close to
+ * the start of the disk
+ */
+ if (dirid <= 2)
+ hash = (hint->inode->i_sb->s_blocksize << 3);
+ else {
+ oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid);
+ bm = bmap_hash_id(hint->inode->i_sb, oid);
+ hash = bm * (hint->inode->i_sb->s_blocksize << 3);
+ }
+ hint->search_start = hash;
+ }
+}
+
+/*
+ * returns 1 if it finds an indirect item and gets valid hint info
+ * from it, otherwise 0
+ */
+static int get_left_neighbor(reiserfs_blocknr_hint_t * hint)
+{
+ struct treepath *path;
+ struct buffer_head *bh;
+ struct item_head *ih;
+ int pos_in_item;
+ __le32 *item;
+ int ret = 0;
+
+ /*
+ * reiserfs code can call this function w/o pointer to path
+ * structure supplied; then we rely on supplied search_start
+ */
+ if (!hint->path)
+ return 0;
+
+ path = hint->path;
+ bh = get_last_bh(path);
+ RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor");
+ ih = tp_item_head(path);
+ pos_in_item = path->pos_in_item;
+ item = tp_item_body(path);
+
+ hint->search_start = bh->b_blocknr;
+
+ /*
+ * for indirect item: go to left and look for the first non-hole entry
+ * in the indirect item
+ */
+ if (!hint->formatted_node && is_indirect_le_ih(ih)) {
+ if (pos_in_item == I_UNFM_NUM(ih))
+ pos_in_item--;
+ while (pos_in_item >= 0) {
+ int t = get_block_num(item, pos_in_item);
+ if (t) {
+ hint->search_start = t;
+ ret = 1;
+ break;
+ }
+ pos_in_item--;
+ }
+ }
+
+ /* does result value fit into specified region? */
+ return ret;
+}
+
+/*
+ * should be, if formatted node, then try to put on first part of the device
+ * specified as number of percent with mount option device, else try to put
+ * on last of device. This is not to say it is good code to do so,
+ * but the effect should be measured.
+ */
+static inline void set_border_in_hint(struct super_block *s,
+ reiserfs_blocknr_hint_t * hint)
+{
+ b_blocknr_t border =
+ SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
+
+ if (hint->formatted_node)
+ hint->end = border - 1;
+ else
+ hint->beg = border;
+}
+
+static inline void displace_large_file(reiserfs_blocknr_hint_t * hint)
+{
+ if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
+ hint->search_start =
+ hint->beg +
+ keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id),
+ 4) % (hint->end - hint->beg);
+ else
+ hint->search_start =
+ hint->beg +
+ keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid),
+ 4) % (hint->end - hint->beg);
+}
+
+static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint)
+{
+ char *hash_in;
+
+ if (!hint->inode)
+ hash_in = (char *)&hint->key.k_dir_id;
+ else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
+ hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
+ else
+ hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
+
+ hint->search_start =
+ hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
+}
+
+static inline int
+this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *
+ hint)
+{
+ return hint->block ==
+ REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
+}
+
+#ifdef DISPLACE_NEW_PACKING_LOCALITIES
+static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint)
+{
+ struct in_core_key *key = &hint->key;
+
+ hint->th->displace_new_blocks = 0;
+ hint->search_start =
+ hint->beg + keyed_hash((char *)(&key->k_objectid),
+ 4) % (hint->end - hint->beg);
+}
+#endif
+
+static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint)
+{
+ b_blocknr_t border;
+ u32 hash_in;
+
+ if (hint->formatted_node || hint->inode == NULL) {
+ return 0;
+ }
+
+ hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
+ border =
+ hint->beg + (u32) keyed_hash(((char *)(&hash_in)),
+ 4) % (hint->end - hint->beg - 1);
+ if (border > hint->search_start)
+ hint->search_start = border;
+
+ return 1;
+}
+
+static inline int old_way(reiserfs_blocknr_hint_t * hint)
+{
+ b_blocknr_t border;
+
+ if (hint->formatted_node || hint->inode == NULL) {
+ return 0;
+ }
+
+ border =
+ hint->beg +
+ le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end -
+ hint->beg);
+ if (border > hint->search_start)
+ hint->search_start = border;
+
+ return 1;
+}
+
+static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint)
+{
+ struct in_core_key *key = &hint->key;
+ b_blocknr_t slice_start;
+
+ slice_start =
+ (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100);
+ if (slice_start > hint->search_start
+ || slice_start + (hint->end / 100) <= hint->search_start) {
+ hint->search_start = slice_start;
+ }
+}
+
+static void determine_search_start(reiserfs_blocknr_hint_t * hint,
+ int amount_needed)
+{
+ struct super_block *s = hint->th->t_super;
+ int unfm_hint;
+
+ hint->beg = 0;
+ hint->end = SB_BLOCK_COUNT(s) - 1;
+
+ /* This is former border algorithm. Now with tunable border offset */
+ if (concentrating_formatted_nodes(s))
+ set_border_in_hint(s, hint);
+
+#ifdef DISPLACE_NEW_PACKING_LOCALITIES
+ /*
+ * whenever we create a new directory, we displace it. At first
+ * we will hash for location, later we might look for a moderately
+ * empty place for it
+ */
+ if (displacing_new_packing_localities(s)
+ && hint->th->displace_new_blocks) {
+ displace_new_packing_locality(hint);
+
+ /*
+ * we do not continue determine_search_start,
+ * if new packing locality is being displaced
+ */
+ return;
+ }
+#endif
+
+ /*
+ * all persons should feel encouraged to add more special cases
+ * here and test them
+ */
+
+ if (displacing_large_files(s) && !hint->formatted_node
+ && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
+ displace_large_file(hint);
+ return;
+ }
+
+ /*
+ * if none of our special cases is relevant, use the left
+ * neighbor in the tree order of the new node we are allocating for
+ */
+ if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) {
+ hash_formatted_node(hint);
+ return;
+ }
+
+ unfm_hint = get_left_neighbor(hint);
+
+ /*
+ * Mimic old block allocator behaviour, that is if VFS allowed for
+ * preallocation, new blocks are displaced based on directory ID.
+ * Also, if suggested search_start is less than last preallocated
+ * block, we start searching from it, assuming that HDD dataflow
+ * is faster in forward direction
+ */
+ if (TEST_OPTION(old_way, s)) {
+ if (!hint->formatted_node) {
+ if (!reiserfs_hashed_relocation(s))
+ old_way(hint);
+ else if (!reiserfs_no_unhashed_relocation(s))
+ old_hashed_relocation(hint);
+
+ if (hint->inode
+ && hint->search_start <
+ REISERFS_I(hint->inode)->i_prealloc_block)
+ hint->search_start =
+ REISERFS_I(hint->inode)->i_prealloc_block;
+ }
+ return;
+ }
+
+ /* This is an approach proposed by Hans */
+ if (TEST_OPTION(hundredth_slices, s)
+ && !(displacing_large_files(s) && !hint->formatted_node)) {
+ hundredth_slices(hint);
+ return;
+ }
+
+ /* old_hashed_relocation only works on unformatted */
+ if (!unfm_hint && !hint->formatted_node &&
+ TEST_OPTION(old_hashed_relocation, s)) {
+ old_hashed_relocation(hint);
+ }
+
+ /* new_hashed_relocation works with both formatted/unformatted nodes */
+ if ((!unfm_hint || hint->formatted_node) &&
+ TEST_OPTION(new_hashed_relocation, s)) {
+ new_hashed_relocation(hint);
+ }
+
+ /* dirid grouping works only on unformatted nodes */
+ if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
+ dirid_groups(hint);
+ }
+#ifdef DISPLACE_NEW_PACKING_LOCALITIES
+ if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
+ dirid_groups(hint);
+ }
+#endif
+
+ /* oid grouping works only on unformatted nodes */
+ if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) {
+ oid_groups(hint);
+ }
+ return;
+}
+
+static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
+{
+ /* make minimum size a mount option and benchmark both ways */
+ /* we preallocate blocks only for regular files, specific size */
+ /* benchmark preallocating always and see what happens */
+
+ hint->prealloc_size = 0;
+
+ if (!hint->formatted_node && hint->preallocate) {
+ if (S_ISREG(hint->inode->i_mode)
+ && hint->inode->i_size >=
+ REISERFS_SB(hint->th->t_super)->s_alloc_options.
+ preallocmin * hint->inode->i_sb->s_blocksize)
+ hint->prealloc_size =
+ REISERFS_SB(hint->th->t_super)->s_alloc_options.
+ preallocsize - 1;
+ }
+ return CARRY_ON;
+}
+
+static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint,
+ b_blocknr_t * new_blocknrs,
+ b_blocknr_t start,
+ b_blocknr_t finish, int min,
+ int amount_needed,
+ int prealloc_size)
+{
+ int rest = amount_needed;
+ int nr_allocated;
+
+ while (rest > 0 && start <= finish) {
+ nr_allocated = scan_bitmap(hint->th, &start, finish, min,
+ rest + prealloc_size,
+ !hint->formatted_node, hint->block);
+
+ if (nr_allocated == 0) /* no new blocks allocated, return */
+ break;
+
+ /* fill free_blocknrs array first */
+ while (rest > 0 && nr_allocated > 0) {
+ *new_blocknrs++ = start++;
+ rest--;
+ nr_allocated--;
+ }
+
+ /* do we have something to fill prealloc. array also ? */
+ if (nr_allocated > 0) {
+ /*
+ * it means prealloc_size was greater that 0 and
+ * we do preallocation
+ */
+ list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
+ &SB_JOURNAL(hint->th->t_super)->
+ j_prealloc_list);
+ REISERFS_I(hint->inode)->i_prealloc_block = start;
+ REISERFS_I(hint->inode)->i_prealloc_count =
+ nr_allocated;
+ break;
+ }
+ }
+
+ return (amount_needed - rest);
+}
+
+static inline int blocknrs_and_prealloc_arrays_from_search_start
+ (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs,
+ int amount_needed) {
+ struct super_block *s = hint->th->t_super;
+ b_blocknr_t start = hint->search_start;
+ b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
+ int passno = 0;
+ int nr_allocated = 0;
+ int depth;
+
+ determine_prealloc_size(hint);
+ if (!hint->formatted_node) {
+ int quota_ret;
+#ifdef REISERQUOTA_DEBUG
+ reiserfs_debug(s, REISERFS_DEBUG_CODE,
+ "reiserquota: allocating %d blocks id=%u",
+ amount_needed, hint->inode->i_uid);
+#endif
+ depth = reiserfs_write_unlock_nested(s);
+ quota_ret =
+ dquot_alloc_block_nodirty(hint->inode, amount_needed);
+ if (quota_ret) { /* Quota exceeded? */
+ reiserfs_write_lock_nested(s, depth);
+ return QUOTA_EXCEEDED;
+ }
+ if (hint->preallocate && hint->prealloc_size) {
+#ifdef REISERQUOTA_DEBUG
+ reiserfs_debug(s, REISERFS_DEBUG_CODE,
+ "reiserquota: allocating (prealloc) %d blocks id=%u",
+ hint->prealloc_size, hint->inode->i_uid);
+#endif
+ quota_ret = dquot_prealloc_block_nodirty(hint->inode,
+ hint->prealloc_size);
+ if (quota_ret)
+ hint->preallocate = hint->prealloc_size = 0;
+ }
+ /* for unformatted nodes, force large allocations */
+ reiserfs_write_lock_nested(s, depth);
+ }
+
+ do {
+ switch (passno++) {
+ case 0: /* Search from hint->search_start to end of disk */
+ start = hint->search_start;
+ finish = SB_BLOCK_COUNT(s) - 1;
+ break;
+ case 1: /* Search from hint->beg to hint->search_start */
+ start = hint->beg;
+ finish = hint->search_start;
+ break;
+ case 2: /* Last chance: Search from 0 to hint->beg */
+ start = 0;
+ finish = hint->beg;
+ break;
+ default:
+ /* We've tried searching everywhere, not enough space */
+ /* Free the blocks */
+ if (!hint->formatted_node) {
+#ifdef REISERQUOTA_DEBUG
+ reiserfs_debug(s, REISERFS_DEBUG_CODE,
+ "reiserquota: freeing (nospace) %d blocks id=%u",
+ amount_needed +
+ hint->prealloc_size -
+ nr_allocated,
+ hint->inode->i_uid);
+#endif
+ /* Free not allocated blocks */
+ depth = reiserfs_write_unlock_nested(s);
+ dquot_free_block_nodirty(hint->inode,
+ amount_needed + hint->prealloc_size -
+ nr_allocated);
+ reiserfs_write_lock_nested(s, depth);
+ }
+ while (nr_allocated--)
+ reiserfs_free_block(hint->th, hint->inode,
+ new_blocknrs[nr_allocated],
+ !hint->formatted_node);
+
+ return NO_DISK_SPACE;
+ }
+ } while ((nr_allocated += allocate_without_wrapping_disk(hint,
+ new_blocknrs +
+ nr_allocated,
+ start, finish,
+ 1,
+ amount_needed -
+ nr_allocated,
+ hint->
+ prealloc_size))
+ < amount_needed);
+ if (!hint->formatted_node &&
+ amount_needed + hint->prealloc_size >
+ nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
+ /* Some of preallocation blocks were not allocated */
+#ifdef REISERQUOTA_DEBUG
+ reiserfs_debug(s, REISERFS_DEBUG_CODE,
+ "reiserquota: freeing (failed prealloc) %d blocks id=%u",
+ amount_needed + hint->prealloc_size -
+ nr_allocated -
+ REISERFS_I(hint->inode)->i_prealloc_count,
+ hint->inode->i_uid);
+#endif
+
+ depth = reiserfs_write_unlock_nested(s);
+ dquot_free_block_nodirty(hint->inode, amount_needed +
+ hint->prealloc_size - nr_allocated -
+ REISERFS_I(hint->inode)->
+ i_prealloc_count);
+ reiserfs_write_lock_nested(s, depth);
+ }
+
+ return CARRY_ON;
+}
+
+/* grab new blocknrs from preallocated list */
+/* return amount still needed after using them */
+static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint,
+ b_blocknr_t * new_blocknrs,
+ int amount_needed)
+{
+ struct inode *inode = hint->inode;
+
+ if (REISERFS_I(inode)->i_prealloc_count > 0) {
+ while (amount_needed) {
+
+ *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++;
+ REISERFS_I(inode)->i_prealloc_count--;
+
+ amount_needed--;
+
+ if (REISERFS_I(inode)->i_prealloc_count <= 0) {
+ list_del(&REISERFS_I(inode)->i_prealloc_list);
+ break;
+ }
+ }
+ }
+ /* return amount still needed after using preallocated blocks */
+ return amount_needed;
+}
+
+int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
+ b_blocknr_t *new_blocknrs,
+ int amount_needed,
+ /* Amount of blocks we have already reserved */
+ int reserved_by_us)
+{
+ int initial_amount_needed = amount_needed;
+ int ret;
+ struct super_block *s = hint->th->t_super;
+
+ /* Check if there is enough space, taking into account reserved space */
+ if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks <
+ amount_needed - reserved_by_us)
+ return NO_DISK_SPACE;
+ /* should this be if !hint->inode && hint->preallocate? */
+ /* do you mean hint->formatted_node can be removed ? - Zam */
+ /*
+ * hint->formatted_node cannot be removed because we try to access
+ * inode information here, and there is often no inode associated with
+ * metadata allocations - green
+ */
+
+ if (!hint->formatted_node && hint->preallocate) {
+ amount_needed = use_preallocated_list_if_available
+ (hint, new_blocknrs, amount_needed);
+
+ /*
+ * We have all the block numbers we need from the
+ * prealloc list
+ */
+ if (amount_needed == 0)
+ return CARRY_ON;
+ new_blocknrs += (initial_amount_needed - amount_needed);
+ }
+
+ /* find search start and save it in hint structure */
+ determine_search_start(hint, amount_needed);
+ if (hint->search_start >= SB_BLOCK_COUNT(s))
+ hint->search_start = SB_BLOCK_COUNT(s) - 1;
+
+ /* allocation itself; fill new_blocknrs and preallocation arrays */
+ ret = blocknrs_and_prealloc_arrays_from_search_start
+ (hint, new_blocknrs, amount_needed);
+
+ /*
+ * We used prealloc. list to fill (partially) new_blocknrs array.
+ * If final allocation fails we need to return blocks back to
+ * prealloc. list or just free them. -- Zam (I chose second
+ * variant)
+ */
+ if (ret != CARRY_ON) {
+ while (amount_needed++ < initial_amount_needed) {
+ reiserfs_free_block(hint->th, hint->inode,
+ *(--new_blocknrs), 1);
+ }
+ }
+ return ret;
+}
+
+void reiserfs_cache_bitmap_metadata(struct super_block *sb,
+ struct buffer_head *bh,
+ struct reiserfs_bitmap_info *info)
+{
+ unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size);
+
+ /* The first bit must ALWAYS be 1 */
+ if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data))
+ reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is "
+ "corrupted: first bit must be 1", bh->b_blocknr);
+
+ info->free_count = 0;
+
+ while (--cur >= (unsigned long *)bh->b_data) {
+ /* 0 and ~0 are special, we can optimize for them */
+ if (*cur == 0)
+ info->free_count += BITS_PER_LONG;
+ else if (*cur != ~0L) /* A mix, investigate */
+ info->free_count += BITS_PER_LONG - hweight_long(*cur);
+ }
+}
+
+struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb,
+ unsigned int bitmap)
+{
+ b_blocknr_t block = (sb->s_blocksize << 3) * bitmap;
+ struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap;
+ struct buffer_head *bh;
+
+ /*
+ * Way old format filesystems had the bitmaps packed up front.
+ * I doubt there are any of these left, but just in case...
+ */
+ if (unlikely(test_bit(REISERFS_OLD_FORMAT,
+ &REISERFS_SB(sb)->s_properties)))
+ block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap;
+ else if (bitmap == 0)
+ block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1;
+
+ bh = sb_bread(sb, block);
+ if (bh == NULL)
+ reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) "
+ "reading failed", __func__, block);
+ else {
+ if (buffer_locked(bh)) {
+ int depth;
+ PROC_INFO_INC(sb, scan_bitmap.wait);
+ depth = reiserfs_write_unlock_nested(sb);
+ __wait_on_buffer(bh);
+ reiserfs_write_lock_nested(sb, depth);
+ }
+ BUG_ON(!buffer_uptodate(bh));
+ BUG_ON(atomic_read(&bh->b_count) == 0);
+
+ if (info->free_count == UINT_MAX)
+ reiserfs_cache_bitmap_metadata(sb, bh, info);
+ }
+
+ return bh;
+}
+
+int reiserfs_init_bitmap_cache(struct super_block *sb)
+{
+ struct reiserfs_bitmap_info *bitmap;
+ unsigned int bmap_nr = reiserfs_bmap_count(sb);
+
+ bitmap = vmalloc(sizeof(*bitmap) * bmap_nr);
+ if (bitmap == NULL)
+ return -ENOMEM;
+
+ memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr);
+
+ SB_AP_BITMAP(sb) = bitmap;
+
+ return 0;
+}
+
+void reiserfs_free_bitmap_cache(struct super_block *sb)
+{
+ if (SB_AP_BITMAP(sb)) {
+ vfree(SB_AP_BITMAP(sb));
+ SB_AP_BITMAP(sb) = NULL;
+ }
+}