path: root/kernel/fs.rv

# on disk layout for the 16 mib test disk (32768 sectors):
#   sector 0        superblock (magic + total sectors + root dir block)
#   sectors 1..128  fat, one 2 byte entry per block on the whole disk
#   sectors 129..   data, used for both file bytes and directory entry blocks
#
# a directory is just a file whose data blocks hold 32 byte entries. the
# superblock points at the root dir, paths are walked from there. a fat entry
# points at the next block in a chain, 0 is free, END is the last

const SB_LBA = 0
const FAT_LBA = 1
const FAT_SECTORS = 128
const DATA_LBA = 129
const BLOCK = 512
const ENTS = 16          # 32 byte entries per 512 byte block
const NAME_MAX = 24
const MAGIC = 0x32465652 # "RVF2" little endian
const END = 0xffff       # end of chain marker in the fat
const T_FILE = 1
const T_DIR = 2

#* into non empty parts *#
fn split_path(path) -> table<string> do
  const raw_parts = path:split("/")
  let parts = {}

  for index in 0..raw_parts:len() do
    if (raw_parts[index]:len() > 0) parts:push(raw_parts[index])
  end

  return parts
end

global fs = {
  # scratch is a spare sector for superblocks/dirs/data
  scratch = 0,
  # fat is a separate scratch
  # so fat lookups dont trample a dir block were mid edit.
  fat = 0,
  ready = :false, total = 0, root = 0,

  fn fat_get(self, block) -> num do
    disk_read(FAT_LBA + (block shr 8), self.fat)

    return mem_read(self.fat + (block band 255) * 2, 2)
  end,

  fn fat_set(self, block, value) do
    const sector = FAT_LBA + (block shr 8)
    disk_read(sector, self.fat)
    mem_write(self.fat + (block band 255) * 2, value, 2)
    disk_write(sector, self.fat)
  end,

  fn fat_alloc(self) -> num do
    let block = DATA_LBA

    while (block < self.total) do
      disk_read(FAT_LBA + (block shr 8), self.fat)

      let offset = block band 255

      while (offset < 256 and block < self.total) do
        if mem_read(self.fat + offset * 2, 2) == 0 do
          return block
        end

        offset += 1
        block += 1
      end
    end

    return 0
  end,

  fn free_chain(self, first) do
    let block = first

    while (block != 0 and block != END) do
      const next_block = self:fat_get(block)

      self:fat_set(block, 0)
      block = next_block
    end
  end,

  #* entry is 32 bytes:
  - +0 type (0 free/1 file/2 dir)
  - +1 name len
  - +2 first block
  - +4 size
  - +8 name bytes *#
  fn ent_name(self, entry_offset) -> string do
    const name_length = mem_read(self.scratch + entry_offset + 1, 1)
    let result = ""

    for index in 0..name_length do
      result = result ~ string.of_ascii(mem_read(self.scratch + entry_offset + 8 + index, 1))
    end

    return result
  end,

  fn ent_write(self, entry_offset, type, name, first, size) do
    mem_write(self.scratch + entry_offset, type, 1)
    mem_write(self.scratch + entry_offset + 1, name:len(), 1)
    mem_write(self.scratch + entry_offset + 2, first, 2)
    mem_write(self.scratch + entry_offset + 4, size, 4)

    for index in 0..name:len() do
      mem_write(self.scratch + entry_offset + 8 + index, name[index]:ascii(), 1)
    end
  end,

  fn dir_lookup(self, dir_first, name) -> { type: num, first: num, size: num } | :nil do
    let block = dir_first

    while (block != 0 and block != END) do
      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      for slot in 0..ENTS do
        const entry_offset = slot * 32

        if mem_read(self.scratch + entry_offset, 1) != 0 and self:ent_name(entry_offset) == name do
          return { type = mem_read(self.scratch + entry_offset, 1), first = mem_read(self.scratch + entry_offset + 2, 2), size = mem_read(self.scratch + entry_offset + 4, 4) }
        end
      end

      block = next_block
    end

    return :nil
  end,

  #* add or overwrite `name` in the dir
     grows a block if every slot is taken *#
  fn dir_set(self, dir_first, name, type, first, size) -> bool do
    let block = dir_first
    let found_block = 0
    let found_offset = 0
    let free_block = 0
    let free_offset = -1
    let last_block = dir_first

    while (block != 0 and block != END) do
      last_block = block

      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      for slot in 0..ENTS do
        const entry_offset = slot * 32

        if mem_read(self.scratch + entry_offset, 1) == 0 do
          if free_offset < 0 do
            free_block = block
            free_offset = entry_offset
          end
        end else do
          if self:ent_name(entry_offset) == name do
            found_block = block
            found_offset = entry_offset
          end
        end
      end

      block = next_block
    end

    let target_block = 0
    let target_offset = 0

    match
    | found_block != 0 => do
        target_block = found_block
        target_offset = found_offset
      end
    | free_offset >= 0 => do
        target_block = free_block
        target_offset = free_offset
      end
    | _ => do
        const new_block = self:fat_alloc()

        if new_block == 0 do
          return :false
        end

        self:fat_set(new_block, END)
        self:fat_set(last_block, new_block)
        mem_zero(self.scratch, BLOCK)
        disk_write(new_block, self.scratch)
        target_block = new_block
        target_offset = 0
      end

    disk_read(target_block, self.scratch)
    self:ent_write(target_offset, type, name, first, size)
    disk_write(target_block, self.scratch)

    return :true
  end,

  fn dir_clear(self, dir_first, name) -> { type: num, first: num } | :nil do
    let block = dir_first

    while (block != 0 and block != END) do
      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      for slot in 0..ENTS do
        const entry_offset = slot * 32

        if mem_read(self.scratch + entry_offset, 1) != 0 and self:ent_name(entry_offset) == name do
          const info = { type = mem_read(self.scratch + entry_offset, 1), first = mem_read(self.scratch + entry_offset + 2, 2) }

          mem_write(self.scratch + entry_offset, 0, 1)
          disk_write(block, self.scratch)

          return info
        end
      end

      block = next_block
    end

    return :nil
  end,

  fn dir_empty(self, dir_first) -> bool do
    let block = dir_first

    while (block != 0 and block != END) do
      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      for slot in 0..ENTS do
        if mem_read(self.scratch + slot * 32, 1) != 0 do
          return :false
        end
      end

      block = next_block
    end

    return :true
  end,

  # resolve a path to its entry
  fn resolve(self, path) -> { type: num, first: num, size: num } | :nil do
    const parts = split_path(path)
    let current = self.root
    let entry = { type = T_DIR, first = self.root, size = 0 }

    for index in 0..parts:len() do
      if entry.type != T_DIR do
        return :nil
      end

      const found = self:dir_lookup(current, parts[index])

      if found == :nil do
        return :nil
      end

      entry = found
      current = found.first
    end

    return entry
  end,

  # resolve a path to its parent dir and name
  fn resolve_parent(self, path) -> { dir: num, name: string } | :nil do
    const parts = split_path(path)

    if parts:len() == 0 do
      return :nil
    end

    let parent_dir = self.root

    for index in 0..(parts:len() - 1) do
      const found = self:dir_lookup(parent_dir, parts[index])

      if found == :nil or found.type != T_DIR do
        return :nil
      end

      parent_dir = found.first
    end

    return { dir = parent_dir, name = parts[parts:len() - 1] }
  end,

  fn mount(self) do
    self.scratch = frame_alloc()
    self.fat = frame_alloc()
    self.total = disk_sectors()

    if self.total == 0 do
      self.ready = :false
      return :nil
    end

    disk_read(SB_LBA, self.scratch)

    if mem_read(self.scratch, 4) == MAGIC do
      self.root = mem_read(self.scratch + 8, 2)
      self.ready = :true
    end else do
      self.ready = :false
    end
  end,

  fn ensure(self) -> bool do
    if self.ready do
      return :true
    end

    puts("no filesystem, run mkfs first\n")

    return :false
  end,

  fn format(self) do
    if disk_sectors() == 0 do
      puts("mkfs: no disk\n")
      return :nil
    end

    mem_zero(self.scratch, BLOCK)

    for sector in 0..FAT_SECTORS do
      disk_write(FAT_LBA + sector, self.scratch)
    end

    const root = self:fat_alloc()

    self:fat_set(root, END)
    mem_zero(self.scratch, BLOCK)
    disk_write(root, self.scratch)
    self.root = root
    mem_zero(self.scratch, BLOCK)
    mem_write(self.scratch, MAGIC, 4)
    mem_write(self.scratch + 4, self.total, 4)
    mem_write(self.scratch + 8, root, 2)
    disk_write(SB_LBA, self.scratch)
    self.ready = :true

    puts("formatted #{self.total} sectors, #{(self.total shr 1)} KiB\n")
  end,

  fn mkdir(self, path) do
    if self:ensure() == :false do
      return :nil
    end

    const parent = self:resolve_parent(path)

    if parent == :nil do
      fail("mkdir: #{path}: bad path\n")
      return :nil
    end

    if parent.name:len() > NAME_MAX do
      fail("name too long (max #{NAME_MAX})\n")
      return :nil
    end

    if self:dir_lookup(parent.dir, parent.name) != :nil do
      fail("mkdir: #{parent.name}: already exists\n")
      return :nil
    end

    const new_block = self:fat_alloc()

    if new_block == 0 do
      fail("disk full\n")
      return :nil
    end

    self:fat_set(new_block, END)
    mem_zero(self.scratch, BLOCK)
    disk_write(new_block, self.scratch)
    self:dir_set(parent.dir, parent.name, T_DIR, new_block, 0)
  end,

  fn store(self, path, text) -> num do
    if self:ensure() == :false do
      return 0
    end

    const parent = self:resolve_parent(path)

    if parent == :nil do
      puts("#{path}: bad path\n")
      return 0
    end

    if parent.name:len() > NAME_MAX do
      puts("name too long (max #{NAME_MAX})\n")
      return 0
    end

    const existing = self:dir_lookup(parent.dir, parent.name)

    if existing != :nil do
      if existing.type == T_DIR do
        fail("#{parent.name}: is a directory\n")
        return 0
      end

      self:free_chain(existing.first)
    end

    const size = text:len()
    let first = 0
    let previous = 0
    let written = 0

    while (written < size) do
      const block = self:fat_alloc()

      if block == 0 do
        fail("disk full\n")
        return 0
      end

      self:fat_set(block, END)

      if first == 0 do
        first = block
      end else do
        self:fat_set(previous, block)
      end

      mem_zero(self.scratch, BLOCK)
      # blit a whole block of the string at once, per byte was O(n^2) and choked
      # the second files got into the kilobytes
      let chunk = size - written

      if (chunk > BLOCK) chunk = BLOCK

      blit_str(self.scratch, text[written..(written + chunk)])
      disk_write(block, self.scratch)
      written += chunk
      previous = block
    end

    self:dir_set(parent.dir, parent.name, T_FILE, first, size)

    return 1
  end,

  fn write(self, path, text) do
    if (self:store(path, text) == 1) puts("wrote #{path} (#{text:len()} bytes)\n")
  end,

  fn size(self, path) -> num do
    const entry = self:resolve(path)

    if entry == :nil or entry.type == T_DIR do
      return -1
    end

    return entry.size
  end,

  fn read_bytes(self, path, offset, length) -> string do
    const entry = self:resolve(path)

    if entry == :nil or entry.type == T_DIR do
      return ""
    end

    let block = entry.first
    let stop = offset + length

    if (stop > entry.size) stop = entry.size

    let position = 0
    let result = ""

    while (block != 0 and block != END and position < stop) do
      const next_block = self:fat_get(block)

      if position + BLOCK > offset and position < stop do
        disk_read(block, self.scratch)
        # pull this blocks slice in one go, per byte concat was O(n^2)
        let from = 0

        if (offset > position) from = offset - position

        let to = BLOCK

        if (stop - position < BLOCK) to = stop - position

        result = result ~ phys_to_str(self.scratch + from, to - from)
      end

      position += BLOCK
      block = next_block
    end

    return result
  end,

  fn read_into(self, path, dest) -> num do
    const entry = self:resolve(path)

    if entry == :nil or entry.type == T_DIR do
      return 0
    end

    let block = entry.first
    let offset = 0
    let remaining = entry.size

    while (block != 0 and block != END and remaining > 0) do
      const next_block = self:fat_get(block)

      disk_read(block, dest + offset)
      offset += BLOCK
      remaining -= BLOCK
      block = next_block
    end

    return entry.size
  end,

  # TODO: ts needs a rewrite its not cheap and rewrites every file from scratch
  fn write_at(self, path, offset, bytes) -> num do
    const size = self:size(path)
    let base = ""

    if size > 0 do base = self:read_bytes(path, 0, size) end

    let prefix = ""

    if offset <= base:len() do
      prefix = base[0..offset]
    end else do
      prefix = base
      while (prefix:len() < offset) do prefix = prefix ~ string.of_ascii(0) end
    end

    const after = offset + bytes:len()
    let tail = ""

    if after < base:len() do tail = base[after..] end

    return self:store(path, prefix ~ bytes ~ tail)
  end,

  fn cat(self, path) do
    if self:ensure() == :false do
      return :nil
    end

    const entry = self:resolve(path)

    if entry == :nil do
      fail("cat: #{path}: no such file\n")
      return :nil
    end

    if entry.type == T_DIR do
      fail("cat: #{path}: is a directory\n")
      return :nil
    end

    let block = entry.first
    let remaining = entry.size
    let result = ""

    while (block != 0 and block != END and remaining > 0) do
      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      const chunk = if (remaining > BLOCK) BLOCK else remaining

      for index in 0..chunk do
        result = result ~ string.of_ascii(mem_read(self.scratch + index, 1))
      end

      remaining -= chunk
      block = next_block
    end

    puts(result)
    puts("\n")
  end,

  fn ls(self, path) -> num do
    if self:ensure() == :false do
      return -1
    end

    const entry = self:resolve(path)

    if entry == :nil do
      fail("ls: #{path}: no such file\n")
      return -1
    end

    if entry.type != T_DIR do
      puts("  #{path}  #{entry.size} bytes\n")
      return -1
    end

    let count = 0
    let block = entry.first

    while (block != 0 and block != END) do
      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      for slot in 0..ENTS do
        const entry_offset = slot * 32
        const entry_type = mem_read(self.scratch + entry_offset, 1)

        if entry_type != 0 do
          const name = self:ent_name(entry_offset)

          if entry_type == T_DIR do
            puts("  #{name}/\n")
          end else do
            puts("  #{name}  #{mem_read(self.scratch + entry_offset + 4, 4)} bytes\n")
          end

          count += 1
        end
      end

      block = next_block
    end

    return count
  end,

  fn rm(self, path) do
    if self:ensure() == :false do
      return :nil
    end

    const parent = self:resolve_parent(path)

    if parent == :nil do
      fail("rm: #{path}: no such file\n")
      return :nil
    end

    const entry = self:dir_lookup(parent.dir, parent.name)

    if entry == :nil do
      fail("rm: #{path}: no such file\n")
      return :nil
    end

    if entry.type == T_DIR and self:dir_empty(entry.first) == :false do
      fail("rm: #{parent.name}: directory not empty\n")
      return :nil
    end

    self:free_chain(entry.first)
    self:dir_clear(parent.dir, parent.name)
    puts("removed #{parent.name}\n")
  end,

  fn is_dir(self, path) -> bool do
    const entry = self:resolve(path)

    return entry != :nil and entry.type == T_DIR
  end,

  fn entries(self, path) -> table | :nil do
    const entry = self:resolve(path)

    if entry == :nil or entry.type != T_DIR do
      return :nil
    end

    let result = {}
    let block = entry.first

    while (block != 0 and block != END) do
      const next_block = self:fat_get(block)

      disk_read(block, self.scratch)

      for slot in 0..ENTS do
        const entry_offset = slot * 32
        const entry_type = mem_read(self.scratch + entry_offset, 1)

        if entry_type != 0 do
          result:push({
            name = self:ent_name(entry_offset),
            type = entry_type,
            size = mem_read(self.scratch + entry_offset + 4, 4),
          })
        end
      end

      block = next_block
    end

    return result
  end,

  fn unlink(self, path) -> bool do
    const parent = self:resolve_parent(path)

    if parent == :nil do
      return :false
    end

    const entry = self:dir_lookup(parent.dir, parent.name)

    if entry == :nil do
      return :false
    end

    if entry.type == T_DIR and self:dir_empty(entry.first) == :false do
      return :false
    end

    self:free_chain(entry.first)
    self:dir_clear(parent.dir, parent.name)

    return :true
  end,
}

global fs_store = fn(name, text) fs:store(name, text)
global fs_size = fn(name) fs:size(name)
global fs_read_bytes = fn(name, offset, length) fs:read_bytes(name, offset, length)
global fs_write_at = fn(name, offset, bytes) fs:write_at(name, offset, bytes)