/*

 * 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, Joyent, Inc. All rights reserved.

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

 * Copyright (c) 2013 by Saso Kiselkov. 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 therefore 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 therefore 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 therefore provide two

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

 * arc list locks.

 *

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

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

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

 *

 * 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/zio_compress.h>

#include <sys/zfs_context.h>

#include <sys/arc.h>

#include <sys/refcount.h>

#include <sys/vdev.h>

#include <sys/vdev_impl.h>

#include <sys/dsl_pool.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>

#ifndef _KERNEL

/* set with ZFS_DEBUG=watch, to enable watchpoints on frozen buffers */

boolean_t arc_watch = B_FALSE;

int arc_procfd;

#endif

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;

#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;

/*

 * The number of iterations through arc_evict_*() before we

 * drop & reacquire the lock.

 */

int arc_evict_iterations = 100;

/* 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;

/*

 * If this percent of memory is free, don't throttle.

 */

int arc_lotsfree_percent = 10;

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;

int zfs_disable_dup_eviction = 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;

	/*

	 * Number of buffers that could not be evicted because the hash lock

	 * was held by another thread.  The lock may not necessarily be held

	 * by something using the same buffer, since hash locks are shared

	 * by multiple buffers.

	 */

	kstat_named_t arcstat_mutex_miss;

	/*

	 * Number of buffers skipped because they have I/O in progress, are

	 * indrect prefetch buffers that have not lived long enough, or are

	 * not from the spa we're trying to evict from.

	 */

	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_asize;

	kstat_named_t arcstat_l2_hdr_size;

	kstat_named_t arcstat_l2_compress_successes;

	kstat_named_t arcstat_l2_compress_zeros;

	kstat_named_t arcstat_l2_compress_failures;

	kstat_named_t arcstat_memory_throttle_count;

	kstat_named_t arcstat_duplicate_buffers;

	kstat_named_t arcstat_duplicate_buffers_size;

	kstat_named_t arcstat_duplicate_reads;

	kstat_named_t arcstat_meta_used;

	kstat_named_t arcstat_meta_limit;

	kstat_named_t arcstat_meta_max;

} 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_asize",			KSTAT_DATA_UINT64 },

	{ "l2_hdr_size",		KSTAT_DATA_UINT64 },

	{ "l2_compress_successes",	KSTAT_DATA_UINT64 },

	{ "l2_compress_zeros",		KSTAT_DATA_UINT64 },

	{ "l2_compress_failures",	KSTAT_DATA_UINT64 },

	{ "memory_throttle_count",	KSTAT_DATA_UINT64 },

	{ "duplicate_buffers",		KSTAT_DATA_UINT64 },

	{ "duplicate_buffers_size",	KSTAT_DATA_UINT64 },

	{ "duplicate_reads",		KSTAT_DATA_UINT64 },

	{ "arc_meta_used",		KSTAT_DATA_UINT64 },

	{ "arc_meta_limit",		KSTAT_DATA_UINT64 },

	{ "arc_meta_max",		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 */

#define	arc_meta_limit	ARCSTAT(arcstat_meta_limit) /* max size for metadata */

#define	arc_meta_used	ARCSTAT(arcstat_meta_used) /* size of metadata */

#define	arc_meta_max	ARCSTAT(arcstat_meta_max) /* max size of metadata */

#define	L2ARC_IS_VALID_COMPRESS(_c_) \

	((_c_) == ZIO_COMPRESS_LZ4 || (_c_) == ZIO_COMPRESS_EMPTY)

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

static uint64_t		arc_tempreserve;

static uint64_t		arc_loaned_bytes;

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_physdone;

	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;