From c70e02ed8cc8771daedb78507b33ab0cecebee43 Mon Sep 17 00:00:00 2001 From: John Hodge Date: Tue, 25 Jun 2013 00:43:34 +0800 Subject: [PATCH] Modules/NTFS - ReadDir/FindDir appear to work well --- KernelLand/Modules/Filesystems/NTFS/dir.c | 263 ++++++++++++++------- KernelLand/Modules/Filesystems/NTFS/main.c | 14 +- KernelLand/Modules/Filesystems/NTFS/ntfs.h | 13 +- 3 files changed, 204 insertions(+), 86 deletions(-) diff --git a/KernelLand/Modules/Filesystems/NTFS/dir.c b/KernelLand/Modules/Filesystems/NTFS/dir.c index d7492d02..17785fb7 100644 --- a/KernelLand/Modules/Filesystems/NTFS/dir.c +++ b/KernelLand/Modules/Filesystems/NTFS/dir.c @@ -17,80 +17,80 @@ tVFS_Node *NTFS_FindDir(tVFS_Node *Node, const char *Name, Uint Flags); Uint64 NTFS_int_IndexLookup(Uint64 Inode, const char *IndexName, const char *Str); // === CODE === +const tNTFS_IndexEntry_Filename *NTFS_int_IterateIndex(const char *Buf, size_t Len, int *Count) +{ + const tNTFS_IndexEntry_Filename *ent; + for( size_t ofs = 0; ofs < Len; ofs += ent->EntrySize ) + { + ent = (const void*)(Buf + ofs); + + if( ofs + sizeof(*ent) > Len ) { + break; + } + if( ent->EntrySize < sizeof(*ent) ) { + break; + } + // End of block - move on to the next one + if( ent->IndexFlags & 0x02 ) { + LOG("end of block at ofs %x", ofs); + break; + } + + // A little hacky - hide all internal files + if( (ent->MFTReference & ((1ULL << 48)-1)) < 12 ) + continue; + // Skip DOS filenames + if( ent->Filename.FilenameNamespace == NTFS_FilenameNamespace_DOS ) + continue ; + + // Located + if( (*Count)-- <= 0 ) + return ent; + } + return NULL; +} + /** * \brief Get the name of an indexed directory entry */ int NTFS_ReadDir(tVFS_Node *Node, int Pos, char Dest[FILENAME_MAX]) { tNTFS_Directory *dir = (void*)Node; - tNTFS_Disk *disk = Node->ImplPtr; + + ENTER("XNode->Inode iPos", Node->Inode, Pos); ASSERT(dir->I30Root->IsResident); const tNTFS_Attrib_IndexRoot *idxroot = dir->I30Root->ResidentData; - //const tNTFS_Attrib_IndexEntry *rootents = (void*)(idxroot + 1); - if( idxroot->Flags & 0x01 ) + // Check resident root + const tNTFS_IndexEntry_Filename *ent; + ent = NTFS_int_IterateIndex( + (char*)idxroot + (0x10 + idxroot->FirstEntryOfs), + dir->I30Root->DataSize - (0x10 + idxroot->FirstEntryOfs), + &Pos); + char buf[idxroot->AllocEntrySize]; + size_t vcn = 0; + size_t len; + while( !ent && (len = NTFS_ReadAttribData(dir->I30Allocation, vcn*sizeof(buf), sizeof(buf), buf)) ) { - // Read from allocation - char buf[disk->ClusterSize]; + // Check allocation struct sNTFS_IndexHeader *hdr = (void*)buf; - size_t ofs = 0; - size_t len = sizeof(buf); - struct sNTFS_IndexEntry_Filename *ent = (void*)(buf + len); - - for( ; ; ent = (void*)((char*)ent + ent->EntrySize) ) - { - if( (char*)ent == buf + len ) { - if( len < sizeof(buf)) - break ; - len = NTFS_ReadAttribData(dir->I30Allocation, ofs, sizeof(buf), buf); - ofs += sizeof(buf); - //Debug_HexDump("NTFS_ReadDir", buf, sizeof(*hdr)); - ent = (void*)(buf + (hdr->EntriesOffset + 0x18)); - } - // TODO: When end of node is hit, should the next cluster be loaded? - if( ent->IndexFlags & 0x02 ) - break; - // A little hacky - hide all internal files - if( (ent->MFTReference & ((1ULL << 48)-1)) < 12 ) - continue; - if( Pos -- <= 0 ) - break; - - //LOG("ent = {.MFTEnt=%llx,.FilenameOfs=%x}", ent->MFTReference, ent->FilenameOfs); - #if 0 - //Uint16 *name16 = (Uint16*)ent + ent->FilenameOfs/2; - Uint16 *name16 = ent->Filename.Filename; - size_t nlen = UTF16_ConvertToUTF8(0, NULL, ent->Filename.FilenameLength, name16); - char tmpname[ nlen+1 ]; - UTF16_ConvertToUTF8(nlen+1, tmpname, ent->Filename.FilenameLength, name16); - LOG("name = %i '%s'", ent->Filename.FilenameNamespace, tmpname); - #elif 0 - LOG("name = '%.*ls'", ent->Filename.FilenameLength, ent->Filename.Filename); - #endif - } - - if( Pos >= 0 ) - return -1; - // Last entry does not refer to a file - if( ent->IndexFlags & 0x02 ) - return -1; - - if( ent->Filename.FilenameNamespace == NTFS_FilenameNamespace_DOS ) - return 1; - - //Uint16 *name16 = (Uint16*)ent + ent->FilenameOfs/2; - Uint16 *name16 = ent->Filename.Filename; - UTF16_ConvertToUTF8(FILENAME_MAX, Dest, ent->Filename.FilenameLength, name16); - LOG("Filename '%s'", Dest); - return 0; + ASSERT(hdr->EntriesOffset + 0x18 < len); + size_t ofs = hdr->EntriesOffset + 0x18; + ent = NTFS_int_IterateIndex(buf + ofs, len - ofs, &Pos); + vcn ++; } - else - { - // Local only + if( !ent ) { + LEAVE('i', 1); + return -1; } - return -ENOTIMPL; + // TODO: This is not future-proof + const Uint16 *name16 = ent->Filename.Filename; + UTF16_ConvertToUTF8(FILENAME_MAX, Dest, ent->Filename.FilenameLength, name16); + LOG("Filename '%s'", Dest); + LEAVE('i', 0); + return 0; } typedef int (*tNTFS_BTreeSearch_CmpFcn)(const tNTFS_IndexEntry_Filename *Ent, size_t SLen, const void *Search); @@ -110,17 +110,17 @@ int NTFS_BTreeSearch_CmpI30(const tNTFS_IndexEntry_Filename *Ent, size_t SLen, c else return 1; #else - LOG("Cmp '%.*ls' == '%s'", Ent->Filename.FilenameLength, Ent->Filename.Filename, Search); + //LOG("Cmp '%.*ls' == '%s'", Ent->Filename.FilenameLength, Ent->Filename.Filename, Search); // return UTF16_CompareWithUTF8(Ent->Filename.FilenameLength, Ent->Filename.Filename, Search); return UTF16_CompareWithUTF8CI(Ent->Filename.FilenameLength, Ent->Filename.Filename, Search); #endif } -Uint64 NTFS_BTreeSearch(size_t Length, tNTFS_IndexHeader *IndexHdr, +Uint64 NTFS_BTreeSearch(size_t Length, const void *Data, tNTFS_BTreeSearch_CmpFcn Cmp, size_t SLen, const void *Search) { - void *buffer_end = (char*)IndexHdr + Length; - tNTFS_IndexEntry_Filename *ent = (void*)((char*)IndexHdr + IndexHdr->EntriesOffset + 0x18); + void *buffer_end = (char*)Data + Length; + const tNTFS_IndexEntry_Filename *ent = Data; while( !(ent->IndexFlags & 0x02) ) { if( (void*)(&ent->_rsvd + 1) > buffer_end ) { @@ -130,7 +130,7 @@ Uint64 NTFS_BTreeSearch(size_t Length, tNTFS_IndexHeader *IndexHdr, // TODO: Handle collations? int cmp = Cmp(ent, SLen, Search); if( cmp == 0 ) { - LOG("Located at %p: 0x%016llx", ent->MFTReference); + LOG("Located at %p: 0x%016llx", ent, ent->MFTReference); return ent->MFTReference & ((1ULL << 48)-1); } if( cmp > 0 ) @@ -146,6 +146,73 @@ Uint64 NTFS_BTreeSearch(size_t Length, tNTFS_IndexHeader *IndexHdr, return 0; } +#define _MFTREF_IDX(ref) ((ref) & ((1ULL<<48)-1)) +#define _MFTREF_SEQ(ref) ((ref) >> 48) + +void NTFS_int_DumpIndex(tNTFS_Attrib *Allocation, Uint AttribID) +{ + ENTER("pAllocation xAttribID", Allocation, AttribID); + if(!Allocation) { + LEAVE('-'); + return ; + } + Uint32 vcn = 0; + size_t block_size = MAX(2048, Allocation->Disk->ClusterSize); + char buf[block_size]; + size_t len; + while( (len = NTFS_ReadAttribData(Allocation, vcn*block_size, block_size, buf)) ) + { + struct sNTFS_IndexHeader *hdr = (void*)buf; + LOG("VCN %x: Ofs=%x, Size=%x", + vcn, hdr->EntriesOffset, hdr->EntriesSize); + if( hdr->ThisVCN != vcn ) { + Log_Notice("NTFS", "Data error: Index header VCN mismatch (%x!=exp %x)", hdr->ThisVCN, vcn); + } + size_t ofs = hdr->EntriesOffset + 0x18; + while( ofs < hdr->EntriesSize + (hdr->EntriesOffset + 0x18) ) + { + struct sNTFS_IndexEntry *ent = (void*)(buf + ofs); + if( ofs + sizeof(*ent) > len ) + break; + LOG("%03x: L=%02x,M=%02x,F=%02x, Ref=%x/%llx", ofs, + ent->EntrySize, ent->MessageLen, ent->IndexFlags, + _MFTREF_SEQ(ent->MFTReference), _MFTREF_IDX(ent->MFTReference)); + + if( ent->EntrySize < sizeof(*ent) ) { + Log_Notice("NTFS", "Data error: Index entry size too small"); + break ; + } + if( ent->MessageLen + sizeof(*ent) > ent->EntrySize ) { + Log_Notice("NTFS", "Data error: Index entry message size > entry size"); + } + + if( ent->IndexFlags & NTFS_IndexFlag_HasSubNode ) + { + if( ent->EntrySize < sizeof(*ent) + 8 ) { + Log_Notice("NTFS", "Data error: Index entry size too small (SubVCN)"); + } + LOG("- SubVCN=%llx", *(Uint64*)((char*)ent + ent->EntrySize - 8)); + } + if( ent->IndexFlags & NTFS_IndexFlag_IsLast ) + break; + + switch(AttribID) + { + case 0x30: { + struct sNTFS_Attrib_Filename *fname = (void*)(buf + ofs + sizeof(*ent)); + LOG("- Filename: %i %.*ls", + fname->FilenameNamespace, + fname->FilenameLength, fname->Filename); + break; } + } + + ofs += ent->EntrySize; + } + vcn ++; + } + LEAVE('-'); +} + tVFS_Node *NTFS_int_CreateNode(tNTFS_Disk *Disk, Uint64 MFTEntry) { tNTFS_FILE_Header *ent = NTFS_GetMFT(Disk, MFTEntry); @@ -168,7 +235,29 @@ tVFS_Node *NTFS_int_CreateNode(tNTFS_Disk *Disk, Uint64 MFTEntry) ret->Flags = VFS_FFLAG_DIRECTORY; types.tpl_dir.I30Root = NTFS_GetAttrib(Disk, MFTEntry, NTFS_FileAttrib_IndexRoot, "$I30", 0); - types.tpl_dir.I30Allocation = NTFS_GetAttrib(Disk, MFTEntry, NTFS_FileAttrib_IndexAllocation, "$I30", 0); + types.tpl_dir.I30Allocation = NTFS_GetAttrib(Disk, MFTEntry, + NTFS_FileAttrib_IndexAllocation, "$I30", 0); + + ASSERT(types.tpl_dir.I30Root->IsResident); + #if 0 + Debug_HexDump("NTFS CreateNode Root", + types.tpl_dir.I30Root->ResidentData, + types.tpl_dir.I30Root->DataSize); + if( types.tpl_dir.I30Allocation ) { + NTFS_int_DumpIndex(types.tpl_dir.I30Allocation, 0x30); + } + #endif + + #if 0 + if( MFTEntry == 0x1C ) + { + char tmpbuf[Disk->ClusterSize]; + NTFS_ReadAttribData(types.tpl_dir.I30Allocation, 0, sizeof(tmpbuf), tmpbuf); + Debug_HexDump("NTFS CreateNode VCN#0", tmpbuf, sizeof(tmpbuf)); + NTFS_ReadAttribData(types.tpl_dir.I30Allocation, sizeof(tmpbuf), sizeof(tmpbuf), tmpbuf); + Debug_HexDump("NTFS CreateNode VCN#1", tmpbuf, sizeof(tmpbuf)); + } + #endif } else { @@ -197,6 +286,9 @@ tVFS_Node *NTFS_FindDir(tVFS_Node *Node, const char *Name, Uint Flags) ASSERT(dir->I30Root->IsResident); const tNTFS_Attrib_IndexRoot *idxroot = dir->I30Root->ResidentData; + ENTER("XNode->Inode sName xFlags", + Node->Inode, Name, Flags); + #if 0 size_t name16len = UTF16_ConvertFromUTF8(0, NULL, Name); Uint16 name16[name16len+1]; @@ -204,28 +296,39 @@ tVFS_Node *NTFS_FindDir(tVFS_Node *Node, const char *Name, Uint Flags) #endif Uint64 mftent = 0; - if( idxroot->Flags & 0x01 ) + + // Check resident first + size_t ofs = 0x10 + idxroot->FirstEntryOfs; + mftent = NTFS_BTreeSearch( + dir->I30Root->DataSize - ofs, dir->I30Root->ResidentData + ofs, + NTFS_BTreeSearch_CmpI30, -1, Name + ); + while( mftent & (1ULL << 63) ) { - size_t unit_len = MAX(disk->ClusterSize, 2048); + size_t unit_len = idxroot->AllocEntrySize; char buf[ unit_len ]; - do { - size_t ofs = (mftent & 0xFFFFFF) * unit_len; - size_t len = NTFS_ReadAttribData(dir->I30Allocation, ofs, sizeof(buf), buf); - //mftent = NTFS_BTreeSearch(len, (void*)buf, NTFS_BTreeSearch_CmpI30, name16len*2, name16); - mftent = NTFS_BTreeSearch(len, (void*)buf, NTFS_BTreeSearch_CmpI30, -1, Name); - } while(mftent & (1ULL << 63)); - } - else - { + size_t ofs = (mftent & 0xFFFFFF) * unit_len; + size_t len = NTFS_ReadAttribData(dir->I30Allocation, ofs, sizeof(buf), buf); + if( len == 0 ) + break; + tNTFS_IndexHeader *hdr = (void*)buf; + //mftent = NTFS_BTreeSearch(len, (void*)buf, NTFS_BTreeSearch_CmpI30, name16len*2, name16); + mftent = NTFS_BTreeSearch( + len-(hdr->EntriesOffset+0x18), buf+hdr->EntriesOffset+0x18, + NTFS_BTreeSearch_CmpI30, -1, Name + ); } - if( !mftent ) + if( !mftent ) { + LEAVE('n'); return NULL; + } // Allocate node tVFS_Node *ret = Inode_GetCache(disk->InodeCache, mftent); - if(ret) - return ret; - return NTFS_int_CreateNode(disk, mftent); + if(!ret) + ret = NTFS_int_CreateNode(disk, mftent); + LEAVE('p', ret); + return ret; } diff --git a/KernelLand/Modules/Filesystems/NTFS/main.c b/KernelLand/Modules/Filesystems/NTFS/main.c index b1fafb95..5e1c2aeb 100644 --- a/KernelLand/Modules/Filesystems/NTFS/main.c +++ b/KernelLand/Modules/Filesystems/NTFS/main.c @@ -7,7 +7,7 @@ * * Reference: ntfsdoc.pdf */ -#define DEBUG 1 +#define DEBUG 0 #define VERBOSE 0 #include #include @@ -96,9 +96,9 @@ tVFS_Node *NTFS_InitDevice(const char *Device, const char **Options) return NULL; } - Log_Debug("FS_NTFS", "&bs = %p", &bs); VFS_ReadAt(disk->FD, 0, 512, &bs); - + +#if 0 Log_Debug("FS_NTFS", "Jump = %02x%02x%02x", bs.Jump[0], bs.Jump[1], @@ -119,10 +119,11 @@ tVFS_Node *NTFS_InitDevice(const char *Device, const char **Options) Log_Debug("FS_NTFS", "ClustersPerMFTRecord = %i", bs.ClustersPerMFTRecord); Log_Debug("FS_NTFS", "ClustersPerIndexRecord = %i", bs.ClustersPerIndexRecord); Log_Debug("FS_NTFS", "SerialNumber = 0x%llx", bs.SerialNumber); +#endif disk->ClusterSize = bs.BytesPerSector * bs.SectorsPerCluster; - Log_Debug("NTFS", "Cluster Size = %i KiB", disk->ClusterSize/1024); disk->MFTBase = bs.MFTStart; + Log_Debug("NTFS", "Cluster Size = %i KiB", disk->ClusterSize/1024); Log_Debug("NTFS", "MFT Base = %i", disk->MFTBase); Log_Debug("NTFS", "TotalSectorCount = 0x%x", bs.TotalSectorCount); @@ -139,7 +140,7 @@ tVFS_Node *NTFS_InitDevice(const char *Device, const char **Options) disk->MFTDataAttr = NULL; disk->MFTDataAttr = NTFS_GetAttrib(disk, 0, NTFS_FileAttrib_Data, "", 0); - NTFS_DumpEntry(disk, 5); // . + //NTFS_DumpEntry(disk, 5); // . disk->RootDir.I30Root = NTFS_GetAttrib(disk, 5, NTFS_FileAttrib_IndexRoot, "$I30", 0); disk->RootDir.I30Allocation = NTFS_GetAttrib(disk, 5, NTFS_FileAttrib_IndexAllocation, "$I30", 0); @@ -345,6 +346,7 @@ tNTFS_Attrib *NTFS_GetAttrib(tNTFS_Disk *Disk, Uint32 MFTEntry, int Type, const } else { + ret->DataSize = edatalen; memcpy(ret->ResidentData, (char*)attr + attr->Resident.AttribOfs, edatalen); } @@ -359,6 +361,8 @@ tNTFS_Attrib *NTFS_GetAttrib(tNTFS_Disk *Disk, Uint32 MFTEntry, int Type, const size_t NTFS_ReadAttribData(tNTFS_Attrib *Attrib, Uint64 Offset, size_t Length, void *Buffer) { + if( !Attrib ) + return 0; if( Offset >= Attrib->DataSize ) return 0; if( Length > Attrib->DataSize ) diff --git a/KernelLand/Modules/Filesystems/NTFS/ntfs.h b/KernelLand/Modules/Filesystems/NTFS/ntfs.h index 55c2631e..a65532e1 100644 --- a/KernelLand/Modules/Filesystems/NTFS/ntfs.h +++ b/KernelLand/Modules/Filesystems/NTFS/ntfs.h @@ -151,6 +151,17 @@ struct sNTFS_IndexHeader Uint16 UpdateSequenceArray[]; } PACKED; +#define NTFS_IndexFlag_HasSubNode 0x01 +#define NTFS_IndexFlag_IsLast 0x02 + +struct sNTFS_IndexEntry +{ + Uint64 MFTReference; + Uint16 EntrySize; + Uint16 MessageLen; + Uint16 IndexFlags; // [0]: Points to sub-node, [1]: Last entry in node + Uint16 _rsvd; +} PACKED; struct sNTFS_IndexEntry_Filename { Uint64 MFTReference; @@ -175,7 +186,7 @@ struct sNTFS_IndexEntry_Filename Uint8 FilenameNamespace; #endif // Filename -}; +} PACKED; #endif -- 2.20.1