bitmap.c

嵌入式系统设计与实例开发实验教材二源码 多线程应用程序设计 串行端口程序设计 AD接口实验 CAN总线通信实验 GPS通信实验 Linux内核移植与编译实验 IC卡读写实验 SD驱动使

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

#include <linux/config.h>
#include <linux/sched.h>
#include <linux/reiserfs_fs.h>
#include <linux/locks.h>
#include <asm/bitops.h>
#include <linux/list.h>

#ifdef CONFIG_REISERFS_CHECK

/* this is a safety check to make sure
** blocks are reused properly.  used for debugging only.
**
** this checks, that block can be reused, and it has correct state
**   (free or busy) 
*/
int is_reusable (struct super_block * s, unsigned long block, int bit_value)
{
    int i, j;
  
    if (block == 0 || block >= SB_BLOCK_COUNT (s)) {
	reiserfs_warning ("vs-4010: is_reusable: block number is out of range %lu (%u)\n",
			  block, SB_BLOCK_COUNT (s));
	return 0;
    }

    /* it can't be one of the bitmap blocks */
    for (i = 0; i < SB_BMAP_NR (s); i ++)
	if (block == SB_AP_BITMAP (s)[i]->b_blocknr) {
	    reiserfs_warning ("vs: 4020: is_reusable: "
			      "bitmap block %lu(%u) can't be freed or reused\n",
			      block, SB_BMAP_NR (s));
	    return 0;
	}
  
    i = block / (s->s_blocksize << 3);
    if (i >= SB_BMAP_NR (s)) {
	reiserfs_warning ("vs-4030: is_reusable: there is no so many bitmap blocks: "
			  "block=%lu, bitmap_nr=%d\n", block, i);
	return 0;
    }

    j = block % (s->s_blocksize << 3);
    if ((bit_value == 0 && 
         reiserfs_test_le_bit(j, SB_AP_BITMAP(s)[i]->b_data)) ||
	(bit_value == 1 && 
	 reiserfs_test_le_bit(j, SB_AP_BITMAP (s)[i]->b_data) == 0)) {
	reiserfs_warning ("vs-4040: is_reusable: corresponding bit of block %lu does not "
			  "match required value (i==%d, j==%d) test_bit==%d\n",
		block, i, j, reiserfs_test_le_bit (j, SB_AP_BITMAP (s)[i]->b_data));
	return 0;
    }

    if (bit_value == 0 && block == SB_ROOT_BLOCK (s)) {
	reiserfs_warning ("vs-4050: is_reusable: this is root block (%u), "
			  "it must be busy", SB_ROOT_BLOCK (s));
	return 0;
    }

    return 1;
}




#endif /* CONFIG_REISERFS_CHECK */

/* get address of corresponding bit (bitmap block number and offset in it) */
static inline void get_bit_address (struct super_block * s, unsigned long block, int * bmap_nr, 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 << 3);
                                /* Within that bitmap block it is located at bit offset *offset. */
    *offset = block % (s->s_blocksize << 3);
    return;
}


/* There would be a modest performance benefit if we write a version
   to free a list of blocks at once. -Hans */
				/* I wonder if it would be less modest
                                   now that we use journaling. -Hans */
static void _reiserfs_free_block (struct reiserfs_transaction_handle *th, unsigned long block)
{
    struct super_block * s = th->t_super;
    struct reiserfs_super_block * rs;
    struct buffer_head * sbh;
    struct buffer_head ** apbh;
    int nr, offset;

  PROC_INFO_INC( s, free_block );

  rs = SB_DISK_SUPER_BLOCK (s);
  sbh = SB_BUFFER_WITH_SB (s);
  apbh = SB_AP_BITMAP (s);

  get_bit_address (s, block, &nr, &offset);

  if (nr >= sb_bmap_nr (rs)) {
	  reiserfs_warning ("vs-4075: reiserfs_free_block: "
			    "block %lu is out of range on %s\n", 
			    block, bdevname(s->s_dev));
	  return;
  }

  reiserfs_prepare_for_journal(s, apbh[nr], 1 ) ;

  /* clear bit for the given block in bit map */
  if (!reiserfs_test_and_clear_le_bit (offset, apbh[nr]->b_data)) {
      reiserfs_warning ("vs-4080: reiserfs_free_block: "
			"free_block (%04x:%lu)[dev:blocknr]: bit already cleared\n", 
	    s->s_dev, block);
  }
  journal_mark_dirty (th, s, apbh[nr]);

  reiserfs_prepare_for_journal(s, sbh, 1) ;
  /* update super block */
  set_sb_free_blocks( rs, sb_free_blocks(rs) + 1 );

  journal_mark_dirty (th, s, sbh);
  s->s_dirt = 1;
}

