Constant-time cache inode cache management implementation. More...

#include "abstract_atomic.h"
#include <unistd.h>
#include <sys/types.h>
#include <sys/param.h>
#include <time.h>
#include <pthread.h>
#include <assert.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>
#include "nlm_list.h"
#include "fsal.h"
#include "nfs_core.h"
#include "log.h"
#include "cache_inode.h"
#include "cache_inode_lru.h"

Classes
struct	lru_q_base
struct	lru_q_
Defines
#define	CACHE_LINE_SIZE 64
#define	CACHE_PAD(_n) char __pad ## _n [CACHE_LINE_SIZE]
#define	ALIGNED_ALLOC(_s)
Functions
void	cache_inode_lru_pkginit (void)
void	cache_inode_lru_pkgshutdown (void)
cache_entry_t *	cache_inode_lru_get (cache_inode_status_t *status, uint32_t flags)
	Re-use or allocate an entry.
cache_inode_status_t	cache_inode_inc_pin_ref (cache_entry_t *entry)
	Function to let the state layer pin an entry.
void	cache_inode_unpinnable (cache_entry_t *entry)
	Make it impossible to pin an entry.
cache_inode_status_t	cache_inode_dec_pin_ref (cache_entry_t *entry)
	Function to let the state layer rlease a pin.
cache_inode_status_t	cache_inode_lru_ref (cache_entry_t *entry, uint32_t flags)
	Get a reference.
void	cache_inode_lru_kill (cache_entry_t *entry)
	Destroy the sentinel refcount safely.
void	cache_inode_lru_unref (cache_entry_t *entry, uint32_t flags)
	Relinquish a reference.
void	lru_wake_thread (uint32_t flags)
	Wake the LRU thread to free FDs.
Variables
struct lru_state	lru_state
size_t	open_fd_count = 0

Detailed Description

Constant-time cache inode cache management implementation.

Author:: Matt Benjamin

DESCRIPTION

This module implements a constant-time cache management strategy based on LRU. Some ideas are taken from 2Q [Johnson and Shasha 1994] and MQ [Zhou, Chen, Li 2004]. In this system, cache management does interact with cache entry lifecycle, but the lru queue is not a garbage collector. Most imporantly, cache management operations execute in constant time, as expected with LRU (and MQ).

Cache entries in use by a currently-active protocol request (or other operation) have a positive refcount, and threfore should not be present at the cold end of an lru queue if the cache is well-sized.

Cache entries with lock and open state are not eligible for collection under ordinary circumstances, so are kept on a separate lru_pinned list to retain constant time.

The locking discipline for this module is complex, because an entry LRU can either be found through the cache entry in which it is embedded (through a hash table or weakref lookup) or one can be found on the queue. Thus, we have some sections for which locking the entry then the queue is natural, and others for which locking the queue then the entry is natural. Because it is the most common case in request processing, we have made the lock the queue case the defined lock order.

This introduces some complication, particularly in the case of cache_inode_lru_get and the repaer thread, which access entries through their queue. Therefore, we introduce the following rules for accessing LRU entries:

The LRU refcount may be increased by a thread holding either the entry lock or the lock for the queue holding the entry.
The entry flags may be set or inspected only by a thread holding the lock on that entry.
An entry may only be removed from or inserted into a queue by a thread holding a lock on both the entry and the queue.
A thread may only decrement the reference count while holding the entry lock.
A thread that wishes to decrement the reference count must check that the reference count is greater than LRU_SENTINEL_REFCOUNT and, if not, acquire the queue lock before decrementing it. When the reference count falls to 0, the controlling thread will have already acquired the queue lock. It must then set the LRU_ENTRY_CONDEMNED bit on the entry's flags, and remove it from the queue. It must then drop both the entry and queue lock, call pthread_yield, and reacquire the entry lock before continuing with disposal.
A thread wishing to operate on an entry picked from a given queue fragment must lock that queue fragment, find the entry, and increase its reference count by one. It must then store a pointer to the entry and release the queue lock before acquiring the entry lock. If the LRU_ENTRY_CONDEMNED bit is set, it must relinquish its lock on the entry and attempt no further access to it. Otherwise, it must examine the flags and lane stored in the entry to determine the current queue fragment containing it, rather than assuming that the original location is still valid.

Definition in file cache_inode_lru.c.

Define Documentation

#define ALIGNED_ALLOC ( _s )

Value:

((void *)(((unsigned long)malloc((_s)+CACHE_LINE_SIZE*2) + \
                CACHE_LINE_SIZE - 1) & ~(CACHE_LINE_SIZE-1)))

Definition at line 141 of file cache_inode_lru.c.

#define CACHE_LINE_SIZE 64

Definition at line 139 of file cache_inode_lru.c.

