reiserfs_fs.h

reiserfsprogs-3.6.19.tar.gz 源码 给有需要的人！

    unsigned short * vi_entry_sizes; /* array of entry lengths for directory item */
};

struct virtual_node
{
    char * vn_free_ptr;	 /* this is a pointer to the free space in the buffer */
    unsigned short vn_nr_item;	/* number of items in virtual node */
    short vn_size; /* size of node , that node would have if it has unlimited
		      size and no balancing is performed */
    short vn_mode;		/* mode of balancing (paste, insert, delete, cut) */
    short vn_affected_item_num; 
    short vn_pos_in_item;
    struct item_head * vn_ins_ih;	/* item header of inserted item, 0 for other modes */
    struct virtual_item * vn_vi;	/* array of items (including a new one, excluding item to be deleted) */
};


/***************************************************************************/
/*                  TREE BALANCE                                           */
/***************************************************************************/

/* This temporary structure is used in tree balance algorithms, and
   constructed as we go to the extent that its various parts are needed.  It
   contains arrays of nodes that can potentially be involved in the balancing
   of node S, and parameters that define how each of the nodes must be
   balanced.  Note that in these algorithms for balancing the worst case is to
   need to balance the current node S and the left and right neighbors and all
   of their parents plus create a new node.  We implement S1 balancing for the
   leaf nodes and S0 balancing for the internal nodes (S1 and S0 are defined
   in our papers.)*/

#define MAX_FREE_BLOCK 7	/* size of the array of buffers to free at end of do_balance */

/* maximum number of FEB blocknrs on a single level */
#define MAX_AMOUNT_NEEDED 2

/* someday somebody will prefix every field in this struct with tb_ */
struct tree_balance
{
    struct reiserfs_transaction_handle *transaction_handle ;
    reiserfs_filsys_t * tb_fs;
    struct path * tb_path;
    struct buffer_head * L[MAX_HEIGHT];        /* array of left neighbors of nodes in the path */
    struct buffer_head * R[MAX_HEIGHT];        /* array of right neighbors of nodes in the path*/
    struct buffer_head * FL[MAX_HEIGHT];       /* array of fathers of the left  neighbors      */
    struct buffer_head * FR[MAX_HEIGHT];       /* array of fathers of the right neighbors      */
    struct buffer_head * CFL[MAX_HEIGHT];      /* array of common parents of center node and its left neighbor  */
    struct buffer_head * CFR[MAX_HEIGHT];      /* array of common parents of center node and its right neighbor */
    
    /* array of blocknr's that are free and are the nearest to the left node that are usable
       for writing dirty formatted leaves, using the write_next_to algorithm. */
    /*unsigned long free_and_near[MAX_DIRTIABLE];*/
    
    struct buffer_head * FEB[MAX_FEB_SIZE]; /* array of empty buffers. Number of buffers in array equals
					       cur_blknum. */
    struct buffer_head * used[MAX_FEB_SIZE];
    short int lnum[MAX_HEIGHT];	/* array of number of items which must be shifted to the left in
				   order to balance the current node; for leaves includes item
				   that will be partially shifted; for internal nodes, it is
				   the number of child pointers rather than items. It includes
				   the new item being created.  For preserve_shifted() purposes
				   the code sometimes subtracts one from this number to get the
				   number of currently existing items being shifted, and even
				   more often for leaves it subtracts one to get the number of
				   wholly shifted items for other purposes. */
    short int rnum[MAX_HEIGHT];	/* substitute right for left in comment above */
    short int lkey[MAX_HEIGHT];               /* array indexed by height h mapping the key delimiting L[h] and
					       S[h] to its item number within the node CFL[h] */
    short int rkey[MAX_HEIGHT];               /* substitute r for l in comment above */
    short int insert_size[MAX_HEIGHT];        /* the number of bytes by we are trying to add or remove from
						 S[h]. A negative value means removing.  */
    short int blknum[MAX_HEIGHT];             /* number of nodes that will replace node S[h] after
						 balancing on the level h of the tree.  If 0 then S is
						 being deleted, if 1 then S is remaining and no new nodes
						 are being created, if 2 or 3 then 1 or 2 new nodes is
						 being created */
    
