fsckdtre.c

在Linux内核从2.4升级到2.6时需要升级的软件包

 *                                  right_key, on the dTree leaf level,
 *                                  is not valid
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_key_compare_leaflvl(UniChar * left_key,
			      uint8_t left_key_len,
			      UniChar * right_key,
			      uint8_t right_key_len, int8_t * keys_ok)
{
	int dkcl_rc = FSCK_OK;
	int outcome;

	/* assume incorrect relation between the keys */
	*keys_ok = 0;

	if (sb_ptr->s_flag & JFS_OS2) {	/* case is preserved but ignored */
		dkcl_rc =
		    dTree_key_to_upper(left_key, &(ukey[0][0]),
				       (int32_t) left_key_len);
		if (dkcl_rc == FSCK_OK) {
			dkcl_rc = dTree_key_to_upper(right_key, &(ukey[1][0]),
						     (int32_t) right_key_len);
			if (dkcl_rc == FSCK_OK) {
				dkcl_rc =
				    dTree_key_compare(&(ukey[0][0]),
						      left_key_len,
						      &(ukey[1][0]),
						      right_key_len, &outcome);
			}
		}

	} else {
		/* case sensitive */
		dkcl_rc = dTree_key_compare(left_key, left_key_len,
					    right_key, right_key_len, &outcome);
	}

	if (dkcl_rc == FSCK_OK) {
		if ((outcome == KEYS_MATCH) || (outcome == LEFT_KEY_LOWER)) {
			/* right key greater */
			*keys_ok = -1;
		}
	}
	return (dkcl_rc);
}

/*****************************************************************************
 * NAME: dTree_key_compare_prntchld
 *
 * FUNCTION: Compare the two given strings according to the rules for
 *           a parent entry key and the first (sorted) entry key in the
 *           node described by the parent entry.
 *
 * PARAMETERS:
 *      dtiptr          - input - pointer to an fsck record describing the
 *                                directory tree
 *      parent_key      - input - pointer to the key extracted from the
 *                                parent node entry
 *      parent_key_len  - input - number of UniChars in parent_key
 *      child_key       - input - pointer to the key extracted from the first
 *                                (sorted) entry in the child node described
 *                                by the entry from which parent_key was
 *                                taken
 *      child_key_len   - input - number of UniChars in child_key
 *      keys_ok         - input - pointer to a variable in which to return
 *                                !0 if the relation between parent_key and
 *                                   child_key, where child_key is the first
 *                                   key in the child node, is valid
 *                                 0 if the relation between parent_key and
 *                                   child_key, where child_key is the first
 *                                   key in the child node, is not valid
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_key_compare_prntchld(struct fsck_Dtree_info *dtiptr,
			       UniChar * parent_key,
			       uint8_t parent_key_len,
			       UniChar * child_key,
			       uint8_t child_key_len, int8_t * keys_ok)
{
	int dnfk_rc = FSCK_OK;
	int outcome;

	/* assume incorrect relation between the keys */
	*keys_ok = 0;

	if (dtiptr->leaf_level == dtiptr->this_Qel->node_level) {
		/*
		 * the child is a leaf so its key is mixed case
		 */
		dnfk_rc =
		    dTree_key_to_upper(child_key, &(ukey[0][0]),
				       (int32_t) child_key_len);
		if (dnfk_rc == FSCK_OK) {
			dnfk_rc = dTree_key_compare(parent_key, parent_key_len,
						    &(ukey[0][0]),
						    child_key_len, &outcome);
		}

	} else {
		/* the child is not a leaf */
		dnfk_rc = dTree_key_compare(parent_key, parent_key_len,
					    child_key, child_key_len, &outcome);
	}

	if ((dnfk_rc == FSCK_OK)
	    && ((outcome == KEYS_MATCH) || (outcome == LEFT_KEY_LOWER))) {
		/* parent is less than or equal to first child */
		*keys_ok = -1;
	}

	return (dnfk_rc);
}

/*****************************************************************************
 * NAME: dTree_key_compare_samelvl
 *
 * FUNCTION: Compare the 2 given strings according to the rules for
 *           sibling entries in an internal node.
 *
 * PARAMETERS:
 *      left_key       - input - pointer to the first in a pair of keys to
 *                               compare
 *      left_key_len   - input - number of UniChars in left_key
 *      right_key      - input - pointer to the second in a pair of keys to
 *                               compare
 *      right_key_len  - input - number of UniChars in right_key
 *      keys_ok        - input - pointer to a variable in which to return
 *                               !0 if the relation between left_key and
 *                                  right_key, on the same dTree level,
 *                                  is valid
 *                                0 if the relation between left_key and
 *                                  right_key, on the same dTree level,
 *                                  is not valid
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_key_compare_samelvl(UniChar * left_key,
			      uint8_t left_key_len,
			      UniChar * right_key,
			      uint8_t right_key_len, int8_t * keys_ok)
{
	int dkcs_rc = FSCK_OK;
	int outcome;

	/* assume incorrect relation between the keys */
	*keys_ok = 0;

	dkcs_rc =
	    dTree_key_compare(left_key, left_key_len, right_key, right_key_len,
			      &outcome);

	if (dkcs_rc == FSCK_OK) {
		if (outcome == LEFT_KEY_LOWER) {
			/* right key greater */
			*keys_ok = -1;
		}
	}
	return (dkcs_rc);
}

