inode.c

EM85XX读NTFS修正代码包

		comp = NTFS_GETU16(src) & 0x8000;
		src += 2;
		stop = src + head;
		bits = 0;
		clear_pos = 0;
		if (head == 0)
			/* Block is not used. */
			return;/* FIXME: copied */
		if (!comp) { /* uncompressible */
			ntfs_memcpy(dest, src, 0x1000);
			dest += 0x1000;
			copied += 0x1000;
			src += 0x1000;
			if (l == copied)
				return;
			continue;
		}
		while (src <= stop) {
			if (clear_pos > 4096) {
				ntfs_error("Error 1 in decompress\n");
				return;
			}
			if (!bits) {
				tag = NTFS_GETU8(src);
				bits = 8;
				src++;
				if (src > stop)
					break;
			}
			if (tag & 1) {
				int i, len, delta, code, lmask, dshift;
				code = NTFS_GETU16(src);
				src += 2;
				if (!clear_pos) {
					ntfs_error("Error 2 in decompress\n");
					return;
				}
				for (i = clear_pos - 1, lmask = 0xFFF,
				     dshift = 12; i >= 0x10; i >>= 1) {
					lmask >>= 1;
					dshift--;
				}
				delta = code >> dshift;
				len = (code & lmask) + 3;
				for (i = 0; i < len; i++) {
					dest[clear_pos] = dest[clear_pos - 
								    delta - 1];
					clear_pos++;
					copied++;
					if (copied==l)
						return;
				}
			} else {
				dest[clear_pos++] = NTFS_GETU8(src);
				src++;
				copied++;
				if (copied==l)
					return;
			}
			tag >>= 1;
			bits--;
		}
		dest += clear_pos;
	}
}

/*
 * NOTE: Neither of the ntfs_*_bit functions are atomic! But we don't need
 * them atomic at present as we never operate on shared/cached bitmaps.
 */
static __inline__ int ntfs_test_bit(unsigned char *byte, const int bit)
{
	return byte[bit >> 3] & (1 << (bit & 7)) ? 1 : 0;
}

static __inline__ void ntfs_set_bit(unsigned char *byte, const int bit)
{
	byte[bit >> 3] |= 1 << (bit & 7);
}

static __inline__ void ntfs_clear_bit(unsigned char *byte, const int bit)
{
	byte[bit >> 3] &= ~(1 << (bit & 7));
}

static __inline__ int ntfs_test_and_clear_bit(unsigned char *byte,
		const int bit)
{
	unsigned char *ptr = byte + (bit >> 3);
	int b = 1 << (bit & 7);
	int oldbit = *ptr & b ? 1 : 0;
	*ptr &= ~b;
	return oldbit;
}

static void dump_runlist(const ntfs_runlist *rl, const int rlen)
{
#ifdef DEBUG
	int i;
	ntfs_cluster_t ct;

	ntfs_debug(DEBUG_OTHER, "%s(): rlen = %i.\n", __FUNCTION__, rlen);
	ntfs_debug(DEBUG_OTHER, "VCN        LCN        Run length\n");
	for (i = 0, ct = 0; i < rlen; ct += rl[i++].len) {
		if (rl[i].lcn == (ntfs_cluster_t)-1)
			ntfs_debug(DEBUG_OTHER, "0x%-8x LCN_HOLE   0x%-8x "
					"(%s)\n", ct, rl[i].len, rl[i].len ?
					"sparse run" : "run list end");
		else
			ntfs_debug(DEBUG_OTHER, "0x%-8x 0x%-8x 0x%-8x%s\n", ct,
					rl[i].lcn, rl[i].len, rl[i].len &&
					i + 1 < rlen ? "" : " (run list end)");
		if (!rl[i].len)
			break;
	}
#endif
}

/**
 * splice_runlists - splice two run lists into one
 * @rl1:	pointer to address of first run list
 * @r1len:	number of elementfs in first run list
 * @rl2:	pointer to second run list
 * @r2len:	number of elements in second run list
 *
 * Append the run list @rl2 to the run list *@rl1 and return the result in
 * *@rl1 and *@r1len.
 *
 * Return 0 on success or -errno on error, in which case *@rl1 and *@r1len are
 * left untouched.
 *
 * The only possible error code at the moment is -ENOMEM and only happens if
 * there is insufficient memory to allocate the new run list (only happens
 * when size of (rl1 + rl2) > allocated size of rl1).
 */
