blob: 08d24ce42cd2a585d7689187b9cdc48842496677 [file] [log] [blame]
// Copyright 2018 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 ZIRCON_SYSTEM_ULIB_BLOBFS_BLOB_CACHE_H_
#define ZIRCON_SYSTEM_ULIB_BLOBFS_BLOB_CACHE_H_
#ifndef __Fuchsia__
#error Fuchsia-only Header
#endif
#include <blobfs/cache-policy.h>
#include <digest/digest.h>
#include <fbl/condition_variable.h>
#include <fbl/function.h>
#include <fbl/intrusive_wavl_tree.h>
#include <fbl/mutex.h>
#include <fbl/ref_ptr.h>
#include <fs/trace.h>
#include <fs/vnode.h>
#include "cache-node.h"
#include "metrics.h"
namespace blobfs {
using digest::Digest;
// BlobCache contains a collection of weak pointers to vnodes.
//
// This cache also helps manage the lifecycle of these vnodes, controlling what is cached
// when there are no more external references.
//
// Internally, the BlobCache contains a "live set" and "closed set" of vnodes.
// The "live set" contains all Vnodes with a strong reference.
// The "closed set" contains references to Vnodes which are not used, but which exist
// on-disk. These Vnodes may be stored in a "low-memory" state until they are requested.
//
// This class is thread-safe.
class BlobCache {
public:
DISALLOW_COPY_ASSIGN_AND_MOVE(BlobCache);
BlobCache();
~BlobCache();
// Empties the cache, evicting all open nodes and deleting all closed nodes.
void Reset();
// Sets the internal cache policy dealing with blob eviction.
//
// Refer to the declaration of |CachePolicy| for more information.
void SetCachePolicy(CachePolicy policy) { cache_policy_ = policy; }
// Iterates over all non-evicted cached nodes with strong references, invoking |callback| on
// each one.
//
// If a node is inserted into the "live set" via a concurrent call to |Add|, or evicted
// with a concurrent call to |Evict|, it is undefined if that node will be returned.
using NextNodeCallback = fbl::Function<void(fbl::RefPtr<CacheNode>)>;
void ForAllOpenNodes(NextNodeCallback callback);
// Searches for a blob by |digest|.
//
// If a readable blob with the same name exists, it is (optionally) placed in |out|.
// If no such blob is found, ZX_ERR_NOT_FOUND is returned.
// |out| may be null. The same error code will be returned as if it was a valid pointer.
// If |out| is not null, then the returned-by-strong-reference Vnode will exist in the "live
// set".
zx_status_t Lookup(const Digest& digest, fbl::RefPtr<CacheNode>* out) __WARN_UNUSED_RESULT;
// Adds a blob to the "live set" of the cache. If |vnode->ShouldCache()| is true, then
// this node will remain discoverable using |Lookup()|, even if no strong references
// remain.
//
// Returns ZX_ERR_ALREADY_EXISTS if this blob could not be added because a node with the same
// key already exists in the cache.
zx_status_t Add(const fbl::RefPtr<CacheNode>& vnode) __WARN_UNUSED_RESULT;
// Deletes a blob from the cache.
// When the last strong reference is removed, it is put into a low-memory state, but
// not placed into the "closed set" of the cache.
// Future calls to "Lookup" will not be able to observe this node.
//
// Returns ZX_OK if the node was evicted from the cache.
// Returns ZX_ERR_NOT_FOUND if the node was not in the cache.
zx_status_t Evict(const fbl::RefPtr<CacheNode>& vnode) __WARN_UNUSED_RESULT;
private:
// Resurrects a Vnode with no strong references, and relocate it from the "live set" to the
// "closed set".
//
// Precondition: The blob must have no strong references.
// This function is currently only safe to call from CacheNode::fbl_recycle.
void Downgrade(CacheNode* vn);
friend void CacheNode::fbl_recycle();
// Identical to |Evict|, but utilizing a raw pointer.
//
// This function is only safe to call from:
// - |Evict|, where the strong reference guarantees that the node will exist in the |open_hash_|
// or not at all, or
// - |fbl_recycle|, where the refcount of zero will prevent other nodes from concurrently
// acquiring a reference. In this case, an argument is passed, identifying that other nodes
// observing the |open_hash_| via lookup should be signalled if this node is removed.
zx_status_t EvictUnsafe(CacheNode* vnode, bool from_recycle = false);
// Returns a strong reference to a node, if it exists. May relocate the
// node from the |closed_hash_| to the |open_hash_| if no strong references
// actively exist. |out| must not be nullptr.
//
// Returns ZX_OK if the node is found and returned.
// Returns ZX_ERR_NOT_FOUND if the node doesn't exist in the cache.
zx_status_t LookupLocked(const uint8_t* key, fbl::RefPtr<CacheNode>* out)
__TA_REQUIRES(hash_lock_);
// Upgrades a Vnode which exists in the |closed_hash_| into |open_hash_|,
// and acquire the strong reference the Vnode which was leaked by
// |Downgrade()|, if it exists.
//
// Precondition: The Vnode must not exist in |open_hash_|.
fbl::RefPtr<CacheNode> UpgradeLocked(const uint8_t* key) __TA_REQUIRES(hash_lock_);
// Resets the cache by deleting all members |closed_hash_|.
void ResetLocked() __TA_REQUIRES(hash_lock_);
// We need to define this structure to allow the CacheNodes to be indexable by a key
// which is larger than a primitive type: the keys are 'digest::kSha256Length'
// bytes long.
struct MerkleRootTraits {
static const uint8_t* GetKey(const CacheNode& obj) { return obj.GetKey(); }
static bool LessThan(const uint8_t* k1, const uint8_t* k2) {
return memcmp(k1, k2, digest::kSha256Length) < 0;
}
static bool EqualTo(const uint8_t* k1, const uint8_t* k2) {
return memcmp(k1, k2, digest::kSha256Length) == 0;
}
};
// CacheNodes exist in the WAVLTree as long as one or more reference exists;
// when the Vnode is deleted, it is immediately removed from the WAVL tree.
using WAVLTreeByMerkle =
fbl::WAVLTree<const uint8_t*, CacheNode*, MerkleRootTraits, CacheNode::TypeWavlTraits>;
CachePolicy cache_policy_ = CachePolicy::EvictImmediately;
fbl::Mutex hash_lock_ = {};
// All 'in use' blobs.
WAVLTreeByMerkle open_hash_ __TA_GUARDED(hash_lock_){};
// All 'closed' blobs.
WAVLTreeByMerkle closed_hash_ __TA_GUARDED(hash_lock_){};
// A condition variable which is signalled whenever a CacheNode has been removed from
// the |open_hash_|. When a CacheNode runs out of references, it exists in the |open_hash_|
// with no strong references for a short period of time before being removed and
// either resurrected or destroyed. This means, however, that a concurrent caller
// trying to |Lookup()| that node may see it, but be unable to acquire it.
// This variable lets those callers wait until SOME node has been removed from the
// |open_hash_|, at which point their |Lookup()| may have a different result.
fbl::ConditionVariable release_cvar_;
};
} // namespace blobfs
#endif // ZIRCON_SYSTEM_ULIB_BLOBFS_BLOB_CACHE_H_