/*

 * CDDL HEADER START

 *

 * The contents of this file are subject to the terms of the

 * Common Development and Distribution License (the "License").

 * You may not use this file except in compliance with the License.

 *

 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

 * or http://www.opensolaris.org/os/licensing.

 * See the License for the specific language governing permissions

 * and limitations under the License.

 *

 * When distributing Covered Code, include this CDDL HEADER in each

 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.

 * If applicable, add the following below this CDDL HEADER, with the

 * fields enclosed by brackets "[]" replaced with your own identifying

 * information: Portions Copyright [yyyy] [name of copyright owner]

 *

 * CDDL HEADER END

 */

/*

 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.

 * Copyright 2011 Nexenta Systems, Inc.  All rights reserved.

 * Copyright (c) 2012 by Delphix. All rights reserved.

 */

/*

 * DVA-based Adjustable Replacement Cache

 *

 * While much of the theory of operation used here is

 * based on the self-tuning, low overhead replacement cache

 * presented by Megiddo and Modha at FAST 2003, there are some

 * significant differences:

 *

 * 1. The Megiddo and Modha model assumes any page is evictable.

 * Pages in its cache cannot be "locked" into memory.  This makes

 * the eviction algorithm simple: evict the last page in the list.

 * This also make the performance characteristics easy to reason

 * about.  Our cache is not so simple.  At any given moment, some

 * subset of the blocks in the cache are un-evictable because we

 * have handed out a reference to them.  Blocks are only evictable

 * when there are no external references active.  This makes

 * eviction far more problematic:  we choose to evict the evictable

 * blocks that are the "lowest" in the list.

 *

 * There are times when it is not possible to evict the requested

 * space.  In these circumstances we are unable to adjust the cache

 * size.  To prevent the cache growing unbounded at these times we

 * implement a "cache throttle" that slows the flow of new data

 * into the cache until we can make space available.

 *

 * 2. The Megiddo and Modha model assumes a fixed cache size.

 * Pages are evicted when the cache is full and there is a cache

 * miss.  Our model has a variable sized cache.  It grows with

 * high use, but also tries to react to memory pressure from the

 * operating system: decreasing its size when system memory is

 * tight.

 *

 * 3. The Megiddo and Modha model assumes a fixed page size. All

 * elements of the cache are therefor exactly the same size.  So

 * when adjusting the cache size following a cache miss, its simply

 * a matter of choosing a single page to evict.  In our model, we

 * have variable sized cache blocks (rangeing from 512 bytes to

 * 128K bytes).  We therefor choose a set of blocks to evict to make

 * space for a cache miss that approximates as closely as possible

 * the space used by the new block.

 *

 * See also:  "ARC: A Self-Tuning, Low Overhead Replacement Cache"

 * by N. Megiddo & D. Modha, FAST 2003

 */

/*

 * The locking model:

 *

 * A new reference to a cache buffer can be obtained in two

 * ways: 1) via a hash table lookup using the DVA as a key,

 * or 2) via one of the ARC lists.  The arc_read() interface

 * uses method 1, while the internal arc algorithms for

 * adjusting the cache use method 2.  We therefor provide two

 * types of locks: 1) the hash table lock array, and 2) the

 * arc list locks.

 *

 * Buffers do not have their own mutexs, rather they rely on the

 * hash table mutexs for the bulk of their protection (i.e. most

 * fields in the arc_buf_hdr_t are protected by these mutexs).

 *

 * buf_hash_find() returns the appropriate mutex (held) when it

 * locates the requested buffer in the hash table.  It returns

 * NULL for the mutex if the buffer was not in the table.

 *

 * buf_hash_remove() expects the appropriate hash mutex to be

 * already held before it is invoked.

 *

 * Each arc state also has a mutex which is used to protect the

 * buffer list associated with the state.  When attempting to

 * obtain a hash table lock while holding an arc list lock you

 * must use: mutex_tryenter() to avoid deadlock.  Also note that

 * the active state mutex must be held before the ghost state mutex.

 *

 * Arc buffers may have an associated eviction callback function.

 * This function will be invoked prior to removing the buffer (e.g.

 * in arc_do_user_evicts()).  Note however that the data associated

 * with the buffer may be evicted prior to the callback.  The callback

 * must be made with *no locks held* (to prevent deadlock).  Additionally,

 * the users of callbacks must ensure that their private data is

 * protected from simultaneous callbacks from arc_buf_evict()

 * and arc_do_user_evicts().

 *

 * Note that the majority of the performance stats are manipulated

 * with atomic operations.

 *

 * The L2ARC uses the l2arc_buflist_mtx global mutex for the following:

 *

 *	- L2ARC buflist creation

 *	- L2ARC buflist eviction

 *	- L2ARC write completion, which walks L2ARC buflists

 *	- ARC header destruction, as it removes from L2ARC buflists

 *	- ARC header release, as it removes from L2ARC buflists

 */