/**************************************************************************
 * NAME:  dTree_key_extract
 *
 * FUNCTION: Extract the specified directory entry (either internal or
 *           leaf) key and concatenate it's segments (if more than one).
 *           Assume the directory structure has already been validated.
 *
 * PARAMETERS:
 *      dtiptr       - input - pointer to an fsck record describing the
 *                             directory tree
 *      start_dtidx  - input - index of the entry in the directory node's
 *                             sorted entry index table containing the
 *                             slot number of the (first segment of the)
 *                             key to extract
 *      key_space    - input - pointer to a buffer in which to return
 *                             the directory key (a complete filename if
 *                             the node is a leaf) extracted
 *      key_length   - input - pointer to a variable in which to return
 *                             the length of the directory key being returned
 *                             in *key_space
 *      is_root      - input - !0 => the specified node is a B+ Tree root
 *                              0 => the specified node is not a B+ Tree root
 *      is_leaf      - input - !0 => the specified node is a leaf node
 *                              0 => the specified node is not a leaf node
 *      inorecptr    - input - pointer to an fsck inode record describing
 *                             the inode
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_key_extract(struct fsck_Dtree_info *dtiptr,
		      int start_dtidx,
		      UniChar * key_space,
		      uint32_t * key_length,
		      int8_t is_root,
		      int8_t is_leaf, struct fsck_inode_record *inorecptr)
{
	int dek_rc = FSCK_OK;
	int this_slotidx, next_slotidx;
	struct idtentry *ientry_ptr;
	struct ldtentry *lentry_ptr;
	UniChar *name_seg;
	int seg_length, UniChars_left = 0, seg_max;
	struct dtslot *contin_entry_ptr;

	this_slotidx = dtiptr->dtstbl[start_dtidx];

	if (is_leaf) {
		lentry_ptr = (struct ldtentry *) &(dtiptr->slots[this_slotidx]);
		name_seg = &(lentry_ptr->name[0]);
		*key_length = lentry_ptr->namlen;
		next_slotidx = lentry_ptr->next;
		if (sb_ptr->s_flag & JFS_DIR_INDEX)
			seg_max = DTLHDRDATALEN;
		else
			seg_max = DTLHDRDATALEN_LEGACY;
	} else {
		ientry_ptr = (struct idtentry *) &(dtiptr->slots[this_slotidx]);
		name_seg = &(ientry_ptr->name[0]);
		*key_length = ientry_ptr->namlen;
		next_slotidx = ientry_ptr->next;
		seg_max = DTIHDRDATALEN;
	}

	if ((*key_length) > JFS_NAME_MAX) {
		/* name too long */
		inorecptr->ignore_alloc_blks = 1;
	} else {
		UniChars_left = *key_length;
		*key_length = 0;
	}

	while ((dek_rc == FSCK_OK) && (this_slotidx != -1)
	       && (!inorecptr->ignore_alloc_blks)) {

		if ((this_slotidx > dtiptr->max_slotidx)
		    || (this_slotidx < DTENTRYSTART)) {
			/* idx out of bounds */
			inorecptr->ignore_alloc_blks = 1;
		} else {
			/* else no reason to think there's a problem */
			if (UniChars_left > seg_max) {
				/* this isn't the last */
				seg_length = seg_max;
				UniChars_left = UniChars_left - seg_max;
			} else {
				seg_length = UniChars_left;
				UniChars_left = 0;
			}
			/* copy this section of the name into the buffer */
			memcpy((void *) &(key_space[*key_length]),
			       (void *) &(name_seg[0]),
			       (seg_length * sizeof (UniChar))
			    );
			*key_length += seg_length;

			this_slotidx = next_slotidx;
			if (next_slotidx != -1) {
				/* it's not the end of chain marker */
				contin_entry_ptr =
				    &(dtiptr->slots[this_slotidx]);
				name_seg = &(contin_entry_ptr->name[0]);
				seg_length = contin_entry_ptr->cnt;
				next_slotidx = contin_entry_ptr->next;
				seg_max = DTSLOTDATALEN;
			}
		}
	}

	return (dek_rc);
}

