Reduce kmalloc() traffic in directory iteration.

Pass the file name in a stack-allocated buffer instead of using an AK::String
when iterating directories. This dramatically reduces the amount of cycles
spent traversing the filesystem.

10 files changed, 60 insertions, 40 deletions

diff --git a/AK/BufferStream.h b/AK/BufferStream.h
index 379fcb5792..6d83e73b58 100644
--- a/AK/BufferStream.h
+++ b/AK/BufferStream.h
@@ -30,6 +30,13 @@ public:
         m_buffer[m_offset++] = (byte)(value >> 24) & 0xffu;
     }
 
+    void operator<<(const char* str)
+    {
+        size_t len = strlen(str);
+        for (unsigned i = 0; i < len; ++i)
+            m_buffer[m_offset++] = str[i];
+    }
+
     void operator<<(const String& value)
     {
         for (unsigned i = 0; i < value.length(); ++i)
diff --git a/Kernel/i386.h b/Kernel/i386.h
index b4c64b6247..5ab93f3653 100644
--- a/Kernel/i386.h
+++ b/Kernel/i386.h
@@ -239,8 +239,7 @@ public:
         dword end_msw;
         read_tsc(end_lsw, end_msw);
         if (m_start_msw != end_msw) {
-            dbgprintf("differing msw's\n");
-            asm volatile("cli;hlt");
+            dbgprintf("stopwatch: differing msw, no result for %s\n", m_name);
         }
         dword diff = end_lsw - m_start_lsw;
         dbgprintf("Stopwatch(%s): %u ticks\n", m_name, diff);
diff --git a/Kernel/init.cpp b/Kernel/init.cpp
index 1419d59ad5..4fbb2b2881 100644
--- a/Kernel/init.cpp
+++ b/Kernel/init.cpp
@@ -26,7 +26,6 @@
 #include "VirtualConsole.h"
 #include "Scheduler.h"
 
-#define TEST_VFS
 #define KSYMS
 #define SPAWN_MULTIPLE_SHELLS
 //#define STRESS_TEST_SPAWNING
@@ -103,7 +102,8 @@ static void loadKsyms(const ByteBuffer& buffer)
         // FIXME: The Strings here should be eternally allocated too.
         ksyms().append({ address, String(startOfName, bufptr - startOfName) });
 
-        kprintf("\033[u\033[s%u/%u", ksyms().size(), ksym_count);
+        if ((ksyms().size() % 10) == 0 || ksym_count == ksyms().size())
+            kprintf("\033[u\033[s%u/%u", ksyms().size(), ksym_count);
         ++bufptr;
     }
     kprintf("\n");
