[RFC-PATCH 2/4] mm: Add __rcu_alloc_page_lockless() func.

[Uladzislau Rezki (Sony)]

Some background and kfree_rcu()
===============================
The pointers to be freed are stored in the per-cpu array to improve
performance, to enable an easier-to-use API, to accommodate vmalloc
memmory and to support a single argument of the kfree_rcu() when only
a pointer is passed. More details are below.

In order to maintain such per-CPU arrays there is a need in dynamic
allocation when a current array is fully populated and a new block is
required. See below the example:

 0 1 2 3      0 1 2 3
|p|p|p|p| -> |p|p|p|p| -> NULL

there are two pointer-blocks, each one can store 4 addresses
which will be freed after a grace period is passed. In reality
we store PAGE_SIZE / sizeof(void *). So to maintain such blocks
a single page is obtain via the page allocator:

    bnode = (struct kvfree_rcu_bulk_data *)
        __get_free_page(GFP_NOWAIT | __GFP_NOWARN);

after that it is attached to the "head" and its "next" pointer is
set to previous "head", so the list of blocks can be maintained and
grow dynamically until it gets drained by the reclaiming thread.

Please note. There is always a fallback if an allocation fails. In the
single argument, this is a call to synchronize_rcu() and for the two
arguments case this is to use rcu_head structure embedded in the object
being free, and then paying cache-miss penalty, also invoke the kfree()
per object instead of kfree_bulk() for groups of objects.

Why we maintain arrays/blocks instead of linking objects by the regular
"struct rcu_head" technique. See below a few but main reasons:

a) A memory can be reclaimed by invoking of the kfree_bulk()
   interface that requires passing an array and number of
   entries in it. That reduces the per-object overhead caused
   by calling kfree() per-object. This reduces the reclamation
   time.

b) Improves locality and reduces the number of cache-misses, due to
   "pointer chasing" between objects, which can be far spread between
   each other.

c) Support a "single argument" in the kvfree_rcu()
   void *ptr = kvmalloc(some_bytes, GFP_KERNEL);
   if (ptr)
        kvfree_rcu(ptr);

   We need it when an "rcu_head" is not embed into a stucture but an
   object must be freed after a grace period. Therefore for the single
   argument, such objects cannot be queued on a linked list.

   So nowadays, since we do not have a single argument but we see the
   demand in it, to workaround it people just do a simple not efficient
   sequence:
   <snip>
       synchronize_rcu(); /* Can be long and blocks a current context */
       kfree(p);
   <snip>

   More details is here: https://lkml.org/lkml/2020/4/28/1626

d) To distinguish vmalloc pointers between SLAB ones. It becomes possible
   to invoke the right freeing API for the right kind of pointer, kfree_bulk()
   or TBD: vmalloc_bulk().

e) Speeding up the post-grace-period freeing reduces the chance of a flood
   of callback's OOMing the system.

Also, please have a look here: https://lkml.org/lkml/2020/7/30/1166

Proposal
========
Introduce a lock-free function that obtain a page from the per-cpu-lists
on current CPU. It returns NULL rather than acquiring any non-raw spinlock.

Description
===========
The page allocator has two phases, fast path and slow one. We are interested
in fast path and order-0 allocations. In its turn it is divided also into two
phases: lock-less and not:

1) As a first step the page allocator tries to obtain a page from the
   per-cpu-list, so each CPU has its own one. That is why this step is
   lock-less and fast. Basically it disables irqs on current CPU in order
   to access to per-cpu data and remove a first element from the pcp-list.
   An element/page is returned to an user.

2) If there is no any available page in per-cpu-list, the second step is
   involved. It removes a specified number of elements from the buddy allocator
   transferring them to the "supplied-list/per-cpu-list" described in [1].

Summarizing. The __rcu_alloc_page_lockless() covers only [1] and can not
do step [2], due to the fact that [2] requires an access to zone->lock.
It implies that it is super fast, but a higher rate of fails is also
expected.

Usage: __rcu_alloc_page_lockless();

