svf.cpp

Go to the documentation of this file.

 
#include <algorithm>
#include <cstring>
#include <iostream>
#include <iterator>
#include <sstream>
#include <set>
 
#include "svf.h"
 
namespace SVFS {
    static const char OVERWRITE_CHAR = '0';
 
    bool SparseVirtualFile::has(t_fpos fpos, size_t len) const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
 
        if (m_svf.empty()) {
            return false;
        }
        t_map::const_iterator iter = m_svf.upper_bound(fpos);
        if (iter != m_svf.begin()) {
            --iter;
        }
        t_fpos fpos_end = _file_position_immediatly_after_block(iter);
        if (fpos >= iter->first && (fpos + len) <= fpos_end) {
            return true;
        }
        return false;
    }
 
    void
    SparseVirtualFile::_throw_diff(t_fpos fpos, const char *data, t_map::const_iterator iter, size_t index_iter) const {
        assert(data);
        assert(iter != m_svf.end());
        assert(m_config.compare_for_diff);
 
        if (*data != iter->second.data[index_iter]) {
            std::ostringstream os;
            os << "SparseVirtualFile::write():";
            os << " Difference at position " << fpos;
            os << " '" << *(data) << "' != '" << iter->second.data[index_iter] << "'";
            os << " Ordinal " << static_cast<int>(*data) << " != " << static_cast<int>(iter->second.data[index_iter]);
            std::string str = os.str();
            throw Exceptions::ExceptionSparseVirtualFileDiff(str);
        }
        // Assert as this should now never be called is there is _not_ a diff.
        assert(0);
    }
 
    void SparseVirtualFile::_write_new_block(t_fpos fpos, const char *data, size_t len, t_map::const_iterator hint) {
        assert(m_svf.count(fpos) == 0);
 
        t_val new_value;
        new_value.data.reserve(len);
        new_value.block_touch = m_block_touch++;
        while (len) {
            new_value.data.push_back(*data);
            --len;
            ++data;
            ++m_bytes_total;
        }
        auto size_before_insert = m_svf.size();
        m_svf.insert(hint, {fpos, std::move(new_value)});
        // Sanity check that we really have added a new block (rather than replacing one).
        if (m_svf.size() != 1 + size_before_insert) {
            std::ostringstream os;
            os << "SparseVirtualFile::_write_new_block():";
            os << " Unable to insert new block at " << fpos;
            throw Exceptions::ExceptionSparseVirtualFileWrite(os.str());
        }
    }
 
    void SparseVirtualFile::_write_new_append_old(t_fpos fpos, const char *data, size_t len, t_map::iterator iter) {
        SVF_ASSERT(integrity() == ERROR_NONE);
        assert(data);
        assert(len > 0);
        assert(iter != m_svf.end());
        assert(iter->first > fpos);
 
        size_t fpos_start = fpos;
        size_t fpos_end = fpos + len;
        t_val new_value;
        new_value.block_touch = m_block_touch++;
 
        while (true) {
            while (len && fpos < iter->first) {
                // Copy new data 'X' up to start of iter.
                //       ^===========|  |=====|
                //  %XXXX+++++++++++++XX++|
                new_value.data.push_back(*data);
                ++data;
                ++fpos;
                --len;
                ++m_bytes_total;
            }
            size_t index_iter = 0;
            size_t delta = std::min(len, iter->second.data.size());
            // Check overlapped data matches 'Y'
            //       ^===========|  |=====|
            //  %++++YYYYYYYYYYYYY++++|
            if (m_config.compare_for_diff) {
                if (std::memcmp(iter->second.data.data(), data, delta) != 0) {
                    _throw_diff(fpos, data, iter, 0);
                }
            }
            for (size_t i = 0; i < delta; ++i) {
                new_value.data.push_back(*data);
                ++data;
            }
            fpos += delta;
            len -= delta;
            index_iter += delta;
            if (_file_position_immediatly_after_block(iter) > fpos_end) {
                // Copy rest of iter 'Z'
                assert(len == 0);
                //       ^=========ZZZ
                //  %+++++++++++++|
                // So append up to the end of iter and (maybe) go round again.
                while (index_iter < iter->second.data.size()) {
                    new_value.data.push_back(iter->second.data[index_iter]);
                    ++index_iter;
                }
                if (m_config.overwrite_on_exit) {
                    iter->second.data.assign(iter->second.data.size(), OVERWRITE_CHAR);
                }
                m_svf.erase(iter);
                break;
            }
            // Remove copied and checked old block and move on.
            if (m_config.overwrite_on_exit) {
                iter->second.data.assign(iter->second.data.size(), OVERWRITE_CHAR);
            }
            iter = m_svf.erase(iter);
            if (iter == m_svf.end() || iter->first > fpos + len) {
                // Copy rest of new and break
                while (len) {
                    new_value.data.push_back(*data);
                    ++data;
                    ++fpos;
                    --len;
                    ++m_bytes_total;
                }
                break;
            }
        }
        auto size_before_insert = m_svf.size();
        m_svf.insert({fpos_start, std::move(new_value)});
        if (m_svf.size() != 1 + size_before_insert) {
            std::ostringstream os;
            os << "SparseVirtualFile::write():";
            os << " Unable to insert new block at " << fpos_start;
            throw Exceptions::ExceptionSparseVirtualFileWrite(os.str());
        }
        assert(len == 0);
        assert(fpos == fpos_end);
        SVF_ASSERT(integrity() == ERROR_NONE);
    }
 
    void SparseVirtualFile::_write_append_new_to_old(t_fpos fpos, const char *new_data, size_t new_data_len,
                                                     t_map::iterator base_block_iter) {
        SVF_ASSERT(integrity() == ERROR_NONE);
        assert(new_data);
        assert(new_data_len > 0);
        assert(base_block_iter != m_svf.end());
        assert(fpos >= base_block_iter->first);
        assert(fpos <= _file_position_immediatly_after_block(base_block_iter));
 
#ifdef DEBUG
        size_t fpos_end = fpos + new_data_len;
#endif
        // Diff check against base_block_iter
        // Do the check to end of new_data_len or end of base_block_iter which ever comes first.
        // Do not increment m_bytes_total as this is existing new_data.
        // Diff check against base_block_iter
        size_t write_index_from_block_start = fpos - base_block_iter->first;
        // Do the check to end of new_data_len or end of base_block_iter which ever comes first.
        size_t len_check_or_copy = std::min(new_data_len,
                                            base_block_iter->second.data.size() - write_index_from_block_start);
        if (m_config.compare_for_diff) {
            if (std::memcmp(base_block_iter->second.data.data() + write_index_from_block_start, new_data,
                            len_check_or_copy) != 0) {
                _throw_diff(fpos, new_data, base_block_iter, write_index_from_block_start);
            }
        }
        new_data += len_check_or_copy;
        fpos += len_check_or_copy;
        new_data_len -= len_check_or_copy;
        t_map::iterator next_block_iter = std::next(base_block_iter);
        while (new_data_len) {
            if (next_block_iter == m_svf.end()) {
                // Termination case, copy remainder
                while (new_data_len) {
                    base_block_iter->second.data.push_back(*new_data);
                    ++new_data;
                    ++fpos;
                    --new_data_len;
                    m_bytes_total += 1;
                }
                break; // Done. Needed because we are going to do erase(next_block_iter) otherwise.
            } else {
                // Copy the new_data up to start of next_block_iter or, we have exhausted the new_data.
                while (new_data_len && fpos < next_block_iter->first) {
                    base_block_iter->second.data.push_back(*new_data);
                    ++new_data;
                    ++fpos;
                    --new_data_len;
                    m_bytes_total += 1;
                }
            }
            if (new_data_len == 0 and fpos < next_block_iter->first) {
                // We have exhausted new data and not reached the next block so we are done
                break;
            }
            // Still data to copy, and we are up against the next block which we will coalesce into the base_block_iter.
            write_index_from_block_start = 0;
            // Diff check, but also append to base_block_iter.
            // Do not increment m_bytes_total as this is existing data.
            len_check_or_copy = std::min(new_data_len, _file_position_immediatly_after_block(next_block_iter) - fpos);
            if (len_check_or_copy) {
                if (m_config.compare_for_diff) {
                    if (std::memcmp(next_block_iter->second.data.data(), new_data, len_check_or_copy) != 0) {
                        _throw_diff(fpos, new_data, base_block_iter, 0);
                    }
                }
                // We could push_back either the new_data or the existing next block data. We choose the former.
                for (size_t i = 0; i < len_check_or_copy; ++i) {
                    base_block_iter->second.data.push_back(*new_data);
                    ++new_data;
                    ++fpos;
                    --new_data_len;
                    ++write_index_from_block_start;
                }
            }
            // Here either new_data is exhausted or next_block_iter is.
            // If new_data is exhausted then copy remaining from next_block_iter to base_block_iter.
            // Do not increment m_bytes_total as this is existing new_data.
            if (new_data_len == 0) {
                while (write_index_from_block_start < next_block_iter->second.data.size()) {
                    base_block_iter->second.data.push_back(next_block_iter->second.data[write_index_from_block_start]);
                    ++write_index_from_block_start;
                }
            }
            // New data is not exhausted so erase next_block_iter as we have copied it and move on to the next block.
            if (m_config.overwrite_on_exit) {
                next_block_iter->second.data.assign(next_block_iter->second.data.size(), OVERWRITE_CHAR);
            }
            next_block_iter = m_svf.erase(next_block_iter);
        }
        base_block_iter->second.block_touch = m_block_touch++;
        assert(new_data_len == 0);
#ifdef DEBUG
        assert(fpos == fpos_end);
#endif
        SVF_ASSERT(integrity() == ERROR_NONE);
    }
 
    void SparseVirtualFile::write(t_fpos fpos, const char *data, size_t len) {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        // TODO: throw if !data, len == 0
        if (m_svf.empty() || fpos > _file_position_immediatly_after_end()) {
            // Simple insert of new data into empty map or a node beyond the end (common case).
            _write_new_block(fpos, data, len, m_svf.begin());
        } else {
            t_map::iterator iter = m_svf.upper_bound(fpos);
            if (iter != m_svf.begin()) {
                --iter;
            }
            if (iter->first > fpos) {
                // Insert new block, possibly coalescing existing blocks.
                // New comes earlier so either create a new block or copy existing block on to it.
                if (iter->first <= fpos + len) {
                    // Need to coalesce
                    _write_new_append_old(fpos, data, len, iter);
                } else {
                    // The new block precedes the old one
                    _write_new_block(fpos, data, len, iter);
                }
            } else {
                // Existing block.first is <= fpos
                if (fpos > _file_position_immediatly_after_block(iter)) {
                    // No overlap so just write new block after the last one
                    _write_new_block(fpos, data, len, m_svf.end());
                } else {
                    // Append new to existing block, possibly coalescing existing blocks.
                    _write_append_new_to_old(fpos, data, len, iter);
                }
            }
        }
        // Update internals.
        // NOTE: m_block_touch is incremented in one of the three actual write methods.
        m_count_write += 1;
        m_bytes_write += len;
        m_time_write = std::chrono::system_clock::now();
        SVF_ASSERT(integrity() == ERROR_NONE);
    }
 
    void SparseVirtualFile::read(t_fpos fpos, size_t len, char *p) {
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        SVF_ASSERT(integrity() == ERROR_NONE);
 
        if (m_svf.empty()) {
            throw Exceptions::ExceptionSparseVirtualFileRead(
                    "SparseVirtualFile::read(): Sparse virtual file is empty.");
        }
        t_map::iterator iter = m_svf.lower_bound(fpos);
        if (iter == m_svf.begin() && iter->first != fpos) {
            std::ostringstream os;
            os << "SparseVirtualFile::read():";
            os << " Requested file position " << fpos << " precedes first block at " << iter->first;
            throw Exceptions::ExceptionSparseVirtualFileRead(os.str());
        }
        size_t offset_into_block = 0;
        if (iter == m_svf.end() || iter->first != fpos) {
            --iter;
            offset_into_block = fpos - iter->first;
        }
        if (offset_into_block + len > iter->second.data.size()) {
            std::ostringstream os;
            os << "SparseVirtualFile::read():";
            os << " Requested position " << fpos << " length " << len;
            os << " (end " << fpos + len << ")";
            os << " overruns block that starts at " << iter->first << " has size " << iter->second.data.size();
            os << " (end " << iter->first + iter->second.data.size() << ").";
            os << " Offset into block is " << offset_into_block;
            os << " overrun is " << offset_into_block + len - iter->second.data.size() << " bytes";
            throw Exceptions::ExceptionSparseVirtualFileRead(os.str());
        }
        if (memcpy(p, iter->second.data.data() + offset_into_block, len) != p) {
            std::ostringstream os;
            os << "SparseVirtualFile::read():";
            os << " memcpy failed " << fpos << " length " << len;
            throw Exceptions::ExceptionSparseVirtualFileRead(os.str());
        }
        // Adjust non-const members
        iter->second.block_touch = m_block_touch++;
        m_bytes_read += len;
        m_count_read += 1;
        m_time_read = std::chrono::system_clock::now();
    }
 
    t_seek_reads SparseVirtualFile::need(t_fpos fpos, size_t len, size_t greedy_length) const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        return _need_no_lock(fpos, len, greedy_length);
    }
 
    t_seek_reads SparseVirtualFile::_need_no_lock(t_fpos fpos, size_t len, size_t greedy_length) const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
        if (m_svf.empty()) {
            return {{fpos, greedy_length > len ? greedy_length : len}};
        }
        size_t original_len = len;
        t_fpos fpos_to = fpos + len;
        t_seek_reads ret;
        t_map::const_iterator iter = m_svf.upper_bound(fpos);
        if (iter == m_svf.begin()) {
            if (fpos + len <= iter->first) {
                //        ^==|
                //   |+++|
                ret.push_back({fpos, len});
                fpos += len;
                // Mark that we are done.
                len = 0;
            }
        } else {
            // Otherwise check the previous node with std::prev.
            auto last_fpos = _file_position_immediatly_after_block(std::prev(iter));
            if (fpos < last_fpos) {
                // Example, change:
                //        |==|    ^==|
                //         |++++++++++++|
                // to:
                //            |+++++++++|
                len -= std::min(len, last_fpos - fpos);
                fpos = std::min(fpos_to, last_fpos);
            }
        }
        // Now walk through the remaining nodes until we have exhausted the read.
        while (len) {
            if (iter == m_svf.end() || fpos + len <= iter->first) {
                // Either:
                //   |==|
                //         |++++++++++++|
                // or:
                //              |==|
                //   |+++++|
                ret.emplace_back(fpos, len);
                fpos += len;
                len = 0;
                break;
            }
            // We are in this state:
            //          ^=====|
            //     |++++++++++++++|
            // or:
            //          ^=====|
            //     |++++++++|
            if (fpos < iter->first) {
                assert(len >= iter->first - fpos);
                auto bytes_added = iter->first - fpos;
                ret.emplace_back(fpos, bytes_added);
                len -= bytes_added;
                fpos += bytes_added;
            }
            // We are now in this state:
            //          ^=====|
            //          |+++++++|
            // or:
            //          ^=====|
            //          |++++|
            assert(fpos == iter->first);
            if (fpos + len <= _file_position_immediatly_after_block(iter)) {
                //          ^======|
                //          |++++|
                fpos += len;
                len = 0;
                break;
            } else {
                //          ^======|
                //          |+++++++++|
                fpos += iter->second.data.size();
                len -= iter->second.data.size();
            }
            ++iter;
        }
        assert(fpos == fpos_to);
        assert(len == 0);
        if (greedy_length && greedy_length > original_len && !ret.empty()) {
            ret = _minimise_seek_reads(ret, greedy_length);
        }
        return ret;
    }
 
    t_seek_reads SparseVirtualFile::need_many(t_seek_reads &seek_reads, size_t greedy_length) const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
 
        std::sort(seek_reads.begin(), seek_reads.end());
        if (m_svf.empty()) {
            return _minimise_seek_reads(seek_reads, greedy_length);
        }
        t_seek_reads ret;
        for (const auto &iter_seek_read: seek_reads) {
            for (const auto &iter_need: _need_no_lock(iter_seek_read.first, iter_seek_read.second, 0)) {
                ret.emplace_back(iter_need);
            }
        }
        return _minimise_seek_reads(ret, greedy_length);
    }
 
    size_t SparseVirtualFile::_amount_to_read(t_seek_read iter, size_t greedy_length) noexcept {
        return iter.second > greedy_length ? iter.second : greedy_length;
    }
 
    t_seek_reads
    SparseVirtualFile::_minimise_seek_reads(const t_seek_reads &seek_reads, size_t greedy_length) noexcept {
 
        t_seek_reads new_seek_reads;
        for (const t_seek_read &seek_read: seek_reads) {
            if (new_seek_reads.empty()) {
                // Add the first greedy block
                new_seek_reads.emplace_back(seek_read.first, _amount_to_read(seek_read, greedy_length));
            } else {
                // Compare with last new block
                auto last_iter_of_new = new_seek_reads.end();
                --last_iter_of_new;
                if (seek_read.first > last_iter_of_new->first + last_iter_of_new->second) {
                    // Add a new greedy block
                    new_seek_reads.emplace_back(seek_read.first, _amount_to_read(seek_read, greedy_length));
                } else if (seek_read.first + seek_read.second > last_iter_of_new->first + last_iter_of_new->second) {
                    // Extend last block
                    last_iter_of_new->second +=
                            (seek_read.first + seek_read.second) - (last_iter_of_new->first + last_iter_of_new->second);
                } // Otherwise do nothing, it is covered by greedy.
            }
        }
        return new_seek_reads;
    }
 
    t_seek_reads SparseVirtualFile::blocks() const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
 
        t_seek_reads ret;
        for (const auto &iter: m_svf) {
            ret.emplace_back(iter.first, iter.second.data.size());
        }
        return ret;
    }
 
    size_t SparseVirtualFile::block_size(t_fpos fpos) const {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
 
        if (m_svf.empty()) {
            throw Exceptions::ExceptionSparseVirtualFileRead(
                    "SparseVirtualFile::block_size(): Sparse virtual file is empty.");
        }
        t_map::const_iterator iter = m_svf.find(fpos);
        if (iter == m_svf.end()) {
            std::ostringstream os;
            os << "SparseVirtualFile::block_size():";
            os << " Requested file position " << fpos << " is not at the start of a block";
            throw Exceptions::ExceptionSparseVirtualFileRead(os.str());
        }
        return iter->second.data.size();
    }
 
    size_t SparseVirtualFile::size_of() const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        size_t ret = sizeof(SparseVirtualFile);
 
        // Add heap referenced data sizes.
        ret += m_id.size();
        for (const auto &iter: m_svf) {
            ret += sizeof(iter.first);
            ret += sizeof(iter.second);
            ret += iter.second.data.size();
        }
        return ret;
    }
 
    void SparseVirtualFile::clear() noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        // Maintain ID and constructor arguments.
