Memory Balancing

Reclaim을 피하는 allocation

Memory Balancing 문서는 2000년 1월 Kanoj Sarcar <[email protected]>가 시작했습니다. Balancing은 `!__GFP_HIGH`, `!__GFP_KSWAPD_RECLAIM`, 그리고 non-`__GFP_IO` allocation에도 필요합니다.

Caller가 reclaim을 피하는 첫 이유는 spinlock을 보유했거나 interrupt context여서 sleep할 수 없기 때문입니다. 두 번째는 page reclaim overhead 없이 allocation 실패를 받아들이려는 경우입니다.

Order-0 fallback이 있는 opportunistic high-order request가 두 번째 경우에 해당할 수 있으며 caller는 kswapd를 깨우는 것도 피하려 할 수 있습니다. `__GFP_IO` allocation request는 filesystem deadlock을 방지하기 위해 사용합니다.

================
Memory Balancing
================

Started Jan 2000 by Kanoj Sarcar <[email protected]>

Memory balancing is needed for !__GFP_HIGH and !__GFP_KSWAPD_RECLAIM as
well as for non __GFP_IO allocations.

The first reason why a caller may avoid reclaim is that the caller can not
sleep due to holding a spinlock or is in interrupt context. The second may
be that the caller is willing to fail the allocation without incurring the
overhead of page reclaim. This may happen for opportunistic high-order
allocation requests that have order-0 fallback options. In such cases,
the caller may also wish to avoid waking kswapd.

__GFP_IO allocation requests are made to prevent file system deadlocks.

Lazy reclaim과 zone pool 선택

Non-sleepable allocation request가 없다면 proactive balancing은 해로워 보일 수 있습니다. Page reclaim은 zone free memory가 0이 되는 등 실제 필요할 때만 lazy하게 시작할 수 있습니다.

그러나 kernel은 direct-mapped page request를 DMA pool로 fallback하기보다 direct-mapped pool에서 충족해 DMA request를 위해 DMA pool을 유지해야 합니다. Highmem과 direct-mapped page에도 같은 논리가 적용됩니다.

반대로 free DMA page가 많다면 regular-zone balancing overhead를 내는 대신 DMA pool에서 regular memory request를 충족하는 편이 낫습니다.

In the absence of non sleepable allocation requests, it seems detrimental
to be doing balancing. Page reclamation can be kicked off lazily, that
is, only when needed (aka zone free memory is 0), instead of making it
a proactive process.

That being said, the kernel should try to fulfill requests for direct
mapped pages from the direct mapped pool, instead of falling back on
the dma pool, so as to keep the dma pool filled for dma requests (atomic
or not). A similar argument applies to highmem and direct mapped pages.
OTOH, if there is a lot of free dma pages, it is preferable to satisfy
regular memory requests by allocating one from the dma pool, instead
of incurring the overhead of regular zone balancing.

Linux 2.2 방식의 한계

Linux 2.2에서는 전체 free page 수가 total memory의 1/64 아래로 떨어질 때만 memory balancing/page reclamation이 시작됐습니다.

DMA와 regular memory 비율에 따라 DMA zone이 완전히 비어도 전체 기준 때문에 balancing이 일어나지 않을 수 있었습니다. 여러 memory 크기의 production machine에서는 이 문제에도 대체로 잘 동작했지만 Linux 2.3의 HIGHMEM 도입으로 문제가 커졌습니다.

In 2.2, memory balancing/page reclamation would kick off only when the
_total_ number of free pages fell below 1/64 th of total memory. With the
right ratio of dma and regular memory, it is quite possible that balancing
would not be done even when the dma zone was completely empty. 2.2 has
been running production machines of varying memory sizes, and seems to be
doing fine even with the presence of this problem. In 2.3, due to
HIGHMEM, this problem is aggravated.

Linux 2.3의 두 zone-balancing 방안

첫 방안은 zone 크기와 필요하면 lower-class zone 크기에 따라 initialization 때 각 zone의 목표 free-page 수를 정하는 것입니다. Balancing 중 lower-class zone 크기를 다시 볼 필요가 없다는 장점이 있지만 lower-class zone의 낮은 사용량을 무시해 너무 자주 balancing할 수 있습니다. Allocation routine을 조금 바꾸면 `memclass()` macro를 단순 equality로 줄일 수도 있습니다.

두 번째 방안은 해당 zone과 모든 lower-class zone의 free memory 합계가 그 zone들과 lower-class zone total memory의 1/64 아래로 떨어질 때만 balance하는 것입니다.

이 방법은 Linux 2.2 문제를 고치면서 당시 동작과 가깝게 유지하고, zone 수와 type이 다른 architecture에도 같은 algorithm을 적용합니다. 앞으로 zone별 free page에 다른 weight를 줄 수도 있습니다.

Regular zone이 DMA zone보다 매우 크면 regular-zone balancing 판단에 free DMA page를 포함하는 의미가 작아지므로 첫 번째 방안이 더 매력적입니다.

