diff options
Diffstat (limited to '')
| -rw-r--r-- | .gitignore | 5 | ||||
| -rw-r--r-- | README.org | 24 | ||||
| -rw-r--r-- | bin/main.ml | 7 | ||||
| -rw-r--r-- | deps/relational_engine_lib.nix | 28 | ||||
| -rw-r--r-- | docs/architecture.plantuml | 72 | ||||
| -rw-r--r-- | dune-project | 2 | ||||
| -rw-r--r-- | flake.nix | 27 | ||||
| -rw-r--r-- | lib/core_functions.ml | 21 | ||||
| -rw-r--r-- | lib/core_types.ml | 3 | ||||
| -rw-r--r-- | lib/disk.ml | 167 | ||||
| -rw-r--r-- | lib/dune | 56 | ||||
| -rw-r--r-- | lib/extensions.ml | 7 | ||||
| -rw-r--r-- | lib/hello.ml | 1 | ||||
| -rw-r--r-- | lib/interop.ml | 19 | ||||
| -rw-r--r-- | lib/merklecpp_stubs.cpp | 15 | ||||
| -rw-r--r-- | shared/librelational_engine/CMakeLists.txt (renamed from CMakeLists.txt) | 10 | ||||
| -rw-r--r-- | shared/librelational_engine/flake.nix | 0 | ||||
| -rw-r--r-- | shared/librelational_engine/library.cpp | 30 | ||||
| -rw-r--r-- | shared/librelational_engine/library.h | 9 |
19 files changed, 443 insertions, 60 deletions
@@ -1,2 +1,5 @@ result -_build
\ No newline at end of file +_build +cmake-build-debug/ +*CMakeFiles +*CMakeCache.txt
\ No newline at end of file diff --git a/README.org b/README.org new file mode 100644 index 0000000..dcd2b7c --- /dev/null +++ b/README.org @@ -0,0 +1,24 @@ +#+TITLE: Relational Engine + +* About +This is a relational engine. + +* Roadmap +- [ ] Filesystem [0/6] + - [ ] Durability + - [ ] Immutable storage + - [ ] ARIES + - [ ] Merkle construction per virtual file + - [ ] Branching + - [ ] Branch merge strategies [0/3] + - [ ] Selected merge + - [ ] Union merge + - [ ] Biased union merge +- [ ] Language [0/4] + - [ ] Lexer + - [ ] Parser + - [ ] AST + - [ ] Unification and query terms +- [ ] Server [0/2] + - [ ] Authentication + - [ ] Multi-client coordination diff --git a/bin/main.ml b/bin/main.ml index 6fe3d69..289b4dd 100644 --- a/bin/main.ml +++ b/bin/main.ml @@ -1,3 +1,6 @@ -open Relational_engine.Hello +open Relational_engine -let _ = hello () +let () = + begin + print_endline @@ Interop.Merkle.merkle_generate_root [Disk.Executor._EMPTY_SHA_HASH_; Disk.Executor._EMPTY_SHA_HASH_] + end diff --git a/deps/relational_engine_lib.nix b/deps/relational_engine_lib.nix new file mode 100644 index 0000000..b1d0488 --- /dev/null +++ b/deps/relational_engine_lib.nix @@ -0,0 +1,28 @@ +{ pkgs, libressl ? pkgs.callPackage ./libressl.nix {}, merklecpp ? pkgs.callPackage ./merklecpp.nix {}, ... }: +let + shared_lib_extension = if pkgs.stdenv.isDarwin then "dylib" else "so"; +in +pkgs.stdenv.mkDerivation { + name = "librelational_engine"; + src = ../shared/librelational_engine; + nativeBuildInputs = [ + pkgs.cmake + pkgs.gcc + ]; + buildInputs = [ libressl merklecpp ]; + env = { + MERKLECPP_INCLUDE_PATH="${merklecpp}/include"; + LIBRESSL_INCLUDE_PATH="${libressl}/include"; + LIBRESSL_LIB_PATH="${libressl}/lib"; + OS_LIB_EXTENSION = shared_lib_extension; + }; + buildPhase = '' + mkdir -p $out/lib + mkdir -p $out/include + cmake --build . --target relational_engine + ''; + installPhase = '' + mv librelational_engine.${shared_lib_extension} $out/lib/librelational_engine.${shared_lib_extension} + cp $src/library.h $out/include/library.h + ''; +} diff --git a/docs/architecture.plantuml b/docs/architecture.plantuml new file mode 100644 index 0000000..90985ba --- /dev/null +++ b/docs/architecture.plantuml @@ -0,0 +1,72 @@ +@startuml +allowmixing + +package Client { + object "Query Interface" as query_interface +} + +package Algebra { + object "Unifier" as unifier + object "Bytecode Builder" as bytecode_builder + object "Parser" as parser + object "Lexer" as lexer +} + +query_interface --> lexer +lexer --> parser +parser --> unifier +unifier --> bytecode_builder + +package Query { + object "Schema Builder" as schema_builder + object "Facts Builder" as facts_builder + object "Optimizer" as optimizer + object "Commands Generator" as commands_generator + object "B+ Tree" as b_plus_tree +} + +bytecode_builder --> optimizer +optimizer --> commands_generator +facts_builder --> commands_generator +schema_builder --> commands_generator +commands_generator --> b_plus_tree +b_plus_tree --> query_interface + +package Coordinator { + object "File Historical Hashes" as file_historical_hashes + object "Location Hashes" as location_hashes + object "Command Parser" as command_parser + object "Curator" as curator +} + +commands_generator <-- command_parser + +package Disk { + object "Merkle Tree Root Generator" as merkle_tree + object "WAL Reader" as wal_reader + object "WAL Writer" as wal_writer + object "ARIES" as aries + object "SHA256 Hasher" as sha + object "Executor" as executor + map storage { + write => +λ + read => +λ + } + object "Courier" as courier + database Wal +} + +executor *--> merkle_tree +executor *--> sha +curator --> command_parser +command_parser --> executor +location_hashes *--> curator +file_historical_hashes *--> curator +executor --> aries +aries --> wal_reader +aries --> wal_writer +wal_writer --> Wal +wal_reader --> Wal +courier <-- wal_reader +courier --> storage +@enduml
\ No newline at end of file diff --git a/dune-project b/dune-project index 3e80424..661cecd 100644 --- a/dune-project +++ b/dune-project @@ -1,6 +1,6 @@ (lang dune 3.16) -;; (using ctypes 0.3) +(using ctypes 0.3) (name relational_engine) @@ -1,5 +1,5 @@ { - description = "A compiler for a statically-typed relational programming language"; + description = "Relational Engine"; # Flake dependency specification # @@ -31,6 +31,7 @@ lib = legacyPackages.lib; merklecpp = legacyPackages.callPackage ./deps/merklecpp.nix {}; libressl = legacyPackages.callPackage ./deps/libressl.nix {}; + librelational_engine = legacyPackages.callPackage ./deps/relational_engine_lib.nix { libressl = libressl; merklecpp = merklecpp; }; # Filtered sources (prevents unecessary rebuilds) sources = { @@ -78,12 +79,17 @@ MERKLECPP_INCLUDE_PATH="${merklecpp}/include"; LIBRESSL_INCLUDE_PATH="${libressl}/include"; LIBRESSL_LIB_PATH="${libressl}/lib"; + OS_LIB_EXTENSION = if legacyPackages.stdenv.isDarwin then "dylib" else "so"; + LIBRELATIONAL_ENGINE_LIB_PATH="${librelational_engine}/lib"; + LIBRELATIONAL_ENGINE_INCLUDE_PATH="${librelational_engine}/include"; }; nativeInputs = []; - buildInputs = [ - # Ocaml package dependencies needed to build go here. + buildInputs = with ocamlPackages; [ + ctypes + ctypes-foreign + data-encoding ]; strictDeps = true; @@ -202,8 +208,9 @@ MERKLECPP_INCLUDE_PATH="${merklecpp}/include"; LIBRESSL_INCLUDE_PATH="${libressl}/include"; LIBRESSL_LIB_PATH="${libressl}/lib"; - CAML_INCLUDE_PATH="${legacyPackages.ocaml}/include"; OS_LIB_EXTENSION = if legacyPackages.stdenv.isDarwin then "dylib" else "so"; + LIBRELATIONAL_ENGINE_LIB_PATH="${librelational_engine}/lib"; + LIBRELATIONAL_ENGINE_INCLUDE_PATH="${librelational_engine}/include"; }; # Development tools @@ -225,8 +232,20 @@ ocamlPackages.menhir ocamlPackages.ctypes ocamlPackages.ctypes-foreign + ocamlPackages.data-encoding + legacyPackages.cmake + legacyPackages.gcc ]; + shellHook = '' + echo MERKLECPP_INCLUDE_PATH=$MERKLECPP_INCLUDE_PATH + echo LIBRESSL_INCLUDE_PATH=$LIBRESSL_INCLUDE_PATH + echo LIBRESSL_LIB_PATH=$LIBRESSL_LIB_PATH + echo OS_LIB_EXTENSION=$OS_LIB_EXTENSION + echo LIBRELATIONAL_ENGINE_LIB_PATH=$LIBRELATIONAL_ENGINE_LIB_PATH + echo LIBRELATIONAL_ENGINE_INCLUDE_PATH=$LIBRELATIONAL_ENGINE_INCLUDE_PATH + ''; + # Tools from packages inputsFrom = [ self.packages.${system}.relational_engine diff --git a/lib/core_functions.ml b/lib/core_functions.ml new file mode 100644 index 0000000..1e1af37 --- /dev/null +++ b/lib/core_functions.ml @@ -0,0 +1,21 @@ +(* open Ctypes *) + +module Types = Types_generated + +module Functions (F : Ctypes.FOREIGN) = struct + (* open F *) + open Ctypes_static + let os_extension = + if Sys.os_type = "Unix" then + let ic = Unix.open_process_in "uname" in + let uname = input_line ic in + let () = close_in ic in + if uname = "Darwin" then + "dylib" + else "so" + else "dll" + let libmerklecpp = Dl.dlopen ~flags:[RTLD_GLOBAL; RTLD_NOW] ~filename:((Sys.getenv "LIBRELATIONAL_ENGINE_LIB_PATH") ^ "/librelational_engine." ^ os_extension) + let compute_hash = Foreign.foreign ~from:libmerklecpp "compute_hash" (ptr char @-> Ctypes.string @-> returning void) + let merkle_generate_root = Foreign.foreign ~from:libmerklecpp "merkle_generate_root" (ptr Ctypes.string @-> int @-> ptr char @-> returning void) + +end diff --git a/lib/core_types.ml b/lib/core_types.ml new file mode 100644 index 0000000..45f5720 --- /dev/null +++ b/lib/core_types.ml @@ -0,0 +1,3 @@ +module Types (F : Ctypes.TYPE) = struct + let hash_size = F.constant "HASH_SIZE" F.int +end diff --git a/lib/disk.ml b/lib/disk.ml new file mode 100644 index 0000000..3c5157b --- /dev/null +++ b/lib/disk.ml @@ -0,0 +1,167 @@ +module type Configuration = sig + val base_dir: string + val storage: string + val transactions: string + val assure: unit -> unit +end + +module DevelopmentConfiguration: Configuration = struct + let base_dir = "/tmp/relational-engine/" + let storage = base_dir ^ "storage/" + let transactions = base_dir ^ "transactions/" + let assure () = + if Sys.file_exists base_dir + then Sys.remove base_dir; + Sys.mkdir base_dir 0o700; + Sys.mkdir storage 0o700; + Sys.mkdir transactions 0o700; +end + +module type FileSystem = sig + type target = + | Storage + | Transaction + val append: target -> bytes -> (int*int64, string) result +end + +module FileSystem (C: Configuration): FileSystem = struct + type target = + | Storage + | Transaction + let target_to_string = function + | Storage -> "storage" + | Transaction -> "transaction" + + (** [append target content] writes content to file in append only format, returning [content_length * offset_written] *) + let append target content = + let register channel = + let offset_written = Out_channel.length channel in + Out_channel.seek channel offset_written; + Out_channel.output_bytes channel content; + Out_channel.flush channel; + Out_channel.close channel; + Ok (Bytes.length content, offset_written) + in + try Out_channel.with_open_bin (target_to_string target) register + with _ -> Error (Printf.sprintf "Error on appending to target '%s'" (target_to_string target)) +end + +module Executor = struct + module StringMap = Map.Make(String) + module FS = FileSystem(DevelopmentConfiguration) + module Location = struct + type t = + { offset: int64; + size: int; + hash: string } + end + module Hashes = struct + type t = string list + end + type files = Hashes.t StringMap.t + type locations = Location.t StringMap.t + let _EMPTY_SHA_HASH_ = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855" + + (** Initializes the virtual file or opens it. *) + let init_file (files: Hashes.t StringMap.t) filename: Hashes.t StringMap.t = + match StringMap.find_opt filename files with + | None -> StringMap.add filename [_EMPTY_SHA_HASH_] files + | Some _ -> files + let write (files: files) (locations: locations) filename ?hash_to_replace (content: Bytes.t) = + let files = init_file files filename in + let computed_hash: string = Interop.Sha256.compute_hash content in + match StringMap.find_opt computed_hash locations with + | None -> + begin match hash_to_replace with + | None -> + begin + (* This instead should store a list of list to keep the history *) + let files = + StringMap.update + filename + (function Some file_hashes -> Some (computed_hash::file_hashes) | None -> Some [computed_hash]) + files + in + let open Extensions.Result in + let+ (size, offset) = FS.append Storage content in + let locations = StringMap.add computed_hash ({size; offset; hash = computed_hash}: Location.t) locations in + Ok (files, locations) + end + | Some hash_to_replace -> + let files = StringMap.update filename (function Some file_hashes -> Some (List.map (fun hash -> if hash = hash_to_replace then computed_hash else hash) file_hashes) | None -> Some [computed_hash]) files in + let open Extensions.Result in + let+ (size, offset) = FS.append Storage content in + let locations = StringMap.add computed_hash ({size; offset; hash = computed_hash}: Location.t) locations in + Ok (files, locations) + end + | Some _ -> + begin match hash_to_replace with + | Some hash_to_replace -> + let files = + StringMap.update filename + (function + | Some file_hashes -> Some (List.map (fun hash -> if hash = hash_to_replace then computed_hash else hash) file_hashes) + | None -> Some [computed_hash]) + files in + Ok (files, locations) + | None -> + Ok (files, locations) + end +end + +module Startup = struct + let () = DevelopmentConfiguration.assure() +end + +module Command = struct + module FS = FileSystem(DevelopmentConfiguration) + open Data_encoding + type command_kind = + | OPEN + | WRITE + | READ + let command_kind_encoding = + union [ + case ~title:"open" (Tag 0) + Data_encoding.empty + (function OPEN -> Some () | _ -> None) + (function () -> OPEN); + case ~title:"write" (Tag 1) + Data_encoding.empty + (function WRITE -> Some () | _ -> None) + (function () -> WRITE); + case ~title:"read" (Tag 2) + Data_encoding.empty + (function READ -> Some () | _ -> None) + (function () -> READ); + ] + type t = + { kind: command_kind; + timestamp: float; + hash: string; + filename: string; + (* branch must be added here later *) + content: string } + let command_encoding = + conv + (fun {kind; timestamp; hash; filename; content} -> (kind, timestamp, hash, filename, content)) + (fun (kind, timestamp, hash, filename, content) -> {kind; timestamp; hash; filename; content}) + Data_encoding.(tup5 command_kind_encoding float string string string) + + let parse_command ~data = + let contract_encoding = Data_encoding.(tup4 command_kind_encoding string string string) in + match Binary.of_bytes_opt contract_encoding data with + | Some (kind, hash, filename, content) -> Ok {kind; timestamp = Unix.time(); hash; filename; content} + | None -> Error "Failed to parse command" + + (** TODO: This does not write atomically. If the system crashes while it attempts to write, it will corrupt. + Solve this with a temporary file and move later. *) + let commit + (* (_files: Filesystem.files) (_locations: Filesystem.locations) *) + command = + let open Extensions.Result in + let+ serialized_command = + Result.map_error (fun _ -> "Failed to serialize command to binary format.") + @@ Binary.to_bytes command_encoding command in + FS.append FS.Transaction serialized_command +end @@ -1,31 +1,29 @@ (library (name relational_engine) - (libraries ctypes ctypes-foreign) - (modes native) - (foreign_stubs - (language cxx) - (names merklecpp_stubs) - (flags - (:standard -lssl -lcrypto) - (-L %{env:LIBRESSL_LIB_PATH=}) - (-I %{env:LIBRESSL_INCLUDE_PATH=}) - (-I %{env:MERKLECPP_INCLUDE_PATH=}))) - - ;; (ctypes - ;; (external_library_name merklecpp_stub) - ;; (headers (include "/Users/mmagueta/CLionProjects/merklecpp_stub/library.h")) - ;; (build_flags_resolver - ;; (vendored - ;; (c_flags - ;; -L %{env:MERKLECPP_LIB_PATH=}))) - ;; (type_description - ;; (instance Types) - ;; (functor Type_description)) - ;; (function_description - ;; (concurrency unlocked) - ;; (instance Functions) - ;; (functor Function_description)) - ;; (generated_types Types_generated) - ;; (generated_entry_point C)) - - ) + (libraries ctypes ctypes-foreign data-encoding) + ;; (c_library_flags -lssl -lcrypto -L %{env:LIBRESSL_LIB_PATH=}) + ;; (foreign_stubs + ;; (language cxx) + ;; (names merklecpp_stubs) + ;; (flags + ;; (:standard -lssl -lcrypto) + ;; (-L %{env:LIBRESSL_LIB_PATH=}) + ;; (-I %{env:LIBRESSL_INCLUDE_PATH=}) + ;; (-I %{env:MERKLECPP_INCLUDE_PATH=}))) + + (ctypes + (external_library_name relational_engine) + (headers (include %{env:LIBRELATIONAL_ENGINE_INCLUDE_PATH=}/library.h)) + (build_flags_resolver + (vendored + (c_flags + -L %{env:LIBRELATIONAL_ENGINE_LIB_PATH=}))) + (type_description + (instance Types) + (functor core_types)) + (function_description + (concurrency unlocked) + (instance Functions) + (functor core_functions)) + (generated_types Types_generated) + (generated_entry_point C))) diff --git a/lib/extensions.ml b/lib/extensions.ml new file mode 100644 index 0000000..c128f2a --- /dev/null +++ b/lib/extensions.ml @@ -0,0 +1,7 @@ +module Option = struct + let ( let+ ) = Option.bind +end + +module Result = struct + let ( let+ ) = Result.bind +end diff --git a/lib/hello.ml b/lib/hello.ml deleted file mode 100644 index 1a3a138..0000000 --- a/lib/hello.ml +++ /dev/null @@ -1 +0,0 @@ -external hello : unit -> int = "hello_ocaml" diff --git a/lib/interop.ml b/lib/interop.ml new file mode 100644 index 0000000..fdfde5f --- /dev/null +++ b/lib/interop.ml @@ -0,0 +1,19 @@ +open Ctypes + +module Sha256 = struct + let compute_hash content = + let size_with_null_terminator = C.Types.hash_size + 1 in + let buf = Ctypes.allocate_n char ~count:size_with_null_terminator in + let () = C.Functions.compute_hash buf (Bytes.to_string content) in + Ctypes.coerce (ptr char) Ctypes.string buf +end + +module Merkle = struct + let merkle_generate_root hashes = + let size_with_null_terminator = C.Types.hash_size + 1 in + let buf = Ctypes.allocate_n char ~count:size_with_null_terminator in + let len = List.length hashes in + let hashes = CArray.of_list string hashes in + C.Functions.merkle_generate_root (CArray.start hashes) len buf; + Ctypes.coerce (ptr char) Ctypes.string buf +end diff --git a/lib/merklecpp_stubs.cpp b/lib/merklecpp_stubs.cpp deleted file mode 100644 index 4ce427e..0000000 --- a/lib/merklecpp_stubs.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include <iostream> -#include <merklecpp.h> - -void cpp_normal_function() { - std::cout << "HELLO OCAML! :)" << std::endl; -} - -extern "C" { -#include <caml/mlvalues.h> -#include <caml/memory.h> - extern value hello_ocaml(value unit){ - cpp_normal_function(); - return 0; - } -} diff --git a/CMakeLists.txt b/shared/librelational_engine/CMakeLists.txt index 98dbfc4..d22d0d0 100644 --- a/CMakeLists.txt +++ b/shared/librelational_engine/CMakeLists.txt @@ -1,16 +1,12 @@ cmake_minimum_required(VERSION 3.29) -project(relational_engine_ocaml) - -set(CMAKE_CXX_STANDARD 20) +project(relational_engine) include_directories($ENV{LIBRESSL_INCLUDE_PATH}) include_directories($ENV{MERKLECPP_INCLUDE_PATH}) -include_directories($ENV{CAML_INCLUDE_PATH}) -add_library(relational_engine_ocaml STATIC - lib/merklecpp_stubs.cpp) +add_library(relational_engine SHARED library.cpp) -target_link_libraries(relational_engine_ocaml +target_link_libraries(relational_engine $ENV{LIBRESSL_LIB_PATH}/libssl.$ENV{OS_LIB_EXTENSION} $ENV{LIBRESSL_LIB_PATH}/libcrypto.$ENV{OS_LIB_EXTENSION} )
\ No newline at end of file diff --git a/shared/librelational_engine/flake.nix b/shared/librelational_engine/flake.nix new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/shared/librelational_engine/flake.nix diff --git a/shared/librelational_engine/library.cpp b/shared/librelational_engine/library.cpp new file mode 100644 index 0000000..8048486 --- /dev/null +++ b/shared/librelational_engine/library.cpp @@ -0,0 +1,30 @@ +#include <iostream> +#include <merklecpp.h> +#include <openssl/sha.h> +#include <iomanip> +extern "C" { +#include "library.h" + extern void merkle_generate_root(char** hashes, const int n, char* root) { + merkle::Tree tree; + for (int i = 0; i < n; i++){ + tree.insert(merkle::Hash(hashes[i])); + } + std::memcpy(root, tree.root().to_string().c_str(), HASH_SIZE); + } + extern void compute_hash(char* computed_hash, const char *content) { + + unsigned char hash[SHA256_DIGEST_LENGTH]; + SHA256_CTX sha256; + SHA256_Init(&sha256); + SHA256_Update(&sha256, content, sizeof(content)); + SHA256_Final(hash, &sha256); + std::stringstream ss; + for (int i = 0; i < SHA256_DIGEST_LENGTH; i++) + ss << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(hash[i]); + + std::memcpy(computed_hash, ss.str().c_str(), HASH_SIZE); + std::cout << "⚙️ COMPUTED HASH: " << computed_hash << std::endl; + } + + extern int trash() { return 100; } +}
\ No newline at end of file diff --git a/shared/librelational_engine/library.h b/shared/librelational_engine/library.h new file mode 100644 index 0000000..ebf8497 --- /dev/null +++ b/shared/librelational_engine/library.h @@ -0,0 +1,9 @@ +#ifndef MERKLECPP_STUB_LIBRARY_H +#define MERKLECPP_STUB_LIBRARY_H + +#define HASH_SIZE 64 + +extern void merkle_generate_root(char**, const int, char*); +extern void compute_hash(char*, const char*); + +#endif //MERKLECPP_STUB_LIBRARY_H |