lbalance.c

《嵌入式系统设计与实例开发实验教材二源码》Linux内核移植与编译实验

    blkh = B_BLK_HEAD(bh);
    nr = blkh_nr_item(blkh);
    free_space = blkh_free_space(blkh);


    /* check free space */
    RFALSE( free_space < paste_size,
            "vs-10175: not enough free space: needed %d, available %d",
            paste_size, free_space);

#ifdef CONFIG_REISERFS_CHECK
    if (zeros_number > paste_size) {
	print_cur_tb ("10177");
	reiserfs_panic ( 0, "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
                         zeros_number, paste_size);
    }
#endif /* CONFIG_REISERFS_CHECK */


    /* item to be appended */
    ih = B_N_PITEM_HEAD(bh, affected_item_num);

    last_loc = ih_location( &(ih[nr - affected_item_num - 1]) );
    unmoved_loc = affected_item_num ? ih_location( ih-1 ) : bh->b_size;

    /* prepare space */
    memmove (bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
	     unmoved_loc - last_loc);


    /* change locations */
    for (i = affected_item_num; i < nr; i ++)
	put_ih_location( &(ih[i-affected_item_num]),
                    ih_location( &(ih[i-affected_item_num])) - paste_size );

    if ( body ) {
	if (!is_direntry_le_ih (ih)) {
	    if (!pos_in_item) {
		/* shift data to right */
		memmove (bh->b_data + ih_location(ih) + paste_size, 
			 bh->b_data + ih_location(ih), ih_item_len(ih));
		/* paste data in the head of item */
		memset (bh->b_data + ih_location(ih), 0, zeros_number);
		memcpy (bh->b_data + ih_location(ih) + zeros_number, body, paste_size - zeros_number);
	    } else {
		memset (bh->b_data + unmoved_loc - paste_size, 0, zeros_number);
		memcpy (bh->b_data + unmoved_loc - paste_size + zeros_number, body, paste_size - zeros_number);
	    }
	}
    }
    else
	memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);

    put_ih_item_len( ih, ih_item_len(ih) + paste_size );

    /* change free space */
    set_blkh_free_space( blkh, free_space - paste_size );

    do_balance_mark_leaf_dirty (bi->tb, bh, 0);

    if (bi->bi_parent) { 
	struct disk_child *t_dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
	put_dc_size( t_dc, dc_size(t_dc) + paste_size );
	do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
    }
}


/* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
   does not have free space, so it moves DEHs and remaining records as
   necessary. Return value is size of removed part of directory item
   in bytes. */
static int	leaf_cut_entries (
				struct buffer_head * bh,
				struct item_head * ih, 
				int from, 
				int del_count
			)
{
  char * item;
  struct reiserfs_de_head * deh;
  int prev_record_offset;	/* offset of record, that is (from-1)th */
  char * prev_record;		/* */
  int cut_records_len;		/* length of all removed records */
  int i;


  /* make sure, that item is directory and there are enough entries to
     remove */
  RFALSE( !is_direntry_le_ih (ih), "10180: item is not directory item");
  RFALSE( I_ENTRY_COUNT(ih) < from + del_count,
	  "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
	  I_ENTRY_COUNT(ih), from, del_count);

  if (del_count == 0)
    return 0;

  /* first byte of item */
  item = bh->b_data + ih_location(ih);

  /* entry head array */
  deh = B_I_DEH (bh, ih);

  /* first byte of remaining entries, those are BEFORE cut entries
     (prev_record) and length of all removed records (cut_records_len) */
  prev_record_offset = (from ? deh_location( &(deh[from - 1])) : ih_item_len(ih));
  cut_records_len = prev_record_offset/*from_record*/ -
                                deh_location( &(deh[from + del_count - 1]));
  prev_record = item + prev_record_offset;


  /* adjust locations of remaining entries */
  for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i --)
    put_deh_location( &(deh[i]),
                        deh_location( &deh[i] ) - (DEH_SIZE * del_count ) );

  for (i = 0; i < from; i ++)
    put_deh_location( &(deh[i]),
        deh_location( &deh[i] ) - (DEH_SIZE * del_count + cut_records_len) );

  put_ih_entry_count( ih, ih_entry_count(ih) - del_count );

  /* shift entry head array and entries those are AFTER removed entries */
  memmove ((char *)(deh + from),
	   deh + from + del_count, 
	   prev_record - cut_records_len - (char *)(deh + from + del_count));
  
  /* shift records, those are BEFORE removed entries */
  memmove (prev_record - cut_records_len - DEH_SIZE * del_count,
	   prev_record, item + ih_item_len(ih) - prev_record);

  return DEH_SIZE * del_count + cut_records_len;
}