int splice_runlists(ntfs_runlist **rl1, int *r1len, const ntfs_runlist *rl2,
		int r2len)
{
	ntfs_runlist *rl;
	int rlen, rl_size, rl2_pos;

	ntfs_debug(DEBUG_OTHER, "%s(): Entering with *r1len = %i, "
			"r2len = %i.\n", __FUNCTION__, *r1len, r2len);
	ntfs_debug(DEBUG_OTHER, "%s(): Dumping 1st runlist.\n", __FUNCTION__);
	if (*rl1)
		dump_runlist(*rl1, *r1len);
	else
		ntfs_debug(DEBUG_OTHER, "%s(): Not present.\n", __FUNCTION__);
	ntfs_debug(DEBUG_OTHER, "%s(): Dumping 2nd runlist.\n", __FUNCTION__);
	dump_runlist(rl2, r2len);
	rlen = *r1len + r2len + 1;
	rl_size = (rlen * sizeof(ntfs_runlist) + PAGE_SIZE - 1) &
			PAGE_MASK;
	ntfs_debug(DEBUG_OTHER, "%s(): rlen = %i, rl_size = %i.\n",
			__FUNCTION__, rlen, rl_size);
	/* Do we have enough space? */
	if (rl_size <= ((*r1len * sizeof(ntfs_runlist) + PAGE_SIZE - 1) &
			PAGE_MASK)) {
		/* Have enough space already. */
		rl = *rl1;
		ntfs_debug(DEBUG_OTHER, "%s(): Have enough space already.\n",
				__FUNCTION__);
	} else {
		/* Need more space. Reallocate. */
		ntfs_debug(DEBUG_OTHER, "%s(): Need more space.\n",
				__FUNCTION__);
		rl = ntfs_vmalloc(rlen << sizeof(ntfs_runlist));
		if (!rl)
			return -ENOMEM;
		/* Copy over rl1. */
		ntfs_memcpy(rl, *rl1, *r1len * sizeof(ntfs_runlist));
		ntfs_vfree(*rl1);
		*rl1 = rl;
	}
	/* Reuse rl_size as the current position index into rl. */
	rl_size = *r1len - 1;
	ntfs_debug(DEBUG_OTHER, "%s(): rl_size = %i.\n", __FUNCTION__,rl_size);
	/* Coalesce neighbouring elements, if present. */
	rl2_pos = 0;
	if (rl[rl_size].lcn + rl[rl_size].len == rl2[rl2_pos].lcn) {
		ntfs_debug(DEBUG_OTHER, "%s(): Coalescing adjacent runs.\n",
				__FUNCTION__);
		ntfs_debug(DEBUG_OTHER, "%s(): Before: rl[rl_size].len = %i.\n",
				__FUNCTION__, rl[rl_size].len);
		rl[rl_size].len += rl2[rl2_pos].len;
		ntfs_debug(DEBUG_OTHER, "%s(): After: rl[rl_size].len = %i.\n",
				__FUNCTION__, rl[rl_size].len);
		rl2_pos++;
		r2len--;
		rlen--;
	}
	rl_size++;
	/* Copy over rl2. */
	ntfs_memcpy(rl + rl_size, rl2 + rl2_pos, r2len * sizeof(ntfs_runlist));
	rlen--;
	rl[rlen].lcn = (ntfs_cluster_t)-1;
	rl[rlen].len = (ntfs_cluster_t)0;
	*r1len = rlen;
	ntfs_debug(DEBUG_OTHER, "%s(): Dumping result runlist.\n",
			__FUNCTION__);
	dump_runlist(*rl1, *r1len);
	ntfs_debug(DEBUG_OTHER, "%s(): Returning with *r1len = %i.\n",
			__FUNCTION__, rlen);
	return 0;
}

