Lots of hacking to make a very simple "ls" utility.

I added a dead-simple malloc that only allows allocations < 4096 bytes.
It just forwards the request to mmap() every time.

I also added simplified versions of opendir() and readdir().

19 files changed, 277 insertions, 67 deletions

diff --git a/AK/BufferStream.h b/AK/BufferStream.h
new file mode 100644
index 0000000000..379fcb5792
--- /dev/null
+++ b/AK/BufferStream.h
@@ -0,0 +1,54 @@
+#pragma once
+
+#include "ByteBuffer.h"
+
+namespace AK {
+
+class BufferStream {
+public:
+    explicit BufferStream(ByteBuffer& buffer)
+        : m_buffer(buffer)
+    {
+    }
+
+    void operator<<(byte value)
+    {
+        m_buffer[m_offset++] = value & 0xffu;
+    }
+
+    void operator<<(word value)
+    {
+        m_buffer[m_offset++] = value & 0xffu;
+        m_buffer[m_offset++] = (byte)(value >> 8) & 0xffu;
+    }
+
+    void operator<<(dword value)
+    {
+        m_buffer[m_offset++] = value & 0xffu;
+        m_buffer[m_offset++] = (byte)(value >> 8) & 0xffu;
+        m_buffer[m_offset++] = (byte)(value >> 16) & 0xffu;
+        m_buffer[m_offset++] = (byte)(value >> 24) & 0xffu;
+    }
+
+    void operator<<(const String& value)
+    {
+        for (unsigned i = 0; i < value.length(); ++i)
+            m_buffer[m_offset++] = value[i];
+    }
+
+    void fillToEnd(byte ch)
+    {
+        while (m_offset < m_buffer.size())
+            m_buffer[m_offset++] = ch;
+    }
+
+    Unix::size_t offset() const { return m_offset; }
+
+private:
+    ByteBuffer& m_buffer;
+    Unix::size_t m_offset { 0 };
+};
+
+}
+
+using AK::BufferStream;
diff --git a/Kernel/ProcFileSystem.cpp b/Kernel/ProcFileSystem.cpp
index 57d7493fd1..039d8c897d 100644
--- a/Kernel/ProcFileSystem.cpp
+++ b/Kernel/ProcFileSystem.cpp
@@ -21,17 +21,18 @@ bool ProcFileSystem::initialize()
         InterruptDisabler disabler;
         auto tasks = Task::allTasks();
         char* buffer;
-        auto stringImpl = StringImpl::createUninitialized(tasks.size() * 128, buffer);
+        auto stringImpl = StringImpl::createUninitialized(tasks.size() * 256, buffer);
         memset(buffer, 0, stringImpl->length());
         char* ptr = buffer;
