Large Blocksize Support V7 (adds memmap support)

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

Quoted 10 lines · Christoph Lameter

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit.

I don't know if those people had gone through the
math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

If you don't consider that is a problem because you don't care about theoretical issues or nobody has reported it from running -mm kernels, then I simply can't argue against that on a technical basis.

But I'm totally against introducing known big fundamental problems to the VM at this stage of the kernel. God knows how long it takes to ever fix them in future after they have become pervasive throughout the kernel.

IMO the only thing that higher order pagecache is good for is a quick hack for filesystems to support larger block sizes. And after seeing it is fairly ugly to support mmap, I'm not even really happy for it to do that.

If VM scalability is a problem, then it needs to be addressed in other areas anyway for order-0 pages, and if contiguous pages helps IO scalability or crappy hardware, then there is nothing stopping us from *attempting* to get contiguous memory in the current scheme.

Basically, if you're placing your hopes for VM and IO scalability on this, then I think that's a totally broken thing to do and will end up making the kernel worse in the years to come (except maybe on some poor configurations of bad hardware).

Quoted 12 lines · Nick Piggin

Quoted 10 lines · Christoph Lameter

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The
variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

Quoted 6 lines

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

I thought we had discussed this already at VM and reached something resembling a conclusion. It was acknowledged that depending on contiguous allocations to always succeed will get a caller into trouble and they need to deal with fallback - whether the problem was theoritical or not. It was also strongly pointed out that the large block patches as presented would be vunerable to that problem.

The alternatives were fs-block and increasing the size of order-0. It was felt that fs-block was far away because it's complex and I thought that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's approach in depth.

I *thought* that the end conclusion was that we would go with Christoph's approach pending two things being resolved;

o mmap() support that we agreed on is good

I also thought there was an acknowledgement that long-term, fs-block was the way to go - possibly using contiguous pages optimistically instead of virtual mapping the pages. At that point, it would be a general solution and we could remove the warnings.

Basically, to start out with, this was going to be an SGI-only thing so they get to rattle out the issues we expect to encounter with large blocks and help steer the direction of the more-complex-but-safer-overall fs-block.

Quoted 3 lines

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit.

When that brushing occured, I thought I made it very clear what the expectations were and that without fallback they would be taking a risk. I am not sure if that message actually sank in or not.

Quoted 5 lines

I don't know if those people had gone through the
math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

That's the absolute worst case but yes, in theory this can occur and it's safest to assume the situation will occur somewhere to someone. It would be difficult to craft an attack to do it but conceivably a machine running for a long enough time would trigger it particularly if the large block allocations are GFP_NOIO or GFP_NOFS.

Quoted 4 lines

Basically, if you're placing your hopes for VM and IO scalability on this, then I think that's a totally broken thing to do and will end up making the kernel worse in the years to come (except maybe on some poor configurations of bad hardware).

My magic 8-ball is in the garage.

I thought the following plan was sane but I could be la-la

1. Go with large block + explosions to start with
- Second class feature at this point, not fully supported
- Experiment in different places to see what it gains (if anything)
2. Get fs-block in slowly over time with the fallback options replacing Christophs patches bit by bit
3. Kick away warnings
- First class feature at this point, fully supported

Independently of that, we would work on order-0 scalability, particularly readahead and batching operations on ranges of pages as much as possible.

Quoted 20 lines · Nick Piggin

Quoted 12 lines · Christoph Lameter

Quoted 10 lines

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The
variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

Quoted 6 lines

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

Quoted 6 lines

I thought we had discussed this already at VM and reached something resembling a conclusion. It was acknowledged that depending on contiguous allocations to always succeed will get a caller into trouble and they need to deal with fallback - whether the problem was theoritical or not. It was also strongly pointed out that the large block patches as presented would be vunerable to that problem.

Well Christoph seems to still be spinning them as a solution for VM scalability and first class support for making contiguous IOs, large filesystem block sizes etc.

At the VM summit I think the conclusion was that grouping by mobility could be merged. I'm still not thrilled by that, but I was going to get steamrolled[*] anyway... and seeing as the userspace hugepages is a relatively demanded workload and can be implemented in this way with basically no other changes to the kernel and already must have fallbacks.... then that's actually a reasonable case for it.

The higher order pagecache, again I'm just going to get steamrolled on, and it actually isn't so intrusive minus the mmap changes, so I didn't have much to reasonably say there.

And I would have kept quiet this time too, except for the worrying idea to use higher order pages to fix the SLUB vs SLAB regression, and if the rationale for this patchset was more realistic.

[*] And I don't say steamrolled because I'm bitter and twisted :) I personally want the kernel to be perfect. But I realise it already isn't and for practical purposes people want these things, so I accept being overruled, no problem. The fact simply is -- I would have been steamrolled I think :P

Quoted 5 lines

The alternatives were fs-block and increasing the size of order-0. It was felt that fs-block was far away because it's complex and I thought that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's approach in depth.

Sure. And some people run workloads where fragmentation is likely never going to be a problem, they are shipping this poorly configured hardware now or soon, so they don't have too much interest in doing it right at this point, rather than doing it *now*. OK, that's a valid reason which is why I don't use the argument that we should do it correctly or never at all.

Quoted 5 lines

I *thought* that the end conclusion was that we would go with Christoph's approach pending two things being resolved;

o mmap() support that we agreed on is good