In 2.3, zone balancing can be done in one of two ways: depending on the
zone size (and possibly of the size of lower class zones), we can decide
at init time how many free pages we should aim for while balancing any
zone. The good part is, while balancing, we do not need to look at sizes
of lower class zones, the bad part is, we might do too frequent balancing
due to ignoring possibly lower usage in the lower class zones. Also,
with a slight change in the allocation routine, it is possible to reduce
the memclass() macro to be a simple equality.

Another possible solution is that we balance only when the free memory
of a zone _and_ all its lower class zones falls below 1/64th of the
total memory in the zone and its lower class zones. This fixes the 2.2
balancing problem, and stays as close to 2.2 behavior as possible. Also,
the balancing algorithm works the same way on the various architectures,
which have different numbers and types of zones. If we wanted to get
fancy, we could assign different weights to free pages in different
zones in the future.

Note that if the size of the regular zone is huge compared to dma zone,
it becomes less significant to consider the free dma pages while
deciding whether to balance the regular zone. The first solution
becomes more attractive then.

선택된 방안과 kswapd

첨부 patch는 두 번째 방안을 구현했습니다. 또한 non-sleepable allocation의 low-memory 상황에서 Linux 2.2처럼 kswapd를 깨우도록 했습니다.

HIGHMEM zone도 balance해 `replace_with_highmem()`이 HIGHMEM page를 얻을 기회를 주고 HIGHMEM allocation이 regular zone으로 fallback하지 않게 했습니다. Swapcache에 있으나 아무도 쓰지 않는 HIGHMEM page 같은 leak도 막습니다.

kswapd는 어느 zone을 balance해야 하는지 알아야 합니다. 모든 allocation이 interrupt context에서 오고 process context가 모두 sleep해 직접 balancing할 수 없는 상황에서 주로 필요합니다.

Linux 2.3에서 interrupt context는 highmem page를 요청하지 않으므로 kswapd가 highmem zone을 balance할 필요는 없습니다. kswapd는 zone structure의 `zone_wake_kswapd` field로 balancing 필요 여부를 판단합니다.

The appended patch implements the second solution. It also "fixes" two
problems: first, kswapd is woken up as in 2.2 on low memory conditions
for non-sleepable allocations. Second, the HIGHMEM zone is also balanced,
so as to give a fighting chance for replace_with_highmem() to get a
HIGHMEM page, as well as to ensure that HIGHMEM allocations do not
fall back into regular zone. This also makes sure that HIGHMEM pages
are not leaked (for example, in situations where a HIGHMEM page is in
the swapcache but is not being used by anyone)

kswapd also needs to know about the zones it should balance. kswapd is
primarily needed in a situation where balancing can not be done,
probably because all allocation requests are coming from intr context
and all process contexts are sleeping. For 2.3, kswapd does not really
need to balance the highmem zone, since intr context does not request
highmem pages. kswapd looks at the zone_wake_kswapd field in the zone
structure to decide whether a zone needs balancing.

Page stealing과 watermark hysteresis

Process memory와 shared memory에서 page를 steal하는 것은 그 page가 속한 node에서 watermark 아래로 내려간 zone의 memory pressure를 완화할 때 수행합니다.

`watermark[WMARK_MIN/WMARK_LOW/WMARK_HIGH]`, `low_on_memory`, `zone_wake_kswapd`는 zone별 field로 balancing 시점을 정합니다.

Free page 수가 `WMARK_MIN` 아래로 내려가면 hysteresis field `low_on_memory`가 set되고, free page가 `WMARK_HIGH`에 이를 때까지 유지됩니다. `low_on_memory`가 set된 동안 allocation request에 `GFP_WAIT`가 있으면 zone에서 page를 free하려 합니다.

kswapd를 깨우는 판단은 이 hysteresis와 별개입니다. Free page가 `WMARK_LOW` 아래면 `zone_wake_kswapd`를 set해 kswapd가 zone page를 free하게 합니다.

Page stealing from process memory and shm is done if stealing the page would
alleviate memory pressure on any zone in the page's node that has fallen below
its watermark.

watermark[WMARK_MIN/WMARK_LOW/WMARK_HIGH]/low_on_memory/zone_wake_kswapd: These
are per-zone fields, used to determine when a zone needs to be balanced. When
the number of pages falls below watermark[WMARK_MIN], the hysteric field
low_on_memory gets set. This stays set till the number of free pages becomes
watermark[WMARK_HIGH]. When low_on_memory is set, page allocation requests will
try to free some pages in the zone (providing GFP_WAIT is set in the request).
Orthogonal to this, is the decision to poke kswapd to free some zone pages.
That decision is not hysteresis based, and is done when the number of free
pages is below watermark[WMARK_LOW]; in which case zone_wake_kswapd is also set.

추가 아이디어

• Zone별 failed request 수를 추적해 dynamic experience가 balancing 정책에 영향을 주게 합니다. 제안자는 [email protected]입니다.
• DMA page를 보존하기 위해 `replace_with_highmem()`과 비슷한 `replace_with_regular()`을 구현합니다. 제안자는 [email protected]입니다.

(Good) Ideas that I have heard:

1. Dynamic experience should influence balancing: number of failed requests
   for a zone can be tracked and fed into the balancing scheme ([email protected])
2. Implement a replace_with_highmem()-like replace_with_regular() to preserve
   dma pages. ([email protected])