KernelLand/Modules/Filesystems/NTFS/dir.c

   1 /*
   2  * Acess2 - NTFS Driver
   3  * By John Hodge (thePowersGang)
   4  * This file is published under the terms of the Acess licence. See the
   5  * file COPYING for details.
   6  *
   7  * dir.c - Directory Handling
   8  */
   9 #define DEBUG   1
  10 #include "common.h"
  11 //#include "index.h"
  12 #include <utf16.h>
  13
  14 // === PROTOTYPES ===
  15  int    NTFS_ReadDir(tVFS_Node *Node, int Pos, char Dest[FILENAME_MAX]);
  16 tVFS_Node       *NTFS_FindDir(tVFS_Node *Node, const char *Name, Uint Flags);
  17 Uint64  NTFS_int_IndexLookup(Uint64 Inode, const char *IndexName, const char *Str);
  18
  19 // === CODE ===
  20 const tNTFS_IndexEntry_Filename *NTFS_int_IterateIndex(const char *Buf, size_t Len, int *Count)
  21 {
  22         const tNTFS_IndexEntry_Filename *ent;
  23         for( size_t ofs = 0; ofs < Len; ofs += ent->EntrySize )
  24         {
  25                 ent = (const void*)(Buf + ofs);
  26
  27                 if( ofs + sizeof(*ent) > Len ) {
  28                         break;
  29                 }
  30                 if( ent->EntrySize < sizeof(*ent) ) {
  31                         break;
  32                 }
  33                 // End of block - move on to the next one
  34                 if( ent->IndexFlags & 0x02 ) {
  35                         LOG("end of block at ofs %x", ofs);
  36                         break;
  37                 }
  38
  39                 // A little hacky - hide all internal files
  40                 if( (ent->MFTReference & ((1ULL << 48)-1)) < 12 )
  41                         continue;
  42                 // Skip DOS filenames
  43                 if( ent->Filename.FilenameNamespace == NTFS_FilenameNamespace_DOS )
  44                         continue ;
  45
  46                 // Located
  47                 if( (*Count)-- <= 0 )
  48                         return ent;
  49         }
  50         return NULL;
  51 }
  52
  53 /**
  54  * \brief Get the name of an indexed directory entry
  55  */
  56 int NTFS_ReadDir(tVFS_Node *Node, int Pos, char Dest[FILENAME_MAX])
  57 {
  58         tNTFS_Directory *dir = (void*)Node;
  59
  60         ENTER("XNode->Inode iPos", Node->Inode, Pos);
  61
  62         ASSERT(dir->I30Root->IsResident);
  63         const tNTFS_Attrib_IndexRoot    *idxroot = dir->I30Root->ResidentData;
  64
  65         // Check resident root
  66         const tNTFS_IndexEntry_Filename *ent;
  67         ent = NTFS_int_IterateIndex(
  68                 (char*)idxroot + (0x10 + idxroot->FirstEntryOfs),
  69                 dir->I30Root->DataSize - (0x10 + idxroot->FirstEntryOfs),
  70                 &Pos);
  71         char buf[idxroot->AllocEntrySize];
  72         size_t  vcn = 0;
  73         size_t  len;
  74         while( !ent && (len = NTFS_ReadAttribData(dir->I30Allocation, vcn*sizeof(buf), sizeof(buf), buf)) )
  75         {
  76                 // Check allocation
  77                 struct sNTFS_IndexHeader *hdr = (void*)buf;
  78                 ASSERT(hdr->EntriesOffset + 0x18 < len);
  79                 // Apply update sequence
  80                 ASSERT(hdr->UpdateSequenceOfs + 2*hdr->UpdateSequenceSize <= len);
  81                 NTFS_int_ApplyUpdateSequence(buf,len, (void*)(buf+hdr->UpdateSequenceOfs), hdr->UpdateSequenceSize);
  82                 size_t  ofs = hdr->EntriesOffset + 0x18;
  83                 ent = NTFS_int_IterateIndex(buf + ofs, len - ofs, &Pos);
  84                 vcn ++;
  85         }
  86         if( !ent ) {
  87                 LEAVE_RET('i', -1);
  88         }
  89
  90         // TODO: This is not future-proof
  91         const Uint16    *name16 = ent->Filename.Filename;
  92         UTF16_ConvertToUTF8(FILENAME_MAX, Dest, ent->Filename.FilenameLength, name16);
  93         LOG("Filename '%s'", Dest);
  94         LEAVE('i', 0);
  95         return 0;
  96 }
  97
  98 typedef int (*tNTFS_BTreeSearch_CmpFcn)(const tNTFS_IndexEntry_Filename *Ent, size_t SLen, const void *Search);
  99
 100 int NTFS_BTreeSearch_CmpI30(const tNTFS_IndexEntry_Filename *Ent, size_t SLen, const void *Search)
 101 {
 102         #if 0
 103         size_t  fname_len = Ent->Filename.FilenameLength*2;
 104         size_t  cmplen = MIN(fnamelen, SLen);
 105         int ret = memcmp(Ent->Filename.Filename, Search, cmplen);
 106         if( ret != 0 )
 107                 return ret;
 108         if( cmplen < SLen )
 109                 return -1;
 110         else if( cmplen == SLen )
 111                 return 0;
 112         else
 113                 return 1;
 114         #else
 115         //LOG("Cmp '%.*ls' == '%s'", Ent->Filename.FilenameLength, Ent->Filename.Filename, Search);
 116 //      return UTF16_CompareWithUTF8(Ent->Filename.FilenameLength, Ent->Filename.Filename, Search);
 117         return UTF16_CompareWithUTF8CI(Ent->Filename.FilenameLength, Ent->Filename.Filename, Search);
 118         #endif
 119 }
 120
 121 Uint64 NTFS_BTreeSearch(size_t Length, const void *Data,
 122         tNTFS_BTreeSearch_CmpFcn Cmp, size_t SLen, const void *Search)
 123 {
 124         void    *buffer_end = (char*)Data + Length;
 125         const tNTFS_IndexEntry_Filename *ent = Data;
 126         while( !(ent->IndexFlags & 0x02) )
 127         {
 128                 if( (void*)(&ent->_rsvd + 1) > buffer_end ) {
 129                         // on-disk error
 130                         return 0;
 131                 }
 132                 // TODO: Handle collations?
 133                 int cmp = Cmp(ent, SLen, Search);
 134                 if( cmp == 0 ) {
 135                         LOG("Located at %p: 0x%016llx", ent, ent->MFTReference);
 136                         return ent->MFTReference & ((1ULL << 48)-1);
 137                 }
 138                 if( cmp > 0 )
 139                         break;
 140
 141                 ent = (void*)((char*)ent + ent->EntrySize);
 142         }
 143         if( ent->IndexFlags & 0x01 ) {
 144                 LOG("Descend to VCN %llx", *(Uint64*)((char*)ent + ent->EntrySize - 8));
 145                 return (1ULL << 63) | *(Uint64*)((char*)ent + ent->EntrySize - 8);
 146         }
 147         LOG("Not found");
 148         return 0;
 149 }
 150
 151 #define _MFTREF_IDX(ref)        ((ref) & ((1ULL<<48)-1))
 152 #define _MFTREF_SEQ(ref)        ((ref) >> 48)
 153
 154 void NTFS_int_DumpIndex(tNTFS_Attrib *Allocation, Uint AttribID)
 155 {
 156         ENTER("pAllocation xAttribID", Allocation, AttribID);
 157         if(!Allocation) {
 158                 LEAVE('-');
 159                 return ;
 160         }
 161         Uint32  vcn = 0;
 162         size_t  block_size = MAX(2048, Allocation->Disk->ClusterSize);
 163         char    buf[block_size];
 164         size_t  len;
 165         while( (len = NTFS_ReadAttribData(Allocation, vcn*block_size, block_size, buf)) )
 166         {
 167                 struct sNTFS_IndexHeader        *hdr = (void*)buf;
 168                 // Apply update sequence
 169                 ASSERT(hdr->UpdateSequenceOfs + 2*hdr->UpdateSequenceSize <= len);
 170                 NTFS_int_ApplyUpdateSequence(buf,len, (void*)(buf+hdr->UpdateSequenceOfs), hdr->UpdateSequenceSize);
 171
 172                 LOG("VCN %x: Ofs=%x, Size=%x",
 173                         vcn, hdr->EntriesOffset, hdr->EntriesSize);
 174                 if( hdr->ThisVCN != vcn ) {
 175                         Log_Notice("NTFS", "Data error: Index header VCN mismatch (%x!=exp %x)", hdr->ThisVCN, vcn);
 176                 }
 177                 size_t  ofs = hdr->EntriesOffset + 0x18;
 178                 while( ofs < hdr->EntriesSize + (hdr->EntriesOffset + 0x18) )
 179                 {
 180                         struct sNTFS_IndexEntry *ent = (void*)(buf + ofs);
 181                         if( ofs + sizeof(*ent) > len )
 182                                 break;
 183                         LOG("%03x: L=%02x,M=%02x,F=%02x, Ref=%x/%llx", ofs,
 184                                 ent->EntrySize, ent->MessageLen, ent->IndexFlags,
 185                                 _MFTREF_SEQ(ent->MFTReference), _MFTREF_IDX(ent->MFTReference));
 186
 187                         if( ent->EntrySize < sizeof(*ent) ) {
 188                                 Log_Notice("NTFS", "Data error: Index entry size too small");
 189                                 break ;
 190                         }
 191                         if( ent->MessageLen + sizeof(*ent) > ent->EntrySize ) {
 192                                 Log_Notice("NTFS", "Data error: Index entry message size > entry size");
 193                         }
 194
 195                         if( ent->IndexFlags & NTFS_IndexFlag_HasSubNode )
 196                         {
 197                                 if( ent->EntrySize < sizeof(*ent) + 8 ) {
 198                                         Log_Notice("NTFS", "Data error: Index entry size too small (SubVCN)");
 199                                 }
 200                                 LOG("- SubVCN=%llx", *(Uint64*)((char*)ent + ent->EntrySize - 8));
 201                         }
 202                         if( ent->IndexFlags & NTFS_IndexFlag_IsLast )
 203                                 break;
 204
 205                         switch(AttribID)
 206                         {
 207                         case 0x30: {
 208                                 struct sNTFS_Attrib_Filename    *fname = (void*)(buf + ofs + sizeof(*ent));
 209                                 LOG("- Filename: %i %.*ls",
 210                                         fname->FilenameNamespace,
 211                                         fname->FilenameLength, fname->Filename);
 212                                 break; }
 213                         }
 214
 215                         ofs += ent->EntrySize;
 216                 }
 217                 vcn ++;
 218         }
 219         LEAVE('-');
 220 }
 221
 222 tVFS_Node *NTFS_int_CreateNode(tNTFS_Disk *Disk, Uint64 MFTEntry)
 223 {
 224         tNTFS_FILE_Header       *ent = NTFS_GetMFT(Disk, MFTEntry);
 225         if( !ent || !(ent->Flags & 0x01) )
 226                 return NULL;
 227
 228         tVFS_Node       *ret;
 229         size_t  size;
 230         union {
 231                 tNTFS_Directory tpl_dir;
 232                 tNTFS_File      tpl_file;
 233         } types;
 234         memset(&types, 0, sizeof(tVFS_Node));
 235         if( ent->Flags & 0x02 )
 236         {
 237                 // Directory
 238                 size = sizeof(types.tpl_dir);
 239                 ret = &types.tpl_dir.Node;
 240                 ret->Type = &gNTFS_DirType;
 241                 ret->Flags = VFS_FFLAG_DIRECTORY;
 242
 243                 types.tpl_dir.I30Root = NTFS_GetAttrib(Disk, MFTEntry, NTFS_FileAttrib_IndexRoot, "$I30", 0);
 244                 types.tpl_dir.I30Allocation = NTFS_GetAttrib(Disk, MFTEntry,
 245                         NTFS_FileAttrib_IndexAllocation, "$I30", 0);
 246
 247                 ASSERT(types.tpl_dir.I30Root->IsResident);
 248                 #if 0
 249                 Debug_HexDump("NTFS CreateNode Root",
 250                         types.tpl_dir.I30Root->ResidentData,
 251                         types.tpl_dir.I30Root->DataSize);
 252                 if( types.tpl_dir.I30Allocation ) {
 253                         NTFS_int_DumpIndex(types.tpl_dir.I30Allocation, 0x30);
 254                 }
 255                 #endif
 256
 257                 #if 0
 258                 if( MFTEntry == 0x1C )
 259                 {
 260                         char tmpbuf[Disk->ClusterSize];
 261                         NTFS_ReadAttribData(types.tpl_dir.I30Allocation, 0, sizeof(tmpbuf), tmpbuf);
 262                         Debug_HexDump("NTFS CreateNode VCN#0", tmpbuf, sizeof(tmpbuf));
 263                         NTFS_ReadAttribData(types.tpl_dir.I30Allocation, sizeof(tmpbuf), sizeof(tmpbuf), tmpbuf);
 264                         Debug_HexDump("NTFS CreateNode VCN#1", tmpbuf, sizeof(tmpbuf));
 265                 }
 266                 #endif
 267         }
 268         else
 269         {
 270                 // File
 271                 size = sizeof(types.tpl_file);
 272                 ret = &types.tpl_file.Node;
 273                 ret->Type = &gNTFS_FileType;
 274                 types.tpl_file.Data = NTFS_GetAttrib(Disk, MFTEntry, NTFS_FileAttrib_Data, "", 0);
 275                 ret->Size = types.tpl_file.Data->DataSize;
 276         }
 277         ret->Inode = MFTEntry;
 278         ret->ImplPtr = Disk;
 279
 280         // TODO: Permissions
 281
 282         NTFS_ReleaseMFT(Disk, MFTEntry, ent);
 283         return Inode_CacheNodeEx(Disk->InodeCache, ret, size);
 284 }
 285
 286 /**
 287  * \brief Get an entry from a directory by name
 288  */
 289 tVFS_Node *NTFS_FindDir(tVFS_Node *Node, const char *Name, Uint Flags)
 290 {
 291         tNTFS_Directory *dir = (void*)Node;
 292         tNTFS_Disk      *disk = Node->ImplPtr;
 293         ASSERT(dir->I30Root->IsResident);
 294         const tNTFS_Attrib_IndexRoot    *idxroot = dir->I30Root->ResidentData;
 295
 296         ENTER("XNode->Inode sName xFlags",
 297                 Node->Inode, Name, Flags);
 298
 299         #if 0
 300         size_t  name16len = UTF16_ConvertFromUTF8(0, NULL, Name);
 301         Uint16  name16[name16len+1];
 302         UTF16_ConvertFromUTF8(name16len+1, name16, Name);
 303         #endif
 304
 305         Uint64  mftent = 0;
 306
 307         // Check resident first
 308         size_t  ofs = 0x10 + idxroot->FirstEntryOfs;
 309         mftent = NTFS_BTreeSearch(
 310                 dir->I30Root->DataSize - ofs, dir->I30Root->ResidentData + ofs,
 311                 NTFS_BTreeSearch_CmpI30, -1, Name
 312                 );
 313         while( mftent & (1ULL << 63) )
 314         {
 315                 size_t  unit_len = idxroot->AllocEntrySize;
 316                 char buf[ unit_len ];
 317                 size_t ofs = (mftent & 0xFFFFFF) * unit_len;
 318                 size_t len = NTFS_ReadAttribData(dir->I30Allocation, ofs, sizeof(buf), buf);
 319                 if( len == 0 )
 320                         break;
 321                 tNTFS_IndexHeader       *hdr = (void*)buf;
 322
 323                 if( memcmp(&hdr->Magic, "INDX", 4) != 0 ) {
 324                         Log_Notice("NTFS", "FindDir %p:%X:%x index magic bad %08x",
 325                                 disk, Node->Inode, ofs / unit_len, hdr->Magic);
 326                         break;
 327                 }
 328                 // Apply update sequence
 329                 if(hdr->UpdateSequenceOfs + 2*hdr->UpdateSequenceSize > len) {
 330                         Log_Notice("NTFS", "FindDir %p:%X:%x index update sequence out of buffer (%x+%x>%x)",
 331                                 disk, Node->Inode, ofs / unit_len,
 332                                 hdr->UpdateSequenceOfs, 2*hdr->UpdateSequenceSize, len);
 333                         break;
 334                 }
 335                 NTFS_int_ApplyUpdateSequence(buf,len, (void*)(buf+hdr->UpdateSequenceOfs), hdr->UpdateSequenceSize);
 336                 // Search
 337                 //mftent = NTFS_BTreeSearch(len, (void*)buf, NTFS_BTreeSearch_CmpI30, name16len*2, name16);
 338                 mftent = NTFS_BTreeSearch(
 339                         len-(hdr->EntriesOffset+0x18), buf+hdr->EntriesOffset+0x18,
 340                         NTFS_BTreeSearch_CmpI30, -1, Name
 341                         );
 342         }
 343
 344         if( !mftent || (mftent & (1ULL << 63)) ) {
 345                 LEAVE('n');
 346                 return NULL;
 347         }
 348
 349         // Allocate node
 350         tVFS_Node       *ret = Inode_GetCache(disk->InodeCache, mftent);
 351         if(!ret)
 352                 ret = NTFS_int_CreateNode(disk, mftent);
 353         LEAVE('p', ret);
 354         return ret;
 355 }
 356