fsckxtre.c

jfs 源码

/*
 *   Copyright (C) International Business Machines Corp., 2000-2004
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or 
 *   (at your option) any later version.
 * 
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software 
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
/* defines and includes common among the fsck.jfs modules */
#include "xfsckint.h"
#include "jfs_byteorder.h"

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  * superblock buffer pointer
  *
  *      defined in xchkdsk.c
  */
extern struct superblock *sb_ptr;

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  * fsck aggregate info structure pointer
  *
  *      defined in xchkdsk.c
  */
extern struct fsck_agg_record *agg_recptr;

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  * For message processing
  *
  *      defined in xchkdsk.c
  */
extern char *verbose_msg_ptr;

extern char *Vol_Label;

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  * Device information.
  *
  *      defined in xchkdsk.c
  */
extern HFILE Dev_IOPort;
extern uint32_t Dev_blksize;

/* VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
 *
 * The following are internal to this file
 *
 */

struct fsck_Xtree_info {
	xtpage_t *xtp_ptr;
	xad_t *xad_ptr;
	int64_t ext_addr;
	uint32_t ext_length;
	struct treeQelem *this_Qel;
	struct treeQelem *next_Qel;
	int64_t this_key;
	int64_t last_key;
	int64_t last_node_addr;
	int8_t last_level;
	int8_t dense_file;
	int8_t leaf_seen;
};

int xTree_binsrch_page(xtpage_t *, int64_t, int8_t *, int16_t *, int8_t *);

int xTree_process_internal_extents(xtpage_t *, struct fsck_inode_record *,
				   struct treeQelem *,
				   struct fsck_ino_msg_info *, int);

int xTree_node_first_key(struct fsck_Xtree_info *, struct fsck_inode_record *,
			 struct fsck_ino_msg_info *, int);

int xTree_node_first_in_level(struct fsck_Xtree_info *,
			      struct fsck_inode_record *,
			      struct fsck_ino_msg_info *, int);

int xTree_node_last_in_level(struct fsck_Xtree_info *,
			     struct fsck_inode_record *,
			     struct fsck_ino_msg_info *, int);

int xTree_node_not_first_in_level(struct fsck_Xtree_info *,
				  struct fsck_inode_record *,
				  struct fsck_ino_msg_info *, int);

int xTree_node_not_last_in_level(struct fsck_Xtree_info *,
				 struct fsck_inode_record *,
				 struct fsck_ino_msg_info *, int);

int xTree_process_leaf_extents(xtpage_t *, struct fsck_inode_record *,
			       struct treeQelem *, struct fsck_ino_msg_info *,
			       int8_t, int);

/* VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV */

/*****************************************************************************
 * NAME: find_first_leaf
 *
 * FUNCTION:  Get the ordinal number of the aggregate block containing the
 *            first leaf node in the B+ Tree, type xTree, rooted in the
 *            given inode.
 *
 * PARAMETERS:
 *      inoptr           - input - pointer to the inode in which the xTree
 *                                 is rooted
 *      addr_leaf_ptr    - input - pointer to a variable in which to return
 *                                 the address of the leaf in an fsck buffer.
 *      leaf_agg_offset  - input - offset, from the beginning of the
 *                                 aggregate, in aggregate blocks, of the
 *                                 leftmost leaf in the xTree
 *      is_inline        - input - pointer to a variable in which to return:
 *                                 !0 if the inode's data is inline (no leaf)
 *                                  0 if the inode's data is not inline
 *      is_rootleaf      - input - pointer to a variable in which to return:
 *                                 !0 if the xTree's root node is a leaf
 *                                  0 if the xTree's root node is an internal
 *                                        node
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int find_first_leaf(struct dinode *inoptr,
		    xtpage_t ** addr_leaf_ptr,
		    int64_t * leaf_agg_offset,
		    int8_t * is_inline, int8_t * is_rootleaf)
{
	int ffl_rc = FSCK_OK;
	xtpage_t *xtpg_ptr;
	xad_t *xad_ptr;
	int64_t first_child_addr = 0;

	*is_rootleaf = 0;	/* assume inode has no data */
	*is_inline = 0;		/* assume inode has no data */
	*addr_leaf_ptr = NULL;	/* assume inode has no data */
	*leaf_agg_offset = 0;	/* assume inode has no data */
	xtpg_ptr = (xtpage_t *) & (inoptr->di_btroot);

	if (xtpg_ptr->header.flag & BT_LEAF) {
		/* it's a root-leaf */
		*is_rootleaf = -1;
		*leaf_agg_offset = addressPXD(&(inoptr->di_ixpxd));
	} else {
		/* it's a tree */
		while ((ffl_rc == FSCK_OK) && (*addr_leaf_ptr == NULL)) {
			if (xtpg_ptr->header.flag & BT_LEAF) {
				/* found it!  */
				*addr_leaf_ptr = xtpg_ptr;
				*leaf_agg_offset = first_child_addr;
			} else {
				/* keep moving down the tree */
				xad_ptr = &(xtpg_ptr->xad[XTENTRYSTART]);
				first_child_addr = addressXAD(xad_ptr);
				ffl_rc = node_get(first_child_addr, &xtpg_ptr);
			}
		}
	}

	return (ffl_rc);
}