In theory (and again for the filesystem guys who don't have to worry about it). In practice after seeing the patch it's not a nice thing for the VM to have to do.

Quoted 5 lines

I also thought there was an acknowledgement that long-term, fs-block was the way to go - possibly using contiguous pages optimistically instead of virtual mapping the pages. At that point, it would be a general solution and we could remove the warnings.

I guess it is still in the air. I personally think a vmapping approach and/or teaching filesystems to do some nonlinear block metadata access is the way to go (strangely, this happens to be one of the fsblock paradigms!).

OTOH, I'm not sure how much buy-in there was from the filesystems guys. Particularly Christoph H and XFS (which is strange because they already do vmapping in places).

That's understandable though. It is a lot of work for filesystems. But the reason I think it is the correct approach for larger block than soft-page size is that it doesn't have fundamental issues (assuming that virtually mapping the entire kernel is off the table).

Quoted 4 lines

Basically, to start out with, this was going to be an SGI-only thing so they get to rattle out the issues we expect to encounter with large blocks and help steer the direction of the more-complex-but-safer-overall fs-block.

That's what I expected, but it seems from the descriptions in the patches that it is also supposed to cure cancer :)

Quoted 8 lines

Quoted 4 lines

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit.

When that brushing occured, I thought I made it very clear what the expectations were and that without fallback they would be taking a risk. I am not sure if that message actually sank in or not.

No, you have been good about that aspect. I wasn't trying to point to you at all here.

Quoted 11 lines

Quoted 5 lines

I don't know if those people had gone through the
math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

That's the absolute worst case but yes, in theory this can occur and it's safest to assume the situation will occur somewhere to someone. It would be difficult to craft an attack to do it but conceivably a machine running for a long enough time would trigger it particularly if the large block allocations are GFP_NOIO or GFP_NOFS.

It would be interesting to craft an attack. If you knew roughly the layout and size of your dentry slab for example... maybe you could stat a whole lot of files, then open one and keep it open (maybe post the fd to a unix socket or something crazy!) when you think you have filled up a couple of MB worth of them.

Repeat the process until your movable zone is
gone. Or do the same things with pagetables, or task structs, or radix tree nodes, etc.. these are the kinds of things I worry about (as well as just the gradual natural degredation).

Yeah, it might be reasonably possible to make an attack that would deplete most of higher order allocations while pinning somewhat close to just the theoretical minimum required.

[snip]

Thanks Mel. Fairly good summary I think.

Quoted 9 lines

Quoted 4 lines

Basically, if you're placing your hopes for VM and IO scalability on this, then I think that's a totally broken thing to do and will end up making the kernel worse in the years to come (except maybe on some poor configurations of bad hardware).

My magic 8-ball is in the garage.

I thought the following plan was sane but I could be la-la

Quoted 7 lines

1. Go with large block + explosions to start with
- Second class feature at this point, not fully supported
- Experiment in different places to see what it gains (if anything)
2. Get fs-block in slowly over time with the fallback options replacing Christophs patches bit by bit
3. Kick away warnings
- First class feature at this point, fully supported

I guess that was my hope. The only problem I have with a 2nd class higher order pagecache on a *practical* technical issue is introducing more complexity in the VM for mmap. Andrea and Hugh are probably more guardians of that area of code than I, so if they're happy with the mmap stuff then again I can accept being overruled on this ;)

Then I would love to say #2 will go ahead (and I hope it would), but I can't force it down the throat of the filesystem maintainers just like I feel they can't force vm devs (me) to do a virtually mapped and defrag-able kernel :) Basically I'm trying to practice what I preach and I don't want to force fsblock onto anyone.

Maybe when ext2 is converted and if I can show it isn't a performance problem / too much complexity then I'll have another leg to stand on here... I don't know.

Quoted 3 lines

Independently of that, we would work on order-0 scalability, particularly readahead and batching operations on ranges of pages as much as possible.

Definitely. Also, aops capable of spanning multiple pages, batching of large write(2) pagecache insertion, etc all are things we must go after, regardless of the large page and/or block size work.

On (11/09/07 11:44), Nick Piggin didst pronounce:

However, this discussion belongs more with the non-existant-remove-slab patch. Based on what we've seen since the summits, we need a thorough analysis with benchmarks before making a final decision (kernbench, ebizzy, tbench (netpipe if someone has the time/resources), hackbench and maybe sysbench as well as something the filesystem people recommend to get good coverage of the subsystems).

I'd rather not get side-tracked here. I regret you feel stream-rolled but I think grouping pages by mobility is the right thing to do for better usage of the TLB by the kernel and for improving hugepage support in userspace minimally. We never really did see eye-to-eye but this way, if I'm wrong you get to chuck eggs down the line.

Quoted 6 lines

Sure. And some people run workloads where fragmentation is likely never going to be a problem, they are shipping this poorly configured hardware now or soon, so they don't have too much interest in doing it right at this point, rather than doing it *now*. OK, that's a valid reason which is why I don't use the argument that we should do it correctly or never at all.

So are we saying the right thing to do is go with fs-block from day 1 once we get it to optimistically use high-order pages? I think your concern might be that if this goes in then it'll be harder to justify fsblock in the future because it'll be solving a theoritical problem that takes months to trigger if at all. i.e. The filesystem people will push because apparently large block support as it is solves world peace. Is that accurate?

Quoted 3 lines

OTOH, I'm not sure how much buy-in there was from the filesystems guys. Particularly Christoph H and XFS (which is strange because they already do vmapping in places).

I think they use vmapping because they have to, not because they want to. They might be a lot happier with fsblock if it used contiguous pages for large blocks whenever possible - I don't know for sure. The metadata accessors they might be unhappy with because it's inconvenient but as Christoph Hellwig pointed out at VM/FS, the filesystems who really care will convert.

Quoted 5 lines

It would be interesting to craft an attack. If you knew roughly the layout and size of your dentry slab for example... maybe you could stat a whole lot of files, then open one and keep it open (maybe post the fd to a unix socket or something crazy!) when you think you have filled up a couple of MB worth of them.

I might regret saying this, but it would be easier to craft an attack using pagetable pages. It's woefully difficult to do but it's probably doable. I say pagetables because while slub targetted reclaim is on the cards and memory compaction exists for page cache pages, pagetables are currently pinned with no prototype patch existing to deal with them.

Quoted 5 lines

Then I would love to say #2 will go ahead (and I hope it would), but I can't force it down the throat of the filesystem maintainers just like I feel they can't force vm devs (me) to do a virtually mapped and defrag-able kernel :) Basically I'm trying to practice what I preach and I don't want to force fsblock onto anyone.

If the FS people really want it and they insist that this has to be a #1 citizen then it's fsblock or make something new up.

But that's not my place to say, and I'm actually not arguing that high order pagecache does not have uses (especially as a practical, shorter-term solution which is unintrusive to filesystems).

So no, I don't think I'm really going against the basics of what we agreed in Cambridge. But it sounds like it's still being billed as first-order support right off the bat here.

But even so, you can just hold an open fd in order to pin the dentry you want. My attack would go like this: get the page size and allocation group size for the machine, then get the number of dentries required to fill a slab. Then read in that many dentries and pin one of them. Repeat the process. Even if there is other activity on the system, it seems possible that such a thing will cause some headaches after not too long a time. Some sources of pinned memory are going to be better than others for this of course, so yeah maybe pagetables will be a bit easier (I don't know).

Quoted 5 lines

But that's not my place to say, and I'm actually not arguing that high order pagecache does not have uses (especially as a practical, shorter-term solution which is unintrusive to filesystems).

Quoted 3 lines

So no, I don't think I'm really going against the basics of what we agreed in Cambridge. But it sounds like it's still being billed as first-order support right off the bat here.

Well its seems that we have different interpretations of what was agreed on. My understanding was that the large blocksize patchset was okay provided that I supply an acceptable mmap implementation and put a warning in.

Quoted 8 lines

But even so, you can just hold an open fd in order to pin the dentry you want. My attack would go like this: get the page size and allocation group size for the machine, then get the number of dentries required to fill a slab. Then read in that many dentries and pin one of them. Repeat the process. Even if there is other activity on the system, it seems possible that such a thing will cause some headaches after not too long a time. Some sources of pinned memory are going to be better than others for this of course, so yeah maybe pagetables will be a bit easier (I don't know).

Well even without slab targeted reclaim: Mel's antifrag will sort the dentries into separate blocks of memory and so isolate the issue.

Quoted 4 lines · Nick Piggin

But that's not my place to say, and I'm actually not arguing that high order pagecache does not have uses (especially as a practical, shorter-term solution which is unintrusive to filesystems).

Quoted 3 lines

So no, I don't think I'm really going against the basics of what we agreed in Cambridge. But it sounds like it's still being billed as first-order support right off the bat here.

Well its seems that we have different interpretations of what was agreed on. My understanding was that the large blocksize patchset was okay provided that I supply an acceptable mmap implementation and put a warning in.

Quoted 9 lines

But even so, you can just hold an open fd in order to pin the dentry you want. My attack would go like this: get the page size and allocation group size for the machine, then get the number of dentries required to fill a slab. Then read in that many dentries and pin one of them. Repeat the process. Even if there is other activity on the system, it seems possible that such a thing will cause some headaches after not too long a time. Some sources of pinned memory are going to be better than others for this of course, so yeah maybe pagetables will be a bit easier (I don't know).

Well even without slab targeted reclaim: Mel's antifrag will sort the dentries into separate blocks of memory and so isolate the issue.

Quoted 4 lines

Well its seems that we have different interpretations of what was agreed on. My understanding was that the large blocksize patchset was okay provided that I supply an acceptable mmap implementation and put a warning in.

Yes. I think we differ on our interpretations of "okay". In my interpretation, it is not OK to use this patch as a way to solve VM or FS or IO scalability issues, especially not while the alternative approaches that do _not_ have these problems have not been adequately compared or argued against.

Quoted 2 lines

Well even without slab targeted reclaim: Mel's antifrag will sort the dentries into separate blocks of memory and so isolate the issue.

So even after all this time you do not understand what the fundamental problem is with anti-frag and yet you are happy to waste both our time in endless flamewars telling me how wrong I am about it.

Forgive me if I'm starting to be rude, Christoph. This is really irritating.

Quoted 5 lines · Nick Piggin

Yes. I think we differ on our interpretations of "okay". In my interpretation, it is not OK to use this patch as a way to solve VM or FS or IO scalability issues, especially not while the alternative approaches that do _not_ have these problems have not been adequately compared or argued against.

We never talked about not being able to solve scalability issues with this patchset. The alternate approaches were discussed at the VM MiniSummit and at the VM/FS meeting. You organized the VM/FS summit. I know you were there and were arguing for your approach. That was not sufficient?

Quoted 3 lines

So even after all this time you do not understand what the fundamental problem is with anti-frag and yet you are happy to waste both our time in endless flamewars telling me how wrong I am about it.

We obviously have discussed this before and the only point of asking this question by you seems to be to have me repeat the whole line argument again?

Quoted 2 lines

Forgive me if I'm starting to be rude, Christoph. This is really irritating.

Sorry but I have had too much exposure to philosophy. Talk about absolutes like guarantees (that do not exist even for order 0 allocs) and unlikely memory fragmentation scenarios to show that something does not work seems to be getting into some metaphysical realm where there is no data anymore to draw any firm conclusions.

Software reliability is inherent probabilistic otherwise we would not have things like CRC sums and SHA1 algorithms. Its just a matter of reducing the failure rate sufficiently. The failure rate for lower order allocations (0-3) seems to have been significantly reduced in 2.6.23 through lumpy reclaim.

If antifrag measures are not successful (likely for 2M allocs) then other methods (like the large page pools that you skipped when reading my post) will need to be used.

I will still argue that my approach is the better technical solution for large block support than yours, I don't think we made progress on that. And I'm quite sure we agreed at the VM summit not to rely on your patches for VM or IO scalability.

But you just showed in two emails that you don't understand what the problem is. To reiterate: lumpy reclaim does *not* invalidate my formulae; and antifrag does *not* isolate the issue.

But what do you say about viable alternatives that do not have to worry about these "unlikely scenarios", full stop? So, why should we not use fs block for higher order page support?

I didn't skip that. We have large page pools today. How does that give first class of support to those allocations if you have to have memory reserves?

Quoted 5 lines

I will still argue that my approach is the better technical solution for large block support than yours, I don't think we made progress on that. And I'm quite sure we agreed at the VM summit not to rely on your patches for VM or IO scalability.

The approach has already been tried (see the XFS layer) and found lacking.

Having a fake linear block through vmalloc means that a special software layer must be introduced and we may face special casing in the block / fs layer to check if we have one of these strange vmalloc blocks.

Quoted 3 lines

But you just showed in two emails that you don't understand what the problem is. To reiterate: lumpy reclaim does *not* invalidate my formulae; and antifrag does *not* isolate the issue.

I do understand what the problem is. I just do not get what your problem with this is and why you have this drive to demand perfection. We are working a variety of approaches on the (potential) issue but you categorically state that it cannot be solved.

Quoted 3 lines

But what do you say about viable alternatives that do not have to worry about these "unlikely scenarios", full stop? So, why should we not use fs block for higher order page support?

Because it has already been rejected in another form and adds more layering to the filesystem and more checking for special cases in which we only have virtual linearity? It does not reduce the number of page structs that have to be handled by the lower layers etc.

Maybe we coud get to something like a hybrid that avoids some of these issues?

Add support so something like a virtual compound page can be handled transparently in the filesystem layer with special casing if such a beast reaches the block layer?

Quoted 3 lines

I didn't skip that. We have large page pools today. How does that give first class of support to those allocations if you have to have memory reserves?

See my other mail. That portion is not complete yet. Sorry.

Surely, we'll be able to detect the situation where the memory is really contiguous as a fast path and have a slower path where fragmentation was a problem.

The only implementation question about these patches that hasn't been addressed is the mmap() support. What's wrong with it in it's current form. Can it be fixed or if it's fundamentally screwed etc. That has fallen by the wayside.

I am *very* wary of using reserve pools for anything other than emergency situations. If nothing else pools == wasted memory + a sizing problem. But hey, it is one option.

Are we going to agree on some sort of plan or are we just going to handwave ourselves to death?

Quoted 4 lines · Nick Piggin

I will still argue that my approach is the better technical solution for large block support than yours, I don't think we made progress on that. And I'm quite sure we agreed at the VM summit not to rely on your patches for VM or IO scalability.

The approach has already been tried (see the XFS layer) and found lacking.

Having a fake linear block through vmalloc means that a special software layer must be introduced and we may face special casing in the block / fs layer to check if we have one of these strange vmalloc blocks.

Quoted 3 lines

But you just showed in two emails that you don't understand what the problem is. To reiterate: lumpy reclaim does *not* invalidate my formulae; and antifrag does *not* isolate the issue.

I do understand what the problem is. I just do not get what your problem with this is and why you have this drive to demand perfection. We are

working a variety of approaches on the (potential) issue but you categorically state that it cannot be solved.

Quoted 3 lines

But what do you say about viable alternatives that do not have to worry about these "unlikely scenarios", full stop? So, why should we not use fs block for higher order page support?

Because it has already been rejected in another form and adds more

Maybe we coud get to something like a hybrid that avoids some of these issues? Add support so something like a virtual compound page can be handled transparently in the filesystem layer with special casing if such a beast reaches the block layer?

However fsblock can do everything that higher order pagecache can do in terms of avoiding vmap and giving contiguous memory to block devices by opportunistically allocating higher orders of pages, and falling back to vmap if they cannot be satisfied.

So if you argue that vmap is a downside, then please tell me how you consider the -ENOMEM of your approach to be better?

If, by special software layer, you mean the vmap/vunmap support in fsblock, let's see... that's probably all of a hundred or two lines. Contrast that with anti-fragmentation, lumpy reclaim, higher order pagecache and its new special mmap layer... Hmm, seems like a no brainer to me. You really still want to persue the "extra layer" argument as a point against fsblock here?

Of course I wouldn't state that. On the contrary, I categorically state that I have already solved it :)

Quoted 1 line

Because it has already been rejected in another form and adds more

You have rejected it. But they are bogus reasons, as I showed above.

You also describe some other real (if lesser) issues like number of page structs to manage in the pagecache. But this is hardly enough to reject my patch now... for every downside you can point out in my approach, I can point out one in yours.

- fsblock doesn't require changes to virtual memory layer

Quoted 4 lines

Maybe we coud get to something like a hybrid that avoids some of these issues? Add support so something like a virtual compound page can be handled transparently in the filesystem layer with special casing if such a beast reaches the block layer?

That's conceptually much worse, IMO.

And practically worse as well: vmap space is limited on 32-bit; fsblock approach can avoid vmap completely in many cases; for two reasons.

The fsblock data accessor APIs aren't _that_ bad changes. They change zero conceptually in the filesystem, are arguably cleaner, and can be essentially nooped if we wanted to stay with a b_data type approach (but they give you that flexibility to replace it with any implementation).

an -ENOMEM. Given the quantities of pages on todays machine--a 1 G machine

has 256 milllion 4k pages--and the unmovable ratios we see today it

Quoted 1 line · Christoph Lameter

an -ENOMEM. Given the quantities of pages on todays machine--a 1 G machine

s/1G/1T/ Sigh.

Quoted 1 line

has 256 milllion 4k pages--and the unmovable ratios we see today it

256k for 1G.

Quoted 4 lines · Nick Piggin

However fsblock can do everything that higher order pagecache can do in terms of avoiding vmap and giving contiguous memory to block devices by opportunistically allocating higher orders of pages, and falling back to vmap if they cannot be satisfied.

fsblock is restricted to the page cache and cannot be used in other contexts where subsystems can benefit from larger linear memory.

Quoted 2 lines

So if you argue that vmap is a downside, then please tell me how you consider the -ENOMEM of your approach to be better?

That is again pretty undifferentiated. Are we talking about low page

orders? There we will reclaim the all of reclaimable memory before getting an -ENOMEM. Given the quantities of pages on todays machine--a 1 G machine has 256 milllion 4k pages--and the unmovable ratios we see today it would require a very strange setup to get an allocation failure while still be able to allocate order 0 pages.

With the ZONE_MOVABLE you can remove the unmovable objects into a defined pool then higher order success rates become reasonable.

Quoted 6 lines

If, by special software layer, you mean the vmap/vunmap support in fsblock, let's see... that's probably all of a hundred or two lines. Contrast that with anti-fragmentation, lumpy reclaim, higher order pagecache and its new special mmap layer... Hmm, seems like a no brainer to me. You really still want to persue the "extra layer" argument as a point against fsblock here?

Yes sure. You code could not live without these approaches. Without the

antifragmentation measures your fsblock code would not be very successful in getting the larger contiguous segments you need to improve performance.

(There is no new mmap layer, the higher order pagecache is simply the old API with set_blocksize expanded).

Quoted 2 lines

Of course I wouldn't state that. On the contrary, I categorically state that I have already solved it :)

Well then I guess that you have not read the requirements...

Quoted 3 lines

Quoted 1 line

Because it has already been rejected in another form and adds more

You have rejected it. But they are bogus reasons, as I showed above.

Thats not me. I am working on this because many of the filesystem people have repeatedly asked me to do this. I am no expert on filesystems.

Quoted 6 lines

You also describe some other real (if lesser) issues like number of page structs to manage in the pagecache. But this is hardly enough to reject my patch now... for every downside you can point out in my approach, I can point out one in yours.

- fsblock doesn't require changes to virtual memory layer

Therefore it is not a generic change but special to the block layer. So other subsystems still have to deal with the single page issues on their own.

Quoted 6 lines

Quoted 4 lines

Maybe we coud get to something like a hybrid that avoids some of these issues? Add support so something like a virtual compound page can be handled transparently in the filesystem layer with special casing if such a beast reaches the block layer?

That's conceptually much worse, IMO.

Why: It is the same approach that you use.

If it is barely ever used and
satisfies your concern then I am fine with it.

Quoted 8 lines

And practically worse as well: vmap space is limited on 32-bit; fsblock approach can avoid vmap completely in many cases; for two reasons.

The fsblock data accessor APIs aren't _that_ bad changes. They change zero conceptually in the filesystem, are arguably cleaner, and can be essentially nooped if we wanted to stay with a b_data type approach (but they give you that flexibility to replace it with any implementation).

The largeblock changes are generic.

They improve general handling of
compound pages, they make the existing APIs work for large units of memory, they are not adding additional new API layers.

Quoted 4 lines

Quoted 2 lines

So if you argue that vmap is a downside, then please tell me how you consider the -ENOMEM of your approach to be better?

That is again pretty undifferentiated. Are we talking about low page

In general.

Quoted 2 lines

With the ZONE_MOVABLE you can remove the unmovable objects into a defined pool then higher order success rates become reasonable.

OK, if you rely on reserve pools, then it is not 1st class support and hence it is a non-solution to VM and IO scalability problems.

Quoted 8 lines

Quoted 6 lines

If, by special software layer, you mean the vmap/vunmap support in fsblock, let's see... that's probably all of a hundred or two lines. Contrast that with anti-fragmentation, lumpy reclaim, higher order pagecache and its new special mmap layer... Hmm, seems like a no brainer to me. You really still want to persue the "extra layer" argument as a point against fsblock here?

Yes sure. You code could not live without these approaches. Without the

Actually: your code is the one that relies on higher order allocations. Now you're trying to turn that into an argument against fsblock?

Quoted 2 lines

antifragmentation measures your fsblock code would not be very successful in getting the larger contiguous segments you need to improve performance.

Complely wrong. *I* don't need to do any of that to improve performance. Actually the VM is well tuned for order-0 pages, and so seeing as I have sane hardware, 4K pagecache works beautifully for me.

Quoted 2 lines

(There is no new mmap layer, the higher order pagecache is simply the old API with set_blocksize expanded).

Yes you add another layer in the userspace mapping code to handle higher order pagecache.

Quoted 1 line

Why: It is the same approach that you use.

Again, rubbish.

Quoted 6 lines · Nick Piggin

Quoted 4 lines

Quoted 2 lines

So if you argue that vmap is a downside, then please tell me how you consider the -ENOMEM of your approach to be better?

That is again pretty undifferentiated. Are we talking about low page

In general.

There is no -ENOMEM approach. Lower order page allocation (< PAGE_ALLOC_COSTLY_ORDER) will reclaim and in the worst case the OOM killer will be activated.

That is the nature of the failures that we saw early in the year when this was first merged into mm.

Quoted 3 lines

Quoted 2 lines

With the ZONE_MOVABLE you can remove the unmovable objects into a defined pool then higher order success rates become reasonable.

Quoted 2 lines

OK, if you rely on reserve pools, then it is not 1st class support and hence it is a non-solution to VM and IO scalability problems.

ZONE_MOVABLE creates two memory pools in a machine. One of them is for movable and one for unmovable. That is in 2.6.23. So 2.6.23 has no first call support for order 0 pages?

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

If, by special software layer, you mean the vmap/vunmap support in fsblock, let's see... that's probably all of a hundred or two lines. Contrast that with anti-fragmentation, lumpy reclaim, higher order pagecache and its new special mmap layer... Hmm, seems like a no brainer to me. You really still want to persue the "extra layer" argument as a point against fsblock here?

Quoted 4 lines

Quoted 1 line

Yes sure. You code could not live without these approaches. Without the

Actually: your code is the one that relies on higher order allocations. Now you're trying to turn that into an argument against fsblock?

fsblock also needs contiguous pages in order to have a beneficial effect that we seem to be looking for.

Quoted 7 lines

Quoted 3 lines

antifragmentation measures your fsblock code would not be very successful in getting the larger contiguous segments you need to improve performance.

Complely wrong. *I* don't need to do any of that to improve performance. Actually the VM is well tuned for order-0 pages, and so seeing as I have sane hardware, 4K pagecache works beautifully for me.

Sure the system works fine as is. Not sure why we would need fsblock then.

Quoted 5 lines

Quoted 2 lines

(There is no new mmap layer, the higher order pagecache is simply the old API with set_blocksize expanded).

Yes you add another layer in the userspace mapping code to handle higher order pagecache.

That would imply a new API or something? I do not see it.

Quoted 3 lines

Quoted 1 line

Why: It is the same approach that you use.

Again, rubbish.

Ok the logical conclusion from the above is that you think your approach is rubbish....

Is there some way you could cool down a bit?

ROFL! Yeah of course, how could I have forgotten about our trusty OOM killer as the solution to the fragmentation problem? It would only have been funnier if you had said to reboot every so often when memory gets fragmented :)

The fact is, *none* of those things are true. The VM doesn't guarantee anything, and is already very much about statistics in many places. You

Many? I can't recall anything besides PF_MEMALLOC and the decision that the VM is oom.

In general every time reliability has a low priority than performance I've an hard time to enjoy it.

This is not about performance. Never has been. It's about SGI wanting a way out of their current 16kB mess.

The way to fix performance is to move to x86-64, and use 4kB pages and be happy. However, the SGI people want a 16kB (and possibly bigger) crap-option for their people who are (often _already_) running some special case situation that nobody else cares about.

It's not about "performance". If it was, they would never have used ia64

FWIW (and I hate to let reality get in the way of a good conspiracy) - all SGI systems have always defaulted to using 4K blocksize filesystems;

there's very few customers who would use larger

especially as the Linux
kernel limitations in this area are well known. There's no "16K mess" that SGI is trying to clean up here (and SGI have offered both IA64 and x86_64 systems for some time now, so not sure how you came up with that whacko theory).

There is *no* valid reason for 16kB blocksizes unless you have legacy issues.

The performance issues have nothing to do with the block-size, and

should be solvable by just making sure that your stupid "state of the art"
crap SCSI controller gets contiguous physical memory, which is best done
in the read-ahead code.

Quoted 5 lines

especially as the Linux
kernel limitations in this area are well known. There's no "16K mess" that SGI is trying to clean up here (and SGI have offered both IA64 and x86_64 systems for some time now, so not sure how you came up with that whacko theory).

Well, if that is the case, then I vote that we drop the whole patch-series entirely. It clearly has no reason for existing at all.

There is *no* valid reason for 16kB blocksizes unless you have legacy issues.

So get your stories straight, people.

The problem is this: to alter the fundamental block size of the filesystem we also need to alter the data block size and that is exactly the piece that linux does not support right now. So while we have the capability to use large block sizes in certain filesystems, we can't use that capability until the data path supports it.

Ok, let's step back for a moment and look at a basic, fundamental constraint of disks - seek capacity. A decade ago, a terabyte of filesystem had 30 disks behind it - a seek capacity of about 6000 seeks/s. Nowdays, that's a single disk with a seek capacity of about 200/s. We're going *rapidly* backwards in terms of seek capacity per terabyte of storage.

Now fill that terabyte of storage and index it in the most efficient way - let's say btrees are used because lots of filesystems use them. Hence the depth of the tree is roughly O((log n)/m) where m is a factor of the btree block size. Effectively, btree depth = seek count on lookup of any object.

Ok, so let's set the record straight. There were 3 justifications for using *large pages* to *support* large filesystem block sizes The justifications for the variable order page cache with large pages were:

	1. little code change needed in the filesystems
		-> still true

3. avoiding the need for vmap() as it has great overhead and does not scale
-> Nick is starting to work on that and has
already had good results.

Everyone seems to be focussing on #2 as the entire justification for large block sizes in filesystems and that this is an "SGI" problem.

Quoted 7 lines · David Chinner

Ok, let's step back for a moment and look at a basic, fundamental constraint of disks - seek capacity. A decade ago, a terabyte of filesystem had 30 disks behind it - a seek capacity of about 6000 seeks/s. Nowdays, that's a single disk with a seek capacity of about 200/s. We're going *rapidly* backwards in terms of seek capacity per terabyte of storage.

Quoted 5 lines

Now fill that terabyte of storage and index it in the most efficient way - let's say btrees are used because lots of filesystems use them. Hence the depth of the tree is roughly O((log n)/m) where m is a factor of the btree block size. Effectively, btree depth = seek count on lookup of any object.

I agree. btrees will clearly benefit if the nodes are larger. We've an excess of disk capacity and an huge gap between seeking and contiguous bandwidth.

You don't need largepages for this, fsblocks is enough.

Plus of course you don't like fsblock because it requires work to adapt a fs to it, I can't argue about that.

Quoted 7 lines

Ok, so let's set the record straight. There were 3 justifications for using *large pages* to *support* large filesystem block sizes The justifications for the variable order page cache with large pages were:

	1. little code change needed in the filesystems
		-> still true

Disagree, the mmap side is not a little change.

Quoted 4 lines

3. avoiding the need for vmap() as it has great overhead and does not scale
-> Nick is starting to work on that and has
already had good results.

Frankly I don't follow this vmap thing. Can you elaborate?

Quoted 2 lines

Everyone seems to be focussing on #2 as the entire justification for large block sizes in filesystems and that this is an "SGI" problem.

I agree it's not a SGI problem and this is why I want a design that has a _slight chance_ to improve performance on x86-64 too. If variable order page cache will provide any further improvement on top of fsblock will be only because your I/O device isn't fast with small sg entries.

config-page-shift + fsblock IMHO is the way to go for x86-64, with one additional 64k PAGE_SIZE rpm. config-page-shift will stack nicely on top of fsblocks.

Sure, and that's what I meant when I said VPC + large pages was a means to the end, not the only solution to the problem.

No, I don't like fsblock because it is inherently a "struture per filesystem block" construct, just like buggerheads. You still need to allocate millions of them when you have millions dirty pages around. Rather than type it all out again, read the fsblocks thread from here:

http://marc.info/?l=linux-fsdevel&m=118284983925719&w=2

FWIW, with Chris mason's extent-based block mapping (which btrfs is using and Christoph Hellwig is porting XFS over to) we completely remove buggerheads from XFS and so fsblock would be a pretty major step backwards for us if Chris's work goes into mainline.

That's not in the filesystem, though. ;)

However, I agree that if you don't have mmap then it's not worthwhile and the changes for VPC aren't trivial.

Quoted 7 lines

Quoted 5 lines

3. avoiding the need for vmap() as it has great overhead and does not scale
-> Nick is starting to work on that and has
already had good results.

Frankly I don't follow this vmap thing. Can you elaborate?

We current support metadata blocks larger than page size for certain types of metadata in XFS. e.g. directory blocks. This however, requires vmap()ing a bunch of individual, non-contiguous pages out of a block device address space in exactly the fashion that was proposed by Nick with fsblock originally.

vmap() has severe scalability problems - read this subthread of this discussion between Nick and myself:

http://lkml.org/lkml/2007/9/11/508

Hmm - so you'll need page cache tail packing as well in that case to prevent memory being wasted on small files. That means any way we look at it (VPC+mmap or config-page-shift+fsblock+pctails) we've got some non-trivial VM modifications to make.

But, I'm not going to argue endlessly for one solution or another; I'm happy to see different solutions being chased, so may the best VM win ;)

The only point of this largepage stuff is to go an extra mile to save a bit more of cpu vs a strict vmap based solution (fsblock of course will be smart enough that if it notices the PAGE_SIZE is >= blocksize it doesn't need to run any vmap at all and it can just use the direct mapping, so vmap translates in 1 branch only to check the blocksize variable, PAGE_SIZE is immediate in the .text at compile time). But if

Quoted 1 line

Disagree, the mmap side is not a little change.

That's not in the filesystem, though. ;)

Quoted 3 lines · David Chinner

Quoted 1 line

Disagree, the mmap side is not a little change.

That's not in the filesystem, though. ;)

And its really only a minimal change for some function to loop over all 4k pages and elsewhere index the right 4k subpage.

I've found some fixes needed on top of your Large Blocksize Support
patches: I'll send those to you in a moment. Looks like you didn't try much swapping!

I only managed to get ext2 working with larger blocksizes:
reiserfs -b 8192 wouldn't mount ("reiserfs_fill_super: can not find reiserfs on /dev/sdb1"); ext3 gave me mysterious errors ("JBD: tar wants too many credits", even after adding JBD patches that you turned out to be depending on); and I didn't try ext4 or xfs (I'm guessing the latter has been quite well tested ;)

Quoted 2 lines · Andrea Arcangeli

Plus of course you don't like fsblock because it requires work to adapt a fs to it, I can't argue about that.

No, I don't like fsblock because it is inherently a "struture per filesystem block" construct, just like buggerheads. You still need to allocate millions of them when you have millions dirty pages around. Rather than type it all out again, read the fsblocks thread from here:

http://marc.info/?l=linux-fsdevel&m=118284983925719&w=2

FWIW, with Chris mason's extent-based block mapping (which btrfs is using and Christoph Hellwig is porting XFS over to) we completely remove buggerheads from XFS and so fsblock would be a pretty major step backwards for us if Chris's work goes into mainline.

But, I'm not going to argue endlessly for one solution or another; I'm happy to see different solutions being chased, so may the best VM win ;)

Nobody sane would *ever* argue for 16kB+ blocksizes in general.

Well, not so sure about that. What if one of your expected uses for example is video data storage -- lots of data, especially for multiple streams, and needs still relatively fast machinery. Why would you care for the overhead af _small_ blocks?

Quoted 4 lines · Rene Herman

Well, not so sure about that. What if one of your expected uses for example is video data storage -- lots of data, especially for multiple streams, and needs still relatively fast machinery. Why would you care for the overhead af _small_ blocks?

.. so work with an extent-based filesystem instead.

16k blocks are total idiocy. If this wasn't about a "support legacy customers", I think the whole patch-series has been a total waste of time.

I do feel larger blocksizes continue to make sense in general though. Packet writing on CD/DVD is a problem already today since the hardware needs 32K or 64K blocks and I'd expect to see more of these and similiar situations when flash gets (even) more popular which it sort of inevitably is going to be.

Quoted 4 lines · Rene Herman

I do feel larger blocksizes continue to make sense in general though. Packet writing on CD/DVD is a problem already today since the hardware needs 32K or 64K blocks and I'd expect to see more of these and similiar situations when flash gets (even) more popular which it sort of inevitably is going to be.

.. that's what scatter-gather exists for.

What's so hard with just realizing that physical memory isn't contiguous?

It's why we have MMU's. It's why we have scatter-gather.

Quoted 4 lines · Nick Piggin

ROFL! Yeah of course, how could I have forgotten about our trusty OOM killer as the solution to the fragmentation problem? It would only have been funnier if you had said to reboot every so often when memory gets fragmented :)

Can we please stop this *idiotic* thread.

Nick, you and some others seem to be arguing based on a totally flawed base, namely:
- we can guarantee anything at all in the VM
- we even care about the 16kB blocksize
- second-class citizenry is "bad"

The fact is, *none* of those things are true. The VM doesn't guarantee anything, and is already very much about statistics in many places. You seem to be arguing as if Christoph was introducing something new and unacceptable, when it's largely just more of the same.

And the fact is, nobody but SGI customers would ever want the 16kB blocksize. IOW - NONE OF THIS MATTERS!

Can you guys stop this inane thread already, or at least take it private between you guys, instead of forcing everybody else to listen in on your flamefest.

Quoted 7 lines · Nick Piggin

But that's not my place to say, and I'm actually not arguing that high order pagecache does not have uses (especially as a practical, shorter-term solution which is unintrusive to filesystems).

So no, I don't think I'm really going against the basics of what we agreed in Cambridge. But it sounds like it's still being billed as first-order support right off the bat here.

Well its seems that we have different interpretations of what was agreed on. My understanding was that the large blocksize patchset was okay provided that I supply an acceptable mmap implementation and put a warning in.

Quoted 10 lines

Quoted 3 lines

OTOH, I'm not sure how much buy-in there was from the filesystems guys. Particularly Christoph H and XFS (which is strange because they already do vmapping in places).

I think they use vmapping because they have to, not because they want to. They might be a lot happier with fsblock if it used contiguous pages for large blocks whenever possible - I don't know for sure. The metadata accessors they might be unhappy with because it's inconvenient but as Christoph Hellwig pointed out at VM/FS, the filesystems who really care will convert.

Sure, they would rather not to. But there are also a lot of ways you can improve vmap more than what XFS does (or probably what darwin does) (more persistence for cached objects, and batched invalidates for example).

There are also a lot of trivial things you can do to make a lot of those accesses not require vmaps (and less trivial things, but even such things as binary searches over multiple pages should be quite possible with a bit of logic).

Quoted 11 lines · Nick Piggin

Quoted 10 lines

Quoted 3 lines

OTOH, I'm not sure how much buy-in there was from the filesystems guys. Particularly Christoph H and XFS (which is strange because they already do vmapping in places).

I think they use vmapping because they have to, not because they want to. They might be a lot happier with fsblock if it used contiguous pages for large blocks whenever possible - I don't know for sure. The metadata accessors they might be unhappy with because it's inconvenient but as Christoph Hellwig pointed out at VM/FS, the filesystems who really care will convert.

Quoted 4 lines

Sure, they would rather not to. But there are also a lot of ways you can improve vmap more than what XFS does (or probably what darwin does) (more persistence for cached objects, and batched invalidates for example).

XFS already has persistence across the object life time (which can be many tens of seconds for a frequently used buffer)

and it also does batched
unmapping of objects as well.

Quoted 4 lines

There are also a lot of trivial things you can do to make a lot of those accesses not require vmaps (and less trivial things, but even such things as binary searches over multiple pages should be quite possible with a bit of logic).

Yes, we already do the many of these things (via xfs_buf_offset()), but that is not good enough for something like a memcpy that spans multiple pages in a large block (think btree block compaction, splits and recombines).

IOWs, we already play these vmap harm-minimisation games in the places where we can, but still the overhead is high and something we'd prefer to be able to avoid.

Quoted 3 lines

IOWs, we already play these vmap harm-minimisation games in the places where we can, but still the overhead is high and something we'd prefer to be able to avoid.

I don't think you've looked nearly far enough with all this low hanging fruit.

I just gave 4 things which combined might easily reduce xfs vmap overhead by several orders of magnitude, all without changing much code at all.

Quoted 2 lines · Nick Piggin

I just gave 4 things which combined might easily reduce xfs vmap overhead by several orders of magnitude, all without changing much code at all.

Patches would be greatly appreciately. You obviously understand this vm code much better than I do, so if it's easy to fix by adding some generic vmap cache thingy, please do.

Quoted 5 lines · David Chinner

Quoted 2 lines · Nick Piggin

I just gave 4 things which combined might easily reduce xfs vmap overhead by several orders of magnitude, all without changing much code at all.

Quoted 3 lines

Patches would be greatly appreciately. You obviously understand this vm code much better than I do, so if it's easy to fix by adding some generic vmap cache thingy, please do.

Well, it may not be easy to _fix_, but it's easy to try a few improvements ;)

How do I make an image and run a workload that will coerce XFS into doing a significant number of vmaps?

Quoted 5 lines · Nick Piggin

Well, it may not be easy to _fix_, but it's easy to try a few improvements ;)

How do I make an image and run a workload that will coerce XFS into doing a significant number of vmaps?

# mkfs.xfs -n size=16384 <dev>

to create a filesystem with a 16k directory block size on a 4k page machine.

Then just do operations on directories with lots of files in them (tens of thousands). Every directory operation will require at least one vmap in this situation - e.g. a traversal will result in lots and lots of blocks being read that will require vmap() for every directory block read from disk and an unmap almost immediately afterwards when the reference is dropped....

Quoted 6 lines · David Chinner

Then just do operations on directories with lots of files in them (tens of thousands). Every directory operation will require at least one vmap in this situation - e.g. a traversal will result in lots and lots of blocks being read that will require vmap() for every directory block read from disk and an unmap almost immediately afterwards when the reference is dropped....

Ah, wow, thanks: I can reproduce it.

Quoted 9 lines · Nick Piggin

Quoted 6 lines · David Chinner

Then just do operations on directories with lots of files in them (tens of thousands). Every directory operation will require at least one vmap in this situation - e.g. a traversal will result in lots and lots of blocks being read that will require vmap() for every directory block read from disk and an unmap almost immediately afterwards when the reference is dropped....

Ah, wow, thanks: I can reproduce it.

OK, the vunmap batching code wipes your TLB flushing and IPIs off the table. Diffstat below, but the TLB portions are here (besides that _everything_ is probably lower due to less TLB misses caused by the TLB flushing):

      -170   -99.4% sn2_send_IPI
      -343  -100.0% sn_send_IPI_phys
    -17911   -99.9% smp_call_function

Total performance went up by 30% on a 64-way system (248 seconds to 172 seconds to run parallel finds over different huge directories).

     23012  54790.5% _read_lock
      9427   329.0% __get_vm_area_node
      5792     0.0% __find_vm_area
      1590  53000.0% __vunmap

Next I have some patches to scale the vmap locks and data structures better, but they're not quite ready yet. This looks like it should result in a further speedup of several times when combined with the TLB flushing reductions here...

Quoted 5 lines · Nick Piggin

OK, the vunmap batching code wipes your TLB flushing and IPIs off the table. Diffstat below, but the TLB portions are here (besides that _everything_ is probably lower due to less TLB misses caused by the TLB flushing):

Quoted 6 lines

      -170   -99.4% sn2_send_IPI
      -343  -100.0% sn_send_IPI_phys
    -17911   -99.9% smp_call_function

Total performance went up by 30% on a 64-way system (248 seconds to 172 seconds to run parallel finds over different huge directories).

Good start, Nick ;)

Quoted 4 lines

     23012  54790.5% _read_lock
      9427   329.0% __get_vm_area_node
      5792     0.0% __find_vm_area
      1590  53000.0% __vunmap

....

_read_lock? I though vmap() and vunmap() only took the vmlist_lock in write mode.....

Quoted 4 lines

Next I have some patches to scale the vmap locks and data structures better, but they're not quite ready yet. This looks like it should result in a further speedup of several times when combined with the TLB flushing reductions here...

Sounds promising - when you have patches that work, send them my way and I'll run some tests on them.

Quoted 11 lines · Nick Piggin

Quoted 10 lines

Quoted 3 lines

OTOH, I'm not sure how much buy-in there was from the filesystems guys. Particularly Christoph H and XFS (which is strange because they already do vmapping in places).

I think they use vmapping because they have to, not because they want to. They might be a lot happier with fsblock if it used contiguous pages for large blocks whenever possible - I don't know for sure. The metadata accessors they might be unhappy with because it's inconvenient but as Christoph Hellwig pointed out at VM/FS, the filesystems who really care will convert.

Quoted 4 lines

Sure, they would rather not to. But there are also a lot of ways you can improve vmap more than what XFS does (or probably what darwin does) (more persistence for cached objects, and batched invalidates for example).

XFS already has persistence across the object life time (which can be many tens of seconds for a frequently used buffer)

and it also does batched
unmapping of objects as well.

Quoted 4 lines

There are also a lot of trivial things you can do to make a lot of those accesses not require vmaps (and less trivial things, but even such things as binary searches over multiple pages should be quite possible with a bit of logic).

Yes, we already do the many of these things (via xfs_buf_offset()), but that is not good enough for something like a memcpy that spans multiple pages in a large block (think btree block compaction, splits and recombines).

IOWs, we already play these vmap harm-minimisation games in the places where we can, but still the overhead is high and something we'd prefer to be able to avoid.

Quoted 4 lines

Well Christoph seems to still be spinning them as a solution for VM scalability and first class support for making contiguous IOs, large filesystem block sizes etc.

Yeah, I can't argue with you there. I was under the impression that we would be dealing with this strictly as a second class solution to see what it bought to help steer the direction of fsblock.

As you say, a difference is if we fail to allocate a hugepage, the world does not end. It's been a well known problem for years and grouping pages by mobility is aimed at relaxing some of the more painful points. It has other uses as well, but each of them is expected to deal with failures with contiguous range allocation.

Quoted 4 lines

And I would have kept quiet this time too, except for the worrying idea to use higher order pages to fix the SLUB vs SLAB regression, and if the rationale for this patchset was more realistic.

I don't agree with using higher order pages to fix SLUB vs SLAB performance issues either. SLUB has to be able to compete with SLAB on it's own terms. If SLUB gains x% over SLAB in specialised cases with high orders, then fair enough but minimally, SLUB has to perform the same as SLAB at order-0. Like you, I think if we depend on SLUB using high orders to match SLAB, we are going to get kicked further down the line.

Quoted 4 lines

In theory (and again for the filesystem guys who don't have to worry about it). In practice after seeing the patch it's not a nice thing for the VM to have to do.

That may be a good enough reason on it's own to delay this. It's a technical provable point.

I might regret saying this, but it would be easier to craft an attack using pagetable pages. It's woefully difficult to do but it's probably doable. I say pagetables because while slub targetted reclaim is on the cards and memory compaction exists for page cache pages, pagetables are currently pinned with no prototype patch existing to deal with them.

If we hit this problem at all, it'll be due to gradual natural degredation. It used to be a case that jumbo ethernets reported problems after running for weeks and we might encounter something similar with large blocks while it lacks a fallback. We no longer see jumbo ethernet reports but the fact is we don't know if it's because we fixed it or people gave up. Chances are people will be more persistent with large blocks than they were with jumbo ethernet.

It would be interesting to craft an attack. If you knew roughly the layout and size of your dentry slab for example... maybe you could stat a whole lot of files, then open one and keep it open (maybe post the fd to a unix socket or something crazy!) when you think you have filled up a couple of MB worth of them. Repeat the process until your movable zone is gone. Or do the same things with pagetables, or task structs, or radix tree nodes, etc.. these are the kinds of things I worry about (as well as just the gradual natural degredation).

Quoted 8 lines · Nick Piggin

It would be interesting to craft an attack. If you knew roughly the layout and size of your dentry slab for example... maybe you could stat a whole lot of files, then open one and keep it open (maybe post the fd to a unix socket or something crazy!) when you think you have filled up a couple of MB worth of them. Repeat the process until your movable zone is gone. Or do the same things with pagetables, or task structs, or radix tree nodes, etc.. these are the kinds of things I worry about (as well as just the gradual natural degredation).

I guess you would have to run that without my targeted slab reclaim patchset? Otherwise the slab that are in the way could be reclaimed and you could not produce your test case.

Quoted 3 lines

I guess you would have to run that without my targeted slab reclaim patchset? Otherwise the slab that are in the way could be reclaimed and you could not produce your test case.

I didn't realise you had patches to move pinned dentries, radix tree nodes, task structs, page tables etc. Did I miss them in your last patchset?

Quoted 7 lines · Nick Piggin

Quoted 3 lines

I guess you would have to run that without my targeted slab reclaim patchset? Otherwise the slab that are in the way could be reclaimed and you could not produce your test case.

I didn't realise you had patches to move pinned dentries, radix tree nodes, task structs, page tables etc. Did I miss them in your last patchset?

You did not mention that in your earlier text.

If these are issues then we
certainly can work on that. Could you first provide us some real failure conditions so that we know that these are real problems?

I think I would have as good a shot as any to write a fragmentation exploit, yes. I think I've given you enough info to do the same, so I'd like to hear a reason why it is not a problem.

Quoted 3 lines · Nick Piggin

I think I would have as good a shot as any to write a fragmentation exploit, yes. I think I've given you enough info to do the same, so I'd like to hear a reason why it is not a problem.

No you have not explained why the theoretical issues continue to exist given even just considering Lumpy Reclaim in .23 nor what effect the antifrag patchset would have.

And you have used a 2M pagesize which is
irrelevant to this patchset that deals with blocksizes up to 64k. In my experience the use of blocksize < PAGE_COSTLY_ORDER (32k) is reasonably safe.

Quoted 3 lines

No you have not explained why the theoretical issues continue to exist given even just considering Lumpy Reclaim in .23 nor what effect the antifrag patchset would have.

So how does lumpy reclaim, your slab patches, or anti-frag have much effect on the worst case situation? Or help much against a targetted fragmentation attack?

Quoted 4 lines

And you have used a 2M pagesize which is
irrelevant to this patchset that deals with blocksizes up to 64k. In my experience the use of blocksize < PAGE_COSTLY_ORDER (32k) is reasonably safe.

I used EXACTLY the page sizes that you brought up in your patch description (ie. 64K and 2MB).

Quoted 7 lines · Nick Piggin

Quoted 3 lines

No you have not explained why the theoretical issues continue to exist given even just considering Lumpy Reclaim in .23 nor what effect the antifrag patchset would have.

So how does lumpy reclaim, your slab patches, or anti-frag have much effect on the worst case situation? Or help much against a targetted fragmentation attack?

F.e. Lumpy reclaim reclaim neighboring pages and thus works against fragmentation. So your formulae no longer works.

Quoted 7 lines

Quoted 4 lines

And you have used a 2M pagesize which is
irrelevant to this patchset that deals with blocksizes up to 64k. In my experience the use of blocksize < PAGE_COSTLY_ORDER (32k) is reasonably safe.

I used EXACTLY the page sizes that you brought up in your patch description (ie. 64K and 2MB).

The patch currently only supports 64k.

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

Now there are lots of other little heuristics, *including lumpy reclaim and various slab reclaim improvements*, that improve the effectiveness or speed of this thing, but at the end of the day, it has the same basic

issues. Unless you can move practically any currently unmovable allocation (which will either be a lot of intrusive code or require a vmapped kernel), then you can't get around the fundamental problem. And if you do get around the fundamental problem, you don't really need to group pages by mobility any more because they are all movable[*].

So lumpy reclaim does not change my formula nor significantly help against a fragmentation attack. AFAIKS.

[*] ok, this isn't quite true because if you can actually put a hard limit on unmovable allocations then anti-frag will fundamentally help -- get back to me on that when you get patches to move most of the obvious ones.

Quoted 1 line

The patch currently only supports 64k.

Sure, and I pointed out the theoretical figure for 64K pages as well. Is that figure not problematic to you? Where do you draw the limit for what is acceptable? Why? What happens with tiny memory machines where a reserve or even the anti-frag patches may not be acceptable and/or work very well? When do you require reserve pools? Why are reserve pools acceptable for first-class support of filesystems when it has been very loudly been made a known policy decision by Linus in the past (and for some valid reasons) that we should not put limits on the sizes of caches in the kernel.

Quoted 2 lines · Nick Piggin

So lumpy reclaim does not change my formula nor significantly help against a fragmentation attack. AFAIKS.

Lumpy reclaim improves the situation significantly because the overwhelming majority of allocation during the lifetime of a systems are movable and thus it is able to opportunistically restore the availability of higher order pages by reclaiming neighboring pages.

Quoted 4 lines

[*] ok, this isn't quite true because if you can actually put a hard limit on unmovable allocations then anti-frag will fundamentally help -- get back to me on that when you get patches to move most of the obvious ones.

We have this hard limit using ZONE_MOVABLE in 2.6.23.

Quoted 9 lines

Sure, and I pointed out the theoretical figure for 64K pages as well. Is that figure not problematic to you? Where do you draw the limit for what is acceptable? Why? What happens with tiny memory machines where a reserve or even the anti-frag patches may not be acceptable and/or work very well? When do you require reserve pools? Why are reserve pools acceptable for first-class support of filesystems when it has been very loudly been made a known policy decision by Linus in the past (and for some valid reasons) that we should not put limits on the sizes of caches in the kernel.

64K pages may problematic because it is above the PAGE_ORDER_COSTLY in 2.6.23. 32K is currently much safer because lumpy reclaim can restore these and does so on my systems. I expect the situation for 64K pages to improve when more of Mel's patches go in. We have long term experience with 32k sized allocation through Andrew's tree.

Reserve pools as handled (by the not yet available) large page pool patches (which again has altogether another purpose) are not a limit. The reserve pools are used to provide a mininum of higher order pages that is not broken down in order to insure that a mininum number of the desired order of pages is even available in your worst case scenario. Mainly I think that is needed during the period when memory defragmentation is still under development.

Quoted 6 lines

Quoted 4 lines

[*] ok, this isn't quite true because if you can actually put a hard limit on unmovable allocations then anti-frag will fundamentally help -- get back to me on that when you get patches to move most of the obvious ones.

We have this hard limit using ZONE_MOVABLE in 2.6.23.

So we're back to 2nd class support.

Quoted 7 lines

Reserve pools as handled (by the not yet available) large page pool patches (which again has altogether another purpose) are not a limit. The reserve pools are used to provide a mininum of higher order pages that is not broken down in order to insure that a mininum number of the desired order of pages is even available in your worst case scenario. Mainly I think that is needed during the period when memory defragmentation is still under development.

fsblock doesn't need any of those hacks, of course.

Quoted 5 lines · Nick Piggin

Quoted 5 lines

Quoted 4 lines

[*] ok, this isn't quite true because if you can actually put a hard limit on unmovable allocations then anti-frag will fundamentally help -- get back to me on that when you get patches to move most of the obvious ones.

Quoted 3 lines

Quoted 1 line

We have this hard limit using ZONE_MOVABLE in 2.6.23.

So we're back to 2nd class support.

2nd class support for me means a feature that is not enabled by default but that can be enabled in order to increase performance. The 2nd class support is there because we are not yet sure about the maturity of the memory allocation methods.

Quoted 8 lines

Quoted 7 lines

Reserve pools as handled (by the not yet available) large page pool patches (which again has altogether another purpose) are not a limit. The reserve pools are used to provide a mininum of higher order pages that is not broken down in order to insure that a mininum number of the desired order of pages is even available in your worst case scenario. Mainly I think that is needed during the period when memory defragmentation is still under development.

Quoted 1 line

fsblock doesn't need any of those hacks, of course.

Nor does mine for the low orders that we are considering. For order > MAX_ORDER this is unavoidable since the page allocator cannot manage such large pages. It can be used for lower order if there are issues (that I have not seen yet).

Quoted 6 lines

Quoted 1 line

fsblock doesn't need any of those hacks, of course.

Nor does mine for the low orders that we are considering. For order > MAX_ORDER this is unavoidable since the page allocator cannot manage such large pages. It can be used for lower order if there are issues (that I have not seen yet).

Or we can just avoid all doubt (and doesn't have arbitrary limitations according to what you think might be reasonable or how well the system actually behaves).

Quoted 7 lines · Nick Piggin

Quoted 6 lines

Quoted 1 line

fsblock doesn't need any of those hacks, of course.

Nor does mine for the low orders that we are considering. For order > MAX_ORDER this is unavoidable since the page allocator cannot manage such large pages. It can be used for lower order if there are issues (that I have not seen yet).

Quoted 3 lines

Or we can just avoid all doubt (and doesn't have arbitrary limitations according to what you think might be reasonable or how well the system actually behaves).

We can avoid all doubt in this patchset as well by adding support for fallback to a vmalloced compound page.

Quoted 2 lines

We can avoid all doubt in this patchset as well by adding support for fallback to a vmalloced compound page.

How would you do a vmapped fallback in your patchset? How would you keep track of pages 2..N if they don't exist in the radix tree?

What if they don't even exist in the kernel's linear mapping? It seems you would also require more special casing in the fault path and special casing in the block layer to do this.

True. That is why we want to limit the number of unmovable allocations and that is why ZONE_MOVABLE exists to limit those. However, unmovable allocations are already rare today. The overwhelming majority of allocations are movable and reclaimable. You can see that f.e. by looking at /proc/meminfo and see how high SUnreclaim: is (does not catch everything but its a good indicator).

Quoted 6 lines · Christoph Lameter

True. That is why we want to limit the number of unmovable allocations and that is why ZONE_MOVABLE exists to limit those. However, unmovable allocations are already rare today. The overwhelming majority of allocations are movable and reclaimable. You can see that f.e. by looking at /proc/meminfo and see how high SUnreclaim: is (does not catch everything but its a good indicator).

Just to inject another factor into the discussion, please remember that Linux also runs on nommu systems, where things like user space allocations are neither movable nor reclaimable.

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

And it doesn't even have to be a DoS. The natural fragmentation that occurs today in a kernel today has the possibility to slowly push out the movable groups and give you the same situation.

Quoted 4 lines · Nick Piggin

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

I'm assuming that when an unmovable allocation hijacks a movable group any further unmovable alloc will evict movable objects out of that group before hijacking another one. right?

Quoted 3 lines

And it doesn't even have to be a DoS. The natural fragmentation that occurs today in a kernel today has the possibility to slowly push out the movable groups and give you the same situation.

How would you cause that? Say you do want to purposefully place one unmovable 4k page into every 64k compund page. So you allocate 4K. First 64k page locked. But now, to get 4K into the second 64K page you have to first use up all the rest of the first 64k page. Meaning one 4k chunk, one 8k chunk, one 16k cunk, one 32k chunk. Only then will a new 64k chunk be broken and become locked.

So to get the last 64k chunk used all previous 32k chunks need to be blocked and you need to allocate 32k (or less if more is blocked). For all previous 32k chunks to be blocked every second 16k needs to be blocked. To block the last of those 16k chunks all previous 8k chunks need to be blocked and you need to allocate 8k. For all previous 8k chunks to be blocked every second 4k page needs to be used. To alloc the last of those 4k pages all previous 4k pages need to be used.

So to construct a situation where no continious 64k chunk is free you have to allocate <total mem> - 64k - 32k - 16k - 8k - 4k (or there about) of memory first. Only then could you free memory again while still keeping every 64k page blocked. Does that occur naturally given enough ram to start with?

Too see how bad fragmentation could be I wrote a little progamm to simulate allocations with the following simplified alogrithm:

Memory management:
- Free pages are kept in buckets, one per order, and sorted by address.
- alloc() the front page (smallest address) out of the bucket of the right order or recursively splits the next higher bucket.
- free() recursively tries to merge a page with its neighbour and puts the result back into the proper bucket (sorted by address).

Allocation and lifetime:
- Every tick a new page is allocated with random order.

- The order is a triangle distribution with max at 0 (throw 2 dice, add the eyes, subtract 7, abs() the number).
- The page is scheduled to be freed after X ticks. Where X is nearly a gaus curve centered at 0 and maximum at <total num pages> * 1.5. (What I actualy do is throw 8 dice and sum them up and shift the result.)

Display:
I start with a white window. Every page allocation draws a black box from the address of the page and as wide as the page is big (-1 pixel to give a seperation to the next page). Every page free draws a yellow box in place of the black one. Yellow to show where a page was in use at one point while white means the page was never used.

As the time ticks the memory fills up. Quickly at first and then comes to a stop around 80% filled. And then something interesting happens. The yellow regions (previously used but now free) start drifting up. Small pages tend to end up in the lower addresses and big pages at the higher addresses. The memory defragments itself to some degree.

http://mrvn.homeip.net/fragment/

Simulating 256MB ram and after 1472943 ticks and 530095 4k, 411841 8k, 295296 16k, 176647 32k and 59064 64k allocations you get this:
http://mrvn.homeip.net/fragment/256mb.png

Simulating 1GB ram and after 5881185 ticks and 2116671 4k, 1645957 8k, 1176994 16k, 705873 32k and 235690 64k allocations you get this:
http://mrvn.homeip.net/fragment/1gb.png

Quoted 11 lines · Goswin von Brederlow

Quoted 4 lines · Nick Piggin

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

I'm assuming that when an unmovable allocation hijacks a movable group any further unmovable alloc will evict movable objects out of that group before hijacking another one. right?

No eviction takes place. If an unmovable allocation gets placed in a movable group, then steps are taken to ensure that future unmovable allocations will take place in the same range (these decisions take place in __rmqueue_fallback()). When choosing a movable block to pollute, it will also choose the lowest possible block in PFN terms to steal so that fragmentation pollution will be as confined as possible. Evicting the unmovable pages would be one of those expensive steps that have been avoided to date.

Quoted 10 lines

Quoted 3 lines

And it doesn't even have to be a DoS. The natural fragmentation that occurs today in a kernel today has the possibility to slowly push out the movable groups and give you the same situation.

How would you cause that? Say you do want to purposefully place one unmovable 4k page into every 64k compund page. So you allocate 4K. First 64k page locked. But now, to get 4K into the second 64K page you have to first use up all the rest of the first 64k page. Meaning one 4k chunk, one 8k chunk, one 16k cunk, one 32k chunk. Only then will a new 64k chunk be broken and become locked.

It would be easier early in the boot to mmap a large area and fault it in in virtual address order then mlock every a page every 64K. Early in the systems lifetime, there will be a rough correlation between physical and virtual memory.

Without mlock(), the most successful attack will like mmap() a 60K region and fault it in as an attempt to get pagetable pages placed in every 64K region. This strategy would not work with grouping pages by mobility though as it would group the pagetable pages together.

Targetted attacks on grouping pages by mobility are not very easy and not that interesting either. As Nick suggests, the natural fragmentation over long periods of time is what is interesting.

Quoted 8 lines

So to get the last 64k chunk used all previous 32k chunks need to be blocked and you need to allocate 32k (or less if more is blocked). For all previous 32k chunks to be blocked every second 16k needs to be blocked. To block the last of those 16k chunks all previous 8k chunks need to be blocked and you need to allocate 8k. For all previous 8k chunks to be blocked every second 4k page needs to be used. To alloc the last of those 4k pages all previous 4k pages need to be used.

Quoted 6 lines

So to construct a situation where no continious 64k chunk is free you have to allocate <total mem> - 64k - 32k - 16k - 8k - 4k (or there about) of memory first. Only then could you free memory again while still keeping every 64k page blocked. Does that occur naturally given enough ram to start with?

I believe it's very difficult to craft an attack that will work in a short period of time. An attack that worked on 2.6.22 as well may have no success on 2.6.23-rc4-mm1 for example as grouping pages by mobility does it make it exceedingly hard to craft an attack unless the attacker can mlock large amounts of memory.

Quoted 11 lines

Too see how bad fragmentation could be I wrote a little progamm to simulate allocations with the following simplified alogrithm:

Memory management:
- Free pages are kept in buckets, one per order, and sorted by address.
- alloc() the front page (smallest address) out of the bucket of the right order or recursively splits the next higher bucket.
- free() recursively tries to merge a page with its neighbour and puts the result back into the proper bucket (sorted by address).

Quoted 2 lines

Allocation and lifetime:
- Every tick a new page is allocated with random order.

This step in itself is not representative of what happens in the kernel. The vast vast majority of allocations are order-0. It's a fun analysis but I'm not sure can we draw any conclusions from it.

Statistical analysis of the buddy algorithm have implied that it doesn't suffer that badly from external fragmentation but we know in practice that things are different. A model is hard because minimally the lifetime of pages varies widely.

Quoted 7 lines

- The order is a triangle distribution with max at 0 (throw 2 dice, add the eyes, subtract 7, abs() the number).
- The page is scheduled to be freed after X ticks. Where X is nearly a gaus curve centered at 0 and maximum at <total num pages> * 1.5. (What I actualy do is throw 8 dice and sum them up and shift the result.)

I doubt this is how the kernel behaves either.

Quoted 20 lines

Display:
I start with a white window. Every page allocation draws a black box from the address of the page and as wide as the page is big (-1 pixel to give a seperation to the next page). Every page free draws a yellow box in place of the black one. Yellow to show where a page was in use at one point while white means the page was never used.

As the time ticks the memory fills up. Quickly at first and then comes to a stop around 80% filled. And then something interesting happens. The yellow regions (previously used but now free) start drifting up. Small pages tend to end up in the lower addresses and big pages at the higher addresses. The memory defragments itself to some degree.

http://mrvn.homeip.net/fragment/

Simulating 256MB ram and after 1472943 ticks and 530095 4k, 411841 8k, 295296 16k, 176647 32k and 59064 64k allocations you get this:
http://mrvn.homeip.net/fragment/256mb.png

Quoted 4 lines

Simulating 1GB ram and after 5881185 ticks and 2116671 4k, 1645957 8k, 1176994 16k, 705873 32k and 235690 64k allocations you get this:
http://mrvn.homeip.net/fragment/1gb.png

These type of pictures feel somewhat familiar
(http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg).

Quoted 13 lines · Mel Gorman

Quoted 11 lines · Goswin von Brederlow

Quoted 4 lines · Nick Piggin

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

I'm assuming that when an unmovable allocation hijacks a movable group any further unmovable alloc will evict movable objects out of that group before hijacking another one. right?

Quoted 8 lines

No eviction takes place. If an unmovable allocation gets placed in a movable group, then steps are taken to ensure that future unmovable allocations will take place in the same range (these decisions take place in __rmqueue_fallback()). When choosing a movable block to pollute, it will also choose the lowest possible block in PFN terms to steal so that fragmentation pollution will be as confined as possible. Evicting the unmovable pages would be one of those expensive steps that have been avoided to date.

But then you can have all blocks filled with movable data, free 4K in one group, allocate 4K unmovable to take over the group, free 4k in the next group, take that group and so on. You can end with 4k unmovable in every 64k easily by accident.

There should be a lot of preassure for movable objects to vacate a mixed group or you do get fragmentation catastrophs.

Looking at my
little test program evicting movable objects from a mixed group should not be that expensive as it doesn't happen often.

The cost of it
should be freeing some pages (or finding free ones in a movable group) and then memcpy.

With my simplified simulation it never happens so I expect it to only happen when the work set changes.

Quoted 16 lines

Quoted 10 lines

Quoted 3 lines

And it doesn't even have to be a DoS. The natural fragmentation that occurs today in a kernel today has the possibility to slowly push out the movable groups and give you the same situation.

How would you cause that? Say you do want to purposefully place one unmovable 4k page into every 64k compund page. So you allocate 4K. First 64k page locked. But now, to get 4K into the second 64K page you have to first use up all the rest of the first 64k page. Meaning one 4k chunk, one 8k chunk, one 16k cunk, one 32k chunk. Only then will a new 64k chunk be broken and become locked.

It would be easier early in the boot to mmap a large area and fault it in in virtual address order then mlock every a page every 64K. Early in the systems lifetime, there will be a rough correlation between physical and virtual memory.

Quoted 4 lines

Without mlock(), the most successful attack will like mmap() a 60K region and fault it in as an attempt to get pagetable pages placed in every 64K region. This strategy would not work with grouping pages by mobility though as it would group the pagetable pages together.

But even with mlock the virtual pages should still be movable.

So if
you evict movable objects from mixed group when needed all the pagetable pages would end up in the same mixed group slowly taking it over completly. No fragmentation at all. See how essential that feature is. :)

Quoted 36 lines

Targetted attacks on grouping pages by mobility are not very easy and not that interesting either. As Nick suggests, the natural fragmentation over long periods of time is what is interesting.

Quoted 8 lines

So to get the last 64k chunk used all previous 32k chunks need to be blocked and you need to allocate 32k (or less if more is blocked). For all previous 32k chunks to be blocked every second 16k needs to be blocked. To block the last of those 16k chunks all previous 8k chunks need to be blocked and you need to allocate 8k. For all previous 8k chunks to be blocked every second 4k page needs to be used. To alloc the last of those 4k pages all previous 4k pages need to be used.

Quoted 6 lines

So to construct a situation where no continious 64k chunk is free you have to allocate <total mem> - 64k - 32k - 16k - 8k - 4k (or there about) of memory first. Only then could you free memory again while still keeping every 64k page blocked. Does that occur naturally given enough ram to start with?

I believe it's very difficult to craft an attack that will work in a short period of time. An attack that worked on 2.6.22 as well may have no success on 2.6.23-rc4-mm1 for example as grouping pages by mobility does it make it exceedingly hard to craft an attack unless the attacker can mlock large amounts of memory.

Quoted 11 lines

Too see how bad fragmentation could be I wrote a little progamm to simulate allocations with the following simplified alogrithm:

Memory management:
- Free pages are kept in buckets, one per order, and sorted by address.
- alloc() the front page (smallest address) out of the bucket of the right order or recursively splits the next higher bucket.
- free() recursively tries to merge a page with its neighbour and puts the result back into the proper bucket (sorted by address).

Quoted 6 lines

Quoted 2 lines

Allocation and lifetime:
- Every tick a new page is allocated with random order.

This step in itself is not representative of what happens in the kernel. The vast vast majority of allocations are order-0. It's a fun analysis but I'm not sure can we draw any conclusions from it.

I skewed the distribution to that end. Maybe not enough but I wanted to get quite a big of large pages. Also I'm only simulating the unmovable objects and I would expect the I/O layer to make a lot of higher order allocs/free to benefit from compound pages. If nobody uses them then what is the point adding them?

Quoted 13 lines

Statistical analysis of the buddy algorithm have implied that it doesn't suffer that badly from external fragmentation but we know in practice that things are different. A model is hard because minimally the lifetime of pages varies widely.

Quoted 7 lines

- The order is a triangle distribution with max at 0 (throw 2 dice, add the eyes, subtract 7, abs() the number).
- The page is scheduled to be freed after X ticks. Where X is nearly a gaus curve centered at 0 and maximum at <total num pages> * 1.5. (What I actualy do is throw 8 dice and sum them up and shift the result.)

Quoted 1 line

I doubt this is how the kernel behaves either.

I had to pick something. I agree that the lifetime part is the hardest to simulate and the point where an attack would start.

Quoted 25 lines

Quoted 24 lines

Display:
I start with a white window. Every page allocation draws a black box from the address of the page and as wide as the page is big (-1 pixel to give a seperation to the next page). Every page free draws a yellow box in place of the black one. Yellow to show where a page was in use at one point while white means the page was never used.

As the time ticks the memory fills up. Quickly at first and then comes to a stop around 80% filled. And then something interesting happens. The yellow regions (previously used but now free) start drifting up. Small pages tend to end up in the lower addresses and big pages at the higher addresses. The memory defragments itself to some degree.

http://mrvn.homeip.net/fragment/

Simulating 256MB ram and after 1472943 ticks and 530095 4k, 411841 8k, 295296 16k, 176647 32k and 59064 64k allocations you get this:
http://mrvn.homeip.net/fragment/256mb.png

Simulating 1GB ram and after 5881185 ticks and 2116671 4k, 1645957 8k, 1176994 16k, 705873 32k and 235690 64k allocations you get this:
http://mrvn.homeip.net/fragment/1gb.png

Quoted 2 lines

These type of pictures feel somewhat familiar
(http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg).

Those look a lot better and look like they are actually real kernel data. How did you make them and can one create them in real-time (say once a second or so)?

There seem to be an awfull lot of pinned pages inbetween the movable.

I would verry much like to see the same data with evicting of movable pages out of mixed groups. I see not a single movable group while with strict eviction there could be at most one mixed group per order.

On (15/09/07 02:31), Goswin von Brederlow didst pronounce:

Quoted 24 lines

Quoted 13 lines · Mel Gorman

Quoted 11 lines · Goswin von Brederlow

Quoted 4 lines · Nick Piggin

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

I'm assuming that when an unmovable allocation hijacks a movable group any further unmovable alloc will evict movable objects out of that group before hijacking another one. right?

Quoted 8 lines

No eviction takes place. If an unmovable allocation gets placed in a movable group, then steps are taken to ensure that future unmovable allocations will take place in the same range (these decisions take place in __rmqueue_fallback()). When choosing a movable block to pollute, it will also choose the lowest possible block in PFN terms to steal so that fragmentation pollution will be as confined as possible. Evicting the unmovable pages would be one of those expensive steps that have been avoided to date.

Quoted 5 lines

But then you can have all blocks filled with movable data, free 4K in one group, allocate 4K unmovable to take over the group, free 4k in the next group, take that group and so on. You can end with 4k unmovable in every 64k easily by accident.

As the mixing takes place at the lowest possible block, it's exceptionally difficult to trigger this. Possible, but exceptionally difficult.

As I have stated repeatedly, the guarantees can be made but potential hugepage allocation did not justify it. Large blocks might.

Quoted 2 lines

There should be a lot of preassure for movable objects to vacate a mixed group or you do get fragmentation catastrophs.

We (Andy Whitcroft and I) did implement something like that. It hooked into kswapd to clean mixed blocks. If the caller could do the cleaning, it did the work instead of kswapd.

Quoted 3 lines

Looking at my
little test program evicting movable objects from a mixed group should not be that expensive as it doesn't happen often.

It happens regularly if the size of the block you need to keep clean is lower than min_free_kbytes. In the case of hugepages, that was always the case.

Quoted 3 lines

The cost of it
should be freeing some pages (or finding free ones in a movable group) and then memcpy.

Freeing pages is not cheap. Copying pages is cheaper but not cheap.

Quoted 6 lines

So if
you evict movable objects from mixed group when needed all the pagetable pages would end up in the same mixed group slowly taking it over completly. No fragmentation at all. See how essential that feature is. :)

To move pages, there must be enough blocks free. That is where min_free_kbytes had to come in. If you cared only about keeping 64KB chunks free, it makes sense but it didn't in the context of hugepages.

Quoted 7 lines

Quoted 2 lines

These type of pictures feel somewhat familiar
(http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg).

Those look a lot better and look like they are actually real kernel data. How did you make them and can one create them in real-time (say once a second or so)?

It's from a real kernel. When I was measuring this stuff, I took a sample every 2 seconds.

Quoted 1 line

There seem to be an awfull lot of pinned pages inbetween the movable.

It wasn't grouping by mobility at the time.

Quoted 4 lines

I would verry much like to see the same data with evicting of movable pages out of mixed groups. I see not a single movable group while with strict eviction there could be at most one mixed group per order.

With strict eviction, there would be no mixed blocks period.

Quoted 31 lines · [email protected] (Mel Gorman) writes:

On (15/09/07 02:31), Goswin von Brederlow didst pronounce:

Quoted 29 lines

Quoted 13 lines · Mel Gorman

Quoted 11 lines · Goswin von Brederlow

Quoted 4 lines · Nick Piggin

In my attack, I cause the kernel to allocate lots of unmovable allocations and deplete movable groups. I theoretically then only need to keep a small number (1/2^N) of these allocations around in order to DoS a page allocation of order N.

I'm assuming that when an unmovable allocation hijacks a movable group any further unmovable alloc will evict movable objects out of that group before hijacking another one. right?

Quoted 8 lines

No eviction takes place. If an unmovable allocation gets placed in a movable group, then steps are taken to ensure that future unmovable allocations will take place in the same range (these decisions take place in __rmqueue_fallback()). When choosing a movable block to pollute, it will also choose the lowest possible block in PFN terms to steal so that fragmentation pollution will be as confined as possible. Evicting the unmovable pages would be one of those expensive steps that have been avoided to date.

But then you can have all blocks filled with movable data, free 4K in one group, allocate 4K unmovable to take over the group, free 4k in the next group, take that group and so on. You can end with 4k unmovable in every 64k easily by accident.

Quoted 3 lines

As the mixing takes place at the lowest possible block, it's exceptionally difficult to trigger this. Possible, but exceptionally difficult.

Why is it difficult?

When user space allocates memory wouldn't it get it contiously?

I mean
that is one of the goals, to use larger continious allocations and map them with a single page table entry where possible, right?

And then
you can roughly predict where an munmap() would free a page.

Say the application does map a few GB of file, uses madvice to tell the kernel it needs a 2MB block (to get a continious 2MB chunk mapped), waits for it and then munmaps 4K in there. A 4k hole for some unmovable object to fill.

If you can then trigger the creation of an
unmovable object as well (stat some file?) and loop you will fill the ram quickly. Maybe it only works in 10% but then you just do it 10 times as often.

Over long times it could occur naturally. This is just to demonstrate it with malice.

Quoted 6 lines

As I have stated repeatedly, the guarantees can be made but potential hugepage allocation did not justify it. Large blocks might.

Quoted 2 lines

There should be a lot of preassure for movable objects to vacate a mixed group or you do get fragmentation catastrophs.

Quoted 3 lines

We (Andy Whitcroft and I) did implement something like that. It hooked into kswapd to clean mixed blocks. If the caller could do the cleaning, it did the work instead of kswapd.

Do you have a graphic like
http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg
for that case?

Quoted 7 lines

Quoted 3 lines

Looking at my
little test program evicting movable objects from a mixed group should not be that expensive as it doesn't happen often.

It happens regularly if the size of the block you need to keep clean is lower than min_free_kbytes. In the case of hugepages, that was always the case.

That assumes that the number of groups allocated for unmovable objects will continiously grow and shrink.

I'm assuming it will level off at
some size for long times (hours) under normal operations.

There should
be some buffering of a few groups to be held back in reserve when it shrinks to prevent the scenario that the size is just at a group boundary and always grows/shrinks by 1 group.

Quoted 5 lines

Quoted 3 lines

The cost of it
should be freeing some pages (or finding free ones in a movable group) and then memcpy.

Freeing pages is not cheap. Copying pages is cheaper but not cheap.

To copy you need a free page as destination. Thats all I ment. Hopefully there will always be a free one and the actual freeing is done asynchronously from the copying.

Quoted 7 lines

Quoted 6 lines

So if
you evict movable objects from mixed group when needed all the pagetable pages would end up in the same mixed group slowly taking it over completly. No fragmentation at all. See how essential that feature is. :)

Quoted 3 lines

To move pages, there must be enough blocks free. That is where min_free_kbytes had to come in. If you cared only about keeping 64KB chunks free, it makes sense but it didn't in the context of hugepages.

I'm more concerned with keeping the little unmovable things out of the way. Those are the things that will fragment the memory and prevent any huge pages to be available even with moving other stuff out of the way.

It would also already be a big plus to have 64k continious chunks for many operations. Guaranty that the filesystem and block layers can always get such a page (by means of copying pages out of the way when needed) and do even larger pages speculative.

But as you say that is where min_free_kbytes comes in. To have the chance of a 2MB continious free chunk you need to have much more reserved free. Something I would certainly do on a 16GB ram server. Note that the buddy system will be better at having large free chunks if user space allocates and frees large chunks as well.

It is
much easier to make an 128K chunk out of 64K chunks than out of 4K chunks. Much more probable to get 2 64k chunks adjacent than 32 4K chunks in series.

Quoted 8 lines

Quoted 7 lines

Quoted 2 lines

These type of pictures feel somewhat familiar
(http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg).

Those look a lot better and look like they are actually real kernel data. How did you make them and can one create them in real-time (say once a second or so)?

Quoted 2 lines

It's from a real kernel. When I was measuring this stuff, I took a sample every 2 seconds.

Can you tell me how? I would like to do the same.

Quoted 3 lines

Quoted 1 line

There seem to be an awfull lot of pinned pages inbetween the movable.

It wasn't grouping by mobility at the time.

That might explain at lot. I was thinking that was with grouping. But without grouping such a rather random distribution of unmovable objects doesn't sound uncommon,.

Quoted 5 lines

Quoted 4 lines

I would verry much like to see the same data with evicting of movable pages out of mixed groups. I see not a single movable group while with strict eviction there could be at most one mixed group per order.

Quoted 1 line

With strict eviction, there would be no mixed blocks period.

I ment on demand eviction. Not evicting the whole group just because we need 4k of it. Even looser would be to allow say 16 mixed groups before moving pages out of the way when needed for an alloc. Best to make it a proc entry and then change the value once a day and see how it behaves. :)

