2.4.15pre6aa1 (fixes google VM problem)
Subsystems (5)
It would be interesting if people experiencing the VM problems originally reported by google (but also trivially reproducible with simple cache operations) could verify that this update fixes those troubles. I wrote some documentation on the bug and the relevant fix in the vm-14 section below. Thanks.
If all works right on Monday I will port the fix to mainline (it's basically only a matter of extracting a few bits from the vm-14 patch, it's not really controversial but I didn't had much time to extract it yet, the reason it's not in a self contained patch from the first place is because of the way it was written). Comments are welcome of course, I don't think there's another way around it though, even if we would generate a logical swap cache not in function of the swap entry that still wouldn't solve the problem of mlocked highmem users [or very frequently accessed ptes] in the lowmem zones. The lowmem ram wasted for this purpose is very minor compared to the total waste of all the highmem zones, and the algorithm I implemented adapts in function of the amount of highmem so the lowmem waste is proportial with the potential highmem waste. However the lower_zone_reserve defaults could be changed, I choosen the current defaults in a conservative manner.
URL:
ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/kernels/v2.4/2.4.15pre6aa1.bz2 ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/kernels/v2.4/2.4.15pre6aa1/
Only in 2.4.15pre1aa1: 00_lvm-1.0.1-rc4-3.bz2
Only in 2.4.15pre6aa1: 00_lvm-1.0.1-rc4-4.bz2
Rest of the rc4 diffs rediffed.
Only in 2.4.15pre1aa1: 00_rwsem-fair-23 Only in 2.4.15pre6aa1: 00_rwsem-fair-24 Only in 2.4.15pre1aa1: 00_rwsem-fair-23-recursive-4 Only in 2.4.15pre6aa1: 00_rwsem-fair-24-recursive-5
Rediffed.
Only in 2.4.15pre1aa1: 00_strnlen_user-x86-ret1-1
Merged in mainline.
Only in 2.4.15pre1aa1: 10_lvm-deadlock-fix-1
Now in mainline.
Only in 2.4.15pre1aa1: 10_lvm-incremental-1
Only in 2.4.15pre6aa1: 10_lvm-incremental-2
Part of it in mainline, rediffed the rest.
Only in 2.4.15pre1aa1: 10_vm-13
Only in 2.4.15pre6aa1: 10_vm-14
This should be the first kernel out there without the google VM troubles (that are affecting more than just google testcase). The broken piece of VM was this kind of loop in the allocator:
for (;;) {
zone_t *z = *(zone++);
if (!z)
break;
if (zone_free_pages(z, order) > z->pages_low) {
page = rmqueue(z, order);
if (page)
return page;
}
}
and the above logic is present in all 2.4 kernels out there (2.3 as well). So the bug has nearly nothing to do with the memory balancing engine as most of us would expect, it's an allocator zone balancing bug instead in a piece of code that one would assume to be obviously correct.
The problem cames from the fact that all the ZONE_NORMAL can be allocated with unfreeable highmem users (like anon pages when no swap is available). If that happens the machine runs out of memory no matter what (even if there are 63G of cache clean ready to be freed). Mainline deadlocks because of the infinite loop in the allocator, -aa was ""correctly"" just killing tasks as soon as the normal zone was filled of mlocked cache or anon pages with no swap.
The fix is to have a per-classzone per-zone set of watermarks (see the zone->watermarks[class_idx] array). Seems to work fine here. Of course this means potentially wasting some memory when the highmem zone is huge but there's no other way around it and the potential waste of all the highmem memory is huge compared to a very small waste of the normal zone (it could be more finegrined of course, for example we don't keep track if an allocation will generate a page freeable from the VM or not, but those are minor issues and not easily solvable anyways [we pin pages with a get_page and we certainly don't want to migrate pages across zones within get_page], and the core problem should be just fixed).
Since the logic is generic and applies also to the zone dma vs zone normal (not only zone normal vs zone highmem) this should be tested a bit on the lowmem boxes too (I just took care of the lowmem boxes in theory, but I didn't tested it in practice).
In short now we reserve a part of the lower zones for the lower classzone allocations. The algorithm I wrote calculates the "reserved portion" in function of the size of the higher zone (higher zone means the "zone" that matches the "classzone"). For example a 1G machine will reserve a very little part of the zone_normal. A 64G machine is going to reserve all the 800mbyte of zone normal for allocations from the normal classzone instead (this is fine because it would be a total waste if a 64G machine would risk to run OOM because the zone normal is all occupied by unfreeable highmem users that would much better stay in the highmem zone instead). The ratio between higher zone size and reserved lower zone size, is selectable via boot option ala memfrac= (the new option is called lower_zone_reserve=). Default values should work well (they as usual doesn't need to be perfect, but they can be changed if you've suggestions), the boot option is there just in case.
Only in 2.4.15pre6aa1: 10_vm-14-no-anonlru-1
Only in 2.4.15pre6aa1: 10_vm-14-no-anonlru-1-simple-cache-1
Backed out the anon pages from the lru again, mainly to avoid to swapout too easily and because this is going to be tested on the big boxes with no swap at all anyways.
Only in 2.4.15pre1aa1: 50_uml-patch-2.4.13-5.bz2
Only in 2.4.15pre6aa1: 50_uml-patch-2.4.14-2.bz2
Latest Jeff's uml update.
Only in 2.4.15pre1aa1: 60_tux-2.4.13-ac5-B0.bz2
Only in 2.4.15pre6aa1: 60_tux-2.4.13-ac5-B1.bz2
Latest Ingo's tux update.
Andrea
Quoted 1 line · Andrea Arcangeli
If all works right on Monday I will port the fix to mainline (it's
Ok here it is against 2.4.15pre6:
ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.15pre6/zone-watermarks-1
(also attached to the email). Untested on top of mainline but should be safe to apply. also avoids GFP_ATOMIC from interrupts to eat the PF_MEMALLOC (longstanding fix from Manfred).
Andrea
include/linux/mmzone.h +23 -4
@@ -18,6 +18,11 @@#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER#endif +#define ZONE_DMA 0 +#define ZONE_NORMAL 1 +#define ZONE_HIGHMEM 2 +#define MAX_NR_ZONES 3 + typedef struct free_area_struct { struct list_head free_list; unsigned long *map;
@@ -25,6 +30,10 @@struct pglist_data ; +typedef struct zone_watermarks_s { +unsigned long min, low, high; +}zone_watermarks_t ; +/* * On machines where it is needed (eg PCs) we divide physical memory * into multiple physical zones. On a PC we have 3 zones:
@@ -39,8 +48,17 @@*/ spinlock_t lock;unsigned long free_pages; -unsigned long pages_min, pages_low, pages_high; -int need_balance; + +/* +* We don't know if the memory that we're going to allocate will be freeable +* or/and it will be released eventually, so to avoid totally wasting several +* GB of ram we must reserve some of the lower zone memory (otherwise we risk +* to run OOM on the lower zones despite there's tons of freeable ram +* on the higher zones). +*/ +zone_watermarks_t watermarks[MAX_NR_ZONES ]; + +unsigned long need_balance;/* * free areas of different sizes
@@ -60,6 +78,7 @@*/ char *name;unsigned long size; +unsigned long realsize; } zone_t;#define ZONE_DMA 0
@@ -113,8 +132,8 @@extern int numnodes;extern pg_data_t *pgdat_list; -#define memclass (pgzone, classzone) (((pgzone)->zone_pgdat == (classzone)->zone_pgdat) \ - && ((pgzone) <= (classzone))) +#define zone_idx (zone) ((zone) - (zone)->zone_pgdat->node_zones) +#define memclass (pgzone, classzone) (zone_idx(pgzone) <= zone_idx(classzone))/* * The following two are not meant for general usage. They are here as
mm/page_alloc.c +52 -16
148 lines not on this page · raw message
mm/vmscan.c +5 -4
@@ -606,11 +606,12 @@static int check_classzone_need_balance (zone_t * classzone) { -zone_t * first_classzone; +zone_t * first_zone; +int class_idx =zone_idx (classzone); - first_classzone = classzone->zone_pgdat->node_zones; -while (classzone >= first_classzone) { -if (classzone->free_pages > classzone->pages_high) + first_zone = classzone->zone_pgdat->node_zones; +while (classzone >= first_zone) { +if (classzone->free_pages > classzone->watermarks[class_idx].high)return 0 ; classzone--; }
Quoted 4 lines · Andrea Arcangeli
Ok here it is against 2.4.15pre6:
ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.15pre6/zone-watermarks-1
Hmm.. I see what you're trying to do, but it seems overly complicated to me.
Correct me if I'm wrong, but what you really want to say is basically:
If we're doing a allocation from many zones, we don't want to allow an allocator that can use big zones to deplete the small zones.
You do this by building up this "per-zone-per-classzone" array, which basically says that "if you had a big classzone, your minimum requirements for the next zonelist are higher".
Now, I'd rather look at it from another angle: the fact is that the simple for-loop that allows any allocator to allocate equal amounts of memory from any zone it wants is kind of unfair. So the for-loop is arguably broken.
So we currently have a for-loop that looks like
for (;;) {
zone_t *z = *(zone++);
..
min = z->pages_low;
..
}and the basic problem is that the above loop doesn't have any "memory": we really want it to remember the fact that it has had an earlier zone that was perhaps large, and not just see each new zone as an independent allocation decision.
So why not have the much simpler patch to just say:
min = 0;
for (;;) {
zone_t *z = *(zone++);
..
min = (min >> 2) + z->pages_low;
..
}or similar that simply _ages_ the "min" according to previous zones that we've already tried. That makes the data structures much simpler, and shows much more clearly what it is we are actually trying to do. We're trying to say that the size of the previous zones in the allocation list _does_ matter. Basically now we have a "history" of how much memory we have already looked at.
(The "(min >> 2) + new" is obviously just a first try, I'm not claiming it's a particularly good aging function, but it's the standard kind of exponential aging approach).
With something like the above, the threshold of allocation in smaller zones is much higher: let's say that your HIGHMEM zone is four times as big as your NORMAL zone, then a HIGHMEM allocation will want to see twice as much memory in the NORMAL zone than a NORMAL allocation would want to.
See what I'm saying? The above algorithm more closely follows what we really want to do, and by doing so it makes the code much simpler to follow (no "What does this 'z->watermarks[class_idx].low' thing mean?" questions), not to mention causing simpler data structures etc.
The actual _behaviour_ should be pretty close to yours (modulo the differences in calculating the watermarks - your "lower_zone_reserve_ratio" setup is not quite the same thing as just shifting by 2 every time).
Linus
Quoted 9 lines · Linus Torvalds
So why not have the much simpler patch to just say:
min = 0; for (;;) { zone_t *z = *(zone++); .. min = (min >> 2) + z->pages_low; ..
Actually, as we already limit "pages_low" (for _all_ zones) through the use of zone_balance_max[], I don't think we need to even age the minimum pages.
And instead of doing "zone->free_pages - (1UL << order)" in zone_free_pages(), we can do it much more efficiently just once for the for-loop by initializing "min" to "(1UL << order)" instead of zero. So we'd just make the loop be
min = (1UL << order);
for (;;) {
zone_t *z = *(zone++);
..
min += z->pages_low;
...instead, which is even simpler (and then just compare page->free_pages against "min" directly..
Linus