fs/xfs/xfs_mru_cache.c

Source file repositories/reference/linux-study-clean/fs/xfs/xfs_mru_cache.c

File Facts

System
Linux kernel
Corpus path
fs/xfs/xfs_mru_cache.c
Extension
.c
Size
17677 bytes
Lines
542
Domain
Core OS
Bucket
VFS And Filesystem Core
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

struct xfs_mru_cache {
	struct radix_tree_root	store;     /* Core storage data structure.  */
	struct list_head	*lists;    /* Array of lists, one per grp.  */
	struct list_head	reap_list; /* Elements overdue for reaping. */
	spinlock_t		lock;      /* Lock to protect this struct.  */
	unsigned int		grp_count; /* Number of discrete groups.    */
	unsigned int		grp_time;  /* Time period spanned by grps.  */
	unsigned int		lru_grp;   /* Group containing time zero.   */
	unsigned long		time_zero; /* Time first element was added. */
	xfs_mru_cache_free_func_t free_func; /* Function pointer for freeing. */
	struct delayed_work	work;      /* Workqueue data for reaping.   */
	unsigned int		queued;	   /* work has been queued */
	void			*data;
};

static struct workqueue_struct	*xfs_mru_reap_wq;

/*
 * When inserting, destroying or reaping, it's first necessary to update the
 * lists relative to a particular time.  In the case of destroying, that time
 * will be well in the future to ensure that all items are moved to the reap
 * list.  In all other cases though, the time will be the current time.
 *
 * This function enters a loop, moving the contents of the LRU list to the reap
 * list again and again until either a) the lists are all empty, or b) time zero
 * has been advanced sufficiently to be within the immediate element lifetime.
 *
 * Case a) above is detected by counting how many groups are migrated and
 * stopping when they've all been moved.  Case b) is detected by monitoring the
 * time_zero field, which is updated as each group is migrated.
 *
 * The return value is the earliest time that more migration could be needed, or
 * zero if there's no need to schedule more work because the lists are empty.
 */
STATIC unsigned long
_xfs_mru_cache_migrate(
	struct xfs_mru_cache	*mru,
	unsigned long		now)
{
	unsigned int		grp;
	unsigned int		migrated = 0;
	struct list_head	*lru_list;

	/* Nothing to do if the data store is empty. */
	if (!mru->time_zero)
		return 0;

	/* While time zero is older than the time spanned by all the lists. */
	while (mru->time_zero <= now - mru->grp_count * mru->grp_time) {

		/*
		 * If the LRU list isn't empty, migrate its elements to the tail
		 * of the reap list.
		 */
		lru_list = mru->lists + mru->lru_grp;
		if (!list_empty(lru_list))
			list_splice_init(lru_list, mru->reap_list.prev);

		/*
		 * Advance the LRU group number, freeing the old LRU list to
		 * become the new MRU list; advance time zero accordingly.
		 */
		mru->lru_grp = (mru->lru_grp + 1) % mru->grp_count;
		mru->time_zero += mru->grp_time;

		/*
		 * If reaping is so far behind that all the elements on all the
		 * lists have been migrated to the reap list, it's now empty.
		 */
		if (++migrated == mru->grp_count) {
			mru->lru_grp = 0;
			mru->time_zero = 0;
			return 0;
		}
	}

	/* Find the first non-empty list from the LRU end. */
	for (grp = 0; grp < mru->grp_count; grp++) {

		/* Check the grp'th list from the LRU end. */
		lru_list = mru->lists + ((mru->lru_grp + grp) % mru->grp_count);
		if (!list_empty(lru_list))
			return mru->time_zero +
			       (mru->grp_count + grp) * mru->grp_time;
	}

	/* All the lists must be empty. */
	mru->lru_grp = 0;
	mru->time_zero = 0;
	return 0;

Annotation

Implementation Notes