On (17/09/07 00:38), Goswin von Brederlow didst pronounce:

Quoted 12 lines

Quoted 9 lines · [email protected] (Mel Gorman) writes:

On (15/09/07 02:31), Goswin von Brederlow didst pronounce:

Quoted 4 lines

Mel Gorman <[email protected]> writes:
Looking at my
little test program evicting movable objects from a mixed group should not be that expensive as it doesn't happen often.

It happens regularly if the size of the block you need to keep clean is lower than min_free_kbytes. In the case of hugepages, that was always the case.

Quoted 2 lines

That assumes that the number of groups allocated for unmovable objects will continiously grow and shrink.

They do grow and shrink. The number of pagetables in use changes for example.

Quoted 2 lines

I'm assuming it will level off at
some size for long times (hours) under normal operations.

It doesn't unless you assume the system remains in a steady state for it's lifetime. Things like updatedb tend to throw a spanner into the works.

Quoted 5 lines

There should
be some buffering of a few groups to be held back in reserve when it shrinks to prevent the scenario that the size is just at a group boundary and always grows/shrinks by 1 group.

And what size should this group be that all workloads function?

Quoted 11 lines

Quoted 10 lines

Quoted 6 lines

So if
you evict movable objects from mixed group when needed all the pagetable pages would end up in the same mixed group slowly taking it over completly. No fragmentation at all. See how essential that feature is. :)