/*****************************************************************************
 * NAME: init_xtree_root
 *
 * FUNCTION:  Initialize the btroot in the given inode as an empty (big)
 *                 xtree root.  Adjust di_nblocks and di_size to match.
 *
 * PARAMETERS:
 *      inoptr           - input - pointer to the inode in which the xTree
 *                                 root should be initialized
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int init_xtree_root(struct dinode *inoptr)
{
	int ixr_rc = FSCK_OK;
	xtpage_t *xtpg_ptr;

	xtpg_ptr = (xtpage_t *) & (inoptr->di_btroot);
	xtpg_ptr->header.flag = (DXD_INDEX | BT_ROOT | BT_LEAF);
	xtpg_ptr->header.maxentry = XTROOTMAXSLOT;
	xtpg_ptr->header.nextindex = XTENTRYSTART;
	inoptr->di_nblocks = 0;
	inoptr->di_size = 0;

	return (ixr_rc);
}

/*****************************************************************************
 * NAME: process_valid_data
 *
 * FUNCTION:  Perform the desired action on the xTree rooted in the given
 *            inode, assume that the xTree has a valid structure.  (I.e.,
 *            that the tree has already been validated.)
 *
 * PARAMETERS:
 *      inoptr          - input - pointer to the inode in which the xTree is
 *                                rooted
 *      inoidx          - input - ordinal number of the inode
 *      inorecptr       - input - pointer to the fsck inode record describing
 *                                the inode in which the xTree is rooted
 *      msg_info_ptr    - input - pointer to data needed for messages about
 *                                the inode in which the xTree is rooted
 *      desired_action  - input - { FSCK_RECORD | FSCK_UNRECORD | FSCK_QUERY }
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int process_valid_data(struct dinode *inoptr,
		       uint32_t inoidx,
		       struct fsck_inode_record *inorecptr,
		       struct fsck_ino_msg_info *msg_info_ptr,
		       int desired_action)
{
	int pvd_rc = FSCK_OK;
	int xad_idx;
	xtpage_t *xtpage_ptr;
	xtpage_t *this_xtpage;
	xad_t *xad_ptr;
	int64_t node_addr_fsblks;
	int64_t first_child_addr;
	int64_t first_fsblk;
	int64_t num_fsblks;
	int8_t extent_is_valid;
	int8_t is_EA = 0;
	int8_t is_ACL = 0;
	int8_t is_rootnode;
	uint32_t block_count;

	if (ISDIR(inoptr->di_mode))
		xtpage_ptr = (xtpage_t *) & (inoptr->di_dirtable);
	else
		xtpage_ptr = (xtpage_t *) & (inoptr->di_btroot);

	is_rootnode = -1;

	if (xtpage_ptr->header.flag == 0)
		goto out;

	/* there is data for this inode */
	while ((pvd_rc == FSCK_OK) && (xtpage_ptr != NULL)) {
		/* while not done processing the tree */
		/*
		 * this node is a first child.  if it isn't a leaf, get
		 * the address of its first child
		 */
		if (xtpage_ptr->header.flag & BT_LEAF) {
			/* it's a leaf */
			first_child_addr = 0;
		} else {	/* else it's not a leaf */
			/* the first child */
			xad_ptr = &(xtpage_ptr->xad[XTENTRYSTART]);
			first_child_addr = addressXAD(xad_ptr);
		}

		/*
		 * process the current level
		 */
		/* first node in the level */
		this_xtpage = xtpage_ptr;
		while ((pvd_rc == FSCK_OK) && (this_xtpage != NULL)) {
			/* process all nodes on the level */
			for (xad_idx = XTENTRYSTART;
			     ((xad_idx < xtpage_ptr->header.nextindex)
			      && (pvd_rc == FSCK_OK)); xad_idx++) {
				/* for each xad in the xtpage */
				xad_ptr = &(this_xtpage->xad[xad_idx]);
				first_fsblk = addressXAD(xad_ptr);
				num_fsblks = lengthXAD(xad_ptr);
				pvd_rc =
				    process_extent(inorecptr,
						   num_fsblks,
						   first_fsblk, is_EA,
						   is_ACL, msg_info_ptr,
						   &block_count,
						   &extent_is_valid,
						   desired_action);
				if ((desired_action == FSCK_RECORD) ||
				    (desired_action == FSCK_RECORD_DUPCHECK)) {
					agg_recptr->blocks_this_fset +=
					    block_count;
					agg_recptr->this_inode.all_blks +=
					    block_count;
					if (first_child_addr == 0) {
						/* this is a leaf */
						agg_recptr->
						    this_inode.data_blks +=
						    block_count;
					}
				} else if (desired_action == FSCK_UNRECORD) {
					agg_recptr->blocks_this_fset -=
					    block_count;
					agg_recptr->this_inode.all_blks -=
					    block_count;
					if (first_child_addr == 0) {
						/* this is a leaf */
						agg_recptr->
						    this_inode.data_blks -=
						    block_count;
					}
				}
			}

			if (is_rootnode) {
				/* root has no siblings */
				is_rootnode = 0;
				this_xtpage = NULL;
			} else if (this_xtpage->header.next == ((int64_t) 0)) {
				/* this is rightmost */
				this_xtpage = NULL;
			} else {
				/* else there is a right sibling/cousin */
				node_addr_fsblks = this_xtpage->header.next;
				pvd_rc =
				    node_get(node_addr_fsblks, &this_xtpage);
			}
		}
		/*
		 * if not done, go down to the next level of the tree
		 */
		if (first_child_addr == 0) {
			/* done! */
			xtpage_ptr = NULL;
		} else {
			/* get the first child/cousin in the next level */
			pvd_rc = node_get(first_child_addr, &xtpage_ptr);
		}
	}
      out:
	return (pvd_rc);
}

/*****************************************************************************
 * NAME: xTree_binsrch_page
 *
 * FUNCTION:  Perform a binary search on the xad's in the given xTree node
 *
 * PARAMETERS:
 *      xtpg_ptr       - input - pointer to the xTree node to search
 *      given_offset   - input - offset to match to an xad key
 *      xad_selected   - input - pointer to a variable in which to return:
 *                               !0 if the search was successful
 *                                0 if the search was not successful
 *      selected_idx   - input - the ordinal value of xad, within the node,
 *                               of the xad whose key matches given_offset
 *                               (if any)
 *      not_allocated  - input - * currently unused *
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int xTree_binsrch_page(xtpage_t * xtpg_ptr,
		       int64_t given_offset,
		       int8_t * xad_selected,
		       int16_t * selected_idx, int8_t * not_allocated)