hare

The Hare programming language
git clone https://git.torresjrjr.com/hare.git
Log | Files | Refs | README | LICENSE

commit 8e88ddbaa31ca21c17ba426c74b3d32b3978085a
parent 2440c5f065e6e782d4c208d79f421531b88ae0f2
Author: Bor Grošelj Simić <bor.groseljsimic@telemach.net>
Date:   Wed, 14 Apr 2021 17:48:06 +0200

fs::mem: new module

Diffstat:
Afs/mem/+test.ha | 148+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Afs/mem/mem.ha | 276+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Afs/mem/stream.ha | 91+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Afs/mem/util.ha | 126+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Mscripts/gen-stdlib | 19+++++++++++++++++++
Mstdlib.mk | 31+++++++++++++++++++++++++++++++
6 files changed, 691 insertions(+), 0 deletions(-)

diff --git a/fs/mem/+test.ha b/fs/mem/+test.ha @@ -0,0 +1,148 @@ +use bytes; +use errors; +use fs; +use io; +use strconv; + +@test fn mem() void = { + // TODO: Make type assertions with fs::error more specific once harec + // permits that. + const names: [6]str = ["foo", "bar", "baz", "quux", "hare.ha", "asdf"]; + let filename = names[0]; + + let memfs = memopen(); + const input: [_]u8 = [0, 1, 2, 3, 4, 5]; + + // fs::create, fs::stat + for (let i = 0z; i < 6; i += 1) { + let f = fs::create(memfs, names[i], 0, fs::flags::RDWR); + let f = f as *io::stream; + io::write(f, input[i..]); + io::close(f); + let st = fs::stat(memfs, names[i]) as fs::filestat; + assert(st.mask & fs::stat_mask::SIZE == fs::stat_mask::SIZE); + assert(st.sz == len(input) - i); + assert(st.mode & fs::mode::REG == fs::mode::REG); + }; + + let f = fs::open(memfs, filename, fs::flags::WRONLY, fs::flags::APPEND); + let f = f as *io::stream; + io::write(f, input); + io::close(f); + let st = fs::stat(memfs, filename) as fs::filestat; + assert(st.sz == len(input) * 2); + + fs::create(memfs, filename, 0, fs::flags::RDONLY) as fs::error; // errors::exists + + // fs::open and read + fs::open(memfs, "nonexistent", fs::flags::RDONLY) as fs::error; // errors::noentry + let f = fs::open(memfs, filename, fs::flags::RDWR, fs::flags::EXCL); + f as fs::error; // errors::unsupported + fs::remove(memfs, "nonexistent") as fs::error; // errors::noentry + + let f = fs::open(memfs, filename, fs::flags::RDONLY) as *io::stream; + let f2 = fs::open(memfs, filename, fs::flags::RDONLY) as *io::stream; + let output: [12]u8 = [0...]; + assert(io::seek(f2, 3, io::whence::SET) as io::off == 3: io::off); + assert(io::read(f2, output) as size == 9); + io::close(f2); + assert(io::read(f, output) as size == 12); + assert(bytes::equal(input, output[..6])); + assert(bytes::equal(input, output[6..])); + io::close(f); + + // fs::iter + let it = fs::iter(memfs, "") as *fs::iterator; + defer free(it); + let count = 0z; + for (true) match (it.next(it)) { + void => break, + d: fs::dirent => count += 1, + }; + assert(count == 6); + + // fs::mkdir + fs::mkdir(memfs, "nonexistent/path") as fs::error; // errors::noentry + fs::rmdir(memfs, "nonexistent/path") as fs::error; // errors::noentry + fs::mkdir(memfs, "dir") as void; + fs::open(memfs, "dir", fs::flags::RDONLY) as fs::error; // fs::wrongtype + fs::mkdir(memfs, "dir") as fs::error; // errors::exists + fs::mkdir(memfs, "dir/subdir") as void; + fs::rmdir(memfs, "dir/subdir") as void; + fs::rmdir(memfs, "dir") as void; + fs::rmdir(memfs, "") as fs::error; // errors::invalid; + + fs::mkdir(memfs, "dir") as void; + f = fs::create(memfs, "dir/file", 0, fs::flags::WRONLY) as *io::stream; + assert(io::write(f, input[..]) as size == 6); + io::close(f); + f = fs::open(memfs, "dir/file", fs::flags::RDONLY) as *io::stream; + assert(io::read(f, output) as size == 6); + assert(bytes::equal(input, output[..6])); + io::close(f); + //fs::rmdir(memfs, "dir") as fs::error; // errors::busy + fs::remove(memfs, "dir/file") as void; + fs::rmdir(memfs, "dir") as void; + + // fs::mksubdir, fs::subdir + fs::mksubdir(memfs, filename) as fs::error; // errors::exists + fs::subdir(memfs, filename) as fs::error; // fs::wrongtype + + let sub = mksubdir(memfs, "dir") as *fs::fs; + + let f = fs::create(sub, "file", 0, fs::flags::WRONLY) as *io::stream; + io::write(f, [42]); + io::close(f); + + let sub2 = fs::subdir(memfs, "dir") as *fs::fs; + assert(sub2 == sub); + fs::close(sub); + + let f = fs::open(sub2, "file", fs::flags::RDONLY) as *io::stream; + assert(io::read(f, output) as size == 1); + assert(output[0] == 42); + io::close(f); + + // fs::close + fs::close(memfs); + + // verify that subdirs can outlive parent dirs + let memsub2 = sub2: *inode; + fs::mkdir(sub2, "subdir") as void; + fs::rmdir(sub2, "subdir") as void; + assert(memsub2.opencount == 1); + assert(memsub2.parent == null); + fs::rmdirall(sub2, ""); + fs::close(sub2); +}; + +@test fn big_dir() void = { + let limit = 32z; + let memfs = memopen(); + for (let i = 0z; i < limit; i += 1) { + let f = fs::create(memfs, strconv::ztos(i), 0, fs::flags::RDWR); + io::close(f as *io::stream); + }; + let ino = memfs: *inode; + let dir = ino.data as directory; + assert(dir.sz == limit); + assert(len(dir.ents) > min_buckets); + + let it = fs::iter(memfs, "") as *fs::iterator; + defer free(it); + let count = 0z; + for (true) match (it.next(it)) { + void => break, + d: fs::dirent => count += 1, + }; + assert(count == limit); + + for (let i = 0z; i < limit; i += 1) { + fs::remove(memfs, strconv::ztos(i)); + }; + let ino = memfs: *inode; + let dir = ino.data as directory; + assert(len(dir.ents) == min_buckets); + assert(dir.sz == 0); + fs::close(memfs); +}; diff --git a/fs/mem/mem.ha b/fs/mem/mem.ha @@ -0,0 +1,276 @@ +// TODO: +// - Symlinks, hard links +// - More fs::flags +// - fs::stat_mask::INODE, ::*TIME + +use errors; +use fs; +use io; +use path; +use strings; + +type directory = struct { + ents: []nullable *inode, + sz: size, +}; + +type file = []u8; + +type inode = struct { + fs: fs::fs, + data: (directory | file), + name: str, + hash: u64, + next: nullable *inode, + opencount: size, + parent: nullable *inode, +}; + +type iterator = struct { + it: fs::iterator, + parent: *inode, + curr: nullable *inode, + idx: size, +}; + +const inode_iface: fs::fs = fs::fs { + close = &close, + create = &create, + iter = &iter, + mkdir = &mkdir, + mksubdir = &mksubdir, + open = &open, + remove = &remove, + rmdir = &rmdir, + stat = &stat, + subdir = &subdir, + ... +}; + +const fs_iter: fs::iterator = fs::iterator { next = &next, }; + +const supported_flags: fs::flags = ( + fs::flags::RDONLY | + fs::flags::WRONLY | + fs::flags::RDWR | + fs::flags::APPEND); + +// Returns the root of an new in-memory file system. The entire directory +// structure and files with metadata only exist in volatile memory. Arbitrary +// number of handles to the same directory simultaneously are allowed. Supports +// any number of readers or one writer at the same time on a file. +export fn memopen() *fs::fs = alloc(inode { + fs = inode_iface, + data = empty_dir(), + name = "", + opencount = 1, + parent = null, +}): *fs::fs; + +fn file_flags(flags: fs::flags...) ((io::mode, bool) | fs::error) = { + let fl: fs::flags = 0; + for (let i = 0z; i < len(flags); i += 1) { + if (flags[i] & supported_flags != flags[i]) { + return errors::unsupported; + }; + fl |= flags[i]; + }; + let appnd = fl & fs::flags::APPEND == fs::flags::APPEND; + let mode = switch (fl & (~fs::flags::APPEND)) { + fs::flags::RDONLY => io::mode::READ, + fs::flags::WRONLY => io::mode::WRITE, + fs::flags::RDWR => io::mode::RDWR, + * => abort("invalid flag combination"), + }; + return (mode, appnd); +}; + +fn create( + fs: *fs::fs, + path: str, + mode: fs::mode, + flags: fs::flags..., +) (*io::stream | fs::error) = { + let t = file_flags(flags...)?; + let mode = t.0, appnd = t.1; + + let parent = fs: *inode; + match (inode_find(parent, path)) { + errors::noentry => void, + * => return errors::exists, + }; + if (path::dirname(path) != path) { + parent = inode_find(parent, path::dirname(path))?; + }; + + let name = strings::dup(path::basename(path)); + let ino = alloc(inode { + name = name, + hash = hash_of(name), + data = []: []u8, + parent = parent, + }); + inode_insert(parent, ino); + return stream_open(ino, mode, appnd); +}; + +fn open( + fs: *fs::fs, + path: str, + flags: fs::flags..., +) (*io::stream | fs::error) = { + let t = file_flags(flags...)?; + let mode = t.0, appnd = t.1; + let ino = inode_find(fs: *inode, path)?; + if (ino.data is directory) { + return fs::wrongtype; + }; + return stream_open(ino, mode, appnd); +}; + +fn stat(fs: *fs::fs, path: str) (fs::filestat | fs::error) = { + return match(inode_find(fs: *inode, path)?.data) { + directory => fs::filestat { mode = fs::mode::DIR | 0o777, ... }, + f: file => fs::filestat { + mode = fs::mode::REG | 0o777, + mask = fs::stat_mask::SIZE, + sz = len(f), + }, + }; +}; + +fn mkdir(fs: *fs::fs, path: str) (void | fs::error) = { + let ino = mksubdir(fs, path)?: *inode; + ino.opencount = 0; + return void; +}; + +fn mksubdir(fs: *fs::fs, path: str) (*fs::fs | fs::error) = { + let parent = fs: *inode; + match (inode_find(parent, path)) { + errors::noentry => void, + * => return errors::exists, + }; + if (path::dirname(path) != path) { + parent = inode_find(parent, path::dirname(path))?; + }; + let name = strings::dup(path::basename(path)); + let ino = alloc(inode { + fs = inode_iface, + data = empty_dir(), + name = name, + hash = hash_of(name), + opencount = 1, + parent = parent, + }); + inode_insert(parent, ino); + return ino: *fs::fs; +}; + +fn subdir(fs: *fs::fs, path: str) (*fs::fs | fs::error) = { + let ino = inode_find(fs: *inode, path)?; + if (!(ino.data is directory)) { + return fs::wrongtype; + }; + ino.opencount += 1; + return ino: *fs::fs; +}; + +fn iter(fs: *fs::fs, path: str) (*fs::iterator | fs::error) = { + let ino = inode_find(fs: *inode, path)?; + if (!(ino.data is directory)) { + return fs::wrongtype; + }; + let p = ino.data: directory; + return alloc(iterator { + it = fs::iterator { next = &next, }, + parent = ino, + idx = 0, + curr = p.ents[0], + }): *fs::iterator; +}; + +fn next(iter: *fs::iterator) (fs::dirent | void) = match (_next(iter)) { + null => void, + ino: *inode => fs::dirent { + name = ino.name, + ftype = match (ino.data) { + directory => fs::mode::DIR, + file => fs::mode::REG, + }, + }, +}; + +fn _next(it: *fs::iterator) nullable *inode = { + let iter = it: *iterator; + if (iter.curr != null) { + let ino = iter.curr: *inode; + iter.curr = ino.next; + return ino; + }; + let p = iter.parent.data as directory; + iter.idx += 1; + for (iter.idx < len(p.ents)) match (p.ents[iter.idx]) { + null => iter.idx += 1, + ino: *inode => { + iter.curr = ino.next; + return ino; + }, + }; + return null; +}; + +fn rmdir(fs: *fs::fs, path: str) (void | fs::error) = { + let ino = inode_find(fs: *inode, path)?; + if (fs: *inode == ino) { + return errors::invalid; + }; + if (!(ino.data is directory)) { + return fs::wrongtype; + }; + let p = ino.data as directory; + if (ino.opencount != 0 || p.sz != 0) { + return errors::busy; + }; + unlink(ino.parent: *inode, ino); + inode_free(ino); +}; + +fn remove(fs: *fs::fs, path: str) (void | fs::error) = { + let ino = inode_find(fs: *inode, path)?; + if (!(ino.data is file)) { + return fs::wrongtype; + }; + unlink(ino.parent: *inode, ino); + if (ino.opencount == 0) { + inode_free(ino); + }; +}; + +fn close(fs: *fs::fs) void = { + let ino = fs: *inode; + if (!(ino.data is directory)) { + return fs::wrongtype; + }; + ino.opencount -= 1; + close_rec(ino); +}; + +fn close_rec(ino: *inode) void = { + if (ino.opencount != 0 || ino.parent != null) { + return; + }; + let it = iterator { it = fs_iter, parent = ino, ... }; + for (true) match (_next(&it: *fs::iterator)) { + null => break, + ino: *inode => { + ino.parent = null; + match (ino.data) { + file => inode_free(ino), + directory => close_rec(ino), + * => abort("unreachable"), + }; + }, + }; + inode_free(ino); +}; diff --git a/fs/mem/stream.ha b/fs/mem/stream.ha @@ -0,0 +1,91 @@ +use bufio; +use errors; +use fmt; +use fs; +use io; +use types; + +type stream = struct { + stream: io::stream, + source: *io::stream, + inode: *inode, + appnd: bool, +}; + +fn stream_open( + ino: *inode, + mode: io::mode, + appnd: bool, +) (*io::stream | fs::error) = { + let f = ino.data as file; + let s = alloc(stream { + stream = io::stream { + name = "<fs::mem::stream>", + closer = &stream_close, + seeker = &seek, + ... + }, + inode = ino, + appnd = appnd, + ... + }); + if (mode & io::mode::WRITE == 0) { + assert(mode & io::mode::READ == io::mode::READ); + s.stream.reader = &read; + if (ino.opencount == types::SIZE_MAX) { + return errors::busy; + }; + ino.opencount += 1; + s.source = bufio::fixed(f, io::mode::READ); + } else { + s.stream.writer = &write; + if (ino.opencount != 0) { + return errors::busy; + }; + ino.opencount = types::SIZE_MAX; + s.source = bufio::dynamic_from(f, mode); + if (!appnd) { + bufio::truncate(s.source); + }; + }; + io::seek(s.source, 0, io::whence::SET); + return &s.stream; +}; + +fn read(s: *io::stream, buf: []u8) (size | io::EOF | io::error) = { + return io::read((s: *stream).source, buf); +}; + +fn write(s: *io::stream, buf: const []u8) (size | io::error) = { + let s = s: *stream; + if (s.appnd) { + io::seek(s.source, 0, io::whence::END); + }; + let sz = io::write(s.source, buf)?; + s.inode.data = bufio::buffer(s.source); + return sz; +}; + +fn seek(s: *io::stream, off: io::off, w: io::whence) (io::off | io::error) = { + return io::seek((s: *stream).source, off, w); +}; + +fn stream_close(s: *io::stream) void = { + let s = s: *stream; + defer free(s); + if (s.stream.writer == null) { + io::close(s.source); + s.inode.opencount -= 1; + if (s.inode.opencount > 0) { + return; + }; + } else { + s.inode.opencount = 0; + bufio::finish(s.source); + }; + + if (s.inode.parent == null) { + // this stream was the last reference to this file, free it + inode_free(s.inode); + }; +}; diff --git a/fs/mem/util.ha b/fs/mem/util.ha @@ -0,0 +1,126 @@ +use errors; +use fs; +use hash::fnv; +use hash; +use path; +use strings; + +def min_buckets: size = 1 << 3; +def max_buckets: size = 1 << 24; + +fn ensure(parent: *inode) void = { + let dir = parent.data: directory; + let old = dir.ents; + let new_size = 0z; + if (dir.sz: u64 * 3u64 >= len(dir.ents): u64 * 4u64) { + new_size = len(dir.ents) << 1; + if (new_size > max_buckets) { + new_size = max_buckets; + }; + } else if (dir.sz: u64 * 10u64 < len(dir.ents): u64) { + new_size = len(dir.ents) >> 3; + if (new_size < min_buckets) { + new_size = min_buckets; + }; + } else { + return; + }; + dir.ents = alloc([], new_size); + for (let i = 0z; i < new_size; i += 1) { + append(dir.ents, null); + }; + parent.data = dir; + for (let i = 0z; i < len(old); i += 1) { + for (true) match (old[i]) { + null => break, + ino: *inode => { + old[i] = ino.next; + _inode_insert(parent, ino); + }, + }; + }; +}; + +fn inode_insert(parent: *inode, ino: *inode) void = { + ensure(parent); + _inode_insert(parent, ino); + let p = parent.data as directory; + p.sz += 1; + parent.data = p; +}; + +fn _inode_insert(parent: *inode, ino: *inode) void = { + let p = parent.data as directory; + let idx: size = ino.hash % len(p.ents): u64; + ino.next = p.ents[idx]; + p.ents[idx] = ino; + parent.data = p; +}; + +fn unlink(parent: *inode, ino: *inode) void = { + let p = parent.data as directory; + let prev = &p.ents[ino.hash % len(p.ents): u64]; + let it = *prev; + for (true) match (it) { + null => break, + ii: *inode => { + if (ii.hash == ino.hash && ii.name == ino.name) { + *prev = ii.next; + break; + }; + prev = &ii.next; + it = ii.next; + }, + }; + p.sz -= 1; + parent.data = p; + ensure(parent); +}; + +fn inode_free(ino: *inode) void = { + match (ino.data) { + d: directory => free(d.ents), + f: file => free(f), + }; + free(ino.name); + free(ino); +}; + +fn inode_find(dir: *inode, path: str) (*inode | fs::error) = { + if (path == "") { + return dir; + }; + let it = path::iter(path); + return find_rec(dir, path::next(&it) as str, &it); +}; + +fn find_rec(dir: *inode, name: str, it: *path::iterator) (*inode | fs::error) = { + let p = dir.data as directory; + let bucket = p.ents[hash_of(name) % len(p.ents): u64]; + for (true) match (bucket) { + null => break, + ino: *inode => { + if (name == ino.name) { + return match (path::next(it)) { + void => ino, + name: str => find_rec(ino, name, it), + }; + }; + bucket = ino.next; + }, + }; + return errors::noentry; +}; + +fn empty_dir() directory = directory { + ents = alloc([null...]: [min_buckets]nullable *inode), + sz = 0, +}; + +fn hash_of(name: str) u64 = { + let h = hash::fnv::fnv64a(); + defer hash::close(h); + hash::write(h, strings::toutf8(name)); + return hash::fnv::sum64(h); +}; + diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib @@ -292,6 +292,24 @@ fs() { gen_ssa fs io strings path time errors } +gensrcs_fs_mem() { + gen_srcs fs::mem \ + mem.ha \ + stream.ha \ + util.ha \ + $* +} + +fs_mem() { + if [ $testing -eq 0 ] + then + gensrcs_fs_mem + else + gensrcs_fs_mem +test.ha + fi + gen_ssa fs::mem bufio errors fs hash hash::fnv io path strconv strings +} + getopt() { gen_srcs getopt \ getopts.ha @@ -659,6 +677,7 @@ fmt format_elf format_xml fs +fs_mem getopt hare_ast hare_lex diff --git a/stdlib.mk b/stdlib.mk @@ -129,6 +129,9 @@ hare_stdlib_deps+=$(stdlib_format_xml) stdlib_fs=$(HARECACHE)/fs/fs.o hare_stdlib_deps+=$(stdlib_fs) +stdlib_fs_mem=$(HARECACHE)/fs/mem/fs_mem.o +hare_stdlib_deps+=$(stdlib_fs_mem) + stdlib_getopt=$(HARECACHE)/getopt/getopt.o hare_stdlib_deps+=$(stdlib_getopt) @@ -447,6 +450,18 @@ $(HARECACHE)/fs/fs.ssa: $(stdlib_fs_srcs) $(stdlib_rt) $(stdlib_io) $(stdlib_str @HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Nfs \ -t$(HARECACHE)/fs/fs.td $(stdlib_fs_srcs) +# fs::mem +stdlib_fs_mem_srcs= \ + $(STDLIB)/fs/mem/mem.ha \ + $(STDLIB)/fs/mem/stream.ha \ + $(STDLIB)/fs/mem/util.ha + +$(HARECACHE)/fs/mem/fs_mem.ssa: $(stdlib_fs_mem_srcs) $(stdlib_rt) $(stdlib_bufio) $(stdlib_errors) $(stdlib_fs) $(stdlib_hash) $(stdlib_hash_fnv) $(stdlib_io) $(stdlib_path) $(stdlib_strconv) $(stdlib_strings) + @printf 'HAREC \t$@\n' + @mkdir -p $(HARECACHE)/fs/mem + @HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Nfs::mem \ + -t$(HARECACHE)/fs/mem/fs_mem.td $(stdlib_fs_mem_srcs) + # getopt stdlib_getopt_srcs= \ $(STDLIB)/getopt/getopts.ha @@ -969,6 +984,9 @@ hare_testlib_deps+=$(testlib_format_xml) testlib_fs=$(TESTCACHE)/fs/fs.o hare_testlib_deps+=$(testlib_fs) +testlib_fs_mem=$(TESTCACHE)/fs/mem/fs_mem.o +hare_testlib_deps+=$(testlib_fs_mem) + testlib_getopt=$(TESTCACHE)/getopt/getopt.o hare_testlib_deps+=$(testlib_getopt) @@ -1293,6 +1311,19 @@ $(TESTCACHE)/fs/fs.ssa: $(testlib_fs_srcs) $(testlib_rt) $(testlib_io) $(testlib @HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Nfs \ -t$(TESTCACHE)/fs/fs.td $(testlib_fs_srcs) +# fs::mem +testlib_fs_mem_srcs= \ + $(STDLIB)/fs/mem/mem.ha \ + $(STDLIB)/fs/mem/stream.ha \ + $(STDLIB)/fs/mem/util.ha \ + $(STDLIB)/fs/mem/+test.ha + +$(TESTCACHE)/fs/mem/fs_mem.ssa: $(testlib_fs_mem_srcs) $(testlib_rt) $(testlib_bufio) $(testlib_errors) $(testlib_fs) $(testlib_hash) $(testlib_hash_fnv) $(testlib_io) $(testlib_path) $(testlib_strconv) $(testlib_strings) + @printf 'HAREC \t$@\n' + @mkdir -p $(TESTCACHE)/fs/mem + @HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Nfs::mem \ + -t$(TESTCACHE)/fs/mem/fs_mem.td $(testlib_fs_mem_srcs) + # getopt testlib_getopt_srcs= \ $(STDLIB)/getopt/getopts.ha