Merge pull request #2820 from JosJuice/filesystem

Filesystem redesign and performance improvements

8 files changed, 548 insertions, 260 deletions

diff --git a/Source/Core/DiscIO/DiscScrubber.cpp b/Source/Core/DiscIO/DiscScrubber.cpp
index fff2db9ab6..009081cbb6 100644
--- a/Source/Core/DiscIO/DiscScrubber.cpp
+++ b/Source/Core/DiscIO/DiscScrubber.cpp
@@ -219,14 +219,21 @@ bool DiscScrubber::ParsePartitionData(const Partition& partition, PartitionHeade
   MarkAsUsedE(partition_data_offset, header->fst_offset, header->fst_size);
 
   // Go through the filesystem and mark entries as used
-  for (const FileInfo& file : filesystem->GetFileList())
-  {
-    DEBUG_LOG(DISCIO, "%s", file.m_FullPath.empty() ? "/" : file.m_FullPath.c_str());
-    if ((file.m_NameOffset & 0x1000000) == 0)
-      MarkAsUsedE(partition_data_offset, file.m_Offset, file.m_FileSize);
-  }
+  ParseFileSystemData(partition_data_offset, filesystem->GetRoot());
 
   return true;
 }
 
+void DiscScrubber::ParseFileSystemData(u64 partition_data_offset, const FileInfo& directory)
+{
+  for (const DiscIO::FileInfo& file_info : directory)
+  {
+    DEBUG_LOG(DISCIO, "Scrubbing %s", file_info.GetPath().c_str());
+    if (file_info.IsDirectory())
+      ParseFileSystemData(partition_data_offset, file_info);
+    else
+      MarkAsUsedE(partition_data_offset, file_info.GetOffset(), file_info.GetSize());
+  }
+}
+
 }  // namespace DiscIO
