reiserfs_fs.h

This is a ReiserFs file system driver for Windows NT/2000/XP/Vista.

#define __fs_changed(gen,s) (gen != get_generation (s))
#define fs_changed(gen,s) ({cond_resched(); __fs_changed(gen, s);})


/***************************************************************************/
/*                  FIXATE NODES                                           */
/***************************************************************************/

#define VI_TYPE_LEFT_MERGEABLE 1
#define VI_TYPE_RIGHT_MERGEABLE 2

/* To make any changes in the tree we always first find node, that
   contains item to be changed/deleted or place to insert a new
   item. We call this node S. To do balancing we need to decide what
   we will shift to left/right neighbor, or to a new node, where new
   item will be etc. To make this analysis simpler we build virtual
   node. Virtual node is an array of items, that will replace items of
   node S. (For instance if we are going to delete an item, virtual
   node does not contain it). Virtual node keeps information about
   item sizes and types, mergeability of first and last items, sizes
   of all entries in directory item. We use this array of items when
   calculating what we can shift to neighbors and how many nodes we
   have to have if we do not any shiftings, if we shift to left/right
   neighbor or to both. */
struct virtual_item
{
    int vi_index; // index in the array of item operations
    unsigned short vi_type;	// left/right mergeability
    unsigned short vi_item_len;           /* length of item that it will have after balancing */
    struct item_head * vi_ih;
    const char * vi_item;     // body of item (old or new)
    const void * vi_new_data; // 0 always but paste mode
    void * vi_uarea;    // item specific area
};


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 */
  const void * vn_data;
  struct virtual_item * vn_vi;	/* array of items (including a new one, excluding item to be deleted) */
};


#ifndef __GCC__
 #pragma pack(push, 1)
#endif

/* used by directory items when creating virtual nodes */
struct direntry_uarea {
    int flags;
    __u16 entry_count;
    __u16 entry_sizes[1];
} __PACKED ;

#ifndef __GCC__
 #pragma pack(pop)
#endif

/***************************************************************************/
/*                  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
{
  int tb_mode;
  int need_balance_dirty;
  struct super_block * tb_sb;
  struct reiserfs_transaction_handle *transaction_handle ;
  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 */

  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];
  struct buffer_head * thrown[MAX_FEB_SIZE];
  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. The code sometimes subtracts
			   one to get the number of wholly shifted
			   items for other purposes. */
  int rnum[MAX_HEIGHT];	/* substitute right for left in comment above */
  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] */
  int rkey[MAX_HEIGHT];               /* substitute r for l in comment above */
  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.  */
  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 */
  int cur_blknum;	/* number of empty blocks having been already allocated			*/
  int s0num;             /* number of items that fall into left most  node when S[0] splits	*/
  int s1num;             /* number of items that fall into first  new node when S[0] splits	*/
  int s2num;             /* number of items that fall into second new node when S[0] splits	*/
  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 */
  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                           */
  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	*/
  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 */

  int fs_gen;                  /* saved value of `reiserfs_generation' counter
			          see FILESYSTEM_CHANGED() macro in reiserfs_fs.h */
#ifdef DISPLACE_NEW_PACKING_LOCALITIES
  struct reiserfs_key  key;	      /* key pointer, to pass to block allocator or
				 another low-level subsystem */
#endif
} ;

/* 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 tree_balance * tb;
    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.
+-------------------+------------+--------------+------------+
|	            |  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
+-------------------+------------+--------------+------------+
*/

struct item_operations {
    int (*bytes_number) (struct item_head * ih, int block_size);
    void (*decrement_key) (struct cpu_key *);
    int (*is_left_mergeable) (struct reiserfs_key * ih, unsigned long bsize);
    void (*print_item) (struct item_head *, char * item);
    void (*check_item) (struct item_head *, char * item);

    int (*create_vi) (struct virtual_node * vn, struct virtual_item * vi, 
		      int is_affected, int insert_size);
    int (*check_left) (struct virtual_item * vi, int free, 
			    int start_skip, int end_skip);
    int (*check_right) (struct virtual_item * vi, int free);
    int (*part_size) (struct virtual_item * vi, int from, int to);
    int (*unit_num) (struct virtual_item * vi);
    void (*print_vi) (struct virtual_item * vi);
};