void reiserfs_free_block (struct reiserfs_transaction_handle *th, 
                          unsigned long block) {
    struct super_block * s = th->t_super;

    RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
    RFALSE(is_reusable (s, block, 1) == 0, "vs-4071: can not free such block");
    /* mark it before we clear it, just in case */
    journal_mark_freed(th, s, block) ;
    _reiserfs_free_block(th, block) ;
}

/* preallocated blocks don't need to be run through journal_mark_freed */
void reiserfs_free_prealloc_block (struct reiserfs_transaction_handle *th, 
                          unsigned long block) {
    struct super_block * s = th->t_super;

    RFALSE(!s, "vs-4060: trying to free block on nonexistent device");
    RFALSE(is_reusable (s, block, 1) == 0, "vs-4070: can not free such block");
    _reiserfs_free_block(th, block) ;
}

/* beginning from offset-th bit in bmap_nr-th bitmap block,
   find_forward finds the closest zero bit. It returns 1 and zero
   bit address (bitmap, offset) if zero bit found or 0 if there is no
   zero bit in the forward direction */
/* The function is NOT SCHEDULE-SAFE! */
static int find_forward (struct super_block * s, int * bmap_nr, int * offset, int for_unformatted)
{
  int i, j;
  struct buffer_head * bh;
  unsigned long block_to_try = 0;
  unsigned long next_block_to_try = 0 ;

  PROC_INFO_INC( s, find_forward.call );

  for (i = *bmap_nr; i < SB_BMAP_NR (s); i ++, *offset = 0, 
	       PROC_INFO_INC( s, find_forward.bmap )) {
    /* get corresponding bitmap block */
    bh = SB_AP_BITMAP (s)[i];
    if (buffer_locked (bh)) {
	PROC_INFO_INC( s, find_forward.wait );
        __wait_on_buffer (bh);
    }
retry:
    j = reiserfs_find_next_zero_le_bit ((unsigned long *)bh->b_data, 
                                         s->s_blocksize << 3, *offset);

    /* wow, this really needs to be redone.  We can't allocate a block if
    ** it is in the journal somehow.  reiserfs_in_journal makes a suggestion
    ** for a good block if the one you ask for is in the journal.  Note,
    ** reiserfs_in_journal might reject the block it suggests.  The big
    ** gain from the suggestion is when a big file has been deleted, and
    ** many blocks show free in the real bitmap, but are all not free
    ** in the journal list bitmaps.
    **
    ** this whole system sucks.  The bitmaps should reflect exactly what
    ** can and can't be allocated, and the journal should update them as
    ** it goes.  TODO.
    */
    if (j < (s->s_blocksize << 3)) {
      block_to_try = (i * (s->s_blocksize << 3)) + j; 

      /* the block is not in the journal, we can proceed */
      if (!(reiserfs_in_journal(s, s->s_dev, block_to_try, s->s_blocksize, for_unformatted, &next_block_to_try))) {
	*bmap_nr = i;
	*offset = j;
	return 1;
      } 
      /* the block is in the journal */
      else if ((j+1) < (s->s_blocksize << 3)) { /* try again */
	/* reiserfs_in_journal suggested a new block to try */
	if (next_block_to_try > 0) {
	  int new_i ;
	  get_bit_address (s, next_block_to_try, &new_i, offset);

	  PROC_INFO_INC( s, find_forward.in_journal_hint );

	  /* block is not in this bitmap. reset i and continue
	  ** we only reset i if new_i is in a later bitmap.
	  */
	  if (new_i > i) {
	    i = (new_i - 1 ); /* i gets incremented by the for loop */
	    PROC_INFO_INC( s, find_forward.in_journal_out );
	    continue ;
	  }
	} else {
	  /* no suggestion was made, just try the next block */
	  *offset = j+1 ;
	}
	PROC_INFO_INC( s, find_forward.retry );
	goto retry ;
      }
    }
  }
    /* zero bit not found */
    return 0;
}