//        m_time_write = std::chrono::time_point<std::chrono::system_clock>::min();
//        m_time_read = std::chrono::time_point<std::chrono::system_clock>::min();
        if (m_config.overwrite_on_exit) {
            for (auto &iter: m_svf) {
                iter.second.data.assign(iter.second.data.size(), OVERWRITE_CHAR);
            }
        }
        m_svf.clear();
        m_bytes_total = 0;
        m_count_write = 0;
        m_count_read = 0;
        m_bytes_write = 0;
        m_bytes_read = 0;
        SVF_ASSERT(integrity() == ERROR_NONE);
    }
 
    size_t SparseVirtualFile::_erase_no_lock(t_fpos fpos) {
        SVF_ASSERT(integrity() == ERROR_NONE);
 
        auto iter = m_svf.find(fpos);
        if (iter == m_svf.end()) {
            std::ostringstream os;
            os << "SparseVirtualFile::erase():";
            os << " Non-existent file position " << fpos << " at start of block.";
            throw Exceptions::ExceptionSparseVirtualFileErase(os.str());
        }
        size_t ret = iter->second.data.size();
        m_bytes_total -= ret;
        m_svf.erase(iter);
        m_blocks_erased++;
        m_bytes_erased += ret;
        return ret;
    }
 
    size_t SparseVirtualFile::erase(t_fpos fpos) {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        return _erase_no_lock(fpos);
    }
 
    SparseVirtualFile::ERROR_CONDITION
    SparseVirtualFile::integrity() const noexcept {
        t_fpos prev_fpos = 0;
        size_t prev_size = 0;
        t_map::const_iterator iter = m_svf.begin();
        size_t byte_count = 0;
        std::set<t_block_touch> block_touches;
 
        while (iter != m_svf.end()) {
            if (iter->second.data.empty()) {
                return ERROR_EMPTY_BLOCK;
            }
            if (iter != m_svf.begin()) {
                if (prev_fpos == iter->first && prev_size == iter->second.data.size()) {
                    return ERROR_DUPLICATE_BLOCK;
                }
                if (prev_fpos + prev_size == iter->first) {
                    return ERROR_ADJACENT_BLOCKS;
                }
                if (prev_fpos + prev_size > iter->first) {
                    return ERROR_BLOCKS_OVERLAP;
                }
            }
            if (block_touches.find(iter->second.block_touch) != block_touches.end()) {
                // Duplicate block_touches value
                return ERROR_DUPLICATE_BLOCK_TOUCH;
            }
            prev_fpos = iter->first;
            prev_size = iter->second.data.size();
            byte_count += prev_size;
            ++iter;
        }
        if (byte_count != m_bytes_total) {
            return ERROR_BYTE_COUNT_MISMATCH;
        }
        return ERROR_NONE;
    }
 
    t_fpos
    SparseVirtualFile::last_file_position() const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        return _file_position_immediatly_after_end();
    }
 
    [[nodiscard]] t_block_touches SparseVirtualFile::_block_touches_no_lock() const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
        t_block_touches ret;
        for (const auto &iter: m_svf) {
            // The block_touch should not be in the return value, yet.
            assert(ret.find(iter.second.block_touch) == ret.end());
            ret[iter.second.block_touch] = iter.first;
        }
        return ret;
    }
 
    [[nodiscard]] t_block_touches SparseVirtualFile::block_touches() const noexcept {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        return _block_touches_no_lock();
    }
 
    size_t SparseVirtualFile::lru_punt(size_t cache_size_upper_bound) {
        SVF_ASSERT(integrity() == ERROR_NONE);
#ifdef SVF_THREAD_SAFE
        std::lock_guard<std::mutex> mutex(m_mutex);
#endif
        size_t ret = 0;
        if (m_svf.size() > 1 and m_bytes_total >= cache_size_upper_bound) {
            auto touch_fpos_map = _block_touches_no_lock();
            for (const auto &iter: touch_fpos_map) {
                if (m_svf.size() > 1 and m_bytes_total >= cache_size_upper_bound) {
                    ret += _erase_no_lock(iter.second);
                    m_blocks_punted++;
                } else {
                    break;
                }
            }
        }
        m_bytes_punted += ret;
        return ret;
    }
 
    t_fpos
    SparseVirtualFile::_file_position_immediatly_after_end() const noexcept {
        if (m_svf.empty()) {
            return 0;
        } else {
            auto iter = m_svf.end();
            --iter;
            return _file_position_immediatly_after_block(iter);
        }
    }
 
    t_fpos
    SparseVirtualFile::_file_position_immediatly_after_block(t_map::const_iterator iter) const noexcept {
        // NOTE: do not SVF_ASSERT(integrity() == ERROR_NONE); as integrity() calls this so infinite recursion.
        assert(iter != m_svf.end());
 
        auto ret = iter->first + iter->second.data.size();
        return ret;
    }
 
} // namespace SVFS