/*****************************************************************************
 * NAME:  dTree_key_extract_cautiously
 *
 * FUNCTION: Extract the specified directory entry (either internal or
 *           leaf) key and concatenate it's segments (if more than one).
 *           Do not assume the directory structure has been validated.
 *
 * PARAMETERS:
 *      dtiptr       - input - pointer to an fsck record describing the
 *                             directory tree
 *      start_dtidx  - input - index of the entry in the directory node's
 *                             sorted entry index table containing the
 *                             slot number of the (first segment of the)
 *                             key to extract
 *      key_space    - input - pointer to a buffer in which to return
 *                             the directory key (a complete filename if
 *                             the node is a leaf) extracted
 *      key_length   - input - pointer to a variable in which to return
 *                             the length of the directory key being returned
 *                             in *key_space
 *      is_root      - input - !0 => the specified node is a B+ Tree root
 *                              0 => the specified node is not a B+ Tree root
 *      is_leaf      - input - !0 => the specified node is a leaf node
 *                              0 => the specified node is not a leaf node
 *      inorecptr    - input - pointer to an fsck inode record describing
 *                             the inode
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_key_extract_cautiously(struct fsck_Dtree_info *dtiptr,
				 int start_dtidx,
				 UniChar * key_space,
				 uint32_t * key_length,
				 int8_t is_root,
				 int8_t is_leaf,
				 struct fsck_inode_record *inorecptr)
{
	int deck_rc = FSCK_OK;
	int8_t temp_slot_map[DTPAGEMAXSLOT];
	int this_slotidx, next_slotidx, this_charidx;
	struct idtentry *ientry_ptr;
	struct ldtentry *lentry_ptr;
	UniChar *name_seg;
	int seg_length, UniChars_left = 0, seg_max;
	struct dtslot *contin_entry_ptr;

	memset((void *) &(temp_slot_map[0]), 0, DTPAGEMAXSLOT);

	this_slotidx = dtiptr->dtstbl[start_dtidx];

	if (is_leaf) {
		lentry_ptr = (struct ldtentry *) &(dtiptr->slots[this_slotidx]);
		name_seg = &(lentry_ptr->name[0]);
		*key_length = lentry_ptr->namlen;
		next_slotidx = lentry_ptr->next;
		if (sb_ptr->s_flag & JFS_DIR_INDEX)
			seg_max = DTLHDRDATALEN;
		else
			seg_max = DTLHDRDATALEN_LEGACY;
	} else {
		ientry_ptr = (struct idtentry *) &(dtiptr->slots[this_slotidx]);
		name_seg = &(ientry_ptr->name[0]);
		*key_length = ientry_ptr->namlen;
		next_slotidx = ientry_ptr->next;
		seg_max = DTIHDRDATALEN;
	}

	if ((*key_length) > JFS_NAME_MAX) {
		/* name too long */
		inorecptr->ignore_alloc_blks = 1;
	} else {
		UniChars_left = *key_length;
		*key_length = 0;
	}

	while ((deck_rc == FSCK_OK) && (this_slotidx != -1)
	       && (!inorecptr->ignore_alloc_blks)) {

		if ((this_slotidx > dtiptr->max_slotidx)
		    || (this_slotidx < DTENTRYSTART)
		    || (temp_slot_map[this_slotidx] != 0)) {
			/* index is out of bounds OR index was seen earlier this key chain */
			/* bad chain */
			inorecptr->ignore_alloc_blks = 1;
		} else {
			/* else no reason to think there's a problem */
			/* mark the slot used */
			temp_slot_map[this_slotidx] = -1;
			if (UniChars_left > seg_max) {
				/* this isn't the last */
				seg_length = seg_max;
				UniChars_left = UniChars_left - seg_max;
			} else {
				seg_length = UniChars_left;
				UniChars_left = 0;
			}
			/* copy this section of the name into the buffer */
			memcpy((void *) &(key_space[*key_length]),
			       (void *) &(name_seg[0]),
			       (seg_length * sizeof (UniChar)));
			*key_length += seg_length;

			this_slotidx = next_slotidx;
			if (next_slotidx != -1) {
				/* it's not the end of chain marker */
				if (UniChars_left == 0)
					/* too many segments */
					inorecptr->ignore_alloc_blks = 1;
				else {
					contin_entry_ptr =
					    &(dtiptr->slots[this_slotidx]);
					name_seg = &(contin_entry_ptr->name[0]);
					seg_length = contin_entry_ptr->cnt;
					next_slotidx = contin_entry_ptr->next;
					seg_max = DTSLOTDATALEN;
				}
			}
		}
	}

	/*
	 * check for a null character embedded in the name
	 */
	this_charidx = 0;
	while ((deck_rc == FSCK_OK) && (!inorecptr->ignore_alloc_blks)
	       && (this_charidx < *key_length)) {
		if (((unsigned short *) key_space)[this_charidx] ==