cde40_repair.c

reiser4progs ReiserFS V4 ReiserFs官方已经关闭 这个是1.0.6 2006-02-22发布的 给需要的朋友

/* Copyright 2001-2005 by Hans Reiser, licensing governed by
   reiser4progs/COPYING.
   
   cde40_repair.c -- reiser4 default direntry plugin.
   
   Description:
   1) If offset is obviously wrong (no space for cde40_t,entry_t's, 
   objid40_t's) mark it as not relable - NR.
   2) If 2 offsets are not NR and entry contents between them are valid,
   (probably even some offsets between them can be recovered also) mark 
   all offsets beteen them as relable - R.
   3) If pair of offsets does not look ok and left is R, mark right as NR.
   4) If there is no R offset on the left, compare the current with 0-th 
   through the current if not NR.
   5) If there are some R offsets on the left, compare with the most right
   of them through the current if not NR. 
   6) If after 1-5 there is no one R - this is likely not to be cde40
   item.
   7) If there is a not NR offset and it has a neighbour which is R and
   its pair with the nearest R offset from the other side if any is ok,
   mark it as R. ?? Disabled. ??
   8) Remove all units with not R offsets.
   9) Remove the space between the last entry_t and the first R offset.
   10)Remove the space between the end of the last entry and the end of 
   the item. */

#ifndef ENABLE_MINIMAL

#include "cde40.h"
#include <reiser4/bitmap.h>
#include <repair/plugin.h>

#define S_NAME	0
#define L_NAME	1

/* short name is all in the key, long is 16 + '\0' */
#define NAME_LEN_MIN(kind)		\
        (kind ? 16 + 1: 0)

#define ENTRY_LEN_MIN(kind, pol)	\
        (ob_size(pol) + NAME_LEN_MIN(kind))

#define UNIT_LEN_MIN(kind, pol)		\
        (en_size(pol) + ENTRY_LEN_MIN(kind, pol))

#define DIRITEM_LEN_MIN			\
        (UNIT_LEN_MIN(S_NAME) + sizeof(cde40_t))

#define en_len_min(count, pol)		\
        ((uint64_t)count * UNIT_LEN_MIN(S_NAME, pol) + sizeof(cde40_t))

#define NR	0
#define R	1

struct entry_flags {
	uint8_t *elem;
	uint32_t count;
};
    
/* Extention for repair_flag_t */
#define REPAIR_SKIP	0

/* Check the i-th offset of the unit body within the item. */
static errno_t cde40_offset_check(reiser4_place_t *place, uint32_t pos) {
	uint32_t pol;
	uint32_t offset;
    
	pol = cde40_key_pol(place);
	
	if (place->len < en_len_min(pos + 1, pol))
		return 1;

	offset = cde_get_offset(place, pos, pol);
    
	/* There must be enough space for the entry in the item. */
	if (offset != place->len - ENTRY_LEN_MIN(S_NAME, pol) && 
	    offset != place->len - 2 * ENTRY_LEN_MIN(S_NAME, pol) && 
	    offset > place->len - ENTRY_LEN_MIN(L_NAME, pol))
	{
		return 1;
	}
	
	/* There must be enough space for item header, set of unit headers and 
	   set of keys of objects entries point to. */
	return pos != 0 ?
		(offset < sizeof(cde40_t) + en_size(pol) * (pos + 1) + 
		 ob_size(pol) * pos) :
		(offset - sizeof(cde40_t)) % (en_size(pol)) != 0;
	
	/* If item was shorten, left entries should be recovered also. 
	   So this check is excessive as it can avoid such recovering 
	   if too many entry headers are left.
	 if (pos == 0) {
	 uint32_t count;
	
	 count = (offset - sizeof(cde40_t)) / en_size(pol);
		
	 if (offset + count * ENTRY_LEN_MIN(S_NAME, pol) > place->len)
	 return 1;
	
	 }
	*/
}