#include <sys/spa.h>

#include <sys/zio.h>

#include <sys/zfs_context.h>

#include <sys/arc.h>

#include <sys/refcount.h>

#include <sys/vdev.h>

#include <sys/vdev_impl.h>

#ifdef _KERNEL

#include <sys/vmsystm.h>

#include <vm/anon.h>

#include <sys/fs/swapnode.h>

#include <sys/dnlc.h>

#endif

#include <sys/callb.h>

#include <sys/kstat.h>

#include <zfs_fletcher.h>

static kmutex_t		arc_reclaim_thr_lock;

static kcondvar_t	arc_reclaim_thr_cv;	/* used to signal reclaim thr */

static uint8_t		arc_thread_exit;

extern int zfs_write_limit_shift;

extern uint64_t zfs_write_limit_max;

extern kmutex_t zfs_write_limit_lock;

#define	ARC_REDUCE_DNLC_PERCENT	3

uint_t arc_reduce_dnlc_percent = ARC_REDUCE_DNLC_PERCENT;

typedef enum arc_reclaim_strategy {

	ARC_RECLAIM_AGGR,		/* Aggressive reclaim strategy */

	ARC_RECLAIM_CONS		/* Conservative reclaim strategy */

} arc_reclaim_strategy_t;

/* number of seconds before growing cache again */

static int		arc_grow_retry = 60;

/* shift of arc_c for calculating both min and max arc_p */

static int		arc_p_min_shift = 4;

/* log2(fraction of arc to reclaim) */

static int		arc_shrink_shift = 5;

/*

 * minimum lifespan of a prefetch block in clock ticks

 * (initialized in arc_init())

 */

static int		arc_min_prefetch_lifespan;

static int arc_dead;

/*

 * The arc has filled available memory and has now warmed up.

 */

static boolean_t arc_warm;

/*

 * These tunables are for performance analysis.

 */

uint64_t zfs_arc_max;

uint64_t zfs_arc_min;

uint64_t zfs_arc_meta_limit = 0;

int zfs_arc_grow_retry = 0;

int zfs_arc_shrink_shift = 0;

int zfs_arc_p_min_shift = 0;

/*

 * Note that buffers can be in one of 6 states:

 *	ARC_anon	- anonymous (discussed below)

 *	ARC_mru		- recently used, currently cached

 *	ARC_mru_ghost	- recentely used, no longer in cache

 *	ARC_mfu		- frequently used, currently cached

 *	ARC_mfu_ghost	- frequently used, no longer in cache

 *	ARC_l2c_only	- exists in L2ARC but not other states

 * When there are no active references to the buffer, they are

 * are linked onto a list in one of these arc states.  These are

 * the only buffers that can be evicted or deleted.  Within each

 * state there are multiple lists, one for meta-data and one for

 * non-meta-data.  Meta-data (indirect blocks, blocks of dnodes,

 * etc.) is tracked separately so that it can be managed more

 * explicitly: favored over data, limited explicitly.

 *

 * Anonymous buffers are buffers that are not associated with

 * a DVA.  These are buffers that hold dirty block copies

 * before they are written to stable storage.  By definition,

 * they are "ref'd" and are considered part of arc_mru

 * that cannot be freed.  Generally, they will aquire a DVA

 * as they are written and migrate onto the arc_mru list.

 *

 * The ARC_l2c_only state is for buffers that are in the second

 * level ARC but no longer in any of the ARC_m* lists.  The second

 * level ARC itself may also contain buffers that are in any of

 * the ARC_m* states - meaning that a buffer can exist in two

 * places.  The reason for the ARC_l2c_only state is to keep the

 * buffer header in the hash table, so that reads that hit the

 * second level ARC benefit from these fast lookups.

 */

typedef struct arc_state {

	list_t	arcs_list[ARC_BUFC_NUMTYPES];	/* list of evictable buffers */

	uint64_t arcs_lsize[ARC_BUFC_NUMTYPES];	/* amount of evictable data */

	uint64_t arcs_size;	/* total amount of data in this state */

	kmutex_t arcs_mtx;

} arc_state_t;

/* The 6 states: */

static arc_state_t ARC_anon;

