lbalance.c

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

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

#include <linux/config.h>
#include <asm/uaccess.h>
#include <linux/string.h>
#include <linux/sched.h>
#include <linux/reiserfs_fs.h>

/* these are used in do_balance.c */

/* leaf_move_items
   leaf_shift_left
   leaf_shift_right
   leaf_delete_items
   leaf_insert_into_buf
   leaf_paste_in_buffer
   leaf_cut_from_buffer
   leaf_paste_entries
   */


/* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
static void leaf_copy_dir_entries (struct buffer_info * dest_bi, struct buffer_head * source, 
				   int last_first, int item_num, int from, int copy_count)
{
    struct buffer_head * dest = dest_bi->bi_bh;
    int item_num_in_dest;		/* either the number of target item,
					   or if we must create a new item,
					   the number of the item we will
					   create it next to */
    struct item_head * ih;
    struct reiserfs_de_head * deh;
    int copy_records_len;			/* length of all records in item to be copied */
    char * records;

    ih = B_N_PITEM_HEAD (source, item_num);

    RFALSE( !is_direntry_le_ih (ih), "vs-10000: item must be directory item");

    /* length of all record to be copied and first byte of the last of them */
    deh = B_I_DEH (source, ih);
    if (copy_count) {
	copy_records_len = (from ? deh_location( &(deh[from - 1]) ) :
            ih_item_len(ih)) - deh_location( &(deh[from + copy_count - 1]));
	records = source->b_data + ih_location(ih) +
                                deh_location( &(deh[from + copy_count - 1]));
    } else {
	copy_records_len = 0;
	records = 0;
    }

    /* when copy last to first, dest buffer can contain 0 items */
    item_num_in_dest = (last_first == LAST_TO_FIRST) ? (( B_NR_ITEMS(dest) ) ? 0 : -1) : (B_NR_ITEMS(dest) - 1);

    /* if there are no items in dest or the first/last item in dest is not item of the same directory */
    if ( (item_num_in_dest == - 1) ||
	(last_first == FIRST_TO_LAST && le_ih_k_offset (ih) == DOT_OFFSET) ||
	    (last_first == LAST_TO_FIRST && comp_short_le_keys/*COMP_SHORT_KEYS*/ (&ih->ih_key, B_N_PKEY (dest, item_num_in_dest)))) {
	/* create new item in dest */
	struct item_head new_ih;

	/* form item header */
	memcpy (&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
	put_ih_version( &new_ih, KEY_FORMAT_3_5 );
	/* calculate item len */
	put_ih_item_len( &new_ih, DEH_SIZE * copy_count + copy_records_len );
	put_ih_entry_count( &new_ih, 0 );
    
	if (last_first == LAST_TO_FIRST) {
	    /* form key by the following way */
	    if (from < I_ENTRY_COUNT(ih)) {
		set_le_ih_k_offset( &new_ih, deh_offset( &(deh[from]) ) );
		/*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE);*/
	    } else {
		/* no entries will be copied to this item in this function */
		set_le_ih_k_offset (&new_ih, U32_MAX);
		/* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
	    }
	    set_le_key_k_type (KEY_FORMAT_3_5, &(new_ih.ih_key), TYPE_DIRENTRY);
	}
    
	/* insert item into dest buffer */
	leaf_insert_into_buf (dest_bi, (last_first == LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), &new_ih, NULL, 0);
    } else {
	/* prepare space for entries */
	leaf_paste_in_buffer (dest_bi, (last_first==FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0, MAX_US_INT,
			      DEH_SIZE * copy_count + copy_records_len, records, 0
	    );
    }
  
    item_num_in_dest = (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest)-1) : 0;
    
    leaf_paste_entries (dest_bi->bi_bh, item_num_in_dest,
			(last_first == FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD (dest, item_num_in_dest)) : 0,
			copy_count, deh + from, records,
			DEH_SIZE * copy_count + copy_records_len
	);
}


/* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or 
   part of it or nothing (see the return 0 below) from SOURCE to the end 
   (if last_first) or beginning (!last_first) of the DEST */
/* returns 1 if anything was copied, else 0 */
static int leaf_copy_boundary_item (struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
				    int bytes_or_entries)
{
  struct buffer_head * dest = dest_bi->bi_bh;
  int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
  struct item_head * ih;
  struct item_head * dih;
  
  dest_nr_item = B_NR_ITEMS(dest);
  
  if ( last_first == FIRST_TO_LAST ) {
    /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
       or of different types ) then there is no need to treat this item differently from the other items
       that we copy, so we return */
    ih = B_N_PITEM_HEAD (src, 0);
    dih = B_N_PITEM_HEAD (dest, dest_nr_item - 1);
    if (!dest_nr_item || (!op_is_left_mergeable (&(ih->ih_key), src->b_size)))
      /* there is nothing to merge */
      return 0;
      
    RFALSE( ! ih_item_len(ih), "vs-10010: item can not have empty length");
      
    if ( is_direntry_le_ih (ih) ) {
      if ( bytes_or_entries == -1 )
	/* copy all entries to dest */
	bytes_or_entries = ih_entry_count(ih);
      leaf_copy_dir_entries (dest_bi, src, FIRST_TO_LAST, 0, 0, bytes_or_entries);
      return 1;
    }
      
    /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
       part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
       */
    if ( bytes_or_entries == -1 )
      bytes_or_entries = ih_item_len(ih);

#ifdef CONFIG_REISERFS_CHECK
    else {
      if (bytes_or_entries == ih_item_len(ih) && is_indirect_le_ih(ih))
	if (get_ih_free_space (ih))
	  reiserfs_panic (0, "vs-10020: leaf_copy_boundary_item: "
			  "last unformatted node must be filled entirely (%h)",
			  ih);
    }
#endif
      
    /* merge first item (or its part) of src buffer with the last
       item of dest buffer. Both are of the same file */
    leaf_paste_in_buffer (dest_bi,
			  dest_nr_item - 1, ih_item_len(dih), bytes_or_entries, B_I_PITEM(src,ih), 0
			  );
      
    if (is_indirect_le_ih (dih)) {
      RFALSE( get_ih_free_space (dih),
              "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
              ih);
      if (bytes_or_entries == ih_item_len(ih))
	set_ih_free_space (dih, get_ih_free_space (ih));
    }
    
    return 1;
  }
  

  /* copy boundary item to right (last_first == LAST_TO_FIRST) */

  /* ( DEST is empty or last item of SOURCE and first item of DEST
     are the items of different object or of different types )
     */
  src_nr_item = B_NR_ITEMS (src);
  ih = B_N_PITEM_HEAD (src, src_nr_item - 1);
  dih = B_N_PITEM_HEAD (dest, 0);

  if (!dest_nr_item || !op_is_left_mergeable (&(dih->ih_key), src->b_size))
    return 0;
  
  if ( is_direntry_le_ih (ih)) {
    if ( bytes_or_entries == -1 )
      /* bytes_or_entries = entries number in last item body of SOURCE */
      bytes_or_entries = ih_entry_count(ih);
    
    leaf_copy_dir_entries (dest_bi, src, LAST_TO_FIRST, src_nr_item - 1, ih_entry_count(ih) - bytes_or_entries, bytes_or_entries);
    return 1;
  }

  /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
     part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
     don't create new item header
     */
  
  RFALSE( is_indirect_le_ih(ih) && get_ih_free_space (ih),
          "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
		    ih);

  if ( bytes_or_entries == -1 ) {
    /* bytes_or_entries = length of last item body of SOURCE */
    bytes_or_entries = ih_item_len(ih);

    RFALSE( le_ih_k_offset (dih) !=
            le_ih_k_offset (ih) + op_bytes_number (ih, src->b_size),
            "vs-10050: items %h and %h do not match", ih, dih);

    /* change first item key of the DEST */
    set_le_ih_k_offset (dih, le_ih_k_offset (ih));

    /* item becomes non-mergeable */
    /* or mergeable if left item was */
    set_le_ih_k_type (dih, le_ih_k_type (ih));
  } else {
    /* merge to right only part of item */
    RFALSE( ih_item_len(ih) <= bytes_or_entries,
            "vs-10060: no so much bytes %lu (needed %lu)",
            ( unsigned long )ih_item_len(ih), ( unsigned long )bytes_or_entries);
    
    /* change first item key of the DEST */
    if ( is_direct_le_ih (dih) ) {
      RFALSE( le_ih_k_offset (dih) <= (unsigned long)bytes_or_entries,
	      "vs-10070: dih %h, bytes_or_entries(%d)", dih, bytes_or_entries);
      set_le_ih_k_offset (dih, le_ih_k_offset (dih) - bytes_or_entries);
    } else {
      RFALSE( le_ih_k_offset (dih) <=
              (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
              "vs-10080: dih %h, bytes_or_entries(%d)",
              dih, (bytes_or_entries/UNFM_P_SIZE)*dest->b_size);
      set_le_ih_k_offset (dih, le_ih_k_offset (dih) - ((bytes_or_entries / UNFM_P_SIZE) * dest->b_size));
    }
  }
  
  leaf_paste_in_buffer (dest_bi, 0, 0, bytes_or_entries, B_I_PITEM(src,ih) + ih_item_len(ih) - bytes_or_entries, 0);
  return 1;
}


/* copy cpy_mun items from buffer src to buffer dest
 * last_first == FIRST_TO_LAST means, that we copy cpy_num  items beginning from first-th item in src to tail of dest
 * last_first == LAST_TO_FIRST means, that we copy cpy_num  items beginning from first-th item in src to head of dest
 */
static void leaf_copy_items_entirely (struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
				      int first, int cpy_num)
{
    struct buffer_head * dest;
    int nr, free_space;
    int dest_before;
    int last_loc, last_inserted_loc, location;
    int i, j;
    struct block_head * blkh;
    struct item_head * ih;

    RFALSE( last_first != LAST_TO_FIRST  && last_first != FIRST_TO_LAST,
	    "vs-10090: bad last_first parameter %d", last_first);
    RFALSE( B_NR_ITEMS (src) - first < cpy_num,
	    "vs-10100: too few items in source %d, required %d from %d",
	    B_NR_ITEMS(src), cpy_num, first);
    RFALSE( cpy_num < 0, "vs-10110: can not copy negative amount of items");
    RFALSE( ! dest_bi, "vs-10120: can not copy negative amount of items");

    dest = dest_bi->bi_bh;

    RFALSE( ! dest, "vs-10130: can not copy negative amount of items");

    if (cpy_num == 0)
	return;

    blkh = B_BLK_HEAD(dest);
    nr = blkh_nr_item( blkh );
    free_space = blkh_free_space(blkh);
  
    /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
    dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;

    /* location of head of first new item */
    ih = B_N_PITEM_HEAD (dest, dest_before);

    RFALSE( blkh_free_space(blkh) < cpy_num * IH_SIZE,
            "vs-10140: not enough free space for headers %d (needed %d)",
            B_FREE_SPACE (dest), cpy_num * IH_SIZE);

    /* prepare space for headers */
    memmove (ih + cpy_num, ih, (nr-dest_before) * IH_SIZE);

    /* copy item headers */
    memcpy (ih, B_N_PITEM_HEAD (src, first), cpy_num * IH_SIZE);

    free_space -= (IH_SIZE * cpy_num);
    set_blkh_free_space( blkh, free_space );

    /* location of unmovable item */
    j = location = (dest_before == 0) ? dest->b_size : ih_location(ih-1);
    for (i = dest_before; i < nr + cpy_num; i ++) {
        location -= ih_item_len( ih + i - dest_before );
        put_ih_location( ih + i - dest_before, location );
    }

    /* prepare space for items */
    last_loc = ih_location( &(ih[nr+cpy_num-1-dest_before]) );
    last_inserted_loc = ih_location( &(ih[cpy_num-1]) );

    /* check free space */
    RFALSE( free_space < j - last_inserted_loc,
	    "vs-10150: not enough free space for items %d (needed %d)",
            free_space, j - last_inserted_loc);

    memmove (dest->b_data + last_loc,
	     dest->b_data + last_loc + j - last_inserted_loc,
	     last_inserted_loc - last_loc);

    /* copy items */
    memcpy (dest->b_data + last_inserted_loc, B_N_PITEM(src,(first + cpy_num - 1)),
	    j - last_inserted_loc);

    /* sizes, item number */
    set_blkh_nr_item( blkh, nr + cpy_num );
    set_blkh_free_space( blkh, free_space - (j - last_inserted_loc) );

    do_balance_mark_leaf_dirty (dest_bi->tb, dest, 0);

    if (dest_bi->bi_parent) {
	struct disk_child *t_dc;
	t_dc = B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position);
	RFALSE( dc_block_number(t_dc) != dest->b_blocknr,
	        "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
                ( long unsigned ) dest->b_blocknr, 
		( long unsigned ) dc_block_number(t_dc));
	put_dc_size( t_dc, dc_size(t_dc) + (j - last_inserted_loc + IH_SIZE * cpy_num ) );
    
	do_balance_mark_internal_dirty (dest_bi->tb, dest_bi->bi_parent, 0);
    }
}


/* This function splits the (liquid) item into two items (useful when
   shifting part of an item into another node.) */
static void leaf_item_bottle (struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
			      int item_num, int cpy_bytes)
{
    struct buffer_head * dest = dest_bi->bi_bh;
    struct item_head * ih;
  
    RFALSE( cpy_bytes == -1, "vs-10170: bytes == - 1 means: do not split item");

    if ( last_first == FIRST_TO_LAST ) {
	/* if ( if item in position item_num in buffer SOURCE is directory item ) */
	if (is_direntry_le_ih (ih = B_N_PITEM_HEAD(src,item_num)))
	    leaf_copy_dir_entries (dest_bi, src, FIRST_TO_LAST, item_num, 0, cpy_bytes);
	else {
	    struct item_head n_ih;
      
	    /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST 
	       part defined by 'cpy_bytes'; create new item header; change old item_header (????);
	       n_ih = new item_header;
	    */
	    memcpy (&n_ih, ih, IH_SIZE);
	    put_ih_item_len( &n_ih, cpy_bytes );
	    if (is_indirect_le_ih (ih)) {
		RFALSE( cpy_bytes == ih_item_len(ih) && get_ih_free_space(ih),
		        "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
                        ( long unsigned ) get_ih_free_space (ih));
		set_ih_free_space (&n_ih, 0);
	    }

	    RFALSE( op_is_left_mergeable (&(ih->ih_key), src->b_size),
		    "vs-10190: bad mergeability of item %h", ih);
	    n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
	    leaf_insert_into_buf (dest_bi, B_NR_ITEMS(dest), &n_ih, B_N_PITEM (src, item_num), 0);
	}
    } else {
	/*  if ( if item in position item_num in buffer SOURCE is directory item ) */
	if (is_direntry_le_ih(ih = B_N_PITEM_HEAD (src, item_num)))
	    leaf_copy_dir_entries (dest_bi, src, LAST_TO_FIRST, item_num, I_ENTRY_COUNT(ih) - cpy_bytes, cpy_bytes);
	else {
	    struct item_head n_ih;
      
	    /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST 
	       part defined by 'cpy_bytes'; create new item header;
	       n_ih = new item_header;
	    */
	    memcpy (&n_ih, ih, SHORT_KEY_SIZE);

	    n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */

	    if (is_direct_le_ih (ih)) {
		set_le_ih_k_offset (&n_ih, le_ih_k_offset (ih) + ih_item_len(ih) - cpy_bytes);
		set_le_ih_k_type (&n_ih, TYPE_DIRECT);
		set_ih_free_space (&n_ih, MAX_US_INT);
	    } else {
		/* indirect item */
		RFALSE( !cpy_bytes && get_ih_free_space (ih),
		        "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
		set_le_ih_k_offset (&n_ih, le_ih_k_offset (ih) + (ih_item_len(ih) - cpy_bytes) / UNFM_P_SIZE * dest->b_size);
		set_le_ih_k_type (&n_ih, TYPE_INDIRECT);
		set_ih_free_space (&n_ih, get_ih_free_space (ih));
	    }
      
	    /* set item length */
	    put_ih_item_len( &n_ih, cpy_bytes );

	    n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */

	    leaf_insert_into_buf (dest_bi, 0, &n_ih, B_N_PITEM(src,item_num) + ih_item_len(ih) - cpy_bytes, 0);
	}
    }
}