diff --git a/Source/Core/DiscIO/DiscScrubber.h b/Source/Core/DiscIO/DiscScrubber.h
index 0eda66da48..d61b8422da 100644
--- a/Source/Core/DiscIO/DiscScrubber.h
+++ b/Source/Core/DiscIO/DiscScrubber.h
@@ -25,6 +25,7 @@ class IOFile;
 
 namespace DiscIO
 {
+class FileInfo;
 class Volume;
 struct Partition;
 
@@ -64,6 +65,7 @@ private:
   bool ReadFromVolume(u64 offset, u64& buffer, const Partition& partition);
   bool ParseDisc();
   bool ParsePartitionData(const Partition& partition, PartitionHeader* header);
+  void ParseFileSystemData(u64 partition_data_offset, const FileInfo& directory);
 
   std::string m_filename;
   std::unique_ptr<Volume> m_disc;
diff --git a/Source/Core/DiscIO/FileSystemGCWii.cpp b/Source/Core/DiscIO/FileSystemGCWii.cpp
index b809047679..09a171677d 100644
--- a/Source/Core/DiscIO/FileSystemGCWii.cpp
+++ b/Source/Core/DiscIO/FileSystemGCWii.cpp
@@ -6,6 +6,8 @@
 #include <cinttypes>
 #include <cstddef>
 #include <cstring>
+#include <map>
+#include <memory>
 #include <optional>
 #include <string>
 #include <vector>
@@ -22,114 +24,372 @@
 
 namespace DiscIO
 {
-FileSystemGCWii::FileSystemGCWii(const Volume* _rVolume, const Partition& partition)
-    : FileSystem(_rVolume, partition), m_Initialized(false), m_Valid(false), m_offset_shift(0)
+constexpr u32 FST_ENTRY_SIZE = 4 * 3;  // An FST entry consists of three 32-bit integers
+
+// Set everything manually.
+FileInfoGCWii::FileInfoGCWii(const u8* fst, u8 offset_shift, u32 index, u32 total_file_infos)
+    : m_fst(fst), m_offset_shift(offset_shift), m_index(index), m_total_file_infos(total_file_infos)
 {
-  m_Valid = DetectFileSystem();
 }
 
-FileSystemGCWii::~FileSystemGCWii()
+// For the root object only.
+// m_fst and m_index must be correctly set before GetSize() is called!
+FileInfoGCWii::FileInfoGCWii(const u8* fst, u8 offset_shift)
+    : m_fst(fst), m_offset_shift(offset_shift), m_index(0), m_total_file_infos(GetSize())
 {
-  m_FileInfoVector.clear();
 }
 
-u64 FileSystemGCWii::GetFileSize(const std::string& _rFullPath)
+// Copy data that is common to the whole file system.
+FileInfoGCWii::FileInfoGCWii(const FileInfoGCWii& file_info, u32 index)
+    : FileInfoGCWii(file_info.m_fst, file_info.m_offset_shift, index, file_info.m_total_file_infos)
 {
-  if (!m_Initialized)
-    InitFileSystem();
+}
 
-  const FileInfo* pFileInfo = FindFileInfo(_rFullPath);
+FileInfoGCWii::~FileInfoGCWii() = default;
 
-  if (pFileInfo != nullptr && !pFileInfo->IsDirectory())
-    return pFileInfo->m_FileSize;
+uintptr_t FileInfoGCWii::GetAddress() const
+{
+  return reinterpret_cast<uintptr_t>(m_fst + FST_ENTRY_SIZE * m_index);
+}
 
-  return 0;
+u32 FileInfoGCWii::GetNextIndex() const
+{
+  return IsDirectory() ? GetSize() : m_index + 1;
 }
 
-std::string FileSystemGCWii::GetFileName(u64 _Address)
+FileInfo& FileInfoGCWii::operator++()
 {
-  if (!m_Initialized)
-    InitFileSystem();
+  m_index = GetNextIndex();
+  return *this;
+}
 
-  for (auto& fileInfo : m_FileInfoVector)
+std::unique_ptr<FileInfo> FileInfoGCWii::clone() const
+{
+  return std::make_unique<FileInfoGCWii>(*this);
+}
+
+FileInfo::const_iterator FileInfoGCWii::begin() const
+{
+  return const_iterator(std::make_unique<FileInfoGCWii>(*this, m_index + 1));
+}
+
+FileInfo::const_iterator FileInfoGCWii::end() const
+{
+  return const_iterator(std::make_unique<FileInfoGCWii>(*this, GetNextIndex()));
+}
+
+u32 FileInfoGCWii::Get(EntryProperty entry_property) const
+{
+  return Common::swap32(m_fst + FST_ENTRY_SIZE * m_index +
+                        sizeof(u32) * static_cast<int>(entry_property));
+}
+
+u32 FileInfoGCWii::GetSize() const
+{
+  return Get(EntryProperty::FILE_SIZE);
+}
+
+u64 FileInfoGCWii::GetOffset() const
+{
+  return static_cast<u64>(Get(EntryProperty::FILE_OFFSET)) << m_offset_shift;
+}
+
+bool FileInfoGCWii::IsDirectory() const
+{
+  return (Get(EntryProperty::NAME_OFFSET) & 0xFF000000) != 0;
+}
+
+u32 FileInfoGCWii::GetTotalChildren() const
+{
+  return Get(EntryProperty::FILE_SIZE) - (m_index + 1);
+}
+
+u64 FileInfoGCWii::GetNameOffset() const
+{
+  return static_cast<u64>(FST_ENTRY_SIZE) * m_total_file_infos +
+         (Get(EntryProperty::NAME_OFFSET) & 0xFFFFFF);
+}
+
+std::string FileInfoGCWii::GetName() const
+{
+  // TODO: Should we really always use SHIFT-JIS?
+  // Some names in Pikmin (NTSC-U) don't make sense without it, but is it correct?
+  return SHIFTJISToUTF8(reinterpret_cast<const char*>(m_fst + GetNameOffset()));
+}
+
+std::string FileInfoGCWii::GetPath() const
+{
+  // The root entry doesn't have a name
+  if (m_index == 0)
+    return "";
+
+  if (IsDirectory())
+  {
+    u32 parent_directory_index = Get(EntryProperty::FILE_OFFSET);
+    return FileInfoGCWii(*this, parent_directory_index).GetPath() + GetName() + "/";
+  }
+  else
   {
-    if ((fileInfo.m_Offset <= _Address) && ((fileInfo.m_Offset + fileInfo.m_FileSize) > _Address))
+    // The parent directory can be found by searching backwards
+    // for a directory that contains this file. The search cannot fail,
+    // because the root directory at index 0 contains all files.
+    FileInfoGCWii potential_parent(*this, m_index - 1);
+    while (!(potential_parent.IsDirectory() &&
+             potential_parent.Get(EntryProperty::FILE_SIZE) > m_index))
     {
-      return fileInfo.m_FullPath;
+      potential_parent = FileInfoGCWii(*this, potential_parent.m_index - 1);
     }
+    return potential_parent.GetPath() + GetName();
+  }
+}
+
+bool FileInfoGCWii::IsValid(u64 fst_size, const FileInfoGCWii& parent_directory) const
+{
+  if (GetNameOffset() >= fst_size)
+  {
+    ERROR_LOG(DISCIO, "Impossibly large name offset in file system");
+    return false;
   }
 
-  return "";
+  if (IsDirectory())
+  {
+    if (Get(EntryProperty::FILE_OFFSET) != parent_directory.m_index)
+    {
+      ERROR_LOG(DISCIO, "Incorrect parent offset in file system");
+      return false;
+    }
+
+    u32 size = Get(EntryProperty::FILE_SIZE);
+
+    if (size <= m_index)
+    {
+      ERROR_LOG(DISCIO, "Impossibly small directory size in file system");
+      return false;
+    }
+
+    if (size > parent_directory.Get(EntryProperty::FILE_SIZE))
+    {
+      ERROR_LOG(DISCIO, "Impossibly large directory size in file system");
+      return false;
+    }
+
+    for (const FileInfo& child : *this)
+    {
+      if (!static_cast<const FileInfoGCWii&>(child).IsValid(fst_size, *this))
+        return false;
+    }
+  }
+
+  return true;
 }
 
-u64 FileSystemGCWii::ReadFile(const std::string& _rFullPath, u8* _pBuffer, u64 _MaxBufferSize,
-                              u64 _OffsetInFile)
+FileSystemGCWii::FileSystemGCWii(const Volume* volume, const Partition& partition)
+    : FileSystem(volume, partition), m_valid(false), m_offset_shift(0), m_root(nullptr, 0, 0, 0)
 {
-  if (!m_Initialized)
-    InitFileSystem();
+  // Check if this is a GameCube or Wii disc
+  if (m_volume->ReadSwapped<u32>(0x18, m_partition) == u32(0x5D1C9EA3))
+    m_offset_shift = 2;  // Wii file system
+  else if (m_volume->ReadSwapped<u32>(0x1c, m_partition) == u32(0xC2339F3D))
+    m_offset_shift = 0;  // GameCube file system
+  else
+    return;
+
+  const std::optional<u32> fst_offset_unshifted = m_volume->ReadSwapped<u32>(0x424, m_partition);
+  const std::optional<u32> fst_size_unshifted = m_volume->ReadSwapped<u32>(0x428, m_partition);
+  if (!fst_offset_unshifted || !fst_size_unshifted)
+    return;
+  const u64 fst_offset = static_cast<u64>(*fst_offset_unshifted) << m_offset_shift;
+  const u64 fst_size = static_cast<u64>(*fst_size_unshifted) << m_offset_shift;
+  if (fst_size < FST_ENTRY_SIZE)
+  {
+    ERROR_LOG(DISCIO, "File system is too small");
+    return;
+  }
+
+  // 128 MiB is more than the total amount of RAM in a Wii.
+  // No file system should use anywhere near that much.
+  static const u32 ARBITRARY_FILE_SYSTEM_SIZE_LIMIT = 128 * 1024 * 1024;
+  if (fst_size > ARBITRARY_FILE_SYSTEM_SIZE_LIMIT)
+  {
+    // Without this check, Dolphin can crash by trying to allocate too much
+    // memory when loading a disc image with an incorrect FST size.
 
-  const FileInfo* pFileInfo = FindFileInfo(_rFullPath);
-  if (pFileInfo == nullptr)
+    ERROR_LOG(DISCIO, "File system is abnormally large! Aborting loading");
+    return;
+  }
+
+  // Read the whole FST
+  m_file_system_table.resize(fst_size);
+  if (!m_volume->Read(fst_offset, fst_size, m_file_system_table.data(), m_partition))
+  {
+    ERROR_LOG(DISCIO, "Couldn't read file system table");
+    return;
+  }
+
+  // Create the root object
+  m_root = FileInfoGCWii(m_file_system_table.data(), m_offset_shift);
+  if (!m_root.IsDirectory())
+  {
+    ERROR_LOG(DISCIO, "File system root is not a directory");
+    return;
+  }
+
+  if (FST_ENTRY_SIZE * m_root.GetSize() > fst_size)
+  {
+    ERROR_LOG(DISCIO, "File system has too many entries for its size");
+    return;
+  }
+
+  // If the FST's final byte isn't 0, CFileInfoGCWii::GetName() can read past the end
+  if (m_file_system_table[fst_size - 1] != 0)
+  {
+    ERROR_LOG(DISCIO, "File system does not end with a null byte");
+    return;
+  }
+
+  m_valid = m_root.IsValid(fst_size, m_root);
+}
+
+FileSystemGCWii::~FileSystemGCWii() = default;
+
+const FileInfo& FileSystemGCWii::GetRoot() const
+{
+  return m_root;
+}
+
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(const std::string& path) const
+{
+  if (!IsValid())
+    return nullptr;
+
+  return FindFileInfo(path, m_root);
+}
+
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(const std::string& path,
+                                                        const FileInfo& file_info) const
+{
+  // Given a path like "directory1/directory2/fileA.bin", this function will
+  // find directory1 and then call itself to search for "directory2/fileA.bin".
+
+  if (path.empty() || path == "/")
+    return file_info.clone();
+
+  // It's only possible to search in directories. Searching in a file is an error
+  if (!file_info.IsDirectory())
+    return nullptr;
+
+  size_t first_dir_separator = path.find('/');
+  const std::string searching_for = path.substr(0, first_dir_separator);
+  const std::string rest_of_path =
+      (first_dir_separator != std::string::npos) ? path.substr(first_dir_separator + 1) : "";
+
+  for (const FileInfo& child : file_info)
+  {
+    if (child.GetName() == searching_for)
+    {
+      // A match is found. The rest of the path is passed on to finish the search.
+      std::unique_ptr<FileInfo> result = FindFileInfo(rest_of_path, child);
+
+      // If the search wasn't successful, the loop continues, just in case there's a second
+      // file info that matches searching_for (which probably won't happen in practice)
+      if (result)
+        return result;
+    }
+  }
+
+  return nullptr;
+}
+
+std::unique_ptr<FileInfo> FileSystemGCWii::FindFileInfo(u64 disc_offset) const
+{
+  if (!IsValid())
+    return nullptr;
+
+  // Build a cache (unless there already is one)
+  if (m_offset_file_info_cache.empty())
+  {
+    u32 fst_entries = m_root.GetSize();
+    for (u32 i = 0; i < fst_entries; i++)
+    {
+      FileInfoGCWii file_info(m_root, i);
+      if (!file_info.IsDirectory())
+        m_offset_file_info_cache.emplace(file_info.GetOffset() + file_info.GetSize(), i);
+    }
+  }
+
+  // Get the first file that ends after disc_offset
+  const auto it = m_offset_file_info_cache.upper_bound(disc_offset);
+  if (it == m_offset_file_info_cache.end())
+    return nullptr;
+  std::unique_ptr<FileInfo> result(std::make_unique<FileInfoGCWii>(m_root, it->second));
+
+  // If the file's start isn't after disc_offset, success
+  if (result->GetOffset() <= disc_offset)
+    return result;
+
+  return nullptr;
+}
+
+u64 FileSystemGCWii::ReadFile(const FileInfo* file_info, u8* buffer, u64 max_buffer_size,
+                              u64 offset_in_file) const
+{
+  if (!file_info || file_info->IsDirectory())
     return 0;
 
-  if (_OffsetInFile >= pFileInfo->m_FileSize)
+  if (offset_in_file >= file_info->GetSize())
     return 0;
 
-  u64 read_length = std::min(_MaxBufferSize, pFileInfo->m_FileSize - _OffsetInFile);
+  u64 read_length = std::min(max_buffer_size, file_info->GetSize() - offset_in_file);
 
   DEBUG_LOG(DISCIO, "Reading %" PRIx64 " bytes at %" PRIx64 " from file %s. Offset: %" PRIx64
-                    " Size: %" PRIx64,
-            read_length, _OffsetInFile, _rFullPath.c_str(), pFileInfo->m_Offset,
-            pFileInfo->m_FileSize);
+                    " Size: %" PRIx32,
+            read_length, offset_in_file, file_info->GetPath().c_str(), file_info->GetOffset(),
+            file_info->GetSize());
 
-  m_rVolume->Read(pFileInfo->m_Offset + _OffsetInFile, read_length, _pBuffer, m_partition);
+  m_volume->Read(file_info->GetOffset() + offset_in_file, read_length, buffer, m_partition);
   return read_length;
 }
 
-bool FileSystemGCWii::ExportFile(const std::string& _rFullPath, const std::string& _rExportFilename)
+bool FileSystemGCWii::ExportFile(const FileInfo* file_info,
+                                 const std::string& export_filename) const
 {
-  if (!m_Initialized)
-    InitFileSystem();
-
-  const FileInfo* pFileInfo = FindFileInfo(_rFullPath);
-
-  if (!pFileInfo)
+  if (!file_info || file_info->IsDirectory())
     return false;
 
-  u64 remainingSize = pFileInfo->m_FileSize;
-  u64 fileOffset = pFileInfo->m_Offset;
+  u64 remaining_size = file_info->GetSize();
+  u64 file_offset = file_info->GetOffset();
 
-  File::IOFile f(_rExportFilename, "wb");
+  File::IOFile f(export_filename, "wb");
   if (!f)
     return false;
 
   bool result = true;
 
-  while (remainingSize)
+  while (remaining_size)
   {
     // Limit read size to 128 MB
-    size_t readSize = (size_t)std::min(remainingSize, (u64)0x08000000);
+    size_t read_size = (size_t)std::min(remaining_size, (u64)0x08000000);
 
-    std::vector<u8> buffer(readSize);
+    std::vector<u8> buffer(read_size);
 
-    result = m_rVolume->Read(fileOffset, readSize, &buffer[0], m_partition);
+    result = m_volume->Read(file_offset, read_size, &buffer[0], m_partition);
 
     if (!result)
       break;
 
-    f.WriteBytes(&buffer[0], readSize);
+    f.WriteBytes(&buffer[0], read_size);
 
-    remainingSize -= readSize;
-    fileOffset += readSize;
+    remaining_size -= read_size;
+    file_offset += read_size;
   }
 
   return result;
 }
 
-bool FileSystemGCWii::ExportApploader(const std::string& _rExportFolder) const
+bool FileSystemGCWii::ExportApploader(const std::string& export_folder) const
 {
-  std::optional<u32> apploader_size = m_rVolume->ReadSwapped<u32>(0x2440 + 0x14, m_partition);
-  const std::optional<u32> trailer_size = m_rVolume->ReadSwapped<u32>(0x2440 + 0x18, m_partition);
+  std::optional<u32> apploader_size = m_volume->ReadSwapped<u32>(0x2440 + 0x14, m_partition);
+  const std::optional<u32> trailer_size = m_volume->ReadSwapped<u32>(0x2440 + 0x18, m_partition);
   constexpr u32 header_size = 0x20;
   if (!apploader_size || !trailer_size)
     return false;
@@ -137,14 +397,14 @@ bool FileSystemGCWii::ExportApploader(const std::string& _rExportFolder) const
   DEBUG_LOG(DISCIO, "Apploader size -> %x", *apploader_size);
 
   std::vector<u8> buffer(*apploader_size);
-  if (m_rVolume->Read(0x2440, *apploader_size, buffer.data(), m_partition))
+  if (m_volume->Read(0x2440, *apploader_size, buffer.data(), m_partition))
   {
-    std::string exportName(_rExportFolder + "/apploader.img");
+    std::string export_name(export_folder + "/apploader.img");
 
-    File::IOFile AppFile(exportName, "wb");
-    if (AppFile)
+    File::IOFile apploader_file(export_name, "wb");
+    if (apploader_file)
     {
-      AppFile.WriteBytes(buffer.data(), *apploader_size);
+      apploader_file.WriteBytes(buffer.data(), *apploader_size);
       return true;
     }
   }
@@ -154,7 +414,7 @@ bool FileSystemGCWii::ExportApploader(const std::string& _rExportFolder) const
 
 std::optional<u64> FileSystemGCWii::GetBootDOLOffset() const
 {
-  std::optional<u32> offset = m_rVolume->ReadSwapped<u32>(0x420, m_partition);
+  std::optional<u32> offset = m_volume->ReadSwapped<u32>(0x420, m_partition);
   return offset ? static_cast<u64>(*offset) << m_offset_shift : std::optional<u64>();
 }
 
@@ -166,9 +426,9 @@ std::optional<u32> FileSystemGCWii::GetBootDOLSize(u64 dol_offset) const
   for (u8 i = 0; i < 7; i++)
   {
     const std::optional<u32> offset =
-        m_rVolume->ReadSwapped<u32>(dol_offset + 0x00 + i * 4, m_partition);
+        m_volume->ReadSwapped<u32>(dol_offset + 0x00 + i * 4, m_partition);
     const std::optional<u32> size =
-        m_rVolume->ReadSwapped<u32>(dol_offset + 0x90 + i * 4, m_partition);
+        m_volume->ReadSwapped<u32>(dol_offset + 0x90 + i * 4, m_partition);
     if (!offset || !size)
       return {};
     dol_size = std::max(*offset + *size, dol_size);
@@ -178,9 +438,9 @@ std::optional<u32> FileSystemGCWii::GetBootDOLSize(u64 dol_offset) const
   for (u8 i = 0; i < 11; i++)
   {
     const std::optional<u32> offset =
-        m_rVolume->ReadSwapped<u32>(dol_offset + 0x1c + i * 4, m_partition);
+        m_volume->ReadSwapped<u32>(dol_offset + 0x1c + i * 4, m_partition);
     const std::optional<u32> size =
-        m_rVolume->ReadSwapped<u32>(dol_offset + 0xac + i * 4, m_partition);
+        m_volume->ReadSwapped<u32>(dol_offset + 0xac + i * 4, m_partition);
     if (!offset || !size)
       return {};
     dol_size = std::max(*offset + *size, dol_size);
@@ -189,7 +449,7 @@ std::optional<u32> FileSystemGCWii::GetBootDOLSize(u64 dol_offset) const
   return dol_size;
 }
 
-bool FileSystemGCWii::ExportDOL(const std::string& _rExportFolder) const
+bool FileSystemGCWii::ExportDOL(const std::string& export_folder) const
 {
   std::optional<u64> dol_offset = GetBootDOLOffset();
   if (!dol_offset)
@@ -199,14 +459,14 @@ bool FileSystemGCWii::ExportDOL(const std::string& _rExportFolder) const
     return false;
 
   std::vector<u8> buffer(*dol_size);
-  if (m_rVolume->Read(*dol_offset, *dol_size, &buffer[0], m_partition))
+  if (m_volume->Read(*dol_offset, *dol_size, buffer.data(), m_partition))
   {
-    std::string exportName(_rExportFolder + "/boot.dol");
+    std::string export_name(export_folder + "/boot.dol");
 
-    File::IOFile DolFile(exportName, "wb");
-    if (DolFile)
+    File::IOFile dol_file(export_name, "wb");
+    if (dol_file)
     {
-      DolFile.WriteBytes(&buffer[0], *dol_size);
+      dol_file.WriteBytes(&buffer[0], *dol_size);
       return true;
     }
   }
@@ -214,137 +474,4 @@ bool FileSystemGCWii::ExportDOL(const std::string& _rExportFolder) const
   return false;
 }
 
-std::string FileSystemGCWii::GetStringFromOffset(u64 _Offset) const
-{
-  std::string data(255, 0x00);
-  m_rVolume->Read(_Offset, data.size(), (u8*)&data[0], m_partition);
-  data.erase(std::find(data.begin(), data.end(), 0x00), data.end());
-
-  // TODO: Should we really always use SHIFT-JIS?
-  // It makes some filenames in Pikmin (NTSC-U) sane, but is it correct?
-  return SHIFTJISToUTF8(data);
-}
-
-const std::vector<FileInfo>& FileSystemGCWii::GetFileList()
-{
-  if (!m_Initialized)
-    InitFileSystem();
-
-  return m_FileInfoVector;
-}
-
-const FileInfo* FileSystemGCWii::FindFileInfo(const std::string& _rFullPath)
-{
-  if (!m_Initialized)
-    InitFileSystem();
-
-  for (auto& fileInfo : m_FileInfoVector)
-  {
-    if (!strcasecmp(fileInfo.m_FullPath.c_str(), _rFullPath.c_str()))
-      return &fileInfo;
-  }
-
-  return nullptr;
-}
-
-bool FileSystemGCWii::DetectFileSystem()
-{
-  if (m_rVolume->ReadSwapped<u32>(0x18, m_partition) == u32(0x5D1C9EA3))
-  {
-    m_offset_shift = 2;  // Wii file system
-    return true;
-  }
-  else if (m_rVolume->ReadSwapped<u32>(0x1c, m_partition) == u32(0xC2339F3D))
-  {
-    m_offset_shift = 0;  // GameCube file system
-    return true;
-  }
-
-  return false;
-}
-
-void FileSystemGCWii::InitFileSystem()
-{
-  m_Initialized = true;
-
-  // read the whole FST
-  const std::optional<u32> fst_offset_unshifted = m_rVolume->ReadSwapped<u32>(0x424, m_partition);
-  if (!fst_offset_unshifted)
-    return;
-  const u64 FSTOffset = static_cast<u64>(*fst_offset_unshifted) << m_offset_shift;
-
-  // read all fileinfos
-  const std::optional<u32> root_name_offset = m_rVolume->ReadSwapped<u32>(FSTOffset, m_partition);
-  const std::optional<u32> root_offset = m_rVolume->ReadSwapped<u32>(FSTOffset + 0x4, m_partition);
-  const std::optional<u32> root_size = m_rVolume->ReadSwapped<u32>(FSTOffset + 0x8, m_partition);
-  if (!root_name_offset || !root_offset || !root_size)
-    return;
-  FileInfo root = {*root_name_offset, static_cast<u64>(*root_offset) << m_offset_shift, *root_size};
-
-  if (!root.IsDirectory())
-    return;
-
-  // 12 bytes (the size of a file entry) times 10 * 1024 * 1024 is 120 MiB,
-  // more than total RAM in a Wii. No file system should use anywhere near that much.
-  static const u32 ARBITRARY_FILE_SYSTEM_SIZE_LIMIT = 10 * 1024 * 1024;
-  if (root.m_FileSize > ARBITRARY_FILE_SYSTEM_SIZE_LIMIT)
-  {
-    // Without this check, Dolphin can crash by trying to allocate too much
-    // memory when loading the file systems of certain malformed disc images.
-
-    ERROR_LOG(DISCIO, "File system is abnormally large! Aborting loading");
-    return;
-  }
-
-  if (m_FileInfoVector.size())
-    PanicAlert("Wtf?");
-  u64 NameTableOffset = FSTOffset;
-
-  m_FileInfoVector.reserve((size_t)root.m_FileSize);
-  for (u32 i = 0; i < root.m_FileSize; i++)
-  {
-    const u64 read_offset = FSTOffset + (i * 0xC);
-    const std::optional<u32> name_offset = m_rVolume->ReadSwapped<u32>(read_offset, m_partition);
-    const std::optional<u32> offset = m_rVolume->ReadSwapped<u32>(read_offset + 0x4, m_partition);
-    const std::optional<u32> size = m_rVolume->ReadSwapped<u32>(read_offset + 0x8, m_partition);
-    m_FileInfoVector.emplace_back(name_offset.value_or(0),
-                                  static_cast<u64>(offset.value_or(0)) << m_offset_shift,
-                                  size.value_or(0));
-    NameTableOffset += 0xC;
-  }
-
-  BuildFilenames(1, m_FileInfoVector.size(), "", NameTableOffset);
-}
-
-size_t FileSystemGCWii::BuildFilenames(const size_t _FirstIndex, const size_t _LastIndex,
-                                       const std::string& _szDirectory, u64 _NameTableOffset)
-{
-  size_t CurrentIndex = _FirstIndex;
-
-  while (CurrentIndex < _LastIndex)
-  {
-    FileInfo& rFileInfo = m_FileInfoVector[CurrentIndex];
-    u64 const uOffset = _NameTableOffset + (rFileInfo.m_NameOffset & 0xFFFFFF);
-    std::string const offset_str{GetStringFromOffset(uOffset)};
-    bool const is_dir = rFileInfo.IsDirectory();
-    rFileInfo.m_FullPath.reserve(_szDirectory.size() + offset_str.size());
-
-    rFileInfo.m_FullPath.append(_szDirectory.data(), _szDirectory.size())
-        .append(offset_str.data(), offset_str.size())
-        .append("/", size_t(is_dir));
-
-    if (!is_dir)
-    {
-      ++CurrentIndex;
-      continue;
-    }
-
-    // check next index
-    CurrentIndex = BuildFilenames(CurrentIndex + 1, (size_t)rFileInfo.m_FileSize,
-                                  rFileInfo.m_FullPath, _NameTableOffset);
-  }
-
-  return CurrentIndex;
-}
-
 }  // namespace
diff --git a/Source/Core/DiscIO/FileSystemGCWii.h b/Source/Core/DiscIO/FileSystemGCWii.h
index 3655c5fcb2..ee69bfed94 100644
--- a/Source/Core/DiscIO/FileSystemGCWii.h
+++ b/Source/Core/DiscIO/FileSystemGCWii.h
@@ -5,6 +5,8 @@
 #pragma once
 
 #include <cstddef>
+#include <map>
+#include <memory>
 #include <optional>
 #include <string>
 #include <vector>
@@ -17,36 +19,97 @@ namespace DiscIO
 class Volume;
 struct Partition;
 
+class FileInfoGCWii : public FileInfo
+{
+public:
+  // None of the constructors take ownership of FST pointers
+
+  // Set everything manually
+  FileInfoGCWii(const u8* fst, u8 offset_shift, u32 index, u32 total_file_infos);
+  // For the root object only
+  FileInfoGCWii(const u8* fst, u8 offset_shift);
+  // Copy another object
+  FileInfoGCWii(const FileInfoGCWii& file_info) = default;
+  // Copy data that is common to the whole file system
+  FileInfoGCWii(const FileInfoGCWii& file_info, u32 index);
+
+  ~FileInfoGCWii() override;
+
+  std::unique_ptr<FileInfo> clone() const override;
+  const_iterator begin() const override;
+  const_iterator end() const override;
+
+  u64 GetOffset() const override;
+  u32 GetSize() const override;
+  bool IsDirectory() const override;
+  u32 GetTotalChildren() const override;
+  std::string GetName() const override;
+  std::string GetPath() const override;
+
+  bool IsValid(u64 fst_size, const FileInfoGCWii& parent_directory) const;
+
+protected:
+  uintptr_t GetAddress() const override;
+  FileInfo& operator++() override;
+
+private:
+  enum class EntryProperty
+  {
+    // NAME_OFFSET's lower 3 bytes are the name's offset within the name table.
+    // NAME_OFFSET's upper 1 byte is 1 for directories and 0 for files.
+    NAME_OFFSET = 0,
+    // For files, FILE_OFFSET is the file offset in the partition,
+    // and for directories, it's the FST index of the parent directory.
+    // The root directory has its parent directory index set to 0.
+    FILE_OFFSET = 1,
+    // For files, FILE_SIZE is the file size, and for directories,
+    // it's the FST index of the next entry that isn't in the directory.
+    FILE_SIZE = 2
+  };
+
+  // For files, returns the index of the next item. For directories,
+  // returns the index of the next item that isn't inside it.
+  u32 GetNextIndex() const;
+  // Returns one of the three properties of this FST entry.
+  // Read the comments in EntryProperty for details.
+  u32 Get(EntryProperty entry_property) const;
+  // Returns the name offset, excluding the directory identification byte
+  u64 GetNameOffset() const;
+
+  const u8* m_fst;
+  u8 m_offset_shift;
+  u32 m_index;
+  u32 m_total_file_infos;
+};
+
 class FileSystemGCWii : public FileSystem
 {
 public:
-  FileSystemGCWii(const Volume* _rVolume, const Partition& partition);
-  virtual ~FileSystemGCWii();
-
-  bool IsValid() const override { return m_Valid; }
-  u64 GetFileSize(const std::string& _rFullPath) override;
-  const std::vector<FileInfo>& GetFileList() override;
-  std::string GetFileName(u64 _Address) override;
-  u64 ReadFile(const std::string& _rFullPath, u8* _pBuffer, u64 _MaxBufferSize,
-               u64 _OffsetInFile) override;
-  bool ExportFile(const std::string& _rFullPath, const std::string& _rExportFilename) override;
-  bool ExportApploader(const std::string& _rExportFolder) const override;
-  bool ExportDOL(const std::string& _rExportFolder) const override;
+  FileSystemGCWii(const Volume* volume, const Partition& partition);
+  ~FileSystemGCWii() override;
+
+  bool IsValid() const override { return m_valid; }
+  const FileInfo& GetRoot() const override;
+  std::unique_ptr<FileInfo> FindFileInfo(const std::string& path) const override;
+  std::unique_ptr<FileInfo> FindFileInfo(u64 disc_offset) const override;
+
+  u64 ReadFile(const FileInfo* file_info, u8* buffer, u64 max_buffer_size,
+               u64 offset_in_file) const override;
+  bool ExportFile(const FileInfo* file_info, const std::string& export_filename) const override;
+  bool ExportApploader(const std::string& export_folder) const override;
+  bool ExportDOL(const std::string& export_folder) const override;
   std::optional<u64> GetBootDOLOffset() const override;
   std::optional<u32> GetBootDOLSize(u64 dol_offset) const override;
 
 private:
-  bool m_Initialized;
-  bool m_Valid;
+  bool m_valid;
   u32 m_offset_shift;
-  std::vector<FileInfo> m_FileInfoVector;
-
-  std::string GetStringFromOffset(u64 _Offset) const;
-  const FileInfo* FindFileInfo(const std::string& _rFullPath);
-  bool DetectFileSystem();
-  void InitFileSystem();
-  size_t BuildFilenames(const size_t _FirstIndex, const size_t _LastIndex,
-                        const std::string& _szDirectory, u64 _NameTableOffset);
+  std::vector<u8> m_file_system_table;
+  FileInfoGCWii m_root;
+  // Maps the end offset of files to FST indexes
+  mutable std::map<u64, u32> m_offset_file_info_cache;
+
+  std::unique_ptr<FileInfo> FindFileInfo(const std::string& path, const FileInfo& file_info) const;
 };
 
 }  // namespace
diff --git a/Source/Core/DiscIO/Filesystem.cpp b/Source/Core/DiscIO/Filesystem.cpp
index a955c1f402..6171c3004f 100644
--- a/Source/Core/DiscIO/Filesystem.cpp
+++ b/Source/Core/DiscIO/Filesystem.cpp
@@ -9,15 +9,15 @@
 
 namespace DiscIO
 {
-FileSystem::FileSystem(const Volume* _rVolume, const Partition& partition)
-    : m_rVolume(_rVolume), m_partition(partition)
-{
-}
+FileInfo::~FileInfo() = default;
 
-FileSystem::~FileSystem()
+FileSystem::FileSystem(const Volume* volume, const Partition& partition)
+    : m_volume(volume), m_partition(partition)
 {
 }
 
+FileSystem::~FileSystem() = default;
+
 std::unique_ptr<FileSystem> CreateFileSystem(const Volume* volume, const Partition& partition)
 {
   if (!volume)
diff --git a/Source/Core/DiscIO/Filesystem.h b/Source/Core/DiscIO/Filesystem.h
index 7502db52f0..879c6fbbdd 100644
--- a/Source/Core/DiscIO/Filesystem.h
+++ b/Source/Core/DiscIO/Filesystem.h
@@ -4,6 +4,7 @@
 
 #pragma once
 
+#include <iterator>
 #include <memory>
 #include <optional>
 #include <string>
@@ -15,47 +16,125 @@
 namespace DiscIO
 {
 // file info of an FST entry
-struct FileInfo
+class FileInfo
 {
-  u64 m_NameOffset = 0u;
-  u64 m_Offset = 0u;
-  u64 m_FileSize = 0u;
-  std::string m_FullPath;
-
-  bool IsDirectory() const { return (m_NameOffset & 0xFF000000) != 0; }
-  FileInfo(u64 name_offset, u64 offset, u64 filesize)
-      : m_NameOffset(name_offset), m_Offset(offset), m_FileSize(filesize)
+  friend class const_iterator;
+
+public:
+  class const_iterator final
   {
-  }
+  public:
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = const FileInfo;
+    using difference_type = std::ptrdiff_t;
+    using pointer = value_type*;
+    using reference = value_type&;
+
+    const_iterator() : m_file_info(nullptr) {}
+    const_iterator(std::unique_ptr<FileInfo> file_info) : m_file_info(std::move(file_info)) {}
+    const_iterator(const const_iterator& it) : m_file_info(it.m_file_info->clone()) {}
+    const_iterator(const_iterator&& it) : m_file_info(std::move(it.m_file_info)) {}
+    ~const_iterator() = default;
+    const_iterator& operator=(const const_iterator& it)
+    {
+      m_file_info = it.m_file_info ? it.m_file_info->clone() : nullptr;
+      return *this;
+    }
+    const_iterator& operator=(const_iterator&& it)
+    {
+      m_file_info = std::move(it.m_file_info);
+      return *this;
+    }
+    const_iterator& operator++()
+    {
+      ++*m_file_info;
+      return *this;
+    }
+    const_iterator operator++(int)
+    {
+      const_iterator old = *this;
+      ++*m_file_info;
+      return old;
+    }
+    bool operator==(const const_iterator& it) const
+    {
+      return m_file_info ? (it.m_file_info && *m_file_info == *it.m_file_info) : (!it.m_file_info);
+    }
+    bool operator!=(const const_iterator& it) const { return !operator==(it); }
+    // Incrementing or destroying an iterator will invalidate its returned references and
+    // pointers, but will not invalidate copies of the iterator or file info object.
+    const FileInfo& operator*() const { return *m_file_info.get(); }
+    const FileInfo* operator->() const { return m_file_info.get(); }
+  private:
+    std::unique_ptr<FileInfo> m_file_info;
+  };
+
+  virtual ~FileInfo();
+
+  bool operator==(const FileInfo& other) const { return GetAddress() == other.GetAddress(); }
+  bool operator!=(const FileInfo& other) const { return !operator==(other); }
+  virtual std::unique_ptr<FileInfo> clone() const = 0;
+  virtual const_iterator cbegin() const { return begin(); }
+  virtual const_iterator cend() const { return end(); }
+  virtual const_iterator begin() const = 0;
+  virtual const_iterator end() const = 0;
+
+  // The offset of a file on the disc (inside the partition, if there is one).
+  // Not guaranteed to return a meaningful value for directories.
+  virtual u64 GetOffset() const = 0;
+  // The size of a file.
+  // Not guaranteed to return a meaningful value for directories.
+  virtual u32 GetSize() const = 0;
+  virtual bool IsDirectory() const = 0;
+  // The number of files and directories in a directory, including those in subdirectories.
+  // Not guaranteed to return a meaningful value for files.
+  virtual u32 GetTotalChildren() const = 0;
+  virtual std::string GetName() const = 0;
+  // GetPath will find the parents of the current object and call GetName on them,
+  // so it's slower than other functions. If you're traversing through folders
+  // to get a file and its path, building the path while traversing is faster.
+  virtual std::string GetPath() const = 0;
 
-  FileInfo(FileInfo const&) = default;
-  FileInfo() = default;
+protected:
+  // Only used for comparisons with other file info objects
+  virtual uintptr_t GetAddress() const = 0;
+
+  // Called by iterators
+  virtual FileInfo& operator++() = 0;
 };
 
 class FileSystem
 {
 public:
-  FileSystem(const Volume* _rVolume, const Partition& partition);
-
+  FileSystem(const Volume* volume, const Partition& partition);
   virtual ~FileSystem();
+
+  // If IsValid is false, GetRoot must not be called. CreateFileSystem
+  // takes care of this automatically, so other code is recommended to use it.
   virtual bool IsValid() const = 0;
-  virtual const std::vector<FileInfo>& GetFileList() = 0;
-  virtual u64 GetFileSize(const std::string& _rFullPath) = 0;
-  virtual u64 ReadFile(const std::string& _rFullPath, u8* _pBuffer, u64 _MaxBufferSize,
-                       u64 _OffsetInFile = 0) = 0;
-  virtual bool ExportFile(const std::string& _rFullPath, const std::string& _rExportFilename) = 0;
-  virtual bool ExportApploader(const std::string& _rExportFolder) const = 0;
-  virtual bool ExportDOL(const std::string& _rExportFolder) const = 0;
-  virtual std::string GetFileName(u64 _Address) = 0;
+  // The object returned by GetRoot and all objects created from it
+  // are only valid for as long as the file system object is valid.
+  virtual const FileInfo& GetRoot() const = 0;
+  // Returns nullptr if not found
+  virtual std::unique_ptr<FileInfo> FindFileInfo(const std::string& path) const = 0;
+  // Returns nullptr if not found
+  virtual std::unique_ptr<FileInfo> FindFileInfo(u64 disc_offset) const = 0;
+
+  virtual u64 ReadFile(const FileInfo* file_info, u8* buffer, u64 max_buffer_size,
+                       u64 offset_in_file = 0) const = 0;
+  virtual bool ExportFile(const FileInfo* file_info, const std::string& export_filename) const = 0;
+  virtual bool ExportApploader(const std::string& export_folder) const = 0;
+  virtual bool ExportDOL(const std::string& export_folder) const = 0;
   virtual std::optional<u64> GetBootDOLOffset() const = 0;
   virtual std::optional<u32> GetBootDOLSize(u64 dol_offset) const = 0;
 
   virtual const Partition GetPartition() const { return m_partition; }
 protected:
-  const Volume* const m_rVolume;
+  const Volume* const m_volume;
   const Partition m_partition;
 };
 
+// Returns nullptr if a valid file system could not be created
 std::unique_ptr<FileSystem> CreateFileSystem(const Volume* volume, const Partition& partition);
 
 }  // namespace
diff --git a/Source/Core/DiscIO/VolumeGC.cpp b/Source/Core/DiscIO/VolumeGC.cpp
index 39bc029ec2..af4178682f 100644
--- a/Source/Core/DiscIO/VolumeGC.cpp
+++ b/Source/Core/DiscIO/VolumeGC.cpp
@@ -177,7 +177,11 @@ void VolumeGC::LoadBannerFile() const
   if (!file_system)
     return;
 
-  size_t file_size = static_cast<size_t>(file_system->GetFileSize("opening.bnr"));
+  std::unique_ptr<FileInfo> file_info = file_system->FindFileInfo("opening.bnr");
+  if (!file_info)
+    return;
+
+  size_t file_size = static_cast<size_t>(file_info->GetSize());
   constexpr int BNR1_MAGIC = 0x31524e42;
   constexpr int BNR2_MAGIC = 0x32524e42;
   if (file_size != BNR1_SIZE && file_size != BNR2_SIZE)
@@ -186,7 +190,12 @@ void VolumeGC::LoadBannerFile() const
     return;
   }
 
-  file_system->ReadFile("opening.bnr", reinterpret_cast<u8*>(&banner_file), file_size);
+  if (file_size !=
+      file_system->ReadFile(file_info.get(), reinterpret_cast<u8*>(&banner_file), file_size))
+  {
+    WARN_LOG(DISCIO, "Could not read opening.bnr.");
+    return;
+  }
 
   bool is_bnr1;
   if (banner_file.id == BNR1_MAGIC && file_size == BNR1_SIZE)
diff --git a/Source/Core/DiscIO/VolumeWii.cpp b/Source/Core/DiscIO/VolumeWii.cpp
index ceb1fa5788..b8215527a6 100644
--- a/Source/Core/DiscIO/VolumeWii.cpp
+++ b/Source/Core/DiscIO/VolumeWii.cpp
@@ -274,8 +274,9 @@ std::map<Language, std::string> VolumeWii::GetLongNames() const
     return {};
 
   std::vector<u8> opening_bnr(NAMES_TOTAL_BYTES);
-  size_t size = file_system->ReadFile("opening.bnr", opening_bnr.data(), opening_bnr.size(), 0x5C);
-  opening_bnr.resize(size);
+  std::unique_ptr<FileInfo> file_info = file_system->FindFileInfo("opening.bnr");
+  opening_bnr.resize(
+      file_system->ReadFile(file_info.get(), opening_bnr.data(), opening_bnr.size(), 0x5C));
   return ReadWiiNames(opening_bnr);
 }