/*
* dir.c
*
* Copyright (C) 1995-1997, 1999 Martin von Löwis
* Copyright (C) 1999 Steve Dodd
* Copyright (C) 1999 Joseph Malicki
* Copyright (C) 2001 Anton Altaparmakov (AIA)
*/
#include "ntfstypes.h"
#include "struct.h"
#include "dir.h"
#include "macros.h"
#include <linux/errno.h>
#include "super.h"
#include "inode.h"
#include "attr.h"
#include "support.h"
#include "util.h"
#include <linux/smp_lock.h>
#include <linux/bitops.h>
static char I30[] = "$I30";
/* An index record should start with INDX, and the last word in each block
* should contain the check value. If it passes, the original values need to
* be restored. */
int ntfs_check_index_record(ntfs_inode *ino, char *record)
{
return ntfs_fixup_record(record, "INDX", ino->u.index.recordsize);
}
static inline int ntfs_is_top(ntfs_u64 stack)
{
return stack == 14;
}
static int ntfs_pop(ntfs_u64 *stack)
{
static int width[16] = {1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,-1};
int res = -1;
switch (width[*stack & 15]) {
case 1:
res = (int)((*stack & 15) >> 1);
*stack >>= 4;
break;
case 2:
res = (int)(((*stack & 63) >> 2) + 7);
*stack >>= 6;
break;
case 3:
res = (int)(((*stack & 255) >> 3) + 23);
*stack >>= 8;
break;
case 4:
res = (int)(((*stack & 1023) >> 4) + 55);
*stack >>= 10;
break;
default:
ntfs_error("Unknown encoding\n");
}
return res;
}
static inline unsigned int ntfs_top(void)
{
return 14;
}
static ntfs_u64 ntfs_push(ntfs_u64 stack, int i)
{
if (i < 7)
return (stack << 4) | (i << 1);
if (i < 23)
return (stack << 6) | ((i - 7) << 2) | 1;
if (i < 55)
return (stack << 8) | ((i - 23) << 3) | 3;
if (i < 120)
return (stack << 10) | ((i - 55) << 4) | 7;
ntfs_error("Too many entries\n");
return ~((ntfs_u64)0);
}
#if 0
static void ntfs_display_stack(ntfs_u64 stack)
{
while(!ntfs_is_top(stack))
{
printf("%d ", ntfs_pop(&stack));
}
printf("\n");
}
#endif
/* True if the entry points to another block of entries. */
static inline int ntfs_entry_has_subnodes(char *entry)
{
return (NTFS_GETU16(entry + 0xc) & 1);
}
/* True if it is not the 'end of dir' entry. */
static inline int ntfs_entry_is_used(char *entry)
{
return !(NTFS_GETU16(entry + 0xc) & 2);
}
/*
* Removed RACE for allocating index blocks. But stil not too happy.
* There might be more races afterwards. (AIA)
*/
static int ntfs_allocate_index_block(ntfs_iterate_s *walk)
{
ntfs_attribute *allocation, *bitmap = 0;
int error, size, i, bit;
ntfs_u8 *bmap;
ntfs_io io;
ntfs_volume *vol = walk->dir->vol;
/* Check for allocation attribute. */
allocation = ntfs_find_attr(walk->dir, vol->at_index_allocation, I30);
if (!allocation) {
ntfs_u8 bmp[8];
/* Create index allocation attribute. */
error = ntfs_create_attr(walk->dir, vol->at_index_allocation,
I30, 0, 0, &allocation);
if (error)
goto err_ret;
ntfs_bzero(bmp, sizeof(bmp));
error = ntfs_create_attr(walk->dir, vol->at_bitmap, I30, bmp,
sizeof(bmp), &bitmap);
if (error)
goto err_ret;
} else
bitmap = ntfs_find_attr(walk->dir, vol->at_bitmap, I30);
if (!bitmap) {
ntfs_error("Directory w/o bitmap\n");
error = -EINVAL;
goto err_ret;
}
size = bitmap->size;
bmap = ntfs_malloc(size);
if (!bmap) {
error = -ENOMEM;
goto err_ret;
}
io.fn_put = ntfs_put;
io.fn_get = ntfs_get;
try_again:
io.param = bmap;
io.size = size;
error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, 0, &io);
if (error || (io.size != size && (error = -EIO, 1)))
goto err_fb_out;
/* Allocate a bit. */
for (bit = i = 0; i < size; i++) {
if (bmap[i] == 0xFF)
continue;
bit = ffz(bmap[i]);
if (bit < 8)
break;
}
if (i >= size) {
/* FIXME: Extend bitmap. */
error = -EOPNOTSUPP;
goto err_fb_out;
}
/* Get the byte containing our bit again, now taking the BKL. */
io.param = bmap;
io.size = 1;
lock_kernel();
error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, i, &io);
if (error || (io.size != 1 && (error = -EIO, 1)))
goto err_unl_out;
if (ntfs_test_and_set_bit(bmap, bit)) {
unlock_kernel();
/* Give other process(es) a chance to finish. */
schedule();
goto try_again;
}
walk->newblock = (i * 8 + bit) * walk->dir->u.index.clusters_per_record;
io.param = bmap;
error = ntfs_write_attr(walk->dir, vol->at_bitmap, I30, i, &io);
if (error || (io.size != size && (error = -EIO, 1)))
goto err_unl_out;
/* Change inode on disk, required when bitmap is resident. */
error = ntfs_update_inode(walk->dir);
if (error)
goto err_unl_out;
unlock_kernel();
ntfs_free(bmap);
/* Check whether record is out of allocated range. */
size = allocation->size;
if (walk->newblock * vol->cluster_size >= size) {
/* Build index record. */
int hsize;
int s1 = walk->dir->u.index.recordsize;
int nr_fix = (s1 >> vol->sector_size) + 1;
char *record = ntfs_malloc(s1);
if (!record) {
error = -ENOMEM;
goto err_ret;
}
ntfs_bzero(record, s1);
/* Magic */
ntfs_memcpy(record, "INDX", 4);
/* Offset to fixups */
NTFS_PUTU16(record + 4, 0x28);
/* Number of fixups. */
NTFS_PUTU16(record + 6, nr_fix);
/* Log file sequence number - We don't do journalling so we
* just set it to zero which should be the Right Thing. (AIA) */
NTFS_PUTU64(record + 8, 0);
/* VCN of buffer */
NTFS_PUTU64(record + 0x10, walk->newblock);
/* Header size. */
hsize = 0x10 + 2 * nr_fix;
hsize = (hsize + 7) & ~7; /* Align. */
NTFS_PUTU16(record + 0x18, hsize);
/* Total size of record. */
NTFS_PUTU32(record + 0x20, s1 - 0x18);
/* Writing the data will extend the attribute. */
io.param = record;
io.size = s1;
io.do_read = 0;
error = ntfs_readwrite_attr(walk->dir, allocation, size, &io);
ntfs_free(record);
if (error || (io.size != s1 && (error = -EIO, 1)))
goto err_ret;
error = ntfs_update_inode(walk->dir);
if (error)
goto err_ret;
}
return 0;
err_unl_out:
unlock_kernel();
err_fb_out:
ntfs_free(bmap);
err_ret:
return error;
}
/* Write an index block (root or allocation) back to storage.
* Used is the total number of bytes in buf, including all headers. */
static int ntfs_index_writeback(ntfs_iterate_s *walk, ntfs_u8 *buf, int block,
int used)
{
ntfs_io io;
int error;
ntfs_attribute *a;
ntfs_volume *vol = walk->dir->vol;
io.fn_put = 0;
io.fn_get = ntfs_get;
io.param = buf;
if (block == -1) { /* Index root. */
NTFS_PUTU16(buf + 0x14, used - 0x10);
/* 0x18 is a copy thereof. */
NTFS_PUTU16(buf + 0x18, used - 0x10);
io.size = used;
error = ntfs_write_attr(walk->dir, vol->at_index_root, I30, 0,
&io);
if (error || (io.size != used && (error = -EIO, 1)))
return error;
/* Shrink if necessary. */
a = ntfs_find_attr(walk->dir, vol->at_index_root, I30);
ntfs_resize_attr(walk->dir, a, used);
} else {
NTFS_PUTU16(buf + 0x1C, used - 0x18);
io.size = walk->dir->u.index.recordsize;
error = ntfs_insert_fixups(buf, io.size);
if (error) {
printk(KERN_ALERT "NTFS: ntfs_index_writeback() caught "
"corrupt index record ntfs record "
"header. Refusing to write corrupt "
"data to disk. Unmount and run chkdsk "
"immediately!\n");
return -EIO;
}
error = ntfs_write_attr(walk->dir, vol->at_index_allocation,
I30, (__s64)block << vol->cluster_size_bits,
&io);
if (error || (io.size != walk->dir->u.index.recordsize &&
(error = -EIO, 1)))
return error;
}
return 0;
}
static int ntfs_split_record(ntfs_iterate_s *walk, char *start, int bsize,
int usize)
{
char *entry, *prev;
ntfs_u8 *newbuf = 0, *middle = 0;
int error, othersize, mlen;
ntfs_io io;
ntfs_volume *vol = walk->dir->vol;
int oldblock;
error = ntfs_allocate_index_block(walk);
if (error)
return error;
/* This should not happen. */
if (walk->block == -1) {
ntfs_error("Trying to split root");
return -EOPNOTSUPP;
}
entry = start + NTFS_GETU16(start + 0x18) + 0x18;
for (prev = entry; entry - start < usize / 2;
entry += NTFS_GETU16(entry + 8))
prev = entry;
newbuf = ntfs_malloc(vol->index_record_size);
if (!newbuf)
return -ENOMEM;
io.fn_put = ntfs_put;
io.fn_get = ntfs_get;
io.param = newbuf;
io.size = vol->index_record_size;
/* Read in old header. FIXME: Reading everything is overkill. */
error = ntfs_read_attr(walk->dir, vol->at_index_allocation, I30,
(__s64)walk->newblock << vol->cluster_size_bits, &io);
if (error)
goto out;
if (io.size != vol->index_record_size) {
error = -EIO;
goto out;
}
/* FIXME: Adjust header. */
/* Copy everything from entry to new block. */
othersize = usize - (entry - start);
ntfs_memcpy(newbuf + NTFS_GETU16(newbuf + 0x18) + 0x18, entry,
othersize);
/* Copy flags. */
NTFS_PUTU32(newbuf + 0x24, NTFS_GETU32(start + 0x24));
error = ntfs_index_writeback(walk, newbuf, walk->newblock,
othersize + NTFS_GETU16(newbuf + 0x18) + 0x18);
if (error)
goto out;
/* Move prev to walk. */
mlen = NTFS_GETU16(prev + 0x8);
/* Remember old child node. */
if (ntfs_entry_has_subnodes(prev))
oldblock = NTFS_GETU32(prev + mlen - 8);
else
oldblock = -1;
/* Allow for pointer to subnode. */
middle = ntfs_malloc(ntfs_entry_has_subnodes(prev) ? mlen : mlen + 8);
if (!middle){
error = -ENOMEM;
goto out;
}
ntfs_memcpy(middle, prev, mlen);
/* Set has_subnodes flag. */
NTFS_PUTU8(middle + 0xC, NTFS_GETU8(middle + 0xC) | 1);
/* Middle entry points to block, parent entry will point to newblock. */
NTFS_PUTU64(middle + mlen - 8, walk->block);
if (walk->new_entry)
ntfs_error("Entry not reset");
walk->new_entry = middle;
walk->u.flags |= ITERATE_SPLIT_DONE;
/* Terminate old block. */
othersize = usize - (prev-start);
NTFS_PUTU64(prev, 0);
if (oldblock == -1) {
NTFS_PUTU32(prev + 8, 0x10);
NTFS_PUTU32(prev + 0xC, 2);
othersize += 0x10;
} else {
NTFS_PUTU32(prev + 8, 0x18);
NTFS_PUTU32(prev + 0xC, 3);
NTFS_PUTU64(prev + 0x10, oldblock);
othersize += 0x18;
}
/* Write back original block. */
error = ntfs_index_writeback(walk, start, walk->block, othersize);
out:
if (newbuf)
ntfs_free(newbuf);
if (middle)
ntfs_free(middle);
return error;
}
static int ntfs_dir_insert(ntfs_iterate_s *walk, char *start, char* entry)
{
int blocksize, usedsize, error, offset;
int do_split = 0;
offset = entry - start;
if (walk->block == -1) { /* index root */
blocksize = walk->dir->vol->mft_record_size;
usedsize = NTFS_GETU16(start + 0x14) + 0x10;
} else {
blocksize = walk->dir->u.index.recordsize;
usedsize = NTFS_GETU16(start + 0x1C) + 0x18;
}
if (usedsize + walk->new_entry_size > blocksize) {
char* s1 = ntfs_malloc(blocksize + walk->new_entry_size);
if (!s1)
return -ENOMEM;
ntfs_memcpy(s1, start, usedsize);
do_split = 1;
/* Adjust entry to s1. */
entry = s1 + (entry - start);
start = s1;
}
ntfs_memmove(entry + walk->new_entry_size, entry, usedsize - offset);
ntfs_memcpy(entry, walk->new_entry, walk->new_entry_size);
usedsize += walk->new_entry_size;
ntfs_free(walk->new_entry);
walk->new_entry = 0;
if (do_split) {
error = ntfs_split_record(walk, start, blocksize, usedsize);
ntfs_free(start);
} else {
error = ntfs_index_writeback(walk, start, walk->block,usedsize);
if (error)
return error;
}
return 0;
}
/* Try to split INDEX_ROOT attributes. Return -E2BIG if nothing changed. */
int ntfs_split_indexroot(ntfs_inode *ino)
{
ntfs_attribute *ra;
ntfs_u8 *root = 0, *index = 0;
ntfs_io io;
int error, off, i, bsize, isize;
ntfs_iterate_s walk;
ra = ntfs_find_attr(ino, ino->vol->at_index_root, I30);
if (!ra)
return -ENOTDIR;
bsize = ino->vol->mft_record_size;
root = ntfs_malloc(bsize);
if (!root)
return -E2BIG;
io.fn_put = ntfs_put;
io.param = root;
io.size = bsize;
error = ntfs_read_attr(ino, ino->vol->at_index_root, I30, 0, &io);
if (error)
goto out;
off = 0x20;
/* Count number of entries. */
for (i = 0; ntfs_entry_is_used(root + off); i++)
off += NTFS_GETU16(root + off + 8);
if (i <= 2) {
/* We don't split small index roots. */
error = -E2BIG;
goto out;
}
index = ntfs_malloc(ino->vol->index_record_size);
if (!index) {
error = -ENOMEM;
goto out;
}
walk.dir = ino;
walk.block = -1;
walk.result = walk.new_entry = 0;
walk.name = 0;
error = ntfs_allocate_index_block(&walk);
if (error)
goto out;
/* Write old root to new index block. */
io.param = index;
io.size = ino->vol->index_record_size;
error = ntfs_read_attr(ino, ino->vol->at_index_allocation, I30,
(__s64)walk.newblock << ino->vol->cluster_size_bits, &io);
if (error)
goto out;
isize = NTFS_GETU16(root + 0x18) - 0x10;
ntfs_memcpy(index + NTFS_GETU16(index + 0x18) + 0x18, root+0x20, isize);
/* Copy flags. */
NTFS_PUTU32(index + 0x24, NTFS_GETU32(root + 0x1C));
error = ntfs_index_writeback(&walk, index, walk.newblock,
isize + NTFS_GETU16(index + 0x18) + 0x18);
if (error)
goto out;
/* Mark root as split. */
NTFS_PUTU32(root + 0x1C, 1);
/* Truncate index root. */
NTFS_PUTU64(root + 0x20, 0);
NTFS_PUTU32(root + 0x28, 0x18);
NTFS_PUTU32(root + 0x2C, 3);
NTFS_PUTU64(root + 0x30, walk.newblock);
error = ntfs_index_writeback(&walk, root, -1, 0x38);
out:
ntfs_free(root);
ntfs_free(index);
return error;
}
/* The entry has been found. Copy the result in the caller's buffer */
static int ntfs_copyresult(char *dest, char *source)
{
int length = NTFS_GETU16(source + 8);
ntfs_memcpy(dest, source, length);
return 1;
}
/* Use $UpCase some day. */
static inline unsigned short ntfs_my_toupper(ntfs_volume *vol, ntfs_u16 x)
{
/* We should read any pending rest of $UpCase here. */
if (x >= vol->upcase_length)
return x;
return vol->upcase[x];
}
/* Everything passed in walk and entry. */
static int ntfs_my_strcmp(ntfs_iterate_s *walk, const unsigned char *entry)
{
int lu = *(entry + 0x50);
int i;
ntfs_u16* name = (ntfs_u16*)(entry + 0x52);
ntfs_volume *vol = walk->dir->vol;
for (i = 0; i < lu && i < walk->namelen; i++)
if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) !=
ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
break;
if (i == lu && i == walk->namelen)
return 0;
if (i == lu)
return 1;
if (i == walk->namelen)
return -1;
if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) <
ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
return 1;
return -1;
}
/* Necessary forward declaration. */
static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);
/* Parse a block of entries. Load the block, fix it up, and iterate over the
* entries. The block is given as virtual cluster number. */
static int ntfs_getdir_record(ntfs_iterate_s *walk, int block)
{
int length = walk->dir->u.index.recordsize;
char *record = (char*)ntfs_malloc(length);
char *offset;
int retval,error;
int oldblock;
ntfs_io io;
if (!record)
return -ENOMEM;
io.fn_put = ntfs_put;
io.param = record;
io.size = length;
/* Read the block from the index allocation attribute. */
error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_allocation,
I30, (__s64)block << walk->dir->vol->cluster_size_bits, &io);
if (error || io.size != length) {
ntfs_error("read failed\n");
ntfs_free(record);
return 0;
}
if (!ntfs_check_index_record(walk->dir, record)) {
ntfs_error("%x is not an index record\n", block);
ntfs_free(record);
return 0;
}
offset = record + NTFS_GETU16(record + 0x18) + 0x18;
oldblock = walk->block;
walk->block = block;
retval = ntfs_getdir_iterate(walk, record, offset);
walk->block = oldblock;
ntfs_free(record);
return retval;
}
/* Go down to the next block of entries. These collate before the current
* entry. */
static int ntfs_descend(ntfs_iterate_s *walk, ntfs_u8 *start, ntfs_u8 *entry)
{
int length = NTFS_GETU16(entry + 8);
int nextblock = NTFS_GETU32(entry + length - 8);
int error;
if (!ntfs_entry_has_subnodes(entry)) {
ntfs_error("illegal ntfs_descend call\n");
return 0;
}
error = ntfs_getdir_record(walk, nextblock);
if (!error && walk->type == DIR_INSERT &&
(walk->u.flags & ITERATE_SPLIT_DONE)) {
/* Split has occurred. Adjust entry, insert new_entry. */
NTFS_PUTU32(entry + length - 8, walk->newblock);
/* Reset flags, as the current block might be split again. */
walk->u.flags &= ~ITERATE_SPLIT_DONE;
error = ntfs_dir_insert(walk, start, entry);
}
return error;
}
static int ntfs_getdir_iterate_byposition(ntfs_iterate_s *walk, char* start,
char *entry)
{
int retval = 0;
int curpos = 0, destpos = 0;
int length;
if (walk->u.pos != 0) {
if (ntfs_is_top(walk->u.pos))
return 0;
destpos = ntfs_pop(&walk->u.pos);
}
while (1) {
if (walk->u.pos == 0) {
if (ntfs_entry_has_subnodes(entry))
ntfs_descend(walk, start, entry);
else
walk->u.pos = ntfs_top();
if (ntfs_is_top(walk->u.pos) &&
!ntfs_entry_is_used(entry))
return 1;
walk->u.pos = ntfs_push(walk->u.pos, curpos);
return 1;
}
if (curpos == destpos) {
if (!ntfs_is_top(walk->u.pos) &&
ntfs_entry_has_subnodes(entry)) {
retval = ntfs_descend(walk, start, entry);
if (retval) {
walk->u.pos = ntfs_push(walk->u.pos,
curpos);
return retval;
}
if (!ntfs_entry_is_used(entry))
return 0;
walk->u.pos = 0;
}
if (ntfs_entry_is_used(entry)) {
retval = ntfs_copyresult(walk->result, entry);
walk->u.pos = 0;
} else {
walk->u.pos = ntfs_top();
return 0;
}
}
curpos++;
if (!ntfs_entry_is_used(entry))
break;
length = NTFS_GETU16(entry + 8);
if (!length) {
ntfs_error("infinite loop\n");
break;
}
entry += length;
}
return -1;
}
/* Iterate over a list of entries, either from an index block, or from the
* index root.
* If searching BY_POSITION, pop the top index from the position. If the
* position stack is empty then, return the item at the index and set the
* position to the next entry. If the position stack is not empty,
* recursively proceed for subnodes. If the entry at the position is the
* 'end of dir' entry, return 'not found' and the empty stack.
* If searching BY_NAME, walk through the items until found or until
* one item is collated after the requested item. In the former case, return
* the result. In the latter case, recursively proceed to the subnodes.
* If 'end of dir' is reached, the name is not in the directory */
static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry)
{
int length;
int cmp;
if (walk->type == BY_POSITION)
return ntfs_getdir_iterate_byposition(walk, start, entry);
do {
/* If the current entry is a real one, compare with the
* requested item. If the current entry is the last item, it
* is always larger than the requested item. */
cmp = ntfs_entry_is_used(entry) ?
ntfs_my_strcmp(walk,entry) : -1;
switch (walk->type) {
case BY_NAME:
switch (cmp) {
case -1:
return ntfs_entry_has_subnodes(entry) ?
ntfs_descend(walk, start, entry) : 0;
case 0:
return ntfs_copyresult(walk->result, entry);
case 1:
break;
}
break;
case DIR_INSERT:
switch (cmp) {
case -1:
return ntfs_entry_has_subnodes(entry) ?
ntfs_descend(walk, start, entry) :
ntfs_dir_insert(walk, start, entry);
case 0:
return -EEXIST;
case 1:
break;
}
break;
default:
ntfs_error("TODO\n"); /* FIXME: ? */
}
if (!ntfs_entry_is_used(entry))
break;
length = NTFS_GETU16(entry + 8);
if (!length) {
ntfs_error("infinite loop\n");
break;
}
entry += length;
} while (1);
return 0;
}
/* Tree walking is done using position numbers. The following numbers have a
* special meaning:
* 0 start (.)
* -1 no more entries
* -2 ..
* All other numbers encode sequences of indices. The sequence a, b, c is
* encoded as <stop><c><b><a>, where <foo> is the encoding of foo. The
* first few integers are encoded as follows:
* 0: 0000 1: 0010 2: 0100 3: 0110
* 4: 1000 5: 1010 6: 1100 stop: 1110
* 7: 000001 8: 000101 9: 001001 10: 001101
* The least significant bits give the width of this encoding, the other bits
* encode the value, starting from the first value of the interval.
* tag width first value last value
* 0 3 0 6
* 01 4 7 22
* 011 5 23 54
* 0111 6 55 119
* More values are hopefully not needed, as the file position has currently
* 64 bits in total. */
/* Find an entry in the directory. Return 0 if not found, otherwise copy the
* entry to the result buffer. */
int ntfs_getdir(ntfs_iterate_s *walk)
{
int length = walk->dir->vol->mft_record_size;
int retval, error;
/* Start at the index root. */
char *root = ntfs_malloc(length);
ntfs_io io;
if (!root)
return -ENOMEM;
io.fn_put = ntfs_put;
io.param = root;
io.size = length;
error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_root, I30,
0, &io);
if (error) {
ntfs_error("Not a directory\n");
return 0;
}
walk->block = -1;
/* FIXME: Move these to walk. */
walk->dir->u.index.recordsize = NTFS_GETU32(root + 0x8);
walk->dir->u.index.clusters_per_record = NTFS_GETU32(root + 0xC);
/* FIXME: Consistency check. */
/* Skip header. */
retval = ntfs_getdir_iterate(walk, root, root + 0x20);
ntfs_free(root);
return retval;
}
/* Find an entry in the directory by its position stack. Iteration starts
* if the stack is 0, in which case the position is set to the first item
* in the directory. If the position is nonzero, return the item at the
* position and change the position to the next item. The position is -1
* if there are no more items. */
int ntfs_getdir_byposition(ntfs_iterate_s *walk)
{
walk->type = BY_POSITION;
return ntfs_getdir(walk);
}
/* Find an entry in the directory by its name. Return 0 if not found. */
int ntfs_getdir_byname(ntfs_iterate_s *walk)
{
walk->type = BY_NAME;
return ntfs_getdir(walk);
}
int ntfs_getdir_unsorted(ntfs_inode *ino, u32 *p_high, u32 *p_low,
int (*cb)(ntfs_u8 *, void *), void *param)
{
s64 ib_ofs;
char *buf = 0, *entry = 0;
ntfs_attribute *attr;
ntfs_volume *vol;
int byte, bit, err = 0;
u32 start, finish, ibs, max_size;
ntfs_io io;
u8 ibs_bits;
if (!ino) {
ntfs_error("%s(): No inode! Returning -EINVAL.\n",__FUNCTION__);
return -EINVAL;
}
vol = ino->vol;
if (!vol) {
ntfs_error("%s(): Inode 0x%lx has no volume. Returning "
"-EINVAL.\n", __FUNCTION__, ino->i_number);
return -EINVAL;
}
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 1: Entering for inode 0x%lx, "
"p_high = 0x%x, p_low = 0x%x.\n", __FUNCTION__,
ino->i_number, *p_high, *p_low);
if (!*p_high) {
/* We are still in the index root. */
buf = ntfs_malloc(io.size = vol->mft_record_size);
if (!buf)
return -ENOMEM;
io.fn_put = ntfs_put;
io.param = buf;
err = ntfs_read_attr(ino, vol->at_index_root, I30, 0, &io);
if (err || !io.size)
goto read_err_ret;
ino->u.index.recordsize = ibs = NTFS_GETU32(buf + 0x8);
ino->u.index.clusters_per_record = NTFS_GETU32(buf + 0xC);
entry = buf + 0x20;
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 2: In index root.\n",
__FUNCTION__);
ibs_bits = ffs(ibs) - 1;
/* Compensate for faked "." and "..". */
start = 2;
} else { /* We are in an index record. */
io.size = ibs = ino->u.index.recordsize;
buf = ntfs_malloc(ibs);
if (!buf)
return -ENOMEM;
ibs_bits = ffs(ibs) - 1;
io.fn_put = ntfs_put;
io.param = buf;
/*
* 0 is index root, index allocation starts at 1 and works in
* units of index block size (ibs).
*/
ib_ofs = (s64)(*p_high - 1) << ibs_bits;
err = ntfs_read_attr(ino, vol->at_index_allocation, I30, ib_ofs,
&io);
if (err || io.size != ibs)
goto read_err_ret;
if (!ntfs_check_index_record(ino, buf)) {
ntfs_error("%s(): Index block 0x%x is not an index "
"record. Returning -ENOTDIR.\n",
__FUNCTION__, *p_high - 1);
ntfs_free(buf);
return -ENOTDIR;
}
entry = buf + 0x18 + NTFS_GETU16(buf + 0x18);
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 3: In index "
"allocation.\n", __FUNCTION__);
start = 0;
}
/* Process the entries. */
finish = *p_low;
for (; entry < (buf + ibs) && ntfs_entry_is_used(entry);
entry += NTFS_GETU16(entry + 8)) {
if (start < finish) {
/* Skip entries that were already processed. */
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 4: Skipping "
"already processed entry p_high 0x%x, "
"p_low 0x%x.\n", __FUNCTION__, *p_high,
start);
start++;
continue;
}
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 5: Processing entry "
"p_high 0x%x, p_low 0x%x.\n", __FUNCTION__,
*p_high, *p_low);
if ((err = cb(entry, param))) {
/* filldir signalled us to stop. */
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 6: cb returned "
"%i, returning 0, p_high 0x%x, "
"p_low 0x%x.\n", __FUNCTION__, err,
*p_high, *p_low);
ntfs_free(buf);
return 0;
}
++*p_low;
}
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 7: After processing entries, "
"p_high 0x%x, p_low 0x%x.\n", __FUNCTION__, *p_high,
*p_low);
/* We have to locate the next record. */
ntfs_free(buf);
buf = 0;
*p_low = 0;
attr = ntfs_find_attr(ino, vol->at_bitmap, I30);
if (!attr) {
/* Directory does not have index bitmap and index allocation. */
*p_high = 0x7fff;
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 8: No index allocation. "
"Returning 0, p_high 0x7fff, p_low 0x0.\n",
__FUNCTION__);
return 0;
}
max_size = attr->size;
if (max_size > 0x7fff >> 3) {
ntfs_error("%s(): Directory too large. Visible "
"length is truncated.\n", __FUNCTION__);
max_size = 0x7fff >> 3;
}
buf = ntfs_malloc(max_size);
if (!buf)
return -ENOMEM;
io.param = buf;
io.size = max_size;
err = ntfs_read_attr(ino, vol->at_bitmap, I30, 0, &io);
if (err || io.size != max_size)
goto read_err_ret;
attr = ntfs_find_attr(ino, vol->at_index_allocation, I30);
if (!attr) {
ntfs_free(buf);
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 9: Find attr failed. "
"Returning -EIO.\n", __FUNCTION__);
return -EIO;
}
if (attr->resident) {
ntfs_free(buf);
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 9.5: IA is resident. Not"
" allowed. Returning EINVAL.\n", __FUNCTION__);
return -EINVAL;
}
/* Loop while going through non-allocated index records. */
max_size <<= 3;
while (1) {
if (++*p_high >= 0x7fff) {
ntfs_error("%s(): Unsorted 10: Directory "
"inode 0x%lx overflowed the maximum "
"number of index allocation buffers "
"the driver can cope with. Pretending "
"to be at end of directory.\n",
__FUNCTION__, ino->i_number);
goto fake_eod;
}
if (*p_high > max_size || (s64)*p_high << ibs_bits >
attr->initialized) {
fake_eod:
/* No more index records. */
*p_high = 0x7fff;
*p_low = 0;
ntfs_free(buf);
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 10.5: No more "
"index records. Returning 0, p_high "
"0x7fff, p_low 0.\n", __FUNCTION__);
return 0;
}
byte = (ntfs_cluster_t)(*p_high - 1);
bit = 1 << (byte & 7);
byte >>= 3;
if ((buf[byte] & bit))
break;
};
ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 11: Done. Returning 0, p_high "
"0x%x, p_low 0x%x.\n", __FUNCTION__, *p_high, *p_low);
ntfs_free(buf);
return 0;
read_err_ret:
if (!err)
err = -EIO;
ntfs_error("%s(): Read failed. Returning error code %i.\n",
__FUNCTION__, err);
ntfs_free(buf);
return err;
}
int ntfs_dir_add(ntfs_inode *dir, ntfs_inode *new, ntfs_attribute *name)
{
ntfs_iterate_s walk;
int nsize, esize;
ntfs_u8* entry, *ndata;
int error;
walk.type = DIR_INSERT;
walk.dir = dir;
walk.u.flags = 0;
nsize = name->size;
ndata = name->d.data;
walk.name = (ntfs_u16*)(ndata + 0x42);
walk.namelen = NTFS_GETU8(ndata + 0x40);
walk.new_entry_size = esize = (nsize + 0x10 + 7) & ~7;
walk.new_entry = entry = ntfs_malloc(esize);
if (!entry)
return -ENOMEM;
NTFS_PUTINUM(entry, new);
NTFS_PUTU16(entry + 0x8, esize); /* Size of entry. */
NTFS_PUTU16(entry + 0xA, nsize); /* Size of original name attribute. */
NTFS_PUTU16(entry + 0xC, 0); /* Flags. */
NTFS_PUTU16(entry + 0xE, 0); /* Reserved. */
ntfs_memcpy(entry + 0x10, ndata, nsize);
ntfs_bzero(entry + 0x10 + nsize, esize - 0x10 - nsize);
error = ntfs_getdir(&walk);
if (walk.new_entry)
ntfs_free(walk.new_entry);
return error;
}
#if 0
int ntfs_dir_add1(ntfs_inode *dir, const char* name, int namelen,
ntfs_inode *ino)
{
ntfs_iterate_s walk;
int error;
int nsize;
char *entry;
ntfs_attribute *name_attr;
error = ntfs_decodeuni(dir->vol, name, namelen, &walk.name,
&walk.namelen);
if (error)
return error;
/* FIXME: Set flags. */
walk.type = DIR_INSERT;
walk.dir = dir;
/* walk.new = ino; */
/* Prepare new entry. */
/* Round up to a multiple of 8. */
walk.new_entry_size = nsize = ((0x52 + 2 * walk.namelen + 7) / 8) * 8;
walk.new_entry = entry = ntfs_malloc(nsize);
if (!entry)
return -ENOMEM;
ntfs_bzero(entry, nsize);
NTFS_PUTINUM(entry, ino);
NTFS_PUTU16(entry + 8, nsize);
NTFS_PUTU16(entry + 0xA, 0x42 + 2 * namelen); /* FIXME: Size of name
* attribute. */
NTFS_PUTU32(entry + 0xC, 0); /* FIXME: D-F? */
name_attr = ntfs_find_attr(ino, vol->at_file_name, 0);
/* FIXME: multiple names */
if (!name_attr || !name_attr->resident)
return -EIDRM;
/* Directory, file stamps, sizes, filename. */
ntfs_memcpy(entry + 0x10, name_attr->d.data, 0x42 + 2 * namelen);
error = ntfs_getdir(&walk);
ntfs_free(walk.name);
return error;
}
#endif
/* Fills out and creates an INDEX_ROOT attribute. */
int ntfs_add_index_root(ntfs_inode *ino, int type)
{
ntfs_attribute *da;
ntfs_u8 data[0x30]; /* 0x20 header, 0x10 last entry. */
char name[10];
NTFS_PUTU32(data, type);
/* Collation rule. 1 == COLLATION_FILENAME */
NTFS_PUTU32(data + 4, 1);
NTFS_PUTU32(data + 8, ino->vol->index_record_size);
NTFS_PUTU32(data + 0xC, ino->vol->index_clusters_per_record);
/* Byte offset to first INDEX_ENTRY. */
NTFS_PUTU32(data + 0x10, 0x10);
/* Size of entries, including header. */
NTFS_PUTU32(data + 0x14, 0x20);
NTFS_PUTU32(data + 0x18, 0x20);
/* No index allocation, yet. */
NTFS_PUTU32(data + 0x1C, 0);
/* Add last entry. */
/* Indexed MFT record. */
NTFS_PUTU64(data + 0x20, 0);
/* Size of entry. */
NTFS_PUTU32(data + 0x28, 0x10);
/* Flags: Last entry, no child nodes. */
NTFS_PUTU32(data + 0x2C, 2);
/* Compute name. */
ntfs_indexname(name, type);
return ntfs_create_attr(ino, ino->vol->at_index_root, name,
data, sizeof(data), &da);
}
int ntfs_mkdir(ntfs_inode *dir, const char *name, int namelen,
ntfs_inode *result)
{
int error;
error = ntfs_alloc_inode(dir, result, name, namelen, NTFS_AFLAG_DIR);
if (error)
goto out;
error = ntfs_add_index_root(result, 0x30);
if (error)
goto out;
/* Set directory bit. */
result->attr[0x16] |= 2;
error = ntfs_update_inode(dir);
if (error)
goto out;
error = ntfs_update_inode(result);
if (error)
goto out;
out:
return error;
}
![[BACK]](/icons/back.gif){kind=icon}
Return to dir.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [Development] / linux-2.4-xfs / fs / ntfs