blob: 96d6f204ead19c061303cbf863df74a72a653de6 [file] [log] [blame]
// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <stddef.h>
#include <stdint.h>
#include <functional>
#include <limits>
#include <map>
#include <memory>
#include <set>
#include <unordered_map>
#include <vector>
#include "base/callback.h"
#include "base/hash/hash.h"
#include "base/macros.h"
#include "base/memory/ref_counted.h"
#include "base/single_thread_task_runner.h"
#include "base/synchronization/lock.h"
#include "build/build_config.h"
#include "media/base/data_buffer.h"
#include "media/blink/interval_map.h"
#include "media/blink/lru.h"
#include "media/blink/media_blink_export.h"
namespace media {
// Used to identify a block of data in the multibuffer.
// Our blocks are 32kb (1 << 15), so our maximum cacheable file size
// is 1 << (15 + 31) = 64Tb
typedef int32_t MultiBufferBlockId;
class MultiBuffer;
// This type is used to identify a block in the LRU, which is shared between
// multibuffers.
typedef std::pair<MultiBuffer*, MultiBufferBlockId> MultiBufferGlobalBlockId;
} // namespace media
namespace std {
template <>
struct hash<media::MultiBufferGlobalBlockId> {
std::size_t operator()(const media::MultiBufferGlobalBlockId& key) const {
return base::HashInts(reinterpret_cast<uintptr_t>(key.first), key.second);
} // namespace std
namespace media {
// Freeing a lot of blocks can be expensive, to keep thing
// flowing smoothly we only free a maximum of |kMaxFreesPerAdd|
// blocks when a new block is added to the cache.
const int kMaxFreesPerAdd = 10;
// There is a simple logic for creating, destroying and deferring
// data providers. Every data provider has a look-ahead region and
// a look-behind region. If there are readers in the look-ahead
// region, we keep reading. If not, but there are readers in the
// look-behind region, we defer. If there are no readers in either
// region, we destroy the data provider.
// When new readers are added, new data providers are created if
// the new reader doesn't fall into the look-ahead region of
// an existing data provider.
// This is the size of the look-ahead region.
const int kMaxWaitForWriterOffset = 5;
// This is the size of the look-behind region.
const int kMaxWaitForReaderOffset = 50;
// MultiBuffers are multi-reader multi-writer cache/buffers with
// prefetching and pinning. Data is stored internally in ref-counted
// blocks of identical size. |block_size_shift| is log2 of the block
// size.
// Users should inherit this class and implement CreateWriter().
// TODO(hubbe): Make the multibuffer respond to memory pressure.
class MEDIA_BLINK_EXPORT MultiBuffer {
// Interface for clients wishing to read data out of this cache.
// Note: It might look tempting to replace this with a callback,
// but we keep and compare pointers to Readers internally.
class Reader {
Reader() {}
virtual ~Reader() {}
// Notifies the reader that the range of available blocks has changed.
// The reader must call MultiBuffer::Observe() to activate this callback.
virtual void NotifyAvailableRange(
const Interval<MultiBufferBlockId>& range) = 0;
// DataProvider is the interface that MultiBuffer
// uses to get data into the cache.
class DataProvider {
virtual ~DataProvider() {}
// Returns the block number that is to be returned
// by the next Read() call.
virtual MultiBufferBlockId Tell() const = 0;
// Returns true if one (or more) blocks are
// availble to read.
virtual bool Available() const = 0;
// Returns how many bytes are available, note that Available() may still
// return false even if AvailableBytes() returns a value greater than
// zero if less than a full block is available.
virtual int64_t AvailableBytes() const = 0;
// Returns the next block. Only valid if Available()
// returns true. Last block might be of a smaller size
// and after the last block we will get an end-of-stream
// DataBuffer.
virtual scoped_refptr<DataBuffer> Read() = 0;
// Ask the data provider to stop giving us data.
// It's ok if the effect is not immediate.
virtual void SetDeferred(bool deferred) = 0;
// Multibuffers use a global shared LRU to free memory.
// This effectively means that recently used multibuffers can
// borrow memory from less recently used ones.
class MEDIA_BLINK_EXPORT GlobalLRU : public base::RefCounted<GlobalLRU> {
typedef MultiBufferGlobalBlockId GlobalBlockId;
explicit GlobalLRU(
const scoped_refptr<base::SingleThreadTaskRunner>& task_runner);
// Free elements from cache if possible.
// Don't free more than |max_to_free| blocks.
void TryFree(int64_t max_to_free);
// Free as much memory from the cache as possible.
// Only used during critical memory pressure.
void TryFreeAll();
// Like TryFree, but only frees blocks if the data
// number of the blocks in the cache is too large.
void Prune(int64_t max_to_free);
// Returns true if there are prunable blocks.
bool Pruneable() const;
// Incremnt the amount of data used by all multibuffers.
void IncrementDataSize(int64_t blocks);
// Each multibuffer is allowed a certain amount of memory,
// that memory is registered by calling this function.
// The memory is actually shared by all multibuffers.
// When the total amount of memory used by all multibuffers
// is greater than what has been registered here, we use the
// LRU to decide what blocks to free first.
void IncrementMaxSize(int64_t blocks);
// LRU operations.
void Use(MultiBuffer* multibuffer, MultiBufferBlockId id);
void Remove(MultiBuffer* multibuffer, MultiBufferBlockId id);
void Insert(MultiBuffer* multibuffer, MultiBufferBlockId id);
bool Contains(MultiBuffer* multibuffer, MultiBufferBlockId id);
int64_t Size() const;
friend class base::RefCounted<GlobalLRU>;
// Schedule background pruning, if needed.
void SchedulePrune();
// Perform background pruning.
void PruneTask();
// Max number of blocks.
int64_t max_size_;
// Sum of all multibuffer::data_.size().
int64_t data_size_;
// True if there is a call to the background pruning outstanding.
bool background_pruning_pending_;
// The LRU should contain all blocks which are not pinned from
// all multibuffers.
LRU<GlobalBlockId> lru_;
// Where we run our tasks.
scoped_refptr<base::SingleThreadTaskRunner> task_runner_;
MultiBuffer(int32_t block_size_shift,
const scoped_refptr<GlobalLRU>& global_lru);
virtual ~MultiBuffer();
// Identifies a block in the cache.
// Block numbers can be calculated from byte positions as:
// block_num = byte_pos >> block_size_shift
typedef MultiBufferBlockId BlockId;
typedef std::unordered_map<BlockId, scoped_refptr<DataBuffer>> DataMap;
// Registers a reader at the given position.
// If the cache does not already contain |pos|, it will activate
// or create data providers to make sure that the block becomes
// available soon. If |pos| is already in the cache, no action is
// taken, it simply lets the cache know that this reader is likely
// to read pos+1, pos+2.. soon.
// Registered readers will be notified when the available range
// at their position changes. The available range at |pos| is a range
// from A to B where: A <= |pos|, B >= |pos| and all blocks in [A..B)
// are present in the cache. When this changes, we will call
// NotifyAvailableRange() on the reader.
void AddReader(const BlockId& pos, Reader* reader);
// Unregister a reader at block |pos|.
// Often followed by a call to AddReader(pos + 1, ...);
// Idempotent.
void RemoveReader(const BlockId& pos, Reader* reader);
// Immediately remove writers at or before |pos| if nobody needs them.
// Note that we can't really do this in StopWaitFor(), because it's very
// likely that StopWaitFor() is immediately followed by a call to WaitFor().
// It is also a bad idea to wait for the writers to clean themselves up when
// they try to provide unwanted data to the cache. Besides the obvoius
// inefficiency, it will also cause the http_cache to bypass the disk/memory
// cache if we have multiple simultaneous requests going against the same
// url.
void CleanupWriters(const BlockId& pos);
// Returns true if block |pos| is available in the cache.
bool Contains(const BlockId& pos) const;
// Returns the next unavailable block at or after |pos|.
BlockId FindNextUnavailable(const BlockId& pos) const;
// Change the pin count for a range of data blocks.
// Note that blocks do not have to be present in the
// cache to be pinned.
// Examples:
// Pin block 3, 4 & 5: PinRange(3, 6, 1);
// Unpin block 4 & 5: PinRange(4, 6, -1);
void PinRange(const BlockId& from, const BlockId& to, int32_t how_much);
// Calls PinRange for each range in |ranges|, convenience
// function for applying multiple changes to the pinned ranges.
void PinRanges(const IntervalMap<BlockId, int32_t>& ranges);
// Returns a continous (but possibly empty) list of blocks starting at
// |from| up to, but not including |to|. This function is thread safe.
void GetBlocksThreadsafe(const BlockId& from,
const BlockId& to,
std::vector<scoped_refptr<DataBuffer>>* output);
// Increment max cache size by |size| (counted in blocks).
void IncrementMaxSize(int32_t size);
// Returns how many bytes have been received by the data providers at position
// |block|, which have not yet been submitted to the multibuffer cache.
// The returned number should be less than the size of one block.
int64_t UncommittedBytesAt(const BlockId& block);
// Caller takes ownership of 'provider', cache will
// not call it anymore.
std::unique_ptr<DataProvider> RemoveProvider(DataProvider* provider);
// Add a writer to this cache. Cache takes ownership, and may
// destroy |provider| later. (Not during this call.)
void AddProvider(std::unique_ptr<DataProvider> provider);
// Transfer all data from |other| to this.
void MergeFrom(MultiBuffer* other);
// Accessors.
const DataMap& map() const { return data_; }
int32_t block_size_shift() const { return block_size_shift_; }
// Setters.
void SetIsClientAudioElement(bool is_client_audio_element) {
is_client_audio_element_ = is_client_audio_element;
// Callback which notifies us that a data provider has
// some data for us. Also called when it might be appropriate
// for a provider in a deferred state to wake up.
void OnDataProviderEvent(DataProvider* provider);
// Create a new writer at |pos| and return it.
// Users needs to implemement this method.
virtual std::unique_ptr<DataProvider> CreateWriter(
const BlockId& pos,
bool is_client_audio_element) = 0;
virtual bool RangeSupported() const = 0;
// Called when the cache becomes empty. Implementations can use this
// as a signal for when we should free this object and any metadata
// that goes with it.
virtual void OnEmpty();
// For testing.
friend class TestMultiBuffer;
enum ProviderState {
// Can be overriden for testing.
virtual void Prune(size_t max_to_free);
// Remove the given blocks from the multibuffer, called from
// GlobalLRU::Prune().
void ReleaseBlocks(const std::vector<MultiBufferBlockId>& blocks);
// Figure out what state a writer at |pos| should be in.
ProviderState SuggestProviderState(const BlockId& pos) const;
// Returns true if a writer at |pos| is colliding with
// output of another writer.
bool ProviderCollision(const BlockId& pos) const;
// Call NotifyAvailableRange(new_range) on all readers waiting
// for a block in |observer_range|
void NotifyAvailableRange(const Interval<MultiBufferBlockId>& observer_range,
const Interval<MultiBufferBlockId>& new_range);
// Max number of blocks.
int64_t max_size_;
// log2 of block size.
int32_t block_size_shift_;
// Is the client an audio element?
bool is_client_audio_element_ = false;
// Stores the actual data.
DataMap data_;
// protects data_
// Note that because data_ is only modified on the a single thread,
// we don't need to lock this if we're reading data from the same thread.
// Instead, we only lock this when:
// * modifying data_
// * reading data_ from another thread
base::Lock data_lock_;
// Keeps track of readers waiting for data.
std::map<MultiBufferBlockId, std::set<Reader*>> readers_;
// Keeps track of writers by their position.
// The writers are owned by this class.
std::map<BlockId, std::unique_ptr<DataProvider>> writer_index_;
// Gloabally shared LRU, decides which block to free next.
scoped_refptr<GlobalLRU> lru_;
// Keeps track of what blocks are pinned. If block p is pinned,
// then pinned_[p] > 0. Pinned blocks cannot be freed and should not
// be present in |lru_|.
IntervalMap<BlockId, int32_t> pinned_;
// present_[block] should be 1 for all blocks that are present
// and 0 for all blocks that are not. Used to quickly figure out
// ranges of available/unavailable blocks without iterating.
IntervalMap<BlockId, int32_t> present_;
} // namespace media