static arc_state_t ARC_mru;

static arc_state_t ARC_mru_ghost;

static arc_state_t ARC_mfu;

static arc_state_t ARC_mfu_ghost;

static arc_state_t ARC_l2c_only;

typedef struct arc_stats {

	kstat_named_t arcstat_hits;

	kstat_named_t arcstat_misses;

	kstat_named_t arcstat_demand_data_hits;

	kstat_named_t arcstat_demand_data_misses;

	kstat_named_t arcstat_demand_metadata_hits;

	kstat_named_t arcstat_demand_metadata_misses;

	kstat_named_t arcstat_prefetch_data_hits;

	kstat_named_t arcstat_prefetch_data_misses;

	kstat_named_t arcstat_prefetch_metadata_hits;

	kstat_named_t arcstat_prefetch_metadata_misses;

	kstat_named_t arcstat_mru_hits;

	kstat_named_t arcstat_mru_ghost_hits;

	kstat_named_t arcstat_mfu_hits;

	kstat_named_t arcstat_mfu_ghost_hits;

	kstat_named_t arcstat_deleted;

	kstat_named_t arcstat_recycle_miss;

	kstat_named_t arcstat_mutex_miss;

	kstat_named_t arcstat_evict_skip;

	kstat_named_t arcstat_evict_l2_cached;

	kstat_named_t arcstat_evict_l2_eligible;

	kstat_named_t arcstat_evict_l2_ineligible;

	kstat_named_t arcstat_hash_elements;

	kstat_named_t arcstat_hash_elements_max;

	kstat_named_t arcstat_hash_collisions;

	kstat_named_t arcstat_hash_chains;

	kstat_named_t arcstat_hash_chain_max;

	kstat_named_t arcstat_p;

	kstat_named_t arcstat_c;

	kstat_named_t arcstat_c_min;

	kstat_named_t arcstat_c_max;

	kstat_named_t arcstat_size;

	kstat_named_t arcstat_hdr_size;

	kstat_named_t arcstat_data_size;

	kstat_named_t arcstat_other_size;

	kstat_named_t arcstat_l2_hits;

	kstat_named_t arcstat_l2_misses;

	kstat_named_t arcstat_l2_feeds;

	kstat_named_t arcstat_l2_rw_clash;

	kstat_named_t arcstat_l2_read_bytes;

	kstat_named_t arcstat_l2_write_bytes;

	kstat_named_t arcstat_l2_writes_sent;

	kstat_named_t arcstat_l2_writes_done;

	kstat_named_t arcstat_l2_writes_error;

	kstat_named_t arcstat_l2_writes_hdr_miss;

	kstat_named_t arcstat_l2_evict_lock_retry;

	kstat_named_t arcstat_l2_evict_reading;

	kstat_named_t arcstat_l2_free_on_write;

	kstat_named_t arcstat_l2_abort_lowmem;

	kstat_named_t arcstat_l2_cksum_bad;

	kstat_named_t arcstat_l2_io_error;

	kstat_named_t arcstat_l2_size;

	kstat_named_t arcstat_l2_hdr_size;

	kstat_named_t arcstat_memory_throttle_count;

} arc_stats_t;