/*  when cut item is part of regular file
        pos_in_item - first byte that must be cut
        cut_size - number of bytes to be cut beginning from pos_in_item
 
   when cut item is part of directory
        pos_in_item - number of first deleted entry
        cut_size - count of deleted entries
    */
void leaf_cut_from_buffer (struct buffer_info * bi, int cut_item_num,
			   int pos_in_item, int cut_size)
{
    int nr;
    struct buffer_head * bh = bi->bi_bh;
    struct block_head * blkh;
    struct item_head * ih;
    int last_loc, unmoved_loc;
    int i;

    blkh = B_BLK_HEAD(bh);
    nr = blkh_nr_item(blkh);

    /* item head of truncated item */
    ih = B_N_PITEM_HEAD (bh, cut_item_num);

    if (is_direntry_le_ih (ih)) {
        /* first cut entry ()*/
        cut_size = leaf_cut_entries (bh, ih, pos_in_item, cut_size);
        if (pos_in_item == 0) {
	        /* change key */
            RFALSE( cut_item_num,
                    "when 0-th enrty of item is cut, that item must be first in the node, not %d-th", cut_item_num);
            /* change item key by key of first entry in the item */
	    set_le_ih_k_offset (ih, deh_offset(B_I_DEH (bh, ih)));
            /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE);*/
	    }
    } else {
        /* item is direct or indirect */
        RFALSE( is_statdata_le_ih (ih), "10195: item is stat data");
        RFALSE( pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
                "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
                ( long unsigned ) pos_in_item, ( long unsigned ) cut_size, 
		( long unsigned ) ih_item_len (ih));

        /* shift item body to left if cut is from the head of item */
        if (pos_in_item == 0) {
            memmove( bh->b_data + ih_location(ih),
		     bh->b_data + ih_location(ih) + cut_size,
		     ih_item_len(ih) - cut_size);
	    
            /* change key of item */
            if (is_direct_le_ih (ih))
		set_le_ih_k_offset (ih, le_ih_k_offset (ih) + cut_size);
            else {
		set_le_ih_k_offset (ih, le_ih_k_offset (ih) + (cut_size / UNFM_P_SIZE) * bh->b_size);
                RFALSE( ih_item_len(ih) == cut_size && get_ih_free_space (ih),
                        "10205: invalid ih_free_space (%h)", ih);
	        }
	    }
    }
  

    /* location of the last item */
    last_loc = ih_location( &(ih[nr - cut_item_num - 1]) );

    /* location of the item, which is remaining at the same place */
    unmoved_loc = cut_item_num ? ih_location(ih-1) : bh->b_size;


    /* shift */
    memmove (bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
	       unmoved_loc - last_loc - cut_size);

    /* change item length */
    put_ih_item_len( ih, ih_item_len(ih) - cut_size );
  
    if (is_indirect_le_ih (ih)) {
        if (pos_in_item)
            set_ih_free_space (ih, 0);
    }

    /* change locations */
    for (i = cut_item_num; i < nr; i ++)
    put_ih_location( &(ih[i-cut_item_num]), ih_location( &ih[i-cut_item_num]) + cut_size );

    /* size, free space */
    set_blkh_free_space( blkh, blkh_free_space(blkh) + cut_size );

    do_balance_mark_leaf_dirty (bi->tb, bh, 0);
    
    if (bi->bi_parent) { 
      struct disk_child *t_dc;
      t_dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
      put_dc_size( t_dc, dc_size(t_dc) - cut_size );
      do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
    }
}


