// 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.

#pragma once

#ifndef __Fuchsia__
#error Fuchsia-only Header
#endif

#include <digest/digest.h>
#include <fbl/condition_variable.h>
#include <fbl/intrusive_wavl_tree.h>
#include <fbl/function.h>
#include <fbl/mutex.h>
#include <fbl/ref_ptr.h>
#include <fs/trace.h>
#include <fs/vnode.h>

#include <blobfs/cache-node.h>
#include <blobfs/metrics.h>

namespace blobfs {

using digest::Digest;

// CachePolicy describes the techniques used to cache blobs in memory, avoiding
// re-reading and re-verifying them from disk.
enum class CachePolicy {
    // When all strong references to a node are closed, |ActivateLowMemory()| is invoked.
    //
    // This option avoids using memory for any longer than it needs to, but
    // may result in higher performance penalties for blobs that are frequently
    // opened and closed.
    EvictImmediately,

    // The node is never evicted from memory, unless it has been fully deleted and there are no
    // additional references.
    //
    // This option costs a significant amount of memory, but it results in high performance.
    NeverEvict,
};

// 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::kLength'
    // 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::kLength) < 0;
        }
        static bool EqualTo(const uint8_t* k1, const uint8_t* k2) {
            return memcmp(k1, k2, Digest::kLength) == 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