| // Copyright 2022 The Fuchsia Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #ifndef SRC_STORAGE_F2FS_FILE_CACHE_H_ | |
| #define SRC_STORAGE_F2FS_FILE_CACHE_H_ | |
| #include <condition_variable> | |
| #include <utility> | |
| #include <fbl/intrusive_double_list.h> | |
| #include <fbl/intrusive_wavl_tree.h> | |
| #include <safemath/checked_math.h> | |
| #include "src/storage/f2fs/common.h" | |
| namespace f2fs { | |
| class F2fs; | |
| class Page; | |
| class VnodeF2fs; | |
| class FileCache; | |
| class LockedPage; | |
| class VmoManager; | |
| constexpr pgoff_t kPgOffMax = std::numeric_limits<pgoff_t>::max() / kBlockSize; | |
| using PageCallback = fit::function<zx_status_t(fbl::RefPtr<Page>)>; | |
| using PageTaggingCallback = fit::function<zx_status_t(fbl::RefPtr<Page>, bool is_last_page)>; | |
| using PageList = fbl::SizedDoublyLinkedList<fbl::RefPtr<Page>>; | |
| enum class PageFlag { | |
| kPageUptodate = | |
| 0, // It is uptodate. No need to read blocks from disk if the backing page is present. | |
| kPageDirty, // It needs to be written out. | |
| kPageWriteback, // It is under writeback. | |
| kPageVmoLocked, // Its vmo is locked. It should not be subject to reclaim. | |
| kPageActive, // Its reference count > 0 | |
| kPageColdData, // It is subject to gc. | |
| kPageCommit, // It is logged with pre-flush and flush. | |
| kPageSync, // It is logged with flush. | |
| kPageFlagSize, | |
| }; | |
| // It defines a writeback operation. | |
| struct WritebackOperation { | |
| pgoff_t start = 0; // All dirty Pages within the range of [start, end) are subject to writeback. | |
| pgoff_t end = kPgOffMax; | |
| pgoff_t to_write = kPgOffMax; // The number of dirty Pages to be written. | |
| bool bSync = false; // If true, FileCache::Writeback() waits for writeback Pages to be | |
| // written to disk. | |
| bool bReclaim = | |
| false; // If true, it releases inactive Pages while traversing FileCache::page_tree_. | |
| VnodeCallback if_vnode = nullptr; // If set, it determines which vnodes are subject to writeback. | |
| PageCallback if_page = nullptr; // If set, it determines which Pages are subject to writeback. | |
| PageTaggingCallback page_cb = | |
| nullptr; // If set, it can touch every page subject to writeback before disk I/O. It is used | |
| // to set flags or update footer for fsync() or checkpoint(). | |
| }; | |
| template <typename T, bool EnableAdoptionValidator = ZX_DEBUG_ASSERT_IMPLEMENTED> | |
| class PageRefCounted : public fs::VnodeRefCounted<T> { | |
| public: | |
| PageRefCounted(const Page &) = delete; | |
| PageRefCounted &operator=(const PageRefCounted &) = delete; | |
| PageRefCounted(const PageRefCounted &&) = delete; | |
| PageRefCounted &operator=(const PageRefCounted &&) = delete; | |
| using ::fbl::internal::RefCountedBase<EnableAdoptionValidator>::IsLastReference; | |
| protected: | |
| constexpr PageRefCounted() = default; | |
| ~PageRefCounted() = default; | |
| }; | |
| class Page : public PageRefCounted<Page>, | |
| public fbl::Recyclable<Page>, | |
| public fbl::WAVLTreeContainable<Page *>, | |
| public fbl::DoublyLinkedListable<fbl::RefPtr<Page>> { | |
| public: | |
| Page() = delete; | |
| Page(FileCache *file_cache, pgoff_t index); | |
| Page(const Page &) = delete; | |
| Page &operator=(const Page &) = delete; | |
| Page(const Page &&) = delete; | |
| Page &operator=(const Page &&) = delete; | |
| virtual ~Page(); | |
| void fbl_recycle() { RecyclePage(); } | |
| pgoff_t GetKey() const { return index_; } | |
| pgoff_t GetIndex() const { return GetKey(); } | |
| VnodeF2fs &GetVnode() const; | |
| FileCache &GetFileCache() const; | |
| VmoManager &GetVmoManager() const; | |
| // If it runs on a discardable VMO, this method ensures that a associated VMO keeps with its | |
| // mapping until |this| is evicted from FileCache. If it is backed on a pager's VMO, it does | |
| // nothing. | |
| zx_status_t GetVmo(); | |
| zx_status_t VmoOpUnlock(bool evict = false); | |
| zx::result<bool> VmoOpLock(); | |
| template <typename U = void> | |
| U *GetAddress() const { | |
| return static_cast<U *>(addr_); | |
| } | |
| bool IsUptodate() const; | |
| bool IsDirty() const { return TestFlag(PageFlag::kPageDirty); } | |
| bool IsWriteback() const { return TestFlag(PageFlag::kPageWriteback); } | |
| bool IsVmoLocked() const { return TestFlag(PageFlag::kPageVmoLocked); } | |
| bool IsActive() const { return TestFlag(PageFlag::kPageActive); } | |
| bool IsColdData() const { return TestFlag(PageFlag::kPageColdData); } | |
| bool IsCommit() const { return TestFlag(PageFlag::kPageCommit); } | |
| bool IsSync() const { return TestFlag(PageFlag::kPageSync); } | |
| void ClearWriteback(); | |
| void WaitOnWriteback(); | |
| bool SetUptodate(); | |
| void ClearUptodate(); | |
| bool SetCommit(); | |
| void ClearCommit(); | |
| bool SetSync(); | |
| void ClearSync(); | |
| void SetColdData(); | |
| bool ClearColdData(); | |
| bool SetDirty(); | |
| static constexpr uint32_t Size() { return kBlockSize; } | |
| block_t GetBlockAddr() const { | |
| if (TestFlag(PageFlag::kPageWriteback)) { | |
| return block_addr_; | |
| } | |
| return kNullAddr; | |
| } | |
| // Check that |this| Page exists in FileCache. | |
| bool InTreeContainer() const { return fbl::WAVLTreeContainable<Page *>::InContainer(); } | |
| // Check that |this| Page exists in any PageList. | |
| bool InListContainer() const { | |
| return fbl::DoublyLinkedListable<fbl::RefPtr<Page>>::InContainer(); | |
| } | |
| zx_status_t Read(void *data, uint64_t offset = 0, size_t len = Size()); | |
| zx_status_t Write(const void *data, uint64_t offset = 0, size_t len = Size()); | |
| F2fs *fs() const; | |
| protected: | |
| // It notifies VmoManager that there is no reference to |this|. | |
| void RecyclePage(); | |
| private: | |
| zx_status_t Map(); | |
| bool TestFlag(PageFlag flag) const { | |
| return flags_[static_cast<uint8_t>(flag)].test(std::memory_order_acquire); | |
| } | |
| void ClearFlag(PageFlag flag) { | |
| flags_[static_cast<uint8_t>(flag)].clear(std::memory_order_relaxed); | |
| } | |
| bool SetFlag(PageFlag flag) { | |
| return flags_[static_cast<uint8_t>(flag)].test_and_set(std::memory_order_acquire); | |
| } | |
| // Atomically marks the page as active and acquires a reference to the owning vnode. | |
| // Returns true if the page was already active. | |
| bool SetActive(); | |
| // Clears the active flag and returns the strong reference to the owning vnode. | |
| // It is called after the last reference is destroyed in FileCache::Downgrade(). | |
| [[nodiscard]] fbl::RefPtr<VnodeF2fs> ClearActive(); | |
| // It is used to track the status of a page by using PageFlag | |
| std::array<std::atomic_flag, static_cast<uint8_t>(PageFlag::kPageFlagSize)> flags_ = { | |
| ATOMIC_FLAG_INIT}; | |
| // It indicates FileCache to which |this| belongs. | |
| FileCache *file_cache_ = nullptr; | |
| // Strong reference to the owning VnodeF2fs while |this| is active (externally referenced). | |
| // Kept null for node/meta vnodes (managed as singletons by F2fs) and when |this| is inactive. | |
| fbl::RefPtr<VnodeF2fs> vnode_; | |
| void *addr_ = nullptr; | |
| // It is used as the key of |this| in a lookup table (i.e., FileCache::page_tree_). | |
| // It indicates different information according to the type of FileCache::vnode_ such as file, | |
| // node, and meta vnodes. For file vnodes, it has file offset. For node vnodes, it indicates the | |
| // node id. For meta vnode, it points to the block address to which the metadata is written. | |
| const pgoff_t index_; | |
| block_t block_addr_ = kNullAddr; | |
| friend class LockedPage; | |
| friend class FileCache; | |
| std::mutex mutex_; | |
| }; | |
| // LockedPage is a wrapper class for f2fs::Page lock management. | |
| // When LockedPage holds "fbl::RefPtr<Page> page" and the page is not nullptr, it guarantees that | |
| // the page is locked. | |
| // | |
| // The syntax looks something like... | |
| // fbl::RefPtr<Page> unlocked_page; | |
| // { | |
| // LockedPage locked_page(unlocked_page); | |
| // do something requiring page lock... | |
| // } | |
| // | |
| // When Page is used as a function parameter, you should use `LockedPage&` type for locked page. | |
| class LockedPage final { | |
| public: | |
| LockedPage() : page_(nullptr) {} | |
| LockedPage(const LockedPage &) = delete; | |
| LockedPage &operator=(const LockedPage &) = delete; | |
| LockedPage(LockedPage &&p) noexcept { | |
| page_ = std::move(p.page_); | |
| lock_ = std::move(p.lock_); | |
| p.page_ = nullptr; | |
| } | |
| LockedPage &operator=(LockedPage &&p) noexcept { | |
| reset(); | |
| page_ = std::move(p.page_); | |
| lock_ = std::move(p.lock_); | |
| p.page_ = nullptr; | |
| return *this; | |
| } | |
| // If it fails to acquire |page->mutex_|, it doesn't own |page|, and LockedPage::bool returns | |
| // false. | |
| explicit LockedPage(fbl::RefPtr<Page> page, std::try_to_lock_t t) { | |
| lock_ = std::unique_lock<std::mutex>(page->mutex_, t); | |
| if (lock_.owns_lock()) { | |
| page_ = std::move(page); | |
| } | |
| } | |
| explicit LockedPage(fbl::RefPtr<Page> page) { | |
| page_ = std::move(page); | |
| lock_ = std::unique_lock<std::mutex>(page_->mutex_); | |
| } | |
| ~LockedPage() { reset(); } | |
| void reset() { | |
| if (page_ != nullptr) { | |
| lock_.unlock(); | |
| lock_.release(); | |
| page_.reset(); | |
| } | |
| } | |
| // It works only for paged vmo. When f2fs needs to update the contents of a page without | |
| // triggering Vnode::VmoDirty(), it calls this method before the modification. If its page is | |
| // present, kernel pre-dirties the page. If not, it returns zx::error(ZX_ERR_NOT_FOUND), and the | |
| // caller have to supply a vmo. | |
| zx::result<> SetVmoDirty(); | |
| bool ClearDirtyForIo(); | |
| bool SetDirty(); | |
| void Zero(size_t start = 0, size_t end = Page::Size()) const; | |
| // It invalidates |this| for truncate and punch-a-hole operations. A caller should call | |
| // WaitOnWriteback() before it. | |
| void Invalidate(); | |
| // It waits for the writeback flag of |page_| to be cleared. So, it should not be called with | |
| // FileCache::page_lock_ acquired. It acquires LockedPage::lock_ during waiting. | |
| // TODO(b/293975446): Consider releasing |lock_| during waiting. | |
| void WaitOnWriteback(); | |
| bool SetWriteback(block_t addr = kNullAddr); | |
| // It returns the ownership of unlocked |page_|. | |
| fbl::RefPtr<Page> release() { | |
| if (page_) { | |
| lock_.unlock(); | |
| lock_.release(); | |
| } | |
| return fbl::RefPtr<Page>(std::move(page_)); | |
| } | |
| // CopyRefPtr() returns a RefPtr of locked |page_|. | |
| fbl::RefPtr<Page> CopyRefPtr() const { return page_; } | |
| template <typename T = Page> | |
| T &GetPage() const { | |
| return static_cast<T &>(*page_); | |
| } | |
| Page *get() const { return page_.get(); } | |
| Page &operator*() const { return *page_; } | |
| Page *operator->() const { return page_.get(); } | |
| explicit operator bool() const { return page_ != nullptr; } | |
| // Comparison against nullptr operators (of the form, myptr == nullptr). | |
| bool operator==(decltype(nullptr)) const { return (page_ == nullptr); } | |
| bool operator!=(decltype(nullptr)) const { return (page_ != nullptr); } | |
| private: | |
| static constexpr std::array<uint8_t, Page::Size()> kZeroBuffer_ = {0}; | |
| fbl::RefPtr<Page> page_ = nullptr; | |
| std::unique_lock<std::mutex> lock_; | |
| }; | |
| class FileCache { | |
| public: | |
| FileCache(VnodeF2fs *vnode, VmoManager *vmo_manager); | |
| FileCache() = delete; | |
| FileCache(const FileCache &) = delete; | |
| FileCache &operator=(const FileCache &) = delete; | |
| FileCache(const FileCache &&) = delete; | |
| FileCache &operator=(const FileCache &&) = delete; | |
| ~FileCache(); | |
| // It returns a locked Page corresponding to |index| from |page_tree_|. | |
| // If there is no Page, it creates and returns a locked Page. | |
| zx_status_t GetLockedPage(pgoff_t index, LockedPage *out) __TA_EXCLUDES(tree_lock_); | |
| // It returns locked Pages corresponding to [start - end) from |page_tree_|. | |
| zx::result<std::vector<LockedPage>> GetLockedPages(pgoff_t start, pgoff_t end) | |
| __TA_EXCLUDES(tree_lock_); | |
| // It does the same thing as the above methods except that it returns unlocked Pages. | |
| zx::result<std::vector<fbl::RefPtr<Page>>> GetPages(const pgoff_t start, const pgoff_t end) | |
| __TA_EXCLUDES(tree_lock_); | |
| // It returns locked Pages corresponding to [start - end) from |page_tree_|. | |
| // If there is no corresponding Page, the returned page will be a null page. | |
| std::vector<LockedPage> FindLockedPages(pgoff_t start, pgoff_t end) __TA_EXCLUDES(tree_lock_); | |
| // It returns an unlocked Page corresponding to |index| from |page_tree|. | |
| // If it fails to find the Page in |page_tree_|, it returns ZX_ERR_NOT_FOUND. | |
| zx_status_t FindPage(pgoff_t index, fbl::RefPtr<Page> *out) __TA_EXCLUDES(tree_lock_); | |
| // It invalidates Pages within the range of |start| to |end| in |page_tree_|. If |zero| is set, | |
| // the data of the corresponding pages are zeored. Then, it evicts all Pages within the range and | |
| // returns them locked. | |
| std::vector<LockedPage> InvalidatePages(pgoff_t start = 0, pgoff_t end = kPgOffMax, | |
| bool zero = true) __TA_EXCLUDES(tree_lock_); | |
| // It invalidates all Pages from |page_tree_|. | |
| void Reset() __TA_EXCLUDES(tree_lock_); | |
| // Clear all dirty pages. | |
| void ClearDirtyPages() __TA_EXCLUDES(tree_lock_); | |
| VnodeF2fs &GetVnode() const { return *vnode_; } | |
| fbl::RefPtr<VnodeF2fs> GetVnodeRefPtr(); | |
| // Only Page::RecyclePage() is allowed to call it. | |
| void Downgrade(Page *raw_page) __TA_EXCLUDES(tree_lock_); | |
| // It returns a proper read size within the range of [size, size + max_size) according to the | |
| // status of recently used pages and memory pressure level. | |
| size_t GetReadHint(pgoff_t start, size_t size, size_t max_size, bool high_memory_pressure = false) | |
| __TA_EXCLUDES(tree_lock_); | |
| F2fs *fs() const; | |
| VmoManager &GetVmoManager() { return *vmo_manager_; } | |
| // It returns a set of dirty Pages that meet |operation|. | |
| std::vector<fbl::RefPtr<Page>> FindDirtyPages(const WritebackOperation &operation) | |
| __TA_EXCLUDES(tree_lock_); | |
| // It evicts every clean, inactive page. | |
| void EvictCleanPages() __TA_EXCLUDES(tree_lock_); | |
| // It provides wait() and notify() for kPageWriteback flag of Page. | |
| void WaitOnWriteback(Page &page) __TA_EXCLUDES(flag_lock_, tree_lock_); | |
| void NotifyWriteback(PageList pages) __TA_EXCLUDES(flag_lock_, tree_lock_); | |
| size_t GetSize() __TA_EXCLUDES(tree_lock_); | |
| private: | |
| // Unless |page| is locked, it returns a locked |page|. If |page| is already locked, | |
| // it waits for |page| to be unlocked. While waiting, |tree_lock_| keeps unlocked to avoid | |
| // possible deadlock problems and to allow other page requests. When it gets the locked |page|, it | |
| // acquires |tree_lock_| again and returns the locked |page| if |page| still belongs to | |
| // |page_tree_|; | |
| zx::result<LockedPage> GetLockedPageUnsafe(fbl::RefPtr<Page> page) __TA_REQUIRES(tree_lock_); | |
| zx::result<LockedPage> GetLockedPageFromRawUnsafe(Page *raw_page) __TA_REQUIRES(tree_lock_); | |
| fbl::RefPtr<Page> AddNewPageUnsafe(pgoff_t index) __TA_REQUIRES(tree_lock_); | |
| zx_status_t EvictUnsafe(Page *page) __TA_REQUIRES(tree_lock_); | |
| // It returns all Pages from |page_tree_| within the range of |start| to |end|. | |
| // If there is no corresponding Page in page_tree_, the Page will not be included in the returned | |
| // vector. Therefore, returned vector's size could be smaller than |end - start|. | |
| std::vector<LockedPage> FindLockedPagesUnsafe(pgoff_t start = 0, pgoff_t end = kPgOffMax) | |
| __TA_REQUIRES(tree_lock_); | |
| std::vector<fbl::RefPtr<Page>> FindPagesUnsafe(pgoff_t start = 0, pgoff_t end = kPgOffMax) | |
| __TA_REQUIRES(tree_lock_); | |
| zx::result<std::vector<LockedPage>> GetLockedPagesUnsafe(pgoff_t start, pgoff_t end) | |
| __TA_REQUIRES(tree_lock_); | |
| zx::result<std::vector<fbl::RefPtr<Page>>> GetPagesUnsafe(pgoff_t start, pgoff_t end) | |
| __TA_REQUIRES(tree_lock_); | |
| using PageTreeTraits = fbl::DefaultKeyedObjectTraits<pgoff_t, Page>; | |
| using PageTree = fbl::WAVLTree<pgoff_t, Page *, PageTreeTraits>; | |
| // |tree_lock_| should not be acquired with |flag_lock_| to avoid deadlock. | |
| std::shared_mutex tree_lock_; | |
| std::condition_variable_any recycle_cvar_; | |
| // |flag_lock_| is used to protect writeback flags of Page. | |
| std::shared_mutex flag_lock_; | |
| std::condition_variable_any flag_cvar_; | |
| PageTree page_tree_ __TA_GUARDED(tree_lock_); | |
| VnodeF2fs *vnode_; | |
| VmoManager *vmo_manager_; | |
| }; | |
| } // namespace f2fs | |
| #endif // SRC_STORAGE_F2FS_FILE_CACHE_H_ |