    /* fields that are used only for balancing leaves of the tree */
    short int cur_blknum;	/* number of empty blocks having been already allocated			*/
    short int s0num;             /* number of items that fall into left most  node when S[0] splits	*/
    short int s1num;             /* number of items that fall into first  new node when S[0] splits	*/
    short int s2num;             /* number of items that fall into second new node when S[0] splits	*/
    short int lbytes;            /* number of bytes which can flow to the left neighbor from the	left	*/
    /* most liquid item that cannot be shifted from S[0] entirely		*/
    /* if -1 then nothing will be partially shifted */
    short int rbytes;            /* number of bytes which will flow to the right neighbor from the right	*/
    /* most liquid item that cannot be shifted from S[0] entirely		*/
    /* if -1 then nothing will be partially shifted                           */
    short int s1bytes;		/* number of bytes which flow to the first  new node when S[0] splits	*/
            			/* note: if S[0] splits into 3 nodes, then items do not need to be cut	*/
    short int s2bytes;
    struct buffer_head * buf_to_free[MAX_FREE_BLOCK]; /* buffers which are to be freed after do_balance finishes by unfix_nodes */
    char * vn_buf;		/* kmalloced memory. Used to create
				   virtual node and keep map of
				   dirtied bitmap blocks */
    int vn_buf_size;		/* size of the vn_buf */
    struct virtual_node * tb_vn;	/* VN starts after bitmap of bitmap blocks */
} ;



/* These are modes of balancing */

/* When inserting an item. */
#define M_INSERT	'i'
/* When inserting into (directories only) or appending onto an already
   existant item. */
#define M_PASTE		'p'
/* When deleting an item. */
#define M_DELETE	'd'
/* When truncating an item or removing an entry from a (directory) item. */
#define M_CUT 		'c'

/* used when balancing on leaf level skipped (in reiserfsck) */
#define M_INTERNAL	'n'

/* When further balancing is not needed, then do_balance does not need
   to be called. */
#define M_SKIP_BALANCING 		's'
#define M_CONVERT	'v'

/* modes of leaf_move_items */
#define LEAF_FROM_S_TO_L 0
#define LEAF_FROM_S_TO_R 1
#define LEAF_FROM_R_TO_L 2
#define LEAF_FROM_L_TO_R 3
#define LEAF_FROM_S_TO_SNEW 4

#define FIRST_TO_LAST 0
#define LAST_TO_FIRST 1

/* used in do_balance for passing parent of node information that has been
   gotten from tb struct */
struct buffer_info {
    struct buffer_head * bi_bh;
    struct buffer_head * bi_parent;
    int bi_position;
};


/* there are 4 types of items: stat data, directory item, indirect, direct.
   FIXME: This table does not describe new key format
+-------------------+------------+--------------+------------+
|	            |  k_offset  | k_uniqueness | mergeable? |
+-------------------+------------+--------------+------------+
|     stat data     |	0        |      0       |   no       |
+-------------------+------------+--------------+------------+
| 1st directory item| DOT_OFFSET |DIRENTRY_UNIQUENESS|   no       | 
| non 1st directory | hash value |              |   yes      |
|     item          |            |              |            |
+-------------------+------------+--------------+------------+
| indirect item     | offset + 1 |TYPE_INDIRECT |   if this is not the first indirect item of the object
+-------------------+------------+--------------+------------+
| direct item       | offset + 1 |TYPE_DIRECT   | if not this is not the first direct item of the object
+-------------------+------------+--------------+------------+
*/



#define KEY_IS_STAT_DATA_KEY(p_s_key) 	( get_type (p_s_key) == TYPE_STAT_DATA )
#define KEY_IS_DIRECTORY_KEY(p_s_key)	( get_type (p_s_key) == TYPE_DIRENTRY )
#define KEY_IS_DIRECT_KEY(p_s_key) 	( get_type (p_s_key) == TYPE_DIRECT )
#define KEY_IS_INDIRECT_KEY(p_s_key)	( get_type (p_s_key) == TYPE_INDIRECT )