-        ptr += ksprintf(ptr, "PID    OWNER      STATE  NSCHED  NAME\n");
+        ptr += ksprintf(ptr, "PID    OWNER      STATE  NSCHED  FDS    NAME\n");
         for (auto* task : tasks) {
-            ptr += ksprintf(ptr, "%w   %w:%w  %b     %w    %s\n",
+            ptr += ksprintf(ptr, "%w   %w:%w  %b     %w    %w   %s\n",
                 task->pid(),
                 task->uid(),
                 task->gid(),
                 task->state(),
                 task->timesScheduled(),
+                task->fileHandleCount(),
                 task->name().characters());
         }
         ptr += ksprintf(ptr, "kmalloc: alloc: %u / free: %u\n", sum_alloc, sum_free);
diff --git a/Kernel/Syscall.cpp b/Kernel/Syscall.cpp
index 1e70f9a510..4be04cbfac 100644
--- a/Kernel/Syscall.cpp
+++ b/Kernel/Syscall.cpp
@@ -66,6 +66,8 @@ DWORD handle(DWORD function, DWORD arg1, DWORD arg2, DWORD arg3)
         break;
     case Syscall::Spawn:
         return current->sys$spawn((const char*)arg1);
+    case Syscall::GetDirEntries:
+        return current->sys$get_dir_entries((int)arg1, (void*)arg2, (size_t)arg3);
     case Syscall::PosixOpen:
         //kprintf("syscall: open('%s', %u)\n", arg1, arg2);
         return current->sys$open((const char*)arg1, (size_t)arg2);
diff --git a/Kernel/Syscall.h b/Kernel/Syscall.h
index 22f6fb3812..70b3f12983 100644
--- a/Kernel/Syscall.h
+++ b/Kernel/Syscall.h
@@ -26,6 +26,7 @@ enum Function {
     PosixWaitpid = 0x1994,
     PosixMmap = 0x1995,
     PosixMunmap = 0x1996,
+    GetDirEntries = 0x1997,
 };
 
 void initialize();
diff --git a/Kernel/Task.cpp b/Kernel/Task.cpp
index 331be38ffb..fe185cc154 100644
--- a/Kernel/Task.cpp
+++ b/Kernel/Task.cpp
@@ -230,6 +230,10 @@ Task::Task(String&& name, uid_t uid, gid_t gid)
     , m_state(Runnable)
     , m_ring(Ring3)
 {
+    m_fileHandles.append(nullptr);
+    m_fileHandles.append(nullptr);
+    m_fileHandles.append(nullptr);
+
     m_nextRegion = LinearAddress(0x600000);
 
     memset(&m_tss, 0, sizeof(m_tss));
@@ -280,6 +284,10 @@ Task::Task(void (*e)(), const char* n, IPC::Handle h, RingLevel ring)
     , m_state(Runnable)
     , m_ring(ring)
 {
+    m_fileHandles.append(nullptr);
+    m_fileHandles.append(nullptr);
+    m_fileHandles.append(nullptr);
+
     m_nextRegion = LinearAddress(0x600000);
 
     Region* codeRegion = nullptr;
@@ -643,6 +651,14 @@ FileHandle* Task::fileHandleIfExists(int fd)
     return nullptr;
 }
 
+ssize_t Task::sys$get_dir_entries(int fd, void* buffer, size_t size)
+{
+    auto* handle = fileHandleIfExists(fd);
+    if (!handle)
+        return -1;
+    return handle->get_dir_entries((byte*)buffer, size);
+}
+
 int Task::sys$seek(int fd, int offset)
 {
     auto* handle = fileHandleIfExists(fd);
diff --git a/Kernel/Task.h b/Kernel/Task.h
index f79ccc267d..8ff28a00ed 100644
--- a/Kernel/Task.h
+++ b/Kernel/Task.h
@@ -101,6 +101,7 @@ public:
     pid_t sys$waitpid(pid_t);
     void* sys$mmap(void*, size_t size);
     int sys$munmap(void*, size_t size);
+    int sys$get_dir_entries(int fd, void*, size_t);
 
     struct
     {
@@ -122,6 +123,8 @@ public:
 
     pid_t waitee() const { return m_waitee; }
 
+    size_t fileHandleCount() const { return m_fileHandles.size(); }
+
 private:
     friend class MemoryManager;
 
diff --git a/Kernel/_fs_contents b/Kernel/_fs_contents
index 315825570e..25f45186bf 100644
--- a/Kernel/_fs_contents
+++ b/Kernel/_fs_contents
diff --git a/LibC/Makefile b/LibC/Makefile
index ed1e157531..3f28724fd9 100644
--- a/LibC/Makefile
+++ b/LibC/Makefile
@@ -4,6 +4,8 @@ OBJS = \
        string.o \
        process.o \
        mman.o \
+       dirent.o \
+       stdlib.o \
        entry.o
 
 LIBRARY = LibC.a
diff --git a/LibC/dirent.cpp b/LibC/dirent.cpp
new file mode 100644
index 0000000000..caea450c5b
--- /dev/null
+++ b/LibC/dirent.cpp
@@ -0,0 +1,67 @@
+#include "dirent.h"
+#include "unistd.h"
+#include "stdlib.h"
+#include <Kernel/Syscall.h>
+#include "stdio.h"
+
+extern "C" {
+
+DIR* opendir(const char* name)
+{
+    // FIXME: Should fail if it's not a directory!
+    int fd = open(name);
+    if (fd == -1)
+        return nullptr;
+    DIR* dirp = (DIR*)malloc(sizeof(dirp));
+    dirp->fd = fd;
+    dirp->buffer = nullptr;
+    dirp->buffer_size = 0;
+    dirp->nextptr = nullptr;
+    return dirp;
+}
+
+struct sys_dirent {
+    ino_t ino;
+    byte file_type;
+    size_t namelen;
+    char name[];
+    size_t total_size()
+    {
+        return sizeof(ino_t) + sizeof(byte) + sizeof(size_t) + sizeof(char) * namelen;
+    }
+} __attribute__ ((packed));
+
+dirent* readdir(DIR* dirp)
+{
+    if (!dirp)
+        return nullptr;
+    if (dirp->fd == -1)
+        return nullptr;
+
+    if (!dirp->buffer) {
+        // FIXME: Figure out how much to actually allocate.
+        dirp->buffer = (char*)malloc(4096);
+        ssize_t nread = Syscall::invoke(Syscall::GetDirEntries, (dword)dirp->fd, (dword)dirp->buffer, 4096);
+        dirp->buffer_size = nread;
+        dirp->nextptr = dirp->buffer;
+    }
+
+    if (dirp->nextptr > (dirp->buffer + dirp->buffer_size))
+        return nullptr;
+
+    auto* sys_ent = (sys_dirent*)dirp->nextptr;
+    dirp->cur_ent.d_ino = sys_ent->ino;
+    dirp->cur_ent.d_type = sys_ent->file_type;
+    dirp->cur_ent.d_off = 0;
+    dirp->cur_ent.d_reclen = sys_ent->total_size();
+    for (size_t i = 0; i < sys_ent->namelen; ++i)
+        dirp->cur_ent.d_name[i] = sys_ent->name[i];
+    // FIXME: I think this null termination behavior is not supposed to be here.
+    dirp->cur_ent.d_name[sys_ent->namelen] = '\0';
+
+    dirp->nextptr += sys_ent->total_size();
+    return &dirp->cur_ent;
+}
+
+}
+
diff --git a/LibC/dirent.h b/LibC/dirent.h
new file mode 100644
index 0000000000..be069d8133
--- /dev/null
+++ b/LibC/dirent.h
@@ -0,0 +1,27 @@
+#pragma once
+
+#include "types.h"
+
+extern "C" {
+
+struct dirent {
+    ino_t d_ino;
+    off_t d_off;
+    unsigned short d_reclen;
+    unsigned char d_type;
+    char d_name[256];
+};
+
+struct DIR {
+    int fd;
+    dirent cur_ent;
+    char* buffer;
+    size_t buffer_size;
+    char* nextptr;
+};
+
+DIR* opendir(const char* name);
+dirent* readdir(DIR* dirp);
+
+}
+
diff --git a/LibC/stdlib.cpp b/LibC/stdlib.cpp
new file mode 100644
index 0000000000..7d0f1b5e8f
--- /dev/null
+++ b/LibC/stdlib.cpp
@@ -0,0 +1,24 @@
+#include "stdlib.h"
+#include "mman.h"
+
+extern "C" {
+
+void* malloc(size_t size)
+{
+    if (size > 4096) {
+        volatile char* crashme = (char*)0xc007d00d;
+        *crashme = 0;
+    }
+    void* ptr = mmap(nullptr, 4096);
+    return ptr;
+}
+
+void free(void* ptr)
+{
+    if (!ptr)
+        return;
+    munmap(ptr, 4096);
+}
+
+}
+
diff --git a/LibC/stdlib.h b/LibC/stdlib.h
new file mode 100644
index 0000000000..55cd47c9f7
--- /dev/null
+++ b/LibC/stdlib.h
@@ -0,0 +1,11 @@
+#pragma once
+
+#include "types.h"
+
+extern "C" {
+
+void* malloc(size_t);
+void free(void*);
+
+}
+
diff --git a/LibC/types.h b/LibC/types.h
index fc990e79f7..cedc52280c 100644
--- a/LibC/types.h
+++ b/LibC/types.h
@@ -17,5 +17,8 @@ typedef dword pid_t;
 typedef dword size_t;
 typedef signed_dword ssize_t;
 
+typedef dword ino_t;
+typedef signed_dword off_t;
+
 }
 
diff --git a/Userland/ls.cpp b/Userland/ls.cpp
index f6a90568b9..dfaa0d4eb2 100644
--- a/Userland/ls.cpp
+++ b/Userland/ls.cpp
@@ -1,21 +1,17 @@
 #include <LibC/stdio.h>
 #include <LibC/unistd.h>
-#include <LibC/mman.h>
+#include <LibC/dirent.h>
 
 int main(int c, char** v)
 {
-    int fd = open("/");
-    if (fd == -1) {
-        printf("failed to open / :(\n");
+    DIR* dirp = opendir("/");
+    if (!dirp) {
+        printf("opendir failed :(\n");
         return 1;
     }
+    while (auto* de = readdir(dirp)) {
+        printf("%s\n", de->d_name);
 
-    byte* memory = (byte*)mmap(nullptr, 16384);
-    printf("%p\n", memory);
-    memory[0] = 'H';
-    memory[1] = 'i';
-    memory[2] = '!';
-    memory[3] = '\0';
-    printf("%p : %s\n", memory, memory);
+    }
     return 0;
 }
diff --git a/VirtualFileSystem/Ext2FileSystem.cpp b/VirtualFileSystem/Ext2FileSystem.cpp
index 8e0dc9b87b..53fa6a3b66 100644
--- a/VirtualFileSystem/Ext2FileSystem.cpp
+++ b/VirtualFileSystem/Ext2FileSystem.cpp
@@ -6,6 +6,7 @@
 #include <AK/kmalloc.h>
 #include <AK/ktime.h>
 #include <AK/kstdio.h>
+#include <AK/BufferStream.h>
 #include "sys-errno.h"
 
 //#define EXT2_DEBUG
@@ -431,49 +432,6 @@ bool Ext2FileSystem::addInodeToDirectory(unsigned directoryInode, unsigned inode
     return writeDirectoryInode(directoryInode, move(entries));
 }
 
-class BufferStream {
-public:
-    explicit BufferStream(ByteBuffer& buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    void operator<<(byte value)
-    {
-        m_buffer[m_offset++] = value & 0xffu;
-    }
-
-    void operator<<(word value)
-    {
-        m_buffer[m_offset++] = value & 0xffu;
-        m_buffer[m_offset++] = (byte)(value >> 8) & 0xffu;
-    }
-
-    void operator<<(dword value)
-    {
-        m_buffer[m_offset++] = value & 0xffu;
-        m_buffer[m_offset++] = (byte)(value >> 8) & 0xffu;
-        m_buffer[m_offset++] = (byte)(value >> 16) & 0xffu;
-        m_buffer[m_offset++] = (byte)(value >> 24) & 0xffu;
-    }
-
-    void operator<<(const String& value)
-    {
-        for (unsigned i = 0; i < value.length(); ++i)
-            m_buffer[m_offset++] = value[i];
-    }
-
-    void fillToEnd(byte ch)
-    {
-        while (m_offset < m_buffer.size())
-            m_buffer[m_offset++] = ch;
-    }
-
-private:
-    ByteBuffer& m_buffer;
-    Unix::size_t m_offset { 0 };
-};
-
 bool Ext2FileSystem::writeDirectoryInode(unsigned directoryInode, Vector<DirectoryEntry>&& entries)
 {
     kprintf("[ext2fs] New directory inode %u contents to write:\n", directoryInode);
diff --git a/VirtualFileSystem/FileHandle.cpp b/VirtualFileSystem/FileHandle.cpp
index 113a9a56c1..90c0beade2 100644
--- a/VirtualFileSystem/FileHandle.cpp
+++ b/VirtualFileSystem/FileHandle.cpp
@@ -3,6 +3,7 @@
 #include "CharacterDevice.h"
 #include "sys-errno.h"
 #include "UnixTypes.h"
+#include <AK/BufferStream.h>
 
 FileHandle::FileHandle(RetainPtr<VirtualFileSystem::Node>&& vnode)
     : m_vnode(move(vnode))
@@ -29,7 +30,7 @@ int FileHandle::stat(Unix::stat* buffer)
     if (!m_vnode)
         return -EBADF;
 
-    auto metadata = m_vnode->inode.metadata();
+    auto metadata = m_vnode->metadata();
     if (!metadata.isValid())
         return -EIO;
 
@@ -58,7 +59,7 @@ Unix::off_t FileHandle::seek(Unix::off_t offset, int whence)
 
     // FIXME: The file type should be cached on the vnode.
     //        It's silly that we have to do a full metadata lookup here.
-    auto metadata = m_vnode->inode.metadata();
+    auto metadata = m_vnode->metadata();
     if (!metadata.isValid())
         return -EIO;
 
@@ -120,3 +121,27 @@ ByteBuffer FileHandle::readEntireFile()
     return m_vnode->fileSystem()->readEntireInode(m_vnode->inode);
 }
 
+ssize_t FileHandle::get_dir_entries(byte* buffer, size_t size)
+{
+    Locker locker(VirtualFileSystem::lock());
+
+    auto metadata = m_vnode->metadata();
+    if (!metadata.isValid())
+        return -EIO;
+    if (!metadata.isDirectory())
+        return -ENOTDIR;
+
+    // FIXME: Compute the actual size needed.
+    auto tempBuffer = ByteBuffer::createUninitialized(2048);
+    BufferStream stream(tempBuffer);
+    m_vnode->vfs()->enumerateDirectoryInode(m_vnode->inode, [&stream] (const FileSystem::DirectoryEntry& entry) {
+        stream << (dword)entry.inode.index();
+        stream << (byte)entry.fileType;
+        stream << (dword)entry.name.length();
+        stream << entry.name;
+        return true;
+    });
+
+    memcpy(buffer, tempBuffer.pointer(), stream.offset());
+    return stream.offset();
+}
diff --git a/VirtualFileSystem/FileHandle.h b/VirtualFileSystem/FileHandle.h
index 16956eb87c..f75d88895c 100644
--- a/VirtualFileSystem/FileHandle.h
+++ b/VirtualFileSystem/FileHandle.h
@@ -12,6 +12,8 @@ public:
     Unix::ssize_t read(byte* buffer, Unix::size_t count);
     int stat(Unix::stat*);
 
+    ssize_t get_dir_entries(byte* buffer, Unix::size_t);
+
     ByteBuffer readEntireFile();
 
 #ifdef SERENITY
diff --git a/VirtualFileSystem/VirtualFileSystem.cpp b/VirtualFileSystem/VirtualFileSystem.cpp
index c4c831b9c1..d7880a1b02 100644
--- a/VirtualFileSystem/VirtualFileSystem.cpp
+++ b/VirtualFileSystem/VirtualFileSystem.cpp
@@ -78,6 +78,7 @@ auto VirtualFileSystem::makeNode(InodeIdentifier inode) -> RetainPtr<Node>
     fileSystem->retain();
 
     vnode->inode = inode;
+    vnode->m_cachedMetadata = { };
 
 #ifdef VFS_DEBUG
     kprintf("makeNode: inode=%u, size=%u, mode=%o, uid=%u, gid=%u\n", inode.index(), metadata.size, metadata.mode, metadata.uid, metadata.gid);
@@ -85,6 +86,7 @@ auto VirtualFileSystem::makeNode(InodeIdentifier inode) -> RetainPtr<Node>
 
     m_inode2vnode.set(inode, vnode.ptr());
     vnode->m_characterDevice = characterDevice;
+
     return vnode;
 }
 
@@ -151,7 +153,7 @@ auto VirtualFileSystem::allocateNode() -> RetainPtr<Node>
     auto* node = m_nodeFreeList.takeLast();
     ASSERT(node->retainCount == 0);
     node->retainCount = 1;
-    node->vfs = this;
+    node->m_vfs = this;
     return adopt(*node);
 }
 
@@ -198,8 +200,7 @@ bool VirtualFileSystem::isRoot(InodeIdentifier inode) const
     return inode == m_rootNode->inode;
 }
 
-template<typename F>
-void VirtualFileSystem::enumerateDirectoryInode(InodeIdentifier directoryInode, F func)
+void VirtualFileSystem::enumerateDirectoryInode(InodeIdentifier directoryInode, Function<bool(const FileSystem::DirectoryEntry&)> callback)
 {
     if (!directoryInode.isValid())
         return;
@@ -216,7 +217,7 @@ void VirtualFileSystem::enumerateDirectoryInode(InodeIdentifier directoryInode,
             ASSERT(mount);
             resolvedInode = mount->host();
         }
-        func({ entry.name, resolvedInode });
+        callback({ entry.name, resolvedInode });
         return true;
     });
 }
