Memory Problem in 2.4.10-pre2 / __alloc_pages failed
Subsystems (2)
Quoted 11 lines · On Fri, 31 Aug 2001 21:03:22 +0200 Daniel Phillips <[email protected]>…
Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +3
-0/* XXX: is pages_min/4 a good amount to reserve for this? */ + if (z->free_pages < z->pages_min / 3 && (gfp_mask & __GFP_WAIT) && + !(current->flags & PF_MEMALLOC)) + continue;Hello Daniel,
I tried this patch and it makes _no_ difference. Failures show up in same situation and amount. Do you need traces? They look the same
OK, first would you confirm that the frequency of 0 order failures has stayed the same?
Hello Daniel (and the rest),
I redid the test and have the following results, based on a 2.4.10-pre2 with above patch:
meminfo before:
Sep 1 15:09:40 admin kernel: SysRq: Show Memory Sep 1 15:09:40 admin kernel: Mem-info: Sep 1 15:09:40 admin kernel: Free pages: 811288kB ( 0kB HighMem) Sep 1 15:09:40 admin kernel: ( Active: 927, inactive_dirty: 9604, inactive_clea n: 0, free: 202822 (383 766 1149) ) Sep 1 15:09:40 admin kernel: 1*4kB 1*8kB 5*16kB 4*32kB 5*64kB 1*128kB 1*256kB 0 *512kB 1*1024kB 6*2048kB = 14236kB) Sep 1 15:09:40 admin kernel: 1*4kB 1*8kB 1*16kB 141*32kB 57*64kB 31*128kB 10*25 6kB 4*512kB 0*1024kB 381*2048kB = 797052kB) Sep 1 15:09:40 admin kernel: = 0kB) Sep 1 15:09:40 admin kernel: Swap cache: add 0, delete 0, find 0/0 Sep 1 15:09:40 admin kernel: Free swap: 265032kB Sep 1 15:09:40 admin kernel: 229376 pages of RAM Sep 1 15:09:40 admin kernel: 0 pages of HIGHMEM Sep 1 15:09:40 admin kernel: 4378 reserved pages Sep 1 15:09:40 admin kernel: 22056 pages shared Sep 1 15:09:40 admin kernel: 0 pages swap cached Sep 1 15:09:40 admin kernel: 0 pages in page table cachSep 1 15:09:40 admin kernel: Buffer memory: 6576kB Sep 1 15:09:40 admin kernel: CLEAN: 1489 buffers, 5935 kbyte, 513 used
(las
t=1489), 0 locked, 0 protected, 0 dirty
total: used: free: shared: buffers: cached:
Mem: 921726976 105066496 816660480 0 6733824 36917248 Swap: 271392768 0 271392768 MemTotal: 900124 kB MemFree: 797520 kB MemShared: 0 kB Buffers: 6576 kB Cached: 36052 kB SwapCached: 0 kB Active: 4076 kB Inact_dirty: 38552 kB Inact_clean: 0 kB Inact_target: 296 kB HighTotal: 0 kB HighFree: 0 kB LowTotal: 900124 kB LowFree: 797520 kB SwapTotal: 265032 kB SwapFree: 265032 kB
(meminfo may slightly differ from SYSREQ, an application (seti) started in between)
The usual test was going on, in the end I had:
meminfo:
Sep 1 15:18:27 admin kernel: SysRq: Show Memory
Sep 1 15:18:27 admin kernel: Mem-info:
Sep 1 15:18:27 admin kernel: Free pages: 3056kB ( 0kB HighMem)
Sep 1 15:18:27 admin kernel: ( Active: 13965, inactive_dirty: 185778,
inactive_clean: 178, free: 764 (383 766 1149) )
Sep 1 15:18:27 admin kernel: 1*4kB 1*8kB 1*16kB 9*32kB 5*64kB 1*128kB 1*256kB
0*512kB 0*1024kB 0*2048kB = 1020kB)
Sep 1 15:18:27 admin kernel: 1*4kB 0*8kB 1*16kB 1*32kB 1*64kB 5*128kB 3*256kB
1*512kB 0*1024kB 0*2048kB = 2036kB)
Sep 1 15:18:27 admin kernel: = 0kB)
Sep 1 15:18:27 admin kernel: Swap cache: add 0, delete 0, find 0/0
Sep 1 15:18:27 admin kernel: Free swap: 265032kB
Sep 1 15:18:27 admin kernel: 229376 pages of RAM
Sep 1 15:18:27 admin kernel: 0 pages of HIGHMEM
Sep 1 15:18:27 admin kernel: 4378 reserved pages
Sep 1 15:18:27 admin kernel: 215286 pages shared
Sep 1 15:18:27 admin kernel: 0 pages swap cached
Sep 1 15:18:27 admin kernel: 0 pages in page table cache
Sep 1 15:18:27 admin kernel: Buffer memory: 15576kB
Sep 1 15:18:27 admin kernel: CLEAN: 178719 buffers, 714855 kbyte, 536 used
(last=178719), 0 locked, 0 protected, 0 dirty
Sep 1 15:18:27 admin kernel: DIRTY: 10060 buffers, 40240 kbyte, 0 used
(last=0), 0 locked, 0 protected, 10060 dirty
S
total: used: free: shared: buffers: cached:
Mem: 921726976 918597632 3129344 0 15958016 802725888
Swap: 271392768 0 271392768
MemTotal: 900124 kB
MemFree: 3056 kB
MemShared: 0 kB
Buffers: 15584 kB
Cached: 783912 kB
SwapCached: 0 kB
Active: 55864 kB
Inact_dirty: 742948 kB
Inact_clean: 684 kB
Inact_target: 8188 kB
HighTotal: 0 kB
HighFree: 0 kB
LowTotal: 900124 kB
LowFree: 3056 kB
SwapTotal: 265032 kB
SwapFree: 265032 kBAnd the traces:
83 mostly identical errors showed up, all looking like
Sep 1 15:17:53 admin kernel: cdda2wav: __alloc_pages: 3-order allocation failed (gfp=0x20/0). Sep 1 15:17:53 admin kernel: Call Trace: [_alloc_pages+22/24] [__get_free_pages+10/28] [<fdcf8826>] [<fdcf88f5>] [<fdcf77d7>] Sep 1 15:17:53 admin kernel: [<fdcf80f5>] [<fdcf6589>] [_alloc_pages+22/24] [__get_free_pages+10/28] [<fdcf8826>] [<fdcf88f5>] Sep 1 15:17:53 admin kernel: [<fdcf76bd>] [filemap_nopage+171/1008] [do_no_page+90/244] [handle_mm_fault+97/192] [<fdcf54aa>] [do_page_fault+0/1164] Sep 1 15:17:53 admin kernel: [dentry_open+189/316] [filp_open+82/92]
[do_fcntl+370/712] [sys_ioctl+443/532] [system_call+51/56]
Trace; fdcf80f5 <[sg]sg_build_reserve+25/48>
Trace; fdcf6589 <[sg]sg_ioctl+6c5/ae4>
Trace; fdcf76bd <[sg]sg_build_indi+55/1a8>
So, there are no 0-order allocs failing in this setup.
Are you content with having no 0-order failures?
I will try to simplify the test to a case that anybody can check out more easily.
Stay tuned.
Regards,
Stephan
Quoted 31 lines · Stephan von Krawczynski
Quoted 11 lines · On Fri, 31 Aug 2001 21:03:22 +0200 Daniel Phillips <[email protected]>…
Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +3
-0/* XXX: is pages_min/4 a good amount to reserve for this? */ + if (z->free_pages < z->pages_min / 3 && (gfp_mask & __GFP_WAIT) && + !(current->flags & PF_MEMALLOC)) + continue;Hello Daniel,
I tried this patch and it makes _no_ difference. Failures show up in same situation and amount. Do you need traces? They look the same
OK, first would you confirm that the frequency of 0 order failures has stayed the same?
Hello Daniel (and the rest),
I redid the test and have the following results, based on a 2.4.10-pre2 with above patch:
[...]And the traces:
83 mostly identical errors showed up, all looking likeSep 1 15:17:53 admin kernel: cdda2wav: __alloc_pages: 3-order allocationfailed (gfp=0x20/0).
[...]
Trace;fdcf80f5<[sg]sg_build_reserve+25/48>
Trace;fdcf6589<[sg]sg_ioctl+6c5/ae4>
Trace;fdcf76bd<[sg]sg_build_indi+55/1a8>
Quoted 3 lines
So, there are no 0-order allocs failing in this setup.
Are you content with having no 0-order failures?
It's a start. The important thing is to have supported my theory of what is going on here. What I did there is probably a good thing, it seems quite effective for combatting 0 order atomic failures. In this case you have a driver that uses a fallback allocation strategy, starting with a 3 order allocation attempt and dropping down top the next lower size on failure. If 0 order allocation fails the whole operation fails, and maybe you will lose a packet. So 0 order allocations are important, we really want them to succeed.
The next part of the theory says that the higher order allocations are failing because of fragmentation. I put considerable thought into this today while wandering around in a dungeon in Berlin watching bats (really) and I will post an article to lkml tomorrow with my findings. To summarize briefly here: a Linux system in steady state operation *is* going to show physical fragmentation so that the chance of a higher order allocation succeeding becomes very small. The chance of failure increases exponentially (or worse) with a) the allocation order and b) the ratio of allocated to free memory. The second of these you can control: the higher you set zone->pages_min the better chance your higher order allocations will have to succeed. Do you want a patch for that, to see if this works in practice?
Of course it would be much better if we had some positive mechanism for defragging physical memory instead of just relying on chance and hoping for the best the way we do now. IMHO, such a mechanism can be built practically and I'm willing to give it a try. Basically, kswapd would try to restore a depleted zone order list by scanning mem_map to find buddy partners for free blocks of the next lower order. This strategy, together with the one used in the patch above, could largly eliminate atomic allocation failures. (Although as I mentioned some time ago, getting rid of them entirely is an impossible problem.)
The question remains why we suddenly started seeing more atomic allocation failures in the recent Linus trees. I'll guess that the changes in scanning strategy have caused the system to spend more time close to the zone->pages_min amount of free memory. This idea seems to be supported by your memstat listings. In some sense, it's been good to have the issue forced so that we must come up with ways to make atomic and higher order allocations less fragile.
--
Daniel
Quoted 15 lines · Daniel Phillips
On September 1, 2001 08:28 pm, Stephan von Krawczynski wrote:
The next part of the theory says that the higher order allocations are failing because of fragmentation. I put considerable thought into this today while wandering around in a dungeon in Berlin watching bats (really) and I will post an article to lkml tomorrow with my findings. To summarize briefly here: a Linux system in steady state operation *is* going to show physical fragmentation so that the chance of a higher order allocation succeeding becomes very small. The chance of failure increases exponentially (or worse) with a) the allocation order and b) the ratio of allocated to free memory. The second of these you can control: the higher you set
zone->pages_minthe better chance your higher order allocations will have to succeed. Do you want a patch for that, to see if this works in practice?
You beat me to it, with some minutes...
(I sent a email to Stephan...)
Quoted 10 lines
Of course it would be much better if we had some positive mechanism for defragging physical memory instead of just relying on chance and hoping for the best the way we do now. IMHO, such a mechanism can be built practically and I'm willing to give it a try. Basically, kswapd would try to restore a depleted zone order list by scanning
mem_mapto find buddy partners for free blocks of the next lower order. This strategy, together with the one used in the patch above, could largly eliminate atomic allocation failures. (Although as I mentioned some time ago, getting rid of them entirely is an impossible problem.)
Quoted 7 lines
The question remains why we suddenly started seeing more atomic allocation failures in the recent Linus trees. I'll guess that the changes in scanning strategy have caused the system to spend more time close to the
zone->pages_minamount of free memory. This idea seems to be supported by your memstat listings. In some sense, it's been good to have the issue forced so that we must come up with ways to make atomic and higher order allocations less fragile.
It might be that the elevator works now... :-)
You will only see it once there are no remaining free pages of an even higher order left - then you will start to fail...
Two things are required:
1) You have lots of memory.
2) You have used it all at some point.
Another thing to do could be to add a order parameter to free. The pages allocated has to be freed sometime... if we make sure that they are freed together it could simplify things - no chance that the first part gets allocated directly...
Or/and we could remove the sources of higher order allocs, as an example:
why is the SCSI layer allowed to allocate order 3 allocs (32 kB) several times per second? Will we really get a performance hit by not allowing higher order allocs in active driver code?
/RogerL
Signature · 3 lines
Roger Larsson Skellefteå Sweden
Quoted 6 lines · Roger Larsson
Quoted 3 lines · Daniel Phillips
In some sense, it's been good to have the issue
forced so that we must come up with ways to make atomic and higher order allocations less fragile.It might be that the elevator works now... :-)
You think it's the elevator? It could be, but scanning policy seems much more likely.
Quoted 5 lines
You will only see it once there are no remaining free pages of an even higher order left - then you will start to fail...
Two things are required:
1) You have lots of memory.
Actually, the situation improves a little as you add memory. I'll show that mathematically tomorrow.
Quoted 1 line
2) You have used it all at some point.
This is the normal case, except for startup and a few special situations such as after heavy file deletion or unmounting a volume.
Quoted 4 lines
Another thing to do could be to add a order parameter to free. The pages allocated has to be freed sometime... if we make sure that they are freed together it could simplify things - no chance that the first part gets allocated directly...
We must be getting a little bit of avoidable fragmentation on freeing, but the real culprit is allocation, which tends to split up higher order allocations rapidly.
Quoted 4 lines
Or/and we could remove the sources of higher order allocs, as an example:
why is the SCSI layer allowed to allocate order 3 allocs (32 kB) several times per second? Will we really get a performance hit by not allowing higher order allocs in active driver code?
Yes, well, if we make it work properly that might not be necessary ;-)
I imagine a lot of higher order allocations could be removed without hurting performance, for example, where dma can handle non-physically-contiguous regions (i.e., scatter/gather). On the other hand, leaving them just the way they are creates more incentive to fix the damn thing, not to mention providing the needed test cases.
--
Daniel
Quoted 4 lines
Or/and we could remove the sources of higher order allocs, as an example:
why is the SCSI layer allowed to allocate order 3 allocs (32 kB) several times per second? Will we really get a performance hit by not allowing higher order allocs in active driver code?
Or put them in some slab like code, the slab for which gets allocated early on when memory is not fragmented, and (nearly) never gets released. Most of the stuff that actually NEEDS atomic allocation (as opposed to some of the requirements that are bogus) are for packets / data in flight. There is probably a finite amount of this at any given time.
--
Alex Bligh
Quoted 7 lines · Alex Bligh - linux-kernel
Quoted 4 lines
Or/and we could remove the sources of higher order allocs, as an example:
why is the SCSI layer allowed to allocate order 3 allocs (32 kB) several times per second? Will we really get a performance hit by not allowing higher order allocs in active driver code?Or put them in some slab like code, the slab for which gets allocated early on when memory is not fragmented, and (nearly) never gets released.
What do you do when a new module gets inserted, increasing the high order load and requiring that the slab be expanded? I.e, the need for dependable handling of high order physical allocations doesn't go away entirely. The slab would help even out the situation with atomic allocs because it can be expanded to a target size by a normal task, which can wait.
Quoted 3 lines
Most of the stuff that actually NEEDS atomic allocation (as opposed to some of the requirements that are bogus) are for packets / data in flight. There is probably a finite amount of this at any given time.
There is no bound, but yes it tends to stay limited to a given, small amount over long periods of time. Hoarding schemes are appropriate. The only problem with slab allocation is, it has more overhead than __alloc_pages allocation. For high-performance networking this may be a measurable hit.
--
Daniel
Daniel,
Quoted 6 lines
What do you do when a new module gets inserted, increasing the high order load and requiring that the slab be expanded? I.e, the need for dependable handling of high order physical allocations doesn't go away entirely. The slab would help even out the situation with atomic allocs because it can be expanded to a target size by a normal task, which can wait.
Yes, chew away to disk as this allocation is non atomic. But this probably still needs something which goes and identifies kernel allocated pages with buddies which can be relocated / pushed to disk / freed etc.;
Alternatively something to temporarilly hold onto 'nearly freed' high-order areas is probably useful. IE if there's an order=3 allocation stuck waiting for a suitable hole, and there's a bit of bitmap that looks like '00010000' (i.e. order 1 hole, order 0 hole, order 0 used, order 2 hole), I wonder if we can't think of some hueristic to avoid allocating the next order 0 page request (atomic or not) from the order 0 hole even if it's at the front of the order (0) free area list.
IDEA: Attempt not to allocate sets of pages buddied with 'nearly free' sets of pages.
When freeing pages, we work our way up the orders until we find a buddy which is non-empty. Let's assume that the free area, and our (non-empty) buddy, are of order N. Let's look at whether at order N-1, it's merely half full, or completely full. If completely full, we guess that the buddy is unlikely to become free soon, and thus add our area to the front of the memory queue (mem_add_head) else we guess it's more likely to have its buddy freed and add it to the back of the memory queue (mem_add_tail).
/Completely/ untested (i.e. uncompiled) patch attached
Quoted 3 lines
The only problem with slab allocation is, it has more overhead than
__alloc_pagesallocation. For high-performance networking this may be a measurable hit.
I meant slab /like/. If all the objects it allocates are the same size, it can't be slower than the buddy allocator. It could be simplified (for instance, drop the cache colouring stuff if that's heavy - everything we allocated is, by definition, much > 1 page in size).
--
Alex Bligh
tmp/page_alloc.c Sun Sep 2 20:28:08 2001 renamed from page_alloc.c Mon Jan 15 20:35:12 2001 +23 -5
@@ -69,6 +69,8 @@ struct page *base; zone_t *zone; + int addfront=1; + if (page->buffers) BUG(); if (page->mapping)
@@ -112,10 +114,22 @@ if (area >= zone->free_area + MAX_ORDER) BUG(); if (!test_and_change_bit(index, area->map)) - /* - * the buddy page is still allocated. - */ - break; + { + /* + * the buddy page is still allocated. + * + * see how many bits are set in its bitmap; + * if 50% or more, we conclude the buddy is + * unlikely to be freed soon, and add the + * area to the head of the queue; else we + * conclude the buddy may be free soon and + * add it to the head. + */ + if (mask & 1) /* not order 0 merge */ + addfront = ( !test_bit((index^1)<<1, (area-1)->map) + && !test_bit((index^1)<<1, (area-1)->map) ); + break; + } /* * Move the buddy up one level. */
@@ -132,7 +146,11 @@ index >>= 1; page_idx &= mask; } - memlist_add_head(&(base + page_idx)->list, &area->free_list); + + if (addfront) + memlist_add_head(&(base + page_idx)->list, &area->free_list); + else + memlist_add_tail(&(base + page_idx)->list, &area->free_list); spin_unlock_irqrestore(&zone->lock, flags);
Quoted 13 lines · Alex Bligh - linux-kernel
IDEA: Attempt not to allocate sets of pages buddied with 'nearly free' sets of pages.
When freeing pages, we work our way up the orders until we find a buddy which is non-empty. Let's assume that the free area, and our (non-empty) buddy, are of order N. Let's look at whether at order N-1, it's merely half full, or completely full. If completely full, we guess that the buddy is unlikely to become free soon, and thus add our area to the front of the memory queue (
mem_add_head) else we guess it's more likely to have its buddy freed and add it to the back of the memory queue (mem_add_tail).
Quoted 1 line
/Completely/ untested (i.e. uncompiled) patch attached
Rediffed to 2.4.9, whitespace and wrapping problems fixed, and compiled but not tested. Now we just need a victi^H^H^H^H^H volunteer to try it... (Stephan?)
mm/page_alloc.c renamed from 2.4.9.clean/mm/page_alloc.c +23 -5
@@ -69,6 +69,8 @@struct page *base;zone_t *zone; +int addfront=1 ; +if (page->buffers)BUG ();if (page->mapping)
@@ -112,10 +114,22 @@if (area >= zone->free_area +MAX_ORDER )BUG ();if (!__test_and_change_bit (index, area->map)) -/* -* the buddy page is still allocated. -*/ -break ; + { +/* +* the buddy page is still allocated. +* +* see how many bits are set in its bitmap; +* if 50% or more, we conclude the buddy is +* unlikely to be freed soon, and add the +* area to the head of the queue; else we +* conclude the buddy may be free soon and +* add it to the head. +*/ +if (mask &1 )/* not order 0 merge */ + addfront = ( !test_bit ((index^1 )<<1 , (area-1 )->map) + && !test_bit ((index^1 )<<1 , (area-1 )->map) ); +break ; + }/* * Move the buddy up one level. */
@@ -132,7 +146,11 @@ index >>=1 ; page_idx &= mask; } -memlist_add_head (&(base + page_idx)->list, &area->free_list); + +if (addfront) +memlist_add_head (&(base + page_idx)->list, &area->free_list); +else +memlist_add_tail (&(base + page_idx)->list, &area->free_list);spin_unlock_irqrestore (&zone->lock, flags);
Quoted 10 lines · Alex Bligh - linux-kernel
Daniel,
Quoted 6 lines
What do you do when a new module gets inserted, increasing the high order load and requiring that the slab be expanded? I.e, the need for dependable handling of high order physical allocations doesn't go away entirely. The slab would help even out the situation with atomic allocs because it can be expanded to a target size by a normal task, which can wait.
Yes, chew away to disk as this allocation is non atomic.
What I meant was, the new module implements a network driver which proceeds to do atomic allocs.
Quoted 4 lines
But this probably still needs something which goes and identifies kernel allocated pages with buddies which can be relocated / pushed to disk / freed etc.;
Quoted 8 lines
Alternatively something to temporarilly hold onto 'nearly freed' high-order areas is probably useful. IE if there's an order=3 allocation stuck waiting for a suitable hole, and there's a bit of bitmap that looks like '00010000' (i.e. order 1 hole, order 0 hole, order 0 used, order 2 hole), I wonder if we can't think of some hueristic to avoid allocating the next order 0 page request (atomic or not) from the order 0 hole even if it's at the front of the order (0) free area list.
One thing I am hearing from some developers is that we don't need to solve the high-order allocation problems because they are really driver issues - all drivers should be changed to use scatter-gather or some such. I don't know if that's correct, this would require knowledge of all driver types and archs which I can't begin to claim.
I'm quite sure we can fix this up though, not to the point of being able to guarantee all high order allocations, but to the point where we have a high probability of success under all loads, as opposed to what we have now which is very fragile, and not just in the Linus tree.
--
Daniel
Review
Quoted 2 lines
(quoted diff) +2
-0+ addfront = ( !test_bit((index^1)<<1, (area-1)->map) + && !test_bit((index^1)<<1,
(area-1) -> map) );
Ooops, that second one should be
Review
Quoted 2 lines
(quoted diff) +2
-0+ && !test_bit((index^1)<<1 | 1, + (area-1) -> map) );
--
Alex Bligh
Daniel,
Quoted 11 lines
Quoted 8 lines
Quoted 6 lines
What do you do when a new module gets inserted, increasing the high order load and requiring that the slab be expanded? I.e, the need for dependable handling of high order physical allocations doesn't go away entirely. The slab would help even out the situation with atomic allocs because it can be expanded to a target size by a normal task, which can wait.
Yes, chew away to disk as this allocation is non atomic.
What I meant was, the new module implements a network driver which proceeds to do atomic allocs.
I think I was agreeing with you, but I think what you meant was that when you load the module, it expands the slab, but with a /non-atomic/ alloc. And what I meant was that as the page reclaim stuff is dumb in terms of recovering buddies of existing pages, it will chew away for a good while until it happens to find a large enough hole. But this isn't really a problem if it happens on module load only.
Quoted 5 lines
One thing I am hearing from some developers is that we don't need to solve the high-order allocation problems because they are really driver issues - all drivers should be changed to use scatter-gather or some such. I don't know if that's correct, this would require knowledge of all driver types and archs which I can't begin to claim.
We have lots of interesting current restrictions, like we assume IP packets are contiguous in memory, and we assume we can allocate their buffers atomically. I suspect there will not be many fans of non-contiguous IP packet models. [Historics: the buddy system was originally introduced to cope with fragments which reassembled to >4k in length, though devices like HSSI with 4470 byte MTU's are going to have the same problem without fragmentation]
No argument that scatter/gather is better if possible & practical (SCSI comes to mind).
--
Alex Bligh
Reposted to include Alex's correction. Alex, could you please check this?
Quoted 13 lines · Alex Bligh - linux-kernel
IDEA: Attempt not to allocate sets of pages buddied with 'nearly free' sets of pages.
When freeing pages, we work our way up the orders until we find a buddy which is non-empty. Let's assume that the free area, and our (non-empty) buddy, are of order N. Let's look at whether at order N-1, it's merely half full, or completely full. If completely full, we guess that the buddy is unlikely to become free soon, and thus add our area to the front of the memory queue (
mem_add_head) else we guess it's more likely to have its buddy freed and add it to the back of the memory queue (mem_add_tail).
Quoted 1 line
/Completely/ untested (i.e. uncompiled) patch attached
Rediffed to 2.4.9, whitespace and wrapping problems fixed, and compiled but not tested. Now we just need a victi^H^H^H^H^H volunteer to try it... (Stephan?)
mm/page_alloc.c renamed from 2.4.9.clean/mm/page_alloc.c +23 -5
@@ -69,6 +69,8 @@struct page *base;zone_t *zone; +int addfront=1 ; +if (page->buffers)BUG ();if (page->mapping)
@@ -112,10 +114,22 @@if (area >= zone->free_area +MAX_ORDER )BUG ();if (!__test_and_change_bit (index, area->map)) -/* -* the buddy page is still allocated. -*/ -break ; + { +/* +* the buddy page is still allocated. +* +* see how many bits are set in its bitmap; +* if 50% or more, we conclude the buddy is +* unlikely to be freed soon, and add the +* area to the head of the queue; else we +* conclude the buddy may be free soon and +* add it to the head. +*/ +if (mask &1 )/* not order 0 merge */ + addfront = ( !test_bit ((index^1 )<<1 , (area-1 )->map) && + !test_bit (((index^1 )<<1 ) |1 , (area-1 )->map) ); +break ; + }/* * Move the buddy up one level. */
@@ -132,7 +146,11 @@ index >>=1 ; page_idx &= mask; } -memlist_add_head (&(base + page_idx)->list, &area->free_list); + +if (addfront) +memlist_add_head (&(base + page_idx)->list, &area->free_list); +else +memlist_add_tail (&(base + page_idx)->list, &area->free_list);spin_unlock_irqrestore (&zone->lock, flags);
Quoted 1 line · --On Sunday, 02 September, 2001 11:23 PM +0200 Daniel Phillips…
Reposted to include Alex's correction. Alex, could you please check this?
Thanks, yep, including () optimisation :-)
Dear volunteer/victim: Last time I looked,
ping -f -s5000 victimip &
ping -f -s10000 victimip &
ping -f -s15000 victimip &
ping -f -s20000 victimip &
ping -f -s25000 victimip &
ping -f -s30000 victimip &
ping -f -s35000 victimip &
while running something buffer intensive (bonnie etc.) tended to do a fair job of exercizing the machine's powers of memory fragmentation / defragmentation; reassembly of IP fragments allocates memory GFP_ATOMIC.
--
Alex Bligh
High order memory allocations (was Re: Memory Problem in 2.4.10-pre2 / __alloc_pages failed)
Next problem / idea:
memory_pressure sets the target for inactive_target (hence free_target etc.)
However, if you do (say) and order 5 allocation, memory pressure is only incremented by 1. This seems illogical, especially given __alloc_pages does not loop via try_again, on order>0 allocations (except
when freeshortage() is true) even if __GFP_WAIT is set (I suspect because it just sits there for ever). In practice, this means page_launder only has one shot at freeing sufficient pages, and this with a wrong inactive target. I propose something like (whitespace broken - sorry):
page_alloc.c Sun Sep 2 23:34:03 2001 renamed from page_alloc.c.keep Sun Sep 2 23:32:56 2001 +2 -2
@@ -141,8 +141,8 @@ * since it's nothing important, but we do want to make sure * it never gets negative. */ - if (memory_pressure > NR_CPUS) - memory_pressure--; + if (memory_pressure > (NR_CPUS << order)) + memory_pressure-= 1<<order;
}
#define MARK_USED(index, order, area) \
@@ -288,7 +288,7 @@
/*
* Allocations put pressure on the VM subsystem.
*/- memory_pressure++;
+ memory_pressure+= 1<<order;
/*
* (If anyone calls gfp from interrupts nonatomically then it
--
Alex Bligh