#define I_IS_STAT_DATA_ITEM(p_s_ih) 	KEY_IS_STAT_DATA_KEY(&((p_s_ih)->ih_key))
#define I_IS_DIRECTORY_ITEM(p_s_ih) 	KEY_IS_DIRECTORY_KEY(&((p_s_ih)->ih_key))
#define I_IS_DIRECT_ITEM(p_s_ih) 	KEY_IS_DIRECT_KEY(&((p_s_ih)->ih_key))
#define I_IS_INDIRECT_ITEM(p_s_ih) 	KEY_IS_INDIRECT_KEY(&((p_s_ih)->ih_key))

#define is_indirect_ih(ih) I_IS_INDIRECT_ITEM(ih)
#define is_direct_ih(ih) I_IS_DIRECT_ITEM(ih)
#define is_direntry_ih(ih) I_IS_DIRECTORY_ITEM(ih)
#define is_stat_data_ih(ih) I_IS_STAT_DATA_ITEM(ih)

#define is_indirect_key(key) KEY_IS_INDIRECT_KEY(key)
#define is_direct_key(key) KEY_IS_DIRECT_KEY(key)
#define is_direntry_key(key) KEY_IS_DIRECTORY_KEY(key)
#define is_stat_data_key(key) KEY_IS_STAT_DATA_KEY(key)

#define COMP_KEYS comp_keys

//#define COMP_SHORT_KEYS comp_short_keys
#define not_of_one_file comp_short_keys

/* number of blocks pointed to by the indirect item */
#define I_UNFM_NUM(p_s_ih)	( get_ih_item_len(p_s_ih) / UNFM_P_SIZE )

/* the used space within the unformatted node corresponding to pos within the item pointed to by ih */
#define I_POS_UNFM_SIZE(ih,pos,size) (((pos) == I_UNFM_NUM(ih) - 1 ) ? (size) - ih_free_space (ih) : (size))

/* check whether byte number 'offset' is in this item */
#define I_OFF_BYTE_IN_ITEM(p_s_ih, n_offset, n_blocksize) \
                  ( get_offset(&(p_s_ih)->ih_key) <= (n_offset) && \
                    get_offset(&(p_s_ih)->ih_key) + get_bytes_number(p_s_ih,n_blocksize) > (n_offset) )

/* these operate on indirect items, where you've got an array of ints
** at a possibly unaligned location.  These are a noop on ia32
**
** p is the array of __u32, i is the index into the array, v is the value
** to store there.
*/
#define d32_get(p, i) le32_to_cpu(get_unaligned((p) + (i)))
#define d32_put(p, i, v) put_unaligned(cpu_to_le32(v), (p) + (i))


/* get the item header */ 
#define B_N_PITEM_HEAD(bh,item_num) ( (struct item_head * )((bh)->b_data + BLKH_SIZE) + (item_num) )

/* get key */
#define B_N_PDELIM_KEY(bh,item_num) ( (struct key * )((bh)->b_data + BLKH_SIZE) + (item_num) )

/* get the key */
#define B_N_PKEY(bh,item_num) ( &(B_N_PITEM_HEAD(bh,item_num)->ih_key) )

/* get item body */
#define B_N_PITEM(bh,item_num) ( (bh)->b_data + get_ih_location (B_N_PITEM_HEAD((bh),(item_num))))

/* get the stat data by the buffer header and the item order */
#define B_N_STAT_DATA(bh,nr) \
( (struct stat_data *)((bh)->b_data+get_ih_location(B_N_PITEM_HEAD((bh),(nr))) ) )

 /* following defines use reiserfs buffer header and item header */
 /* get item body */
#define B_I_PITEM(bh,ih) ( (bh)->b_data + get_ih_location(ih))

/* get stat-data */
#define B_I_STAT_DATA(bh, ih) ( (struct stat_data * )B_I_PITEM(bh,ih) )

#define MAX_DIRECT_ITEM_LEN(size) ((size) - BLKH_SIZE - 2*IH_SIZE - SD_SIZE - UNFM_P_SIZE)
#define MAX_INDIRECT_ITEM_LEN(size) MAX_ITEM_LEN(size)