To move pages, there must be enough blocks free. That is where min_free_kbytes had to come in. If you cared only about keeping 64KB chunks free, it makes sense but it didn't in the context of hugepages.

Quoted 4 lines

I'm more concerned with keeping the little unmovable things out of the way. Those are the things that will fragment the memory and prevent any huge pages to be available even with moving other stuff out of the way.

That's fair, just not cheap

Quoted 2 lines

Can you tell me how? I would like to do the same.

They were generated using trace_allocmap kernel module in
http://www.csn.ul.ie/~mel/projects/vmregress/vmregress-0.81-rc2.tar.gz
in combination with frag-display in the same package. However, in the current version against current -mm's, it'll identify some movable pages wrong. Specifically, it will appear to be mixing movable pages with slab pages and it doesn't identify SLUB pages properly at all (SLUB came after the last revision of this tool). I need to bring an annotation patch up to date before it can generate the images correctly.

that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's

approach in depth.

I *thought* that the end conclusion was that we would go with

Christoph's approach pending two things being resolved;

o mmap() support that we agreed on is good

o A clear statement, with logging maybe for users that mounted a large block filesystem that it might blow up and they get to keep both parts when it does. Basically, for now it's only suitable in specialised environments.

I also thought there was an acknowledgement that long-term, fs-block was the way to go - possibly using contiguous pages optimistically instead of virtual mapping the pages. At that point, it would be a general solution and we could remove the warnings.