static arc_stats_t arc_stats = {

	{ "hits",			KSTAT_DATA_UINT64 },

	{ "misses",			KSTAT_DATA_UINT64 },

	{ "demand_data_hits",		KSTAT_DATA_UINT64 },

	{ "demand_data_misses",		KSTAT_DATA_UINT64 },

	{ "demand_metadata_hits",	KSTAT_DATA_UINT64 },

	{ "demand_metadata_misses",	KSTAT_DATA_UINT64 },

	{ "prefetch_data_hits",		KSTAT_DATA_UINT64 },

	{ "prefetch_data_misses",	KSTAT_DATA_UINT64 },

	{ "prefetch_metadata_hits",	KSTAT_DATA_UINT64 },

	{ "prefetch_metadata_misses",	KSTAT_DATA_UINT64 },

	{ "mru_hits",			KSTAT_DATA_UINT64 },

	{ "mru_ghost_hits",		KSTAT_DATA_UINT64 },

	{ "mfu_hits",			KSTAT_DATA_UINT64 },

	{ "mfu_ghost_hits",		KSTAT_DATA_UINT64 },

	{ "deleted",			KSTAT_DATA_UINT64 },

	{ "recycle_miss",		KSTAT_DATA_UINT64 },

	{ "mutex_miss",			KSTAT_DATA_UINT64 },

	{ "evict_skip",			KSTAT_DATA_UINT64 },

	{ "evict_l2_cached",		KSTAT_DATA_UINT64 },

	{ "evict_l2_eligible",		KSTAT_DATA_UINT64 },

	{ "evict_l2_ineligible",	KSTAT_DATA_UINT64 },

	{ "hash_elements",		KSTAT_DATA_UINT64 },

	{ "hash_elements_max",		KSTAT_DATA_UINT64 },

	{ "hash_collisions",		KSTAT_DATA_UINT64 },

	{ "hash_chains",		KSTAT_DATA_UINT64 },

	{ "hash_chain_max",		KSTAT_DATA_UINT64 },

	{ "p",				KSTAT_DATA_UINT64 },

	{ "c",				KSTAT_DATA_UINT64 },

	{ "c_min",			KSTAT_DATA_UINT64 },

	{ "c_max",			KSTAT_DATA_UINT64 },

	{ "size",			KSTAT_DATA_UINT64 },

	{ "hdr_size",			KSTAT_DATA_UINT64 },

	{ "data_size",			KSTAT_DATA_UINT64 },

	{ "other_size",			KSTAT_DATA_UINT64 },

	{ "l2_hits",			KSTAT_DATA_UINT64 },

	{ "l2_misses",			KSTAT_DATA_UINT64 },

	{ "l2_feeds",			KSTAT_DATA_UINT64 },

	{ "l2_rw_clash",		KSTAT_DATA_UINT64 },

	{ "l2_read_bytes",		KSTAT_DATA_UINT64 },

	{ "l2_write_bytes",		KSTAT_DATA_UINT64 },

	{ "l2_writes_sent",		KSTAT_DATA_UINT64 },

	{ "l2_writes_done",		KSTAT_DATA_UINT64 },

	{ "l2_writes_error",		KSTAT_DATA_UINT64 },

	{ "l2_writes_hdr_miss",		KSTAT_DATA_UINT64 },

	{ "l2_evict_lock_retry",	KSTAT_DATA_UINT64 },

	{ "l2_evict_reading",		KSTAT_DATA_UINT64 },

	{ "l2_free_on_write",		KSTAT_DATA_UINT64 },

	{ "l2_abort_lowmem",		KSTAT_DATA_UINT64 },

	{ "l2_cksum_bad",		KSTAT_DATA_UINT64 },

	{ "l2_io_error",		KSTAT_DATA_UINT64 },

	{ "l2_size",			KSTAT_DATA_UINT64 },

	{ "l2_hdr_size",		KSTAT_DATA_UINT64 },

	{ "memory_throttle_count",	KSTAT_DATA_UINT64 }

};

#define	ARCSTAT(stat)	(arc_stats.stat.value.ui64)

#define	ARCSTAT_INCR(stat, val) \

	atomic_add_64(&arc_stats.stat.value.ui64, (val));

#define	ARCSTAT_BUMP(stat)	ARCSTAT_INCR(stat, 1)

#define	ARCSTAT_BUMPDOWN(stat)	ARCSTAT_INCR(stat, -1)

#define	ARCSTAT_MAX(stat, val) {					\

	uint64_t m;							\

	while ((val) > (m = arc_stats.stat.value.ui64) &&		\

	    (m != atomic_cas_64(&arc_stats.stat.value.ui64, m, (val))))	\

		continue;						\

}