@@ -340,6 +341,7 @@ void VirtualFileSystem::listDirectoryRecursively(const String& path)
         } else {
             kprintf("%s/%s\n", path.characters(), entry.name.characters());
         }
+        return true;
     });
 }
 
@@ -467,10 +469,17 @@ void VirtualFileSystem::Node::release()
 {
     ASSERT(retainCount);
     if (--retainCount == 0) {
-        vfs->freeNode(this);
+        m_vfs->freeNode(this);
     }
 }
 
+const InodeMetadata& VirtualFileSystem::Node::metadata() const
+{
+    if (!m_cachedMetadata.isValid())
+        m_cachedMetadata = inode.metadata();
+    return m_cachedMetadata;
+}
+
 VirtualFileSystem::Mount::Mount(InodeIdentifier host, RetainPtr<FileSystem>&& guestFileSystem)
     : m_host(host)
     , m_guest(guestFileSystem->rootInode())
diff --git a/VirtualFileSystem/VirtualFileSystem.h b/VirtualFileSystem/VirtualFileSystem.h
index 2fa31b51b9..bafb791d9f 100644
--- a/VirtualFileSystem/VirtualFileSystem.h
+++ b/VirtualFileSystem/VirtualFileSystem.h
@@ -6,12 +6,14 @@
 #include <AK/String.h>
 #include <AK/Vector.h>
 #include <AK/Lock.h>