That's the absolute worst case but yes, in theory this can occur and it's safest to assume the situation will occur somewhere to someone. It

Where we expected to see the the use of this patchset was in specialised environments *only*. The SGI people can mitigate their mixed fragmentation problems somewhat by setting slub_min_order == large_block_order so that blocks get allocated and freed at the same size. This is partial way towards Andrea's solution of raising the size of an order-0 allocation. The point of printing out the warnings at

Independently of that, we would work on order-0 scalability, particularly readahead and batching operations on ranges of pages as much as possible.

Hi Mel,

Quoted 2 lines

that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's

The config_page_shift guarantees the kernel stacks or whatever not defragmentable allocation other allocation goes into the same 64k "not defragmentable" page. Not like with SGI design that a 8k kernel stack could be allocated in the first 64k page, and then another 8k stack could be allocated in the next 64k page, effectively pinning all 64k pages until Nick worst case scenario triggers.

What I said at the VM summit is that your reclaim-defrag patch in the slub isn't necessarily entirely useless with config_page_shift, because the larger the software page_size, the more partial pages we could find in the slab, so to save some memory if there are tons of pages very partially used, we could free some of them.

But the whole point is that with the config_page_shift, Nick's worst case scenario can't happen by design regardless of defrag or not defrag.

While it can _definitely_ happen with SGI design (regardless
of any defrag thing).

We can still try to save some memory by
defragging the slab a bit, but it's by far *not* required with config_page_shift. No defrag at all is required infact.

Plus there's a cost in defragging and freeing cache... the more you need defrag, the slower the kernel will be.

Quoted 1 line

approach in depth.

Well it wasn't my fault if we didn't discuss it in depth though.

I
tried to discuss it in all possible occasions where I was suggested to talk about it and where it was somewhat on topic.

Given I wasn't even
invited at the KS, I felt it would not be appropriate for me to try to monopolize the VM summit according to my agenda. So I happily listened to what the top kernel developers are planning ;), while giving some hints on what I think the right direction is instead.

Quoted 1 line

I *thought* that the end conclusion was that we would go with

Frankly I don't care what the end conclusion was.

Quoted 3 lines

Christoph's approach pending two things being resolved;

o mmap() support that we agreed on is good

Let's see how good the mmap support for variable order page size will work after the 2 weeks...

Quoted 4 lines

o A clear statement, with logging maybe for users that mounted a large block filesystem that it might blow up and they get to keep both parts when it does. Basically, for now it's only suitable in specialised environments.

Yes, but perhaps you missed that such printk is needed exactly to provide proof that SGI design is the wrong way and it needs to be dumped. If that printk ever triggers it means you were totally wrong.

Quoted 4 lines

I also thought there was an acknowledgement that long-term, fs-block was the way to go - possibly using contiguous pages optimistically instead of virtual mapping the pages. At that point, it would be a general solution and we could remove the warnings.

fsblock should stack on top of config_page_shift simply.

Both are
needed. You don't want to use 64k pages on a laptop but you may want a larger blocksize for the btrees etc... if you've a large harddisk and not much ram.

Quoted 2 lines

That's the absolute worst case but yes, in theory this can occur and it's safest to assume the situation will occur somewhere to someone. It

Do you agree this worst case can't happen with config_page_shift?

Quoted 6 lines

Where we expected to see the the use of this patchset was in specialised environments *only*. The SGI people can mitigate their mixed fragmentation problems somewhat by setting slub_min_order == large_block_order so that blocks get allocated and freed at the same size. This is partial way towards Andrea's solution of raising the size of an order-0 allocation. The point of printing out the warnings at

Except you don't get all the full benefits of it...

Even if I could end up mapping 4k kmalloced entries in userland for the tail packing, that IMHO would still be a preferable solution than to keep the base-page small and to make an hard effort to create large pages out of small pages. The approach I advocate keeps the base page big and the fast path fast, and it rather does some work to split the base pages outside the buddy for the small files.

All your defrag work is still good to have, like I said at the VM summit if you remember, to grow the hugetlbfs at runtime etc... I just rather avoid to depend on it to avoid I/O failure in presence of mlocked pagecache for example.

Quoted 3 lines

Independently of that, we would work on order-0 scalability, particularly readahead and batching operations on ranges of pages as much as possible.

That's pretty much an unnecessary logic, if the order0 pages become larger.

Quoted 1 line · Andrea Arcangeli

Hi Mel,

Hi,

Quoted 10 lines · Mel Gorman

Quoted 2 lines

that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's