/* delete del_num items from buffer starting from the first'th item */
static void leaf_delete_items_entirely (struct buffer_info * bi,
					int first, int del_num)
{
    struct buffer_head * bh = bi->bi_bh;
    int nr;
    int i, j;
    int last_loc, last_removed_loc;
    struct block_head * blkh;
    struct item_head * ih;

  RFALSE( bh == NULL, "10210: buffer is 0");
  RFALSE( del_num < 0, "10215: del_num less than 0 (%d)", del_num);

  if (del_num == 0)
    return;

  blkh = B_BLK_HEAD(bh);
  nr = blkh_nr_item(blkh);

  RFALSE( first < 0 || first + del_num > nr,
          "10220: first=%d, number=%d, there is %d items", first, del_num, nr);

  if (first == 0 && del_num == nr) {
    /* this does not work */
    make_empty_node (bi);
    
    do_balance_mark_leaf_dirty (bi->tb, bh, 0);
    return;
  }

  ih = B_N_PITEM_HEAD (bh, first);
  
  /* location of unmovable item */
  j = (first == 0) ? bh->b_size : ih_location(ih-1);
      
  /* delete items */
  last_loc = ih_location( &(ih[nr-1-first]) );
  last_removed_loc = ih_location( &(ih[del_num-1]) );

  memmove (bh->b_data + last_loc + j - last_removed_loc,
	   bh->b_data + last_loc, last_removed_loc - last_loc);
  
  /* delete item headers */
  memmove (ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
  
  /* change item location */
  for (i = first; i < nr - del_num; i ++)
    put_ih_location( &(ih[i-first]), ih_location( &(ih[i-first]) ) + (j - last_removed_loc) );

  /* sizes, item number */
  set_blkh_nr_item( blkh, blkh_nr_item(blkh) - del_num );
  set_blkh_free_space( blkh, blkh_free_space(blkh) + (j - last_removed_loc + IH_SIZE * del_num) );

  do_balance_mark_leaf_dirty (bi->tb, bh, 0);
  
  if (bi->bi_parent) {
    struct disk_child *t_dc = B_N_CHILD (bi->bi_parent, bi->bi_position);
    put_dc_size( t_dc, dc_size(t_dc) -
				(j - last_removed_loc + IH_SIZE * del_num));
    do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
  }
}





/* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
void    leaf_paste_entries (
			struct buffer_head * bh,
			int item_num,
			int before,
			int new_entry_count,
			struct reiserfs_de_head * new_dehs,
			const char * records,
			int paste_size
		)
{
    struct item_head * ih;
    char * item;
    struct reiserfs_de_head * deh;
    char * insert_point;
    int i, old_entry_num;

    if (new_entry_count == 0)
        return;

    ih = B_N_PITEM_HEAD(bh, item_num);

  /* make sure, that item is directory, and there are enough records in it */
  RFALSE( !is_direntry_le_ih (ih), "10225: item is not directory item");
  RFALSE( I_ENTRY_COUNT (ih) < before,
	  "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
	  I_ENTRY_COUNT (ih), before);


  /* first byte of dest item */
  item = bh->b_data + ih_location(ih);

  /* entry head array */
  deh = B_I_DEH (bh, ih);

  /* new records will be pasted at this point */
  insert_point = item + (before ? deh_location( &(deh[before - 1])) : (ih_item_len(ih) - paste_size));

  /* adjust locations of records that will be AFTER new records */
  for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i --)
    put_deh_location( &(deh[i]),
                deh_location(&(deh[i])) + (DEH_SIZE * new_entry_count )); 

  /* adjust locations of records that will be BEFORE new records */
  for (i = 0; i < before; i ++)
    put_deh_location( &(deh[i]), deh_location(&(deh[i])) + paste_size );

  old_entry_num = I_ENTRY_COUNT(ih);
  put_ih_entry_count( ih, ih_entry_count(ih) + new_entry_count );

  /* prepare space for pasted records */
  memmove (insert_point + paste_size, insert_point, item + (ih_item_len(ih) - paste_size) - insert_point);

  /* copy new records */
  memcpy (insert_point + DEH_SIZE * new_entry_count, records,
		   paste_size - DEH_SIZE * new_entry_count);
  
  /* prepare space for new entry heads */
  deh += before;
  memmove ((char *)(deh + new_entry_count), deh, insert_point - (char *)deh);

  /* copy new entry heads */
  deh = (struct reiserfs_de_head *)((char *)deh);
  memcpy (deh, new_dehs, DEH_SIZE * new_entry_count);

  /* set locations of new records */
  for (i = 0; i < new_entry_count; i ++)
  {
    put_deh_location( &(deh[i]),
        deh_location( &(deh[i] )) +
        (- deh_location( &(new_dehs[new_entry_count - 1])) +
        insert_point + DEH_SIZE * new_entry_count - item));
  }


  /* change item key if neccessary (when we paste before 0-th entry */
  if (!before)
    {
	set_le_ih_k_offset (ih, deh_offset(new_dehs));
/*      memcpy (&ih->ih_key.k_offset, 
		       &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
    }

#ifdef CONFIG_REISERFS_CHECK
  {
    int prev, next;
    /* check record locations */
    deh = B_I_DEH (bh, ih);
    for (i = 0; i < I_ENTRY_COUNT(ih); i ++) {
      next = (i < I_ENTRY_COUNT(ih) - 1) ? deh_location( &(deh[i + 1])) : 0;
      prev = (i != 0) ? deh_location( &(deh[i - 1]) ) : 0;
      
      if (prev && prev <= deh_location( &(deh[i])))
	reiserfs_warning ("vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)\n", 
			  ih, deh + i - 1, i, deh + i);
      if (next && next >= deh_location( &(deh[i])))
	reiserfs_warning ("vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)\n",
			  ih, i, deh + i, deh + i + 1);
    }
  }
#endif

}