linux-lru.txt

LRU Organization
----------------

struct pagevec
--> Collection of pages to be put in an appropriate LRU list
--> Intermediary for moving pages between active and inactive LRU lists
    or for adding and removing pages to and from LRU lists
--> Holds up to 15 pages
--> Managed via helper functions
    --> pagevec_add() adds a page and returns the remaining number of free slots
    --> pagevec_count() returns the number of used slots
    --> pagevec_space() returns the number of free slots
    --> pagevec_init() initializes a pagevec, all slots are emptied and drain is
        not required
    --> pagevec_reinit() reinitializes a pagevec, all slots are emptied, whether
        drain is required or not depends on its previous state
    --> pagevec_add_and_need_flush()
        --> Returns true if pagevec is full after addition or page is compound

struct lru_pvecs
--> Has different pagevecs that serve different purposes
    --> lru_add
        --> Contains new pages to be considered for addition to LRU lists
    --> lru_deactivate_file
        --> Contains existing file-backed pages from both active and inactive
	    file LRU lists that are to be moved between lists or place at some
	    strategic positions of the inactive list (head or tail) depending
	    on the page flags
    --> lru_deactivate
    --> lru_lazyfree
    --> activate_page
    --> lru_rotate
        --> Special pagevec outside struct lru_pvecs
--> All pagevecs are managed at a per-cpu granularity

struct lruvec
--> Collection of different LRU lists
    --> LRU_INACTIVE_ANON
    --> LRU_ACTIVE_ANON
    --> LRU_INACTIVE_FILE
    --> LRU_ACTIVE_FILE
    --> LRU_UNEVICTABLE
--> Each lruvec is managed at a per-node (i.e. pg_data_t) granularity

Adding pages to LRU lists
-------------------------

add_page_to_lru_list()
--> Adds a page to the head of the appropriate LRU list
--> Calls page_lru() to determine the appropriate LRU list
    --> If Unevictable flag is set, page goes to LRU_UNEVICTABLE
    --> If SwapBacked flag is set, i.e. page is anonymous, page goes to
        LRU_ACTIVE_ANON if Active flag is also set else LRU_INACTIVE_ANON
    --> If SwapBacked flag is not set, i.e. page is file-backed, page goes
        to LRU_ACTIVE_FILE if Active flag is also set else LRU_INACTIVE_FILE
--> Readjusts the size of the lruvec and updates the corresponding zone stats

add_page_to_lru_list_tail()
--> Same as add_page_to_lru_list(), except that it adds the page to the tail
    of the appropriate LRU list instead

Removing pages from LRU lists
-----------------------------

del_page_from_lru_list()
--> Removes a page from the appropriate LRU list

Maintaining LRU lists
---------------------

__putback_lru_fast()
--> Putback multiple evictable pages to the LRU
--> Batched putback of evictable pages that bypasses the per-cpu pagevecs
--> 

lru_cache_add()
lru_add_drain_cpu()
--> __pagevec_lru_add()

lru_add_drain_cpu()
--> Moves pages in different per-cpu pagevecs in and out of LRU lists
    --> Calls __pagevec_lru_add() on lru_add pagevec
    --> Calls pagevec_move_tail_fn() on lru_rotate pagevec
    --> Calls lru_deactivate_file_fn() on lru_deactivate_file pagevec
        --> Active, mapped page remains in active list
	--> Active, dirty page is moved to the head of inactive list with
	    reclaim flag set
	--> Inactive, mapped page remains in inactive list
	--> Inactive, dirty page is moved to the head of inactive list with
	    reclaim flag set
    --> Calls lru_deactivate_fn() on lru_deactivate pagevec
    --> Calls lru_lazyfree_fn() on lru_lazyfree pagevec
    --> Calls __activate_page() on activate_page pagevec

shrink_active_list()
shrink_inactive_list()
--> Calls lru_add_drain()

LRU Per-CPU Page Vector Usage
-----------------------------

lru_rotate.pvec is used in
--> end_page_writeback()
    --> rotate_reclaimable_page()
        --> pvec = this_cpu_ptr(&lru_rotate.pvec)
        --> if (pagevec_add_and_need_flush(pvec, page))
            --> pagevec_lru_move_fn(pvec, pagevec_move_tail_fn)
--> lru_add_drain_cpu()
    --> pvec = &per_cpu(lru_rotate.pvec, cpu)
    --> if (data_race(pagevec_count(pvec)))
        --> pagevec_lru_move_fn(pvec, pagevec_move_tail_fn)

lru_pvecs.lru_add is used in
--> mark_page_accessed()
    --> __lru_cache_activate_page()
        --> pvec = this_cpu_ptr(&lru_pvecs.lru_add)
--> lru_cache_add()
    --> pvec = this_cpu_ptr(&lru_pvecs.lru_add)
    --> if (pagevec_add_and_need_flush(pvec, page))
        --> __pagevec_lru_add(pvec)
--> lru_add_drain_cpu()

lru_pvecs.lru_deactivate is used in
--> lru_add_drain_cpu()
--> madvise_cold_or_pageout_pte_range()
    --> deactivate_page()
        --> pvec = this_cpu_ptr(&lru_pvecs.lru_deactivate)
        --> if (pagevec_add_and_need_flush(pvec, page))
            --> pagevec_lru_move_fn(pvec, lru_deactivate_fn)

lru_pvecs.lru_deactivate_file is used in
--> lru_add_drain_cpu()
--> Multiple places in FS code
    --> invalidate_mapping_pages()
        --> __invalidate_mapping_pages()
            --> deactivate_file_page()
                --> pvec = this_cpu_ptr(&lru_pvecs.lru_deactivate_file)
                --> if (pagevec_add_and_need_flush(pvec, page))
                    --> pagevec_lru_move_fn(pvec, lru_deactivate_file_fn)
--> generic_fadvise() upon POSIX_FADV_DONTNEED
    --> invalidate_mapping_pagevec()
        --> __invalidate_mapping_pages()
            --> deactivate_file_page()
                --> pvec = this_cpu_ptr(&lru_pvecs.lru_deactivate_file)
                --> if (pagevec_add_and_need_flush(pvec, page))
                    --> pagevec_lru_move_fn(pvec, lru_deactivate_file_fn)

lru_pvecs.lru_lazyfree is used in
--> lru_add_drain_cpu()
--> mark_page_lazyfree()
    --> if (pagevec_add_and_need_flush(pvec, page))
        --> pagevec_lru_move_fn(pvec, lru_lazyfree_fn)

lru_pvecs.activate_page is used in
--> activate_page_drain()
    --> if (pagevec_count(pvec))
        --> pagevec_lru_move_fn(pvec, __activate_page)
--> need_activate_page_drain()
    --> pagevec_count(&per_cpu(lru_pvecs.activate_page, cpu)) != 0
--> mark_page_accessed()
    --> activate_page()
        --> pvec = this_cpu_ptr(&lru_pvecs.activate_page)
        --> if (pagevec_add_and_need_flush(pvec, page))
            --> pagevec_lru_move_fn(pvec, __activate_page)