Link: https://lore.kernel.org/lkml/20200814215206.GL3982@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/
Not-signed-off-by: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Signed-off-by: Uladzislau Rezki (Sony) <urezki@xxxxxxxxx>
---
 include/linux/gfp.h |  1 +
 mm/page_alloc.c     | 82 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)

diff --git a/include/linux/gfp.h b/include/linux/gfp.h
index 67a0774e080b..c065031b4403 100644
--- a/include/linux/gfp.h
+++ b/include/linux/gfp.h
@@ -565,6 +565,7 @@ extern struct page *alloc_pages_vma(gfp_t gfp_mask, int order,
 
 extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
 extern unsigned long get_zeroed_page(gfp_t gfp_mask);
+extern unsigned long __rcu_alloc_page_lockless(void);
 
 void *alloc_pages_exact(size_t size, gfp_t gfp_mask);
 void free_pages_exact(void *virt, size_t size);
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 0e2bab486fea..360c68ea3491 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -4908,6 +4908,88 @@ __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
 }
 EXPORT_SYMBOL(__alloc_pages_nodemask);
 
+static struct page *__rmqueue_lockless(struct zone *zone, struct per_cpu_pages *pcp)
+{
+	struct list_head *list;
+	struct page *page;
+	int migratetype;
+
+	for (migratetype = 0; migratetype < MIGRATE_PCPTYPES; migratetype++) {
+		list = &pcp->lists[migratetype];
+		page = list_first_entry_or_null(list, struct page, lru);
+		if (page && !check_new_pcp(page)) {
+			list_del(&page->lru);
+			pcp->count--;
+			return page;
+		}
+	}
+
+	return NULL;
+}
+
+/*
+ * Semantic of this function illustrates that a page
+ * is obtained in lock-free maneer. Instead of going
+ * deeper in the page allocator, it uses the pcplists
+ * only. Such way provides lock-less allocation method.
+ *
+ * Some notes are below:
+ * - intended to use for RCU code only;
+ * - it does not use any atomic reserves.
+ */
+unsigned long __rcu_alloc_page_lockless(void)
+{
+	struct zonelist *zonelist =
+		node_zonelist(numa_node_id(), GFP_KERNEL);
+	struct zoneref *z, *preferred_zoneref;
+	struct per_cpu_pages *pcp;
+	struct page *page;
+	unsigned long flags;
+	struct zone *zone;
+
+	/*
+	 * If DEBUG_PAGEALLOC is enabled, the post_alloc_hook()
+	 * in the prep_new_page() function also does some extra
+	 * page mappings via __kernel_map_pages(), what is arch
+	 * specific. It is for debug purpose only.
+	 *
+	 * For example, powerpc variant of __kernel_map_pages()
+	 * uses sleep-able locks. Thus a lock-less access can
+	 * not be provided if debug option is activated. In that
+	 * case it is fine to revert and return NULL, since RCU
+	 * code has a fallback mechanism. It is OK if it is used
+	 * for debug kernel.
+	 */
+	if (IS_ENABLED(CONFIG_DEBUG_PAGEALLOC))
+		return 0;
+
+	/*
+	 * Preferred zone is a first one in the zonelist.
+	 */
+	preferred_zoneref = NULL;
+
+	for_each_zone_zonelist(zone, z, zonelist, ZONE_NORMAL) {
+		if (!preferred_zoneref)
+			preferred_zoneref = z;
+
+		local_irq_save(flags);
+		pcp = &this_cpu_ptr(zone->pageset)->pcp;
+		page = __rmqueue_lockless(zone, pcp);
+		if (page) {
+			__count_zid_vm_events(PGALLOC, page_zonenum(page), 1);
+			zone_statistics(preferred_zoneref->zone, zone);
+		}
+		local_irq_restore(flags);
+
+		if (page) {
+			prep_new_page(page, 0, 0, 0);
+			return (unsigned long) page_address(page);
+		}
+	}
+
+	return 0;
+}
+
 /*
  * Common helper functions. Never use with __GFP_HIGHMEM because the returned
  * address cannot represent highmem pages. Use alloc_pages and then kmap if
-- 
2.20.1