Re: [RFC] mm: Proactive compaction
On 9/24/19 7:39 AM, Vlastimil Babka wrote: > On 9/20/19 1:37 AM, Nitin Gupta wrote: >> On Tue, 2019-08-20 at 10:46 +0200, Vlastimil Babka wrote: >>> >>> That's a lot of control knobs - how is an admin supposed to tune them to >>> their >>> needs? >> >> >> Yes, it's difficult for an admin to get so many tunable right unless >> targeting a very specific workload. >> >> How about a simpler solution where we exposed just one tunable per-node: >>/sys/.../node-x/compaction_effort >> which accepts [0, 100] >> >> This parallels /proc/sys/vm/swappiness but for compaction. With this >> single number, we can estimate per-order [low, high] watermarks for external >> fragmentation like this: >> - For now, map this range to [low, medium, high] which correponds to >> specific >> low, high thresholds for extfrag. >> - Apply more relaxed thresholds for higher-order than for lower orders. >> >> With this single tunable we remove the burden of setting per-order explicit >> [low, high] thresholds and it should be easier to experiment with. > > What about instead autotuning by the numbers of allocations hitting > direct compaction recently? IIRC there were attempts in the past (myself > included) and recently Khalid's that was quite elaborated. > I do think the right way forward with this longstanding problem is to take the burden of managing free memory away from end user and let the kernel autotune itself to the demands of workload. We can start with a simpler algorithm in the kernel that adapts to workload and refine it as we move forward. As long as initial implementation performs at least as well as current free page management, we have a workable path for improvements. I am moving the implementation I put together in kernel to a userspace daemon just to test it out on larger variety of workloads. It is more limited in userspace with limited access to statistics the algorithm needs to perform trend analysis so I would rather be doing this in the kernel. -- Khalid
Re: [RFC] mm: Proactive compaction
On 9/20/19 1:37 AM, Nitin Gupta wrote: > On Tue, 2019-08-20 at 10:46 +0200, Vlastimil Babka wrote: >> >> That's a lot of control knobs - how is an admin supposed to tune them to >> their >> needs? > > > Yes, it's difficult for an admin to get so many tunable right unless > targeting a very specific workload. > > How about a simpler solution where we exposed just one tunable per-node: >/sys/.../node-x/compaction_effort > which accepts [0, 100] > > This parallels /proc/sys/vm/swappiness but for compaction. With this > single number, we can estimate per-order [low, high] watermarks for external > fragmentation like this: > - For now, map this range to [low, medium, high] which correponds to specific > low, high thresholds for extfrag. > - Apply more relaxed thresholds for higher-order than for lower orders. > > With this single tunable we remove the burden of setting per-order explicit > [low, high] thresholds and it should be easier to experiment with. What about instead autotuning by the numbers of allocations hitting direct compaction recently? IIRC there were attempts in the past (myself included) and recently Khalid's that was quite elaborated. > -Nitin > > >
Re: [RFC] mm: Proactive compaction
On Tue, 2019-08-20 at 10:46 +0200, Vlastimil Babka wrote:
> > This patch is largely based on ideas from Michal Hocko posted here:
> > https://lore.kernel.org/linux-mm/20161230131412.gi13...@dhcp22.suse.cz/
> >
> > Testing done (on x86):
> > - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> > respectively.
> > - Use a test program to fragment memory: the program allocates all
> > memory
> > and then for each 2M aligned section, frees 3/4 of base pages using
> > munmap.
> > - kcompactd0 detects fragmentation for order-9 > extfrag_high and starts
> > compaction till extfrag < extfrag_low for order-9.
> >
> > The patch has plenty of rough edges but posting it early to see if I'm
> > going in the right direction and to get some early feedback.
>
> That's a lot of control knobs - how is an admin supposed to tune them to
> their
> needs?
Yes, it's difficult for an admin to get so many tunable right unless
targeting a very specific workload.
How about a simpler solution where we exposed just one tunable per-node:
/sys/.../node-x/compaction_effort
which accepts [0, 100]
This parallels /proc/sys/vm/swappiness but for compaction. With this
single number, we can estimate per-order [low, high] watermarks for external
fragmentation like this:
- For now, map this range to [low, medium, high] which correponds to specific
low, high thresholds for extfrag.
- Apply more relaxed thresholds for higher-order than for lower orders.
With this single tunable we remove the burden of setting per-order explicit
[low, high] thresholds and it should be easier to experiment with.
-Nitin
Re: [RFC] mm: Proactive compaction
On Thu, 2019-08-22 at 09:51 +0100, Mel Gorman wrote: > As unappealing as it sounds, I think it is better to try improve the > allocation latency itself instead of trying to hide the cost in a kernel > thread. It's far harder to implement as compaction is not easy but it > would be more obvious what the savings are by looking at a histogram of > allocation latencies -- there are other metrics that could be considered > but that's the obvious one. > Do you mean reducing allocation latency especially when it hits direct compaction path? Do you have any ideas in mind for this? I'm open to working on them and report back latency nummbers, while I think more on less tunable-heavy background (pro-active) compaction approaches. -Nitin
Re: [RFC] mm: Proactive compaction
On Tue, 17 Sep 2019, John Hubbard wrote: > > We've had good success with periodically compacting memory on a regular > > cadence on systems with hugepages enabled. The cadence itself is defined > > by the admin but it causes khugepaged[*] to periodically wakeup and invoke > > compaction in an attempt to keep zones as defragmented as possible > > That's an important data point, thanks for reporting it. > > And given that we have at least one data point validating it, I think we > should feel fairly comfortable with this approach. Because the sys admin > probably knows when are the best times to steal cpu cycles and recover > some huge pages. Unlike the kernel, the sys admin can actually see the > future sometimes, because he/she may know what is going to be run. > > It's still sounding like we can expect excellent results from simply > defragmenting from user space, via a chron job and/or before running > important tests, rather than trying to have the kernel guess whether > it's a performance win to defragment at some particular time. > > Are you using existing interfaces, or did you need to add something? How > exactly are you triggering compaction? > It's possible to do this through a cron job but there are a fre reasons that we preferred to do it through khugepaged: - we use a lighter variation of compaction, MIGRATE_SYNC_LIGHT, than what the per-node trigger provides since compact_node() forces MIGRATE_SYNC and can stall for minutes and become disruptive under some circumstances, - we do not ignore the pageblock skip hint which compact_node() hardcodes to ignore, and - we didn't want to do this in process context so that the cpu time is not taxed to any user cgroup since it's on behalf of the system as a whole. It seems much better to do this on a per-node basis rather than through the sysctl to do it for the whole system to partition the work. Extending the per-node interface to do MIGRATE_SYNC_LIGHT and not ignore pageblock skip is possible but the work done would still be done in process context so if done from userspace this would need to be attached to a cgroup that does not tax that cgroup for usage done on behalf of the entire system. Again, we're using khugepaged and allowing the period to be defined through /sys/kernel/mm/transparent_hugepage/khugepaged but that is because we only want to do this on systems where we want to dynamically allocate hugepages on a regular basis.
Re: [RFC] mm: Proactive compaction
On 9/16/19 1:16 PM, David Rientjes wrote: > On Fri, 16 Aug 2019, Nitin Gupta wrote: ... > > We've had good success with periodically compacting memory on a regular > cadence on systems with hugepages enabled. The cadence itself is defined > by the admin but it causes khugepaged[*] to periodically wakeup and invoke > compaction in an attempt to keep zones as defragmented as possible That's an important data point, thanks for reporting it. And given that we have at least one data point validating it, I think we should feel fairly comfortable with this approach. Because the sys admin probably knows when are the best times to steal cpu cycles and recover some huge pages. Unlike the kernel, the sys admin can actually see the future sometimes, because he/she may know what is going to be run. It's still sounding like we can expect excellent results from simply defragmenting from user space, via a chron job and/or before running important tests, rather than trying to have the kernel guess whether it's a performance win to defragment at some particular time. Are you using existing interfaces, or did you need to add something? How exactly are you triggering compaction? thanks, -- John Hubbard NVIDIA
Re: [RFC] mm: Proactive compaction
On Mon, 2019-09-16 at 13:16 -0700, David Rientjes wrote:
> On Fri, 16 Aug 2019, Nitin Gupta wrote:
>
> > 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-order external fragmentation thresholds and let kcompactd
> > threads act on these thresholds.
> >
> > The low and high thresholds are defined per page-order and exposed
> > through sysfs:
> >
> > /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
> >
> > Per-node kcompactd thread is woken up every few seconds to check if
> > any zone on its node has extfrag above the extfrag_high threshold for
> > any order, in which case the thread starts compaction in the backgrond
> > till all zones are below extfrag_low level for all orders. By default
> > both these thresolds are set to 100 for all orders which essentially
> > disables kcompactd.
> >
> > To avoid wasting CPU cycles when compaction cannot help, such as when
> > memory is full, we check both, extfrag > extfrag_high and
> > compaction_suitable(zone). This allows kcomapctd thread to stays inactive
> > even if extfrag thresholds are not met.
> >
> > This patch is largely based on ideas from Michal Hocko posted here:
> > https://lore.kernel.org/linux-mm/20161230131412.gi13...@dhcp22.suse.cz/
> >
> > Testing done (on x86):
> > - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> > respectively.
> > - Use a test program to fragment memory: the program allocates all memory
> > and then for each 2M aligned section, frees 3/4 of base pages using
> > munmap.
> > - kcompactd0 detects fragmentation for order-9 > extfrag_high and starts
> > compaction till extfrag < extfrag_low for order-9.
> >
> > The patch has plenty of rough edges but posting it early to see if I'm
> > going in the right direction and to get some early feedback.
> >
>
> Is there an update to this proposal or non-RFC patch that has been posted
> for proactive compaction?
>
> We've had good success with periodically compacting memory on a regular
> cadence on systems with hugepages enabled. The cadence itself is defined
> by the admin but it causes khugepaged[*] to periodically wakeup and invoke
> compaction in an attempt to keep zones as defragmented as possible
> (perhaps more "proactive" than what is proposed here in an attempt to keep
> all memory as unfragmented as possible regardless of extfrag thresholds).
> It also avoids corner-cases where kcompactd could become more expensive
> than what is anticipated because it is unsuccessful at compacting memory
> yet the extfrag threshold is still exceeded.
>
> [*] Khugepaged instead of kcompactd only because this is only enabled
> for systems where transparent hugepages are enabled, probably better
> off in kcompactd to avoid duplicating work between two kthreads if
> there is already a need for background compaction.
>
Discussion on this RFC patch revolved around the issue of exposing too
many tunables (per-node, per-order, [low-high] extfrag thresholds). It
was sort-of concluded that no admin will get these tunables right for
a variety of workloads.
To eliminate the need for tunables, I proposed another patch:
https://patchwork.kernel.org/patch/11140067/
which does not add any tunables but extends and exports an existing
function (compact_zone_order). In summary, this new patch adds a
callback function which allows any driver to implement ad-hoc
compaction policies. There is also a sample driver which makes use
of this interface to keep hugepage external fragmentation within
specified range (exposed through debugfs):
https://gitlab.com/nigupta/linux/snippets/1894161
-Nitin
Re: [RFC] mm: Proactive compaction
On Fri, 16 Aug 2019, Nitin Gupta wrote:
> 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-order external fragmentation thresholds and let kcompactd
> threads act on these thresholds.
>
> The low and high thresholds are defined per page-order and exposed
> through sysfs:
>
> /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
>
> Per-node kcompactd thread is woken up every few seconds to check if
> any zone on its node has extfrag above the extfrag_high threshold for
> any order, in which case the thread starts compaction in the backgrond
> till all zones are below extfrag_low level for all orders. By default
> both these thresolds are set to 100 for all orders which essentially
> disables kcompactd.
>
> To avoid wasting CPU cycles when compaction cannot help, such as when
> memory is full, we check both, extfrag > extfrag_high and
> compaction_suitable(zone). This allows kcomapctd thread to stays inactive
> even if extfrag thresholds are not met.
>
> This patch is largely based on ideas from Michal Hocko posted here:
> https://lore.kernel.org/linux-mm/20161230131412.gi13...@dhcp22.suse.cz/
>
> Testing done (on x86):
> - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> respectively.
> - Use a test program to fragment memory: the program allocates all memory
> and then for each 2M aligned section, frees 3/4 of base pages using
> munmap.
> - kcompactd0 detects fragmentation for order-9 > extfrag_high and starts
> compaction till extfrag < extfrag_low for order-9.
>
> The patch has plenty of rough edges but posting it early to see if I'm
> going in the right direction and to get some early feedback.
>
Is there an update to this proposal or non-RFC patch that has been posted
for proactive compaction?
We've had good success with periodically compacting memory on a regular
cadence on systems with hugepages enabled. The cadence itself is defined
by the admin but it causes khugepaged[*] to periodically wakeup and invoke
compaction in an attempt to keep zones as defragmented as possible
(perhaps more "proactive" than what is proposed here in an attempt to keep
all memory as unfragmented as possible regardless of extfrag thresholds).
It also avoids corner-cases where kcompactd could become more expensive
than what is anticipated because it is unsuccessful at compacting memory
yet the extfrag threshold is still exceeded.
[*] Khugepaged instead of kcompactd only because this is only enabled
for systems where transparent hugepages are enabled, probably better
off in kcompactd to avoid duplicating work between two kthreads if
there is already a need for background compaction.
Re: [RFC] mm: Proactive compaction
On Mon, 2019-08-26 at 12:47 +0100, Mel Gorman wrote:
> On Thu, Aug 22, 2019 at 09:57:22PM +, Nitin Gupta wrote:
> > > Note that proactive compaction may reduce allocation latency but
> > > it is not
> > > free either. Even though the scanning and migration may happen in
> > > a kernel
> > > thread, tasks can incur faults while waiting for compaction to
> > > complete if the
> > > task accesses data being migrated. This means that costs are
> > > incurred by
> > > applications on a system that may never care about high-order
> > > allocation
> > > latency -- particularly if the allocations typically happen at
> > > application
> > > initialisation time. I recognise that kcompactd makes a bit of
> > > effort to
> > > compact memory out-of-band but it also is typically triggered in
> > > response to
> > > reclaim that was triggered by a high-order allocation request.
> > > i.e. the work
> > > done by the thread is triggered by an allocation request that hit
> > > the slow
> > > paths and not a preemptive measure.
> > >
> >
> > Hitting the slow path for every higher-order allocation is a
> > signification
> > performance/latency issue for applications that requires a large
> > number of
> > these allocations to succeed in bursts. To get some concrete
> > numbers, I
> > made a small driver that allocates as many hugepages as possible
> > and
> > measures allocation latency:
> >
>
> Every higher-order allocation does not necessarily hit the slow path
> nor
> does it incur equal latency.
I did not mean *every* hugepage allocation in a literal sense.
I meant to say: higher order allocation *tend* to hit slow path
with a high probability under reasonably fragmented memory state
and when they do, they incur high latency.
>
> > The driver first tries to allocate hugepage using
> > GFP_TRANSHUGE_LIGHT
> > (referred to as "Light" in the table below) and if that fails,
> > tries to
> > allocate with `GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL` (referred to as
> > "Fallback" in table below). We stop the allocation loop if both
> > methods
> > fail.
> >
> > Table-1: hugepage allocation latencies on vanilla 5.3.0-rc5. All
> > latencies
> > are in microsec.
> >
> > > GFP/Stat |Any | Light | Fallback |
> > > : | -: | --: | -: |
> > >count | 9908 | 788 | 9120 |
> > > min |0.0 | 0.0 | 1726.0 |
> > > max | 135387.0 | 142.0 | 135387.0 |
> > > mean |5494.66 |1.83 |5969.26 |
> > > stddev | 21624.04 |7.58 | 22476.06 |
>
> Given that it is expected that there would be significant tail
> latencies,
> it would be better to analyse this in terms of percentiles. A very
> small
> number of high latency allocations would skew the mean significantly
> which is hinted by the stddev.
>
Here is the same data in terms of percentiles:
- with vanilla kernel 5.3.0-rc5:
percentile latency
–– –––
5 1
10179
0
251829
301838
401854
5018
71
601890
751924
801945
902
206
952302
- Now with kernel 5.3.0-rc5 + this patch:
percentile latency
–– –––
5 3
10 4
25
4
30 4
40 4
50 4
60
4
75 5
80 5
90 9
951
154
> > As you can see, the mean and stddev of allocation is extremely high
> > with
> > the current approach of on-demand compaction.
> >
> > The system was fragmented from a userspace program as I described
> > in this
> > patch description. The workload is mainly anonymous userspace pages
> > which
> > as easy to move around. I intentionally avoided unmovable pages in
> > this
> > test to see how much latency do we incur just by hitting the slow
> > path for
> > a majority of allocations.
> >
>
> Even though, the penalty for proactive compaction is that
> applications
> that may have no interest in higher-order pages may still stall while
> their data is migrated if the data is hot. This is why I think the
> focus
> should be on reducing the latency of compaction -- it benefits
> applications that require higher-order latencies without increasing
> the
> overhead for unrelated applications.
>
Sure, reducing compaction latency would help but there should still
be an option to proactively compact to hide latencies further.
> > > > For a more proactive compaction, the approach taken here is to
> > > > define
> > > > per page-order external fragmentation thresholds and let
> > > > kcompactd
> > > > threads act on these thresholds.
> > > >
> > > > The low and high thresholds are defined per page-order and
> > > > exposed
> > > > through sysfs:
> > > >
> > > > /sys/kernel/mm/compaction/order-
> > > > [1..MAX_ORDER]/extfrag_{low,high}
> > > >
> > >
> > > These will be difficult for an admin to tune that is not
Re: [RFC] mm: Proactive compaction
On Thu, Aug 22, 2019 at 09:57:22PM +, Nitin Gupta wrote:
> > Note that proactive compaction may reduce allocation latency but it is not
> > free either. Even though the scanning and migration may happen in a kernel
> > thread, tasks can incur faults while waiting for compaction to complete if
> > the
> > task accesses data being migrated. This means that costs are incurred by
> > applications on a system that may never care about high-order allocation
> > latency -- particularly if the allocations typically happen at application
> > initialisation time. I recognise that kcompactd makes a bit of effort to
> > compact memory out-of-band but it also is typically triggered in response to
> > reclaim that was triggered by a high-order allocation request. i.e. the work
> > done by the thread is triggered by an allocation request that hit the slow
> > paths and not a preemptive measure.
> >
>
> Hitting the slow path for every higher-order allocation is a signification
> performance/latency issue for applications that requires a large number of
> these allocations to succeed in bursts. To get some concrete numbers, I
> made a small driver that allocates as many hugepages as possible and
> measures allocation latency:
>
Every higher-order allocation does not necessarily hit the slow path nor
does it incur equal latency.
> The driver first tries to allocate hugepage using GFP_TRANSHUGE_LIGHT
> (referred to as "Light" in the table below) and if that fails, tries to
> allocate with `GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL` (referred to as
> "Fallback" in table below). We stop the allocation loop if both methods
> fail.
>
> Table-1: hugepage allocation latencies on vanilla 5.3.0-rc5. All latencies
> are in microsec.
>
> | GFP/Stat |Any | Light | Fallback |
> |: | -: | --: | -: |
> |count | 9908 | 788 | 9120 |
> | min |0.0 | 0.0 | 1726.0 |
> | max | 135387.0 | 142.0 | 135387.0 |
> | mean |5494.66 |1.83 |5969.26 |
> | stddev | 21624.04 |7.58 | 22476.06 |
>
Given that it is expected that there would be significant tail latencies,
it would be better to analyse this in terms of percentiles. A very small
number of high latency allocations would skew the mean significantly
which is hinted by the stddev.
> As you can see, the mean and stddev of allocation is extremely high with
> the current approach of on-demand compaction.
>
> The system was fragmented from a userspace program as I described in this
> patch description. The workload is mainly anonymous userspace pages which
> as easy to move around. I intentionally avoided unmovable pages in this
> test to see how much latency do we incur just by hitting the slow path for
> a majority of allocations.
>
Even though, the penalty for proactive compaction is that applications
that may have no interest in higher-order pages may still stall while
their data is migrated if the data is hot. This is why I think the focus
should be on reducing the latency of compaction -- it benefits
applications that require higher-order latencies without increasing the
overhead for unrelated applications.
>
> > > For a more proactive compaction, the approach taken here is to define
> > > per page-order external fragmentation thresholds and let kcompactd
> > > threads act on these thresholds.
> > >
> > > The low and high thresholds are defined per page-order and exposed
> > > through sysfs:
> > >
> > > /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
> > >
> >
> > These will be difficult for an admin to tune that is not extremely familiar
> > with
> > how external fragmentation is defined. If an admin asked "how much will
> > stalls be reduced by setting this to a different value?", the answer will
> > always
> > be "I don't know, maybe some, maybe not".
> >
>
> Yes, this is my main worry. These values can be set to emperically
> determined values on highly specialized systems like database appliances.
> However, on a generic system, there is no real reasonable value.
>
Yep, which means the tunable will be vulnerable to cargo-cult tuning
recommendations. Or worse, the tuning recommendation will be a flat
"disable THP".
> Still, at the very least, I would like an interface that allows compacting
> system to a reasonable state. Something like:
>
> compact_extfrag(node, zone, order, high, low)
>
> which start compaction if extfrag > high, and goes on till extfrag < low.
>
> It's possible that there are too many unmovable pages mixed around for
> compaction to succeed, still it's a reasonable interface to expose rather
> than forced on-demand style of compaction (please see data below).
>
> How (and if) to expose it to userspace (sysfs etc.) can be a separate
> discussion.
>
That would be functionally similar to vm.compact_memory although it
would either need an extension or a separate tunable. With sysfs, there
could be a per-node
Re: [RFC] mm: Proactive compaction
On 8/20/19 2:46 AM, Vlastimil Babka wrote: > +CC Khalid Aziz who proposed a different approach: > https://lore.kernel.org/linux-mm/20190813014012.30232-1-khalid.a...@oracle.com/T/#u > > On 8/16/19 11:43 PM, Nitin Gupta wrote: >> The patch has plenty of rough edges but posting it early to see if I'm >> going in the right direction and to get some early feedback. > > That's a lot of control knobs - how is an admin supposed to tune them to their > needs? > At a high level, this idea makes sense and is similar to the idea of watermarks for free pages. My concern is the same. We now have more knobs to tune and that increases complexity for sys admins as well as the chances of a misconfigured system. -- Khalid
Re: [RFC] mm: Proactive compaction
> -Original Message-
> From: owner-linux...@kvack.org On Behalf
> Of Mel Gorman
> Sent: Thursday, August 22, 2019 1:52 AM
> To: Nitin Gupta
> Cc: a...@linux-foundation.org; vba...@suse.cz; mho...@suse.com;
> dan.j.willi...@intel.com; Yu Zhao ; Matthew Wilcox
> ; Qian Cai ; Andrey Ryabinin
> ; Roman Gushchin ; Greg Kroah-
> Hartman ; Kees Cook
> ; Jann Horn ; Johannes
> Weiner ; Arun KS ; Janne
> Huttunen ; Konstantin Khlebnikov
> ; linux-kernel@vger.kernel.org; linux-
> m...@kvack.org
> Subject: Re: [RFC] mm: Proactive compaction
>
> On Fri, Aug 16, 2019 at 02:43:30PM -0700, Nitin Gupta wrote:
> > 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.
> >
>
> Note that proactive compaction may reduce allocation latency but it is not
> free either. Even though the scanning and migration may happen in a kernel
> thread, tasks can incur faults while waiting for compaction to complete if the
> task accesses data being migrated. This means that costs are incurred by
> applications on a system that may never care about high-order allocation
> latency -- particularly if the allocations typically happen at application
> initialisation time. I recognise that kcompactd makes a bit of effort to
> compact memory out-of-band but it also is typically triggered in response to
> reclaim that was triggered by a high-order allocation request. i.e. the work
> done by the thread is triggered by an allocation request that hit the slow
> paths and not a preemptive measure.
>
Hitting the slow path for every higher-order allocation is a signification
performance/latency issue for applications that requires a large number of
these allocations to succeed in bursts. To get some concrete numbers, 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
(referred to as "Light" in the table below) and if that fails, tries to
allocate with `GFP_TRANSHUGE | __GFP_RETRY_MAYFAIL` (referred to as
"Fallback" in table below). We stop the allocation loop if both methods
fail.
Table-1: hugepage allocation latencies on vanilla 5.3.0-rc5. All latencies
are in microsec.
| GFP/Stat |Any | Light | Fallback |
|: | -: | --: | -: |
|count | 9908 | 788 | 9120 |
| min |0.0 | 0.0 | 1726.0 |
| max | 135387.0 | 142.0 | 135387.0 |
| mean |5494.66 |1.83 |5969.26 |
| stddev | 21624.04 |7.58 | 22476.06 |
As you can see, the mean and stddev of allocation is extremely high with
the current approach of on-demand compaction.
The system was fragmented from a userspace program as I described in this
patch description. The workload is mainly anonymous userspace pages which
as easy to move around. I intentionally avoided unmovable pages in this
test to see how much latency do we incur just by hitting the slow path for
a majority of allocations.
> > For a more proactive compaction, the approach taken here is to define
> > per page-order external fragmentation thresholds and let kcompactd
> > threads act on these thresholds.
> >
> > The low and high thresholds are defined per page-order and exposed
> > through sysfs:
> >
> > /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
> >
>
> These will be difficult for an admin to tune that is not extremely familiar
> with
> how external fragmentation is defined. If an admin asked "how much will
> stalls be reduced by setting this to a different value?", the answer will
> always
> be "I don't know, maybe some, maybe not".
>
Yes, this is my main worry. These values can be set to emperically
determined values on highly specialized systems like database appliances.
However, on a generic system, there is no real reasonable value.
Still, at the very least, I would like an interface that allows compacting
system to a reasonable state. Something like:
compact_extfrag(node, zone, order, high, low)
which start compaction if extfrag > high, a
Re: [RFC] mm: Proactive compaction
On Fri, Aug 16, 2019 at 02:43:30PM -0700, Nitin Gupta wrote:
> 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.
>
Note that proactive compaction may reduce allocation latency but it is not
free either. Even though the scanning and migration may happen in a kernel
thread, tasks can incur faults while waiting for compaction to complete if
the task accesses data being migrated. This means that costs are incurred
by applications on a system that may never care about high-order allocation
latency -- particularly if the allocations typically happen at application
initialisation time. I recognise that kcompactd makes a bit of effort to
compact memory out-of-band but it also is typically triggered in response
to reclaim that was triggered by a high-order allocation request. i.e. the
work done by the thread is triggered by an allocation request that hit
the slow paths and not a preemptive measure.
> For a more proactive compaction, the approach taken here is to define
> per page-order external fragmentation thresholds and let kcompactd
> threads act on these thresholds.
>
> The low and high thresholds are defined per page-order and exposed
> through sysfs:
>
> /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
>
These will be difficult for an admin to tune that is not extremely
familiar with how external fragmentation is defined. If an admin asked
"how much will stalls be reduced by setting this to a different value?",
the answer will always be "I don't know, maybe some, maybe not".
> Per-node kcompactd thread is woken up every few seconds to check if
> any zone on its node has extfrag above the extfrag_high threshold for
> any order, in which case the thread starts compaction in the backgrond
> till all zones are below extfrag_low level for all orders. By default
> both these thresolds are set to 100 for all orders which essentially
> disables kcompactd.
>
> To avoid wasting CPU cycles when compaction cannot help, such as when
> memory is full, we check both, extfrag > extfrag_high and
> compaction_suitable(zone). This allows kcomapctd thread to stays inactive
> even if extfrag thresholds are not met.
>
There is still a risk that if a system is completely fragmented that it
may consume CPU on pointless compaction cycles. This is why compaction
from kernel thread context makes no special effort and bails relatively
quickly and assumes that if an application really needs high-order pages
that it'll incur the cost at allocation time.
> This patch is largely based on ideas from Michal Hocko posted here:
> https://lore.kernel.org/linux-mm/20161230131412.gi13...@dhcp22.suse.cz/
>
> Testing done (on x86):
> - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> respectively.
> - Use a test program to fragment memory: the program allocates all memory
> and then for each 2M aligned section, frees 3/4 of base pages using
> munmap.
> - kcompactd0 detects fragmentation for order-9 > extfrag_high and starts
> compaction till extfrag < extfrag_low for order-9.
>
This is a somewhat optimisitic allocation scenario. The interesting
ones are when a system is fragmenteed in a manner that is not trivial to
resolve -- e.g. after a prolonged period of time with unmovable/reclaimable
allocations stealing pageblocks. It's also fairly difficult to analyse
if this is helping because you cannot measure after the fact how much
time was saved in allocation time due to the work done by kcompactd. It
is also hard to determine if the sum of the stalls incurred by proactive
compaction is lower than the time saved at allocation time.
I fear that the user-visible effect will be times when there are very
short but numerous stalls due to proactive compaction running in the
background that will be hard to detect while the benefits may be invisible.
> The patch has plenty of rough edges but posting it early to see if I'm
> going in the right direction and to get some early feedback.
>
As unappealing as it sounds, I think it is better to try improve the
allocation latency itself instead of trying to hide the cost in a kernel
thread. It's far harder to implement as compaction is not easy but it
would be more obvious what the savings are by looking at a histogram of
allocation latencies -- there are other metrics that could be considered
but that's the obvious one.
--
RE: [RFC] mm: Proactive compaction
> -Original Message-
> From: owner-linux...@kvack.org On Behalf
> Of Matthew Wilcox
> Sent: Tuesday, August 20, 2019 3:21 PM
> To: Nitin Gupta
> Cc: a...@linux-foundation.org; vba...@suse.cz;
> mgor...@techsingularity.net; mho...@suse.com;
> dan.j.willi...@intel.com; Yu Zhao ; Qian Cai
> ; Andrey Ryabinin ; Roman
> Gushchin ; Greg Kroah-Hartman
> ; Kees Cook ; Jann
> Horn ; Johannes Weiner ; Arun
> KS ; Janne Huttunen
> ; Konstantin Khlebnikov
> ; linux-kernel@vger.kernel.org; linux-
> m...@kvack.org
> Subject: Re: [RFC] mm: Proactive compaction
>
> On Fri, Aug 16, 2019 at 02:43:30PM -0700, Nitin Gupta wrote:
> > Testing done (on x86):
> > - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> > respectively.
> > - Use a test program to fragment memory: the program allocates all
> > memory and then for each 2M aligned section, frees 3/4 of base pages
> > using munmap.
> > - kcompactd0 detects fragmentation for order-9 > extfrag_high and
> > starts compaction till extfrag < extfrag_low for order-9.
>
> Your test program is a good idea, but I worry it may produce unrealistically
> optimistic outcomes. Page cache is readily reclaimable, so you're setting up
> a situation where 2MB pages can once again be produced.
>
> How about this:
>
> One program which creates a file several times the size of memory (or
> several files which total the same amount). Then read the file(s). Maybe by
> mmap(), and just do nice easy sequential accesses.
>
> A second program which causes slab allocations. eg
>
> for (;;) {
> for (i = 0; i < n * 1000 * 1000; i++) {
> char fname[64];
>
> sprintf(fname, "/tmp/missing.%d", i);
> open(fname, O_RDWR);
> }
> }
>
> The first program should thrash the pagecache, causing pages to
> continuously be allocated, reclaimed and freed. The second will create
> millions of dentries, causing the slab allocator to allocate a lot of
> order-0 pages which are harder to free. If you really want to make it work
> hard, mix in opening some files whihc actually exist, preventing the pages
> which contain those dentries from being evicted.
>
> This feels like it's simulating a more normal workload than your test.
> What do you think?
This combination of workloads for mixing movable and unmovable
pages sounds good. I coded up these two and here's what I observed:
- kernel: 5.3.0-rc5 + this patch, x86_64, 32G RAM.
- Set extfrag_{low,high} = {25,30} for order-9
- Run pagecache and dentry thrash test programs as you described
- for pagecache test: mmap and sequentially read 128G file on a 32G system.
- for dentry test: set n=100. I created /tmp/missing.[0-1] so these
dentries stay allocated..
- Start linux kernel compile for further pagecache thrashing.
With above workload fragmentation for order-9 stayed 80-90% which kept
kcompactd0 working but it couldn't make progress due to unmovable pages
from dentries. As expected, we keep hitting compaction_deferred() as
compaction attempts fail.
After a manual `echo 3 | /proc/sys/vm/drop_caches` and stopping dentry thrasher,
kcompactd succeded in bringing extfrag below set thresholds.
With unmovable pages spread across memory, there is little compaction
can do. Maybe we should have a knob like 'compactness' (like swapiness) which
defines how aggressive compaction can be. For high values, maybe allow
freeing dentries too? This way hugepage sensitive applications can trade
with higher I/O latencies.
Thanks,
Nitin
Re: [RFC] mm: Proactive compaction
On Fri, Aug 16, 2019 at 02:43:30PM -0700, Nitin Gupta wrote:
> Testing done (on x86):
> - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> respectively.
> - Use a test program to fragment memory: the program allocates all memory
> and then for each 2M aligned section, frees 3/4 of base pages using
> munmap.
> - kcompactd0 detects fragmentation for order-9 > extfrag_high and starts
> compaction till extfrag < extfrag_low for order-9.
Your test program is a good idea, but I worry it may produce
unrealistically optimistic outcomes. Page cache is readily reclaimable,
so you're setting up a situation where 2MB pages can once again be
produced.
How about this:
One program which creates a file several times the size of memory (or
several files which total the same amount). Then read the file(s). Maybe
by mmap(), and just do nice easy sequential accesses.
A second program which causes slab allocations. eg
for (;;) {
for (i = 0; i < n * 1000 * 1000; i++) {
char fname[64];
sprintf(fname, "/tmp/missing.%d", i);
open(fname, O_RDWR);
}
}
The first program should thrash the pagecache, causing pages to
continuously be allocated, reclaimed and freed. The second will create
millions of dentries, causing the slab allocator to allocate a lot of
order-0 pages which are harder to free. If you really want to make it
work hard, mix in opening some files whihc actually exist, preventing
the pages which contain those dentries from being evicted.
This feels like it's simulating a more normal workload than your test.
What do you think?
RE: [RFC] mm: Proactive compaction
> -Original Message-
> From: Vlastimil Babka
> Sent: Tuesday, August 20, 2019 1:46 AM
> To: Nitin Gupta ; a...@linux-foundation.org;
> mgor...@techsingularity.net; mho...@suse.com;
> dan.j.willi...@intel.com
> Cc: Yu Zhao ; Matthew Wilcox ;
> Qian Cai ; Andrey Ryabinin ; Roman
> Gushchin ; Greg Kroah-Hartman
> ; Kees Cook ; Jann
> Horn ; Johannes Weiner ; Arun
> KS ; Janne Huttunen
> ; Konstantin Khlebnikov
> ; linux-kernel@vger.kernel.org; linux-
> m...@kvack.org; Khalid Aziz
> Subject: Re: [RFC] mm: Proactive compaction
>
> +CC Khalid Aziz who proposed a different approach:
> https://lore.kernel.org/linux-mm/20190813014012.30232-1-
> khalid.a...@oracle.com/T/#u
>
> On 8/16/19 11:43 PM, Nitin Gupta wrote:
> > 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-order external fragmentation thresholds and let kcompactd
> > threads act on these thresholds.
> >
> > The low and high thresholds are defined per page-order and exposed
> > through sysfs:
> >
> > /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
> >
> > Per-node kcompactd thread is woken up every few seconds to check if
> > any zone on its node has extfrag above the extfrag_high threshold for
> > any order, in which case the thread starts compaction in the backgrond
> > till all zones are below extfrag_low level for all orders. By default
> > both these thresolds are set to 100 for all orders which essentially
> > disables kcompactd.
>
> Could you define what exactly extfrag is, in the changelog?
>
extfrag for order-n = ((total free pages) - (free pages for order >= n)) /
(total free pages) * 100;
I will add this to v2 changelog.
> > To avoid wasting CPU cycles when compaction cannot help, such as when
> > memory is full, we check both, extfrag > extfrag_high and
> > compaction_suitable(zone). This allows kcomapctd thread to stays
> > inactive even if extfrag thresholds are not met.
>
> How does it translate to e.g. the number of free pages of order?
>
Watermarks are checked as follows (see: __compaction_suitable)
watermark = (order > PAGE_ALLOC_COSTLY_ORDER) ?
low_wmark_pages(zone) : min_wmark_pages(zone);
If a zone does not satisfy this watermark, we don't start compaction.
> > This patch is largely based on ideas from Michal Hocko posted here:
> > https://lore.kernel.org/linux-
> mm/20161230131412.gi13...@dhcp22.suse.cz
> > /
> >
> > Testing done (on x86):
> > - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> > respectively.
> > - Use a test program to fragment memory: the program allocates all
> > memory and then for each 2M aligned section, frees 3/4 of base pages
> > using munmap.
> > - kcompactd0 detects fragmentation for order-9 > extfrag_high and
> > starts compaction till extfrag < extfrag_low for order-9.
> >
> > The patch has plenty of rough edges but posting it early to see if I'm
> > going in the right direction and to get some early feedback.
>
> That's a lot of control knobs - how is an admin supposed to tune them to
> their needs?
I expect that a workload would typically care for just a particular page order
(say, order-9 on x86 for the default hugepage size). An admin can set
extfrag_{low,high} for just that order (say, low=25, high=30) and leave these
thresholds to their default value (low=100, high=100) for all other orders.
Thanks,
Nitin
>
> (keeping the rest for reference)
>
> > Signed-off-by: Nitin Gupta
> > ---
> > include/linux/compaction.h | 12 ++
> > mm/compaction.c| 250 ++---
> > mm/vmstat.c| 12 ++
> > 3 files changed, 228 insertions(+), 46 deletions(-)
> >
> > diff --git a/include/linux/compaction.h b/include/linux/compaction.h
> > index 9569e7c786d3..26bfedbbc64b 100
Re: [RFC] mm: Proactive compaction
+CC Khalid Aziz who proposed a different approach:
https://lore.kernel.org/linux-mm/20190813014012.30232-1-khalid.a...@oracle.com/T/#u
On 8/16/19 11:43 PM, Nitin Gupta wrote:
> 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-order external fragmentation thresholds and let kcompactd
> threads act on these thresholds.
>
> The low and high thresholds are defined per page-order and exposed
> through sysfs:
>
> /sys/kernel/mm/compaction/order-[1..MAX_ORDER]/extfrag_{low,high}
>
> Per-node kcompactd thread is woken up every few seconds to check if
> any zone on its node has extfrag above the extfrag_high threshold for
> any order, in which case the thread starts compaction in the backgrond
> till all zones are below extfrag_low level for all orders. By default
> both these thresolds are set to 100 for all orders which essentially
> disables kcompactd.
Could you define what exactly extfrag is, in the changelog?
> To avoid wasting CPU cycles when compaction cannot help, such as when
> memory is full, we check both, extfrag > extfrag_high and
> compaction_suitable(zone). This allows kcomapctd thread to stays inactive
> even if extfrag thresholds are not met.
How does it translate to e.g. the number of free pages of order?
> This patch is largely based on ideas from Michal Hocko posted here:
> https://lore.kernel.org/linux-mm/20161230131412.gi13...@dhcp22.suse.cz/
>
> Testing done (on x86):
> - Set /sys/kernel/mm/compaction/order-9/extfrag_{low,high} = {25, 30}
> respectively.
> - Use a test program to fragment memory: the program allocates all memory
> and then for each 2M aligned section, frees 3/4 of base pages using
> munmap.
> - kcompactd0 detects fragmentation for order-9 > extfrag_high and starts
> compaction till extfrag < extfrag_low for order-9.
>
> The patch has plenty of rough edges but posting it early to see if I'm
> going in the right direction and to get some early feedback.
That's a lot of control knobs - how is an admin supposed to tune them to their
needs?
(keeping the rest for reference)
> Signed-off-by: Nitin Gupta
> ---
> include/linux/compaction.h | 12 ++
> mm/compaction.c| 250 ++---
> mm/vmstat.c| 12 ++
> 3 files changed, 228 insertions(+), 46 deletions(-)
>
> diff --git a/include/linux/compaction.h b/include/linux/compaction.h
> index 9569e7c786d3..26bfedbbc64b 100644
> --- a/include/linux/compaction.h
> +++ b/include/linux/compaction.h
> @@ -60,6 +60,17 @@ enum compact_result {
>
> struct alloc_context; /* in mm/internal.h */
>
> +// "order-%d"
> +#define COMPACTION_ORDER_STATE_NAME_LEN 16
> +// Per-order compaction state
> +struct compaction_order_state {
> + unsigned int order;
> + unsigned int extfrag_low;
> + unsigned int extfrag_high;
> + unsigned int extfrag_curr;
> + char name[COMPACTION_ORDER_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 +101,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,
> diff --git a/mm/compaction.c b/mm/compaction.c
> index 952dc2fb24e5..21866b1ad249 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -25,6 +25,10 @@
> #include
> #include "internal.h"
>
> +#ifdef CONFIG_COMPACTION
> +struct compaction_order_state compaction_order_states[MAX_ORDER+1];
> +#endif
> +
> #ifdef CONFIG_COMPACTION
> static inline void count_compact_event(enum vm_event_item item)
> {
> @@ -1846,6 +1850,49 @@ static inline bool is_via_compact_memory(int order)
> return order == -1;
> }
>
> +static int extfrag_wmark_high(struct zone *zone)
> +{
> + int order;
> +
> + for (order = 1; order <= MAX_ORDER; order++) {
> + int extfrag = extfrag_for_order(zone, order);
> +