static uint32_t cde40_count_estimate(reiser4_place_t *place, uint32_t pos) {
	uint32_t pol = cde40_key_pol(place);
	uint32_t offset = cde_get_offset(place, pos, pol);
	
	aal_assert("vpf-761", place->len >= en_len_min(pos + 1, pol));
	
	return pos == 0 ?
		(offset - sizeof(cde40_t)) / en_size(pol) :
		((offset - pos * ob_size(pol) - sizeof(cde40_t)) / 
		 en_size(pol));
}

/* Check that 2 neighbour offsets look coorect. */
static errno_t cde40_pair_offsets_check(reiser4_place_t *place, 
					uint32_t start_pos, 
					uint32_t end_pos) 
{    
	uint32_t pol;
	uint32_t offset, end_offset;
	uint32_t count = end_pos - start_pos;
	
	pol = cde40_key_pol(place);
	
	aal_assert("vpf-753", start_pos < end_pos);
	aal_assert("vpf-752", place->len >= en_len_min(end_pos + 1, pol));

	end_offset = cde_get_offset(place, end_pos, pol);
	
	if (end_offset == cde_get_offset(place, start_pos, pol) +
	    ENTRY_LEN_MIN(S_NAME, pol) * count)
	{
		return 0;
	}
	
	offset = cde_get_offset(place, start_pos, pol) +
		ENTRY_LEN_MIN(L_NAME, pol);
	
	return (end_offset < offset + (count - 1) * ENTRY_LEN_MIN(S_NAME, pol));
}

static uint32_t cde40_name_len(char *body, uint32_t start, uint32_t end) {
	uint32_t i;
	
	aal_assert("vpf-759", start < end);
	
	for (i = start; i < end; i++) {
		if (body[i] == '\0')
			break;
	}
	
	return i - start;
}

/* Returns amount of entries detected. */
static uint32_t cde40_short_entry_detect(reiser4_place_t *place, 
					uint32_t start_pos, 
					uint32_t length, 
					uint8_t mode)
{
	uint32_t pol;
	uint32_t offset, limit;

	pol = cde40_key_pol(place);
	limit = cde_get_offset(place, start_pos, pol);
	
	aal_assert("vpf-770", length < place->len);
	aal_assert("vpf-769", limit <= place->len - length);
	
	if (length % ENTRY_LEN_MIN(S_NAME, pol))
		return 0;
	
	if (mode == REPAIR_SKIP)
		return length / ENTRY_LEN_MIN(S_NAME, pol);
	
	start_pos++;
	for (offset = ENTRY_LEN_MIN(S_NAME, pol); offset < length; 
	     offset += ENTRY_LEN_MIN(S_NAME, pol), start_pos++) 
	{
		fsck_mess("Node (%llu), item (%u), unit (%u), [%s]: unit "
			  "offset (%u) is wrong, should be (%u). %s", 
			  place_blknr(place), place->pos.item, start_pos,
			  print_key(cde40_core, &place->key),
			  cde_get_offset(place, start_pos, pol),
			  limit + offset,  mode == RM_BUILD ? "Fixed." : "");
		
		if (mode == RM_BUILD)
			cde_set_offset(place, start_pos, limit + offset, pol);
	}
	
	return length / ENTRY_LEN_MIN(S_NAME, pol);
}

