subsys/demand_paging/eviction/nru.c

/*
 * Copyright (c) 2020 Intel Corporation
 *
 * SPDX-License-Identifier: Apache-2.0
 *
 * Not Recently Used (NRU) eviction algorithm for demand paging
 */
#include <zephyr/kernel.h>
#include <mmu.h>
#include <kernel_arch_interface.h>
#include <zephyr/init.h>

/* The accessed and dirty states of each page frame are used to create
 * a hierarchy with a numerical value. When evicting a page, try to evict
 * page with the highest value (we prefer clean, not accessed pages).
 *
 * In this ontology, "accessed" means "recently accessed" and gets cleared
 * during the periodic update.
 *
 * 0 not accessed, clean
 * 1 not accessed, dirty
 * 2 accessed, clean
 * 3 accessed, dirty
 */
static void nru_periodic_update(struct k_timer *timer)
{
	uintptr_t phys;
	struct z_page_frame *pf;
	unsigned int key = irq_lock();

	Z_PAGE_FRAME_FOREACH(phys, pf) {
		if (!z_page_frame_is_evictable(pf)) {
			continue;
		}

		/* Clear accessed bit in page tables */
		(void)arch_page_info_get(pf->addr, NULL, true);
	}

	irq_unlock(key);
}

struct z_page_frame *k_mem_paging_eviction_select(bool *dirty_ptr)
{
	unsigned int last_prec = 4U;
	struct z_page_frame *last_pf = NULL, *pf;
	bool accessed;
	bool last_dirty = false;
	bool dirty = false;
	uintptr_t flags, phys;

	Z_PAGE_FRAME_FOREACH(phys, pf) {
		unsigned int prec;

		if (!z_page_frame_is_evictable(pf)) {
			continue;
		}

		flags = arch_page_info_get(pf->addr, NULL, false);
		accessed = (flags & ARCH_DATA_PAGE_ACCESSED) != 0UL;
		dirty = (flags & ARCH_DATA_PAGE_DIRTY) != 0UL;

		/* Implies a mismatch with page frame ontology and page
		 * tables
		 */
		__ASSERT((flags & ARCH_DATA_PAGE_LOADED) != 0U,
			 "non-present page, %s",
			 ((flags & ARCH_DATA_PAGE_NOT_MAPPED) != 0U) ?
			 "un-mapped" : "paged out");

		prec = (dirty ? 1U : 0U) + (accessed ? 2U : 0U);
		if (prec == 0) {
			/* If we find a not accessed, clean page we're done */
			last_pf = pf;
			last_dirty = dirty;
			break;
		}

		if (prec < last_prec) {
			last_prec = prec;
			last_pf = pf;
			last_dirty = dirty;
		}
	}
	/* Shouldn't ever happen unless every page is pinned */
	__ASSERT(last_pf != NULL, "no page to evict");

	*dirty_ptr = last_dirty;

	return last_pf;
}

static K_TIMER_DEFINE(nru_timer, nru_periodic_update, NULL);

void k_mem_paging_eviction_init(void)
{
	k_timer_start(&nru_timer, K_NO_WAIT,
		      K_MSEC(CONFIG_EVICTION_NRU_PERIOD));
}