The config_page_shift guarantees the kernel stacks or whatever not defragmentable allocation other allocation goes into the same 64k "not defragmentable" page. Not like with SGI design that a 8k kernel stack could be allocated in the first 64k page, and then another 8k stack could be allocated in the next 64k page, effectively pinning all 64k pages until Nick worst case scenario triggers.

In practice, it's pretty difficult to trigger. Buddy allocators always try and use the smallest possible sized buddy to split. Once a 64K is split for a 4K or 8K allocation, the remainder of that block will be used for other 4K, 8K, 16K, 32K allocations. The situation where multiple 64K blocks gets split does not occur.

Now, the worst case scenario for your patch is that a hostile process allocates large amount of memory and mlocks() one 4K page per 64K chunk (this is unlikely in practice I know). The end result is you have many 64KB regions that are now unusable because 4K is pinned in each of them. Your approach is not immune from problems either. To me, only Nicks approach is bullet-proof in the long run.

Quoted 3 lines

We can still try to save some memory by
defragging the slab a bit, but it's by far *not* required with config_page_shift. No defrag at all is required infact.

You will need to take some sort of defragmentation to deal with internal fragmentation. It's a very similar problem to blasting away at slab pages and still not being able to free them because objects are in use. Replace "slab" with "large page" and "object" with "4k page" and the issues are similar.

Quoted 6 lines

Plus there's a cost in defragging and freeing cache... the more you need defrag, the slower the kernel will be.

Quoted 1 line

approach in depth.

Well it wasn't my fault if we didn't discuss it in depth though.

If it's my fault, sorry about that. It wasn't my intention.

Quoted 22 lines · Mel Gorman

Quoted 1 line · Andrea Arcangeli

Hi Mel,

Hi,

Quoted 10 lines · Mel Gorman

Quoted 2 lines

that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's

The config_page_shift guarantees the kernel stacks or whatever not defragmentable allocation other allocation goes into the same 64k "not defragmentable" page. Not like with SGI design that a 8k kernel stack could be allocated in the first 64k page, and then another 8k stack could be allocated in the next 64k page, effectively pinning all 64k pages until Nick worst case scenario triggers.

In practice, it's pretty difficult to trigger. Buddy allocators always try and use the smallest possible sized buddy to split. Once a 64K is split for a 4K or 8K allocation, the remainder of that block will be used for other 4K, 8K, 16K, 32K allocations. The situation where multiple 64K blocks gets split does not occur.

Quoted 6 lines

Now, the worst case scenario for your patch is that a hostile process allocates large amount of memory and mlocks() one 4K page per 64K chunk (this is unlikely in practice I know). The end result is you have many 64KB regions that are now unusable because 4K is pinned in each of them. Your approach is not immune from problems either. To me, only Nicks approach is bullet-proof in the long run.

One important thing I think in Andrea's case, the memory will be accounted for (eg. we can limit mlock, or work within various memory accounting things).

With fragmentation, I suspect it will be much more difficult to do this. It would be another layer of heuristics that will also inevitably go wrong at times if you try to limit how much "fragmentation" a process can do. Quite likely it is hard to make something even work reasonably well in most cases.

Quoted 9 lines

Quoted 3 lines

We can still try to save some memory by
defragging the slab a bit, but it's by far *not* required with config_page_shift. No defrag at all is required infact.

You will need to take some sort of defragmentation to deal with internal fragmentation. It's a very similar problem to blasting away at slab pages and still not being able to free them because objects are in use. Replace "slab" with "large page" and "object" with "4k page" and the issues are similar.

Well yes and slab has issues today too with internal fragmentation, targetted reclaim and some (small) higher order allocations too today. But at least with config_page_shift, you don't introduce _new_ sources of problems (eg. coming from pagecache or other allocs).

Sure, there are some other things -- like pagecache can actually use up more memory instead -- but there are a number of other positives that Andrea's has as well. It is using order-0 pages, which are first class throughout the VM; they have per-cpu queues, and do not require any special reclaim code. They also *actually do* reduce the page management overhead in the general case, unlike higher order pcache.

So combined with the accounting issues, I think it is unfair to say that Andrea's is just moving the fragmentation to internal. It has a number of upsides. I have no idea how it will actually behave and perform, mind you ;)

Quoted 7 lines

Quoted 6 lines

Plus there's a cost in defragging and freeing cache... the more you need defrag, the slower the kernel will be.

Quoted 1 line

approach in depth.

Well it wasn't my fault if we didn't discuss it in depth though.

Quoted 1 line

If it's my fault, sorry about that. It wasn't my intention.

I think it did get brushed aside a little quickly too (not blaming anyone). Maybe because Linus was hostile. But *if* the idea is that page management overhead has or will become a problem that needs fixing, then neither higher order pagecache, nor (obviously) fsblock, fixes this properly. Andrea's most definitely has the potential to.

Hi,

I think that fundamental problem is no fragmentation/large pages/...

The problem is the VM itself.
The vm doesn't use virtual memory, thats all, that the problem. Although this will be probably linux 3.0, I think that the right way to solve all those problems is to make all kernel memory vmalloced (except few areas like kernel .text)

It will suddenly remove the buddy allocator, it will remove need for highmem, it will allow to allocate any amount of memory (for example 4k stacks will be obsolete)
It will even allow kernel memory to be swapped to disk.

This is the solution, but it is very very hard.

Quoted 18 lines · Andrea Arcangeli

Quoted 10 lines · Mel Gorman

Quoted 2 lines

that increasing the pagesize like what Andrea suggested would lead to internal fragmentation problems. Regrettably we didn't discuss Andrea's

The config_page_shift guarantees the kernel stacks or whatever not defragmentable allocation other allocation goes into the same 64k "not defragmentable" page. Not like with SGI design that a 8k kernel stack could be allocated in the first 64k page, and then another 8k stack could be allocated in the next 64k page, effectively pinning all 64k pages until Nick worst case scenario triggers.

In practice, it's pretty difficult to trigger. Buddy allocators always try and use the smallest possible sized buddy to split. Once a 64K is split for a 4K or 8K allocation, the remainder of that block will be used for other 4K, 8K, 16K, 32K allocations. The situation where multiple 64K blocks gets split does not occur.

Quoted 6 lines

Now, the worst case scenario for your patch is that a hostile process allocates large amount of memory and mlocks() one 4K page per 64K chunk (this is unlikely in practice I know). The end result is you have many 64KB regions that are now unusable because 4K is pinned in each of them. Your approach is not immune from problems either. To me, only Nicks approach is bullet-proof in the long run.

One important thing I think in Andrea's case, the memory will be accounted for (eg. we can limit mlock, or work within various memory accounting things).

With fragmentation, I suspect it will be much more difficult to do this. It would be another layer of heuristics that will also inevitably go wrong at times if you try to limit how much "fragmentation" a process can do. Quite likely it is hard to make something even work reasonably well in most cases.

Quoted 9 lines

Quoted 3 lines

We can still try to save some memory by
defragging the slab a bit, but it's by far *not* required with config_page_shift. No defrag at all is required infact.

You will need to take some sort of defragmentation to deal with internal fragmentation. It's a very similar problem to blasting away at slab pages and still not being able to free them because objects are in use. Replace "slab" with "large page" and "object" with "4k page" and the issues are similar.

Well yes and slab has issues today too with internal fragmentation, targetted reclaim and some (small) higher order allocations too today. But at least with config_page_shift, you don't introduce _new_ sources of problems (eg. coming from pagecache or other allocs).

Sure, there are some other things -- like pagecache can actually use up more memory instead -- but there are a number of other positives that Andrea's has as well. It is using order-0 pages, which are first class throughout the VM; they have per-cpu queues, and do not require any special reclaim code.

They also *actually do* reduce the page
management overhead in the general case, unlike higher order pcache.

So combined with the accounting issues, I think it is unfair to say that Andrea's is just moving the fragmentation to internal. It has a number of upsides. I have no idea how it will actually behave and perform, mind you ;)

Quoted 8 lines

Quoted 7 lines

Plus there's a cost in defragging and freeing cache... the more you need defrag, the slower the kernel will be.

Quoted 1 line

approach in depth.

Well it wasn't my fault if we didn't discuss it in depth though.

Quoted 1 line

If it's my fault, sorry about that. It wasn't my intention.

I think it did get brushed aside a little quickly too (not blaming anyone). Maybe because Linus was hostile. But *if* the idea is that page management overhead has or will become a problem that needs fixing, then neither higher order pagecache, nor (obviously) fsblock, fixes this properly. Andrea's most definitely has the potential to.

Now, the worst case scenario for your patch is that a hostile process allocates large amount of memory and mlocks() one 4K page per 64K chunk (this is unlikely in practice I know). The end result is you have many 64KB regions that are now unusable because 4K is pinned in each of them.

If it's my fault, sorry about that. It wasn't my intention.

heh. Well we need to come to some sort of conclusion here or this will go around the merri-go-round till we're all bald.

heh, I suggested printing the warning because I knew it had this problem. The purpose in my mind was to see how far the design could be brought before fs-block had to fill in the holes.

I am still failing to see what happens when there are pagetable pages, slab objects or mlocked 4k pages pinning the 64K pages and you need to allocate another 64K page for the filesystem. I *think* you deadlock in a similar fashion to Christoph's approach but the shape of the problem is different because we are dealing with internal instead of external fragmentation. Am I wrong?

Yes. I just think you have a different worst case that is just as bad.

