/*
   * 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) {

  		b_blocknr_t block_to_free;
  
  		/*
  		 * reiserfs_free_prealloc_block can drop the write lock,
  		 * which could allow another caller to free the same block.
  		 * We can protect against it by modifying the prealloc
  		 * state before calling it.
  		 */
  		block_to_free = ei->i_prealloc_block++;

  		ei->i_prealloc_count--;

  		reiserfs_free_prealloc_block(th, inode, block_to_free);

  		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]
  ", 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) && !IS_PRIVATE(hint->inode)

  		    && 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;
  	}
  }