@@ -174,7 +174,6 @@ static void init_stage2()
 {
     Syscall::initialize();
 
-#ifdef TEST_VFS
     auto vfs = make<VirtualFileSystem>();
 
     auto dev_zero = make<ZeroDevice>();
@@ -218,8 +217,6 @@ static void init_stage2()
 
     vfs->mount(ProcFileSystem::the(), "/proc");
 
-#endif
-
 #ifdef TEST_ELF_LOADER
     {
         auto testExecutable = vfs->open("/bin/id");
diff --git a/Userland/sh.cpp b/Userland/sh.cpp
index 3986f402fc..85cfed3091 100644
--- a/Userland/sh.cpp
+++ b/Userland/sh.cpp
@@ -16,12 +16,13 @@ struct GlobalState {
     char ttyname[32];
     char hostname[32];
     pid_t sid;
+    uid_t uid;
 };
 static GlobalState* g;
 
 static void prompt()
 {
-    if (getuid() == 0)
+    if (g->uid == 0)
         printf("# ");
     else
         printf("\033[31;1m%s\033[0m@\033[37;1m%s\033[0m:\033[32;1m%s\033[0m$> ", g->username.characters(), g->hostname, g->cwd.characters());
@@ -350,6 +351,7 @@ static void greeting()
 int main(int, char**)
 {
     g = new GlobalState;
+    g->uid = getuid();
     g->sid = setsid();
     tcsetpgrp(0, getpgrp());
 
diff --git a/VirtualFileSystem/Ext2FileSystem.cpp b/VirtualFileSystem/Ext2FileSystem.cpp
index 1a9dfc8622..36053d54d5 100644
--- a/VirtualFileSystem/Ext2FileSystem.cpp
+++ b/VirtualFileSystem/Ext2FileSystem.cpp
@@ -211,7 +211,7 @@ auto Ext2FileSystem::lookupExt2Inode(unsigned inode) const -> CachedExt2Inode
 #endif
 
     LOCKER(m_inodeCacheLock);
-    if (m_inodeCache.size() >= 64)
+    if (m_inodeCache.size() >= 128)
         m_inodeCache.removeOneRandomly();
     auto cachedInode = adopt(*new CachedExt2InodeImpl(OwnPtr<ext2_inode>(e2inode)));
     m_inodeCache.set(inode, cachedInode.copyRef());
@@ -261,14 +261,14 @@ Vector<unsigned> Ext2FileSystem::blockListForInode(const ext2_inode& e2inode) co
 
     unsigned directCount = min(blockCount, (unsigned)EXT2_NDIR_BLOCKS);
     for (unsigned i = 0; i < directCount; ++i) {
-        list.append(e2inode.i_block[i]);
+        list.unchecked_append(e2inode.i_block[i]);
         --blocksRemaining;
     }
 
     if (!blocksRemaining)
         return list;
 
-    auto processBlockArray = [&] (unsigned arrayBlockIndex, Function<void(unsigned)> callback) {
+    auto processBlockArray = [&] (unsigned arrayBlockIndex, auto&& callback) {
         auto arrayBlock = readBlock(arrayBlockIndex);
         ASSERT(arrayBlock);
         auto* array = reinterpret_cast<const __u32*>(arrayBlock.pointer());
@@ -284,7 +284,7 @@ Vector<unsigned> Ext2FileSystem::blockListForInode(const ext2_inode& e2inode) co
     };
 
     processBlockArray(e2inode.i_block[EXT2_IND_BLOCK], [&] (unsigned entry) {
-        list.append(entry);
+        list.unchecked_append(entry);
     });
 
     if (!blocksRemaining)
@@ -292,7 +292,7 @@ Vector<unsigned> Ext2FileSystem::blockListForInode(const ext2_inode& e2inode) co
 
     processBlockArray(e2inode.i_block[EXT2_DIND_BLOCK], [&] (unsigned entry) {
         processBlockArray(entry, [&] (unsigned entry) {
-            list.append(entry);
+            list.unchecked_append(entry);
         });
     });
 
@@ -302,7 +302,7 @@ Vector<unsigned> Ext2FileSystem::blockListForInode(const ext2_inode& e2inode) co
     processBlockArray(e2inode.i_block[EXT2_TIND_BLOCK], [&] (unsigned entry) {
         processBlockArray(entry, [&] (unsigned entry) {
             processBlockArray(entry, [&] (unsigned entry) {
-                list.append(entry);
+                list.unchecked_append(entry);
             });
         });
     });
@@ -434,16 +434,12 @@ bool Ext2FileSystem::enumerateDirectoryInode(InodeIdentifier inode, Function<boo
     ASSERT(buffer);
     auto* entry = reinterpret_cast<ext2_dir_entry_2*>(buffer.pointer());
 
-    char namebuf[EXT2_NAME_LEN + 1];
-
     while (entry < buffer.endPointer()) {
         if (entry->inode != 0) {
-            memcpy(namebuf, entry->name, entry->name_len);
-            namebuf[entry->name_len] = 0;
 #ifdef EXT2_DEBUG
             kprintf("inode: %u, name_len: %u, rec_len: %u, file_type: %u, name: %s\n", entry->inode, entry->name_len, entry->rec_len, entry->file_type, namebuf);
 #endif
-            if (!callback({ namebuf, { id(), entry->inode }, entry->file_type }))
+            if (!callback({ entry->name, entry->name_len, { id(), entry->inode }, entry->file_type }))
                 break;
         }
         entry = (ext2_dir_entry_2*)((char*)entry + entry->rec_len);
@@ -464,7 +460,7 @@ bool Ext2FileSystem::addInodeToDirectory(unsigned directoryInode, unsigned inode
     Vector<DirectoryEntry> entries;
     bool nameAlreadyExists = false;
     enumerateDirectoryInode({ id(), directoryInode }, [&] (const DirectoryEntry& entry) {
-        if (entry.name == name) {
+        if (!strcmp(entry.name, name.characters())) {
             nameAlreadyExists = true;
             return false;
         }
@@ -476,8 +472,7 @@ bool Ext2FileSystem::addInodeToDirectory(unsigned directoryInode, unsigned inode
         return false;
     }
 
-    entries.append({ name, { id(), inode }, fileType });
-
+    entries.append({ name.characters(), name.length(), { id(), inode }, fileType });
     return writeDirectoryInode(directoryInode, move(entries));
 }
 
@@ -487,8 +482,8 @@ bool Ext2FileSystem::writeDirectoryInode(unsigned directoryInode, Vector<Directo
 
     unsigned directorySize = 0;
     for (auto& entry : entries) {
-        kprintf("  - %08u %s\n", entry.inode.index(), entry.name.characters());
-        directorySize += EXT2_DIR_REC_LEN(entry.name.length());
+        kprintf("  - %08u %s\n", entry.inode.index(), entry.name);
+        directorySize += EXT2_DIR_REC_LEN(entry.name_length);
     }
 
     unsigned blocksNeeded = ceilDiv(directorySize, blockSize());
@@ -502,23 +497,23 @@ bool Ext2FileSystem::writeDirectoryInode(unsigned directoryInode, Vector<Directo
     for (unsigned i = 0; i < entries.size(); ++i) {
         auto& entry = entries[i];
 
-        unsigned recordLength = EXT2_DIR_REC_LEN(entry.name.length());
+        unsigned recordLength = EXT2_DIR_REC_LEN(entry.name_length);
         if (i == entries.size() - 1)
             recordLength += occupiedSize - directorySize;
 
         kprintf("* inode: %u", entry.inode.index());
-        kprintf(", name_len: %u", word(entry.name.length()));
+        kprintf(", name_len: %u", word(entry.name_length));
         kprintf(", rec_len: %u", word(recordLength));
         kprintf(", file_type: %u", byte(entry.fileType));
-        kprintf(", name: %s\n", entry.name.characters());
+        kprintf(", name: %s\n", entry.name);
 
         stream << dword(entry.inode.index());
         stream << word(recordLength);
-        stream << byte(entry.name.length());
+        stream << byte(entry.name_length);
         stream << byte(entry.fileType);
         stream << entry.name;
 
-        unsigned padding = recordLength - entry.name.length() - 8;
+        unsigned padding = recordLength - entry.name_length - 8;
         kprintf("  *** pad %u bytes\n", padding);
         for (unsigned j = 0; j < padding; ++j) {
             stream << byte(0);
diff --git a/VirtualFileSystem/FileDescriptor.cpp b/VirtualFileSystem/FileDescriptor.cpp
index 566ae61561..6a3898aeac 100644
--- a/VirtualFileSystem/FileDescriptor.cpp
+++ b/VirtualFileSystem/FileDescriptor.cpp
@@ -218,7 +218,7 @@ ssize_t FileDescriptor::get_dir_entries(byte* buffer, Unix::size_t size)
     m_vnode->vfs()->enumerateDirectoryInode(m_vnode->inode, [&stream] (auto& entry) {
         stream << (dword)entry.inode.index();
         stream << (byte)entry.fileType;
-        stream << (dword)entry.name.length();
+        stream << (dword)entry.name_length;
         stream << entry.name;
         return true;
     });
diff --git a/VirtualFileSystem/FileSystem.cpp b/VirtualFileSystem/FileSystem.cpp
index 84bb76b8ac..4747e1e25c 100644
--- a/VirtualFileSystem/FileSystem.cpp
+++ b/VirtualFileSystem/FileSystem.cpp
@@ -41,7 +41,7 @@ InodeIdentifier FileSystem::childOfDirectoryInodeWithName(InodeIdentifier inode,
 {
     InodeIdentifier foundInode;
     enumerateDirectoryInode(inode, [&] (const DirectoryEntry& entry) {
-        if (entry.name == name) {
+        if (!strcmp(entry.name, name.characters())) {
             foundInode = entry.inode;
             return false;
         }
@@ -101,3 +101,20 @@ ByteBuffer FileSystem::readEntireInode(InodeIdentifier inode, FileDescriptor* ha
     return contents;
 }
 
+FileSystem::DirectoryEntry::DirectoryEntry(const char* n, InodeIdentifier i, byte ft)
+    : name_length(strlen(name))
+    , inode(i)
+    , fileType(ft)
+{
+    memcpy(name, n, name_length);
+    name[name_length] = '\0';
+}
+
+FileSystem::DirectoryEntry::DirectoryEntry(const char* n, Unix::size_t nl, InodeIdentifier i, byte ft)
+    : name_length(nl)
+    , inode(i)
+    , fileType(ft)
+{
+    memcpy(name, n, nl);
+    name[nl] = '\0';
+}
diff --git a/VirtualFileSystem/FileSystem.h b/VirtualFileSystem/FileSystem.h
index 8d5313eb1e..6c203b93e7 100644
--- a/VirtualFileSystem/FileSystem.h
+++ b/VirtualFileSystem/FileSystem.h
@@ -35,7 +35,10 @@ public:
     virtual Unix::ssize_t readInodeBytes(InodeIdentifier, Unix::off_t offset, Unix::size_t count, byte* buffer, FileDescriptor*) const = 0;
 
     struct DirectoryEntry {
-        String name;
+        DirectoryEntry(const char* name, InodeIdentifier, byte fileType);
+        DirectoryEntry(const char* name, Unix::size_t name_length, InodeIdentifier, byte fileType);
+        char name[256];
+        Unix::size_t name_length { 0 };
         InodeIdentifier inode;
         byte fileType { 0 };
     };
diff --git a/VirtualFileSystem/SyntheticFileSystem.cpp b/VirtualFileSystem/SyntheticFileSystem.cpp
index dd1c0c0de3..676aff6b80 100644
--- a/VirtualFileSystem/SyntheticFileSystem.cpp
+++ b/VirtualFileSystem/SyntheticFileSystem.cpp
@@ -147,11 +147,11 @@ bool SyntheticFileSystem::enumerateDirectoryInode(InodeIdentifier inode, Functio
     if (!synInode.metadata.isDirectory())
         return false;
 
-    callback({ ".", synInode.metadata.inode });
-    callback({ "..", synInode.parent });
+    callback({ ".", 1, synInode.metadata.inode, 2 });
+    callback({ "..", 2, synInode.parent, 2 });
 
     for (auto& child : synInode.children)
-        callback({ child->name, child->metadata.inode });
+        callback({ child->name.characters(), child->name.length(), child->metadata.inode, child->metadata.isDirectory() ? (byte)2 : (byte)1 });
     return true;
 }
 
diff --git a/VirtualFileSystem/VirtualFileSystem.cpp b/VirtualFileSystem/VirtualFileSystem.cpp
index 358cc39cbf..d6f9301cad 100644
--- a/VirtualFileSystem/VirtualFileSystem.cpp
+++ b/VirtualFileSystem/VirtualFileSystem.cpp
@@ -250,12 +250,12 @@ void VirtualFileSystem::enumerateDirectoryInode(InodeIdentifier directoryInode,
         else
             resolvedInode = entry.inode;
 
-        if (directoryInode.isRootInode() && !isRoot(directoryInode) && entry.name == "..") {
+        if (directoryInode.isRootInode() && !isRoot(directoryInode) && !strcmp(entry.name, "..")) {
             auto mount = findMountForGuest(entry.inode);
             ASSERT(mount);
             resolvedInode = mount->host();
         }
-        callback({ entry.name, resolvedInode });
+        callback(FileSystem::DirectoryEntry(entry.name, entry.name_length, resolvedInode, entry.fileType));
         return true;
     });
 }
@@ -348,7 +348,7 @@ void VirtualFileSystem::listDirectory(const String& path, InodeIdentifier base)
 
         kprintf("%s%s%s",
             nameColorBegin,
-            entry.name.characters(),
+            entry.name,
             nameColorEnd);
 
         if (metadata.isDirectory()) {
@@ -376,11 +376,11 @@ void VirtualFileSystem::listDirectoryRecursively(const String& path, InodeIdenti
         if (metadata.isDirectory()) {
             if (entry.name != "." && entry.name != "..") {
                 char buf[4096];
-                ksprintf(buf, "%s/%s", path.characters(), entry.name.characters());
+                ksprintf(buf, "%s/%s", path.characters(), entry.name);
                 listDirectoryRecursively(buf, base);
             }
         } else {
-            kprintf("%s/%s\n", path.characters(), entry.name.characters());
+            kprintf("%s/%s\n", path.characters(), entry.name);
         }
         return true;
     });