#define	ARCSTAT_MAXSTAT(stat) \

	ARCSTAT_MAX(stat##_max, arc_stats.stat.value.ui64)

/*

 * We define a macro to allow ARC hits/misses to be easily broken down by

 * two separate conditions, giving a total of four different subtypes for

 * each of hits and misses (so eight statistics total).

 */

#define	ARCSTAT_CONDSTAT(cond1, stat1, notstat1, cond2, stat2, notstat2, stat) \

	if (cond1) {							\

		if (cond2) {						\

			ARCSTAT_BUMP(arcstat_##stat1##_##stat2##_##stat); \

		} else {						\

			ARCSTAT_BUMP(arcstat_##stat1##_##notstat2##_##stat); \

		}							\

	} else {							\

		if (cond2) {						\

			ARCSTAT_BUMP(arcstat_##notstat1##_##stat2##_##stat); \

		} else {						\

			ARCSTAT_BUMP(arcstat_##notstat1##_##notstat2##_##stat);\

		}							\

	}

kstat_t			*arc_ksp;

static arc_state_t	*arc_anon;

static arc_state_t	*arc_mru;

static arc_state_t	*arc_mru_ghost;

static arc_state_t	*arc_mfu;

static arc_state_t	*arc_mfu_ghost;

static arc_state_t	*arc_l2c_only;

/*

 * There are several ARC variables that are critical to export as kstats --

 * but we don't want to have to grovel around in the kstat whenever we wish to

 * manipulate them.  For these variables, we therefore define them to be in

 * terms of the statistic variable.  This assures that we are not introducing

 * the possibility of inconsistency by having shadow copies of the variables,

 * while still allowing the code to be readable.

 */

#define	arc_size	ARCSTAT(arcstat_size)	/* actual total arc size */

#define	arc_p		ARCSTAT(arcstat_p)	/* target size of MRU */

#define	arc_c		ARCSTAT(arcstat_c)	/* target size of cache */

#define	arc_c_min	ARCSTAT(arcstat_c_min)	/* min target cache size */

#define	arc_c_max	ARCSTAT(arcstat_c_max)	/* max target cache size */

static int		arc_no_grow;	/* Don't try to grow cache size */

static uint64_t		arc_tempreserve;

static uint64_t		arc_loaned_bytes;

static uint64_t		arc_meta_used;

static uint64_t		arc_meta_limit;

static uint64_t		arc_meta_max = 0;

typedef struct l2arc_buf_hdr l2arc_buf_hdr_t;

typedef struct arc_callback arc_callback_t;

struct arc_callback {

	void			*acb_private;

	arc_done_func_t		*acb_done;

	arc_buf_t		*acb_buf;

	zio_t			*acb_zio_dummy;

	arc_callback_t		*acb_next;

};

typedef struct arc_write_callback arc_write_callback_t;

struct arc_write_callback {

	void		*awcb_private;

	arc_done_func_t	*awcb_ready;

	arc_done_func_t	*awcb_done;

	arc_buf_t	*awcb_buf;

};

struct arc_buf_hdr {

	/* protected by hash lock */

	dva_t			b_dva;

	uint64_t		b_birth;

	uint64_t		b_cksum0;

	kmutex_t		b_freeze_lock;

	zio_cksum_t		*b_freeze_cksum;

	void			*b_thawed;

	arc_buf_hdr_t		*b_hash_next;

	arc_buf_t		*b_buf;

	uint32_t		b_flags;

	uint32_t		b_datacnt;

	arc_callback_t		*b_acb;

	kcondvar_t		b_cv;

	/* immutable */

	arc_buf_contents_t	b_type;

	uint64_t		b_size;

	uint64_t		b_spa;

	/* protected by arc state mutex */

	arc_state_t		*b_state;

	list_node_t		b_arc_node;

	/* updated atomically */

	clock_t			b_arc_access;

	/* self protecting */

	refcount_t		b_refcnt;

	l2arc_buf_hdr_t		*b_l2hdr;

	list_node_t		b_l2node;

};

static arc_buf_t *arc_eviction_list;

static kmutex_t arc_eviction_mtx;

static arc_buf_hdr_t arc_eviction_hdr;

static void arc_get_data_buf(arc_buf_t *buf);

static void arc_access(arc_buf_hdr_t *buf, kmutex_t *hash_lock);

static int arc_evict_needed(arc_buf_contents_t type);

static void arc_evict_ghost(arc_state_t *state, uint64_t spa, int64_t bytes);

static boolean_t l2arc_write_eligible(uint64_t spa_guid, arc_buf_hdr_t *ab);

#define	GHOST_STATE(state)	\

	((state) == arc_mru_ghost || (state) == arc_mfu_ghost ||	\

	(state) == arc_l2c_only)

/*

 * Private ARC flags.  These flags are private ARC only flags that will show up

 * in b_flags in the arc_hdr_buf_t.  Some flags are publicly declared, and can

 * be passed in as arc_flags in things like arc_read.  However, these flags

 * should never be passed and should only be set by ARC code.  When adding new

 * public flags, make sure not to smash the private ones.

 */

#define	ARC_IN_HASH_TABLE	(1 << 9)	/* this buffer is hashed */

#define	ARC_IO_IN_PROGRESS	(1 << 10)	/* I/O in progress for buf */

#define	ARC_IO_ERROR		(1 << 11)	/* I/O failed for buf */

#define	ARC_FREED_IN_READ	(1 << 12)	/* buf freed while in read */

#define	ARC_BUF_AVAILABLE	(1 << 13)	/* block not in active use */

#define	ARC_INDIRECT		(1 << 14)	/* this is an indirect block */

#define	ARC_FREE_IN_PROGRESS	(1 << 15)	/* hdr about to be freed */