extern struct item_operations * item_ops [TYPE_ANY + 1];

#define op_bytes_number(ih,bsize)                    item_ops[le_ih_k_type (ih)]->bytes_number (ih, bsize)
#define op_is_left_mergeable(key,bsize)              item_ops[le_key_k_type (le_key_version (key), key)]->is_left_mergeable (key, bsize)
#define op_print_item(ih,item)                       item_ops[le_ih_k_type (ih)]->print_item (ih, item)
#define op_check_item(ih,item)                       item_ops[le_ih_k_type (ih)]->check_item (ih, item)
#define op_create_vi(vn,vi,is_affected,insert_size)  item_ops[le_ih_k_type ((vi)->vi_ih)]->create_vi (vn,vi,is_affected,insert_size)
#define op_check_left(vi,free,start_skip,end_skip) item_ops[(vi)->vi_index]->check_left (vi, free, start_skip, end_skip)
#define op_check_right(vi,free)                      item_ops[(vi)->vi_index]->check_right (vi, free)
#define op_part_size(vi,from,to)                     item_ops[(vi)->vi_index]->part_size (vi, from, to)
#define op_unit_num(vi)				     item_ops[(vi)->vi_index]->unit_num (vi)
#define op_print_vi(vi)                              item_ops[(vi)->vi_index]->print_vi (vi)



#define COMP_SHORT_KEYS comp_short_keys

/* number of blocks pointed to by the indirect item */
#define I_UNFM_NUM(p_s_ih)	( 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))

/* number of bytes contained by the direct item or the unformatted nodes the indirect item points to */


/* 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 reiserfs_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 + 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 + ih_location(B_N_PITEM_HEAD((bh),(nr))) ) )

    /* following defines use reiserfs buffer header and item header */

/* get stat-data */
#define B_I_STAT_DATA(bh, ih) ( (struct stat_data * )((bh)->b_data + ih_location(ih)) )

// this is 3976 for size==4096
#define MAX_DIRECT_ITEM_LEN(size) ((size) - BLKH_SIZE - 2*IH_SIZE - SD_SIZE - UNFM_P_SIZE)

/* indirect items consist of entries which contain blocknrs, pos
   indicates which entry, and B_I_POS_UNFM_POINTER resolves to the
   blocknr contained by the entry pos points to */
#define B_I_POS_UNFM_POINTER(bh,ih,pos) le32_to_cpu(*(((unp_t *)B_I_PITEM(bh,ih)) + (pos)))
#define PUT_B_I_POS_UNFM_POINTER(bh,ih,pos, val) do {*(((unp_t *)B_I_PITEM(bh,ih)) + (pos)) = cpu_to_le32(val); } while (0)

struct reiserfs_iget_args {
    __u32 objectid ;
    __u32 dirid ;
} ;

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

/*#ifdef __KERNEL__*/
#define get_journal_desc_magic(bh) (bh->b_data + bh->b_size - 12)

#define journal_trans_half(blocksize) \
	((blocksize - sizeof (struct reiserfs_journal_desc) + sizeof (__u32) - 12) / sizeof (__u32))

/* journal.c see journal.c for all the comments here */

/* first block written in a commit.  */
struct reiserfs_journal_desc {
  __u32 j_trans_id ;			/* id of commit */
  __u32 j_len ;			/* length of commit. len +1 is the commit block */
  __u32 j_mount_id ;				/* mount id of this trans*/
  __u32 j_realblock[1] ; /* real locations for each block */
} ;

#define get_desc_trans_id(d)   le32_to_cpu((d)->j_trans_id)
#define get_desc_trans_len(d)  le32_to_cpu((d)->j_len)
#define get_desc_mount_id(d)   le32_to_cpu((d)->j_mount_id)

#define set_desc_trans_id(d,val)       do { (d)->j_trans_id = cpu_to_le32 (val); } while (0)
#define set_desc_trans_len(d,val)      do { (d)->j_len = cpu_to_le32 (val); } while (0)
#define set_desc_mount_id(d,val)       do { (d)->j_mount_id = cpu_to_le32 (val); } while (0)

/* last block written in a commit */
struct reiser