mm: page_alloc: High-order per-cpu page allocator
Subsystems (4)
RFC PATCH 1/1 mm: page_alloc: High-order per-cpu page allocator
SLUB has been the default small kernel object allocator for quite some time but it is not universally used due to performance concerns and a reliance on high-order pages. The high-order concerns has two major components -- high-order pages are not always available and high-order page allocations potentially contend on the zone->lock. This patch addresses some concerns about the zone lock contention by extending the per-cpu page allocator to cache high-order pages. The patch makes the following modifications
o New per-cpu lists are added to cache the high-order pages. This increases the cache footprint of the per-cpu allocator and overall usage but for some workloads, this will be offset by reduced contention on zone->lock. The first MIGRATE_PCPTYPE entries in the list are per-migratetype. The remaining are high-order caches up to and including PAGE_ALLOC_COSTLY_ORDER
o pcp accounting during free is now confined to free_pcppages_bulk as it's impossible for the caller to know exactly how many pages were freed. Due to the high-order caches, the number of pages drained for a request is no longer precise.
o When draining pages, it'll use the migratetype as a hint about which list to drain first. This is to avoid a case where MIGRATE_UNMOVABLE order-0 pages are artifically preserved and draining focuses on the high-order pages.
o The high watermark for per-cpu pages is increased to reduce the probability that a single refill causes a drain on the next free.
The benefit depends on both the workload and the machine as ultimately the determining factor is whether cache line bounces on zone->lock or contention is a problem. The patch was tested on a variety of workloads and machines, some of which are reported here.
This is the result from netperf running UDP_STREAM on localhost. It was selected on the basis that it is slab-intensive and has been the subject of previous SLAB vs SLUB comparisons with the caveat that this is not testing between two physical hosts.
2-socket modern machine
4.9.0-rc5 4.9.0-rc5
vanilla hopcpu-v1r9
Hmean send-64 178.38 ( 0.00%) 189.49 ( 6.23%)
Hmean send-128 351.49 ( 0.00%) 379.40 ( 7.94%)
Hmean send-256 671.23 ( 0.00%) 735.03 ( 9.50%)
Hmean send-1024 2663.60 ( 0.00%) 2842.09 ( 6.70%)
Hmean send-2048 5126.53 ( 0.00%) 5547.27 ( 8.21%)
Hmean send-3312 7949.99 ( 0.00%) 8515.82 ( 7.12%)
Hmean send-4096 9433.56 ( 0.00%) 9964.34 ( 5.63%)
Hmean send-8192 15940.64 ( 0.00%) 17120.50 ( 7.40%)
Hmean send-16384 26699.54 ( 0.00%) 28307.62 ( 6.02%)
Hmean recv-64 178.38 ( 0.00%) 189.48 ( 6.23%)
Hmean recv-128 351.49 ( 0.00%) 379.39 ( 7.94%)
Hmean recv-256 671.20 ( 0.00%) 734.94 ( 9.50%)
Hmean recv-1024 2663.45 ( 0.00%) 2841.86 ( 6.70%)
Hmean recv-2048 5126.26 ( 0.00%) 5546.79 ( 8.20%)
Hmean recv-3312 7949.50 ( 0.00%) 8515.34 ( 7.12%)
Hmean recv-4096 9433.04 ( 0.00%) 9963.78 ( 5.63%)
Hmean recv-8192 15939.64 ( 0.00%) 17119.63 ( 7.40%)
Hmean recv-16384 26698.44 ( 0.00%) 28305.98 ( 6.02%)1-socket 6 year old machine
4.9.0-rc5 4.9.0-rc5
vanilla hopcpu-v1r9
Hmean send-64 87.47 ( 0.00%) 87.69 ( 0.25%)
Hmean send-128 174.36 ( 0.00%) 175.22 ( 0.49%)
Hmean send-256 347.52 ( 0.00%) 350.15 ( 0.76%)
Hmean send-1024 1363.03 ( 0.00%) 1374.17 ( 0.82%)
Hmean send-2048 2632.68 ( 0.00%) 2673.81 ( 1.56%)
Hmean send-3312 4123.19 ( 0.00%) 4197.08 ( 1.79%)
Hmean send-4096 5056.48 ( 0.00%) 5089.92 ( 0.66%)
Hmean send-8192 8784.22 ( 0.00%) 8951.35 ( 1.90%)
Hmean send-16384 15081.60 ( 0.00%) 15283.81 ( 1.34%)
Hmean recv-64 86.19 ( 0.00%) 87.40 ( 1.39%)
Hmean recv-128 173.93 ( 0.00%) 174.71 ( 0.44%)
Hmean recv-256 346.19 ( 0.00%) 348.82 ( 0.76%)
Hmean recv-1024 1358.28 ( 0.00%) 1369.33 ( 0.81%)
Hmean recv-2048 2623.45 ( 0.00%) 2665.06 ( 1.59%)
Hmean recv-3312 4108.63 ( 0.00%) 4180.29 ( 1.74%)
Hmean recv-4096 5037.25 ( 0.00%) 5073.50 ( 0.72%)
Hmean recv-8192 8762.32 ( 0.00%) 8918.69 ( 1.78%)
Hmean recv-16384 15042.36 ( 0.00%) 15209.75 ( 1.11%)These are quite different results but illustrate that the patch is dependent on the CPU. The results are similar for TCP_STREAM on the two-socket machine but shows more consistent improvements on the 1-socket old machine highlighting that the impact is both CPU and workload dependent.
Similar observations are made when using sockperf to send packets of different sizes over localhost. There are a mix of gains and losses depending on machine, packet size and protocol which was overall inconclusive.
hackbench was also tested with both socket and pipes and both processes and threads and the results are interesting in terms of how variability is imapcted
1-socket machine -- pipes and processes
4.9.0-rc5 4.9.0-rc5
vanilla highmark-v1r12
Amean 1 12.9637 ( 0.00%) 12.9570 ( 0.05%)
Amean 3 13.4770 ( 0.00%) 13.4447 ( 0.24%)
Amean 5 18.5333 ( 0.00%) 19.0917 ( -3.01%)
Amean 7 24.5690 ( 0.00%) 26.1010 ( -6.24%)
Amean 12 39.7990 ( 0.00%) 40.6763 ( -2.20%)
Amean 16 56.0520 ( 0.00%) 58.2530 ( -3.93%)
Stddev 1 0.3847 ( 0.00%) 0.3137 ( 18.45%)
Stddev 3 0.2652 ( 0.00%) 0.3697 (-39.41%)
Stddev 5 0.5589 ( 0.00%) 0.9438 (-68.88%)
Stddev 7 0.5310 ( 0.00%) 0.2699 ( 49.18%)
Stddev 12 1.0780 ( 0.00%) 0.3421 ( 68.26%)
Stddev 16 2.1138 ( 0.00%) 1.5677 ( 25.84%)It's not a universal win but the differences are within the noise. What is interesting is that for high thread counts that variability is much reduced -- the time when contention would be expected to be high. This is not consistent across all machines but it mostly applies.
While pipes, sockets and threads were tested, they did not show anything else interesting.
fsmark was tested with zero-sized files to continually allocate slab objects but didn't show any differences. This can be explained by the fact that the workload is only allocating and does not have mix of allocs/frees that would benefit from the caching. It was tested to ensure no major harm was done.
--- include/linux/mmzone.h | 20 ++++++++- mm/page_alloc.c | 120 +++++++++++++++++++++++++++++-------------------- 2 files changed, 90 insertions(+), 50 deletions(-)
include/linux/mmzone.h +19 -1
@@ -255,6 +255,24 @@ enum zone_watermarks { NR_WMARK }; +/* +* One per migratetype for order-0 pages and one per high-order up to +* and including PAGE_ALLOC_COSTLY_ORDER. This may allow unmovable +* allocations to contaminate reclaimable pageblocks if high-order +* pages are heavily used. +*/ +#define NR_PCP_LISTS (MIGRATE_PCPTYPES + PAGE_ALLOC_COSTLY_ORDER + 1) + +static inline unsigned int pindex_to_order (unsigned int pindex) +{ +return pindex <MIGRATE_PCPTYPES ?0 : pindex -MIGRATE_PCPTYPES +1 ; +} + +static inline unsigned int order_to_pindex (int migratetype,unsigned int order) +{ +return (order ==0 ) ? migratetype :MIGRATE_PCPTYPES -1 + order; +} +#define min_wmark_pages (z) (z->watermark[WMARK_MIN])#define low_wmark_pages (z) (z->watermark[WMARK_LOW])#define high_wmark_pages (z) (z->watermark[WMARK_HIGH])
@@ -265,7 +283,7 @@ struct per_cpu_pages {int batch;/* chunk size for buddy add/remove */ /* Lists of pages, one per migrate type stored on the pcp-lists */ -struct list_head lists[MIGRATE_PCPTYPES ]; +struct list_head lists[NR_PCP_LISTS ]; };struct per_cpu_pageset {
mm/page_alloc.c +71 -49
257 lines not on this page · raw message
Signature · 7 lines
2.10.2 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
On 11/21/2016 04:55 PM, Mel Gorman wrote:
...
Quoted 5 lines
hackbench was also tested with both socket and pipes and both processes and threads and the results are interesting in terms of how variability is imapcted
1-socket machine -- pipes and processes
Quoted 8 lines
4.9.0-rc5 4.9.0-rc5
vanilla highmark-v1r12
Amean 1 12.9637 ( 0.00%) 12.9570 ( 0.05%)
Amean 3 13.4770 ( 0.00%) 13.4447 ( 0.24%)
Amean 5 18.5333 ( 0.00%) 19.0917 ( -3.01%)
Amean 7 24.5690 ( 0.00%) 26.1010 ( -6.24%)
Amean 12 39.7990 ( 0.00%) 40.6763 ( -2.20%)
Amean 16 56.0520 ( 0.00%) 58.2530 ( -3.93%)Here, higher values are better or worse?
Quoted 31 lines
Stddev 1 0.3847 ( 0.00%) 0.3137 ( 18.45%) Stddev 3 0.2652 ( 0.00%) 0.3697 (-39.41%) Stddev 5 0.5589 ( 0.00%) 0.9438 (-68.88%) Stddev 7 0.5310 ( 0.00%) 0.2699 ( 49.18%) Stddev 12 1.0780 ( 0.00%) 0.3421 ( 68.26%) Stddev 16 2.1138 ( 0.00%) 1.5677 ( 25.84%)It's not a universal win but the differences are within the noise. What is interesting is that for high thread counts that variability is much reduced -- the time when contention would be expected to be high. This is not consistent across all machines but it mostly applies.
While pipes, sockets and threads were tested, they did not show anything else interesting.
fsmark was tested with zero-sized files to continually allocate slab objects but didn't show any differences. This can be explained by the fact that the workload is only allocating and does not have mix of allocs/frees that would benefit from the caching. It was tested to ensure no major harm was done.
Signed-off-by Mel Gorman <[email protected]>--- include/linux/mmzone.h | 20 ++++++++- mm/page_alloc.c | 120 +++++++++++++++++++++++++++++-------------------- 2 files changed, 90 insertions(+), 50 deletions(-)include/linux/mmzone.h +0
-0
include/linux/mmzone.h enum zone_watermarks { · line 264
Quoted 10 lines
include/linux/mmzone.h +7
-0@@ -255,6 +255,24 @@ enum zone_watermarks { NR_WMARK }; +/* +* One per migratetype for order-0 pages and one per high-order up to +* and including PAGE_ALLOC_COSTLY_ORDER. This may allow unmovable +* allocations to contaminate reclaimable pageblocks if high-order +* pages are heavily used. +*/ +#define NR_PCP_LISTS (MIGRATE_PCPTYPES + PAGE_ALLOC_COSTLY_ORDER + 1)
Should it be "- 1" instead of "+ 1"?
include/linux/mmzone.h enum zone_watermarks { · line 273
Quoted 9 lines
include/linux/mmzone.h +9
-0+ +static inline unsigned int pindex_to_order (unsigned int pindex) +{ +return pindex <MIGRATE_PCPTYPES ?0 : pindex -MIGRATE_PCPTYPES +1 ; +} + +static inline unsigned int order_to_pindex (int migratetype,unsigned int order) +{ +return (order ==0 ) ? migratetype :MIGRATE_PCPTYPES -1 + order;
HereI think that "MIGRATE_PCPTYPES + order - 1" would be easier to understand as the array is for all migratetypes, but the order is shifted?
include/linux/mmzone.h static bool bulkfree_pcp_prepare(struct page *page) · line 1089
Quoted 11 lines
include/linux/mmzone.h +3
-3@@ -1083,10 +1083,12 @@ static bool bulkfree_pcp_prepare(struct page *page)* pinned" detection logic. */ static void free_pcppages_bulk (struct zone *zone,int count, -struct per_cpu_pages *pcp) +struct per_cpu_pages *pcp, +int migratetype) { -int migratetype =0 ; -int batch_free =0 ; +unsigned int pindex =0 ;
Should pindex be initialized to migratetype to match the list below?
include/linux/mmzone.h static bool bulkfree_pcp_prepare(struct page *page) · line 1094
Quoted 5 lines
include/linux/mmzone.h +2
-0+struct list_head *list = &pcp->lists[migratetype]; +unsigned int nr_freed =0 ;unsigned long nr_scanned;bool isolated_pageblocks;
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 18 lines · Vlastimil Babka
On 11/21/2016 04:55 PM, Mel Gorman wrote:
...
Quoted 5 lines
hackbench was also tested with both socket and pipes and both processes and threads and the results are interesting in terms of how variability is imapcted
1-socket machine -- pipes and processes
Quoted 8 lines
4.9.0-rc5 4.9.0-rc5 vanilla highmark-v1r12 Amean 1 12.9637 ( 0.00%) 12.9570 ( 0.05%) Amean 3 13.4770 ( 0.00%) 13.4447 ( 0.24%) Amean 5 18.5333 ( 0.00%) 19.0917 ( -3.01%) Amean 7 24.5690 ( 0.00%) 26.1010 ( -6.24%) Amean 12 39.7990 ( 0.00%) 40.6763 ( -2.20%) Amean 16 56.0520 ( 0.00%) 58.2530 ( -3.93%)
Quoted 2 lines
Here, higher values are better or worse?
Higher values are worse.
Quoted 8 lines
Quoted 8 lines
include/linux/mmzone.h +0
-0@@ -255,6 +255,24 @@ enum zone_watermarks { NR_WMARK };
Quoted 10 lines
include/linux/mmzone.h enum zone_watermarks { · line 264
Quoted 7 lines
include/linux/mmzone.h +7
-0+/* +* One per migratetype for order-0 pages and one per high-order up to +* and including PAGE_ALLOC_COSTLY_ORDER. This may allow unmovable +* allocations to contaminate reclaimable pageblocks if high-order +* pages are heavily used. +*/ +#define NR_PCP_LISTS (MIGRATE_PCPTYPES + PAGE_ALLOC_COSTLY_ORDER + 1)Should it be "- 1" instead of "+ 1"?
Yes.
Quoted 4 lines
Quoted 4 lines
include/linux/mmzone.h +4
-0+ +static inline unsigned int pindex_to_order (unsigned int pindex) +{ +return pindex <MIGRATE_PCPTYPES ?0 : pindex -MIGRATE_PCPTYPES +1 ;
Quoted 9 lines
include/linux/mmzone.h enum zone_watermarks { · line 273
Quoted 5 lines
include/linux/mmzone.h +5
-0+} + +static inline unsigned int order_to_pindex (int migratetype,unsigned int order) +{ +return (order ==0 ) ? migratetype :MIGRATE_PCPTYPES -1 + order;Here I think that "
MIGRATE_PCPTYPES+ order - 1" would be easier to understand as the array is for all migratetypes, but the order is shifted?
As in migratetypes * costly_order ? That would be excessively large.
Quoted 5 lines
Quoted 5 lines
include/linux/mmzone.h +0
-1@@ -1083,10 +1083,12 @@ static bool bulkfree_pcp_prepare(struct page *page)* pinned" detection logic. */ static void free_pcppages_bulk(struct zone *zone, int count, -struct per_cpu_pages *pcp)
Quoted 9 lines
include/linux/mmzone.h static bool bulkfree_pcp_prepare(struct page *page) · line 1089
Quoted 6 lines
include/linux/mmzone.h +3
-2+ struct per_cpu_pages *pcp, + int migratetype) { -int migratetype =0 ; -int batch_free =0 ; +unsigned int pindex =0 ;Should pindex be initialized to migratetype to match the list below?
Functionally it doesn't matter. It affects which list is tried first if the preferred list is empty. Arguably it would make more sense to init it to NR_PCP_LISTS - 1 so all order-0 lists are always drained before the high-order pages but there is not much justification for that.
I'll take your suggestion until there is data supporting that high-order caches should be preserved.
Thanks.
Signature · 8 lines
Mel Gorman SUSE Labs -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 14 lines · Mel Gorman
Quoted 4 lines
Quoted 4 lines
include/linux/mmzone.h +4
-0+ +static inline unsigned int pindex_to_order (unsigned int pindex) +{ +return pindex <MIGRATE_PCPTYPES ?0 : pindex -MIGRATE_PCPTYPES +1 ;Quoted 9 lines
include/linux/mmzone.h enum zone_watermarks { · line 273
Quoted 5 lines
include/linux/mmzone.h +5
-0+} + +static inline unsigned int order_to_pindex (int migratetype,unsigned int order) +{ +return (order ==0 ) ? migratetype :MIGRATE_PCPTYPES -1 + order;Here I think that "
MIGRATE_PCPTYPES+ order - 1" would be easier to understand as the array is for all migratetypes, but the order is shifted?
Quoted 1 line
As in migratetypes *
costly_order? That would be excessively large.
No, I just meant that instead of "MIGRATE_PCPTYPES - 1 + order" it could be "MIGRATE_PCPTYPES + order - 1" as we are subtracting from order, not migratetypes. Just made me confused a bit when seeing the code for the first time.
Quoted 15 lines
Quoted 5 lines
Quoted 5 lines
mm/page_alloc.c +0
-1@@ -1083,10 +1083,12 @@ static bool bulkfree_pcp_prepare(struct page *page)* pinned" detection logic. */ static void free_pcppages_bulk(struct zone *zone, int count, -struct per_cpu_pages *pcp)Quoted 9 lines
mm/page_alloc.c static bool bulkfree_pcp_prepare(struct page *page) · line 1089
Quoted 6 lines
mm/page_alloc.c +3
-2+ struct per_cpu_pages *pcp, + int migratetype) { -int migratetype =0 ; -int batch_free =0 ; +unsigned int pindex =0 ;Should pindex be initialized to migratetype to match the list below?
Quoted 4 lines
Functionally it doesn't matter. It affects which list is tried first if the preferred list is empty. Arguably it would make more sense to init it to
NR_PCP_LISTS- 1 so all order-0 lists are always drained before the high-order pages but there is not much justification for that.
OK
Quoted 5 lines
I'll take your suggestion until there is data supporting that high-order caches should be preserved.
Thanks.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 15 lines · Vlastimil Babka
Quoted 14 lines · Mel Gorman
Quoted 13 lines
include/linux/mmzone.h enum zone_watermarks { · line 273
Quoted 9 lines
include/linux/mmzone.h +9
-0+ +static inline unsigned int pindex_to_order (unsigned int pindex) +{ +return pindex <MIGRATE_PCPTYPES ?0 : pindex -MIGRATE_PCPTYPES +1 ; +} + +static inline unsigned int order_to_pindex (int migratetype,unsigned int order) +{ +return (order ==0 ) ? migratetype :MIGRATE_PCPTYPES -1 + order;Here I think that "
MIGRATE_PCPTYPES+ order - 1" would be easier to understand as the array is for all migratetypes, but the order is shifted?
Quoted 7 lines
Quoted 1 line
As in migratetypes *
costly_order? That would be excessively large.No, I just meant that instead of "
MIGRATE_PCPTYPES- 1 + order" it could be "MIGRATE_PCPTYPES+ order - 1" as we are subtracting from order, not migratetypes. Just made me confused a bit when seeing the code for the first time.
Oh ok. At the time I was thinking in terms of the starting offset for the high-order and this seemed more natural but I'm ok with it either way.
As an aside, the sizing of the array was still wrong but I corrected it yesterday shortly after sending the mail. I also realised that the free_pcppages_bulk was not interleaving properly and it should be fixed now. More tests are in progress.
Thanks.
Signature · 8 lines
Mel Gorman SUSE Labs -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"[email protected]"> [email protected] </a>