/***************************************************************************/
/*                    FUNCTION DECLARATIONS                                */
/***************************************************************************/



/* stree.c */
void padd_item (char * item, int total_length, int length);
int B_IS_IN_TREE(struct buffer_head *);
struct key * get_rkey (struct path * p_s_chk_path, reiserfs_filsys_t *);
int bin_search (void * p_v_key, void * p_v_base, int p_n_num, int p_n_width, int * p_n_pos);
int search_by_key (reiserfs_filsys_t *, struct key *, struct path *, int);
int search_by_entry_key (reiserfs_filsys_t *, struct key *, struct path *);
int search_for_position_by_key (reiserfs_filsys_t *, struct key *, struct path *);
int search_by_objectid (reiserfs_filsys_t *, struct key *, struct path *, int *);
void decrement_counters_in_path (struct path * p_s_search_path);
void pathrelse (struct path * p_s_search_path);


int is_left_mergeable (reiserfs_filsys_t * s, struct path * path);
int is_right_mergeable (reiserfs_filsys_t * s, struct path * path);
int are_items_mergeable (struct item_head * left, struct item_head * right, int bsize);


/* fix_nodes.c */
void * reiserfs_kmalloc (size_t size, int flags, reiserfs_filsys_t * s);
void reiserfs_kfree (/*const*/ void * vp, size_t size, reiserfs_filsys_t * s);
int fix_nodes (/*struct reiserfs_transaction_handle *th,*/ int n_op_mode, struct tree_balance * p_s_tb, 
               /*int n_pos_in_item,*/ struct item_head * p_s_ins_ih);
void unfix_nodes (/*struct reiserfs_transaction_handle *th,*/ struct tree_balance *);
void free_buffers_in_tb (struct tree_balance * p_s_tb);
void init_path (struct path *);

/* prints.c */
/* options */
#define PRINT_TREE_DETAILS 	0x1	/* print all items from internal tree */
#define PRINT_DETAILS 		0x2       /* print all items from bitmap */
#define PRINT_ITEM_DETAILS 	0x4 	/* print contents of directory items and stat
                                	   data items and indirect items */
#define PRINT_DIRECT_ITEMS 	0x8 	/* print contents of direct items */

void print_tb (int mode, int item_pos, int pos_in_item, struct tree_balance * tb, char * mes);


void print_bmap (FILE * fp, reiserfs_filsys_t * fs, int silent);
void print_objectid_map (FILE * fp, reiserfs_filsys_t * fs);



/* lbalance.c */
int leaf_move_items (int shift_mode, struct tree_balance * tb, 
                     int mov_num, int mov_bytes, struct buffer_head * Snew);
int leaf_shift_left (struct tree_balance * tb, int shift_num, int shift_bytes);
int leaf_shift_right (struct tree_balance * tb, int shift_num, int shift_bytes);
void leaf_delete_items (reiserfs_filsys_t *, struct buffer_info * cur_bi, 
                        int last_first, int first, int del_num, int del_bytes);
void leaf_insert_into_buf (reiserfs_filsys_t *, struct buffer_info * bi, 
			   int before, struct item_head * inserted_item_ih, const char * inserted_item_body, 
			   int zeros_number);
void leaf_paste_in_buffer (reiserfs_filsys_t *, struct buffer_info * bi, int pasted_item_num, 
			   int pos_in_item, int paste_size, const char * body, int zeros_number);
void leaf_cut_from_buffer (reiserfs_filsys_t *, struct buffer_info * bi, int cut_item_num, 
                           int pos_in_item, int cut_size);
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);
void delete_item (reiserfs_filsys_t *, struct buffer_head * bh, int item_num);
void cut_entry (reiserfs_filsys_t *, struct buffer_head * bh,
		int item_num, int entry_num, int del_count);


/* ibalance.c */
int balance_internal (struct tree_balance * , int, int, struct item_head * , 
                      struct buffer_head **);

/* do_balance.c */
void do_balance (struct tree_balance * tb,
                 struct item_head * ih, const char * body, int flag, in