#define CACHE_PAD ( _n ) char __pad ## _n [CACHE_LINE_SIZE]

Definition at line 140 of file cache_inode_lru.c.

Function Documentation

cache_inode_status_t cache_inode_dec_pin_ref ( cache_entry_t * entry )

Function to let the state layer rlease a pin.

This function moves the given entry out of the pinned queue fragment for its lane. If the entry is not pinned, it is a no-op.

Parameters:

[in] entry The entry to be moved

Return values:

CACHE_INODE_SUCCESS if the entry was moved.

Definition at line 1211 of file cache_inode_lru.c.

cache_inode_status_t cache_inode_inc_pin_ref ( cache_entry_t * entry )

Function to let the state layer pin an entry.

This function moves the given entry to the pinned queue fragment for its lane. If the entry is already pinned, it is a no-op.

Parameters:

[in] entry The entry to be moved

Return values:

CACHE_INODE_SUCCESS	if the entry was moved.
CACHE_INODE_DEAD_ENTRY	if the entry is in the process of disposal

Definition at line 1155 of file cache_inode_lru.c.

cache_entry_t* cache_inode_lru_get	(	cache_inode_status_t *	status,
		uint32_t	flags
	)		`[read]`

Re-use or allocate an entry.

This function repurposes a resident entry in the LRU system if the system is above low-water mark, and allocates a new one otherwise. On success, this function always returns an entry with two references (one for the sentinel, one to allow the caller's use.)

Parameters:

[in]	status	Returned status
[in]	flags	Flags governing call

Returns:: CACHE_INODE_SUCCESS or error.

Definition at line 1056 of file cache_inode_lru.c.

void cache_inode_lru_kill ( cache_entry_t * entry )

Destroy the sentinel refcount safely.

This function decrements the refcount by one unless the LRU_FLAG_KILLED bit is set in the flags word. This is intended to allow a function that needs to remove an extra refcount (the sentinel) to be called multiple times without causing an underflow.

Parameters:

[in] entry The entry to decrement.

Definition at line 1307 of file cache_inode_lru.c.

void cache_inode_lru_pkginit ( void )

Initialize subsystem

Definition at line 876 of file cache_inode_lru.c.

void cache_inode_lru_pkgshutdown ( void )

Shutdown subsystem

Definition at line 1032 of file cache_inode_lru.c.

cache_inode_status_t cache_inode_lru_ref	(	cache_entry_t *	entry,
		uint32_t	flags
	)

Get a reference.

This function acquires a reference on the given cache entry, if the entry is still live. Terrible things will happen if you call this function and don't check its return value.

Parameters:

[in]	entry	The entry on which to get a reference
[in]	flags	Flags indicating the type of reference sought

Return values:

CACHE_INODE_SUCCESS	if the reference was acquired
CACHE_INODE_DEAD_ENTRY	if the object is being disposed

Definition at line 1247 of file cache_inode_lru.c.

void cache_inode_lru_unref	(	cache_entry_t *	entry,
		uint32_t	flags
	)

Relinquish a reference.

This function relinquishes a reference on the given cache entry. It follows the disposal/recycling lock discipline given at the beginning of the file.

The supplied entry is always either unlocked or destroyed by the time this function returns.

Parameters:

[in]	entry	The entry on which to release a reference
[in]	flags	Currently significant are and LRU_FLAG_LOCKED (indicating that the caller holds the LRU mutex lock for this entry.)

Definition at line 1337 of file cache_inode_lru.c.

void cache_inode_unpinnable ( cache_entry_t * entry )

Make it impossible to pin an entry.

This function makes it impossible to pin an entry, but does not unpin it.

Parameters:

[in] entry The entry to be moved

Definition at line 1191 of file cache_inode_lru.c.

void lru_wake_thread ( uint32_t flags )

Wake the LRU thread to free FDs.

This function wakes the LRU reaper thread to free FDs and should be called when we are over the high water mark.

Parameters:

[in] flags Flags to affect the wake (currently none)

Definition at line 1397 of file cache_inode_lru.c.

Variable Documentation

struct lru_state lru_state

Definition at line 124 of file cache_inode_lru.c.

size_t open_fd_count = 0

This is a global counter of files opened by cache_inode. This is preliminary expected to go away. Problems with this method are that it overcounts file descriptors for FSALs that don't use them for open files, and, under the Lieb Rearchitecture, FSALs will be responsible for caching their own file descriptors, with interfaces for Cache_Inode to interrogate them as to usage or instruct them to close them.

Definition at line 178 of file cache_inode_lru.c.

cache_inode_lru.c File Reference

Classes

Defines

Functions

Variables

Detailed Description

DESCRIPTION

Define Documentation

Function Documentation

Variable Documentation