fs/ntfs/dir.c

   1 /**
   2  * dir.c - NTFS kernel directory operations. Part of the Linux-NTFS project.
   3  *
   4  * Copyright (c) 2001-2004 Anton Altaparmakov
   5  * Copyright (c) 2002 Richard Russon
   6  *
   7  * This program/include file is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as published
   9  * by the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program/include file is distributed in the hope that it will be
  13  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program (in the main directory of the Linux-NTFS
  19  * distribution in the file COPYING); if not, write to the Free Software
  20  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  */
  22
  23 #include <linux/smp_lock.h>
  24 #include "ntfs.h"
  25 #include "dir.h"
  26
  27 /**
  28  * The little endian Unicode string $I30 as a global constant.
  29  */
  30 ntfschar I30[5] = { const_cpu_to_le16('$'), const_cpu_to_le16('I'),
  31                 const_cpu_to_le16('3'), const_cpu_to_le16('0'),
  32                 const_cpu_to_le16(0) };
  33
  34 /**
  35  * ntfs_lookup_inode_by_name - find an inode in a directory given its name
  36  * @dir_ni:     ntfs inode of the directory in which to search for the name
  37  * @uname:      Unicode name for which to search in the directory
  38  * @uname_len:  length of the name @uname in Unicode characters
  39  * @res:        return the found file name if necessary (see below)
  40  *
  41  * Look for an inode with name @uname in the directory with inode @dir_ni.
  42  * ntfs_lookup_inode_by_name() walks the contents of the directory looking for
  43  * the Unicode name. If the name is found in the directory, the corresponding
  44  * inode number (>= 0) is returned as a mft reference in cpu format, i.e. it
  45  * is a 64-bit number containing the sequence number.
  46  *
  47  * On error, a negative value is returned corresponding to the error code. In
  48  * particular if the inode is not found -ENOENT is returned. Note that you
  49  * can't just check the return value for being negative, you have to check the
  50  * inode number for being negative which you can extract using MREC(return
  51  * value).
  52  *
  53  * Note, @uname_len does not include the (optional) terminating NULL character.
  54  *
  55  * Note, we look for a case sensitive match first but we also look for a case
  56  * insensitive match at the same time. If we find a case insensitive match, we
  57  * save that for the case that we don't find an exact match, where we return
  58  * the case insensitive match and setup @res (which we allocate!) with the mft
  59  * reference, the file name type, length and with a copy of the little endian
  60  * Unicode file name itself. If we match a file name which is in the DOS name
  61  * space, we only return the mft reference and file name type in @res.
  62  * ntfs_lookup() then uses this to find the long file name in the inode itself.
  63  * This is to avoid polluting the dcache with short file names. We want them to
  64  * work but we don't care for how quickly one can access them. This also fixes
  65  * the dcache aliasing issues.
  66  */
  67 MFT_REF ntfs_lookup_inode_by_name(ntfs_inode *dir_ni, const ntfschar *uname,
  68                 const int uname_len, ntfs_name **res)
  69 {
  70         ntfs_volume *vol = dir_ni->vol;
  71         struct super_block *sb = vol->sb;
  72         MFT_RECORD *m;
  73         INDEX_ROOT *ir;
  74         INDEX_ENTRY *ie;
  75         INDEX_ALLOCATION *ia;
  76         u8 *index_end;
  77         u64 mref;
  78         attr_search_context *ctx;
  79         int err, rc;
  80         VCN vcn, old_vcn;
  81         struct address_space *ia_mapping;
  82         struct page *page;
  83         u8 *kaddr;
  84         ntfs_name *name = NULL;
  85
  86         /* Get hold of the mft record for the directory. */
  87         m = map_mft_record(dir_ni);
  88         if (unlikely(IS_ERR(m))) {
  89                 ntfs_error(sb, "map_mft_record() failed with error code %ld.",
  90                                 -PTR_ERR(m));
  91                 return ERR_MREF(PTR_ERR(m));
  92         }
  93         ctx = get_attr_search_ctx(dir_ni, m);
  94         if (unlikely(!ctx)) {
  95                 err = -ENOMEM;
  96                 goto err_out;
  97         }
  98         /* Find the index root attribute in the mft record. */
  99         if (!lookup_attr(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL, 0,
 100                         ctx)) {
 101                 ntfs_error(sb, "Index root attribute missing in directory "
 102                                 "inode 0x%lx.", dir_ni->mft_no);
 103                 err = -EIO;
 104                 goto err_out;
 105         }
 106         /* Get to the index root value (it's been verified in read_inode). */
 107         ir = (INDEX_ROOT*)((u8*)ctx->attr +
 108                         le16_to_cpu(ctx->attr->data.resident.value_offset));
 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 dir_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_are_names_equal(uname, uname_len,
 138                                 (ntfschar*)&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, so we can
 145                          * free name and set *res to NULL.
 146                          * However, if the perfect match is a short file name,
 147                          * we need to signal this through *res, so that
 148                          * ntfs_lookup() can fix dcache aliasing issues.
 149                          * As an optimization we just reuse an existing
 150                          * allocation of *res.
 151                          */
 152                         if (ie->key.file_name.file_name_type == FILE_NAME_DOS) {
 153                                 if (!name) {
 154                                         name = kmalloc(sizeof(ntfs_name),
 155                                                         GFP_NOFS);
 156                                         if (!name) {
 157                                                 err = -ENOMEM;
 158                                                 goto err_out;
 159                                         }
 160                                 }
 161                                 name->mref = le64_to_cpu(
 162                                                 ie->data.dir.indexed_file);
 163                                 name->type = FILE_NAME_DOS;
 164                                 name->len = 0;
 165                                 *res = name;
 166                         } else {
 167                                 if (name)
 168                                         kfree(name);
 169                                 *res = NULL;
 170                         }
 171                         mref = le64_to_cpu(ie->data.dir.indexed_file);
 172                         put_attr_search_ctx(ctx);
 173                         unmap_mft_record(dir_ni);
 174                         return mref;
 175                 }
 176                 /*
 177                  * For a case insensitive mount, we also perform a case
 178                  * insensitive comparison (provided the file name is not in the
 179                  * POSIX namespace). If the comparison matches, and the name is
 180                  * in the WIN32 namespace, we cache the filename in *res so
 181                  * that the caller, ntfs_lookup(), can work on it. If the
 182                  * comparison matches, and the name is in the DOS namespace, we
 183                  * only cache the mft reference and the file name type (we set
 184                  * the name length to zero for simplicity).
 185                  */
 186                 if (!NVolCaseSensitive(vol) &&
 187                                 ie->key.file_name.file_name_type &&
 188                                 ntfs_are_names_equal(uname, uname_len,
 189                                 (ntfschar*)&ie->key.file_name.file_name,
 190                                 ie->key.file_name.file_name_length,
 191                                 IGNORE_CASE, vol->upcase, vol->upcase_len)) {
 192                         int name_size = sizeof(ntfs_name);
 193                         u8 type = ie->key.file_name.file_name_type;
 194                         u8 len = ie->key.file_name.file_name_length;
 195
 196                         /* Only one case insensitive matching name allowed. */
 197                         if (name) {
 198                                 ntfs_error(sb, "Found already allocated name "
 199                                                 "in phase 1. Please run chkdsk "
 200                                                 "and if that doesn't find any "
 201                                                 "errors please report you saw "
 202                                                 "this message to "
 203                                                 "linux-ntfs-dev@lists."
 204                                                 "sourceforge.net.");
 205                                 goto dir_err_out;
 206                         }
 207
 208                         if (type != FILE_NAME_DOS)
 209                                 name_size += len * sizeof(ntfschar);
 210                         name = kmalloc(name_size, GFP_NOFS);
 211                         if (!name) {
 212                                 err = -ENOMEM;
 213                                 goto err_out;
 214                         }
 215                         name->mref = le64_to_cpu(ie->data.dir.indexed_file);
 216                         name->type = type;
 217                         if (type != FILE_NAME_DOS) {
 218                                 name->len = len;
 219                                 memcpy(name->name, ie->key.file_name.file_name,
 220                                                 len * sizeof(ntfschar));
 221                         } else
 222                                 name->len = 0;
 223                         *res = name;
 224                 }
 225                 /*
 226                  * Not a perfect match, need to do full blown collation so we
 227                  * know which way in the B+tree we have to go.
 228                  */
 229                 rc = ntfs_collate_names(uname, uname_len,
 230                                 (ntfschar*)&ie->key.file_name.file_name,
 231                                 ie->key.file_name.file_name_length, 1,
 232                                 IGNORE_CASE, vol->upcase, vol->upcase_len);
 233                 /*
 234                  * If uname collates before the name of the current entry, there
 235                  * is definitely no such name in this index but we might need to
 236                  * descend into the B+tree so we just break out of the loop.
 237                  */
 238                 if (rc == -1)
 239                         break;
 240                 /* The names are not equal, continue the search. */
 241                 if (rc)
 242                         continue;
 243                 /*
 244                  * Names match with case insensitive comparison, now try the
 245                  * case sensitive comparison, which is required for proper
 246                  * collation.
 247                  */
 248                 rc = ntfs_collate_names(uname, uname_len,
 249                                 (ntfschar*)&ie->key.file_name.file_name,
 250                                 ie->key.file_name.file_name_length, 1,
 251                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len);
 252                 if (rc == -1)
 253                         break;
 254                 if (rc)
 255                         continue;
 256                 /*
 257                  * Perfect match, this will never happen as the
 258                  * ntfs_are_names_equal() call will have gotten a match but we
 259                  * still treat it correctly.
 260                  */
 261                 goto found_it;
 262         }
 263         /*
 264          * We have finished with this index without success. Check for the
 265          * presence of a child node and if not present return -ENOENT, unless
 266          * we have got a matching name cached in name in which case return the
 267          * mft reference associated with it.
 268          */
 269         if (!(ie->flags & INDEX_ENTRY_NODE)) {
 270                 if (name) {
 271                         put_attr_search_ctx(ctx);
 272                         unmap_mft_record(dir_ni);
 273                         return name->mref;
 274                 }
 275                 ntfs_debug("Entry not found.");
 276                 err = -ENOENT;
 277                 goto err_out;
 278         } /* Child node present, descend into it. */
 279         /* Consistency check: Verify that an index allocation exists. */
 280         if (!NInoIndexAllocPresent(dir_ni)) {
 281                 ntfs_error(sb, "No index allocation attribute but index entry "
 282                                 "requires one. Directory inode 0x%lx is "
 283                                 "corrupt or driver bug.", dir_ni->mft_no);
 284                 err = -EIO;
 285                 goto err_out;
 286         }
 287         /* Get the starting vcn of the index_block holding the child node. */
 288         vcn = sle64_to_cpup((u8*)ie + le16_to_cpu(ie->length) - 8);
 289         ia_mapping = VFS_I(dir_ni)->i_mapping;
 290         /*
 291          * We are done with the index root and the mft record. Release them,
 292          * otherwise we deadlock with ntfs_map_page().
 293          */
 294         put_attr_search_ctx(ctx);
 295         unmap_mft_record(dir_ni);
 296         m = NULL;
 297         ctx = NULL;
 298 descend_into_child_node:
 299         /*
 300          * Convert vcn to index into the index allocation attribute in units
 301          * of PAGE_CACHE_SIZE and map the page cache page, reading it from
 302          * disk if necessary.
 303          */
 304         page = ntfs_map_page(ia_mapping, vcn <<
 305                         dir_ni->itype.index.vcn_size_bits >> PAGE_CACHE_SHIFT);
 306         if (IS_ERR(page)) {
 307                 ntfs_error(sb, "Failed to map directory index page, error %ld.",
 308                                 -PTR_ERR(page));
 309                 err = PTR_ERR(page);
 310                 goto err_out;
 311         }
 312         kaddr = (u8*)page_address(page);
 313 fast_descend_into_child_node:
 314         /* Get to the index allocation block. */
 315         ia = (INDEX_ALLOCATION*)(kaddr + ((vcn <<
 316                         dir_ni->itype.index.vcn_size_bits) & ~PAGE_CACHE_MASK));
 317         /* Bounds checks. */
 318         if ((u8*)ia < kaddr || (u8*)ia > kaddr + PAGE_CACHE_SIZE) {
 319                 ntfs_error(sb, "Out of bounds check failed. Corrupt directory "
 320                                 "inode 0x%lx or driver bug.", dir_ni->mft_no);
 321                 err = -EIO;
 322                 goto unm_err_out;
 323         }
 324         if (sle64_to_cpu(ia->index_block_vcn) != vcn) {
 325                 ntfs_error(sb, "Actual VCN (0x%llx) of index buffer is "
 326                                 "different from expected VCN (0x%llx). "
 327                                 "Directory inode 0x%lx is corrupt or driver "
 328                                 "bug.", (unsigned long long)
 329                                 sle64_to_cpu(ia->index_block_vcn),
 330                                 (unsigned long long)vcn, dir_ni->mft_no);
 331                 err = -EIO;
 332                 goto unm_err_out;
 333         }
 334         if (le32_to_cpu(ia->index.allocated_size) + 0x18 !=
 335                         dir_ni->itype.index.block_size) {
 336                 ntfs_error(sb, "Index buffer (VCN 0x%llx) of directory inode "
 337                                 "0x%lx has a size (%u) differing from the "
 338                                 "directory specified size (%u). Directory "
 339                                 "inode is corrupt or driver bug.",
 340                                 (unsigned long long)vcn, dir_ni->mft_no,
 341                                 le32_to_cpu(ia->index.allocated_size) + 0x18,
 342                                 dir_ni->itype.index.block_size);
 343                 err = -EIO;
 344                 goto unm_err_out;
 345         }
 346         index_end = (u8*)ia + dir_ni->itype.index.block_size;
 347         if (index_end > kaddr + PAGE_CACHE_SIZE) {
 348                 ntfs_error(sb, "Index buffer (VCN 0x%llx) of directory inode "
 349                                 "0x%lx crosses page boundary. Impossible! "
 350                                 "Cannot access! This is probably a bug in the "
 351                                 "driver.", (unsigned long long)vcn,
 352                                 dir_ni->mft_no);
 353                 err = -EIO;
 354                 goto unm_err_out;
 355         }
 356         index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);
 357         if (index_end > (u8*)ia + dir_ni->itype.index.block_size) {
 358                 ntfs_error(sb, "Size of index buffer (VCN 0x%llx) of directory "
 359                                 "inode 0x%lx exceeds maximum size.",
 360                                 (unsigned long long)vcn, dir_ni->mft_no);
 361                 err = -EIO;
 362                 goto unm_err_out;
 363         }
 364         /* The first index entry. */
 365         ie = (INDEX_ENTRY*)((u8*)&ia->index +
 366                         le32_to_cpu(ia->index.entries_offset));
 367         /*
 368          * Iterate similar to above big loop but applied to index buffer, thus
 369          * loop until we exceed valid memory (corruption case) or until we
 370          * reach the last entry.
 371          */
 372         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 373                 /* Bounds check. */
 374                 if ((u8*)ie < (u8*)ia || (u8*)ie +
 375                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 376                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 377                                 index_end) {
 378                         ntfs_error(sb, "Index entry out of bounds in "
 379                                         "directory inode 0x%lx.",
 380                                         dir_ni->mft_no);
 381                         err = -EIO;
 382                         goto unm_err_out;
 383                 }
 384                 /*
 385                  * The last entry cannot contain a name. It can however contain
 386                  * a pointer to a child node in the B+tree so we just break out.
 387                  */
 388                 if (ie->flags & INDEX_ENTRY_END)
 389                         break;
 390                 /*
 391                  * We perform a case sensitive comparison and if that matches
 392                  * we are done and return the mft reference of the inode (i.e.
 393                  * the inode number together with the sequence number for
 394                  * consistency checking). We convert it to cpu format before
 395                  * returning.
 396                  */
 397                 if (ntfs_are_names_equal(uname, uname_len,
 398                                 (ntfschar*)&ie->key.file_name.file_name,
 399                                 ie->key.file_name.file_name_length,
 400                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len)) {
 401 found_it2:
 402                         /*
 403                          * We have a perfect match, so we don't need to care
 404                          * about having matched imperfectly before, so we can
 405                          * free name and set *res to NULL.
 406                          * However, if the perfect match is a short file name,
 407                          * we need to signal this through *res, so that
 408                          * ntfs_lookup() can fix dcache aliasing issues.
 409                          * As an optimization we just reuse an existing
 410                          * allocation of *res.
 411                          */
 412                         if (ie->key.file_name.file_name_type == FILE_NAME_DOS) {
 413                                 if (!name) {
 414                                         name = kmalloc(sizeof(ntfs_name),
 415                                                         GFP_NOFS);
 416                                         if (!name) {
 417                                                 err = -ENOMEM;
 418                                                 goto unm_err_out;
 419                                         }
 420                                 }
 421                                 name->mref = le64_to_cpu(
 422                                                 ie->data.dir.indexed_file);
 423                                 name->type = FILE_NAME_DOS;
 424                                 name->len = 0;
 425                                 *res = name;
 426                         } else {
 427                                 if (name)
 428                                         kfree(name);
 429                                 *res = NULL;
 430                         }
 431                         mref = le64_to_cpu(ie->data.dir.indexed_file);
 432                         ntfs_unmap_page(page);
 433                         return mref;
 434                 }
 435                 /*
 436                  * For a case insensitive mount, we also perform a case
 437                  * insensitive comparison (provided the file name is not in the
 438                  * POSIX namespace). If the comparison matches, and the name is
 439                  * in the WIN32 namespace, we cache the filename in *res so
 440                  * that the caller, ntfs_lookup(), can work on it. If the
 441                  * comparison matches, and the name is in the DOS namespace, we
 442                  * only cache the mft reference and the file name type (we set
 443                  * the name length to zero for simplicity).
 444                  */
 445                 if (!NVolCaseSensitive(vol) &&
 446                                 ie->key.file_name.file_name_type &&
 447                                 ntfs_are_names_equal(uname, uname_len,
 448                                 (ntfschar*)&ie->key.file_name.file_name,
 449                                 ie->key.file_name.file_name_length,
 450                                 IGNORE_CASE, vol->upcase, vol->upcase_len)) {
 451                         int name_size = sizeof(ntfs_name);
 452                         u8 type = ie->key.file_name.file_name_type;
 453                         u8 len = ie->key.file_name.file_name_length;
 454
 455                         /* Only one case insensitive matching name allowed. */
 456                         if (name) {
 457                                 ntfs_error(sb, "Found already allocated name "
 458                                                 "in phase 2. Please run chkdsk "
 459                                                 "and if that doesn't find any "
 460                                                 "errors please report you saw "
 461                                                 "this message to "
 462                                                 "linux-ntfs-dev@lists."
 463                                                 "sourceforge.net.");
 464                                 ntfs_unmap_page(page);
 465                                 goto dir_err_out;
 466                         }
 467
 468                         if (type != FILE_NAME_DOS)
 469                                 name_size += len * sizeof(ntfschar);
 470                         name = kmalloc(name_size, GFP_NOFS);
 471                         if (!name) {
 472                                 err = -ENOMEM;
 473                                 goto unm_err_out;
 474                         }
 475                         name->mref = le64_to_cpu(ie->data.dir.indexed_file);
 476                         name->type = type;
 477                         if (type != FILE_NAME_DOS) {
 478                                 name->len = len;
 479                                 memcpy(name->name, ie->key.file_name.file_name,
 480                                                 len * sizeof(ntfschar));
 481                         } else
 482                                 name->len = 0;
 483                         *res = name;
 484                 }
 485                 /*
 486                  * Not a perfect match, need to do full blown collation so we
 487                  * know which way in the B+tree we have to go.
 488                  */
 489                 rc = ntfs_collate_names(uname, uname_len,
 490                                 (ntfschar*)&ie->key.file_name.file_name,
 491                                 ie->key.file_name.file_name_length, 1,
 492                                 IGNORE_CASE, vol->upcase, vol->upcase_len);
 493                 /*
 494                  * If uname collates before the name of the current entry, there
 495                  * is definitely no such name in this index but we might need to
 496                  * descend into the B+tree so we just break out of the loop.
 497                  */
 498                 if (rc == -1)
 499                         break;
 500                 /* The names are not equal, continue the search. */
 501                 if (rc)
 502                         continue;
 503                 /*
 504                  * Names match with case insensitive comparison, now try the
 505                  * case sensitive comparison, which is required for proper
 506                  * collation.
 507                  */
 508                 rc = ntfs_collate_names(uname, uname_len,
 509                                 (ntfschar*)&ie->key.file_name.file_name,
 510                                 ie->key.file_name.file_name_length, 1,
 511                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len);
 512                 if (rc == -1)
 513                         break;
 514                 if (rc)
 515                         continue;
 516                 /*
 517                  * Perfect match, this will never happen as the
 518                  * ntfs_are_names_equal() call will have gotten a match but we
 519                  * still treat it correctly.
 520                  */
 521                 goto found_it2;
 522         }
 523         /*
 524          * We have finished with this index buffer without success. Check for
 525          * the presence of a child node.
 526          */
 527         if (ie->flags & INDEX_ENTRY_NODE) {
 528                 if ((ia->index.flags & NODE_MASK) == LEAF_NODE) {
 529                         ntfs_error(sb, "Index entry with child node found in "
 530                                         "a leaf node in directory inode 0x%lx.",
 531                                         dir_ni->mft_no);
 532                         err = -EIO;
 533                         goto unm_err_out;
 534                 }
 535                 /* Child node present, descend into it. */
 536                 old_vcn = vcn;
 537                 vcn = sle64_to_cpup((u8*)ie + le16_to_cpu(ie->length) - 8);
 538                 if (vcn >= 0) {
 539                         /* If vcn is in the same page cache page as old_vcn we
 540                          * recycle the mapped page. */
 541                         if (old_vcn << vol->cluster_size_bits >>
 542                                         PAGE_CACHE_SHIFT == vcn <<
 543                                         vol->cluster_size_bits >>
 544                                         PAGE_CACHE_SHIFT)
 545                                 goto fast_descend_into_child_node;
 546                         ntfs_unmap_page(page);
 547                         goto descend_into_child_node;
 548                 }
 549                 ntfs_error(sb, "Negative child node vcn in directory inode "
 550                                 "0x%lx.", dir_ni->mft_no);
 551                 err = -EIO;
 552                 goto unm_err_out;
 553         }
 554         /*
 555          * No child node present, return -ENOENT, unless we have got a matching
 556          * name cached in name in which case return the mft reference
 557          * associated with it.
 558          */
 559         if (name) {
 560                 ntfs_unmap_page(page);
 561                 return name->mref;
 562         }
 563         ntfs_debug("Entry not found.");
 564         err = -ENOENT;
 565 unm_err_out:
 566         ntfs_unmap_page(page);
 567 err_out:
 568         if (ctx)
 569                 put_attr_search_ctx(ctx);
 570         if (m)
 571                 unmap_mft_record(dir_ni);
 572         if (name) {
 573                 kfree(name);
 574                 *res = NULL;
 575         }
 576         return ERR_MREF(err);
 577 dir_err_out:
 578         ntfs_error(sb, "Corrupt directory. Aborting lookup.");
 579         err = -EIO;
 580         goto err_out;
 581 }
 582
 583 #if 0
 584
 585 // TODO: (AIA)
 586 // The algorithm embedded in this code will be required for the time when we
 587 // want to support adding of entries to directories, where we require correct
 588 // collation of file names in order not to cause corruption of the file system.
 589
 590 /**
 591  * ntfs_lookup_inode_by_name - find an inode in a directory given its name
 592  * @dir_ni:     ntfs inode of the directory in which to search for the name
 593  * @uname:      Unicode name for which to search in the directory
 594  * @uname_len:  length of the name @uname in Unicode characters
 595  *
 596  * Look for an inode with name @uname in the directory with inode @dir_ni.
 597  * ntfs_lookup_inode_by_name() walks the contents of the directory looking for
 598  * the Unicode name. If the name is found in the directory, the corresponding
 599  * inode number (>= 0) is returned as a mft reference in cpu format, i.e. it
 600  * is a 64-bit number containing the sequence number.
 601  *
 602  * On error, a negative value is returned corresponding to the error code. In
 603  * particular if the inode is not found -ENOENT is returned. Note that you
 604  * can't just check the return value for being negative, you have to check the
 605  * inode number for being negative which you can extract using MREC(return
 606  * value).
 607  *
 608  * Note, @uname_len does not include the (optional) terminating NULL character.
 609  */
 610 u64 ntfs_lookup_inode_by_name(ntfs_inode *dir_ni, const ntfschar *uname,
 611                 const int uname_len)
 612 {
 613         ntfs_volume *vol = dir_ni->vol;
 614         struct super_block *sb = vol->sb;
 615         MFT_RECORD *m;
 616         INDEX_ROOT *ir;
 617         INDEX_ENTRY *ie;
 618         INDEX_ALLOCATION *ia;
 619         u8 *index_end;
 620         u64 mref;
 621         attr_search_context *ctx;
 622         int err, rc;
 623         IGNORE_CASE_BOOL ic;
 624         VCN vcn, old_vcn;
 625         struct address_space *ia_mapping;
 626         struct page *page;
 627         u8 *kaddr;
 628
 629         /* Get hold of the mft record for the directory. */
 630         m = map_mft_record(dir_ni);
 631         if (IS_ERR(m)) {
 632                 ntfs_error(sb, "map_mft_record() failed with error code %ld.",
 633                                 -PTR_ERR(m));
 634                 return ERR_MREF(PTR_ERR(m));
 635         }
 636         ctx = get_attr_search_ctx(dir_ni, m);
 637         if (!ctx) {
 638                 err = -ENOMEM;
 639                 goto err_out;
 640         }
 641         /* Find the index root attribute in the mft record. */
 642         if (!lookup_attr(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL, 0,
 643                         ctx)) {
 644                 ntfs_error(sb, "Index root attribute missing in directory "
 645                                 "inode 0x%lx.", dir_ni->mft_no);
 646                 err = -EIO;
 647                 goto err_out;
 648         }
 649         /* Get to the index root value (it's been verified in read_inode). */
 650         ir = (INDEX_ROOT*)((u8*)ctx->attr +
 651                         le16_to_cpu(ctx->attr->data.resident.value_offset));
 652         index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length);
 653         /* The first index entry. */
 654         ie = (INDEX_ENTRY*)((u8*)&ir->index +
 655                         le32_to_cpu(ir->index.entries_offset));
 656         /*
 657          * Loop until we exceed valid memory (corruption case) or until we
 658          * reach the last entry.
 659          */
 660         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 661                 /* Bounds checks. */
 662                 if ((u8*)ie < (u8*)ctx->mrec || (u8*)ie +
 663                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 664                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 665                                 index_end)
 666                         goto dir_err_out;
 667                 /*
 668                  * The last entry cannot contain a name. It can however contain
 669                  * a pointer to a child node in the B+tree so we just break out.
 670                  */
 671                 if (ie->flags & INDEX_ENTRY_END)
 672                         break;
 673                 /*
 674                  * If the current entry has a name type of POSIX, the name is
 675                  * case sensitive and not otherwise. This has the effect of us
 676                  * not being able to access any POSIX file names which collate
 677                  * after the non-POSIX one when they only differ in case, but
 678                  * anyone doing screwy stuff like that deserves to burn in
 679                  * hell... Doing that kind of stuff on NT4 actually causes
 680                  * corruption on the partition even when using SP6a and Linux
 681                  * is not involved at all.
 682                  */
 683                 ic = ie->key.file_name.file_name_type ? IGNORE_CASE :
 684                                 CASE_SENSITIVE;
 685                 /*
 686                  * If the names match perfectly, we are done and return the
 687                  * mft reference of the inode (i.e. the inode number together
 688                  * with the sequence number for consistency checking. We
 689                  * convert it to cpu format before returning.
 690                  */
 691                 if (ntfs_are_names_equal(uname, uname_len,
 692                                 (ntfschar*)&ie->key.file_name.file_name,
 693                                 ie->key.file_name.file_name_length, ic,
 694                                 vol->upcase, vol->upcase_len)) {
 695 found_it:
 696                         mref = le64_to_cpu(ie->data.dir.indexed_file);
 697                         put_attr_search_ctx(ctx);
 698                         unmap_mft_record(dir_ni);
 699                         return mref;
 700                 }
 701                 /*
 702                  * Not a perfect match, need to do full blown collation so we
 703                  * know which way in the B+tree we have to go.
 704                  */
 705                 rc = ntfs_collate_names(uname, uname_len,
 706                                 (ntfschar*)&ie->key.file_name.file_name,
 707                                 ie->key.file_name.file_name_length, 1,
 708                                 IGNORE_CASE, vol->upcase, vol->upcase_len);
 709                 /*
 710                  * If uname collates before the name of the current entry, there
 711                  * is definitely no such name in this index but we might need to
 712                  * descend into the B+tree so we just break out of the loop.
 713                  */
 714                 if (rc == -1)
 715                         break;
 716                 /* The names are not equal, continue the search. */
 717                 if (rc)
 718                         continue;
 719                 /*
 720                  * Names match with case insensitive comparison, now try the
 721                  * case sensitive comparison, which is required for proper
 722                  * collation.
 723                  */
 724                 rc = ntfs_collate_names(uname, uname_len,
 725                                 (ntfschar*)&ie->key.file_name.file_name,
 726                                 ie->key.file_name.file_name_length, 1,
 727                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len);
 728                 if (rc == -1)
 729                         break;
 730                 if (rc)
 731                         continue;
 732                 /*
 733                  * Perfect match, this will never happen as the
 734                  * ntfs_are_names_equal() call will have gotten a match but we
 735                  * still treat it correctly.
 736                  */
 737                 goto found_it;
 738         }
 739         /*
 740          * We have finished with this index without success. Check for the
 741          * presence of a child node.
 742          */
 743         if (!(ie->flags & INDEX_ENTRY_NODE)) {
 744                 /* No child node, return -ENOENT. */
 745                 err = -ENOENT;
 746                 goto err_out;
 747         } /* Child node present, descend into it. */
 748         /* Consistency check: Verify that an index allocation exists. */
 749         if (!NInoIndexAllocPresent(dir_ni)) {
 750                 ntfs_error(sb, "No index allocation attribute but index entry "
 751                                 "requires one. Directory inode 0x%lx is "
 752                                 "corrupt or driver bug.", dir_ni->mft_no);
 753                 err = -EIO;
 754                 goto err_out;
 755         }
 756         /* Get the starting vcn of the index_block holding the child node. */
 757         vcn = sle64_to_cpup((u8*)ie + le16_to_cpu(ie->length) - 8);
 758         ia_mapping = VFS_I(dir_ni)->i_mapping;
 759         /*
 760          * We are done with the index root and the mft record. Release them,
 761          * otherwise we deadlock with ntfs_map_page().
 762          */
 763         put_attr_search_ctx(ctx);
 764         unmap_mft_record(dir_ni);
 765         m = NULL;
 766         ctx = NULL;
 767 descend_into_child_node:
 768         /*
 769          * Convert vcn to index into the index allocation attribute in units
 770          * of PAGE_CACHE_SIZE and map the page cache page, reading it from
 771          * disk if necessary.
 772          */
 773         page = ntfs_map_page(ia_mapping, vcn <<
 774                         dir_ni->itype.index.vcn_size_bits >> PAGE_CACHE_SHIFT);
 775         if (IS_ERR(page)) {
 776                 ntfs_error(sb, "Failed to map directory index page, error %ld.",
 777                                 -PTR_ERR(page));
 778                 err = PTR_ERR(page);
 779                 goto err_out;
 780         }
 781         kaddr = (u8*)page_address(page);
 782 fast_descend_into_child_node:
 783         /* Get to the index allocation block. */
 784         ia = (INDEX_ALLOCATION*)(kaddr + ((vcn <<
 785                         dir_ni->itype.index.vcn_size_bits) & ~PAGE_CACHE_MASK));
 786         /* Bounds checks. */
 787         if ((u8*)ia < kaddr || (u8*)ia > kaddr + PAGE_CACHE_SIZE) {
 788                 ntfs_error(sb, "Out of bounds check failed. Corrupt directory "
 789                                 "inode 0x%lx or driver bug.", dir_ni->mft_no);
 790                 err = -EIO;
 791                 goto unm_err_out;
 792         }
 793         if (sle64_to_cpu(ia->index_block_vcn) != vcn) {
 794                 ntfs_error(sb, "Actual VCN (0x%llx) of index buffer is "
 795                                 "different from expected VCN (0x%llx). "
 796                                 "Directory inode 0x%lx is corrupt or driver "
 797                                 "bug.", (unsigned long long)
 798                                 sle64_to_cpu(ia->index_block_vcn),
 799                                 (unsigned long long)vcn, dir_ni->mft_no);
 800                 err = -EIO;
 801                 goto unm_err_out;
 802         }
 803         if (le32_to_cpu(ia->index.allocated_size) + 0x18 !=
 804                         dir_ni->itype.index.block_size) {
 805                 ntfs_error(sb, "Index buffer (VCN 0x%llx) of directory inode "
 806                                 "0x%lx has a size (%u) differing from the "
 807                                 "directory specified size (%u). Directory "
 808                                 "inode is corrupt or driver bug.",
 809                                 (unsigned long long)vcn, dir_ni->mft_no,
 810                                 le32_to_cpu(ia->index.allocated_size) + 0x18,
 811                                 dir_ni->itype.index.block_size);
 812                 err = -EIO;
 813                 goto unm_err_out;
 814         }
 815         index_end = (u8*)ia + dir_ni->itype.index.block_size;
 816         if (index_end > kaddr + PAGE_CACHE_SIZE) {
 817                 ntfs_error(sb, "Index buffer (VCN 0x%llx) of directory inode "
 818                                 "0x%lx crosses page boundary. Impossible! "
 819                                 "Cannot access! This is probably a bug in the "
 820                                 "driver.", (unsigned long long)vcn,
 821                                 dir_ni->mft_no);
 822                 err = -EIO;
 823                 goto unm_err_out;
 824         }
 825         index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);
 826         if (index_end > (u8*)ia + dir_ni->itype.index.block_size) {
 827                 ntfs_error(sb, "Size of index buffer (VCN 0x%llx) of directory "
 828                                 "inode 0x%lx exceeds maximum size.",
 829                                 (unsigned long long)vcn, dir_ni->mft_no);
 830                 err = -EIO;
 831                 goto unm_err_out;
 832         }
 833         /* The first index entry. */
 834         ie = (INDEX_ENTRY*)((u8*)&ia->index +
 835                         le32_to_cpu(ia->index.entries_offset));
 836         /*
 837          * Iterate similar to above big loop but applied to index buffer, thus
 838          * loop until we exceed valid memory (corruption case) or until we
 839          * reach the last entry.
 840          */
 841         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
 842                 /* Bounds check. */
 843                 if ((u8*)ie < (u8*)ia || (u8*)ie +
 844                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
 845                                 (u8*)ie + le16_to_cpu(ie->key_length) >
 846                                 index_end) {
 847                         ntfs_error(sb, "Index entry out of bounds in "
 848                                         "directory inode 0x%lx.",
 849                                         dir_ni->mft_no);
 850                         err = -EIO;
 851                         goto unm_err_out;
 852                 }
 853                 /*
 854                  * The last entry cannot contain a name. It can however contain
 855                  * a pointer to a child node in the B+tree so we just break out.
 856                  */
 857                 if (ie->flags & INDEX_ENTRY_END)
 858                         break;
 859                 /*
 860                  * If the current entry has a name type of POSIX, the name is
 861                  * case sensitive and not otherwise. This has the effect of us
 862                  * not being able to access any POSIX file names which collate
 863                  * after the non-POSIX one when they only differ in case, but
 864                  * anyone doing screwy stuff like that deserves to burn in
 865                  * hell... Doing that kind of stuff on NT4 actually causes
 866                  * corruption on the partition even when using SP6a and Linux
 867                  * is not involved at all.
 868                  */
 869                 ic = ie->key.file_name.file_name_type ? IGNORE_CASE :
 870                                 CASE_SENSITIVE;
 871                 /*
 872                  * If the names match perfectly, we are done and return the
 873                  * mft reference of the inode (i.e. the inode number together
 874                  * with the sequence number for consistency checking. We
 875                  * convert it to cpu format before returning.
 876                  */
 877                 if (ntfs_are_names_equal(uname, uname_len,
 878                                 (ntfschar*)&ie->key.file_name.file_name,
 879                                 ie->key.file_name.file_name_length, ic,
 880                                 vol->upcase, vol->upcase_len)) {
 881 found_it2:
 882                         mref = le64_to_cpu(ie->data.dir.indexed_file);
 883                         ntfs_unmap_page(page);
 884                         return mref;
 885                 }
 886                 /*
 887                  * Not a perfect match, need to do full blown collation so we
 888                  * know which way in the B+tree we have to go.
 889                  */
 890                 rc = ntfs_collate_names(uname, uname_len,
 891                                 (ntfschar*)&ie->key.file_name.file_name,
 892                                 ie->key.file_name.file_name_length, 1,
 893                                 IGNORE_CASE, vol->upcase, vol->upcase_len);
 894                 /*
 895                  * If uname collates before the name of the current entry, there
 896                  * is definitely no such name in this index but we might need to
 897                  * descend into the B+tree so we just break out of the loop.
 898                  */
 899                 if (rc == -1)
 900                         break;
 901                 /* The names are not equal, continue the search. */
 902                 if (rc)
 903                         continue;
 904                 /*
 905                  * Names match with case insensitive comparison, now try the
 906                  * case sensitive comparison, which is required for proper
 907                  * collation.
 908                  */
 909                 rc = ntfs_collate_names(uname, uname_len,
 910                                 (ntfschar*)&ie->key.file_name.file_name,
 911                                 ie->key.file_name.file_name_length, 1,
 912                                 CASE_SENSITIVE, vol->upcase, vol->upcase_len);
 913                 if (rc == -1)
 914                         break;
 915                 if (rc)
 916                         continue;
 917                 /*
 918                  * Perfect match, this will never happen as the
 919                  * ntfs_are_names_equal() call will have gotten a match but we
 920                  * still treat it correctly.
 921                  */
 922                 goto found_it2;
 923         }
 924         /*
 925          * We have finished with this index buffer without success. Check for
 926          * the presence of a child node.
 927          */
 928         if (ie->flags & INDEX_ENTRY_NODE) {
 929                 if ((ia->index.flags & NODE_MASK) == LEAF_NODE) {
 930                         ntfs_error(sb, "Index entry with child node found in "
 931                                         "a leaf node in directory inode 0x%lx.",
 932                                         dir_ni->mft_no);
 933                         err = -EIO;
 934                         goto unm_err_out;
 935                 }
 936                 /* Child node present, descend into it. */
 937                 old_vcn = vcn;
 938                 vcn = sle64_to_cpup((u8*)ie + le16_to_cpu(ie->length) - 8);
 939                 if (vcn >= 0) {
 940                         /* If vcn is in the same page cache page as old_vcn we
 941                          * recycle the mapped page. */
 942                         if (old_vcn << vol->cluster_size_bits >>
 943                                         PAGE_CACHE_SHIFT == vcn <<
 944                                         vol->cluster_size_bits >>
 945                                         PAGE_CACHE_SHIFT)
 946                                 goto fast_descend_into_child_node;
 947                         ntfs_unmap_page(page);
 948                         goto descend_into_child_node;
 949                 }
 950                 ntfs_error(sb, "Negative child node vcn in directory inode "
 951                                 "0x%lx.", dir_ni->mft_no);
 952                 err = -EIO;
 953                 goto unm_err_out;
 954         }
 955         /* No child node, return -ENOENT. */
 956         ntfs_debug("Entry not found.");
 957         err = -ENOENT;
 958 unm_err_out:
 959         ntfs_unmap_page(page);
 960 err_out:
 961         if (ctx)
 962                 put_attr_search_ctx(ctx);
 963         if (m)
 964                 unmap_mft_record(dir_ni);
 965         return ERR_MREF(err);
 966 dir_err_out:
 967         ntfs_error(sb, "Corrupt directory. Aborting lookup.");
 968         err = -EIO;
 969         goto err_out;
 970 }
 971
 972 #endif
 973
 974 typedef union {
 975         INDEX_ROOT *ir;
 976         INDEX_ALLOCATION *ia;
 977 } index_union __attribute__ ((__transparent_union__));
 978
 979 typedef enum {
 980         INDEX_TYPE_ROOT,        /* index root */
 981         INDEX_TYPE_ALLOCATION,  /* index allocation */
 982 } INDEX_TYPE;
 983
 984 /**
 985  * ntfs_filldir - ntfs specific filldir method
 986  * @vol:        current ntfs volume
 987  * @fpos:       position in the directory
 988  * @ndir:       ntfs inode of current directory
 989  * @index_type: specifies whether @iu is an index root or an index allocation
 990  * @iu:         index root or index allocation attribute to which @ie belongs
 991  * @ie:         current index entry
 992  * @name:       buffer to use for the converted name
 993  * @dirent:     vfs filldir callback context
 994  * @filldir:    vfs filldir callback
 995  *
 996  * Convert the Unicode @name to the loaded NLS and pass it to the @filldir
 997  * callback.
 998  */
 999 static inline int ntfs_filldir(ntfs_volume *vol, loff_t *fpos,
1000                 ntfs_inode *ndir, const INDEX_TYPE index_type,
1001                 index_union iu, INDEX_ENTRY *ie, u8 *name,
1002                 void *dirent, filldir_t filldir)
1003 {
1004         int name_len;
1005         unsigned dt_type;
1006         FILE_NAME_TYPE_FLAGS name_type;
1007
1008         /* Advance the position even if going to skip the entry. */
1009         if (index_type == INDEX_TYPE_ALLOCATION)
1010                 *fpos = (u8*)ie - (u8*)iu.ia +
1011                                 (sle64_to_cpu(iu.ia->index_block_vcn) <<
1012                                 ndir->itype.index.vcn_size_bits) +
1013                                 vol->mft_record_size;
1014         else /* if (index_type == INDEX_TYPE_ROOT) */
1015                 *fpos = (u8*)ie - (u8*)iu.ir;
1016         name_type = ie->key.file_name.file_name_type;
1017         if (name_type == FILE_NAME_DOS) {
1018                 ntfs_debug("Skipping DOS name space entry.");
1019                 return 0;
1020         }
1021         if (MREF_LE(ie->data.dir.indexed_file) == FILE_root) {
1022                 ntfs_debug("Skipping root directory self reference entry.");
1023                 return 0;
1024         }
1025         if (MREF_LE(ie->data.dir.indexed_file) < FILE_first_user &&
1026                         !NVolShowSystemFiles(vol)) {
1027                 ntfs_debug("Skipping system file.");
1028                 return 0;
1029         }
1030         name_len = ntfs_ucstonls(vol, (ntfschar*)&ie->key.file_name.file_name,
1031                         ie->key.file_name.file_name_length, &name,
1032                         NTFS_MAX_NAME_LEN * NLS_MAX_CHARSET_SIZE + 1);
1033         if (name_len <= 0) {
1034                 ntfs_debug("Skipping unrepresentable file.");
1035                 return 0;
1036         }
1037         if (ie->key.file_name.file_attributes &
1038                         FILE_ATTR_DUP_FILE_NAME_INDEX_PRESENT)
1039                 dt_type = DT_DIR;
1040         else
1041                 dt_type = DT_REG;
1042         ntfs_debug("Calling filldir for %s with len %i, fpos 0x%llx, inode "
1043                         "0x%lx, DT_%s.", name, name_len, *fpos,
1044                         MREF_LE(ie->data.dir.indexed_file),
1045                         dt_type == DT_DIR ? "DIR" : "REG");
1046         return filldir(dirent, name, name_len, *fpos,
1047                         MREF_LE(ie->data.dir.indexed_file), dt_type);
1048 }
1049
1050 /*
1051  * VFS calls readdir without BKL but with i_sem held. This protects the VFS
1052  * parts (e.g. ->f_pos and ->i_size, and it also protects against directory
1053  * modifications).
1054  *
1055  * We use the same basic approach as the old NTFS driver, i.e. we parse the
1056  * index root entries and then the index allocation entries that are marked
1057  * as in use in the index bitmap.
1058  * While this will return the names in random order this doesn't matter for
1059  * readdir but OTOH results in a faster readdir.
1060  */
1061 static int ntfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
1062 {
1063         s64 ia_pos, ia_start, prev_ia_pos, bmp_pos;
1064         loff_t fpos;
1065         struct inode *bmp_vi, *vdir = filp->f_dentry->d_inode;
1066         struct super_block *sb = vdir->i_sb;
1067         ntfs_inode *ndir = NTFS_I(vdir);
1068         ntfs_volume *vol = NTFS_SB(sb);
1069         MFT_RECORD *m;
1070         INDEX_ROOT *ir = NULL;
1071         INDEX_ENTRY *ie;
1072         INDEX_ALLOCATION *ia;
1073         u8 *name = NULL;
1074         int rc, err, ir_pos, cur_bmp_pos;
1075         struct address_space *ia_mapping, *bmp_mapping;
1076         struct page *bmp_page = NULL, *ia_page = NULL;
1077         u8 *kaddr, *bmp, *index_end;
1078         attr_search_context *ctx;
1079
1080         fpos = filp->f_pos;
1081         ntfs_debug("Entering for inode 0x%lx, fpos 0x%llx.",
1082                         vdir->i_ino, fpos);
1083         rc = err = 0;
1084         /* Are we at end of dir yet? */
1085         if (fpos >= vdir->i_size + vol->mft_record_size)
1086                 goto done;
1087         /* Emulate . and .. for all directories. */
1088         if (!fpos) {
1089                 ntfs_debug("Calling filldir for . with len 1, fpos 0x0, "
1090                                 "inode 0x%lx, DT_DIR.", vdir->i_ino);
1091                 rc = filldir(dirent, ".", 1, fpos, vdir->i_ino, DT_DIR);
1092                 if (rc)
1093                         goto done;
1094                 fpos++;
1095         }
1096         if (fpos == 1) {
1097                 ntfs_debug("Calling filldir for .. with len 2, fpos 0x1, "
1098                                 "inode 0x%lx, DT_DIR.",
1099                                 parent_ino(filp->f_dentry));
1100                 rc = filldir(dirent, "..", 2, fpos,
1101                                 parent_ino(filp->f_dentry), DT_DIR);
1102                 if (rc)
1103                         goto done;
1104                 fpos++;
1105         }
1106         m = NULL;
1107         ctx = NULL;
1108         /*
1109          * Allocate a buffer to store the current name being processed
1110          * converted to format determined by current NLS.
1111          */
1112         name = (u8*)kmalloc(NTFS_MAX_NAME_LEN * NLS_MAX_CHARSET_SIZE + 1,
1113                         GFP_NOFS);
1114         if (unlikely(!name)) {
1115                 err = -ENOMEM;
1116                 goto err_out;
1117         }
1118         /* Are we jumping straight into the index allocation attribute? */
1119         if (fpos >= vol->mft_record_size)
1120                 goto skip_index_root;
1121         /* Get hold of the mft record for the directory. */
1122         m = map_mft_record(ndir);
1123         if (unlikely(IS_ERR(m))) {
1124                 err = PTR_ERR(m);
1125                 m = NULL;
1126                 goto err_out;
1127         }
1128         ctx = get_attr_search_ctx(ndir, m);
1129         if (unlikely(!ctx)) {
1130                 err = -ENOMEM;
1131                 goto err_out;
1132         }
1133         /* Get the offset into the index root attribute. */
1134         ir_pos = (s64)fpos;
1135         /* Find the index root attribute in the mft record. */
1136         if (unlikely(!lookup_attr(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0,
1137                         NULL, 0, ctx))) {
1138                 ntfs_error(sb, "Index root attribute missing in directory "
1139                                 "inode 0x%lx.", vdir->i_ino);
1140                 goto err_out;
1141         }
1142         /*
1143          * Copy the index root attribute value to a buffer so that we can put
1144          * the search context and unmap the mft record before calling the
1145          * filldir() callback.  We need to do this because of NFSd which calls
1146          * ->lookup() from its filldir callback() and this causes NTFS to
1147          * deadlock as ntfs_lookup() maps the mft record of the directory and
1148          * we have got it mapped here already.  The only solution is for us to
1149          * unmap the mft record here so that a call to ntfs_lookup() is able to
1150          * map the mft record without deadlocking.
1151          */
1152         rc = le32_to_cpu(ctx->attr->data.resident.value_length);
1153         ir = (INDEX_ROOT*)kmalloc(rc, GFP_NOFS);
1154         if (unlikely(!ir)) {
1155                 err = -ENOMEM;
1156                 goto err_out;
1157         }
1158         /* Copy the index root value (it has been verified in read_inode). */
1159         memcpy(ir, (u8*)ctx->attr +
1160                         le16_to_cpu(ctx->attr->data.resident.value_offset), rc);
1161         put_attr_search_ctx(ctx);
1162         unmap_mft_record(ndir);
1163         ctx = NULL;
1164         m = NULL;
1165         index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length);
1166         /* The first index entry. */
1167         ie = (INDEX_ENTRY*)((u8*)&ir->index +
1168                         le32_to_cpu(ir->index.entries_offset));
1169         /*
1170          * Loop until we exceed valid memory (corruption case) or until we
1171          * reach the last entry or until filldir tells us it has had enough
1172          * or signals an error (both covered by the rc test).
1173          */
1174         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
1175                 ntfs_debug("In index root, offset 0x%x.", (u8*)ie - (u8*)ir);
1176                 /* Bounds checks. */
1177                 if (unlikely((u8*)ie < (u8*)ir || (u8*)ie +
1178                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
1179                                 (u8*)ie + le16_to_cpu(ie->key_length) >
1180                                 index_end))
1181                         goto err_out;
1182                 /* The last entry cannot contain a name. */
1183                 if (ie->flags & INDEX_ENTRY_END)
1184                         break;
1185                 /* Skip index root entry if continuing previous readdir. */
1186                 if (ir_pos > (u8*)ie - (u8*)ir)
1187                         continue;
1188                 /* Submit the name to the filldir callback. */
1189                 rc = ntfs_filldir(vol, &fpos, ndir, INDEX_TYPE_ROOT, ir, ie,
1190                                 name, dirent, filldir);
1191                 if (rc) {
1192                         kfree(ir);
1193                         goto abort;
1194                 }
1195         }
1196         /* We are done with the index root and can free the buffer. */
1197         kfree(ir);
1198         ir = NULL;
1199         /* If there is no index allocation attribute we are finished. */
1200         if (!NInoIndexAllocPresent(ndir))
1201                 goto EOD;
1202         /* Advance fpos to the beginning of the index allocation. */
1203         fpos = vol->mft_record_size;
1204 skip_index_root:
1205         kaddr = NULL;
1206         prev_ia_pos = -1LL;
1207         /* Get the offset into the index allocation attribute. */
1208         ia_pos = (s64)fpos - vol->mft_record_size;
1209         ia_mapping = vdir->i_mapping;
1210         bmp_vi = ndir->itype.index.bmp_ino;
1211         if (unlikely(!bmp_vi)) {
1212                 ntfs_debug("Inode 0x%lx, regetting index bitmap.", vdir->i_ino);
1213                 bmp_vi = ntfs_attr_iget(vdir, AT_BITMAP, I30, 4);
1214                 if (unlikely(IS_ERR(bmp_vi))) {
1215                         ntfs_error(sb, "Failed to get bitmap attribute.");
1216                         err = PTR_ERR(bmp_vi);
1217                         goto err_out;
1218                 }
1219                 ndir->itype.index.bmp_ino = bmp_vi;
1220         }
1221         bmp_mapping = bmp_vi->i_mapping;
1222         /* Get the starting bitmap bit position and sanity check it. */
1223         bmp_pos = ia_pos >> ndir->itype.index.block_size_bits;
1224         if (unlikely(bmp_pos >> 3 >= bmp_vi->i_size)) {
1225                 ntfs_error(sb, "Current index allocation position exceeds "
1226                                 "index bitmap size.");
1227                 goto err_out;
1228         }
1229         /* Get the starting bit position in the current bitmap page. */
1230         cur_bmp_pos = bmp_pos & ((PAGE_CACHE_SIZE * 8) - 1);
1231         bmp_pos &= ~(u64)((PAGE_CACHE_SIZE * 8) - 1);
1232 get_next_bmp_page:
1233         ntfs_debug("Reading bitmap with page index 0x%llx, bit ofs 0x%llx",
1234                         (unsigned long long)bmp_pos >> (3 + PAGE_CACHE_SHIFT),
1235                         (unsigned long long)bmp_pos &
1236                         ((PAGE_CACHE_SIZE * 8) - 1));
1237         bmp_page = ntfs_map_page(bmp_mapping,
1238                         bmp_pos >> (3 + PAGE_CACHE_SHIFT));
1239         if (unlikely(IS_ERR(bmp_page))) {
1240                 ntfs_error(sb, "Reading index bitmap failed.");
1241                 err = PTR_ERR(bmp_page);
1242                 bmp_page = NULL;
1243                 goto err_out;
1244         }
1245         bmp = (u8*)page_address(bmp_page);
1246         /* Find next index block in use. */
1247         while (!(bmp[cur_bmp_pos >> 3] & (1 << (cur_bmp_pos & 7)))) {
1248 find_next_index_buffer:
1249                 cur_bmp_pos++;
1250                 /*
1251                  * If we have reached the end of the bitmap page, get the next
1252                  * page, and put away the old one.
1253                  */
1254                 if (unlikely((cur_bmp_pos >> 3) >= PAGE_CACHE_SIZE)) {
1255                         ntfs_unmap_page(bmp_page);
1256                         bmp_pos += PAGE_CACHE_SIZE * 8;
1257                         cur_bmp_pos = 0;
1258                         goto get_next_bmp_page;
1259                 }
1260                 /* If we have reached the end of the bitmap, we are done. */
1261                 if (unlikely(((bmp_pos + cur_bmp_pos) >> 3) >= vdir->i_size))
1262                         goto unm_EOD;
1263                 ia_pos = (bmp_pos + cur_bmp_pos) <<
1264                                 ndir->itype.index.block_size_bits;
1265         }
1266         ntfs_debug("Handling index buffer 0x%llx.",
1267                         (unsigned long long)bmp_pos + cur_bmp_pos);
1268         /* If the current index buffer is in the same page we reuse the page. */
1269         if ((prev_ia_pos & PAGE_CACHE_MASK) != (ia_pos & PAGE_CACHE_MASK)) {
1270                 prev_ia_pos = ia_pos;
1271                 if (likely(ia_page != NULL))
1272                         ntfs_unmap_page(ia_page);
1273                 /*
1274                  * Map the page cache page containing the current ia_pos,
1275                  * reading it from disk if necessary.
1276                  */
1277                 ia_page = ntfs_map_page(ia_mapping, ia_pos >> PAGE_CACHE_SHIFT);
1278                 if (unlikely(IS_ERR(ia_page))) {
1279                         ntfs_error(sb, "Reading index allocation data failed.");
1280                         err = PTR_ERR(ia_page);
1281                         ia_page = NULL;
1282                         goto err_out;
1283                 }
1284                 kaddr = (u8*)page_address(ia_page);
1285         }
1286         /* Get the current index buffer. */
1287         ia = (INDEX_ALLOCATION*)(kaddr + (ia_pos & ~PAGE_CACHE_MASK &
1288                         ~(s64)(ndir->itype.index.block_size - 1)));
1289         /* Bounds checks. */
1290         if (unlikely((u8*)ia < kaddr || (u8*)ia > kaddr + PAGE_CACHE_SIZE)) {
1291                 ntfs_error(sb, "Out of bounds check failed. Corrupt directory "
1292                                 "inode 0x%lx or driver bug.", vdir->i_ino);
1293                 goto err_out;
1294         }
1295         if (unlikely(sle64_to_cpu(ia->index_block_vcn) != (ia_pos &
1296                         ~(s64)(ndir->itype.index.block_size - 1)) >>
1297                         ndir->itype.index.vcn_size_bits)) {
1298                 ntfs_error(sb, "Actual VCN (0x%llx) of index buffer is "
1299                                 "different from expected VCN (0x%llx). "
1300                                 "Directory inode 0x%lx is corrupt or driver "
1301                                 "bug. ", (unsigned long long)
1302                                 sle64_to_cpu(ia->index_block_vcn),
1303                                 (unsigned long long)ia_pos >>
1304                                 ndir->itype.index.vcn_size_bits, vdir->i_ino);
1305                 goto err_out;
1306         }
1307         if (unlikely(le32_to_cpu(ia->index.allocated_size) + 0x18 !=
1308                         ndir->itype.index.block_size)) {
1309                 ntfs_error(sb, "Index buffer (VCN 0x%llx) of directory inode "
1310                                 "0x%lx has a size (%u) differing from the "
1311                                 "directory specified size (%u). Directory "
1312                                 "inode is corrupt or driver bug.",
1313                                 (unsigned long long)ia_pos >>
1314                                 ndir->itype.index.vcn_size_bits, vdir->i_ino,
1315                                 le32_to_cpu(ia->index.allocated_size) + 0x18,
1316                                 ndir->itype.index.block_size);
1317                 goto err_out;
1318         }
1319         index_end = (u8*)ia + ndir->itype.index.block_size;
1320         if (unlikely(index_end > kaddr + PAGE_CACHE_SIZE)) {
1321                 ntfs_error(sb, "Index buffer (VCN 0x%llx) of directory inode "
1322                                 "0x%lx crosses page boundary. Impossible! "
1323                                 "Cannot access! This is probably a bug in the "
1324                                 "driver.", (unsigned long long)ia_pos >>
1325                                 ndir->itype.index.vcn_size_bits, vdir->i_ino);
1326                 goto err_out;
1327         }
1328         ia_start = ia_pos & ~(s64)(ndir->itype.index.block_size - 1);
1329         index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);
1330         if (unlikely(index_end > (u8*)ia + ndir->itype.index.block_size)) {
1331                 ntfs_error(sb, "Size of index buffer (VCN 0x%llx) of directory "
1332                                 "inode 0x%lx exceeds maximum size.",
1333                                 (unsigned long long)ia_pos >>
1334                                 ndir->itype.index.vcn_size_bits, vdir->i_ino);
1335                 goto err_out;
1336         }
1337         /* The first index entry in this index buffer. */
1338         ie = (INDEX_ENTRY*)((u8*)&ia->index +
1339                         le32_to_cpu(ia->index.entries_offset));
1340         /*
1341          * Loop until we exceed valid memory (corruption case) or until we
1342          * reach the last entry or until filldir tells us it has had enough
1343          * or signals an error (both covered by the rc test).
1344          */
1345         for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
1346                 ntfs_debug("In index allocation, offset 0x%llx.",
1347                                 (unsigned long long)ia_start + ((u8*)ie -
1348                                 (u8*)ia));
1349                 /* Bounds checks. */
1350                 if (unlikely((u8*)ie < (u8*)ia || (u8*)ie +
1351                                 sizeof(INDEX_ENTRY_HEADER) > index_end ||
1352                                 (u8*)ie + le16_to_cpu(ie->key_length) >
1353                                 index_end))
1354                         goto err_out;
1355                 /* The last entry cannot contain a name. */
1356                 if (ie->flags & INDEX_ENTRY_END)
1357                         break;
1358                 /* Skip index block entry if continuing previous readdir. */
1359                 if (ia_pos - ia_start > (u8*)ie - (u8*)ia)
1360                         continue;
1361                 /* Submit the name to the filldir callback. */
1362                 rc = ntfs_filldir(vol, &fpos, ndir, INDEX_TYPE_ALLOCATION, ia,
1363                                 ie, name, dirent, filldir);
1364                 if (rc) {
1365                         ntfs_unmap_page(ia_page);
1366                         ntfs_unmap_page(bmp_page);
1367                         goto abort;
1368                 }
1369         }
1370         goto find_next_index_buffer;
1371 unm_EOD:
1372         if (ia_page)
1373                 ntfs_unmap_page(ia_page);
1374         ntfs_unmap_page(bmp_page);
1375 EOD:
1376         /* We are finished, set fpos to EOD. */
1377         fpos = vdir->i_size + vol->mft_record_size;
1378 abort:
1379         kfree(name);
1380 done:
1381 #ifdef DEBUG
1382         if (!rc)
1383                 ntfs_debug("EOD, fpos 0x%llx, returning 0.", fpos);
1384         else
1385                 ntfs_debug("filldir returned %i, fpos 0x%llx, returning 0.",
1386                                 rc, fpos);
1387 #endif
1388         filp->f_pos = fpos;
1389         return 0;
1390 err_out:
1391         if (bmp_page)
1392                 ntfs_unmap_page(bmp_page);
1393         if (ia_page)
1394                 ntfs_unmap_page(ia_page);
1395         if (ir)
1396                 kfree(ir);
1397         if (name)
1398                 kfree(name);
1399         if (ctx)
1400                 put_attr_search_ctx(ctx);
1401         if (m)
1402                 unmap_mft_record(ndir);
1403         if (!err)
1404                 err = -EIO;
1405         ntfs_debug("Failed. Returning error code %i.", -err);
1406         filp->f_pos = fpos;
1407         return err;
1408 }
1409
1410 /**
1411  * ntfs_dir_open - called when an inode is about to be opened
1412  * @vi:         inode to be opened
1413  * @filp:       file structure describing the inode
1414  *
1415  * Limit directory size to the page cache limit on architectures where unsigned
1416  * long is 32-bits. This is the most we can do for now without overflowing the
1417  * page cache page index. Doing it this way means we don't run into problems
1418  * because of existing too large directories. It would be better to allow the
1419  * user to read the accessible part of the directory but I doubt very much
1420  * anyone is going to hit this check on a 32-bit architecture, so there is no
1421  * point in adding the extra complexity required to support this.
1422  *
1423  * On 64-bit architectures, the check is hopefully optimized away by the
1424  * compiler.
1425  */
1426 static int ntfs_dir_open(struct inode *vi, struct file *filp)
1427 {
1428         if (sizeof(unsigned long) < 8) {
1429                 if (vi->i_size > MAX_LFS_FILESIZE)
1430                         return -EFBIG;
1431         }
1432         return 0;
1433 }
1434
1435 struct file_operations ntfs_dir_ops = {
1436         .llseek         = generic_file_llseek,  /* Seek inside directory. */
1437         .read           = generic_read_dir,     /* Return -EISDIR. */
1438         .readdir        = ntfs_readdir,         /* Read directory contents. */
1439         .open           = ntfs_dir_open,        /* Open directory. */
1440 };
1441