For now, only transaction blocks are sensitive to the residual values on them, so we should zero before using them.

According to the profiling, opening a file takes ~1 us but setting up other related stuff takes ~9 us, which mostly comes from page fault and mapping shared memory bitmaps (even more costly than replaying the tx history).

Thus, as an optimization, if a file is not meant for writing, there is no need to open shared memory. This should significantly reduce the overhead of open for read-only files and *stat.

With Spin Lock

For single-threaded 4k overwrite, spin lock takes ~18.88% of the overall execution time:

BENCH_NUM_ITER=1000000 ./run bench profile --prog_args="--benchmark_filter='overwrite/4096/.*/threads:1$'"

Specifically, the lock instruction takes the majority of the time in pthread_spin_lock

Without Spin Lock

When the spinlock is commented out, ~18.33% of the time is spent on BlkTable::update, and ~16.31% of the time is on the method itself (as opposed to the function it calls e.g., advance_tx_idx).

Within BlkTable::update, ~55.56% of the time is spent on the line if (tx_idx) *tx_idx = tail_tx_idx;

To support garbage collection (i.e. remove) on shared memory objects, the key is to figure out how many processes are still referring to this shared memory object. Maintaining a reference counter on the shared memory seems ad hoc as it cannot handle failure. Here is the proposal for implementing garbage collection for shared memory objects:

• every process that opens the shared memory file acquires a shared flock
• the garbage collection process attempts to acquire an exclusive lock with a non-blocking flag; if acquire succeeds, this means no process is using it, and we should be free to delete it; otherwise do not touch it

This is just a tentative proposal. There surely be other issues to handle i.e. the race condition between acquiring flock and open, etc. We only consider this proposal after DRAM bitmaps are fully functional.

In the current implementation of persist operation, there is only one fence:

static inline void persist_cl_fenced(void *p) {
  persist_cl_unfenced(p);
  _mm_sfence();
}

The problem is, people typically update the cache line *p, and then call persist. persist should have a fence before flushing so that operations on *p won't get reordered after the flush.

In the current implementation, the process that creates the file is responsible to initialize the file. To avoid the race condition, every process who doesn't think it has creator responsibility will check and spin until the first bit of bitmap in the metablock is 1 (this bit indicates the metablock itself is taken). However, it could be the case that a process may create and die, leaving the file layout uninitialized. We may need to use flock instead of the first bit of bitmap to handle this race condition.

A few thoughts on how to implement GC when there are still other processes running:

• As discussed previously, we could move blocks at the end of the file to fill holes in the middle. Let' call it relocation. For the blocks that are organized as linked lists (e.g. LogEntryBlock), we could use an RCU to atomically relocate the block: copy it to the hole and CAS to update the pointer pointing to it.
• To relocate DataBlock, we must scan through the log (and clean up dead log entries too), since the log will contain pointer points to DataBlock.
• In MetaBlock, we maintain a gc_clock, which is a logical clock (or version number, if this is a better term); every time a GC completes, increase gc_clock by one. In the current block allocation, every process will always try to allocate from the recent bitmap it has successfully allocated; if fails, then try to allocate from the next bitmap, so bitmaps are searched in increasing order. When a process fails to allocate blocks from the last bitmap, it then tries to extend the bitmap. Now that we gc_clock, the process could compare it to the last gc_clock it has seen. If it is mismatched, it means a new GC happened so instead of extending the file, it tries to rescan all the bitmap from the head.

Since we have already collected everything we need during open.

In the previous discussion, we consider organizing bitmaps as a linked list. It turns out that, when all bitmaps are marked as taken, it is liked we have to call ftruncate to extend the file and put the new bitmap as the next block. This works fine, but there could be an easier implementation: a bitmap block contains 32k bits, which maintains 128M blocks. We could instead just claims that for every 128M blocks, the first block is always a bitmap block. This saves the effort to organize things into a linked list, and it might be easier for GC.

./run bench_append

For APIs like ftruncate that we did not support yet but would hurt the file integrity, it's better to hook them up and throw exceptions so that we could capture the issue.

Currently, bitmap is persistent on PM, but since we are going to scan through the tx log to rebuild the image during open, we can always know the bitmap latest state from the shared memory. The idea is, when the first process open the file, it creates a shared memory object and leaves this object name in the meta block. Later processes could just check the meta block to open the same shared memory for bitmap.

By moving the bitmap to DRAM, we get additional benefits:

• no need for cache line flush during allocation.
• no GC is needed for allocated (by some processed) but unused block. Just remove the shared memory (when no one is opening the file) and ask the next one to open it to rebuild the bitmap image. GC is only needed for TX and Log block. GC for these two blocks are easier because we could just dump the new image into a new log and switch the pointer in meta block to the new log. Then we discard everything in the old log.

There is also additional attention needed:

• How to name the shared memory object. Probably not just filename because rename may mess things up. Some version number or timestamp might be perferred.

Probably wrap them into something like util.h? SplitFS and NOVA should be good references.

As Mike suggested, we flush the cache line in the tx block every time using up the whole cache line; this helps for fsync latency.

The test case failed when we call pwrite NUM_INLINE_TX_ENTRY / 2 = 120 times

https://github.com/ShawnZhong/uLayFS/blob/8370c61c3964354326b68275c45c5477f482c93a/test/test_rw.cpp#L24-L26

Since fclose bypass glibc and directly call into syscall close, we have to intercept fclose too. However, in the current implementation, we only close the fd but don't flush FILE stream.

Reference implementation can be found here.

Block local index is used to index into an offset within a block, so it typically only requires 12 bits. The current implementation uses int32_t, which might be wasteful in the case of using a container of block local index.

Specifically we may modify get_coverage and handle_conflict

The block index is of type uint32_t, but commonly we have idx << BLOCK_SHIFT to get file size. This would result in overflow if the file size is larger than 4G.

To fix it, we could add another macro or inline function idx_to_block_size with casting block index into uint64_t first and then perform shifting.

The tricky piece of read/write (in contrast to pread and pwrite) is, changing file offset would imply a serialization point while OCC will pick another serialization point. Such divergence could result in anomalies.

The easiest way to resolve it is to use a lock for file offset. A multithreaded program that has concurrent read/write on a file usually uses pread and pwrite instead.

A better solution is to fully exploit OCC: in BlkTable.update, a thread A acquires the current offset and the last offset-changing thread's tx tail. Then it performs its IO, commits, and leaves the tx tail it has seen (this is the serialization point). Another thread B that does IO concurrently should see A's offset changing and A does not finish (probably implemented as a ticket lock etc); B could proceed and when it is about to commit, it must ensure A has already committed and it must ensure its' commit is after A.

Ref: https://github.com/ShawnZhong/uLayFS/runs/4735546543?check_suite_focus=true#logs
Also check why CI does not fail

In the current implementation, num_blocks and file_size are in the first cache line of the meta block, but these two fields are written often, while the other fields are mostly read-only. It might be a good idea to move these two fields to the second cache line because these two fields' change usually require meta_lock held.

  union {
    struct {
      // file signature
      char signature[SIGNATURE_SIZE];

      // file size in bytes (logical size to users)
      uint64_t file_size;

      // total number of blocks actually in this file (including unused ones)
      uint32_t num_blocks;

      // if inline_tx_entries is used up, this points to the next log block
      LogicalBlockIdx next_tx_block;

      // hint to find tx log tail; not necessarily up-to-date
      TxEntryIdx tx_log_tail;
    };

    // padding avoid cache line contention
    char cl1[CACHELINE_SIZE];
  };

  union {
    // address for futex to lock, 4 bytes in size
    // this lock is ONLY used for ftruncate
    Futex meta_lock;

    // set futex to another cacheline to avoid futex's contention affect
    // reading the metadata above
    char cl2[CACHELINE_SIZE];
  };

We plan to make some data structures shared by threads e.g. mem_table. These data structures should be thread-safe.

For BlkTable, we probably use some spin lock to avoid multiple update happening.

ref: https://github.com/ShawnZhong/uLayFS/runs/4754646094?check_suite_focus=true (first attempt)

For now, there are some unknown scalability bottlenecks:

1. When trying to commit to the global timeline log, multiple processes might result in contention of the log tail.
2. In a strict mode when every process might apply the newest log entries detected in every read operation: once a process publishes its transaction by committing it to the global timeline log, other processes would see it and try to read this log and apply it. This would cause a huge amount of traffic to read the cacheline that holding the log entries.

1 is yet an open question. One possible solution is to introduce partial ordering, but might be too complicated and out of the scope.
2 is possible to alleviate: once a process commits its log entries to the global timeline, it prefers to use another cacheline to write its next log entries. This will leave the previous cacheline holding the log entries untouched and shared-read by other processes.

