[RFC] redoxfs.pk: Pickle for RedoxFS file system

[Mohammad-Reza Nabipoor]

Hi, Jose.

This pickle `redoxfs.pk` needs your review!
It needs more systematic tests to make sure I didn't miss anything.

The final goal is to provide all facilities to put data in the FS or
get data from it:
  - ls
  - ar a
  - ar x
  - find
  - ...


Regards,
Mohammad-Reza

---

/* redoxfs.pk - RedoxFS file system of Redox OS.  */

/* Copyright (C) 2020 The poke authors */

/* This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/* RedoxFS
 * File-system of RedoxOS (a Unix-like operating system written in Rust)
 *
 * The file-system has a header (type `RedoxFS_Header`). Header has a
 * pointer to root node. Nodes are represented by type `RedoxFS_Node`.
 * Data is stored in `extents` of each node. Extents are represented
 * by type `RedoxFS_Extents`. Each node has 238 extents. If a node needs
 * more extents, it will use the extents of the `next` node.
 * Each node can be a file or directory or symlink.
 * Extents of file nodes are point to the actual data. And extents of
 * directory nodes are point to child nodes.
 *
 * https://gitlab.redox-os.org/redox-os/redoxfs/
 */

/* set_endian(ENDIAN_LITTLE); */

load time;

/* Block size */
unit RedoxFS_BLKSZ = 4096UL * 8;  /* `4096*8` bits */

type RedoxFS_Extent =
  struct
  {
    offset<uint<64>,RedoxFS_BLKSZ> block;
    offset<uint<64>,B> length;

    method empty = int:
      {
        return block == 0#B && length == 0#B;  /* CHKME block ?= 0#B */
      }
    method data = uint<8>[]:
      {
        return uint<8>[length] @ block;
      }
  };

var RedoxFS_MODE_TYPE    = 0xF000UH,
    RedoxFS_MODE_FILE    = 0x8000UH,
    RedoxFS_MODE_DIR     = 0x4000UH,
    RedoxFS_MODE_SYMLINK = 0xA000UH;

var RedoxFS_MODE_PERM  = 0x0FFFUH,
    RedoxFS_MODE_EXEC  = 0o1UH,
    RedoxFS_MODE_WRITE = 0o2UH,
    RedoxFS_MODE_READ  = 0o4UH;

