Module `Tjr_fs_shared`

Common types and defns for file system work.

A collection of the main types provided by this library.

include Tjr_fs_shared__.Summary

  type ('blk_id,'t) blk_allocator_ops = {
    blk_alloc : unit -> ('blk_id,'t) m; 
    blk_free  : 'blk_id -> (unit,'t) m;
  }

type ('blk_id,'blk,'t,'fd) blk_dev_impl = <
  add_debug : 
    ('blk_id,'blk,'t)blk_dev_ops -> 
    ('blk_id,'blk,'t)blk_dev_ops;

  add_profiling: 
    ('blk_id,'blk,'t)blk_dev_ops -> 
    ('blk_id,'blk,'t)blk_dev_ops;

  with_ : blk_sz:blk_sz -> <
      from_fd: 'fd -> 
        <
          blk_dev_ops : ('blk_id,'blk,'t)blk_dev_ops;
          fd          : 'fd;
          sync        : unit -> (unit,'t)m;
          close       : unit -> (unit,'t)m;
        >;
    >
>    

  type ('blk_id,'blk,'t) blk_dev_ops = {
    blk_sz     : blk_sz; 
    write      : blk_id:'blk_id -> blk:'blk -> (unit,'t) m;
    read       : blk_id:'blk_id -> ('blk,'t) m;
    write_many : ('blk_id*'blk)list -> (unit,'t) m  (* FIXME may want to make this a seq? *)
  }

  type ('blk,'buf) blk_ops = {
    blk_sz: blk_sz;
    blk_to_buf: 'blk -> 'buf;
    buf_to_blk: 'buf -> 'blk;
  }

type 'buf buf_ops = {
  buf_create         : int -> 'buf;
  buf_length         : 'buf -> int;
  buf_get            : int -> 'buf -> char;
  buf_to_string      : src:'buf -> off:offset -> len:len -> string; 
  to_string          : 'buf -> string;
  of_string          : string -> 'buf;
  of_bytes           : bytes -> 'buf;

  blit               : src:'buf   -> src_off:offset -> src_len:len -> dst:'buf -> dst_off:offset -> 'buf;
  blit_bytes_to_buf  : src:bytes  -> src_off:offset -> src_len:len -> dst:'buf -> dst_off:offset -> 'buf;
  blit_string_to_buf : src:string -> src_off:offset -> src_len:len -> dst:'buf -> dst_off:offset -> 'buf;
}

type ('blk_id,'t) freelist_factory = <
  with_:
    fn:string -> 
    <

      create: min_free:'blk_id -> ( ('blk_id,'t)freelist_ops,'t)m;
      (** Create a new freelist *)

      restore: unit -> ( ('blk_id,'t)freelist_ops,'t)m;
      (** Restore from file *)

    >      
>

type ('blk_id,'t) freelist_ops = {
  alloc      : unit -> ('blk_id,'t)m;
  alloc_many : int -> ('blk_id list,'t)m;
  free       : 'blk_id -> (unit,'t)m;
  free_many  : 'blk_id list -> (unit,'t)m;
  sync       : unit -> (unit,'t)m;
  (** NOTE the freelist already ensures it is crash safe; this sync is
      really for tidy shutdown *)
}

type ('r,'blk,'buf,'t) shared_ctxt = {
  r_cmp      : 'r -> 'r -> int;
  r_size     :int;
  buf_ops    :'buf buf_ops;
  monad_ops  : 't monad_ops;
  async      : 't async;
  event_ops  : 't event_ops;
  blk_ops    : ('blk,'buf) blk_ops;
  blk_sz     : blk_sz;
  buf_to_blk : 'buf -> 'blk;
  blk_to_buf : 'blk -> 'buf;
  buf_create : unit -> 'buf;
}

Int-like types

module Int_like : sig ... end: Int-like types with unboxed record wrappers, for documentation purposes

Buffers

module Buf_ops : sig ... end: Buffer operations including blit, moved from Tjr_btree.

type 'buf buf_ops = 'buf Buf_ops.buf_ops

val chr0 : char

type ba_buf = Buf_ops.ba_buf
type ba_buf_ops = Buf_ops.ba_buf_ops

val ba_buf_ops : Bigstring.t Buf_ops.buf_ops
val by_buf_ops : Stdlib.Bytes.t Buf_ops.buf_ops

Block identifiers

module Blk_intf : sig ... end: Blk-related interfaces

module Blk_id_as_int = Blk_intf.Blk_id_as_int

Blocks

module Blk_sz = Blk_intf.Blk_sz

type blk_sz = Blk_sz.blk_sz

val blk_sz_4096 : Blk_sz.blk_sz

module Blk_ops = Blk_intf.Blk_ops

type ('blk, 'buf) blk_ops = ('blk, 'buf) Blk_ops.blk_ops

Block devices

module Blk_dev_ops = Blk_intf.Blk_dev_ops

type ('blk_id, 'blk, 't) blk_dev_ops = ('blk_id, 'blk, 't) Blk_dev_ops.blk_dev_ops = { blk_sz : blk_sz; write : blk_id:'blk_id -> blk:'blk -> (unit, 't) Tjr_monad.m; read : blk_id:'blk_id -> ('blk, 't) Tjr_monad.m; write_many : ('blk_id * 'blk) list -> (unit, 't) Tjr_monad.m; }

val blk_devs : < in_mem : monad_ops:'a Tjr_monad.monad_ops -> blk_sz:Blk_intf.blk_sz -> with_state:(('b, 'c) Tjr_lib.Tjr_map.With_stdcmp.stdmap, 'a) Tjr_monad.with_state -> ('b, 'c, 'a) Blk_intf.blk_dev_ops; lwt : (Blk_intf.Blk_id_as_int.blk_id, Shared_ctxt.blk, Tjr_monad.With_lwt.lwt, Lwt_unix.file_descr) Blk_intf.blk_dev_impl; lwt_open_file : fn:string -> create:bool -> trunc:bool -> (< blk_dev_ops : (Blk_intf.Blk_id_as_int.blk_id, Shared_ctxt.blk, Tjr_monad.With_lwt.lwt) Blk_intf.blk_dev_ops; close : unit -> (unit, Tjr_monad.With_lwt.lwt) Tjr_monad.m; fd : Lwt_unix.file_descr; sync : unit -> (unit, Tjr_monad.With_lwt.lwt) Tjr_monad.m; >, Tjr_monad.With_lwt.lwt) Tjr_monad.m; >

Block allocation

module Blk_allocator_ops = Blk_intf.Blk_allocator_ops

type ('blk_id, 't) blk_allocator_ops = ('blk_id, 't) Blk_allocator_ops.blk_allocator_ops = { blk_alloc : unit -> ('blk_id, 't) Tjr_monad.m; blk_free : 'blk_id -> (unit, 't) Tjr_monad.m; }

Note on sync and the blk device layer

A traditional block device accepts (read and) write requests. Write requests can be reordered, although writes for a particular blk id will commit in order.

A barrier operation enforces that it is not the case that a request before the barrier is reordered with a request after the barrier.

A sync operation requests that all writes are actually made persistent.

Of course, many devices do not implement these things properly.

Newer interfaces, such as (variants of) TCQ and NVMe, are more complicated. Typically there are queues of operations. Barrier and flush commands can be per-queue. It may be possible to request notification for when some operation actually completes (say, when a write is made persistent). There is often a "Forced Unit Access (FUA)" mode, which attempts to avoid caching etc and just persist the write. It may also be possible to provide additional information about the "priority" of a write, or even a "time out" associated with a write (if it hasn't happened by this time, then don't perform the write at all).

Effectively, a queue operates like a traditional block device.

Traditional block devices are likely to be very slow; queue-based interfaces such as those used in NVMe, are likely to be a much better fit for ImpFS. Suppose we have a persistent object on which we call the "sync" method. Then a traditional blk layer may already have some cached writes related to that object. If the blk layer does not know the connection between these writes and the object, then a sync on the object must force a complete sync of the blk layer (including all writes to all objects) which is potentially very costly. If we assume a queue-based interface, then things are much better, because the sync can target a particular queue (and all writes for the object will be placed in that queue).

In ImpFS, each object is provided with an interface that appears like a traditional block device (with sync and possibly barrier operations). However, the real block layer is assumed to be queue based. Our current implementations of this on top of traditional block devices are very inefficient because we effectively have only one queue. However, we expect that porting the code to use a more advanced queue-based interface would give a much greater performance.

It is perhaps worth putting some effort into emulating the queue-based interface efficiently on top of a traditional block device. I'm not sure how this should best be achieved, or whether it would actually improve performance.

Kv ops

module Kvop : sig ... end: A concrete type for insert and delete operations. Don't open.

type ('k, 'v) kvop = ('k, 'v) Kvop.kvop

module Kvop_map = Kvop.Kvop_map

Small strings, leq 256 bytes

module Str_256 : sig ... end: Strings with max length 256 bytes; safe to open

type str_256 = Str_256.str_256

Write back cache

module Write_back_cache_v1_DONT_USE = Write_back_cache

module Write_back_cache_v2_DONT_USE = Tjr_fs_shared__.Write_back_cache_v2

module Write_back_cache_v3 : sig ... end: A write-back cache; a wrapper around pqwy/lru.

module Write_back_cache = Write_back_cache_v3

type wbc_params = Write_back_cache.wbc_params
type ('k, 'v, 't) wbc_ops = ('k, 'v, 't) Write_back_cache.wbc_ops
type ('k, 'v, 't) wbc_ops_plus = ('k, 'v, 't) Write_back_cache.wbc_ops_plus
type ('k, 'v, 't) wbc_factory = ('k, 'v, 't) Write_back_cache.wbc_factory

Marshalling

There are basically two types of marshalling one might consider. They differ in the behaviour when attempting to marshal to a point in a buffer where the remaining space is not sufficient. In the first "max-size-based" model, the marshaller knows the max size of an element, and the remaining space, and then can determine ahead of marshalling if the space is (potentially) not sufficient. In this case, the marshaller can abort early without attempting any modification of the buffer. However, it may be that the particular element would have actually fit the space, so the approach may be inefficient. Maybe the marshaller can calculate the marshalled size of each element (without actually performing the marshalling). As mentioned in the bin_prot documentation, this is rare because being able to calculate the marshalled size of an elt is often as difficult as trying to marshal the element (and failing when the space is insufficient). So if we assume the decision is based on the max-size, this approach may be inefficient. However, crucially, in the case that the marshalling is not attempted because of insufficient space, the buffer is unchanged.

This should be contrasted with the "always-try-to-write" approach, where the marshalling is attempted regardless of the available space. If an error occurs (lack of space), the marshalling is aborted. In this case, the buffer will almost certainly be altered from the write position onwards (because it is too costly to record what these bytes are and replace them on a failed marshal).

The B-tree datastructure arguably favours the "max-size-based" model, and so this is mostly the approach we take here.

module Marshal_factory : sig ... end: Common marshallers

type ('a, 'buf) mshlr = ('a, 'buf) Marshal_factory.mshlr = { max_elt_sz : int; mshl : 'a -> ('buf * int) -> 'buf * int; umshl : 'buf -> int -> 'a * int; }
type ('k, 'v, 'buf) kv_mshlr = ('k, 'v, 'buf) Marshal_factory.kv_mshlr = { k_mshlr : ('k, 'buf) mshlr; v_mshlr : ('v, 'buf) mshlr; }

val mshlrs : < for_blk_id : (Blk_intf.Blk_id_as_int.blk_id, Shared_ctxt.buf) Marshal_factory.mshlr; for_blk_id_option : (Blk_intf.Blk_id_as_int.blk_id option, Shared_ctxt.buf) Marshal_factory.mshlr; for_int : (int, Shared_ctxt.buf) Marshal_factory.mshlr; for_int_int_kvop : ((int, int) Kvop.kvop, Shared_ctxt.buf) Marshal_factory.mshlr; for_int_int_kvop_option : ((int, int) Kvop.kvop option, Shared_ctxt.buf) Marshal_factory.mshlr; for_int_option : (int option, Shared_ctxt.buf) Marshal_factory.mshlr; for_kv : < int_int : (int, int, Shared_ctxt.buf) Marshal_factory.kv_mshlr; s256_int : (Str_256.str_256, int, Shared_ctxt.buf) Marshal_factory.kv_mshlr; s256_s256 : (Str_256.str_256, Str_256.str_256, Shared_ctxt.buf) Marshal_factory.kv_mshlr; >; for_s256 : (Str_256.str_256, Shared_ctxt.buf) Marshal_factory.mshlr; >

Marshalling with bin-prot

module Pvt_bin_prot_marshalling = Tjr_fs_shared__.Bin_prot_marshalling

type 'a bp_mshlr = 'a Pvt_bin_prot_marshalling.bp_mshlr
type 'a ba_mshlr = 'a Pvt_bin_prot_marshalling.ba_mshlr

val bp_mshlrs : < ba_mshlr : a. mshlr:'a Pvt_bin_prot_marshalling.bp_mshlr -> buf_sz:int -> 'a Pvt_bin_prot_marshalling.ba_mshlr; int_mshlr : int Pvt_bin_prot_marshalling.bp_mshlr; r_mshlr : Shared_ctxt.r Pvt_bin_prot_marshalling.bp_mshlr; s256_mshlr : Str_256.str_256 Pvt_bin_prot_marshalling.bp_mshlr; >

Standard example types and defns

module Shared_ctxt : sig ... end: Represent common context using classes; don't open (use Tjr_fs_shared.ctxt#shared)

val ctxt : < shared_ctxt : (Shared_ctxt.r, Shared_ctxt.blk, Shared_ctxt.buf, Tjr_monad.With_lwt.lwt) Shared_ctxt.shared_ctxt; >

Dummy freelist for testing

module Shared_freelist : sig ... end: This is a shared type for blk freelists, and a dummy implementation; other libraries may have their own; don't open

val shared_freelist : (Shared_ctxt.r, Tjr_monad.With_lwt.lwt, Shared_freelist.Example.t) Shared_freelist.freelist_factory

Testing

module Test : sig ... end: Support for basic testing, controlled by optcomp

Log

module Log : sig ... end

Runtime config support

val runtime_config_factory : < make : default:'a option -> filename:string -> 'a Tjr_fs_shared__.Runtime_config_factory.runtime_config -> 'a Stdlib.Lazy.t; >