The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/ntfs/dir.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * dir.c
    3  *
    4  * Copyright (C) 1995-1997, 1999 Martin von L÷wis
    5  * Copyright (C) 1999 Steve Dodd
    6  * Copyright (C) 1999 Joseph Malicki
    7  * Copyright (C) 2001 Anton Altaparmakov (AIA)
    8  */
    9 
   10 #include "ntfstypes.h"
   11 #include "struct.h"
   12 #include "dir.h"
   13 #include "macros.h"
   14 
   15 #include <linux/errno.h>
   16 #include "super.h"
   17 #include "inode.h"
   18 #include "attr.h"
   19 #include "support.h"
   20 #include "util.h"
   21 #include <linux/smp_lock.h>
   22 #include <linux/bitops.h>
   23 
   24 static char I30[] = "$I30";
   25 
   26 /* An index record should start with INDX, and the last word in each block
   27  * should contain the check value. If it passes, the original values need to
   28  * be restored. */
   29 int ntfs_check_index_record(ntfs_inode *ino, char *record)
   30 {
   31         return ntfs_fixup_record(record, "INDX", ino->u.index.recordsize);
   32 }
   33 
   34 static inline int ntfs_is_top(ntfs_u64 stack)
   35 {
   36         return stack == 14;
   37 }
   38 
   39 static int ntfs_pop(ntfs_u64 *stack)
   40 {
   41         static int width[16] = {1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,-1};
   42         int res = -1;
   43         
   44         switch (width[*stack & 15]) {
   45         case 1:
   46                 res = (int)((*stack & 15) >> 1);
   47                 *stack >>= 4;
   48                 break;
   49         case 2:
   50                 res = (int)(((*stack & 63) >> 2) + 7);
   51                 *stack >>= 6;
   52                 break;
   53         case 3:
   54                 res = (int)(((*stack & 255) >> 3) + 23);
   55                 *stack >>= 8;
   56                 break;
   57         case 4:
   58                 res = (int)(((*stack & 1023) >> 4) + 55);
   59                 *stack >>= 10;
   60                 break;
   61         default:
   62                 ntfs_error("Unknown encoding\n");
   63         }
   64         return res;
   65 }
   66 
   67 static inline unsigned int ntfs_top(void)
   68 {
   69         return 14;
   70 }
   71 
   72 static ntfs_u64 ntfs_push(ntfs_u64 stack, int i)
   73 {
   74         if (i < 7)
   75                 return (stack << 4) | (i << 1);
   76         if (i < 23)
   77                 return (stack << 6) | ((i - 7) << 2) | 1;
   78         if (i < 55)
   79                 return (stack << 8) | ((i - 23) << 3) | 3;
   80         if (i < 120)
   81                 return (stack << 10) | ((i - 55) << 4) | 7;
   82         ntfs_error("Too many entries\n");
   83         return ~((ntfs_u64)0);
   84 }
   85 
   86 #if 0
   87 static void ntfs_display_stack(ntfs_u64 stack)
   88 {
   89         while(!ntfs_is_top(stack))
   90         {
   91                 printf("%d ", ntfs_pop(&stack));
   92         }
   93         printf("\n");
   94 }
   95 #endif
   96 
   97 /* True if the entry points to another block of entries. */
   98 static inline int ntfs_entry_has_subnodes(char *entry)
   99 {
  100         return (NTFS_GETU16(entry + 0xc) & 1);
  101 }
  102 
  103 /* True if it is not the 'end of dir' entry. */
  104 static inline int ntfs_entry_is_used(char *entry)
  105 {
  106         return !(NTFS_GETU16(entry + 0xc) & 2);
  107 }
  108 
  109 /*
  110  * Removed RACE for allocating index blocks. But stil not too happy.
  111  * There might be more races afterwards. (AIA)
  112  */
  113 static int ntfs_allocate_index_block(ntfs_iterate_s *walk)
  114 {
  115         ntfs_attribute *allocation, *bitmap = 0;
  116         int error, size, i, bit;
  117         ntfs_u8 *bmap;
  118         ntfs_io io;
  119         ntfs_volume *vol = walk->dir->vol;
  120 
  121         /* Check for allocation attribute. */
  122         allocation = ntfs_find_attr(walk->dir, vol->at_index_allocation, I30);
  123         if (!allocation) {
  124                 ntfs_u8 bmp[8];
  125                 /* Create index allocation attribute. */
  126                 error = ntfs_create_attr(walk->dir, vol->at_index_allocation,
  127                                          I30, 0, 0, &allocation);
  128                 if (error)
  129                         goto err_ret;
  130                 ntfs_bzero(bmp, sizeof(bmp));
  131                 error = ntfs_create_attr(walk->dir, vol->at_bitmap, I30, bmp,
  132                                          sizeof(bmp), &bitmap);
  133                 if (error)
  134                         goto err_ret;
  135         } else
  136                 bitmap = ntfs_find_attr(walk->dir, vol->at_bitmap, I30);
  137         if (!bitmap) {
  138                 ntfs_error("Directory w/o bitmap\n");
  139                 error = -EINVAL;
  140                 goto err_ret;
  141         }
  142         size = bitmap->size;
  143         bmap = ntfs_malloc(size);
  144         if (!bmap) {
  145                 error = -ENOMEM;
  146                 goto err_ret;
  147         }
  148         io.fn_put = ntfs_put;
  149         io.fn_get = ntfs_get;
  150 try_again:
  151         io.param = bmap;
  152         io.size = size;
  153         error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, 0, &io);
  154         if (error || (io.size != size && (error = -EIO, 1)))
  155                 goto err_fb_out;
  156         /* Allocate a bit. */
  157         for (bit = i = 0; i < size; i++) {
  158                 if (bmap[i] == 0xFF)
  159                         continue;
  160                 bit = ffz(bmap[i]);
  161                 if (bit < 8)
  162                         break;
  163         }
  164         if (i >= size) {
  165                 /* FIXME: Extend bitmap. */
  166                 error = -EOPNOTSUPP;
  167                 goto err_fb_out;
  168         }
  169         /* Get the byte containing our bit again, now taking the BKL. */
  170         io.param = bmap;
  171         io.size = 1;
  172         lock_kernel();
  173         error = ntfs_read_attr(walk->dir, vol->at_bitmap, I30, i, &io);
  174         if (error || (io.size != 1 && (error = -EIO, 1)))
  175                 goto err_unl_out;
  176         if (ntfs_test_and_set_bit(bmap, bit)) {
  177                 unlock_kernel();
  178                 /* Give other process(es) a chance to finish. */
  179                 schedule();
  180                 goto try_again;
  181         }
  182         walk->newblock = (i * 8 + bit) * walk->dir->u.index.clusters_per_record;
  183         io.param = bmap;
  184         error = ntfs_write_attr(walk->dir, vol->at_bitmap, I30, i, &io);
  185         if (error || (io.size != size && (error = -EIO, 1)))
  186                 goto err_unl_out;
  187         /* Change inode on disk, required when bitmap is resident. */
  188         error = ntfs_update_inode(walk->dir);
  189         if (error)
  190                 goto err_unl_out;
  191         unlock_kernel();
  192         ntfs_free(bmap);
  193         /* Check whether record is out of allocated range. */
  194         size = allocation->size;
  195         if (walk->newblock * vol->cluster_size >= size) {
  196                 /* Build index record. */
  197                 int hsize;
  198                 int s1 = walk->dir->u.index.recordsize;
  199                 int nr_fix = (s1 >> vol->sector_size) + 1;
  200                 char *record = ntfs_malloc(s1);
  201                 if (!record) {
  202                         error = -ENOMEM;
  203                         goto err_ret;
  204                 }
  205                 ntfs_bzero(record, s1);
  206                 /* Magic */
  207                 ntfs_memcpy(record, "INDX", 4);
  208                 /* Offset to fixups */
  209                 NTFS_PUTU16(record + 4, 0x28);
  210                 /* Number of fixups. */
  211                 NTFS_PUTU16(record + 6, nr_fix);
  212                 /* Log file sequence number - We don't do journalling so we
  213                  * just set it to zero which should be the Right Thing. (AIA) */
  214                 NTFS_PUTU64(record + 8, 0);
  215                 /* VCN of buffer */
  216                 NTFS_PUTU64(record + 0x10, walk->newblock);
  217                 /* Header size. */
  218                 hsize = 0x10 + 2 * nr_fix;
  219                 hsize = (hsize + 7) & ~7; /* Align. */
  220                 NTFS_PUTU16(record + 0x18, hsize);
  221                 /* Total size of record. */
  222                 NTFS_PUTU32(record + 0x20, s1 - 0x18);
  223                 /* Writing the data will extend the attribute. */
  224                 io.param = record;
  225                 io.size = s1;
  226                 io.do_read = 0;
  227                 error = ntfs_readwrite_attr(walk->dir, allocation, size, &io);
  228                 ntfs_free(record);
  229                 if (error || (io.size != s1 && (error = -EIO, 1)))
  230                         goto err_ret;
  231                 error = ntfs_update_inode(walk->dir);
  232                 if (error)
  233                         goto err_ret;
  234         }
  235         return 0;
  236 err_unl_out:
  237         unlock_kernel();
  238 err_fb_out:
  239         ntfs_free(bmap);
  240 err_ret:
  241         return error;
  242 }
  243 
  244 /* Write an index block (root or allocation) back to storage.
  245  * Used is the total number of bytes in buf, including all headers. */
  246 static int ntfs_index_writeback(ntfs_iterate_s *walk, ntfs_u8 *buf, int block,
  247                                 int used)
  248 {
  249         ntfs_io io;
  250         int error;
  251         ntfs_attribute *a;
  252         ntfs_volume *vol = walk->dir->vol;
  253         
  254         io.fn_put = 0;
  255         io.fn_get = ntfs_get;
  256         io.param = buf;
  257         if (block == -1) {      /* Index root. */
  258                 NTFS_PUTU16(buf + 0x14, used - 0x10);
  259                 /* 0x18 is a copy thereof. */
  260                 NTFS_PUTU16(buf + 0x18, used - 0x10);
  261                 io.size = used;
  262                 error = ntfs_write_attr(walk->dir, vol->at_index_root, I30, 0,
  263                                         &io);
  264                 if (error || (io.size != used && (error = -EIO, 1)))
  265                         return error;
  266                 /* Shrink if necessary. */
  267                 a = ntfs_find_attr(walk->dir, vol->at_index_root, I30);
  268                 ntfs_resize_attr(walk->dir, a, used);
  269         } else {
  270                 NTFS_PUTU16(buf + 0x1C, used - 0x18);
  271                 io.size = walk->dir->u.index.recordsize;
  272                 error = ntfs_insert_fixups(buf, io.size);
  273                 if (error) {
  274                         printk(KERN_ALERT "NTFS: ntfs_index_writeback() caught "
  275                                         "corrupt index record ntfs record "
  276                                         "header. Refusing to write corrupt "
  277                                         "data to disk. Unmount and run chkdsk "
  278                                         "immediately!\n");
  279                         return -EIO;
  280                 }
  281                 error = ntfs_write_attr(walk->dir, vol->at_index_allocation,
  282                                 I30, (__s64)block << vol->cluster_size_bits,
  283                                 &io);
  284                 if (error || (io.size != walk->dir->u.index.recordsize &&
  285                                 (error = -EIO, 1)))
  286                         return error;
  287         }
  288         return 0;
  289 }
  290 
  291 static int ntfs_split_record(ntfs_iterate_s *walk, char *start, int bsize,
  292                              int usize)
  293 {
  294         char *entry, *prev;
  295         ntfs_u8 *newbuf = 0, *middle = 0;
  296         int error, othersize, mlen;
  297         ntfs_io io;
  298         ntfs_volume *vol = walk->dir->vol;
  299         int oldblock;
  300 
  301         error = ntfs_allocate_index_block(walk);
  302         if (error)
  303                 return error;
  304         /* This should not happen. */
  305         if (walk->block == -1) {
  306                 ntfs_error("Trying to split root");
  307                 return -EOPNOTSUPP;
  308         }
  309         entry = start + NTFS_GETU16(start + 0x18) + 0x18; 
  310         for (prev = entry; entry - start < usize / 2; 
  311                                                entry += NTFS_GETU16(entry + 8))
  312                 prev = entry;
  313         newbuf = ntfs_malloc(vol->index_record_size);
  314         if (!newbuf)
  315                 return -ENOMEM;
  316         io.fn_put = ntfs_put;
  317         io.fn_get = ntfs_get;
  318         io.param = newbuf;
  319         io.size = vol->index_record_size;
  320         /* Read in old header. FIXME: Reading everything is overkill. */
  321         error = ntfs_read_attr(walk->dir, vol->at_index_allocation, I30,
  322                         (__s64)walk->newblock << vol->cluster_size_bits, &io);
  323         if (error)
  324                 goto out;
  325         if (io.size != vol->index_record_size) {
  326                 error = -EIO;
  327                 goto out;
  328         }
  329         /* FIXME: Adjust header. */
  330         /* Copy everything from entry to new block. */
  331         othersize = usize - (entry - start);
  332         ntfs_memcpy(newbuf + NTFS_GETU16(newbuf + 0x18) + 0x18, entry,
  333                                                                     othersize);
  334         /* Copy flags. */
  335         NTFS_PUTU32(newbuf + 0x24, NTFS_GETU32(start + 0x24));
  336         error = ntfs_index_writeback(walk, newbuf, walk->newblock,
  337                                 othersize + NTFS_GETU16(newbuf + 0x18) + 0x18);
  338         if (error)
  339                 goto out;
  340         /* Move prev to walk. */
  341         mlen = NTFS_GETU16(prev + 0x8);
  342         /* Remember old child node. */
  343         if (ntfs_entry_has_subnodes(prev))
  344                 oldblock = NTFS_GETU32(prev + mlen - 8);
  345         else
  346                 oldblock = -1;
  347         /* Allow for pointer to subnode. */
  348         middle = ntfs_malloc(ntfs_entry_has_subnodes(prev) ? mlen : mlen + 8);
  349         if (!middle){
  350                 error = -ENOMEM;
  351                 goto out;
  352         }
  353         ntfs_memcpy(middle, prev, mlen);
  354         /* Set has_subnodes flag. */
  355         NTFS_PUTU8(middle + 0xC, NTFS_GETU8(middle + 0xC) | 1);
  356         /* Middle entry points to block, parent entry will point to newblock. */
  357         NTFS_PUTU64(middle + mlen - 8, walk->block);
  358         if (walk->new_entry)
  359                 ntfs_error("Entry not reset");
  360         walk->new_entry = middle;
  361         walk->u.flags |= ITERATE_SPLIT_DONE;
  362         /* Terminate old block. */
  363         othersize = usize - (prev-start);
  364         NTFS_PUTU64(prev, 0);
  365         if (oldblock == -1) {
  366                 NTFS_PUTU32(prev + 8, 0x10);
  367                 NTFS_PUTU32(prev + 0xC, 2);
  368                 othersize += 0x10;
  369         } else {
  370                 NTFS_PUTU32(prev + 8, 0x18);
  371                 NTFS_PUTU32(prev + 0xC, 3);
  372                 NTFS_PUTU64(prev + 0x10, oldblock);
  373                 othersize += 0x18;
  374         }
  375         /* Write back original block. */
  376         error = ntfs_index_writeback(walk, start, walk->block, othersize);
  377  out:
  378         if (newbuf)
  379                 ntfs_free(newbuf);
  380         if (middle)
  381                 ntfs_free(middle);
  382         return error;
  383 }
  384 
  385 static int ntfs_dir_insert(ntfs_iterate_s *walk, char *start, char* entry)
  386 {
  387         int blocksize, usedsize, error, offset;
  388         int do_split = 0;
  389         offset = entry - start;
  390         if (walk->block == -1) { /* index root */
  391                 blocksize = walk->dir->vol->mft_record_size;
  392                 usedsize = NTFS_GETU16(start + 0x14) + 0x10;
  393         } else {
  394                 blocksize = walk->dir->u.index.recordsize;
  395                 usedsize = NTFS_GETU16(start + 0x1C) + 0x18;
  396         }
  397         if (usedsize + walk->new_entry_size > blocksize) {
  398                 char* s1 = ntfs_malloc(blocksize + walk->new_entry_size);
  399                 if (!s1)
  400                         return -ENOMEM;
  401                 ntfs_memcpy(s1, start, usedsize);
  402                 do_split = 1;
  403                 /* Adjust entry to s1. */
  404                 entry = s1 + (entry - start);
  405                 start = s1;
  406         }
  407         ntfs_memmove(entry + walk->new_entry_size, entry, usedsize - offset);
  408         ntfs_memcpy(entry, walk->new_entry, walk->new_entry_size);
  409         usedsize += walk->new_entry_size;
  410         ntfs_free(walk->new_entry);
  411         walk->new_entry = 0;
  412         if (do_split) {
  413                 error = ntfs_split_record(walk, start, blocksize, usedsize);
  414                 ntfs_free(start);
  415         } else {
  416                 error = ntfs_index_writeback(walk, start, walk->block,usedsize);
  417                 if (error)
  418                         return error;
  419         }
  420         return 0;
  421 }
  422 
  423 /* Try to split INDEX_ROOT attributes. Return -E2BIG if nothing changed. */
  424 int ntfs_split_indexroot(ntfs_inode *ino)
  425 {
  426         ntfs_attribute *ra;
  427         ntfs_u8 *root = 0, *index = 0;
  428         ntfs_io io;
  429         int error, off, i, bsize, isize;
  430         ntfs_iterate_s walk;
  431 
  432         ra = ntfs_find_attr(ino, ino->vol->at_index_root, I30);
  433         if (!ra)
  434                 return -ENOTDIR;
  435         bsize = ino->vol->mft_record_size;
  436         root = ntfs_malloc(bsize);
  437         if (!root)
  438                 return -E2BIG;
  439         io.fn_put = ntfs_put;
  440         io.param = root;
  441         io.size = bsize;
  442         error = ntfs_read_attr(ino, ino->vol->at_index_root, I30, 0, &io);
  443         if (error)
  444                 goto out;
  445         off = 0x20;
  446         /* Count number of entries. */
  447         for (i = 0; ntfs_entry_is_used(root + off); i++)
  448                 off += NTFS_GETU16(root + off + 8);
  449         if (i <= 2) {
  450                 /* We don't split small index roots. */
  451                 error = -E2BIG;
  452                 goto out;
  453         }
  454         index = ntfs_malloc(ino->vol->index_record_size);
  455         if (!index) {
  456                 error = -ENOMEM;
  457                 goto out;
  458         }
  459         walk.dir = ino;
  460         walk.block = -1;
  461         walk.result = walk.new_entry = 0;
  462         walk.name = 0;
  463         error = ntfs_allocate_index_block(&walk);
  464         if (error)
  465                 goto out;
  466         /* Write old root to new index block. */
  467         io.param = index;
  468         io.size = ino->vol->index_record_size;
  469         error = ntfs_read_attr(ino, ino->vol->at_index_allocation, I30,
  470                 (__s64)walk.newblock << ino->vol->cluster_size_bits, &io);
  471         if (error)
  472                 goto out;
  473         isize = NTFS_GETU16(root + 0x18) - 0x10;
  474         ntfs_memcpy(index + NTFS_GETU16(index + 0x18) + 0x18, root+0x20, isize);
  475         /* Copy flags. */
  476         NTFS_PUTU32(index + 0x24, NTFS_GETU32(root + 0x1C));
  477         error = ntfs_index_writeback(&walk, index, walk.newblock, 
  478                                      isize + NTFS_GETU16(index + 0x18) + 0x18);
  479         if (error)
  480                 goto out;
  481         /* Mark root as split. */
  482         NTFS_PUTU32(root + 0x1C, 1);
  483         /* Truncate index root. */
  484         NTFS_PUTU64(root + 0x20, 0);
  485         NTFS_PUTU32(root + 0x28, 0x18);
  486         NTFS_PUTU32(root + 0x2C, 3);
  487         NTFS_PUTU64(root + 0x30, walk.newblock);
  488         error = ntfs_index_writeback(&walk, root, -1, 0x38);
  489  out:
  490         ntfs_free(root);
  491         ntfs_free(index);
  492         return error;
  493 }
  494 
  495 /* The entry has been found. Copy the result in the caller's buffer */
  496 static int ntfs_copyresult(char *dest, char *source)
  497 {
  498         int length = NTFS_GETU16(source + 8);
  499         ntfs_memcpy(dest, source, length);
  500         return 1;
  501 }
  502 
  503 /* Use $UpCase some day. */
  504 static inline unsigned short ntfs_my_toupper(ntfs_volume *vol, ntfs_u16 x)
  505 {
  506         /* We should read any pending rest of $UpCase here. */
  507         if (x >= vol->upcase_length)
  508                 return x;
  509         return vol->upcase[x];
  510 }
  511 
  512 /* Everything passed in walk and entry. */
  513 static int ntfs_my_strcmp(ntfs_iterate_s *walk, const unsigned char *entry)
  514 {
  515         int lu = *(entry + 0x50);
  516         int i;
  517 
  518         ntfs_u16* name = (ntfs_u16*)(entry + 0x52);
  519         ntfs_volume *vol = walk->dir->vol;
  520         for (i = 0; i < lu && i < walk->namelen; i++)
  521                 if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) != 
  522                              ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
  523                         break;
  524         if (i == lu && i == walk->namelen)
  525                 return 0;
  526         if (i == lu)
  527                 return 1;
  528         if (i == walk->namelen)
  529                 return -1;
  530         if (ntfs_my_toupper(vol, NTFS_GETU16(name + i)) < 
  531                             ntfs_my_toupper(vol, NTFS_GETU16(walk->name + i)))
  532                 return 1;
  533         return -1;
  534 }
  535 
  536 /* Necessary forward declaration. */
  537 static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);
  538 
  539 /* Parse a block of entries. Load the block, fix it up, and iterate over the
  540  * entries. The block is given as virtual cluster number. */
  541 static int ntfs_getdir_record(ntfs_iterate_s *walk, int block)
  542 {
  543         int length = walk->dir->u.index.recordsize;
  544         char *record = (char*)ntfs_malloc(length);
  545         char *offset;
  546         int retval,error;
  547         int oldblock;
  548         ntfs_io io;
  549 
  550         if (!record)
  551                 return -ENOMEM;
  552         io.fn_put = ntfs_put;
  553         io.param = record;
  554         io.size = length;
  555         /* Read the block from the index allocation attribute. */
  556         error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_allocation,
  557                 I30, (__s64)block << walk->dir->vol->cluster_size_bits, &io);
  558         if (error || io.size != length) {
  559                 ntfs_error("read failed\n");
  560                 ntfs_free(record);
  561                 return 0;
  562         }
  563         if (!ntfs_check_index_record(walk->dir, record)) {
  564                 ntfs_error("%x is not an index record\n", block);
  565                 ntfs_free(record);
  566                 return 0;
  567         }
  568         offset = record + NTFS_GETU16(record + 0x18) + 0x18;
  569         oldblock = walk->block;
  570         walk->block = block;
  571         retval = ntfs_getdir_iterate(walk, record, offset);
  572         walk->block = oldblock;
  573         ntfs_free(record);
  574         return retval;
  575 }
  576 
  577 /* Go down to the next block of entries. These collate before the current
  578  * entry. */
  579 static int ntfs_descend(ntfs_iterate_s *walk, ntfs_u8 *start, ntfs_u8 *entry)
  580 {
  581         int length = NTFS_GETU16(entry + 8);
  582         int nextblock = NTFS_GETU32(entry + length - 8);
  583         int error;
  584 
  585         if (!ntfs_entry_has_subnodes(entry)) {
  586                 ntfs_error("illegal ntfs_descend call\n");
  587                 return 0;
  588         }
  589         error = ntfs_getdir_record(walk, nextblock);
  590         if (!error && walk->type == DIR_INSERT && 
  591             (walk->u.flags & ITERATE_SPLIT_DONE)) {
  592                 /* Split has occurred. Adjust entry, insert new_entry. */
  593                 NTFS_PUTU32(entry + length - 8, walk->newblock);
  594                 /* Reset flags, as the current block might be split again. */
  595                 walk->u.flags &= ~ITERATE_SPLIT_DONE;
  596                 error = ntfs_dir_insert(walk, start, entry);
  597         }
  598         return error;
  599 }
  600 
  601 static int ntfs_getdir_iterate_byposition(ntfs_iterate_s *walk, char* start,
  602                                           char *entry)
  603 {
  604         int retval = 0;
  605         int curpos = 0, destpos = 0;
  606         int length;
  607         if (walk->u.pos != 0) {
  608                 if (ntfs_is_top(walk->u.pos))
  609                         return 0;
  610                 destpos = ntfs_pop(&walk->u.pos);
  611         }
  612         while (1) {
  613                 if (walk->u.pos == 0) {
  614                         if (ntfs_entry_has_subnodes(entry))
  615                                 ntfs_descend(walk, start, entry);
  616                         else
  617                                 walk->u.pos = ntfs_top();
  618                         if (ntfs_is_top(walk->u.pos) && 
  619                             !ntfs_entry_is_used(entry))
  620                                 return 1;
  621                         walk->u.pos = ntfs_push(walk->u.pos, curpos);
  622                         return 1;
  623                 }
  624                 if (curpos == destpos) {
  625                         if (!ntfs_is_top(walk->u.pos) && 
  626                             ntfs_entry_has_subnodes(entry)) {
  627                                 retval = ntfs_descend(walk, start, entry);
  628                                 if (retval) {
  629                                         walk->u.pos = ntfs_push(walk->u.pos,
  630                                                                 curpos);
  631                                         return retval;
  632                                 }
  633                                 if (!ntfs_entry_is_used(entry))
  634                                         return 0;
  635                                 walk->u.pos = 0;
  636                         }
  637                         if (ntfs_entry_is_used(entry)) {
  638                                 retval = ntfs_copyresult(walk->result, entry);
  639                                 walk->u.pos = 0;
  640                         } else {
  641                                 walk->u.pos = ntfs_top();
  642                                 return 0;
  643                         }
  644                 }
  645                 curpos++;
  646                 if (!ntfs_entry_is_used(entry))
  647                         break;
  648                 length = NTFS_GETU16(entry + 8);
  649                 if (!length) {
  650                         ntfs_error("infinite loop\n");
  651                         break;
  652                 }
  653                 entry += length;
  654         }
  655         return -1;
  656 }
  657         
  658 /* Iterate over a list of entries, either from an index block, or from the
  659  * index root.
  660  * If searching BY_POSITION, pop the top index from the position. If the
  661  * position stack is empty then, return the item at the index and set the
  662  * position to the next entry. If the position stack is not empty, 
  663  * recursively proceed for subnodes. If the entry at the position is the
  664  * 'end of dir' entry, return 'not found' and the empty stack.
  665  * If searching BY_NAME, walk through the items until found or until
  666  * one item is collated after the requested item. In the former case, return
  667  * the result. In the latter case, recursively proceed to the subnodes.
  668  * If 'end of dir' is reached, the name is not in the directory */
  669 static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry)
  670 {
  671         int length;
  672         int cmp;
  673 
  674         if (walk->type == BY_POSITION)
  675                 return ntfs_getdir_iterate_byposition(walk, start, entry);
  676         do {
  677                 /* If the current entry is a real one, compare with the
  678                  * requested item. If the current entry is the last item, it
  679                  * is always larger than the requested item. */
  680                 cmp = ntfs_entry_is_used(entry) ? 
  681                                                 ntfs_my_strcmp(walk,entry) : -1;
  682                 switch (walk->type) {
  683                 case BY_NAME:
  684                         switch (cmp) {
  685                         case -1:
  686                                 return ntfs_entry_has_subnodes(entry) ?
  687                                         ntfs_descend(walk, start, entry) : 0;
  688                         case  0:
  689                                 return ntfs_copyresult(walk->result, entry);
  690                         case  1:
  691                                 break;
  692                         }
  693                         break;
  694                 case DIR_INSERT:
  695                         switch (cmp) {
  696                         case -1:
  697                                 return ntfs_entry_has_subnodes(entry) ?
  698                                         ntfs_descend(walk, start, entry) :
  699                                         ntfs_dir_insert(walk, start, entry);
  700                         case  0:
  701                                 return -EEXIST;
  702                         case  1:
  703                                 break;
  704                         }
  705                         break;
  706                 default:
  707                         ntfs_error("TODO\n"); /* FIXME: ? */
  708                 }
  709                 if (!ntfs_entry_is_used(entry))
  710                         break;
  711                 length = NTFS_GETU16(entry + 8);
  712                 if (!length) {
  713                         ntfs_error("infinite loop\n");
  714                         break;
  715                 }
  716                 entry += length;
  717         } while (1);
  718         return 0;
  719 }
  720 
  721 /*  Tree walking is done using position numbers. The following numbers have a
  722  *  special meaning:
  723  *       0   start (.)
  724  *      -1   no more entries
  725  *      -2   ..
  726  *  All other numbers encode sequences of indices. The sequence a, b, c is 
  727  *  encoded as <stop><c><b><a>, where <foo> is the encoding of foo. The
  728  *  first few integers are encoded as follows:
  729  *      0:    0000    1:    0010    2:    0100    3:    0110
  730  *      4:    1000    5:    1010    6:    1100 stop:    1110
  731  *      7:  000001    8:  000101    9:  001001   10:  001101
  732  *  The least significant bits give the width of this encoding, the other bits
  733  *  encode the value, starting from the first value of the interval.
  734  *   tag     width  first value  last value
  735  *   0       3      0            6
  736  *   01      4      7            22
  737  *   011     5      23           54
  738  *   0111    6      55           119
  739  *   More values are hopefully not needed, as the file position has currently
  740  *   64 bits in total. */
  741 
  742 /* Find an entry in the directory. Return 0 if not found, otherwise copy the
  743  * entry to the result buffer. */
  744 int ntfs_getdir(ntfs_iterate_s *walk)
  745 {
  746         int length = walk->dir->vol->mft_record_size;
  747         int retval, error;
  748         /* Start at the index root. */
  749         char *root = ntfs_malloc(length);
  750         ntfs_io io;
  751 
  752         if (!root)
  753                 return -ENOMEM;
  754         io.fn_put = ntfs_put;
  755         io.param = root;
  756         io.size = length;
  757         error = ntfs_read_attr(walk->dir, walk->dir->vol->at_index_root, I30,
  758                                0, &io);
  759         if (error) {
  760                 ntfs_error("Not a directory\n");
  761                 return 0;
  762         }
  763         walk->block = -1;
  764         /* FIXME: Move these to walk. */
  765         walk->dir->u.index.recordsize = NTFS_GETU32(root + 0x8);
  766         walk->dir->u.index.clusters_per_record = NTFS_GETU32(root + 0xC);
  767         /* FIXME: Consistency check. */
  768         /* Skip header. */
  769         retval = ntfs_getdir_iterate(walk, root, root + 0x20);
  770         ntfs_free(root);
  771         return retval;
  772 }
  773 
  774 /* Find an entry in the directory by its position stack. Iteration starts
  775  * if the stack is 0, in which case the position is set to the first item
  776  * in the directory. If the position is nonzero, return the item at the
  777  * position and change the position to the next item. The position is -1
  778  * if there are no more items. */
  779 int ntfs_getdir_byposition(ntfs_iterate_s *walk)
  780 {
  781         walk->type = BY_POSITION;
  782         return ntfs_getdir(walk);
  783 }
  784 
  785 /* Find an entry in the directory by its name. Return 0 if not found. */
  786 int ntfs_getdir_byname(ntfs_iterate_s *walk)
  787 {
  788         walk->type = BY_NAME;
  789         return ntfs_getdir(walk);
  790 }
  791 
  792 int ntfs_getdir_unsorted(ntfs_inode *ino, u32 *p_high, u32 *p_low,
  793                 int (*cb)(ntfs_u8 *, void *), void *param)
  794 {
  795         s64 ib_ofs;
  796         char *buf = 0, *entry = 0;
  797         ntfs_attribute *attr;
  798         ntfs_volume *vol;
  799         int byte, bit, err = 0;
  800         u32 start, finish, ibs, max_size;
  801         ntfs_io io;
  802         u8 ibs_bits;
  803 
  804         if (!ino) {
  805                 ntfs_error(__FUNCTION__ "(): No inode! Returning -EINVAL.\n");
  806                 return -EINVAL;
  807         }
  808         vol = ino->vol;
  809         if (!vol) {
  810                 ntfs_error(__FUNCTION__ "(): Inode 0x%lx has no volume. "
  811                                 "Returning -EINVAL.\n", ino->i_number);
  812                 return -EINVAL;
  813         }
  814         ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 1: Entering for "
  815                         "inode 0x%lx, p_high = 0x%x, p_low = 0x%x.\n",
  816                         ino->i_number, *p_high, *p_low);
  817         if (!*p_high) {
  818                 /* We are still in the index root. */
  819                 buf = ntfs_malloc(io.size = vol->mft_record_size);
  820                 if (!buf)
  821                         return -ENOMEM;
  822                 io.fn_put = ntfs_put;
  823                 io.param = buf;
  824                 err = ntfs_read_attr(ino, vol->at_index_root, I30, 0, &io);
  825                 if (err || !io.size)
  826                         goto read_err_ret;
  827                 ino->u.index.recordsize = ibs = NTFS_GETU32(buf + 0x8);
  828                 ino->u.index.clusters_per_record = NTFS_GETU32(buf + 0xC);
  829                 entry = buf + 0x20;
  830                 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 2: In index "
  831                                 "root.\n");
  832                 ibs_bits = ffs(ibs) - 1;
  833                 /* Compensate for faked "." and "..". */
  834                 start = 2;
  835         } else { /* We are in an index record. */
  836                 io.size = ibs = ino->u.index.recordsize;
  837                 buf = ntfs_malloc(ibs);
  838                 if (!buf)
  839                         return -ENOMEM;
  840                 ibs_bits = ffs(ibs) - 1;
  841                 io.fn_put = ntfs_put;
  842                 io.param = buf;
  843                 /*
  844                  * 0 is index root, index allocation starts at 1 and works in
  845                  * units of index block size (ibs).
  846                  */
  847                 ib_ofs = (s64)(*p_high - 1) << ibs_bits;
  848                 err = ntfs_read_attr(ino, vol->at_index_allocation, I30, ib_ofs,
  849                                 &io);
  850                 if (err || io.size != ibs)
  851                         goto read_err_ret;
  852                 if (!ntfs_check_index_record(ino, buf)) {
  853                         ntfs_error(__FUNCTION__ "(): Index block 0x%x is not "
  854                                         "an index record. Returning "
  855                                         "-ENOTDIR.\n", *p_high - 1);
  856                         ntfs_free(buf);
  857                         return -ENOTDIR;
  858                 }
  859                 entry = buf + 0x18 + NTFS_GETU16(buf + 0x18);
  860                 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 3: In index "
  861                                 "allocation.\n");
  862                 start = 0;
  863         }
  864         /* Process the entries. */
  865         finish = *p_low;
  866         for (; entry < (buf + ibs) && ntfs_entry_is_used(entry);
  867                         entry += NTFS_GETU16(entry + 8)) {
  868                 if (start < finish) {
  869                         /* Skip entries that were already processed. */
  870                         ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 4: "
  871                                         "Skipping already processed entry "
  872                                         "p_high 0x%x, p_low 0x%x.\n", *p_high,
  873                                         start);
  874                         start++;
  875                         continue;
  876                 }
  877                 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 5: "
  878                                 "Processing entry p_high 0x%x, p_low 0x%x.\n",
  879                                 *p_high, *p_low);
  880                 if ((err = cb(entry, param))) {
  881                         /* filldir signalled us to stop. */
  882                         ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): "
  883                                         "Unsorted 6: cb returned %i, "
  884                                         "returning 0, p_high 0x%x, p_low 0x%x."
  885                                         "\n", *p_high, *p_low);
  886                         ntfs_free(buf);
  887                         return 0;
  888                 }
  889                 ++*p_low;
  890         }
  891         ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 7: After processing "
  892                         "entries, p_high 0x%x, p_low 0x%x.\n", *p_high, *p_low);
  893         /* We have to locate the next record. */
  894         ntfs_free(buf);
  895         buf = 0;
  896         *p_low = 0;
  897         attr = ntfs_find_attr(ino, vol->at_bitmap, I30);
  898         if (!attr) {
  899                 /* Directory does not have index bitmap and index allocation. */
  900                 *p_high = 0x7fff;
  901                 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 8: No index "
  902                                 "allocation. Returning 0, p_high 0x7fff, "
  903                                 "p_low 0x0.\n");
  904                 return 0;
  905         }
  906         max_size = attr->size;
  907         if (max_size > 0x7fff >> 3) {
  908                 ntfs_error(__FUNCTION__ "(): Directory too large. Visible "
  909                                 "length is truncated.\n");
  910                 max_size = 0x7fff >> 3;
  911         }
  912         buf = ntfs_malloc(max_size);
  913         if (!buf)
  914                 return -ENOMEM;
  915         io.param = buf;
  916         io.size = max_size;
  917         err = ntfs_read_attr(ino, vol->at_bitmap, I30, 0, &io);
  918         if (err || io.size != max_size)
  919                 goto read_err_ret;
  920         attr = ntfs_find_attr(ino, vol->at_index_allocation, I30);
  921         if (!attr) {
  922                 ntfs_free(buf);
  923                 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 9: Find "
  924                                 "attr failed. Returning -EIO.\n");
  925                 return -EIO;
  926         }
  927         if (attr->resident) {
  928                 ntfs_free(buf);
  929                 ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 9.5: IA is "
  930                                 "resident. Not allowed. Returning EINVAL.\n");
  931                 return -EINVAL;
  932         }
  933         /* Loop while going through non-allocated index records. */
  934         max_size <<= 3;
  935         while (1) {
  936                 if (++*p_high >= 0x7fff) {
  937                         ntfs_error(__FUNCTION__ "(): Unsorted 10: Directory "
  938                                         "inode 0x%lx overflowed the maximum "
  939                                         "number of index allocation buffers "
  940                                         "the driver can cope with. Pretending "
  941                                         "to be at end of directory.\n",
  942                                         ino->i_number);
  943                         goto fake_eod;
  944                 }
  945                 if (*p_high > max_size || (s64)*p_high << ibs_bits >
  946                                 attr->initialized) {
  947 fake_eod:
  948                         /* No more index records. */
  949                         *p_high = 0x7fff;
  950                         *p_low = 0;
  951                         ntfs_free(buf);
  952                         ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted "
  953                                         "10.5: No more index records. "
  954                                         "Returning 0, p_high 0x7fff, p_low "
  955                                         "0.\n");
  956                         return 0;
  957                 }
  958                 byte = (ntfs_cluster_t)(*p_high - 1);
  959                 bit = 1 << (byte & 7);
  960                 byte >>= 3;
  961                 if ((buf[byte] & bit))
  962                         break;
  963         };
  964         ntfs_debug(DEBUG_DIR3, __FUNCTION__ "(): Unsorted 11: Done. "
  965                         "Returning 0, p_high 0x%x, p_low 0x%x.\n", *p_high,
  966                         *p_low);
  967         ntfs_free(buf);
  968         return 0;
  969 read_err_ret:
  970         if (!err)
  971                 err = -EIO;
  972         ntfs_error(__FUNCTION__ "(): Read failed. Returning error code %i.\n",
  973                         err);
  974         ntfs_free(buf);
  975         return err;
  976 }
  977 
  978 int ntfs_dir_add(ntfs_inode *dir, ntfs_inode *new, ntfs_attribute *name)
  979 {
  980         ntfs_iterate_s walk;
  981         int nsize, esize;
  982         ntfs_u8* entry, *ndata;
  983         int error;
  984 
  985         walk.type = DIR_INSERT;
  986         walk.dir = dir;
  987         walk.u.flags = 0;
  988         nsize = name->size;
  989         ndata = name->d.data;
  990         walk.name = (ntfs_u16*)(ndata + 0x42);
  991         walk.namelen = NTFS_GETU8(ndata + 0x40);
  992         walk.new_entry_size = esize = (nsize + 0x10 + 7) & ~7;
  993         walk.new_entry = entry = ntfs_malloc(esize);
  994         if (!entry)
  995                 return -ENOMEM;
  996         NTFS_PUTINUM(entry, new);
  997         NTFS_PUTU16(entry + 0x8, esize); /* Size of entry. */
  998         NTFS_PUTU16(entry + 0xA, nsize); /* Size of original name attribute. */
  999         NTFS_PUTU16(entry + 0xC, 0);     /* Flags. */
 1000         NTFS_PUTU16(entry + 0xE, 0);     /* Reserved. */
 1001         ntfs_memcpy(entry + 0x10, ndata, nsize);
 1002         ntfs_bzero(entry + 0x10 + nsize, esize - 0x10 - nsize);
 1003         error = ntfs_getdir(&walk);
 1004         if (walk.new_entry)
 1005                 ntfs_free(walk.new_entry);
 1006         return error;
 1007 }
 1008 
 1009 #if 0
 1010 int ntfs_dir_add1(ntfs_inode *dir, const char* name, int namelen,
 1011                   ntfs_inode *ino)
 1012 {
 1013         ntfs_iterate_s walk;
 1014         int error;
 1015         int nsize;
 1016         char *entry;
 1017         ntfs_attribute *name_attr;
 1018         error = ntfs_decodeuni(dir->vol, name, namelen, &walk.name,
 1019                                &walk.namelen);
 1020         if (error)
 1021                 return error;
 1022         /* FIXME: Set flags. */
 1023         walk.type = DIR_INSERT;
 1024         walk.dir = dir;
 1025         /* walk.new = ino; */
 1026         /* Prepare new entry. */
 1027         /* Round up to a multiple of 8. */
 1028         walk.new_entry_size = nsize = ((0x52 + 2 * walk.namelen + 7) / 8) * 8;
 1029         walk.new_entry = entry = ntfs_malloc(nsize);
 1030         if (!entry)
 1031                 return -ENOMEM;
 1032         ntfs_bzero(entry, nsize);
 1033         NTFS_PUTINUM(entry, ino);
 1034         NTFS_PUTU16(entry + 8, nsize);
 1035         NTFS_PUTU16(entry + 0xA, 0x42 + 2 * namelen); /* FIXME: Size of name 
 1036                                                        * attribute. */
 1037         NTFS_PUTU32(entry + 0xC, 0); /* FIXME: D-F? */
 1038         name_attr = ntfs_find_attr(ino, vol->at_file_name, 0);
 1039                                                     /* FIXME: multiple names */
 1040         if (!name_attr || !name_attr->resident)
 1041                 return -EIDRM;
 1042         /* Directory, file stamps, sizes, filename. */
 1043         ntfs_memcpy(entry + 0x10, name_attr->d.data, 0x42 + 2 * namelen);
 1044         error = ntfs_getdir(&walk);
 1045         ntfs_free(walk.name);
 1046         return error;
 1047 }
 1048 #endif
 1049 
 1050 /* Fills out and creates an INDEX_ROOT attribute. */
 1051 int ntfs_add_index_root(ntfs_inode *ino, int type)
 1052 {
 1053         ntfs_attribute *da;
 1054         ntfs_u8 data[0x30]; /* 0x20 header, 0x10 last entry. */
 1055         char name[10];
 1056 
 1057         NTFS_PUTU32(data, type);
 1058         /* Collation rule. 1 == COLLATION_FILENAME */
 1059         NTFS_PUTU32(data + 4, 1);
 1060         NTFS_PUTU32(data + 8, ino->vol->index_record_size);
 1061         NTFS_PUTU32(data + 0xC, ino->vol->index_clusters_per_record);
 1062         /* Byte offset to first INDEX_ENTRY. */
 1063         NTFS_PUTU32(data + 0x10, 0x10);
 1064         /* Size of entries, including header. */
 1065         NTFS_PUTU32(data + 0x14, 0x20);
 1066         NTFS_PUTU32(data + 0x18, 0x20);
 1067         /* No index allocation, yet. */
 1068         NTFS_PUTU32(data + 0x1C, 0);
 1069         /* Add last entry. */
 1070         /* Indexed MFT record. */
 1071         NTFS_PUTU64(data + 0x20, 0);
 1072         /* Size of entry. */
 1073         NTFS_PUTU32(data + 0x28, 0x10);
 1074         /* Flags: Last entry, no child nodes. */
 1075         NTFS_PUTU32(data + 0x2C, 2);
 1076         /* Compute name. */
 1077         ntfs_indexname(name, type);
 1078         return ntfs_create_attr(ino, ino->vol->at_index_root, name,
 1079                                 data, sizeof(data), &da);
 1080 }
 1081 
 1082 int ntfs_mkdir(ntfs_inode *dir, const char *name, int namelen,
 1083                ntfs_inode *result)
 1084 {
 1085         int error;
 1086         
 1087         error = ntfs_alloc_inode(dir, result, name, namelen, NTFS_AFLAG_DIR);
 1088         if (error)
 1089                 goto out;
 1090         error = ntfs_add_index_root(result, 0x30);
 1091         if (error)
 1092                 goto out;
 1093         /* Set directory bit. */
 1094         result->attr[0x16] |= 2;
 1095         error = ntfs_update_inode(dir);
 1096         if (error)
 1097                 goto out;
 1098         error = ntfs_update_inode(result);
 1099         if (error)
 1100                 goto out;
 1101  out:
 1102         return error;
 1103 }
 1104 

Cache object: dfc4f6ebef62b433bb68145cb510fddf


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.