+#include <AK/Function.h>
 #include "InodeIdentifier.h"
+#include "InodeMetadata.h"
 #include "Limits.h"
+#include "FileSystem.h"
 
 class CharacterDevice;
 class FileHandle;
-class FileSystem;
 
 class VirtualFileSystem {
 public:
@@ -20,6 +22,7 @@ public:
 
     struct Node {
         InodeIdentifier inode;
+        const InodeMetadata& metadata() const;
 
         bool inUse() const { return inode.isValid(); }
 
@@ -32,11 +35,15 @@ public:
         FileSystem* fileSystem() { return inode.fileSystem(); }
         const FileSystem* fileSystem() const { return inode.fileSystem(); }
 
+        VirtualFileSystem* vfs() { return m_vfs; }
+        const VirtualFileSystem* vfs() const { return m_vfs; }
+
     private:
         friend class VirtualFileSystem;
-        VirtualFileSystem* vfs { nullptr };
+        VirtualFileSystem* m_vfs { nullptr };
         unsigned retainCount { 0 };
         CharacterDevice* m_characterDevice { nullptr };
+        mutable InodeMetadata m_cachedMetadata;
     };
 
     static VirtualFileSystem& the();
@@ -68,7 +75,9 @@ public:
     void registerCharacterDevice(unsigned major, unsigned minor, CharacterDevice&);
 
 private:
-    template<typename F> void enumerateDirectoryInode(InodeIdentifier, F func);
+    friend class FileHandle;
+
+    void enumerateDirectoryInode(InodeIdentifier, Function<bool(const FileSystem::DirectoryEntry&)>);
     InodeIdentifier resolvePath(const String& path);
     InodeIdentifier resolveSymbolicLink(const String& basePath, InodeIdentifier symlinkInode);