small files (you need something like Shaggy's page tail packing), pagetable pages, pte pages all have to be dealt with. These are the things I think will cause us internal fragmentaiton problems.

The the problem with the slub fragmentation isn't a new problem, it happens in today kernels as well and at least the slab by design is meant to _defrag_ internally. So it's practically already solved and it provides some guarantee unlike the buddy allocator.

What I think you're missing is that for Nick's worst case to trigger with the config_page_shift design, you would need the _whole_ ram to be _at_least_once_ allocated completely in kernel stacks. If the whole 100% of ram wouldn't go allocated in slub as a pure kernel stack, such a scenario could never materialize.

But the whole point is that with the config_page_shift, Nick's worst case scenario can't happen by design regardless of defrag or not defrag. While it can _definitely_ happen with SGI design (regardless of any defrag thing). We can still try to save some memory by defragging the slab a bit, but it's by far *not* required with config_page_shift. No defrag at all is required infact.

Let's see how good the mmap support for variable order page size will work after the 2 weeks...

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit. I don't know if those people had gone through the math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

If you don't consider that is a problem because you don't care about theoretical issues or nobody has reported it from running -mm

kernels, then I simply can't argue against that on a technical basis. But I'm totally against introducing known big fundamental problems to the VM at this stage of the kernel. God knows how long it takes to ever fix them in future after they have become pervasive throughout the kernel.

IMO the only thing that higher order pagecache is good for is a quick hack for filesystems to support larger block sizes. And after seeing it is fairly ugly to support mmap, I'm not even really happy for it to do that.

If VM scalability is a problem, then it needs to be addressed in other areas anyway for order-0 pages, and if contiguous pages helps IO scalability or crappy hardware, then there is nothing stopping us from

*attempting* to get contiguous memory in the current scheme.

Basically, if you're placing your hopes for VM and IO scalability on this, then I think that's a totally broken thing to do and will end up making the kernel worse in the years to come (except maybe on some poor configurations of bad hardware).

Furthermore all the issues with writeprotect faults over MAP_PRIVATE regions will have to be addressed the same way with both approaches if we want real 100% 4k-granular backwards compatibility.

And if I'm terribly wrong and the variable order pagecache is the way to go for the long run, the 64k tlb feature will fit in that model very nicely too.

Quoted 10 lines · Christoph Lameter

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit. I don't know if those people had gone through the math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

Quoted 12 lines · Nick Piggin

Quoted 10 lines · Christoph Lameter

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The
variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

Quoted 7 lines

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit. I don't know if those people had gone through the math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

While I agree with your concern, those numbers are quite silly. The

chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision. I don't see anyone abandoning git or rsync, so your extreme example clearly is the wrong one.

Again, I agree with your concern, even though your example makes it look silly.

Quoted 21 lines · Jörn Engel

Quoted 19 lines · Nick Piggin

Quoted 10 lines · Christoph Lameter

5. VM scalability
Large block sizes mean less state keeping for the information being transferred. For a 1TB file one needs to handle 256 million page structs in the VM if one uses 4k page size. A 64k page size reduces that amount to 16 million. If the limitation in existing filesystems are removed then even higher reductions become possible. For very large files like that a page size of 2 MB may be beneficial which will reduce the number of page struct to handle to 512k. The
variable nature of the block size means that the size can be tuned at file system creation time for the anticipated needs on a volume.

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit. I don't know if those people had gone through the math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

Quoted 1 line

While I agree with your concern, those numbers are quite silly. The

They are the theoretical worst case. Obviously with a non trivially sized system and non-DoS workload, they will not be reached.

Quoted 7 lines

chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision. I don't see anyone abandoning git or rsync, so your extreme example clearly is the wrong one.

Again, I agree with your concern, even though your example makes it look silly.

It is not simply a question of once-off chance for an all-at-once layout to fail in this way. Fragmentation slowly builds over time, and especially if you do actually use higher-order pages for a significant number of things (unlike we do today), then the problem will become worse. If you have any part of your workload that is affected by fragmentation, then it will cause unfragmented regions to eventually be used for fragmentation inducing allocations (by definition -- if it did not, eg. then there would be no fragmentation problem and no need for Mel's patches).

=64k only. This should be configurable via sys.

I don't know what happens as time tends towards infinity, but I don't think it will be good.

At millions of allocations per second, how long does it take to produce an unacceptable number of free pages before the ENOMEM condition? Furthermore, what *is* an unacceptable number? I don't know. I am not trying to push this feature in, so the burden is not mine to make sure it is OK.

Yes, we already have some of these problems today. Introducing more and worse problems and justifying them because of existing ones is much more silly than my quoting of the numbers. IMO.

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision. I don't see anyone abandoning git or rsync, so your extreme example clearly is the wrong one.

Again, I agree with your concern, even though your example makes it look silly.

You may want to consider Mel's antifrag approaches which certainly decreases the chance of this occurring. Reclaim can open up the needed linear memory hole in a intentional way. The memory compaction approach can even move pages to open up these 2M holes. The more pages we make movable (see f.e. the targeted slab reclaim patchset that makes slab pages movable) the more reliable higher order allocations become.

What I'm starting to wonder about is where your approach has advantages over Andrea's. The chances of triggering something vaguely similar to Nick's worst case scenario are certainly higher for your solution. So unless there are other upsides it is just the second-best solution.

The advantages of this approach over Andreas is basically that the 4k filesystems still can be used as is. 4k is useful for binaries and for

Quoted 2 lines · Christoph Lameter

The advantages of this approach over Andreas is basically that the 4k filesystems still can be used as is. 4k is useful for binaries and for

If you mean that with my approach you can't use a 4k filesystem as is, that's not correct. I even run the (admittedly premature but promising) benchmarks on my patch on a 4k blocksized filesystem... Guess what, you can even still mount a 1k fs on a 2.6 kernel.

The main advantage I can see in your patch is that distributions won't need to ship a 64k PAGE_SIZE kernel rpm (but your single rpm will be slower).

I would think that your approach would be slower since you always have to populate 1 << N ptes when mmapping a file? Plus there is a lot of wastage

of memory because even a file with one character needs an order N page? So there are less pages available for the same workload.

Then you are breaking mmap assumptions of applications becaused the order N kernel will no longer be able to map 4k pages. You likely need a new binary format that has pages correctly aligned. I know that we would need one on IA64 if we go beyond the established page sizes.

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Quoted 4 lines · On Tue, 11 Sep 2007 14:12:26 +0200 Jörn Engel <[email protected]> wrote:

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Actually it'd be pretty easy to craft an application which allocates seven pages for pagecache, then one for <something>, then seven for pagecache, then one for <something>, etc.

I've had test apps which do that sort of thing accidentally. The result wasn't pretty.

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows

Quoted 2 lines · Goswin von Brederlow

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows

That's incidentally exactly what the slab does, no need to reinvent the wheel for that, it's an old problem and there's room for optimization in the slab partial-reuse logic too. Just boost the order 0 page size and use the slab to get the 4k chunks. The sgi/defrag design is backwards.

How does that help? Will slabs move objects around to combine two

partially filled slabs into nearly full one? If not consider this:

- You create a slab for 4k objects based on 64k compound pages. (first of all that wastes you a page already for the meta infos)

- Something movable allocates a 14 4k page in there making the slab partially filled.

- Something unmovable alloactes a 4k page making the slab mixed and full.

- Repeat until out of memory.

- Userspace allocates a lot of memory in those slabs.

- Userspace frees one in every 15 4k chunks.

- Userspace forks 1000 times causing an unmovable task structure to appear in 1000 slabs.

Quoted 1 line · Goswin von Brederlow

- Userspace allocates a lot of memory in those slabs.

If with slabs you mean slab/slub, I can't follow, there has never been a single byte of userland memory allocated there since ever the slab existed in linux.

Quoted 6 lines · Andrea Arcangeli

Quoted 1 line · Goswin von Brederlow

- Userspace allocates a lot of memory in those slabs.

If with slabs you mean slab/slub, I can't follow, there has never been a single byte of userland memory allocated there since ever the slab existed in linux.

This and other comments in your reply show me that you completly misunderstood what I was talking about.

Look at
http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg

The red dots (pinned) are dentries, page tables, kernel stacks, whatever kernel stuff, right?

The green dots (movable) are mostly userspace pages being mapped there, right?

What I was refering too is that because movable objects (green dots) aren't moved out of a mixed group (the boxes) when some unmovable object needs space all the groups become mixed over time. That means the unmovable objects are spread out over all the ram and the buddy system can't recombine regions when unmovable objects free them. There will nearly always be some movable objects in the other buddy. The system of having unmovable and movable groups breaks down and becomes useless.

I'm assuming here that we want the possibility of larger order pages for unmovable objects (large continiuos regions for DMA for example) than the smallest order user space gets (or any movable object). If mmap() still works on 4k page bounaries then those will fragment all regions into 4k chunks in the worst case.

Obviously if userspace has a minimum order of 64k chunks then it will never break any region smaller than 64k chunks and will never cause a fragmentation catastroph. I know that is verry roughly your aproach (make order 0 bigger), and I like it, but it has some limits as to how

big you can make it. I don't think my system with 1GB ram would work so well with 2MB order 0 pages. But I wasn't refering to that but to the picture.

Quoted 9 lines

Quoted 6 lines · Andrea Arcangeli

Quoted 1 line · Goswin von Brederlow

- Userspace allocates a lot of memory in those slabs.

If with slabs you mean slab/slub, I can't follow, there has never been a single byte of userland memory allocated there since ever the slab existed in linux.

Quoted 5 lines

This and other comments in your reply show me that you completly misunderstood what I was talking about.

Look at
http://www.skynet.ie/~mel/anti-frag/2007-02-28/page_type_distribution.jpg

What does the large square represent here? A "largepage"? If yes, which order? There seem to be quite some pixels in each square...

Quoted 5 lines

The red dots (pinned) are dentries, page tables, kernel stacks, whatever kernel stuff, right?

The green dots (movable) are mostly userspace pages being mapped there, right?

If the largepage is the square, there can't be red pixels mixed with green pixels with the config-page-shift design, this is the whole difference...

zooming in I see red pixels all over the squares mized with green pixels in the same square. This is exactly what happens with the variable order page cache and that's why it provides zero guarantees in terms of how much ram is really "free" (free as in "available").

Quoted 8 lines

What I was refering too is that because movable objects (green dots) aren't moved out of a mixed group (the boxes) when some unmovable object needs space all the groups become mixed over time. That means the unmovable objects are spread out over all the ram and the buddy system can't recombine regions when unmovable objects free them. There will nearly always be some movable objects in the other buddy. The system of having unmovable and movable groups breaks down and becomes useless.

If I understood correctly, here you agree that mixing movable and unmovable objects in the same largepage is a bad thing, and that's incidentally what config-page-shift prevents. It avoids it instead of undoing the mixture later with defrag when it's far too late for anything but updatedb.

Quoted 5 lines

I'm assuming here that we want the possibility of larger order pages for unmovable objects (large continiuos regions for DMA for example) than the smallest order user space gets (or any movable object). If mmap() still works on 4k page bounaries then those will fragment all regions into 4k chunks in the worst case.

With config-page-shift mmap works on 4k chunks but it's always backed by 64k or any other largesize that you choosed at compile time. And if the virtual alignment of mmap matches the physical alignment of the physical largepage and is >= PAGE_SIZE (software PAGE_SIZE I mean) we could use the 62nd bit of the pte to use a 64k tlb (if future cpus will allow that). Nick also suggested to still set all ptes equal to make life easier for the tlb miss microcode.

Quoted 4 lines

Obviously if userspace has a minimum order of 64k chunks then it will never break any region smaller than 64k chunks and will never cause a fragmentation catastroph. I know that is verry roughly your aproach (make order 0 bigger), and I like it, but it has some limits as to how

Yep, exactly this is what happens, it avoids that trouble. But as far as fragmentation guarantees goes, it's really about keeping the unmovable out of our way (instead of spreading the unmovable all over the buddy randomly, or with ugly boot-time-fixed-numbers-memory-reservations) than to map largepages in userland. Infact as I said we could map kmalloced 4k entries in userland to save memory if we would really want to hurt the fast paths to make a generic kernel to use on smaller systems, but that would be very complex. Since those 4k entries would be 100% movable (not like the rest of the slab, like dentries and inodes etc..) that wouldn't make the design less reliable, it'd still be 100% reliable and performance would be ok because that memory is userland memory, we've to set the pte anyway, regardless if it's a 4k page or a largepage.

Quoted 3 lines

big you can make it. I don't think my system with 1GB ram would work so well with 2MB order 0 pages. But I wasn't refering to that but to the picture.

Sure! 2M is sure way excessive for a 1G system, 64k most certainly too, of course unless you're running a db or a multimedia streaming service, in which case it should be ideal.

On (16/09/07 17:08), Andrea Arcangeli didst pronounce:

Quoted 5 lines

zooming in I see red pixels all over the squares mized with green pixels in the same square. This is exactly what happens with the variable order page cache and that's why it provides zero guarantees in terms of how much ram is really "free" (free as in "available").

This picture is not grouping pages by mobility so that is hardly a suprise. This picture is not running grouping pages by mobility. This is what the normal kernel looks like. Look at the videos in
http://www.skynet.ie/~mel/anti-frag/2007-02-28 and see how list-based compares to vanilla. These are from February when there was less control over mixing blocks than there is today.

In the current version mixing occurs in the lower blocks as much as possible not the upper ones. So there are a number of mixed blocks but the number is kept to a minimum.

The number of mixed blocks could have been enforced as 0, but I felt it was better in the general case to fragment rather than regress performance. That may be different for large blocks where you will want to take the enforcement steps.

Quoted 2 lines

With config-page-shift mmap works on 4k chunks but it's always backed by 64k or any other largesize that you choosed at compile time. And if

Quoted 5 lines

the virtual alignment of mmap matches the physical alignment of the physical largepage and is >= PAGE_SIZE (software PAGE_SIZE I mean) we could use the 62nd bit of the pte to use a 64k tlb (if future cpus will allow that). Nick also suggested to still set all ptes equal to make life easier for the tlb miss microcode.

Quoted 7 lines

Quoted 3 lines

big you can make it. I don't think my system with 1GB ram would work so well with 2MB order 0 pages. But I wasn't refering to that but to the picture.

Sure! 2M is sure way excessive for a 1G system, 64k most certainly too, of course unless you're running a db or a multimedia streaming service, in which case it should be ideal.

Quoted 14 lines · [email protected] (Mel Gorman) writes:

On (16/09/07 17:08), Andrea Arcangeli didst pronounce:

Quoted 5 lines

zooming in I see red pixels all over the squares mized with green pixels in the same square. This is exactly what happens with the variable order page cache and that's why it provides zero guarantees in terms of how much ram is really "free" (free as in "available").

This picture is not grouping pages by mobility so that is hardly a suprise. This picture is not running grouping pages by mobility. This is what the normal kernel looks like. Look at the videos in
http://www.skynet.ie/~mel/anti-frag/2007-02-28 and see how list-based compares to vanilla. These are from February when there was less control over mixing blocks than there is today.

Quoted 8 lines

In the current version mixing occurs in the lower blocks as much as possible not the upper ones. So there are a number of mixed blocks but the number is kept to a minimum.

The number of mixed blocks could have been enforced as 0, but I felt it was better in the general case to fragment rather than regress performance. That may be different for large blocks where you will want to take the enforcement steps.

I agree that 0 is a bad value. But so is infinity. There should be some mixing but not a lot. You say "kept to a minimum". Is that actively done or already happens by itself. Hopefully the later which would be just splendid.

Quoted 2 lines

Quoted 2 lines

With config-page-shift mmap works on 4k chunks but it's always backed by 64k or any other largesize that you choosed at compile time. And if

But would mapping a random 4K page out of a file then consume 64k? That sounds like an awfull lot of internal fragmentation. I hope the unaligned bits and pices get put into a slab or something as you suggested previously.

Quoted 5 lines

Quoted 5 lines

the virtual alignment of mmap matches the physical alignment of the physical largepage and is >= PAGE_SIZE (software PAGE_SIZE I mean) we could use the 62nd bit of the pte to use a 64k tlb (if future cpus will allow that). Nick also suggested to still set all ptes equal to make life easier for the tlb miss microcode.

It is too bad that existing amd64 CPUs only allow such large physical pages. But it kind of makes sense to cut away a full level or page tables for the next bigger size each.

Quoted 7 lines

Quoted 7 lines

Quoted 3 lines

big you can make it. I don't think my system with 1GB ram would work so well with 2MB order 0 pages. But I wasn't refering to that but to the picture.

Sure! 2M is sure way excessive for a 1G system, 64k most certainly too, of course unless you're running a db or a multimedia streaming service, in which case it should be ideal.

rtorrent, Xemacs/gnus, bash, xterm, zsh, make, gcc, galeon and the ocasional mplayer.

I would mostly be concerned how rtorrents totaly random access of mmapped files negatively impacts such a 64k page system.

Movable? I rather assume all slab allocations aren't movable. Then slab defrag can try to tackle on users like dcache and inodes. Keep in mind that with the exception of updatedb, those inodes/dentries will be pinned and you won't move them, which is why I prefer to consider them not movable too... since there's no guarantee they are.

I have been toying with the idea of having seperate caches for pinned and movable dentries. Downside of such a patch would be the number of memcpy() operations when moving dentries from one cache to the other.

Quoted 4 lines · Jörn Engel

I have been toying with the idea of having seperate caches for pinned and movable dentries. Downside of such a patch would be the number of memcpy() operations when moving dentries from one cache to the other.

Totally inappropriate.

I bet 99% of all "dentry_lookup()" calls involve turning the last dentry from having a count of zero ("movable") to having a count of 1 ("pinned").

So such an approach would fundamentally be broken. It would slow down all normal dentry lookups, since the *common* case for leaf dentries is that they have a zero count.

So it's much better to do it on a "directory/file" basis, on the assumption that files are *mostly* movable (or just freeable). The fact that they aren't always (ie while kept open etc), is likely statistically not all that important.

My approach is to have one for mount points and ramfs/tmpfs/sysfs/etc. which are pinned for their entire lifetime and another for regular files/inodes. One could take a three-way approach and have always-pinned, often-pinned and rarely-pinned.

We won't get never-pinned that way.

Quoted 7 lines · Jörn Engel

My approach is to have one for mount points and ramfs/tmpfs/sysfs/etc. which are pinned for their entire lifetime and another for regular files/inodes. One could take a three-way approach and have always-pinned, often-pinned and rarely-pinned.

We won't get never-pinned that way.

That sounds pretty good. The problem, of course, is that most of the time, the actual dentry allocation itself is done before you really know which case the dentry will be in, and the natural place for actually giving the dentry lifetime hint is *not* at "d_alloc()", but when we "instantiate" it with d_add() or d_instantiate().

But it turns out that most of the filesystems we care about already use a special case of "d_add()" that *already* replaces the dentry with another one in some cases: "d_splice_alias()".

So I bet that if we just taught "d_splice_alias()" to look at the inode, and based on the inode just re-allocate the dentry to some other slab cache, we'd already handle a lot of the cases!

And yes, you'd end up with the reallocation overhead quite often, but at least it would now happen only when filling in a dentry, not in the (*much* more critical) cached lookup path.

Linus

Quoted 7 lines · Jörn Engel

My approach is to have one for mount points and ramfs/tmpfs/sysfs/etc. which are pinned for their entire lifetime and another for regular files/inodes. One could take a three-way approach and have always-pinned, often-pinned and rarely-pinned.

We won't get never-pinned that way.

That sounds pretty good. The problem, of course, is that most of the time, the actual dentry allocation itself is done before you really know which case the dentry will be in, and the natural place for actually giving the dentry lifetime hint is *not* at "d_alloc()", but when we "instantiate" it with d_add() or d_instantiate().

[...]

And yes, you'd end up with the reallocation overhead quite often, but at least it would now happen only when filling in a dentry, not in the (*much* more critical) cached lookup path.

Quoted 6 lines · Andrea Arcangeli

Movable? I rather assume all slab allocations aren't movable. Then slab defrag can try to tackle on users like dcache and inodes. Keep in mind that with the exception of updatedb, those inodes/dentries will be pinned and you won't move them, which is why I prefer to consider them not movable too... since there's no guarantee they are.

I have been toying with the idea of having seperate caches for pinned and movable dentries. Downside of such a patch would be the number of memcpy() operations when moving dentries from one cache to the other. Upside is that a fair amount of slab cache can be made movable. memcpy() is still faster than reading an object from disk.

Most likely the current reaction to such a patch would be to shoot it down due to overhead, so I didn't pursue it. All I have is an old patch to seperate never-cached from possibly-cached dentries. It will increase the odds of freeing a slab, but provide no guarantee.

But the point here is: dentries/inodes can be made movable if there are clear advantages to it. Maybe they should?

Jörn

How probable is it that the dentry is needed again? If you copy it and it is not needed then you wasted time. If you throw it out and it is needed then you wasted time too. Depending on the probability one of the two is cheaper overall. Idealy I would throw away dentries that haven't been accessed recently and copy recently used ones.

How much of a systems ram is spend on dentires? How much on task structures? Does anyone have some stats on that? If it is <10% of the total ram combined then I don't see much point in moving them. Just keep them out of the way of users memory so the buddy system can work effectively.

Quoted 2 lines

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows

That's incidentally exactly what the slab does, no need to reinvent the wheel for that, it's an old problem and there's room for optimization in the slab partial-reuse logic too.

Just boost the order
0 page size and use the slab to get the 4k chunks. The sgi/defrag design is backwards.

Except now as I've repeatadly pointed out, you have internal fragmentation problems. If we went with the SLAB, we would need 16MB slabs on PowerPC for example to get the same sort of results and a lot of copying and moving when

a suitable slab page was not available.

Quoted 3 lines

Except now as I've repeatadly pointed out, you have internal fragmentation problems. If we went with the SLAB, we would need 16MB slabs on PowerPC for example to get the same sort of results and a lot of copying and moving when

Well not sure about the 16MB number, since I'm unsure what the size of the ram was.

But clearly I agree there are fragmentation issues in the slab too, there have always been, except they're much less severe, and the slab is meant to deal with that regardless of the PAGE_SIZE. That is not a new problem, you are introducing a new problem instead.

We can do a lot better than slab currently does without requiring any defrag move-or-shrink at all.

slab is trying to defrag memory for small objects at nearly zero cost, by not giving pages away randomly. I thought you agreed that solving the slab fragmentation was going to provide better guarantees when in

another email you suggested that you could start allocating order > 0 pages in the slab to reduce the fragmentation (to achieve most of the guarantee provided by config-page-shift, but while still keeping the order 0 at 4k for whatever reason I can't see).

Quoted 1 line

a suitable slab page was not available.

You ignore one other bit, when "/usr/bin/free" says 1G is free, with config-page-shift it's free no matter what, same goes for not mlocked cache. With variable order page cache, /usr/bin/free becomes mostly a lie as long as there's no 4k fallback (like fsblock).

And most important you're only tackling on the pagecache and I/O performance with the inefficient I/O devices, the whole kernel has no cahnce to get a speedup, infact you're making the fast paths slower, just the opposite of config-page-shift and original Hugh's large PAGE_SIZE ;).

The 16MB is the size of a hugepage, the size of interest as far as I am concerned. Your idea makes sense for large block support, but much less for huge pages because you are incurring a cost in the general case for something that may not be used.

There is nothing to say that both can't be done. Raise the size of order-0 for large block support and continue trying to group the block to make hugepage allocations likely succeed during the lifetime of the system.

At the risk of repeating, your approach will be adding a new and significant dimension to the internal fragmentation problem where a kernel allocation may fail because the larger order-0 pages are all being pinned by userspace pages.

It improves the probabilty of hugepage allocations working because the blocks with slab pages can be targetted and cleared if necessary.

That suggestion was aimed at the large block support more than hugepages. It helps large blocks because we'll be allocating and freeing as more or less the same size. It certainly is easier to set slub_min_order to the same size as what is needed for large blocks in the system than introducing the necessary mechanics to allocate pagetable pages and userspace pages from slab.

I'm not sure what you are getting at here. I think it would make more sense if you said "when you read /proc/buddyinfo, you know the order-0 pages are really free for use with large blocks" with your approach.

All this aside, there is nothing mutually exclusive with what you are proposing and what grouping pages by mobility does. Your stuff can exist even if grouping pages by mobility is in place. In fact, it'll help us by giving an important comparison point as grouping pages by mobility can be trivially disabled with a one-liner for the purposes of testing. If your approach is brought to being a general solution that also helps hugepage allocation, then we can revisit grouping pages by mobility by comparing kernels with it enabled and without.

Quoted 4 lines

The 16MB is the size of a hugepage, the size of interest as far as I am concerned. Your idea makes sense for large block support, but much less for huge pages because you are incurring a cost in the general case for something that may not be used.

Sorry for the misunderstanding, I totally agree!

Quoted 4 lines

There is nothing to say that both can't be done. Raise the size of order-0 for large block support and continue trying to group the block to make hugepage allocations likely succeed during the lifetime of the system.

Sure, I completely agree.

Quoted 4 lines

At the risk of repeating, your approach will be adding a new and significant dimension to the internal fragmentation problem where a kernel allocation may fail because the larger order-0 pages are all being pinned by userspace pages.

This is exactly correct, some memory will be wasted. It'll reach 0 free memory more quickly depending on which kind of applications are being run.

Quoted 2 lines

It improves the probabilty of hugepage allocations working because the blocks with slab pages can be targetted and cleared if necessary.

Agreed.

Quoted 6 lines

That suggestion was aimed at the large block support more than hugepages. It helps large blocks because we'll be allocating and freeing as more or less the same size. It certainly is easier to set slub_min_order to the same size as what is needed for large blocks in the system than introducing the necessary mechanics to allocate pagetable pages and userspace pages from slab.

Allocating userpages from slab in 4k chunks with a 64k PAGE_SIZE is really complex indeed. I'm not planning for that in the short term but it remains a possibility to make the kernel more generic. Perhaps it could worth it...

Allocating ptes from slab is fairly simple but I think it would be better to allocate ptes in PAGE_SIZE (64k) chunks and preallocate the nearby ptes in the per-task local pagetable tree, to reduce the number of locks taken and not to enter the slab at all for that.

Infact we
could allocate the 4 levels (or anyway more than one level) in one single alloc_pages(0) and track the leftovers in the mm (or similar).

Quoted 3 lines

I'm not sure what you are getting at here. I think it would make more sense if you said "when you read /proc/buddyinfo, you know the order-0 pages are really free for use with large blocks" with your approach.

I'm unsure who reads /proc/buddyinfo (that can change a lot and that is not very significant information if the vm can defrag well inside the reclaim code),

but it's not much different and it's more about
knowing the real meaning of /proc/meminfo, freeable (unmapped) cache, anon ram, and free memory.

The idea is that to succeed an mmap over a large xfs file with mlockall being invoked, those largepages must become available or it'll be oom despite there are still 512M free... I'm quite sure admins will gets confused if they get oom killer invoked with lots of ram still free.

The overcommit feature will also break, just to make an example (so much for overcommit 2 guaranteeing -ENOMEM retvals instead of oom killage ;).

Quoted 7 lines

All this aside, there is nothing mutually exclusive with what you are proposing and what grouping pages by mobility does. Your stuff can exist even if grouping pages by mobility is in place. In fact, it'll help us by giving an important comparison point as grouping pages by mobility can be trivially disabled with a one-liner for the purposes of testing. If your approach is brought to being a general solution that also helps hugepage allocation, then we can revisit grouping pages by mobility by comparing kernels with it enabled and without.

Yes, I totally agree. It sounds worthwhile to have a good defrag logic in the VM. Even allocating the kernel stack in today kernels should be able to benefit from your work. It's just comparing a fork() failure (something that will happen with ulimit -n too and that apps must be able to deal with) with an I/O failure that worries me a bit.

I'm
quite sure a db failing I/O will not recover too nicely. If fork fails that's most certainly ok... at worst a new client won't be able to connect and he can retry later. Plus order 1 isn't really a big deal, you know the probability to succeeds decreases exponentially with the order.

On (16/09/07 23:31), Andrea Arcangeli didst pronounce:

Quoted 5 lines · Mel Gorman

Allocating ptes from slab is fairly simple but I think it would be better to allocate ptes in PAGE_SIZE (64k) chunks and preallocate the nearby ptes in the per-task local pagetable tree, to reduce the number of locks taken and not to enter the slab at all for that.

It runs the risk of pinning up to 60K of data per task that is unusable for any other purpose. On average, it'll be more like 32K but worth keeping in mind.

Quoted 3 lines

Infact we
could allocate the 4 levels (or anyway more than one level) in one single alloc_pages(0) and track the leftovers in the mm (or similar).

You ignore one other bit, when "/usr/bin/free" says 1G is free, with config-page-shift it's free no matter what, same goes for not mlocked cache. With variable order page cache, /usr/bin/free becomes mostly a lie as long as there's no 4k fallback (like fsblock).

When has free ever given any usefull "free" number? I can perfectly fine allocate another gigabyte of memory despide free saing 25MB. But that is because I know that the buffer/cached are not locked in.

On the other hand 1GB can instantly vanish when I start a xen domain and anything relying on the free value would loose.

The only sensible thing for an application concerned with swapping is to whatch the swapping and then reduce itself. Not the amount free. Although I wish there were some kernel interface to get a preasure value of how valuable free pages would be right now. I would like that for fuse so a userspace filesystem can do caching without cripling the kernel.

Quoted 3 lines · Goswin von Brederlow

When has free ever given any usefull "free" number? I can perfectly fine allocate another gigabyte of memory despide free saing 25MB. But that is because I know that the buffer/cached are not locked in.

Well, as you said you know that buffer/cached are not locked in. If /proc/meminfo would be rubbish like you seem to imply in the first line, why would we ever bother to export that information and even waste time writing a binary that parse it for admins?

Quoted 2 lines

On the other hand 1GB can instantly vanish when I start a xen domain and anything relying on the free value would loose.

Actually you better check meminfo or free before starting a 1G of Xen!!

Quoted 6 lines

The only sensible thing for an application concerned with swapping is to whatch the swapping and then reduce itself. Not the amount free. Although I wish there were some kernel interface to get a preasure value of how valuable free pages would be right now. I would like that for fuse so a userspace filesystem can do caching without cripling the kernel.

Repeated drop caches + free can help.

As a user I know it because I didn't put a kernel source into /tmp. A programm can't reasonably know that.

Xen has its own memory pool and can quite agressively reclaim memory from dom0 when needed. I just ment to say that the number in

/proc/meminfo can change in a second so it is not much use knowing what it said last minute.

I would kill any programm that does that to find out how much free ram the system has.

Quoted 11 lines · Andrew Morton

Quoted 4 lines · On Tue, 11 Sep 2007 14:12:26 +0200 Jörn Engel <[email protected]> wrote:

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Actually it'd be pretty easy to craft an application which allocates seven pages for pagecache, then one for <something>, then seven for pagecache, then one for <something>, etc.

Quoted 2 lines

I've had test apps which do that sort of thing accidentally. The result wasn't pretty.

Except that the applications 7 pages are movable and the <something> would have to be unmovable. And then they should not share the same memory region. At least they should never be allowed to interleave in such a pattern on a larger scale.

The only way a fragmentation catastroph can be (proovable) avoided is by having so few unmovable objects that size + max waste << ram size. The smaller the better. Allowing movable and unmovable objects to mix means that max waste goes way up. In your example waste would be 7*size. With 2MB uper order limit it would be 511*size.

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows fragmentation to build up.

On (15/09/07 14:14), Goswin von Brederlow didst pronounce:

Quoted 13 lines

Quoted 11 lines · Andrew Morton

Quoted 4 lines · On Tue, 11 Sep 2007 14:12:26 +0200 Jörn Engel <[email protected]> wrote:

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Actually it'd be pretty easy to craft an application which allocates seven pages for pagecache, then one for <something>, then seven for pagecache, then one for <something>, etc.

Quoted 8 lines

Quoted 2 lines

I've had test apps which do that sort of thing accidentally. The result wasn't pretty.

Except that the applications 7 pages are movable and the <something> would have to be unmovable. And then they should not share the same memory region. At least they should never be allowed to interleave in such a pattern on a larger scale.

It is actually really easy to force regions to never share. At the moment, there is a fallback list that determines a preference for what block to mix.

The reason why this isn't enforced is the cost of moving. On x86 and x86_64, a block of interest is usually 2MB or 4MB. Clearing out one of those pages to prevent any mixing would be bad enough. On PowerPC, it's potentially 16MB. On IA64, it's 1GB.

As this was fragmentation avoidance, not guarantees, the decision was made to not strictly enforce the types of pages within a block as the cost cannot be made back unless the system was making agressive use of large pages. This is not the case with Linux.

Quoted 10 lines

The only way a fragmentation catastroph can be (proovable) avoided is by having so few unmovable objects that size + max waste << ram size. The smaller the better. Allowing movable and unmovable objects to mix means that max waste goes way up. In your example waste would be 7*size. With 2MB uper order limit it would be 511*size.

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows fragmentation to build up.

This is easily achieved, just really really expensive because of the amount of copying that would have to take place. It would also compel that min_free_kbytes be at least one free PAGEBLOCK_NR_PAGES and likely MIGRATE_TYPES * PAGEBLOCK_NR_PAGES to reduce excessive copying. That is a lot of free memory to keep around which is why fragmentation avoidance doesn't do it.

Quoted 32 lines · [email protected] (Mel Gorman) writes:

On (15/09/07 14:14), Goswin von Brederlow didst pronounce:

Quoted 13 lines

Quoted 11 lines · Andrew Morton

Quoted 4 lines · On Tue, 11 Sep 2007 14:12:26 +0200 Jörn Engel <[email protected]> wrote:

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Actually it'd be pretty easy to craft an application which allocates seven pages for pagecache, then one for <something>, then seven for pagecache, then one for <something>, etc.

Quoted 8 lines

Quoted 2 lines

I've had test apps which do that sort of thing accidentally. The result wasn't pretty.

Except that the applications 7 pages are movable and the <something> would have to be unmovable. And then they should not share the same memory region. At least they should never be allowed to interleave in such a pattern on a larger scale.

It is actually really easy to force regions to never share. At the moment, there is a fallback list that determines a preference for what block to mix.

The reason why this isn't enforced is the cost of moving. On x86 and x86_64, a block of interest is usually 2MB or 4MB. Clearing out one of those pages to prevent any mixing would be bad enough. On PowerPC, it's potentially 16MB. On IA64, it's 1GB.

Quoted 4 lines

As this was fragmentation avoidance, not guarantees, the decision was made to not strictly enforce the types of pages within a block as the cost cannot be made back unless the system was making agressive use of large pages. This is not the case with Linux.

I don't say the group should never be mixed. The movable objects could be moved out on demand. If 64k get allocated then up to 64k get moved.

That would reduce the impact as the kernel does not hang while it moves 2MB or even 1GB. It also allows objects to be freed and the space reused in the unmovable and mixed groups. There could also be a certain number or percentage of mixed groupd be allowed to further increase the chance of movable objects freeing themself from mixed groups.

But when you already have say 10% of the ram in mixed groups then it is a sign the external fragmentation happens and some time should be spend on moving movable objects.

Quoted 11 lines

Quoted 10 lines

The only way a fragmentation catastroph can be (proovable) avoided is by having so few unmovable objects that size + max waste << ram size. The smaller the better. Allowing movable and unmovable objects to mix means that max waste goes way up. In your example waste would be 7*size. With 2MB uper order limit it would be 511*size.

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows fragmentation to build up.

Quoted 6 lines

This is easily achieved, just really really expensive because of the amount of copying that would have to take place. It would also compel that min_free_kbytes be at least one free PAGEBLOCK_NR_PAGES and likely MIGRATE_TYPES * PAGEBLOCK_NR_PAGES to reduce excessive copying. That is a lot of free memory to keep around which is why fragmentation avoidance doesn't do it.

In your sample graphics you had 1152 groups. Reserving a few of those doesnt sound too bad.

And how many migrate types do we talk about.
So
far we only had movable and unmovable.

I would split unmovable into
short term (caches, I/O pages) and long term (task structures, dentries).

Reserving 6 groups for schort term unmovable and long term unmovable would be 1% of ram in your situation.

Maybe instead of reserving one could say that you can have up to 6 groups of space

not used by unmovable objects before aggressive moving starts. I don't quite see why you NEED reserving as long as there is enough space free alltogether in case something needs moving.

1 group
worth of space free might be plenty to move stuff too. Note that all the virtual pages can be stuffed in every little free space there is and reassembled by the MMU. There is no space lost there.

But until one tries one can't say.

MfG
Goswin

PS: How do allocations pick groups?

Could one use the oldest group
dedicated to each MIGRATE_TYPE?

Or lowest address for unmovable and
highest address for movable? Something to better keep the two out of each other way.

On (16/09/07 23:58), Goswin von Brederlow didst pronounce:

Quoted 4 lines

But when you already have say 10% of the ram in mixed groups then it is a sign the external fragmentation happens and some time should be spend on moving movable objects.

I'll play around with it on the side and see what sort of results I get. I won't be pushing anything any time soon in relation to this though. For now, I don't intend to fiddle more with grouping pages by mobility for something that may or may not be of benefit to a feature that hasn't been widely tested with what exists today.

Quoted 2 lines

Maybe instead of reserving one could say that you can have up to 6 groups of space

And if the groups are 1GB in size? I tried something like this already. It didn't work out well at the time although I could revisit.

Quoted 3 lines

not used by unmovable objects before aggressive moving starts. I don't quite see why you NEED reserving as long as there is enough space free alltogether in case something needs moving.

hence, increase min_free_kbytes.

Quoted 5 lines

1 group
worth of space free might be plenty to move stuff too. Note that all the virtual pages can be stuffed in every little free space there is and reassembled by the MMU. There is no space lost there.

What you suggest sounds similar to having a type MIGRATE_MIXED where you allocate from when the preferred lists are full. It became a sizing problem that never really worked out. As I said, I can try again.

Quoted 6 lines

But until one tries one can't say.

MfG
Goswin

PS: How do allocations pick groups?

Using GFP flags to identify the type.

Quoted 2 lines

Could one use the oldest group
dedicated to each MIGRATE_TYPE?

Age is difficult to determine so probably not.

Quoted 3 lines

Or lowest address for unmovable and
highest address for movable? Something to better keep the two out of each other way.

We bias the location of unmovable and reclaimable allocations already. It's not done for movable because it wasn't necessary (as they are easily reclaimed or moved anyway).

Quoted 4 lines · [email protected] (Mel Gorman) writes:

On (16/09/07 23:58), Goswin von Brederlow didst pronounce:

Quoted 1 line

But when you already have say 10% of the ram in mixed groups then it is a sign the external fragmentation happens and some time should be spend on moving movable objects.

I'll play around with it on the side and see what sort of results I get. I won't be pushing anything any time soon in relation to this though. For now, I don't intend to fiddle more with grouping pages by mobility for something that may or may not be of benefit to a feature that hasn't been widely tested with what exists today.

I watched the videos you posted. A nice and quite clear improvement with and without your logic. Cudos.

When you play around with it may I suggest a change to the display of the memory information. I think it would be valuable to use a Hilbert Curve to arange the pages into pixels. Like this:

# # 0 3
# #
### 1 2

### ### 0 1 E F
# #
### ### 3 2 D C
# #
# ### # 4 7 8 B
# # # #
### ### 5 6 9 A

On (15/09/07 14:14), Goswin von Brederlow didst pronounce:

Quoted 3 lines

I keep coming back to the fact that movable objects should be moved out of the way for unmovable ones. Anything else just allows fragmentation to build up.

This is easily achieved, just really really expensive because of the amount of copying that would have to take place. It would also compel that min_free_kbytes be at least one free PAGEBLOCK_NR_PAGES and likely MIGRATE_TYPES * PAGEBLOCK_NR_PAGES to reduce excessive copying. That is a lot of free memory to keep around which is why fragmentation avoidance doesn't do it.

I don't know how it would prevent fragmentation from building up anyway. It's commonly the case that potentially unmovable objects are allowed to fill up all of ram (dentries, inodes, etc).

Quoted 4 lines

I don't know how it would prevent fragmentation from building up anyway. It's commonly the case that potentially unmovable objects are allowed to fill up all of ram (dentries, inodes, etc).

Not in 2.6.23 with ZONE_MOVABLE. Unmovable objects are not allocated from ZONE_MOVABLE and thus the memory that can be allocated for them is limited.

We still lack data on what sort of workloads really benefit from large blocks

We still lack data on what sort of workloads really benefit from large blocks (assuming there are any that cannot also be solved by improving order-0).

Quoted 3 lines · Nick Piggin

I don't know how it would prevent fragmentation from building up anyway. It's commonly the case that potentially unmovable objects are allowed to fill up all of ram (dentries, inodes, etc).

Not in 2.6.23 with ZONE_MOVABLE. Unmovable objects are not allocated from ZONE_MOVABLE and thus the memory that can be allocated for them is limited.

Quoted 5 lines · Christoph Lameter

Quoted 3 lines · Nick Piggin

I don't know how it would prevent fragmentation from building up anyway. It's commonly the case that potentially unmovable objects are allowed to fill up all of ram (dentries, inodes, etc).

Quoted 3 lines

Not in 2.6.23 with ZONE_MOVABLE. Unmovable objects are not allocated from ZONE_MOVABLE and thus the memory that can be allocated for them is limited.

Why would ZONE_MOVABLE require that "movable objects should be moved out of the way for unmovable ones"? It never _has_ any unmovable objects in it. Quite obviously we were not talking about reserve zones.

Quoted 4 lines · On Tue, 11 Sep 2007 14:12:26 +0200 Jörn Engel <[email protected]> wrote:

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Actually it'd be pretty easy to craft an application which allocates seven pages for pagecache, then one for <something>, then seven for pagecache, then one for <something>, etc.

I've had test apps which do that sort of thing accidentally. The result wasn't pretty.

Quoted 11 lines · On Tue, 11 Sep 2007 14:12:26 +0200 Jörn Engel <[email protected]> wrote:

Quoted 5 lines

While I agree with your concern, those numbers are quite silly. The chances of 99.8% of pages being free and the remaining 0.2% being perfectly spread across all 2MB large_pages are lower than those of SHA1 creating a collision.

Actually it'd be pretty easy to craft an application which allocates seven pages for pagecache, then one for <something>, then seven for pagecache, then one for <something>, etc.

Quoted 2 lines

I've had test apps which do that sort of thing accidentally. The result wasn't pretty.

I bet! My (false) assumption was the same as Goswin's. If non-movable pages are clearly seperated from movable ones and will evict movable ones before polluting further mixed superpages, Nick's scenario would be nearly infinitely impossible.

Assumption doesn't reflect current code. Enforcing this assumption would cost extra overhead. The amount of effort to make Christoph's approach work reliably seems substantial and I have no idea whether it would be worth it.

I bet! My (false) assumption was the same as Goswin's. If non-movable pages are clearly seperated from movable ones and will evict movable ones before polluting further mixed superpages, Nick's scenario would be nearly infinitely impossible.

Assumption doesn't reflect current code. Enforcing this assumption would cost extra overhead. The amount of effort to make Christoph's approach work reliably seems substantial and I have no idea whether it would be worth it.

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

The idea that there even _is_ a bug to fail when higher order pages cannot be allocated was also brushed aside by some people at the vm/fs summit. I don't know if those people had gone through the math about this, but it goes somewhat like this: if you use a 64K page size, you can "run out of memory" with 93% of your pages free. If you use a 2MB page size, you can fail with 99.8% of your pages still free. That's 64GB of memory used on a 32TB Altix.

Quoted 6 lines · Nick Piggin

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

Well my problem first of all is that you did not read the full message. It discusses that later and provides page pools to address the issue.

Secondly you keep FUDding people with lots of theoretical concerns assuming Mel's approaches must fail. If there is an issue (I guess there must be right?) then please give us a concrete case of a failure that we can work against.

Quoted 6 lines · Nick Piggin

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

Well my problem first of all is that you did not read the full message. It discusses that later and provides page pools to address the issue.

Secondly you keep FUDding people with lots of theoretical concerns assuming Mel's approaches must fail. If there is an issue (I guess there must be right?) then please give us a concrete case of a failure that we can work against.

Quoted 11 lines · Nick Piggin

Quoted 6 lines

There is a limitation in the VM. Fragmentation. You keep saying this is a solved issue and just assuming you'll be able to fix any cases that come up as they happen.

I still don't get the feeling you realise that there is a fundamental fragmentation issue that is unsolvable with Mel's approach.

Well my problem first of all is that you did not read the full message. It discusses that later and provides page pools to address the issue.

Quoted 4 lines

Secondly you keep FUDding people with lots of theoretical concerns assuming Mel's approaches must fail. If there is an issue (I guess there must be right?) then please give us a concrete case of a failure that we can work against.

And BTW, before you accuse me of FUD, I'm actually talking about the fragmentation issues on which Mel I think mostly agrees with me at this point.

Also have you really a rational reason why we should just up and accept all these big changes happening just because that, while there are lots of theoretical issues, the person pointing them out to you hasn't happened to give you a concrete failure case. Oh, and the actual performance benefit is actually not really even quantified yet, crappy hardware not withstanding, and neither has a proper evaluation of the alternatives.

So... would you drive over a bridge if the engineer had this mindset?