/* Returns amount of entries detected. */
static uint32_t cde40_long_entry_detect(reiser4_place_t *place, 
				       uint32_t start_pos, 
				       uint32_t length, 
				       uint8_t mode)
{
	uint32_t pol;
	int count = 0;
	uint32_t offset;
	uint32_t l_limit;
	uint32_t r_limit;

	pol = cde40_key_pol(place);
	
	aal_assert("umka-2405", place != NULL);
	aal_assert("vpf-771", length < place->len);
	
	aal_assert("vpf-772", cde_get_offset(place, start_pos, pol)
		   <= (place->len - length));
	
	l_limit = cde_get_offset(place, start_pos, pol);
	r_limit = l_limit + length;
	
	while (l_limit + ob_size(pol) < r_limit) {
		offset = l_limit + ob_size(pol) +
			cde40_name_len(place->body, l_limit +
				       ob_size(pol), r_limit);
		
		if (offset == r_limit)
			return 0;
		
		offset++;
		
		if (offset - l_limit < ENTRY_LEN_MIN(L_NAME, pol))
			return 0;
		
		l_limit = offset;
		count++;
		
		if (mode != REPAIR_SKIP && 
		    l_limit != cde_get_offset(place, start_pos + count, pol)) 
		{
			fsck_mess("Node (%llu), item (%u), unit (%u), [%s]: "
				  "unit offset (%u) is wrong, should be (%u)."
				  "%s", place_blknr(place), place->pos.item,
				  start_pos + count,
				  print_key(cde40_core, &place->key), 
				  cde_get_offset(place, start_pos + count, pol),
				  l_limit, mode == RM_BUILD ? " Fixed." : "");
			
			if (mode == RM_BUILD) {
				cde_set_offset(place, start_pos + count, 
					       l_limit, pol);
			}
		}
	}
	
	return l_limit == r_limit ? count : 0;
}

static inline uint32_t cde40_entry_detect(reiser4_place_t *place, uint32_t start_pos,
					 uint32_t end_pos, uint8_t mode)
{
	uint32_t pol;
	uint32_t count;

	pol = cde40_key_pol(place);
	count = cde40_short_entry_detect(place, start_pos,
					 cde_get_offset(place, end_pos, pol) - 
					 cde_get_offset(place, start_pos, pol), 
					 0);
    
	if (count == end_pos - start_pos) {
		cde40_short_entry_detect(place, start_pos, 
					 cde_get_offset(place, end_pos, pol) - 
					 cde_get_offset(place, start_pos, pol), 
					 mode);
		
		return count;
	}
	
	count = cde40_long_entry_detect(place, start_pos, 
					cde_get_offset(place, end_pos, pol) - 
					cde_get_offset(place, start_pos, pol), 
					0);
	
	if (count == end_pos - start_pos) {
		cde40_long_entry_detect(place, start_pos, 
					cde_get_offset(place, end_pos, pol) - 
					cde_get_offset(place, start_pos, pol), 
					mode);
		
		return count;
	}
	
	return 0;
}

/* Build a bitmap of not R offstes. */
static errno_t cde40_offsets_range_check(reiser4_place_t *place, 
					 struct entry_flags *flags, 
					 uint8_t mode) 
{
	uint32_t pol;
	uint32_t i, j;
	errno_t res = 0;
	uint32_t to_compare;
	
	aal_assert("vpf-757", flags != NULL);

	pol = cde40_key_pol(place);
	to_compare = MAX_UINT32;
	
	for (i = 0; i < flags->count; i++) {
		/* Check if the offset is valid. */
		if (cde40_offset_check(place, i)) {
			fsck_mess("Node (%llu), item (%u), unit (%u), "
				  "[%s]: unit offset (%u) is wrong.",
				  place_blknr(place), place->pos.item, i,
				  print_key(cde40_core, &place->key),
				  cde_get_offset(place, i, pol));
			
			/* mark offset wrong. */	    
			aal_set_bit(flags->elem + i, NR);
			continue;
		}
		
		/* If there was not any R offset, skip pair comparing. */
		if (to_compare == MAX_UINT32) {
			if ((i == 0) && (cde40_count_estimate(place, i) == 
					 cde_get_units(place)))
			{
				flags->count = cde_get_units(place);
				aal_set_bit(flags->elem + i, R);
			}
			
			to_compare = i;
			continue;
		}
		
		for (j = to_compare; j < i; j++) {
			/* If to_compare is a R element, do just 1 comparing.
			   Otherwise, compare with all not NR elements. */
			if (aal_test_bit(flags->elem + j, NR))
				continue;
			
			/* Check that a pair of offsets is valid. */
			if (!cde40_pair_offsets_check(place, j, i)) {
				/* Pair looks ok. Try to recover it. */
				if (cde40_entry_detect(place, j, i, mode)) {
					uint32_t limit;
					
					/* Do not compair with elements before 
					   the last R. */
					to_compare = i;
					
					/* It's possible to decrease the count 
					   when first R found. */
					limit = cde40_count_estimate(place, j);
					
					if (flags->count > limit)
						flags->count = limit;
					
					/* If more then 1 item were detected, 
					   some offsets have been recovered, 
					   set result properly. */
					if (i - j > 1) {
						if (mode == RM_BUILD)
							place_mkdirty(place);
						else
							res |= RE_FATAL;
					}
					
					/* Mark all recovered elements as R. */
					for (j++; j <= i; j++)
						aal_set_bit(flags->elem + j, R);
					
					break;
				}
				
				continue;
			}
			
			/* Pair does not look ok, if left is R offset, this is 
			   NR offset. */
			if (aal_test_bit(flags->elem + j, R)) {
				aal_set_bit(flags->elem + i, NR);
				break;
			}
		}
	}
	
	return res;
}