/* A file/folder node */
type RedoxFS_Node =
  struct
  {
    uint<16> mode;
    uint<32> uid;
    uint<32> gid;
    uint<64> ctime;
    uint<32> ctime_nsec;
    uint<64> mtime;
    uint<32> mtime_nsec;
    uint<64> atime;
    uint<32> atime_nsec;
    uint<8>[226] name;
    offset<uint<64>,RedoxFS_BLKSZ> parent;
    offset<uint<64>,RedoxFS_BLKSZ> next;
    RedoxFS_Extent[(#RedoxFS_BLKSZ/#B - 288UL) / (#RedoxFS_Extent/#B)] extents;

    method isdir = int:
      {
        return (mode & RedoxFS_MODE_DIR) == RedoxFS_MODE_DIR;
      }
    method isfile = int:
      {
        return (mode & RedoxFS_MODE_FILE) == RedoxFS_MODE_FILE;
      }
    method issymlink = int:
      {
        return (mode & RedoxFS_MODE_SYMLINK) == RedoxFS_MODE_SYMLINK;
      }
  };

type RedoxFS_Header =
  struct
  {
    uint<8>[8] signature = ['R', 'e', 'd', 'o', 'x', 'F', 'S', 0UB];
    uint<64> version = 4UL;

    /* Disk ID, a 128-bit unique identifier */
    uint<8>[16] uuid;

    offset<uint<64>,B> size;

    offset<uint<64>,RedoxFS_BLKSZ> root;  /* Block of root node */
    offset<uint<64>,RedoxFS_BLKSZ> free;  /* Block of free space node */

    /* Padding */
    /* uint<8>[#RedoxFS_BLKSZ/#B - 56UL]; */
  };


/* Node pretty-printer
 *
 * Prints the contents of a `RedoxFS_Node` in a readable fashion.
 * To increase readability, only non-empty extents are get printed before any
 * other fields. By default, extents are get printed from first one to last
 * one by default, but this can be changed by passing 1 in `reverse` argument.
 */
fun redoxfs_nprint = (RedoxFS_Node n, int reverse = 0) void:
  {
    print ("#<\n  extents = [\n");

    var f = reverse ? n.extents'length : 0UL;  /* first */
    var l = reverse ? 0UL : n.extents'length;  /* last  */

    while (f != l) {
      if (reverse)
        --f;

      var e = n.extents[f];

      if (!e.empty)
        printf ("    .[%u64d]={block=%v, length=%v}\n", f, e.block, e.length);

      if (!reverse)
        ++f;
    }

    var mtype =
      n.issymlink ? "FILE | SYM"
      : n.isfile ? "FILE"
      : n.isdir ? "DIR"
      : "" ;

    printf (
      "  ],\n  mode=%s | %u12o,\n  uid=%u32d,\n  gid=%u32d,\n  ctime=%u64d (",
      mtype, n.mode & RedoxFS_MODE_PERM, n.uid, n.gid, n.ctime);
    ptime (n.ctime);
    printf ("),\n  ctime_nsec=%u64d,\n  mtime=%u64d (", n.ctime_nsec, n.mtime);
    ptime (n.mtime);
    printf ("),\n  mtime_nsec=%u64d,\n  atime=%u64d (", n.mtime_nsec, n.atime);
    ptime (n.atime);
    printf (
      "),\n  atime_nsec=%u64d,\n  name=%s,\n", n.atime_nsec, catos (n.name));
    printf ("  parent=%v,\n  next=%v,\n>\n", n.parent, n.next);
  }

fun redoxfs_root = (RedoxFS_Header hdr = RedoxFS_Header @ 0#B) RedoxFS_Node:
  {
    return RedoxFS_Node @ hdr.root;
  }

/* Visits all the extents of a node (extents + next.extents +
 * next.next.extents + ...).
 */

type RedoxFS_EVisitor = (RedoxFS_Extent) void;
fun redoxfs_extents = (RedoxFS_Node n, RedoxFS_EVisitor v) uint<64>:
  {
    var c = 0;  /* counter */
    var nxt = n.next;

    for (e in n.extents where !e.empty)
      {
        ++c;
        v (e);
      }
    while (nxt != 0#B)
      {
        n = RedoxFS_Node @ nxt;
        nxt = n.next;
        for (e in n.extents where !e.empty)
          {
            ++c;
            v (e);
          }
      }
    return c;
  }

/* File-system walker
 *
 * `redoxfs_walk` traverse the file-system hierarchy and call the vistor
 * callback function for each entiry (file, directory or symlink).
 *
 * First argument of visitor `ftype` is `'f'` for files, `'d'` for
 * directories and `'s'` for symlinks. The next argument is the name of
 * the entity. The third one is path of parent directory of the entity.
 * The last argument is an array of extents corresponds to the entity.
 */

type RedoxFS_Visitor =
  (char /*ftype*/, string /*name*/, string /*path*/, RedoxFS_Extent[]) void;

fun redoxfs_walk = (RedoxFS_Node n, RedoxFS_Visitor v) void:
  {
    fun nothing = (RedoxFS_Extent e) void: {};
    fun filev = (RedoxFS_Node n, string curdir) void:
      {
        /* TODO(mnabipoor) Measure performance of array construction */
        var es_count = redoxfs_extents (n, nothing);
        var es = RedoxFS_Extent[es_count] ();
        var i = 0UL;

        redoxfs_extents (n, lambda (RedoxFS_Extent e) void: { es[i++] = e; });
        v('f', catos (n.name), curdir, es);
      }
    fun visit = (RedoxFS_Node n, string curdir) void:
      {
        if (n.issymlink)
          v('s', catos (n.extents[0].data), curdir, RedoxFS_Extent[] ());
        else if (n.isfile)
          filev (n, curdir);
        else if (n.isdir)
          {
            var name = catos (n.name);
            var path = (curdir == "/" ? "" :  curdir) + "/" + name;
            var es_count = redoxfs_extents (n, nothing);
            var es = RedoxFS_Extent[es_count] ();
            var i = 0UL;
            fun ev = (RedoxFS_Extent e) void:
              {
                es[i++] = e;
                visit (RedoxFS_Node @ e.block, path); 
              };

            redoxfs_extents (n, ev);
            v('d', name, curdir, es);
          }
      }
    var nxt = n.next;

    visit (n, "/");
    while (nxt != 0#B)
      {
        n = RedoxFS_Node @ nxt;
        nxt = n.next;
        visit (n, "/");
      }
  }