/**
 * ntfs_alloc_mft_record - allocate an mft record
 * @vol:	volume to allocate an mft record on
 * @result:	the mft record number allocated
 *
 * Allocate a new mft record on disk. Return 0 on success or -ERRNO on error.
 * On success, *@result contains the allocated mft record number. On error,
 * *@result is -1UL.
 *
 * Note, this function doesn't actually set the mft record to be in use. This
 * is done by the caller, which at the moment is only ntfs_alloc_inode().
 *
 * To find a free mft record, we scan the mft bitmap for a zero bit. To
 * optimize this we start scanning at the place where we last stopped and we
 * perform wrap around when we reach the end. Note, we do not try to allocate
 * mft records below number 24 because numbers 0 to 15 are the defined system
 * files anyway and 16 to 24 are special in that they are used for storing
 * extension mft records for $MFT's $DATA attribute. This is required to avoid
 * the possibility of creating a run list with a circular dependence which once
 * written to disk can never be read in again. Windows will only use records
 * 16 to 24 for normal files if the volume is completely out of space. We never
 * use them which means that when the volume is really out of space we cannot
 * create any more files while Windows can still create up to 8 small files. We
 * can start doing this at some later time, doesn't matter much for now.
 *
 * When scanning the mft bitmap, we only search up to the last allocated mft
 * record. If there are no free records left in the range 24 to number of
 * allocated mft records, then we extend the mft data in order to create free
 * mft records. We extend the allocated size of $MFT/$DATA by 16 records at a
 * time or one cluster, if cluster size is above 16kiB. If there isn't
 * sufficient space to do this, we try to extend by a single mft record or one
 * cluster, if cluster size is above mft record size, but we only do this if
 * there is enough free space, which we know from the values returned by the
 * failed cluster allocation function when we tried to do the first allocation.
 *
 * No matter how many mft records we allocate, we initialize only the first
 * allocated mft record (incrementing mft data size and initialized size) and
 * return its number to the caller in @*result, unless there are less than 24
 * mft records, in which case we allocate and initialize mft records until we
 * reach record 24 which we consider as the first free mft record for use by
 * normal files.
 *
 * If during any stage we overflow the initialized data in the mft bitmap, we
 * extend the initialized size (and data size) by 8 bytes, allocating another
 * cluster if required. The bitmap data size has to be at least equal to the
 * number of mft records in the mft, but it can be bigger, in which case the
 * superflous bits are padded with zeroes.
 *
 * Thus, when we return successfully (return value 0), we will have:
 *	- initialized / extended the mft bitmap if necessary,
 *	- initialized / extended the mft data if necessary,
 *	- set the bit corresponding to the mft record being allocated in the
 *	  mft bitmap, and we will
 *	- return the mft record number in @*result.
 *
 * On error (return value below zero), nothing will have changed. If we had
 * changed anything before the error occured, we will have reverted back to
 * the starting state before returning to the caller. Thus, except for bugs,
 * we should always leave the volume in a consitents state when returning from
 * this function. NOTE: Small exception to this is that we set the bit in the
 * mft bitmap but we do not mark the mft record in use, which is inconsistent.
 * However, the caller will immediately add the wanted attributes to the mft
 * record, set it in use and write it out to disk, so there should be no
 * problem.
 *
 * Note, this function cannot make use of most of the normal functions, like
 * for example for attribute resizing, etc, because when the run list overflows
 * the base mft record and an attribute list is used, it is very important
 * that the extension mft records used to store the $DATA attribute of $MFT
 * can be reached without having to read the information contained inside
 * them, as this would make it impossible to find them in the first place
 * after the volume is dismounted. $MFT/$BITMAP probably doesn't need to
 * follow this rule because the bitmap is not essential for finding the mft
 * records, but on the other hand, handling the bitmap in this special way
 * would make life easier because otherwise there might be circular invocations
 * of functions when reading the bitmap but if we are careful, we should be
 * able to avoid all problems.
 *
 * FIXME: Don't forget $MftMirr, though this probably belongs in
 *	  ntfs_update_inode() (or even deeper). (AIA)
 *
 * FIXME: Want finer grained locking. (AIA)
 */