Otherwise, there could be a race condition that calling get_tail_tx is not what update seen.

See output at https://github.com/ShawnZhong/uLayFS/runs/4053312753?check_suite_focus=true

After calling pwrite 119 times, the number of logical blocks grows to 1536 whereas there are only 9 virtual blocks used.

Note @chenhao-ye : you don't need to change anything for now, we should do measurement (profiling) first.

For zero_init, we currently have the following logic:

• For each cacheline:
  • memcmp
  • memset
  • persist
• fence

First, it might not be desirable to do the for loop in cache line granularity as pmem internally uses 256 bytes granularity. Second, it may unnecessarily pollute the cache with a bunch of zero cache lines.

It would be desirable to follow how PMDK handles this at https://pmem.io/2019/01/22/extended-memcpy.html.

The logic is simple - if a modification is smaller than 256 bytes (configurable using PMEM_MOVNT_THRESHOLD environment variable) they use normal mov instructions followed by pmem_flush, but for modifications of 256 bytes or more they use non-temporal (NT) stores. These instructions on x86_64 have 2 properties - they bypass CPU caches (so that pmem_flush is not needed) and treat destination memory as write-combining type. The latter property means that if the destination memory is not in the cache, the CPU doesn’t have to fetch full cache lines, only to flush them a moment later. This is important not because data is not stored in the cache, but because there’s no fetch of previous data. This means that application can update the same cache lines multiple times without waiting for them to be available for reading.

In the current implementation of Futex:

  void acquire() {
    atomic_thread_fence(std::memory_order_acquire);
    while (true) {
      uint32_t one = 1;
      __atomic_compare_exchange_n(&val, &one, 0, true, __ATOMIC_ACQ_REL,
                                  __ATOMIC_ACQUIRE);

      long rc = futex(&val, FUTEX_TRYLOCK_PI, 0, nullptr, nullptr, 0);
      if (errno == EAGAIN) continue;
      if (rc == -1) perror("futex-acquire");
      return;
    }
  }

  void release() {
    val = 0;
    long rc = futex(&val, FUTEX_WAKE, 1, nullptr, nullptr, 0);
    if (rc == -1) perror("futex-release");
    atomic_thread_fence(std::memory_order_release);
  }

These fence functions might not be necessary, given that we call into kernel anyway. In addition, __atomic_compare_exchange_n here looks weird because we are going to make futex syscall anyway... Maybe some revisit of this piece of code is necessary.

Design:

Base struct is struct LogEntry of size 8 bytes. Two subtypes:

• LogHeadEntry stores:
  • bool overflow (1 bit -- true if there is an overflow segment in another LogBlock following me)
  • bool saturate (1 bit -- true if the current segment fills the current LogBlock; overflow implies saturate)
  • op (2 bits)
  • leftover_bytes (12 bits -- previously last_remaining)
  • leftover_blocks (8 bits -- 6 bits is actually enough, max 64)
  • num_local_entries (8 bits -- number of local body entries of this segment inside my LogBlock)
  • union next (4 bytes, content depends on the value of saturate)
    • if !saturate, stores LogLocalIdx next_local_idx : 8 -- block idx is the same as mine
    • if saturate, stores LogicalBlockIdx next_block_idx : 32 -- local idx must be zero
• LogBodyEntry: stores begin_virtual_idx (4 bytes) and begin_logical_idx (4 bytes).

The idea behind the union is to pack LogHeadEntry within 8 bytes in all cases. We need either next_local_idx or next_block_idx to locate the next header, but not both, depending on the value of saturate.

Without the saturate indicator and the union, it is not possible to support the case where there is no overflow segment after me (so I must store the leftover_* numbers) but I'm also filling up the current LogBlock (so I must store the 4-byte next block idx).

See https://github.com/ShawnZhong/uLayFS/runs/4670721281

This will save one more mutex operation.

There are some OS configurations for the huge page.

We need to add a script to set up huge page, and enable BuildOptions::use_hugepage

The first block index returned by the allocator is 64.

Current Impl

As talked with @chenhao-ye, the current organization of thread-local data structure is as follows:

• Per-process data structures are maintained in a mapping fd -> file.

• Per-thread data structures are maintained in thread-local mappings: fd -> allocator and fd ->log_mgr. A thread-local object is inserted into the mapping the first time the thread accesses the file.

