libntfs/dir.c

   1 /*
   2  * dir.c - Directory handling code. Part of the Linux-NTFS project.
   3  *
   4  * Copyright (c) 2002 Anton Altaparmakov
   5  *
   6  * This program/include file is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as published
   8  * by the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program/include file is distributed in the hope that it will be
  12  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  13  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program (in the main directory of the Linux-NTFS
  18  * distribution in the file COPYING); if not, write to the Free Software
  19  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  */
  21
  22 #include <stdlib.h>
  23 #include <errno.h>
  24 #include <string.h>
  25
  26 #include "types.h"
  27 #include "debug.h"
  28 #include "attrib.h"
  29 #include "inode.h"
  30 #include "dir.h"
  31 #include "volume.h"
  32
  33 /*
  34  * The little endian Unicode string "$I30" as a global constant.
  35  */
  36 uchar_t I30[5] = { const_cpu_to_le16('$'), const_cpu_to_le16('I'),
  37                    const_cpu_to_le16('3'), const_cpu_to_le16('0'),
  38                    const_cpu_to_le16('\0') };
  39
  40 /**
  41  * ntfs_inode_lookup_by_name - find an inode in a directory given its name
  42  * @dir_ni:     ntfs inode of the directory in which to search for the name
  43  * @uname:      Unicode name for which to search in the directory
  44  * @uname_len:  length of the name @uname in Unicode characters
  45  *
  46  * Look for an inode with name @uname in the directory with inode @dir_ni.
  47  * ntfs_inode_lookup_by_name() walks the contents of the directory looking for
  48  * the Unicode name. If the name is found in the directory, the corresponding
  49  * inode number (>= 0) is returned as a mft reference in cpu format, i.e. it
  50  * is a 64-bit number containing the sequence number.
  51  *
  52  * On error, return -1 with errno set to the error code. If the inode is is not
  53  * found errno is ENOENT.
  54  *
  55  * Note, @uname_len does not include the (optional) terminating NULL character.
  56  *
  57  * Note, we look for a case sensitive match first but we also look for a case
  58  * insensitive match at the same time. If we find a case insensitive match, we
  59  * save that for the case that we don't find an exact match, where we return
  60  * the mft reference of the case insensitive match.
  61  *
  62  * If the volume is mounted with the case sensitive flag set, then we only
  63  * allow exact matches.
  64  */
  65 u64 ntfs_inode_lookup_by_name(ntfs_inode *dir_ni, const uchar_t *uname,
  66                 const int uname_len)
  67 {
  68         VCN vcn;
  69         u64 mref = 0;
  70         s64 br;
  71         ntfs_volume *vol = dir_ni->vol;
  72         ntfs_attr_search_ctx *ctx;
  73         INDEX_ROOT *ir;
  74         INDEX_ENTRY *ie;
  75         INDEX_ALLOCATION *ia;
  76         u8 *index_end;
  77         ntfs_attr *ia_na;
  78         int eo, rc;
  79         u32 index_block_size, index_vcn_size;
  80         u8 index_vcn_size_bits;
  81
  82         if (!dir_ni || !dir_ni->mrec || !uname || uname_len <= 0) {
  83                 errno = EINVAL;
  84                 return -1;
  85         }
  86
  87         ctx = ntfs_attr_get_search_ctx(dir_ni, NULL);
  88         if (!ctx)
  89                 return -1;
  90
  91         /* Find the index root attribute in the mft record. */
  92         if (ntfs_attr_lookup(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL,
  93                         0, ctx)) {
  94                 Dprintf("Index root attribute missing in directory inode "
  95                                 "0x%Lx: %s\n",
  96                                 (unsigned long long)dir_ni->mft_no,
  97                                 strerror(errno));
  98                 goto put_err_out;
  99         }
 100         /* Get to the index root value. */
 101         ir = (INDEX_ROOT*)((u8*)ctx->attr +
 102                         le16_to_cpu(ctx->attr->value_offset));
 103         index_block_size = le32_to_cpu(ir->index_block_size);
 104         if (index_block_size < NTFS_SECTOR_SIZE ||
 105                         index_block_size & (index_block_size - 1)) {
 106                 Dprintf("Index block size %u is invalid.\n", index_block_size);
 107                 goto put_err_out;
 108         }
 109         index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length);
 110         /* The first index entry. */
 111         ie = (INDEX_ENTRY*)((u8*)&ir->index +
 112                         le32_to_cpu(ir->index.entries_offset));
 113         /*
 114          * Loop until we exceed valid memory (corruption case) or until we
 115          * reach the last entry.
 116          */
 117         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 118                 /* Bounds checks. */
 119                 if ((u8*)ie < (u8*)ctx->mrec || (u8*)ie +
 120                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 121                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 122                                 index_end)
 123                         goto put_err_out;
 124                 /*
 125                  * The last entry cannot contain a name. It can however contain
 126                  * a pointer to a child node in the B+tree so we just break out.
 127                  */
 128                 if (ie->flags & INDEX_ENTRY_END)
 129                         break;
 130                 /*
 131                  * We perform a case sensitive comparison and if that matches
 132                  * we are done and return the mft reference of the inode (i.e.
 133                  * the inode number together with the sequence number for
 134                  * consistency checking). We convert it to cpu format before
 135                  * returning.
 136                  */
 137                 if (ntfs_names_are_equal(uname, uname_len,
 138                                 (uchar_t*)&ie->key.file_name.file_name,
 139                                 ie->key.file_name.file_name_length,
 140                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len)) {
 141 found_it:
 142                         /*
 143                          * We have a perfect match, so we don't need to care
 144                          * about having matched imperfectly before.
 145                          */
 146                         mref = le64_to_cpu(ie->indexed_file);
 147                         ntfs_attr_put_search_ctx(ctx);
 148                         return mref;
 149                 }
 150                 /*
 151                  * For a case insensitive mount, we also perform a case
 152                  * insensitive comparison (provided the file name is not in the
 153                  * POSIX namespace). If the comparison matches, we cache the
 154                  * mft reference in mref.
 155                  */
 156                 if (!NVolCaseSensitive(vol) &&
 157                                 ie->key.file_name.file_name_type &&
 158                                 ntfs_names_are_equal(uname, uname_len,
 159                                 (uchar_t*)&ie->key.file_name.file_name,
 160                                 ie->key.file_name.file_name_length,
 161                                 IGNORE_CASE, vol->upcase, vol->upcase_len)) {
 162                         /* Only one case insensitive matching name allowed. */
 163                         if (mref) {
 164                                 Dputs("Found already cached mft reference in "
 165                                                 "phase 1. Please run chkdsk "
 166                                                 "and if that doesn't find any "
 167                                                 "errors please report you saw "
 168                                                 "this message to "
 169                                                 "linux-ntfs-dev@lists.sf.net.");
 170                                 goto put_err_out;
 171                         }
 172                         mref = le64_to_cpu(ie->indexed_file);
 173                 }
 174                 /*
 175                  * Not a perfect match, need to do full blown collation so we
 176                  * know which way in the B+tree we have to go.
 177                  */
 178                 rc = ntfs_names_collate(uname, uname_len,
 179                                 (uchar_t*)&ie->key.file_name.file_name,
 180                                 ie->key.file_name.file_name_length, 1,
 181                                 IGNORE_CASE, vol->upcase, vol->upcase_len);
 182                 /*
 183                  * If uname collates before the name of the current entry, there
 184                  * is definitely no such name in this index but we might need to
 185                  * descend into the B+tree so we just break out of the loop.
 186                  */
 187                 if (rc == -1)
 188                         break;
 189                 /* The names are not equal, continue the search. */
 190                 if (rc)
 191                         continue;
 192                 /*
 193                  * Names match with case insensitive comparison, now try the
 194                  * case sensitive comparison, which is required for proper
 195                  * collation.
 196                  */
 197                 rc = ntfs_names_collate(uname, uname_len,
 198                                 (uchar_t*)&ie->key.file_name.file_name,
 199                                 ie->key.file_name.file_name_length, 1,
 200                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len);
 201                 if (rc == -1)
 202                         break;
 203                 if (rc)
 204                         continue;
 205                 /*
 206                  * Perfect match, this will never happen as the
 207                  * ntfs_are_names_equal() call will have gotten a match but we
 208                  * still treat it correctly.
 209                  */
 210                 goto found_it;
 211         }
 212         /*
 213          * We have finished with this index without success. Check for the
 214          * presence of a child node and if not present return error code
 215          * ENOENT, unless we have got the mft reference of a matching name
 216          * cached in mref in which case return mref.
 217          */
 218         if (!(ie->flags & INDEX_ENTRY_NODE)) {
 219                 ntfs_attr_put_search_ctx(ctx);
 220                 if (mref)
 221                         return mref;
 222                 Dputs("Entry not found.");
 223                 errno = ENOENT;
 224                 return -1;
 225         } /* Child node present, descend into it. */
 226
 227         /* Open the index allocation attribute. */
 228         ia_na = ntfs_attr_open(dir_ni, AT_INDEX_ALLOCATION, I30, 4);
 229         if (!ia_na) {
 230                 Dprintf("Failed to open index allocation attribute. Directory "
 231                                 "inode 0x%Lx is corrupt or driver bug: %s\n",
 232                                 (unsigned long long)dir_ni->mft_no,
 233                                 strerror(errno));
 234                 goto put_err_out;
 235         }
 236
 237         /* Allocate a buffer for the current index block. */
 238         ia = (INDEX_ALLOCATION*)malloc(index_block_size);
 239         if (!ia) {
 240                 Dperror("Failed to allocate buffer for index block");
 241                 goto put_err_out;
 242         }
 243
 244         /* Determine the size of a vcn in the directory index. */
 245         if (vol->cluster_size <= index_block_size) {
 246                 index_vcn_size = vol->cluster_size;
 247                 index_vcn_size_bits = vol->cluster_size_bits;
 248         } else {
 249                 index_vcn_size = vol->sector_size;
 250                 index_vcn_size_bits = vol->sector_size_bits;
 251         }
 252
 253         /* Get the starting vcn of the index_block holding the child node. */
 254         vcn = sle64_to_cpup((u8*)ie + le16_to_cpu(ie->length) - 8);
 255
 256 descend_into_child_node:
 257
 258         /* Read the index block starting at vcn. */
 259         br = ntfs_attr_mst_pread(ia_na, vcn << index_vcn_size_bits, 1,
 260                         index_block_size, ia);
 261         if (br != 1) {
 262                 if (br != -1)
 263                         errno = EIO;
 264                 Dprintf("Failed to read vcn 0x%Lx: %s\n", vcn, strerror(errno));
 265                 goto close_err_out;
 266         }
 267
 268         if (sle64_to_cpu(ia->index_block_vcn) != vcn) {
 269                 Dprintf("Actual VCN (0x%Lx) of index buffer is different from "
 270                                 "expected VCN (0x%Lx).\n",
 271                                 (long long)sle64_to_cpu(ia->index_block_vcn),
 272                                 (long long)vcn);
 273                 errno = EIO;
 274                 goto close_err_out;
 275         }
 276         if (le32_to_cpu(ia->index.allocated_size) + 0x18 != index_block_size) {
 277                 Dprintf("Index buffer (VCN 0x%Lx) of directory inode 0x%Lx "
 278                                 "has a size (%u) differing from the directory "
 279                                 "specified size (%u).\n", (long long)vcn,
 280                                 (unsigned long long)dir_ni->mft_no,
 281                                 le32_to_cpu(ia->index.allocated_size) + 0x18,
 282                                 index_block_size);
 283                 errno = EIO;
 284                 goto close_err_out;
 285         }
 286         index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);
 287         if (index_end > (u8*)ia + index_block_size) {
 288                 Dprintf("Size of index buffer (VCN 0x%Lx) of directory inode "
 289                                 "0x%Lx exceeds maximum size.\n", (long long)vcn,
 290                                 (unsigned long long)dir_ni->mft_no);
 291                 errno = EIO;
 292                 goto close_err_out;
 293         }
 294
 295         /* The first index entry. */
 296         ie = (INDEX_ENTRY*)((u8*)&ia->index +
 297                         le32_to_cpu(ia->index.entries_offset));
 298         /*
 299          * Iterate similar to above big loop but applied to index buffer, thus
 300          * loop until we exceed valid memory (corruption case) or until we
 301          * reach the last entry.
 302          */
 303         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 304                 /* Bounds check. */
 305                 if ((u8*)ie < (u8*)ia || (u8*)ie +
 306                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 307                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 308                                 index_end) {
 309                         Dprintf("Index entry out of bounds in directory inode "
 310                                         "0x%Lx.\n",
 311                                         (unsigned long long)dir_ni->mft_no);
 312                         errno = EIO;
 313                         goto close_err_out;
 314                 }
 315                 /*
 316                  * The last entry cannot contain a name. It can however contain
 317                  * a pointer to a child node in the B+tree so we just break out.
 318                  */
 319                 if (ie->flags & INDEX_ENTRY_END)
 320                         break;
 321                 /*
 322                  * We perform a case sensitive comparison and if that matches
 323                  * we are done and return the mft reference of the inode (i.e.
 324                  * the inode number together with the sequence number for
 325                  * consistency checking). We convert it to cpu format before
 326                  * returning.
 327                  */
 328                 if (ntfs_names_are_equal(uname, uname_len,
 329                                 (uchar_t*)&ie->key.file_name.file_name,
 330                                 ie->key.file_name.file_name_length,
 331                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len)) {
 332 found_it2:
 333                         /*
 334                          * We have a perfect match, so we don't need to care
 335                          * about having matched imperfectly before.
 336                          */
 337                         mref = le64_to_cpu(ie->indexed_file);
 338                         ntfs_attr_close(ia_na);
 339                         ntfs_attr_put_search_ctx(ctx);
 340                         return mref;
 341                 }
 342                 /*
 343                  * For a case insensitive mount, we also perform a case
 344                  * insensitive comparison (provided the file name is not in the
 345                  * POSIX namespace). If the comparison matches, we cache the
 346                  * mft reference in mref.
 347                  */
 348                 if (!NVolCaseSensitive(vol) &&
 349                                 ie->key.file_name.file_name_type &&
 350                                 ntfs_names_are_equal(uname, uname_len,
 351                                 (uchar_t*)&ie->key.file_name.file_name,
 352                                 ie->key.file_name.file_name_length,
 353                                 IGNORE_CASE, vol->upcase, vol->upcase_len)) {
 354                         /* Only one case insensitive matching name allowed. */
 355                         if (mref) {
 356                                 Dputs("Found already cached mft reference in "
 357                                                 "phase 2. Please run chkdsk "
 358                                                 "and if that doesn't find any "
 359                                                 "errors please report you saw "
 360                                                 "this message to "
 361                                                 "linux-ntfs-dev@lists.sf.net.");
 362                                 goto close_err_out;
 363                         }
 364                         mref = le64_to_cpu(ie->indexed_file);
 365                 }
 366                 /*
 367                  * Not a perfect match, need to do full blown collation so we
 368                  * know which way in the B+tree we have to go.
 369                  */
 370                 rc = ntfs_names_collate(uname, uname_len,
 371                                 (uchar_t*)&ie->key.file_name.file_name,
 372                                 ie->key.file_name.file_name_length, 1,
 373                                 IGNORE_CASE, vol->upcase, vol->upcase_len);
 374                 /*
 375                  * If uname collates before the name of the current entry, there
 376                  * is definitely no such name in this index but we might need to
 377                  * descend into the B+tree so we just break out of the loop.
 378                  */
 379                 if (rc == -1)
 380                         break;
 381                 /* The names are not equal, continue the search. */
 382                 if (rc)
 383                         continue;
 384                 /*
 385                  * Names match with case insensitive comparison, now try the
 386                  * case sensitive comparison, which is required for proper
 387                  * collation.
 388                  */
 389                 rc = ntfs_names_collate(uname, uname_len,
 390                                 (uchar_t*)&ie->key.file_name.file_name,
 391                                 ie->key.file_name.file_name_length, 1,
 392                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len);
 393                 if (rc == -1)
 394                         break;
 395                 if (rc)
 396                         continue;
 397                 /*
 398                  * Perfect match, this will never happen as the
 399                  * ntfs_are_names_equal() call will have gotten a match but we
 400                  * still treat it correctly.
 401                  */
 402                 goto found_it2;
 403         }
 404         /*
 405          * We have finished with this index buffer without success. Check for
 406          * the presence of a child node.
 407          */
 408         if (ie->flags & INDEX_ENTRY_NODE) {
 409                 if ((ia->index.flags & NODE_MASK) == LEAF_NODE) {
 410                         Dprintf("Index entry with child node found in a leaf "
 411                                         "node in directory inode 0x%Lx.\n",
 412                                         (unsigned long long)dir_ni->mft_no);
 413                         errno = EIO;
 414                         goto close_err_out;
 415                 }
 416                 /* Child node present, descend into it. */
 417                 vcn = sle64_to_cpup((u8*)ie + le16_to_cpu(ie->length) - 8);
 418                 if (vcn >= 0)
 419                         goto descend_into_child_node;
 420                 Dprintf("Negative child node vcn in directory inode 0x%Lx.\n",
 421                                 (unsigned long long)dir_ni->mft_no);
 422                 errno = EIO;
 423                 goto close_err_out;
 424         }
 425         ntfs_attr_close(ia_na);
 426         ntfs_attr_put_search_ctx(ctx);
 427         /*
 428          * No child node present, return error code ENOENT, unless we have got
 429          * the mft reference of a matching name cached in mref in which case
 430          * return mref.
 431          */
 432         if (mref)
 433                 return mref;
 434         Dputs("Entry not found.");
 435         errno = ENOENT;
 436         return -1;
 437 put_err_out:
 438         eo = EIO;
 439         Dputs("Corrupt directory. Aborting lookup.");
 440 eo_put_err_out:
 441         ntfs_attr_put_search_ctx(ctx);
 442         errno = eo;
 443         return -1;
 444 close_err_out:
 445         eo = errno;
 446         free(ia);
 447         ntfs_attr_close(ia_na);
 448         goto eo_put_err_out;
 449 }
 450
 451 /*
 452  * The little endian Unicode string ".." for ntfs_readdir().
 453  */
 454 static const uchar_t dotdot[3] = { const_cpu_to_le16('.'),
 455                                    const_cpu_to_le16('.'),
 456                                    const_cpu_to_le16('\0') };
 457
 458 /*
 459  * More helpers for ntfs_readdir().
 460  */
 461 typedef union {
 462         INDEX_ROOT *ir;
 463         INDEX_ALLOCATION *ia;
 464 } index_union __attribute__ ((__transparent_union__));
 465
 466 typedef enum {
 467         INDEX_TYPE_ROOT,        /* index root */
 468         INDEX_TYPE_ALLOCATION,  /* index allocation */
 469 } INDEX_TYPE;
 470
 471 /**
 472  * Internal:
 473  *
 474  * ntfs_filldir - ntfs specific filldir method
 475  * @dir_ni:     ntfs inode of current directory
 476  * @pos:        current position in directory
 477  * @ivcn_bits:  log(2) of index vcn size
 478  * @index_type: specifies whether @iu is an index root or an index allocation
 479  * @iu:         index root or index block to which @ie belongs
 480  * @ie:         current index entry
 481  * @dirent:     context for filldir callback supplied by the caller
 482  * @filldir:    filldir callback supplied by the caller
 483  *
 484  * Pass information specifying the current directory entry @ie to the @filldir
 485  * callback.
 486  */
 487 static inline int ntfs_filldir(ntfs_inode *dir_ni, s64 *pos, u8 ivcn_bits,
 488                 const INDEX_TYPE index_type, index_union iu, INDEX_ENTRY *ie,
 489                 void *dirent, ntfs_filldir_t filldir)
 490 {
 491         FILE_NAME_ATTR *fn = &ie->key.file_name;
 492         unsigned dt_type;
 493
 494         /* Advance the position even if going to skip the entry. */
 495         if (index_type == INDEX_TYPE_ALLOCATION)
 496                 *pos = (u8*)ie - (u8*)iu.ia + (sle64_to_cpu(
 497                                 iu.ia->index_block_vcn) << ivcn_bits) +
 498                                 dir_ni->vol->mft_record_size;
 499         else /* if (index_type == INDEX_TYPE_ROOT) */
 500                 *pos = (u8*)ie - (u8*)iu.ir;
 501         /* Skip root directory self reference entry. */
 502         if (MREF_LE(ie->indexed_file) == FILE_root)
 503                 return 0;
 504         if (ie->key.file_name.file_attributes &
 505                         FILE_ATTR_DUP_FILE_NAME_INDEX_PRESENT)
 506                 dt_type = NTFS_DT_DIR;
 507         else
 508                 dt_type = NTFS_DT_REG;
 509         return filldir(dirent, fn->file_name, fn->file_name_length,
 510                         fn->file_name_type, *pos,
 511                         le64_to_cpu(ie->indexed_file), dt_type);
 512 }
 513
 514 /**
 515  * Internal:
 516  *
 517  * ntfs_mft_get_parent_ref - find mft reference of parent directory of an inode
 518  * @ni:         ntfs inode whose parent directory to find
 519  *
 520  * Find the parent directory of the ntfs inode @ni. To do this, find the first
 521  * file name attribute in the mft record of @ni and return the parent mft
 522  * reference from that.
 523  *
 524  * Note this only makes sense for directories, since files can be hard linked
 525  * from multiple directories and there is no way for us to tell which one is
 526  * being looked for.
 527  *
 528  * Technically directories can have hard links, too, but we consider that as
 529  * illegal as Linux/UNIX do not support directory hard links.
 530  *
 531  * Return the mft reference of the parent directory on success or -1 on error
 532  * with errno set to the error code.
 533  */
 534 static MFT_REF ntfs_mft_get_parent_ref(ntfs_inode *ni)
 535 {
 536         MFT_REF mref;
 537         ntfs_attr_search_ctx *ctx;
 538         FILE_NAME_ATTR *fn;
 539         int eo;
 540
 541         if (!ni) {
 542                 errno = EINVAL;
 543                 return -1;
 544         }
 545
 546         ctx = ntfs_attr_get_search_ctx(ni, NULL);
 547         if (!ctx)
 548                 return -1;
 549         if (ntfs_attr_lookup(AT_FILE_NAME, AT_UNNAMED, 0, 0, 0, NULL, 0, ctx)) {
 550                 Dprintf("No file name found in inode 0x%Lx. Corrupt inode.\n",
 551                                 (unsigned long long)ni->mft_no);
 552                 goto err_out;
 553         }
 554         if (ctx->attr->non_resident) {
 555                 Dprintf("File name attribute must be resident. Corrupt inode "
 556                                 "0x%Lx.\n", (unsigned long long)ni->mft_no);
 557                 goto io_err_out;
 558         }
 559         fn = (FILE_NAME_ATTR*)((u8*)ctx->attr +
 560                         le16_to_cpu(ctx->attr->value_offset));
 561         if ((u8*)fn +   le32_to_cpu(ctx->attr->value_length) >
 562                         (u8*)ctx->attr + le32_to_cpu(ctx->attr->length)) {
 563                 Dprintf("Corrupt file name attribute in inode 0x%Lx.\n",
 564                                 (unsigned long long)ni->mft_no);
 565                 goto io_err_out;
 566         }
 567         mref = le64_to_cpu(fn->parent_directory);
 568         ntfs_attr_put_search_ctx(ctx);
 569         return mref;
 570 io_err_out:
 571         errno = EIO;
 572 err_out:
 573         eo = errno;
 574         ntfs_attr_put_search_ctx(ctx);
 575         errno = eo;
 576         return -1;
 577 }
 578
 579 /**
 580  * ntfs_readdir - read the contents of an ntfs directory
 581  * @dir_ni:     ntfs inode of current directory
 582  * @pos:        current position in directory
 583  * @dirent:     context for filldir callback supplied by the caller
 584  * @filldir:    filldir callback supplied by the caller
 585  *
 586  * Parse the index root and the index blocks that are marked in use in the
 587  * index bitmap and hand each found directory entry to the @filldir callback
 588  * supplied by the caller.
 589  *
 590  * Return 0 on success or -1 on error with errno set to the error code.
 591  *
 592  * Note: Index blocks are parsed in ascending vcn order, from which follows
 593  * that the directory entries are not returned sorted.
 594  */
 595 int ntfs_readdir(ntfs_inode *dir_ni, s64 *pos,
 596                 void *dirent, ntfs_filldir_t filldir)
 597 {
 598         s64 i_size, br, ia_pos, bmp_pos, ia_start;
 599         ntfs_volume *vol;
 600         ntfs_attr *ia_na, *bmp_na = NULL;
 601         ntfs_attr_search_ctx *ctx = NULL;
 602         u8 *index_end, *bmp;
 603         INDEX_ROOT *ir;
 604         INDEX_ENTRY *ie;
 605         INDEX_ALLOCATION *ia;
 606         int rc, ir_pos, bmp_buf_size, bmp_buf_pos, eo;
 607         u32 index_block_size, index_vcn_size;
 608         u8 index_block_size_bits, index_vcn_size_bits;
 609
 610         if (!dir_ni || !pos || !filldir) {
 611                 errno = EINVAL;
 612                 return -1;
 613         }
 614
 615         vol = dir_ni->vol;
 616
 617         Dprintf("Entering for inode 0x%Lx, *pos 0x%Lx.\n",
 618                         (unsigned long long)dir_ni->mft_no, (long long)*pos);
 619
 620         /* Open the index allocation attribute. */
 621         ia_na = ntfs_attr_open(dir_ni, AT_INDEX_ALLOCATION, I30, 4);
 622         if (!ia_na) {
 623                 if (errno != ENOENT) {
 624                         Dprintf("Failed to open index allocation attribute. "
 625                                         "Directory inode 0x%Lx is corrupt or "
 626                                         "bug: %s\n",
 627                                         (unsigned long long)dir_ni->mft_no,
 628                                         strerror(errno));
 629                         return -1;
 630                 }
 631                 i_size = 0;
 632         } else
 633                 i_size = ia_na->data_size;
 634
 635         rc = 0;
 636
 637         /* Are we at end of dir yet? */
 638         if (*pos >= i_size + vol->mft_record_size)
 639                 goto done;
 640
 641         /* Emulate . and .. for all directories. */
 642         if (!*pos) {
 643                 rc = filldir(dirent, dotdot, 1, FILE_NAME_POSIX, *pos,
 644                                 MK_MREF(dir_ni->mft_no,
 645                                 le16_to_cpu(dir_ni->mrec->sequence_number)),
 646                                 NTFS_DT_DIR);
 647                 if (rc)
 648                         goto done;
 649                 ++*pos;
 650         }
 651         if (*pos == 1) {
 652                 MFT_REF parent_mref;
 653
 654                 parent_mref = ntfs_mft_get_parent_ref(dir_ni);
 655                 if (parent_mref == -1) {
 656                         Dprintf("Parent directory not found: %s\n", errno);
 657                         goto dir_err_out;
 658                 }
 659
 660                 rc = filldir(dirent, dotdot, 2, FILE_NAME_POSIX, *pos,
 661                                 parent_mref, NTFS_DT_DIR);
 662                 if (rc)
 663                         goto done;
 664                 ++*pos;
 665         }
 666
 667         ctx = ntfs_attr_get_search_ctx(dir_ni, NULL);
 668         if (!ctx)
 669                 goto err_out;
 670
 671         /* Get the offset into the index root attribute. */
 672         ir_pos = (int)*pos;
 673         /* Find the index root attribute in the mft record. */
 674         if (ntfs_attr_lookup(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL,
 675                         0, ctx)) {
 676                 Dprintf("Index root attribute missing in directory inode "
 677                                 "0x%Lx.\n", (unsigned long long)dir_ni->mft_no);
 678                 goto dir_err_out;
 679         }
 680         /* Get to the index root value. */
 681         ir = (INDEX_ROOT*)((u8*)ctx->attr +
 682                         le16_to_cpu(ctx->attr->value_offset));
 683
 684         /* Determine the size of a vcn in the directory index. */
 685         index_block_size = le32_to_cpu(ir->index_block_size);
 686         if (index_block_size < NTFS_SECTOR_SIZE ||
 687                         index_block_size & (index_block_size - 1)) {
 688                 Dprintf("Index block size %u is invalid.\n", index_block_size);
 689                 goto dir_err_out;
 690         }
 691         index_block_size_bits = ffs(index_block_size) - 1;
 692         if (vol->cluster_size <= index_block_size) {
 693                 index_vcn_size = vol->cluster_size;
 694                 index_vcn_size_bits = vol->cluster_size_bits;
 695         } else {
 696                 index_vcn_size = vol->sector_size;
 697                 index_vcn_size_bits = vol->sector_size_bits;
 698         }
 699
 700         /* Are we jumping straight into the index allocation attribute? */
 701         if (*pos >= vol->mft_record_size) {
 702                 ntfs_attr_put_search_ctx(ctx);
 703                 ctx = NULL;
 704                 goto skip_index_root;
 705         }
 706
 707         index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length);
 708         /* The first index entry. */
 709         ie = (INDEX_ENTRY*)((u8*)&ir->index +
 710                         le32_to_cpu(ir->index.entries_offset));
 711         /*
 712          * Loop until we exceed valid memory (corruption case) or until we
 713          * reach the last entry or until filldir tells us it has had enough
 714          * or signals an error (both covered by the rc test).
 715          */
 716         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 717                 Dprintf("In index root, offset 0x%x.\n", (u8*)ie - (u8*)ir);
 718                 /* Bounds checks. */
 719                 if ((u8*)ie < (u8*)ctx->mrec || (u8*)ie +
 720                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 721                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 722                                 index_end)
 723                         goto dir_err_out;
 724                 /* The last entry cannot contain a name. */
 725                 if (ie->flags & INDEX_ENTRY_END)
 726                         break;
 727                 /* Skip index root entry if continuing previous readdir. */
 728                 if (ir_pos > (u8*)ie - (u8*)ir)
 729                         continue;
 730                 /*
 731                  * Submit the directory entry to ntfs_filldir(), which will
 732                  * invoke the filldir() callback as appropriate.
 733                  */
 734                 rc = ntfs_filldir(dir_ni, pos, index_vcn_size_bits,
 735                                 INDEX_TYPE_ROOT, ir, ie, dirent, filldir);
 736                 if (rc) {
 737                         ntfs_attr_put_search_ctx(ctx);
 738                         ctx = NULL;
 739                         goto done;
 740                 }
 741         }
 742         ntfs_attr_put_search_ctx(ctx);
 743         ctx = NULL;
 744
 745         /* If there is no index allocation attribute we are finished. */
 746         if (!ia_na)
 747                 goto EOD;
 748
 749         /* Advance *pos to the beginning of the index allocation. */
 750         *pos = vol->mft_record_size;
 751
 752 skip_index_root:
 753
 754         if (!ia_na)
 755                 goto done;
 756
 757         /* Allocate a buffer for the current index block. */
 758         ia = (INDEX_ALLOCATION*)malloc(index_block_size);
 759         if (!ia) {
 760                 Dperror("Failed to allocate buffer for index block");
 761                 goto err_out;
 762         }
 763
 764         bmp_na = ntfs_attr_open(dir_ni, AT_BITMAP, I30, 4);
 765         if (!bmp_na) {
 766                 Dperror("Failed to open index bitmap attribute");
 767                 goto dir_err_out;
 768         }
 769
 770         /* Get the offset into the index allocation attribute. */
 771         ia_pos = *pos - vol->mft_record_size;
 772
 773         bmp_pos = ia_pos >> index_block_size_bits;
 774         if (bmp_pos >> 3 >= bmp_na->data_size) {
 775                 Dputs("Current index position exceeds index bitmap size.");
 776                 goto dir_err_out;
 777         }
 778
 779         bmp_buf_size = min(bmp_na->data_size - (bmp_pos >> 3), 4096);
 780         bmp = (u8*)malloc(bmp_buf_size);
 781         if (!bmp) {
 782                 Dperror("Failed to allocate bitmap buffer");
 783                 goto err_out;
 784         }
 785
 786         br = ntfs_attr_pread(bmp_na, bmp_pos >> 3, bmp_buf_size, bmp);
 787         if (br != bmp_buf_size) {
 788                 if (br != -1)
 789                         errno = EIO;
 790                 Dperror("Failed to read from inde bitmap attribute");
 791                 goto err_out;
 792         }
 793
 794         bmp_buf_pos = 0;
 795         /* If the index block is not in use find the next one that is. */
 796         while (!(bmp[bmp_buf_pos >> 3] & (1 << (bmp_buf_pos & 7)))) {
 797 find_next_index_buffer:
 798                 bmp_pos++;
 799                 bmp_buf_pos++;
 800                 /* If we have reached the end of the bitmap, we are done. */
 801                 if (bmp_pos >> 3 >= bmp_na->data_size)
 802                         goto EOD;
 803                 ia_pos = bmp_pos << index_block_size_bits;
 804                 if (bmp_buf_pos >> 3 < bmp_buf_size)
 805                         continue;
 806                 /* Read next chunk from the index bitmap. */
 807                 if ((bmp_pos >> 3) + bmp_buf_size > bmp_na->data_size)
 808                         bmp_buf_size = bmp_na->data_size - (bmp_pos >> 3);
 809                 br = ntfs_attr_pread(bmp_na, bmp_pos >> 3, bmp_buf_size, bmp);
 810                 if (br != bmp_buf_size) {
 811                         if (br != -1)
 812                                 errno = EIO;
 813                         Dperror("Failed to read from inde bitmap attribute");
 814                         goto err_out;
 815                 }
 816         }
 817
 818         Dprintf("Handling index block 0x%Lx.", (long long)bmp_pos);
 819
 820         /* Read the index block starting at bmp_pos. */
 821         br = ntfs_attr_mst_pread(ia_na, bmp_pos << index_block_size_bits, 1,
 822                         index_block_size, ia);
 823         if (br != 1) {
 824                 if (br != -1)
 825                         errno = EIO;
 826                 Dperror("Failed to read index block");
 827                 goto err_out;
 828         }
 829
 830         ia_start = ia_pos & ~(s64)(index_block_size - 1);
 831         if (sle64_to_cpu(ia->index_block_vcn) != ia_start >>
 832                         index_vcn_size_bits) {
 833                 Dprintf("Actual VCN (0x%Lx) of index buffer is different from "
 834                                 "expected VCN (0x%Lx) in inode 0x%Lx.\n",
 835                                 (long long)sle64_to_cpu(ia->index_block_vcn),
 836                                 (long long)ia_start >> index_vcn_size_bits,
 837                                 (unsigned long long)dir_ni->mft_no);
 838                 goto dir_err_out;
 839         }
 840         if (le32_to_cpu(ia->index.allocated_size) + 0x18 != index_block_size) {
 841                 Dprintf("Index buffer (VCN 0x%Lx) of directory inode 0x%Lx "
 842                                 "has a size (%u) differing from the directory "
 843                                 "specified size (%u).\n",
 844                                 (long long)ia_start >> index_vcn_size_bits,
 845                                 (unsigned long long)dir_ni->mft_no,
 846                                 le32_to_cpu(ia->index.allocated_size) + 0x18,
 847                                 index_block_size);
 848                 goto dir_err_out;
 849         }
 850         index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);
 851         if (index_end > (u8*)ia + index_block_size) {
 852                 Dprintf("Size of index buffer (VCN 0x%Lx) of directory inode "
 853                                 "0x%Lx exceeds maximum size.\n",
 854                                 (long long)ia_start >> index_vcn_size_bits,
 855                                 (unsigned long long)dir_ni->mft_no);
 856                 goto dir_err_out;
 857         }
 858         /* The first index entry. */
 859         ie = (INDEX_ENTRY*)((u8*)&ia->index +
 860                         le32_to_cpu(ia->index.entries_offset));
 861         /*
 862          * Loop until we exceed valid memory (corruption case) or until we
 863          * reach the last entry or until ntfs_filldir tells us it has had
 864          * enough or signals an error (both covered by the rc test).
 865          */
 866         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 867                 Dprintf("In index allocation, offset 0x%Lx.\n",
 868                                 (long long)ia_start + ((u8*)ie - (u8*)ia));
 869                 /* Bounds checks. */
 870                 if ((u8*)ie < (u8*)ia || (u8*)ie +
 871                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 872                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 873                                 index_end) {
 874                         Dprintf("Index entry out of bounds in directory inode "
 875                                         "0x%Lx.\n",
 876                                         (unsigned long long)dir_ni->mft_no);
 877                         goto dir_err_out;
 878                 }
 879                 /* The last entry cannot contain a name. */
 880                 if (ie->flags & INDEX_ENTRY_END)
 881                         break;
 882                 /* Skip index entry if continuing previous readdir. */
 883                 if (ia_pos - ia_start > (u8*)ie - (u8*)ia)
 884                         continue;
 885                 /*
 886                  * Submit the directory entry to ntfs_filldir(), which will
 887                  * invoke the filldir() callback as appropriate.
 888                  */
 889                 rc = ntfs_filldir(dir_ni, pos, index_vcn_size_bits,
 890                                 INDEX_TYPE_ALLOCATION, ia, ie, dirent, filldir);
 891                 if (rc)
 892                         goto done;
 893         }
 894         goto find_next_index_buffer;
 895 EOD:
 896         /* We are finished, set *pos to EOD. */
 897         *pos = i_size + vol->mft_record_size;
 898 done:
 899         if (bmp_na)
 900                 ntfs_attr_close(bmp_na);
 901         ntfs_attr_close(ia_na);
 902 #ifdef DEBUG
 903         if (!rc)
 904                 Dprintf("EOD, *pos 0x%Lx, returning 0.\n", (long long)*pos);
 905         else
 906                 Dprintf("filldir returned %i, *pos 0x%Lx, returning 0.\n",
 907                                 rc, (long long)*pos);
 908 #endif
 909         return 0;
 910 dir_err_out:
 911         errno = EIO;
 912 err_out:
 913         eo = errno;
 914         Dprintf("%s() failed.\n", __FUNCTION__);
 915         if (ctx)
 916                 ntfs_attr_put_search_ctx(ctx);
 917         if (bmp_na)
 918                 ntfs_attr_close(bmp_na);
 919         ntfs_attr_close(ia_na);
 920         errno = eo;
 921         return -1;
 922 }
 923