static errno_t cde40_filter(reiser4_place_t *place, 
			    struct entry_flags *flags,
			    repair_hint_t *hint)
{
	/* The correct number of units. */
	uint32_t real_count;
	/* Estimated number of units. The maximim possible limit. */
	uint32_t e_count;
	/* Offset within the item. */
	uint32_t offset;
	errno_t res = 0;
	/* The first relable unit offset. */
	uint32_t first;
	/* The last relable unit offset. */
	uint32_t last;
	/* Count of bytes to be removed at the end of the item. */
	uint32_t tail;
	uint32_t pol;
	
	aal_assert("vpf-757", flags != NULL);

	pol = cde40_key_pol(place);
	
	/* Get the last correct unit + 1 into @last. */
	for (last = flags->count; 
	     last && (aal_test_bit(flags->elem + last - 1, NR) || 
		      !aal_test_bit(flags->elem + last - 1, R)); last--) {}
	
	if (last == 0) {
		/* No one R unit was found */
		fsck_mess("Node (%llu), item (%u), [%s]: no one valid unit "
			  "has been found. Does not look like a valid `%s` "
			  "item.", place_blknr(place), place->pos.item, 
			  print_key(cde40_core, &place->key),
			  place->plug->p.label);
		
		return RE_FATAL;
	}
	
	/* the last unit size is not checked yet, so save - 1 into @count. */
	flags->count = --last;
	
	tail = cde_get_offset(place, last, pol);
	offset = tail + ob_size(pol);
	
	/* Last is the last valid offset. If the last unit is valid also, count
	   is the last + 1. */
	if (offset == place->len) {
		flags->count++;
	} else if (offset < place->len) {
		/* The last offset is correct, but the entity is not checked 
		   yet. */
		offset += aal_strlen(place->body + offset) + 1;

		/* If nothing to be removed, the last unit is relable. */
		if (offset == place->len)
			flags->count++;
	} else {
		aal_bug("vpf-1560", "Amount of detected units exceeds the "
			"item length.");
	}
	
	/* Amount of bytes that should be removed at the end. */
	if (flags->count == last) {
		tail = place->len - tail;
	} else {
		tail = 0;
	}

	/* Count is the amount of recovered elements. */
	
	/* Find the first relable. */
	for (first = 0; 
	     first < flags->count && 
	     !aal_test_bit(flags->elem + first, R);
	     first++) {}
	
	/* Estimate the amount of unit headers by the first R element offset. */
	e_count = cde40_count_estimate(place, first);
	
	/* Estimated count must be larger than the recovered count. */
	aal_assert("vpf-765", e_count >= flags->count);
	
	/* If the first unit offset is correct, the correct unit number 
	   is estimated count, otherwise will be changed later. */
	real_count = e_count;
	
	if (first) {
		/* Some first offset are not relable. Consider count as
		   the correct count and set the first offset just after
		   the last unit to remove first items correctly later.*/
		if (hint->mode == RM_BUILD) {