This patch adds a new page allocator interface via alloc_pages_bulk,
and __alloc_pages_bulk_nodemask. A caller requests a number of pages
to be allocated and added to a list. They can be freed in bulk using
free_pages_bulk().
The API is not guaranteed to return the requested number of pages and
may fail if the preferred allocation zone has limited free memory, the
cpuset changes during the allocation or page debugging decides to fail
an allocation. It's up to the caller to request more pages in batch
if necessary.
Note that this implementation is not very efficient and could be improved
but it would require refactoring. The intent is to make it available early
to determine what semantics are required by different callers. Once the
full semantics are nailed down, it can be refactored.
Signed-off-by: Mel Gorman <[email protected]>
---
include/linux/gfp.h | 13 +++++
mm/page_alloc.c | 113 +++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 124 insertions(+), 2 deletions(-)
diff --git a/include/linux/gfp.h b/include/linux/gfp.h
index 8572a1474e16..4903d1cc48dc 100644
--- a/include/linux/gfp.h
+++ b/include/linux/gfp.h
@@ -515,6 +515,10 @@ static inline int arch_make_page_accessible(struct page *page)
}
#endif
+int __alloc_pages_bulk_nodemask(gfp_t gfp_mask, int preferred_nid,
+ nodemask_t *nodemask, int nr_pages,
+ struct list_head *list);
+
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
nodemask_t *nodemask);
@@ -525,6 +529,14 @@ __alloc_pages(gfp_t gfp_mask, unsigned int order, int preferred_nid)
return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
}
+/* Bulk allocate order-0 pages */
+static inline unsigned long
+alloc_pages_bulk(gfp_t gfp_mask, unsigned long nr_pages, struct list_head *list)
+{
+ return __alloc_pages_bulk_nodemask(gfp_mask, numa_mem_id(), NULL,
+ nr_pages, list);
+}
+
/*
* Allocate pages, preferring the node given as nid. The node must be valid and
* online. For more general interface, see alloc_pages_node().
@@ -594,6 +606,7 @@ void * __meminit alloc_pages_exact_nid(int nid, size_t size, gfp_t gfp_mask);
extern void __free_pages(struct page *page, unsigned int order);
extern void free_pages(unsigned long addr, unsigned int order);
+extern void free_pages_bulk(struct list_head *list);
struct page_frag_cache;
extern void __page_frag_cache_drain(struct page *page, unsigned int count);
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 3e4b29ee2b1e..ff1e55793786 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -4436,6 +4436,21 @@ static void wake_all_kswapds(unsigned int order, gfp_t gfp_mask,
}
}
+/* Drop reference counts and free order-0 pages from a list. */
+void free_pages_bulk(struct list_head *list)
+{
+ struct page *page, *next;
+
+ list_for_each_entry_safe(page, next, list, lru) {
+ trace_mm_page_free_batched(page);
+ if (put_page_testzero(page)) {
+ list_del(&page->lru);
+ __free_pages_ok(page, 0, FPI_NONE);
+ }
+ }
+}
+EXPORT_SYMBOL_GPL(free_pages_bulk);
+
static inline unsigned int
gfp_to_alloc_flags(gfp_t gfp_mask)
{
@@ -4919,6 +4934,9 @@ static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
struct alloc_context *ac, gfp_t *alloc_mask,
unsigned int *alloc_flags)
{
+ gfp_mask &= gfp_allowed_mask;
+ *alloc_mask = gfp_mask;
+
ac->highest_zoneidx = gfp_zone(gfp_mask);
ac->zonelist = node_zonelist(preferred_nid, gfp_mask);
ac->nodemask = nodemask;
@@ -4960,6 +4978,99 @@ static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
return true;
}
+/*
+ * This is a batched version of the page allocator that attempts to
+ * allocate nr_pages quickly from the preferred zone and add them to list.
+ */
+int __alloc_pages_bulk_nodemask(gfp_t gfp_mask, int preferred_nid,
+ nodemask_t *nodemask, int nr_pages,
+ struct list_head *alloc_list)
+{
+ struct page *page;
+ unsigned long flags;
+ struct zone *zone;
+ struct zoneref *z;
+ struct per_cpu_pages *pcp;
+ struct list_head *pcp_list;
+ struct alloc_context ac;
+ gfp_t alloc_mask;
+ unsigned int alloc_flags;
+ int alloced = 0;
+
+ if (nr_pages == 1)
+ goto failed;
+
+ /* May set ALLOC_NOFRAGMENT, fragmentation will return 1 page. */
+ if (!prepare_alloc_pages(gfp_mask, 0, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
+ return 0;
+ gfp_mask = alloc_mask;
+
+ /* Find an allowed local zone that meets the high watermark. */
+ for_each_zone_zonelist_nodemask(zone, z, ac.zonelist, ac.highest_zoneidx, ac.nodemask) {
+ unsigned long mark;
+
+ if (cpusets_enabled() && (alloc_flags & ALLOC_CPUSET) &&
+ !__cpuset_zone_allowed(zone, gfp_mask)) {
+ continue;
+ }
+
+ if (nr_online_nodes > 1 && zone != ac.preferred_zoneref->zone &&
+ zone_to_nid(zone) != zone_to_nid(ac.preferred_zoneref->zone)) {
+ goto failed;
+ }
+
+ mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK) + nr_pages;
+ if (zone_watermark_fast(zone, 0, mark,
+ zonelist_zone_idx(ac.preferred_zoneref),
+ alloc_flags, gfp_mask)) {
+ break;
+ }
+ }
+ if (!zone)
+ return 0;
+
+ /* Attempt the batch allocation */
+ local_irq_save(flags);
+ pcp = &this_cpu_ptr(zone->pageset)->pcp;
+ pcp_list = &pcp->lists[ac.migratetype];
+
+ while (alloced < nr_pages) {
+ page = __rmqueue_pcplist(zone, ac.migratetype, alloc_flags,
+ pcp, pcp_list);
+ if (!page)
+ break;
+
+ prep_new_page(page, 0, gfp_mask, 0);
+ list_add(&page->lru, alloc_list);
+ alloced++;
+ }
+
+ if (!alloced)
+ goto failed_irq;
+
+ if (alloced) {
+ __count_zid_vm_events(PGALLOC, zone_idx(zone), alloced);
+ zone_statistics(zone, zone);
+ }
+
+ local_irq_restore(flags);
+
+ return alloced;
+
+failed_irq:
+ local_irq_restore(flags);
+
+failed:
+ page = __alloc_pages_nodemask(gfp_mask, 0, preferred_nid, nodemask);
+ if (page) {
+ alloced++;
+ list_add(&page->lru, alloc_list);
+ }
+
+ return alloced;
+}
+EXPORT_SYMBOL_GPL(__alloc_pages_bulk_nodemask);
+
/*
* This is the 'heart' of the zoned buddy allocator.
*/
@@ -4981,8 +5092,6 @@ __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
return NULL;
}
- gfp_mask &= gfp_allowed_mask;
- alloc_mask = gfp_mask;
if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
return NULL;
--
2.26.2
On Wed, Mar 10, 2021 at 01:04:17PM +0200, Shay Agroskin wrote:
>
> Mel Gorman <[email protected]> writes:
>
> >
> > diff --git a/include/linux/gfp.h b/include/linux/gfp.h
> > index 8572a1474e16..4903d1cc48dc 100644
> > --- a/include/linux/gfp.h
> > +++ b/include/linux/gfp.h
> > @@ -515,6 +515,10 @@ static inline int arch_make_page_accessible(struct
> > page *page)
> > }
> > #endif
> > +int __alloc_pages_bulk_nodemask(gfp_t gfp_mask, int preferred_nid,
> > + nodemask_t *nodemask, int nr_pages,
> > + struct list_head *list);
> > +
> > struct page *
> > __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int
> > preferred_nid,
> > nodemask_t *nodemask);
> > @@ -525,6 +529,14 @@ __alloc_pages(gfp_t gfp_mask, unsigned int order,
> > int preferred_nid)
> > return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
> > }
> > +/* Bulk allocate order-0 pages */
> > +static inline unsigned long
> > +alloc_pages_bulk(gfp_t gfp_mask, unsigned long nr_pages, struct
> > list_head *list)
> > +{
> > + return __alloc_pages_bulk_nodemask(gfp_mask, numa_mem_id(), NULL,
> > + nr_pages, list);
>
> Is the second line indentation intentional ? Why not align it to the first
> argument (gfp_mask) ?
>
No particular reason. I usually pick this as it's visually clearer to me
that it's part of the same line when the multi-line is part of an if block.
> > +}
> > +
> > /*
> > * Allocate pages, preferring the node given as nid. The node must be
> > valid and
> > * online. For more general interface, see alloc_pages_node().
> > @@ -594,6 +606,7 @@ void * __meminit alloc_pages_exact_nid(int nid,
> > size_t size, gfp_t gfp_mask);
> > extern void __free_pages(struct page *page, unsigned int order);
> > extern void free_pages(unsigned long addr, unsigned int order);
> > +extern void free_pages_bulk(struct list_head *list);
> > struct page_frag_cache;
> > extern void __page_frag_cache_drain(struct page *page, unsigned int
> > count);
> > diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> > index 3e4b29ee2b1e..ff1e55793786 100644
> > --- a/mm/page_alloc.c
> > +++ b/mm/page_alloc.c
> > @@ -4436,6 +4436,21 @@ static void wake_all_kswapds(unsigned int order,
> > gfp_t gfp_mask,
> > }
> > }
> > ...
> > +/*
> > + * This is a batched version of the page allocator that attempts to
> > + * allocate nr_pages quickly from the preferred zone and add them to
> > list.
> > + */
> > +int __alloc_pages_bulk_nodemask(gfp_t gfp_mask, int preferred_nid,
> > + nodemask_t *nodemask, int nr_pages,
> > + struct list_head *alloc_list)
> > +{
> > + struct page *page;
> > + unsigned long flags;
> > + struct zone *zone;
> > + struct zoneref *z;
> > + struct per_cpu_pages *pcp;
> > + struct list_head *pcp_list;
> > + struct alloc_context ac;
> > + gfp_t alloc_mask;
> > + unsigned int alloc_flags;
> > + int alloced = 0;
>
> Does alloced count the number of allocated pages ?
Yes.
> Do you mind renaming it to 'allocated' ?
I will if there is another version as I do not feel particularly strongly
about alloced vs allocated. alloc was to match the function name and I
don't think the change makes it much clearer.
> > <SNIP>
> > + /* Attempt the batch allocation */
> > + local_irq_save(flags);
> > + pcp = &this_cpu_ptr(zone->pageset)->pcp;
> > + pcp_list = &pcp->lists[ac.migratetype];
> > +
> > + while (alloced < nr_pages) {
> > + page = __rmqueue_pcplist(zone, ac.migratetype, alloc_flags,
> > + pcp, pcp_list);
>
> Same indentation comment as before
>
Again, simple personal perference to avoid any possibility it's mixed
up with a later line. There has not been consistent code styling
enforcement of what indentation style should be used for a multi-line
within mm/page_alloc.c
--
Mel Gorman
SUSE Labs
On Wed, 10 Mar 2021 11:38:36 +0000
Mel Gorman <[email protected]> wrote:
> On Wed, Mar 10, 2021 at 01:04:17PM +0200, Shay Agroskin wrote:
> >
> > Mel Gorman <[email protected]> writes:
> >
> > >
> > > diff --git a/include/linux/gfp.h b/include/linux/gfp.h
> > > index 8572a1474e16..4903d1cc48dc 100644
> > > --- a/include/linux/gfp.h
> > > +++ b/include/linux/gfp.h
> > > @@ -515,6 +515,10 @@ static inline int arch_make_page_accessible(struct
> > > page *page)
> > > }
> > > #endif
> > > +int __alloc_pages_bulk_nodemask(gfp_t gfp_mask, int preferred_nid,
> > > + nodemask_t *nodemask, int nr_pages,
> > > + struct list_head *list);
> > > +
> > > struct page *
> > > __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int
> > > preferred_nid,
> > > nodemask_t *nodemask);
> > > @@ -525,6 +529,14 @@ __alloc_pages(gfp_t gfp_mask, unsigned int order,
> > > int preferred_nid)
> > > return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
> > > }
> > > +/* Bulk allocate order-0 pages */
> > > +static inline unsigned long
> > > +alloc_pages_bulk(gfp_t gfp_mask, unsigned long nr_pages, struct
> > > list_head *list)
> > > +{
> > > + return __alloc_pages_bulk_nodemask(gfp_mask, numa_mem_id(), NULL,
> > > + nr_pages, list);
> >
> > Is the second line indentation intentional ? Why not align it to the first
> > argument (gfp_mask) ?
> >
>
> No particular reason. I usually pick this as it's visually clearer to me
> that it's part of the same line when the multi-line is part of an if block.
>
> > > +}
> > > +
[...]
> >
> > Same indentation comment as before
> >
>
> Again, simple personal perference to avoid any possibility it's mixed
> up with a later line. There has not been consistent code styling
> enforcement of what indentation style should be used for a multi-line
> within mm/page_alloc.c
Hi Shay, it is might be surprising that indentation style actually
differs slightly in different parts of the kernel. I started in
networking area of the kernel, and I was also surprised when I started
working in MM area that the coding style differs. I can tell you that
the indentation style Mel choose is consistent with the code styling in
MM area. I usually respect that even-though I prefer the networking
style as I was "raised" with that style.
--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
LinkedIn: http://www.linkedin.com/in/brouer
On Sat, Mar 13, 2021 at 01:16:48PM +0000, Mel Gorman wrote:
> > I'm not claiming the pagevec is definitely a win, but it's very
> > unclear which tradeoff is actually going to lead to better performance.
> > Hopefully Jesper or Chuck can do some tests and figure out what actually
> > works better with their hardware & usage patterns.
>
> The NFS user is often going to need to make round trips to get the pages it
> needs. The pagevec would have to be copied into the target array meaning
> it's not much better than a list manipulation.
I don't think you fully realise how bad CPUs are at list manipulation.
See the attached program (and run it on your own hardware). On my
less-than-a-year-old core-i7:
$ gcc -W -Wall -O2 -g array-vs-list.c -o array-vs-list
$ ./array-vs-list
walked sequential array in 0.001765s
walked sequential list in 0.002920s
walked sequential array in 0.001777s
walked shuffled list in 0.081955s
walked shuffled array in 0.007367s
If you happen to get the objects in-order, it's only 64% worse to walk
a list as an array. If they're out of order, it's *11.1* times as bad.
On Sun, 14 Mar 2021 12:52:32 +0000
Mel Gorman <[email protected]> wrote:
> mm/page_alloc: Add an array-based interface to the bulk page allocator
>
> The existing callers for the bulk allocator are storing the pages in
> arrays. This patch adds an array-based interface to the API to avoid
> multiple list iterations. The page list interface is preserved to
> avoid requiring all users of the bulk API to allocate and manage
> enough storage to store the pages.
I'm testing this patch, see results below and in commit[1]. The array
variant is clearly faster in these micro-benchmarks.
(Some comment inlined about code)
The change to my page_bench04_bulk is here[1]:
[1] https://github.com/netoptimizer/prototype-kernel/commit/4c41fe0d4107f514
Notice these "per elem" measurements are alloc+free cost for order-0 pages.
BASELINE
single_page alloc+put: 207 cycles(tsc) 57.773 ns
LIST variant: time_bulk_page_alloc_free_list: step=bulk size
Per elem: 294 cycles(tsc) 81.866 ns (step:1)
Per elem: 214 cycles(tsc) 59.477 ns (step:2)
Per elem: 199 cycles(tsc) 55.504 ns (step:3)
Per elem: 192 cycles(tsc) 53.489 ns (step:4)
Per elem: 188 cycles(tsc) 52.456 ns (step:8)
Per elem: 184 cycles(tsc) 51.346 ns (step:16)
Per elem: 183 cycles(tsc) 50.883 ns (step:32)
Per elem: 184 cycles(tsc) 51.236 ns (step:64)
Per elem: 189 cycles(tsc) 52.620 ns (step:128)
ARRAY variant: time_bulk_page_alloc_free_array: step=bulk size
Per elem: 195 cycles(tsc) 54.174 ns (step:1)
Per elem: 123 cycles(tsc) 34.224 ns (step:2)
Per elem: 113 cycles(tsc) 31.430 ns (step:3)
Per elem: 108 cycles(tsc) 30.003 ns (step:4)
Per elem: 102 cycles(tsc) 28.417 ns (step:8)
Per elem: 98 cycles(tsc) 27.475 ns (step:16)
Per elem: 96 cycles(tsc) 26.901 ns (step:32)
Per elem: 95 cycles(tsc) 26.487 ns (step:64)
Per elem: 94 cycles(tsc) 26.170 ns (step:128)
The array variant is clearly faster.
It it worth mentioning that bulk=1 result in fallback to normal
single page allocation via __alloc_pages().
> Signed-off-by: Mel Gorman <[email protected]>
>
> diff --git a/include/linux/gfp.h b/include/linux/gfp.h
> index 4a304fd39916..fb6234e1fe59 100644
> --- a/include/linux/gfp.h
> +++ b/include/linux/gfp.h
> @@ -520,13 +520,20 @@ struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
>
> int __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
> nodemask_t *nodemask, int nr_pages,
> - struct list_head *list);
> + struct list_head *page_list,
> + struct page **page_array);
>
> /* Bulk allocate order-0 pages */
> static inline unsigned long
> -alloc_pages_bulk(gfp_t gfp, unsigned long nr_pages, struct list_head *list)
> +alloc_pages_bulk_list(gfp_t gfp, unsigned long nr_pages, struct list_head *list)
> {
> - return __alloc_pages_bulk(gfp, numa_mem_id(), NULL, nr_pages, list);
> + return __alloc_pages_bulk(gfp, numa_mem_id(), NULL, nr_pages, list, NULL);
> +}
> +
> +static inline unsigned long
> +alloc_pages_bulk_array(gfp_t gfp, unsigned long nr_pages, struct page **page_array)
> +{
> + return __alloc_pages_bulk(gfp, numa_mem_id(), NULL, nr_pages, NULL, page_array);
> }
>
> /*
> diff --git a/mm/page_alloc.c b/mm/page_alloc.c
> index 3e0c87c588d3..96590f0726c7 100644
> --- a/mm/page_alloc.c
> +++ b/mm/page_alloc.c
> @@ -4965,13 +4965,20 @@ static inline bool prepare_alloc_pages(gfp_t gfp, unsigned int order,
>
> /*
> * This is a batched version of the page allocator that attempts to
> - * allocate nr_pages quickly from the preferred zone and add them to list.
> + * allocate nr_pages quickly from the preferred zone. Pages are added
> + * to page_list if page_list is not NULL, otherwise it is assumed
> + * that the page_array is valid.
> + *
> + * If using page_array, only NULL elements are populated with pages.
> + * The caller must ensure that the array has enough NULL elements
> + * to store nr_pages or the buffer overruns.
> *
> * Returns the number of pages allocated.
> */
> int __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
> nodemask_t *nodemask, int nr_pages,
> - struct list_head *alloc_list)
> + struct list_head *page_list,
> + struct page **page_array)
> {
> struct page *page;
> unsigned long flags;
> @@ -4987,6 +4994,9 @@ int __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
> if (WARN_ON_ONCE(nr_pages <= 0))
> return 0;
>
> + if (WARN_ON_ONCE(!page_list && !page_array))
> + return 0;
> +
> if (nr_pages == 1)
> goto failed;
>
> @@ -5035,7 +5045,24 @@ int __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
> break;
> }
>
> - list_add(&page->lru, alloc_list);
> + if (page_list) {
> + /* New page prep is deferred */
> + list_add(&page->lru, page_list);
> + } else {
> + /* Skip populated elements */
> + while (*page_array)
> + page_array++;
I don't like this approach as it is a dangerous construct, that can run
wild through the memory. I have coded up another approach where I have
an nr_avail counter instead, that will "include" and count existing
elements in the array.
> +
> + /*
> + * Array pages must be prepped immediately to
> + * avoid tracking which pages are new and
> + * which ones were already on the array.
> + */
> + prep_new_page(page, 0, gfp, 0);
> + *page_array = page;
> + page_array++;
> + }
> +
> allocated++;
> }
>
> @@ -5044,9 +5071,12 @@ int __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
>
> local_irq_restore(flags);
>
> - /* Prep page with IRQs enabled to reduce disabled times */
> - list_for_each_entry(page, alloc_list, lru)
> - prep_new_page(page, 0, gfp, 0);
> + /* Prep pages with IRQs enabled if using a list */
> + if (page_list) {
> + list_for_each_entry(page, page_list, lru) {
> + prep_new_page(page, 0, gfp, 0);
> + }
> + }
>
> return allocated;
>
> @@ -5056,7 +5086,10 @@ int __alloc_pages_bulk(gfp_t gfp, int preferred_nid,
> failed:
> page = __alloc_pages(gfp, 0, preferred_nid, nodemask);
> if (page) {
> - list_add(&page->lru, alloc_list);
> + if (page_list)
> + list_add(&page->lru, page_list);
> + else
> + *page_array = page;
> allocated = 1;
> }
>
--
Best regards,
Jesper Dangaard Brouer
MSc.CS, Principal Kernel Engineer at Red Hat
LinkedIn: http://www.linkedin.com/in/brouer