Upon receiving a write request, we would have 3 look-ups: 1 from the global files, and 2 from the thread-local mappings. And the number could increase if we have more thread-local data structures. (I think TxMgr could be made thread-local as well?):

• From the global files map, look up the file instance
• Look up the thread-local allocator from allocators
• Look up the thread-local log_mgr from log_mgrs

Alternative Impl

An alternative implementation would be the following:

• Have a per-thread mapping of type thread_local std::unordered_map<int, File> where File contains all the information about a file. Some fields are local to the thread, and some fields are pointers to the per-process data structure (see below), such as mem_table and blk_table.

• Have a per-process mapping tbb::concurrent_unordered_map<int, SharedFile> where SharedFile stores the shared data structure, including mem_table and blk_table.

Upon opening a file, the thread:

• emplace a SharedFile to the global mapping
• create a local File object, and insert it into the local mapping

Upon reading a file, the thread:

• looks up the local mapping to find the file
• if not found, the thread needs to look up the global data structure for the corresponding SharedFile and insert the File into local mapping.

In this case, a write request can be handled with only 1 lookup most of the time.

Hi, out of experimentation I tried compiling MadFS on GitHub Codespaces (hoping to then write a mini CI that just tries to verify whether MadFS compiles on the ubuntu-latest GitHub runner).

Is this error expected? If not then I believe an explicit cast might be needed.

@osalbahr ➜ /workspaces/MadFS (main) $ make BUILD_TARGETS="madfs"
cmake -S . -B build-release -DCMAKE_BUILD_TYPE=release 
-- Configuring done
-- Generating done
-- Build files have been written to: /workspaces/MadFS/build-release
cmake --build build-release -j --target madfs -- --quiet 
[ 72%] Built target pmem2
[ 74%] Building CXX object CMakeFiles/madfs.dir/src/file/write.cpp.o
[ 75%] Building CXX object CMakeFiles/madfs.dir/src/file/read.cpp.o
In file included from /workspaces/MadFS/src/tx/write.h:3,
                 from /workspaces/MadFS/src/tx/write_aligned.h:1,
                 from /workspaces/MadFS/src/file/write.cpp:2:
/workspaces/MadFS/src/tx/tx.h: In member function ‘bool madfs::dram::Tx::handle_conflict(madfs::pmem::TxEntry, madfs::VirtualBlockIdx, madfs::VirtualBlockIdx, std::vector<madfs::BaseIdx<unsigned int, madfs::IdxType::LOGICAL_BLOCK_IDX> >&, bool*)’:
/workspaces/MadFS/src/tx/tx.h:109:78: error: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Werror=sign-conversion]
  109 |         VirtualBlockIdx end_vidx = curr_entry.inline_entry.begin_virtual_idx +
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
  110 |                                    curr_entry.inline_entry.num_blocks;
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~         
In file included from /workspaces/MadFS/src/tx/read.h:3,
                 from /workspaces/MadFS/src/file/read.cpp:1:
/workspaces/MadFS/src/tx/tx.h: In member function ‘bool madfs::dram::Tx::handle_conflict(madfs::pmem::TxEntry, madfs::VirtualBlockIdx, madfs::VirtualBlockIdx, std::vector<madfs::BaseIdx<unsigned int, madfs::IdxType::LOGICAL_BLOCK_IDX> >&, bool*)’:
/workspaces/MadFS/src/tx/tx.h:109:78: error: conversion to ‘unsigned int’ from ‘int’ may change the sign of the result [-Werror=sign-conversion]
  109 |         VirtualBlockIdx end_vidx = curr_entry.inline_entry.begin_virtual_idx +
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
  110 |                                    curr_entry.inline_entry.num_blocks;
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~         
cc1plus: all warnings being treated as errors
make[4]: *** [CMakeFiles/madfs.dir/build.make:102: CMakeFiles/madfs.dir/src/file/read.cpp.o] Error 1
make[4]: *** Waiting for unfinished jobs....
cc1plus: all warnings being treated as errors
make[4]: *** [CMakeFiles/madfs.dir/build.make:141: CMakeFiles/madfs.dir/src/file/write.cpp.o] Error 1
make[3]: *** [CMakeFiles/Makefile2:365: CMakeFiles/madfs.dir/all] Error 2
make[2]: *** [CMakeFiles/Makefile2:372: CMakeFiles/madfs.dir/rule] Error 2
make[1]: *** [Makefile:236: madfs] Error 2
make: *** [Makefile:16: release] Error 2

Might be related: