Skip to contentSkip to conversation

mm: Proactive compaction

PATCH In review Nitin Gupta 3 participants 4 messages Nov 15, 2019 – Dec 3, 2019

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 mm: Proactive compaction

For some applications we need to allocate almost all memory as hugepages. However, on a running system, higher order allocations can fail if the memory is fragmented. Linux kernel currently does on-demand compaction as we request more hugepages but this style of compaction incurs very high latency. Experiments with one-time full memory compaction (followed by hugepage allocations) shows that kernel is able to restore a highly fragmented memory state to a fairly compacted memory state within <1 sec for a 32G system. Such data suggests that a more proactive compaction can help us allocate a large fraction of memory as hugepages keeping allocation latencies low.

For a more proactive compaction, the approach taken here is to define per page-node tunable called ‘hpage_compaction_effort’ which dictates bounds for external fragmentation for HPAGE_PMD_ORDER pages which kcompactd should try to maintain.

The tunable is exposed through sysfs:
/sys/kernel/mm/compaction/node-n/hpage_compaction_effort

The value of this tunable is used to determine low and high thresholds for external fragmentation wrt HPAGE_PMD_ORDER order.

Note that previous version of this patch [1] was found to introduce too many tunables (per-order, extfrag_{low, high}) but this one reduces them to just (per-node, hpage_compaction_effort). Also, the new tunable is an opaque value instead of asking for specific bounds of “external fragmentation” which would have been difficult to estimate. The internal interpretation of this opaque value allows for future fine-tuning.

Currently, we use a simple translation from this tunable to [low, high] extfrag thresholds (low=100-hpage_compaction_effort, high=low+10%). To periodically check per-node extfrag status, we reuse per-node kcompactd threads which are woken up every few milliseconds to check the same. If any zone on its corresponding node has extfrag above the high threshold for the HPAGE_PMD_ORDER order, the thread starts compaction in background till all zones are below the low extfrag level for this order. By default. By default, the tunable is set to 0 (=> low=100%, high=100%).

This patch is largely based on ideas from Michal Hocko posted here:
https://lore.kernel.org/linux-mm/[email protected]/

* Performance data

System: x64_64, 32G RAM, 12-cores.

I made a small driver that allocates as many hugepages as possible and measures allocation latency:

The driver first tries to allocate hugepage using GFP_TRANSHUGE_LIGHT and if that fails, tries to allocate with GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL. The drives stops when both methods fail for a hugepage allocation.

Before starting the driver, the system was fragmented from a userspace program that allocates all memory and then for each 2M aligned section, frees 3/4 of base pages using munmap. The workload is mainly anonymous userspace pages which are easy to move around. I intentionally avoided unmovable pages in this test to see how much latency we incur just by hitting the slow path for most allocations.

(all latency values are in microseconds)

- With vanilla kernel 5.4.0-rc5:

percentile latency
---------- -------

         5       7
        10       7
        25       8
        30       8
        40       8
        50       8
        60       9
        75     215
        80     222
        90     323
        95     429

Total 2M hugepages allocated = 1829 (3.5G worth of hugepages out of 25G total free => 14% of free memory could be allocated as hugepages)

- Now with kernel 5.4.0-rc5 + this patch:
(hpage_compaction_effort = 60)

percentile latency
---------- -------

         5       3
        10       3
        25       4
        30       4
        40       4
        50       4
        60       5
        75       6
        80       9
        90     370
        95     652

Total 2M hugepages allocated = 11120 (21.7G worth of hugepages out of 25G total free => 86% of free memory could be allocated as hugepages)

Above workload produces a memory state which is easy to compact. However, if memory is filled with unmovable pages, pro-active compaction should essentially back off. To test this aspect, I ran a mix of this workload (thanks to Matthew Wilcox for suggesting these):

- dentry_thrash: it opens /tmp/missing.x for x in [1, 1000000] where first 10000 files actually exist.
- pagecache_thrash: it opens a 128G file (on a 32G system) and then reads at random offsets.

With this mix of workload, system quickly reaches 90-100% fragmentation wrt order-9. Trace of compaction events shows that we keep hitting compaction_deferred event, as expected.

After terminating dentry_thrash and dropping denty caches, the system could proceed with compaction according to set value of hpage_compaction_effort (60).

[1] https://patchwork.kernel.org/patch/11098289/

---
 include/linux/compaction.h |  10 ++
 mm/compaction.c            | 193 ++++++++++++++++++++++++++++++-------
 mm/vmstat.c                |  12 +++
 3 files changed, 178 insertions(+), 37 deletions(-)
include/linux/compaction.h +10 -0
index 4b898cdbdf05..7bf78b74b46a 100644
@@ -60,6 +60,15 @@ enum compact_result {
 
 struct alloc_context; /* in mm/internal.h */
 
+// "node-%d"
+#define COMPACTION_STATE_NAME_LEN 16
+// Per-node compaction state
+struct compaction_state {
+	int node_id;
+	unsigned int hpage_compaction_effort;
+	char name[COMPACTION_STATE_NAME_LEN];
+};
+
 /*
  * Number of free order-0 pages that should be available above given watermark
  * to make sure compaction has reasonable chance of not running out of free
@@ -90,6 +99,7 @@ extern int sysctl_compaction_handler(struct ctl_table *table, int write,
 extern int sysctl_extfrag_threshold;
 extern int sysctl_compact_unevictable_allowed;
 
+extern int extfrag_for_order(struct zone *zone, unsigned int order);
 extern int fragmentation_index(struct zone *zone, unsigned int order);
 extern enum compact_result try_to_compact_pages(gfp_t gfp_mask,
 		unsigned int order, unsigned int alloc_flags,
mm/compaction.c +156 -37

266 lines not on this page · raw message

mm/vmstat.c +12 -0
index a8222041bd44..0230a45c548a 100644
@@ -1074,6 +1074,18 @@ static int __fragmentation_index(unsigned int order, struct contig_page_info *in
 	return 1000 - div_u64( (1000+(div_u64(info->free_pages * 1000ULL, requested))), info->free_blocks_total);
 }
 
+int extfrag_for_order(struct zone *zone, unsigned int order)
+{
+	struct contig_page_info info;
+
+	fill_contig_page_info(zone, order, &info);
+	if (info.free_pages == 0)
+		return 0;
+
+	return (info.free_pages - (info.free_blocks_suitable << order)) * 100
+							/ info.free_pages;
+}
+
 /* Same as __fragmentation index but allocs contig_page_info on stack */
 int fragmentation_index(struct zone *zone, unsigned int order)
 {
Signature · 1 line
2.17.1
#1 lore raw
I love your patch! Yet something to improve:

Hi Nitin,

I love your patch! Yet something to improve:

[auto build test ERROR on mmotm/master]
[also build test ERROR on v5.4-rc7 next-20191115]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system. BTW, we also suggest to use '--base' option to specify the base tree in git format-patch, please see https://stackoverflow.com/a/37406982]

url:    https://github.com/0day-ci/linux/commits/Nitin-Gupta/mm-Proactive-compaction/20191116-062531
base:   git://git.cmpxchg.org/linux-mmotm.git master
config: parisc-c3000_defconfig (attached as .config)
compiler: hppa-linux-gcc (GCC) 7.4.0

reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
GCC_VERSION=7.4.0 make.cross ARCH=parisc

If you fix the issue, kindly add following tag

All error/warnings (new ones prefixed by >>):

mm/compaction.c: In function 'extfrag_hpage_wmark':

>> mm/compaction.c:1860:33: error: 'HUGETLB_PAGE_ORDER' undeclared (first use in this function); did you mean 'HPAGE_PMD_ORDER'?
     return extfrag_for_order(zone, HUGETLB_PAGE_ORDER) > wmark;
                                    ^~~~~~~~~~~~~~~~~~
                                    HPAGE_PMD_ORDER
   mm/compaction.c:1860:33: note: each undeclared identifier is reported only once for each function it appears in
   mm/compaction.c: In function 'node_hpage_should_compact':
   mm/compaction.c:1869:30: error: 'HUGETLB_PAGE_ORDER' undeclared (first use in this function); did you mean 'HPAGE_PMD_ORDER'?
       compaction_suitable(zone, HUGETLB_PAGE_ORDER,
                                 ^~~~~~~~~~~~~~~~~~
                                 HPAGE_PMD_ORDER
   mm/compaction.c: In function 'extfrag_hpage_wmark':
>> mm/compaction.c:1861:1: warning: control reaches end of non-void function [-Wreturn-type]
    }
    ^

vim +1860 mm/compaction.c

1851
1852 static unsigned int extfrag_hpage_wmark(struct zone *zone, bool low)
1853 {
1854 int node_id, wmark, wmark_low;
1855
1856 node_id = zone->zone_pgdat->node_id;
1857 wmark_low = 100 - compaction_states[node_id].hpage_compaction_effort;
1858 wmark = low ? wmark_low : min(wmark_low + 10, 100);
1859

> 1860		return extfrag_for_order(zone, HUGETLB_PAGE_ORDER) > wmark;
> 1861	}

1862

---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org Intel Corporation

#2 lore raw
In reply to Nitin Gupta
Quoted 16 lines · Nitin Gupta

For some applications we need to allocate almost all memory as hugepages. However, on a running system, higher order allocations can fail if the memory is fragmented. Linux kernel currently does on-demand compaction as we request more hugepages but this style of compaction incurs very high latency. Experiments with one-time full memory compaction (followed by hugepage allocations) shows that kernel is able to restore a highly fragmented memory state to a fairly compacted memory state within <1 sec for a 32G system. Such data suggests that a more proactive compaction can help us allocate a large fraction of memory as hugepages keeping allocation latencies low.

For a more proactive compaction, the approach taken here is to define per page-node tunable called ‘hpage_compaction_effort’ which dictates bounds for external fragmentation for HPAGE_PMD_ORDER pages which kcompactd should try to maintain.

Quoted 5 lines

The tunable is exposed through sysfs:
/sys/kernel/mm/compaction/node-n/hpage_compaction_effort

The value of this tunable is used to determine low and high thresholds for external fragmentation wrt HPAGE_PMD_ORDER order.

Could we instead start with a non-tunable value that would be linked to
to e.g. the number of THP allocations between kcompactd cycles?
Anything we expose will inevitably get set to stone, I'm afraid, so I would introduce it only as a last resort.

Quoted 77 lines

Note that previous version of this patch [1] was found to introduce too many tunables (per-order, extfrag_{low, high}) but this one reduces them to just (per-node, hpage_compaction_effort). Also, the new tunable is an opaque value instead of asking for specific bounds of “external fragmentation” which would have been difficult to estimate. The internal interpretation of this opaque value allows for future fine-tuning.

Currently, we use a simple translation from this tunable to [low, high] extfrag thresholds (low=100-hpage_compaction_effort, high=low+10%). To periodically check per-node extfrag status, we reuse per-node kcompactd threads which are woken up every few milliseconds to check the same. If any zone on its corresponding node has extfrag above the high threshold for the HPAGE_PMD_ORDER order, the thread starts compaction in background till all zones are below the low extfrag level for this order. By default. By default, the tunable is set to 0 (=> low=100%, high=100%).

This patch is largely based on ideas from Michal Hocko posted here:
https://lore.kernel.org/linux-mm/[email protected]/

* Performance data

System: x64_64, 32G RAM, 12-cores.

I made a small driver that allocates as many hugepages as possible and measures allocation latency:

The driver first tries to allocate hugepage using GFP_TRANSHUGE_LIGHT and if that fails, tries to allocate with GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL. The drives stops when both methods fail for a hugepage allocation.

Before starting the driver, the system was fragmented from a userspace program that allocates all memory and then for each 2M aligned section, frees 3/4 of base pages using munmap. The workload is mainly anonymous userspace pages which are easy to move around. I intentionally avoided unmovable pages in this test to see how much latency we incur just by hitting the slow path for most allocations.

(all latency values are in microseconds)

- With vanilla kernel 5.4.0-rc5:

percentile latency
---------- -------

         5       7
        10       7
        25       8
        30       8
        40       8
        50       8
        60       9
        75     215
        80     222
        90     323
        95     429

Total 2M hugepages allocated = 1829 (3.5G worth of hugepages out of 25G total free => 14% of free memory could be allocated as hugepages)

- Now with kernel 5.4.0-rc5 + this patch:
(hpage_compaction_effort = 60)

percentile latency
---------- -------

         5       3
        10       3
        25       4
        30       4
        40       4
        50       4
        60       5
        75       6
        80       9
        90     370
        95     652
Quoted 2 lines

Total 2M hugepages allocated = 11120 (21.7G worth of hugepages out of 25G total free => 86% of free memory could be allocated as hugepages)

I wonder about the 14->86% improvement. As you say, this kind of fragmentation is easy to compact. Why wouldn't GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL attempts succeed?

Thanks,
Vlastimil

Quoted 21 lines

Above workload produces a memory state which is easy to compact. However, if memory is filled with unmovable pages, pro-active compaction should essentially back off. To test this aspect, I ran a mix of this workload (thanks to Matthew Wilcox for suggesting these):

- dentry_thrash: it opens /tmp/missing.x for x in [1, 1000000] where first 10000 files actually exist.
- pagecache_thrash: it opens a 128G file (on a 32G system) and then reads at random offsets.

With this mix of workload, system quickly reaches 90-100% fragmentation wrt order-9. Trace of compaction events shows that we keep hitting compaction_deferred event, as expected.

After terminating dentry_thrash and dropping denty caches, the system could proceed with compaction according to set value of hpage_compaction_effort (60).

[1] https://patchwork.kernel.org/patch/11098289/

#3 lore raw
Quoted 32 lines

-----Original Message-----
From: [email protected] <[email protected]> On Behalf Of Vlastimil Babka
Sent: Friday, November 29, 2019 5:55 AM
To: Nitin Gupta <[email protected]>; Mel Gorman <[email protected]>; Michal Hocko <[email protected]>
Cc: Andrew Morton <[email protected]>; Yu Zhao <[email protected]>; Mike Kravetz <[email protected]>; Matthew Wilcox <[email protected]>; [email protected]; linux- [email protected]
Subject: Re: [PATCH] mm: Proactive compaction

Quoted 19 lines · Nitin Gupta

For some applications we need to allocate almost all memory as hugepages. However, on a running system, higher order allocations can fail if the memory is fragmented. Linux kernel currently does on-demand compaction as we request more hugepages but this style of compaction incurs very high latency. Experiments with one-time full memory compaction (followed by hugepage allocations) shows that kernel is able to restore a highly fragmented memory state to a fairly compacted memory state within <1 sec for a 32G system. Such data suggests that a more proactive compaction can help us allocate a large fraction of memory as hugepages keeping allocation latencies low.

For a more proactive compaction, the approach taken here is to define per page-node tunable called ‘hpage_compaction_effort’ which dictates bounds for external fragmentation for HPAGE_PMD_ORDER pages which kcompactd should try to maintain.

The tunable is exposed through sysfs:
/sys/kernel/mm/compaction/node-n/hpage_compaction_effort

Quoted 8 lines
Quoted 2 lines

The value of this tunable is used to determine low and high thresholds for external fragmentation wrt HPAGE_PMD_ORDER order.

Could we instead start with a non-tunable value that would be linked to to e.g. the number of THP allocations between kcompactd cycles? Anything we expose will inevitably get set to stone, I'm afraid, so I would introduce it only as a last resort.

There have been attempts in the past to do proactive compaction without adding any new tunables. For instance, see this patch from Khalid (CC'ed):

https://lkml.org/lkml/2019/8/12/1302

This patch collects allocation and fragmentation data points to predict memory exhaustion or fragmentation and triggers reclaim or compaction proactively. The main concern in the discussion for this patch was that such data collection and predictive analysis can be done from userspace together with wmark adjustment (already exposed), so no kernel changes are potentially necessary.

However, in the same discussion, Michal pointed out a lack of similar interface (like wmarks for kswapd) missing to guide kcompactd:

https://lkml.org/lkml/2019/8/13/730

My patch is addressing the need for that missing userspace tunable. A userspace daemon can measure fragmentation trends and adjust this tunable to let kernel know amount of effort to put into compaction to avoid hitting direct compact path.

Quoted 80 lines
Quoted 6 lines

Note that previous version of this patch [1] was found to introduce too many tunables (per-order, extfrag_{low, high}) but this one reduces them to just (per-node, hpage_compaction_effort). Also, the new tunable is an opaque value instead of asking for specific bounds of “external fragmentation” which would have been difficult to estimate. The internal interpretation of this opaque value allows for future

fine-tuning.

Quoted 11 lines

Currently, we use a simple translation from this tunable to [low, high] extfrag thresholds (low=100-hpage_compaction_effort, high=low+10%). To periodically check per-node extfrag status, we reuse per-node kcompactd threads which are woken up every few milliseconds to check the same. If any zone on its corresponding node has extfrag above the high threshold for the HPAGE_PMD_ORDER order, the thread starts compaction in background till all zones are below the low extfrag level for this order. By default. By default, the tunable is set to 0 (=> low=100%, high=100%).

Quoted 2 lines

This patch is largely based on ideas from Michal Hocko posted here:
https://lore.kernel.org/linux-

mm/[email protected]

Quoted 59 lines

/

* Performance data

System: x64_64, 32G RAM, 12-cores.

I made a small driver that allocates as many hugepages as possible and measures allocation latency:

The driver first tries to allocate hugepage using GFP_TRANSHUGE_LIGHT and if that fails, tries to allocate with GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL. The drives stops when both methods fail for a hugepage allocation.

Before starting the driver, the system was fragmented from a userspace program that allocates all memory and then for each 2M aligned section, frees 3/4 of base pages using munmap. The workload is mainly anonymous userspace pages which are easy to move around. I intentionally avoided unmovable pages in this test to see how much latency we incur just by hitting the slow path for most allocations.

(all latency values are in microseconds)

- With vanilla kernel 5.4.0-rc5:

percentile latency
---------- -------

         5       7
        10       7
        25       8
        30       8
        40       8
        50       8
        60       9
        75     215
        80     222
        90     323
        95     429

Total 2M hugepages allocated = 1829 (3.5G worth of hugepages out of 25G total free => 14% of free memory could be allocated as hugepages)

- Now with kernel 5.4.0-rc5 + this patch:
(hpage_compaction_effort = 60)

percentile latency
---------- -------

         5       3
        10       3
        25       4
        30       4
        40       4
        50       4
        60       5
        75       6
        80       9
        90     370
        95     652
Quoted 7 lines
Quoted 2 lines

Total 2M hugepages allocated = 11120 (21.7G worth of hugepages out of 25G total free => 86% of free memory could be allocated as hugepages)

I wonder about the 14->86% improvement. As you say, this kind of fragmentation is easy to compact. Why wouldn't GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL attempts succeed?

I'm not too sure at this point. With kernel 5.3.0 I could allocate 80-90% of memory as hugepages under similar conditions though with very high latencies (as I reported here: https://patchwork.kernel.org/patch/11098289/)

With kernel 5.4.0-x I observed this significant drop. Perhaps GFP_TRANSHUGE flag was changed between these versions. I will post future numbers with base flags to avoid such surprises in future.

Thanks,
Nitin

Quoted 21 lines
Quoted 21 lines

Above workload produces a memory state which is easy to compact. However, if memory is filled with unmovable pages, pro-active compaction should essentially back off. To test this aspect, I ran a mix of this workload (thanks to Matthew Wilcox for suggesting these):

- dentry_thrash: it opens /tmp/missing.x for x in [1, 1000000] where first 10000 files actually exist.
- pagecache_thrash: it opens a 128G file (on a 32G system) and then reads at random offsets.

With this mix of workload, system quickly reaches 90-100% fragmentation wrt order-9. Trace of compaction events shows that we keep hitting compaction_deferred event, as expected.

After terminating dentry_thrash and dropping denty caches, the system could proceed with compaction according to set value of hpage_compaction_effort (60).

[1] https://patchwork.kernel.org/patch/11098289/