fs/ntfs/dir.c

   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("%s(): No inode! Returning -EINVAL.\n",__FUNCTION__);
 806                 return -EINVAL;
 807         }
 808         vol = ino->vol;
 809         if (!vol) {
 810                 ntfs_error("%s(): Inode 0x%lx has no volume. Returning "
 811                             "-EINVAL.\n", __FUNCTION__, ino->i_number);
 812                 return -EINVAL;
 813         }
 814         ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 1: Entering for inode 0x%lx, "
 815                         "p_high = 0x%x, p_low = 0x%x.\n", __FUNCTION__,
 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, "%s(): Unsorted 2: In index root.\n",
 831                                 __FUNCTION__);
 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("%s(): Index block 0x%x is not an index "
 854                                         "record. Returning -ENOTDIR.\n",
 855                                          __FUNCTION__, *p_high - 1);
 856                         ntfs_free(buf);
 857                         return -ENOTDIR;
 858                 }
 859                 entry = buf + 0x18 + NTFS_GETU16(buf + 0x18);
 860                 ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 3: In index "
 861                                 "allocation.\n", __FUNCTION__);
 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, "%s(): Unsorted 4: Skipping "
 871                                         "already processed entry p_high 0x%x, "
 872                                         "p_low 0x%x.\n", __FUNCTION__, *p_high,
 873                                         start);
 874                         start++;
 875                         continue;
 876                 }
 877                 ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 5: Processing entry "
 878                                 "p_high 0x%x, p_low 0x%x.\n", __FUNCTION__,
 879                                 *p_high, *p_low);
 880                 if ((err = cb(entry, param))) {
 881                         /* filldir signalled us to stop. */
 882                         ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 6: cb returned "
 883                                         "%i, returning 0, p_high 0x%x, "
 884                                         "p_low 0x%x.\n", __FUNCTION__, err,
 885                                         *p_high, *p_low);
 886                         ntfs_free(buf);
 887                         return 0;
 888                 }
 889                 ++*p_low;
 890         }
 891         ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 7: After processing entries, "
 892                         "p_high 0x%x, p_low 0x%x.\n", __FUNCTION__, *p_high,
 893                         *p_low);
 894         /* We have to locate the next record. */
 895         ntfs_free(buf);
 896         buf = 0;
 897         *p_low = 0;
 898         attr = ntfs_find_attr(ino, vol->at_bitmap, I30);
 899         if (!attr) {
 900                 /* Directory does not have index bitmap and index allocation. */
 901                 *p_high = 0x7fff;
 902                 ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 8: No index allocation. "
 903                                 "Returning 0, p_high 0x7fff, p_low 0x0.\n",
 904                                 __FUNCTION__);
 905                 return 0;
 906         }
 907         max_size = attr->size;
 908         if (max_size > 0x7fff >> 3) {
 909                 ntfs_error("%s(): Directory too large. Visible "
 910                                 "length is truncated.\n", __FUNCTION__);
 911                 max_size = 0x7fff >> 3;
 912         }
 913         buf = ntfs_malloc(max_size);
 914         if (!buf)
 915                 return -ENOMEM;
 916         io.param = buf;
 917         io.size = max_size;
 918         err = ntfs_read_attr(ino, vol->at_bitmap, I30, 0, &io);
 919         if (err || io.size != max_size)
 920                 goto read_err_ret;
 921         attr = ntfs_find_attr(ino, vol->at_index_allocation, I30);
 922         if (!attr) {
 923                 ntfs_free(buf);
 924                 ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 9: Find attr failed. "
 925                                 "Returning -EIO.\n", __FUNCTION__);
 926                 return -EIO;
 927         }
 928         if (attr->resident) {
 929                 ntfs_free(buf);
 930                 ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 9.5: IA is resident. Not"
 931                                 " allowed. Returning EINVAL.\n", __FUNCTION__);
 932                 return -EINVAL;
 933         }
 934         /* Loop while going through non-allocated index records. */
 935         max_size <<= 3;
 936         while (1) {
 937                 if (++*p_high >= 0x7fff) {
 938                         ntfs_error("%s(): Unsorted 10: Directory "
 939                                         "inode 0x%lx overflowed the maximum "
 940                                         "number of index allocation buffers "
 941                                         "the driver can cope with. Pretending "
 942                                         "to be at end of directory.\n",
 943                                         __FUNCTION__, ino->i_number);
 944                         goto fake_eod;
 945                 }
 946                 if (*p_high > max_size || (s64)*p_high << ibs_bits >
 947                                 attr->initialized) {
 948 fake_eod:
 949                         /* No more index records. */
 950                         *p_high = 0x7fff;
 951                         *p_low = 0;
 952                         ntfs_free(buf);
 953                         ntfs_debug(DEBUG_DIR3, "%s(): Unsorted 10.5: No more "
 954                                         "index records. Returning 0, p_high "
 955                                         "0x7fff, p_low 0.\n", __FUNCTION__);
 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, "%s(): Unsorted 11: Done. Returning 0, p_high "
 965                         "0x%x, p_low 0x%x.\n", __FUNCTION__, *p_high, *p_low);
 966         ntfs_free(buf);
 967         return 0;
 968 read_err_ret:
 969         if (!err)
 970                 err = -EIO;
 971         ntfs_error("%s(): Read failed. Returning error code %i.\n",
 972                         __FUNCTION__, err);
 973         ntfs_free(buf);
 974         return err;
 975 }
 976
 977 int ntfs_dir_add(ntfs_inode *dir, ntfs_inode *new, ntfs_attribute *name)
 978 {
 979         ntfs_iterate_s walk;
 980         int nsize, esize;
 981         ntfs_u8* entry, *ndata;
 982         int error;
 983
 984         walk.type = DIR_INSERT;
 985         walk.dir = dir;
 986         walk.u.flags = 0;
 987         nsize = name->size;
 988         ndata = name->d.data;
 989         walk.name = (ntfs_u16*)(ndata + 0x42);
 990         walk.namelen = NTFS_GETU8(ndata + 0x40);
 991         walk.new_entry_size = esize = (nsize + 0x10 + 7) & ~7;
 992         walk.new_entry = entry = ntfs_malloc(esize);
 993         if (!entry)
 994                 return -ENOMEM;
 995         NTFS_PUTINUM(entry, new);
 996         NTFS_PUTU16(entry + 0x8, esize); /* Size of entry. */
 997         NTFS_PUTU16(entry + 0xA, nsize); /* Size of original name attribute. */
 998         NTFS_PUTU16(entry + 0xC, 0);     /* Flags. */
 999         NTFS_PUTU16(entry + 0xE, 0);     /* Reserved. */
1000         ntfs_memcpy(entry + 0x10, ndata, nsize);
1001         ntfs_bzero(entry + 0x10 + nsize, esize - 0x10 - nsize);
1002         error = ntfs_getdir(&walk);
1003         if (walk.new_entry)
1004                 ntfs_free(walk.new_entry);
1005         return error;
1006 }
1007
1008 #if 0
1009 int ntfs_dir_add1(ntfs_inode *dir, const char* name, int namelen,
1010                   ntfs_inode *ino)
1011 {
1012         ntfs_iterate_s walk;
1013         int error;
1014         int nsize;
1015         char *entry;
1016         ntfs_attribute *name_attr;
1017         error = ntfs_decodeuni(dir->vol, name, namelen, &walk.name,
1018                                &walk.namelen);
1019         if (error)
1020                 return error;
1021         /* FIXME: Set flags. */
1022         walk.type = DIR_INSERT;
1023         walk.dir = dir;
1024         /* walk.new = ino; */
1025         /* Prepare new entry. */
1026         /* Round up to a multiple of 8. */
1027         walk.new_entry_size = nsize = ((0x52 + 2 * walk.namelen + 7) / 8) * 8;
1028         walk.new_entry = entry = ntfs_malloc(nsize);
1029         if (!entry)
1030                 return -ENOMEM;
1031         ntfs_bzero(entry, nsize);
1032         NTFS_PUTINUM(entry, ino);
1033         NTFS_PUTU16(entry + 8, nsize);
1034         NTFS_PUTU16(entry + 0xA, 0x42 + 2 * namelen); /* FIXME: Size of name
1035                                                        * attribute. */
1036         NTFS_PUTU32(entry + 0xC, 0); /* FIXME: D-F? */
1037         name_attr = ntfs_find_attr(ino, vol->at_file_name, 0);
1038                                                     /* FIXME: multiple names */
1039         if (!name_attr || !name_attr->resident)
1040                 return -EIDRM;
1041         /* Directory, file stamps, sizes, filename. */
1042         ntfs_memcpy(entry + 0x10, name_attr->d.data, 0x42 + 2 * namelen);
1043         error = ntfs_getdir(&walk);
1044         ntfs_free(walk.name);
1045         return error;
1046 }
1047 #endif
1048
1049 /* Fills out and creates an INDEX_ROOT attribute. */
1050 int ntfs_add_index_root(ntfs_inode *ino, int type)
1051 {
1052         ntfs_attribute *da;
1053         ntfs_u8 data[0x30]; /* 0x20 header, 0x10 last entry. */
1054         char name[10];
1055
1056         NTFS_PUTU32(data, type);
1057         /* Collation rule. 1 == COLLATION_FILENAME */
1058         NTFS_PUTU32(data + 4, 1);
1059         NTFS_PUTU32(data + 8, ino->vol->index_record_size);
1060         NTFS_PUTU32(data + 0xC, ino->vol->index_clusters_per_record);
1061         /* Byte offset to first INDEX_ENTRY. */
1062         NTFS_PUTU32(data + 0x10, 0x10);
1063         /* Size of entries, including header. */
1064         NTFS_PUTU32(data + 0x14, 0x20);
1065         NTFS_PUTU32(data + 0x18, 0x20);
1066         /* No index allocation, yet. */
1067         NTFS_PUTU32(data + 0x1C, 0);
1068         /* Add last entry. */
1069         /* Indexed MFT record. */
1070         NTFS_PUTU64(data + 0x20, 0);
1071         /* Size of entry. */
1072         NTFS_PUTU32(data + 0x28, 0x10);
1073         /* Flags: Last entry, no child nodes. */
1074         NTFS_PUTU32(data + 0x2C, 2);
1075         /* Compute name. */
1076         ntfs_indexname(name, type);
1077         return ntfs_create_attr(ino, ino->vol->at_index_root, name,
1078                                 data, sizeof(data), &da);
1079 }
1080
1081 int ntfs_mkdir(ntfs_inode *dir, const char *name, int namelen,
1082                ntfs_inode *result)
1083 {
1084         int error;
1085
1086         error = ntfs_alloc_inode(dir, result, name, namelen, NTFS_AFLAG_DIR);
1087         if (error)
1088                 goto out;
1089         error = ntfs_add_index_root(result, 0x30);
1090         if (error)
1091                 goto out;
1092         /* Set directory bit. */
1093         result->attr[0x16] |= 2;
1094         error = ntfs_update_inode(dir);
1095         if (error)
1096                 goto out;
1097         error = ntfs_update_inode(result);
1098         if (error)
1099                 goto out;
1100  out:
1101         return error;
1102 }
1103