static int ntfs_alloc_mft_record(ntfs_volume *vol, unsigned long *result)
{
	unsigned long nr_mft_records, buf_size, buf_pos, pass_start, pass_end;
	unsigned long last_read_pos, mft_rec_size, bit, l;
	ntfs_attribute *data, *bmp;
	__u8 *buf, *byte, pass, b, have_allocated_mftbmp = 0;
	int rlen, rl_size = 0, r2len, rl2_size, old_data_rlen, err = 0;
	ntfs_runlist *rl, *rl2;
	ntfs_cluster_t lcn = 0, old_data_len;
	ntfs_io io;
	__s64 ll, old_data_allocated, old_data_initialized, old_data_size;

	*result = -1UL;
	/* Allocate a buffer and setup the io structure. */
	buf = (__u8*)__get_free_page(GFP_NOFS);
	if (!buf)
		return -ENOMEM;
	lock_kernel();
	/* Get the $DATA and $BITMAP attributes of $MFT. */
	data = ntfs_find_attr(vol->mft_ino, vol->at_data, 0);
	bmp = ntfs_find_attr(vol->mft_ino, vol->at_bitmap, 0);
	if (!data || !bmp) {
		err = -EINVAL;
		goto err_ret;
	}
	/* Determine the number of allocated mft records in the mft. */
	pass_end = nr_mft_records = data->allocated >>
			vol->mft_record_size_bits;
	ntfs_debug(DEBUG_OTHER, "%s(): nr_mft_records = %lu.\n", __FUNCTION__,
			nr_mft_records);
	/* Make sure we don't overflow the bitmap. */
	l = bmp->initialized << 3;
	if (l < nr_mft_records)
		// FIXME: It might be a good idea to extend the bitmap instead.
		pass_end = l;
	pass = 1;
	buf_pos = vol->mft_data_pos;
	if (buf_pos >= pass_end) {
		buf_pos = 24UL;
		pass = 2;
	}
	pass_start = buf_pos;
	rl = bmp->d.r.runlist;
	rlen = bmp->d.r.len - 1;
	lcn = rl[rlen].lcn + rl[rlen].len;
	io.fn_put = ntfs_put;
	io.fn_get = ntfs_get;
	ntfs_debug(DEBUG_OTHER, "%s(): Starting bitmap search.\n",
			__FUNCTION__);
	ntfs_debug(DEBUG_OTHER, "%s(): pass = %i, pass_start = %lu, pass_end = "
			"%lu.\n", __FUNCTION__, pass, pass_start, pass_end);
	byte = NULL; // FIXME: For debugging only.
	/* Loop until a free mft record is found. */
	io.size = (nr_mft_records >> 3) & ~PAGE_MASK;
	for (;; io.size = PAGE_SIZE) {
		io.param = buf;
		io.do_read = 1;
		last_read_pos = buf_pos >> 3;
		ntfs_debug(DEBUG_OTHER, "%s(): Before: bmp->allocated = 0x%Lx, "
				"bmp->size = 0x%Lx, bmp->initialized = "
				"0x%Lx.\n", __FUNCTION__, bmp->allocated,
				bmp->size, bmp->initialized);
		err = ntfs_readwrite_attr(vol->mft_ino, bmp, last_read_pos,
				&io);
		if (err)
			goto err_ret;
		ntfs_debug(DEBUG_OTHER, "%s(): Read %lu bytes.\n", __FUNCTION__,
				(unsigned long)io.size);
		ntfs_debug(DEBUG_OTHER, "%s(): After: bmp->allocated = 0x%Lx, "
				"bmp->size = 0x%Lx, bmp->initialized = "
				"0x%Lx.\n", __FUNCTION__, bmp->allocated,
				bmp->size, bmp->initialized);
		if (!io.size)
			goto pass_done;
		buf_size = io.size << 3;
		bit = buf_pos & 7UL;
		buf_pos &= ~7UL;
		ntfs_debug(DEBUG_OTHER, "%s(): Before loop: buf_size = %lu, "
				"buf_pos = %lu, bit = %lu, *byte = 0x%x, b = "
				"%u.\n", __FUNCTION__, buf_size, buf_pos, bit,
				byte ? *byte : -1, b);
		for (; bit < buf_size && bit + buf_pos < pass_end;
				bit &= ~7UL, bit += 8UL) {
			byte = buf + (bit >> 3);
			if (*byte == 0xff)
				continue;
			b = ffz((unsigned long)*byte);
			if (b < (__u8)8 && b >= (bit & 7UL)) {
				bit = b + (bit & ~7UL) + buf_pos;
				ntfs_debug(DEBUG_OTHER, "%s(): Found free rec "
						"in for loop. bit = %lu\n",
						__FUNCTION__, bit);
				goto found_free_rec;
			}
		}
		ntfs_debug(DEBUG_OTHER, "%s(): After loop: buf_size = %lu, "
				"buf_pos = %lu, bit = %lu, *byte = 0x%x, b = "
				"%u.\n", __FUNCTION__, buf_size, buf_pos, bit,
				byte ? *byte : -1, b);
		buf_pos += buf_size;
		if (buf_pos < pass_end)
			continue;
pass_done:	/* Finished with the current pass. */
		ntfs_debug(DEBUG_OTHER, "%s(): At pass_done.\n", __FUNCTION__);
		if (pass == 1) {
			/*
			 * Now do pass 2, scanning the first part of the zone
			 * we omitted in pass 1.
			 */
			ntfs_debug(DEBUG_OTHER, "%s(): Done pass 1.\n",
					__FUNCTION__);
			ntfs_debug(DEBUG_OTHER, "%s(): Pass = 2.\n",
					__FUNCTION__);
			pass = 2;
			pass_end = pass_start;
			buf_pos = pass_start = 24UL;
			ntfs_debug(DEBUG_OTHER, "%s(): pass = %i, pass_start = "
					"%lu, pass_end = %lu.\n", __FUNCTION__,
					pass, pass_start, pass_end);
			continue;
		} /* pass == 2 */
		/* No free records left. */