/* return 0 if no free blocks, else return 1 */
/* The function is NOT SCHEDULE-SAFE!  
** because the bitmap block we want to change could be locked, and on its
** way to the disk when we want to read it, and because of the 
** flush_async_commits.  Per bitmap block locks won't help much, and 
** really aren't needed, as we retry later on if we try to set the bit
** and it is already set.
*/
static int find_zero_bit_in_bitmap (struct super_block * s, 
                                    unsigned long search_start, 
				    int * bmap_nr, int * offset, 
				    int for_unformatted)
{
  int retry_count = 0 ;
  /* get bit location (bitmap number and bit offset) of search_start block */
  get_bit_address (s, search_start, bmap_nr, offset);

    /* note that we search forward in the bitmap, benchmarks have shown that it is better to allocate in increasing
       sequence, which is probably due to the disk spinning in the forward direction.. */
    if (find_forward (s, bmap_nr, offset, for_unformatted) == 0) {
      /* there wasn't a free block with number greater than our
         starting point, so we are going to go to the beginning of the disk */

retry:
      search_start = 0; /* caller will reset search_start for itself also. */
      get_bit_address (s, search_start, bmap_nr, offset);
      if (find_forward (s, bmap_nr,offset,for_unformatted) == 0) {
	if (for_unformatted) {	/* why only unformatted nodes? -Hans */
	  if (retry_count == 0) {
	    /* we've got a chance that flushing async commits will free up
	    ** some space.  Sync then retry
	    */
	    flush_async_commits(s) ;
	    retry_count++ ;
	    goto retry ;
	  } else if (retry_count > 0) {
	    /* nothing more we can do.  Make the others wait, flush
	    ** all log blocks to disk, and flush to their home locations.
	    ** this will free up any blocks held by the journal
	    */
	    SB_JOURNAL(s)->j_must_wait = 1 ;
	  }
	}
        return 0;
      }
    }
  return 1;
}

/* get amount_needed free block numbers from scanning the bitmap of
   free/used blocks.
   
   Optimize layout by trying to find them starting from search_start
   and moving in increasing blocknr direction.  (This was found to be
   faster than using a bi-directional elevator_direction, in part
   because of disk spin direction, in part because by the time one
   reaches the end of the disk the beginning of the disk is the least
   congested).

   search_start is the block number of the left
   semantic neighbor of the node we create.

   return CARRY_ON if everything is ok
   return NO_DISK_SPACE if out of disk space
   return NO_MORE_UNUSED_CONTIGUOUS_BLOCKS if the block we found is not contiguous to the last one
   
   return block numbers found, in the array free_blocknrs.  assumes
   that any non-zero entries already present in the array are valid.
   This feature is perhaps convenient coding when one might not have
   used all blocknrs from the last time one called this function, or
   perhaps it is an archaism from the days of schedule tracking, one
   of us ought to reread the code that calls this, and analyze whether
   it is still the right way to code it.

   spare space is used only when priority is set to 1. reiserfsck has
   its own reiserfs_new_blocknrs, which can use reserved space

   exactly what reserved space?  the SPARE_SPACE?  if so, please comment reiserfs.h.

   Give example of who uses spare space, and say that it is a deadlock
   avoidance mechanism.  -Hans */

/* This function is NOT SCHEDULE-SAFE! */

static int do_reiserfs_new_blocknrs (struct reiserfs_transaction_handle *th,
                                     unsigned long * free_blocknrs, 
				     unsigned long search_start, 
				     int amount_needed, int priority, 
				     int for_unformatted,
				     int for_prealloc)
{
  struct super_block * s = th->t_super;
  int i, j;
  unsigned long * block_list_start = free_blocknrs;
  int init_amount_needed = amount_needed;
  unsigned long new_block = 0 ; 

    if (SB_FREE_BLOCKS (s) < SPARE_SPACE && !priority)
	/* we can answer NO_DISK_SPACE being asked for new block with
	   priority 0 */
	return NO_DISK_SPACE;

  RFALSE( !s, "vs-4090: trying to get new block from nonexistent device");
  RFALSE( search_start == MAX_B_NUM,
	  "vs-4100: we are optimizing location based on "
	  "the bogus location of a temp buffer (%lu).", search_start);
  RFALSE( amount_needed < 1 || amount_needed > 2,
	  "vs-4110: amount_needed parameter incorrect (%d)", amount_needed);

  /* We continue the while loop if another process snatches our found
   * free block from us after we find it but before we successfully
   * mark it as in use */

  while (amount_needed--) {
    /* skip over any blocknrs already gotten last time. */
    if (*(free_blocknrs) != 0) {
      RFALSE( is_reusable (s, *free_blocknrs, 1) == 0, 
	      "vs-4120: bad blocknr on free_blocknrs list");
      free_blocknrs++;
      continue;
    }
    /* look for zero bits in bitmap */
    if (find_zero_bit_in_bitmap(s,search_start, &i, &j,for_unformatted) == 0) {
      if (find_zero_bit_in_bitmap(s,search_start,&i,&j, for_unformatted) == 0) {
				/* recode without the goto and without
				   the if.  It will require a
				   duplicate for.  This is worth the
				   code clarity.  Your way was
				   admirable, and just a bit too
				   clever in saving instructions.:-)
				   I'd say create a new function, but
				   that would slow things also, yes?