Skip to contentSkip to conversation

Page aging broken in 2.6

DISCUSSION Benjamin Herrenschmidt 11 participants 30 messages Dec 26, 2003 – Dec 28, 2003

lore
Share & tools
lore
#0 lore raw

HI !

I don't know if x86 is affected (I suspect not) but ppc and ppc64 definitely are.

in mm/rmap.c, in page_referenced(), we do that twice:

                if (ptep_test_and_clear_young(pte))
                        referenced++;

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

ppc and ppc64 need a flush to evict the entry from the hash table or we'll never set the _PAGE_ACCESSED bit anymore.

On the other hand, I'd like to propose a semantic change here, by changing ptep_test_and_clear_dirty() as well so that the flush is done by the arch function and not explicitely by the generic code in both cases. (I'm not sure if it's worth adding an mm parameter to the call or if the arch will figure it out, we don't have it at hand in page_referenced()).

That way, arch that don't need the flush (if any) can avoid it, and in the case of ptep_test_and_clear_dirty, I may have a better way of implementing it without a flush in mind.

Comments ?

Ben.

#1 lore raw
Quoted 8 lines · Benjamin Herrenschmidt

HI !

I don't know if x86 is affected (I suspect not) but ppc and ppc64 definitely are.

in mm/rmap.c, in page_referenced(), we do that twice:

Quoted 8 lines
                if (ptep_test_and_clear_young(pte))
                        referenced++;

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

x86 needs a flush_tlb_page(), yes.

Quoted 10 lines

ppc and ppc64 need a flush to evict the entry from the hash table or we'll never set the _PAGE_ACCESSED bit anymore.

On the other hand, I'd like to propose a semantic change here, by changing ptep_test_and_clear_dirty() as well so that the flush is done by the arch function and not explicitely by the generic code in both cases. (I'm not sure if it's worth adding an mm parameter to the call or if the arch will figure it out, we don't have it at hand in page_referenced()).

Quoted 3 lines

That way, arch that don't need the flush (if any) can avoid it, and in the case of ptep_test_and_clear_dirty, I may have a better way of implementing it without a flush in mind.

I don't feel particularly strongly either way, but the core mm code is sprinkled with flushes anyway; it would probably be more consistent to open-code it in rmap.c now.

#2 lore raw
Quoted 8 lines
Quoted 6 lines

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

x86 needs a flush_tlb_page(), yes.

it does? Are you 100% sure ?

Afaik x86 is very very slow in setting the A and D bits (like 2000 to 3000 cycles) *because* it doesn't need a TLB flush....

#3 lore raw
Quoted 6 lines · Arjan van de Ven
Quoted 6 lines
Quoted 5 lines

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

Quoted 6 lines
Quoted 1 line

x86 needs a flush_tlb_page(), yes.

it does? Are you 100% sure ?

Afaik x86 is very very slow in setting the A and D bits (like 2000 to 3000 cycles) *because* it doesn't need a TLB flush....

How does this work ? If x86 always update those bits even when the TLB copy has them already set, then it will keep writing to the PTEs on every access... which I doubt it does ;) Or does it snoop accesses to the PTE to "catch" somebody clearing the bits ?

Ben.

#4 lore raw
In reply to Arjan van de Ven
Quoted 10 lines · Arjan van de Ven
Quoted 8 lines
Quoted 6 lines

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

x86 needs a flush_tlb_page(), yes.

it does? Are you 100% sure ?

According to the Intel doc #24319202, section 3.7, it is OS responsibility to invalidate the TLB entry.

- Davide

#5 lore raw
In reply to Andrew Morton
Quoted 11 lines · Andrew Morton
Quoted 5 lines · Benjamin Herrenschmidt

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

x86 needs a flush_tlb_page(), yes.

Quoted 2 lines

ppc and ppc64 need a flush to evict the entry from the hash table or we'll never set the _PAGE_ACCESSED bit anymore.

ARM would strictly need the flush as well. I seem to vaguely remember, however, that when this code went in there was some discussion about this very topic, and it was decided that the flush was not critical.

Indeed, 2.4 seems to have the same logic concerning not flushing the PTE:

        /* Don't look at this pte if it's been accessed recently. */
        if ((vma->vm_flags & VM_LOCKED) || ptep_test_and_clear_young(page_table)) {
                mark_page_accessed(page);
                return 0;
        }
Signature · 4 lines
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 PCMCIA      - http://pcmcia.arm.linux.org.uk/
                 2.6 Serial core
#6 lore raw
Quoted 5 lines

ARM would strictly need the flush as well. I seem to vaguely remember, however, that when this code went in there was some discussion about this very topic, and it was decided that the flush was not critical.

Quoted 8 lines

Indeed, 2.4 seems to have the same logic concerning not flushing the PTE:

        /* Don't look at this pte if it's been accessed recently. */
        if ((vma->vm_flags & VM_LOCKED) || ptep_test_and_clear_young(page_table)) {
                mark_page_accessed(page);
                return 0;
        }

I can imagine that an architecture with TLBs will usually evict the entry from the TLB sooner or later and the accessed bit will end up beeing set again. On PPC, that isn't the case, the entry can well stay a loooong time in the hash and if not evicted, _PAGE_ACCESSED will never be set again.

Ben.

#7 lore raw
In reply to Benjamin Herrenschmidt
Quoted 11 lines · Benjamin Herrenschmidt

in mm/rmap.c, in page_referenced(), we do that twice:

                if (ptep_test_and_clear_young(pte))
                        referenced++;

And we never flush the TLB entry.

I don't know if x86 (or other archs really using page tables) will actually set the referenced bit again in the PTE if it's already set in the TLB, if not, then x86 needs a flush too.

This was very much done on purpose. The theory is, that if you're low on memory and have a lot of pages mapped, you will see enough TLB trashing for this to not matter.

And if you aren't low on memory, or don't have a lot of pages mapped, it _also_ doesn't matter.

Quoted 2 lines

ppc and ppc64 need a flush to evict the entry from the hash table or we'll never set the _PAGE_ACCESSED bit anymore.

Yeah, all hail bad MMU's.

Hash tables may need some kind of "not very urgent TLB flush" thing, so that it doesn't penalize sane architectures.

Linus

#8 lore raw
Quoted 2 lines

Yeah, all hail bad MMU's.

Bad MMUs or our architetured beeing tied to one MMU type ? :)

(Note that I'm no special fan of our PPC hash table, it seems to be fairly bad with the cache).

Note also that the need for a flush isn't tied to that fact we have a hash table but to how we use it in linux. If we used the real HW A and D bits and had ptep_test_and_clear* actually walk the hash and use them, we could avoid the flush the same way in this case.

But we do not, we use the hash as a big TLB cache and consider any page in there as accessed and any writeable page in there as diry, so clearing those bits requires evicting from the hash (hash misses, at least on ppc32, are fairly cheap though).

Quoted 2 lines

Hash tables may need some kind of "not very urgent TLB flush" thing, so that it doesn't penalize sane architectures.

Or do what I propose here, that is have ptep_test_and_clear_* be responsible for the flush on archs where it is necessary, but then it would be nice to have more than the ptep as an argument...

Ben.

#9 lore raw
Quoted 4 lines · Benjamin Herrenschmidt

Or do what I propose here, that is have ptep_test_and_clear_* be responsible for the flush on archs where it is necessary, but then it would be nice to have more than the ptep as an argument...

The dirty handling already does the TLB flush (in that case it's a correctness issue, not a hint). So it's only ptep_test_and_clear_young() that matters.

I don't know whather that ever ends up being performance-critical, and I don't see what else could be passed into it. We literally don't _have_ anythign else than the pte.

But the ppc architecture could easily decide to walk the hash tables and invalidate in ptep_test_and_clear_young(). And if it ends up being a performance issue, it _appears_ that all users of "page_referenced()" (which is the only thing that does this) are actually using the return value as just a boolean. And it's entirely possible that we should break out of "page_referenced()" on the _first_ hit of "yes, this has been referenced".

That would make it much less CPU-intensive to make "ptep_test_and_clear_young()" slightly heavier to execute. It would also cause "page_referenced()" to not clear _all_ mapped reference bits at the same time - which might unfairly cause multi-used pages to stay in memory. On the other hand, that might be the _right_ behaviour.

Rik? Andrea?

Worth testing, perhaps.

Linus

#10 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · Benjamin Herrenschmidt

Or do what I propose here, that is have ptep_test_and_clear_* be responsible for the flush on archs where it is necessary, but then it would be nice to have more than the ptep as an argument...

The dirty handling already does the TLB flush (in that case it's a correctness issue, not a hint). So it's only ptep_test_and_clear_young() that matters.

Yes, but it would be possible to optimize it some way on our beloved hash tables ;) (By marking the entry read-only in the hash instead of evicting it). Maybe not worth the pain though...

Quoted 3 lines

I don't know whather that ever ends up being performance-critical, and I don't see what else could be passed into it. We literally don't _have_ anythign else than the pte.

Ok, figured that out.

Quoted 7 lines

But the ppc architecture could easily decide to walk the hash tables and invalidate in ptep_test_and_clear_young(). And if it ends up being a performance issue, it _appears_ that all users of "page_referenced()" (which is the only thing that does this) are actually using the return value as just a boolean. And it's entirely possible that we should break out of "page_referenced()" on the _first_ hit of "yes, this has been referenced".

Except that we may expect all "referencing" PTEs to have the accessed bit cleared, no ? Or if we have lots of users we'll end up getting lots of positive results while after the page was actually referenced... I don't know if this would be a real problem though.

Quoted 9 lines

That would make it much less CPU-intensive to make "ptep_test_and_clear_young()" slightly heavier to execute. It would also cause "page_referenced()" to not clear _all_ mapped reference bits at the same time - which might unfairly cause multi-used pages to stay in memory. On the other hand, that might be the _right_ behaviour.

Rik? Andrea?

Worth testing, perhaps.

Ok, right now, Anton is testing a patch from paulus where we do our own flush batching and do the flush inside ptep_test_and_clear_* That will at least fix the problem for us now.

Ben.

#11 lore raw
Quoted 8 lines · Benjamin Herrenschmidt
Quoted 4 lines

The dirty handling already does the TLB flush (in that case it's a correctness issue, not a hint). So it's only ptep_test_and_clear_young() that matters.

Yes, but it would be possible to optimize it some way on our beloved hash tables ;) (By marking the entry read-only in the hash instead of evicting it). Maybe not worth the pain though...

I don't think you should evict it, since
- you know the value it should have
- if you do the hash lookup anyway, you might as well just update the entry.

And it's not "read-only" - it's the "A" bit, not the "W" bit you should be clearing in "ptep_test_and_clear_young()".

Quoted 4 lines

Except that we may expect all "referencing" PTEs to have the accessed bit cleared, no ? Or if we have lots of users we'll end up getting lots of positive results while after the page was actually referenced... I don't know if this would be a real problem though.

I'll let Rik and Andrea argue that part - it's entirely possible that getting lots of positive results is a _good_ thing, if the same page is mapped multiple times. That would just make us less eager to unmap it, which sounds like potentially the right thign to do (it's also how the old non-rmap code worked, and I know Rik thought it was "unfair", but whatever).

Quoted 3 lines

Ok, right now, Anton is testing a patch from paulus where we do our own flush batching and do the flush inside ptep_test_and_clear_* That will at least fix the problem for us now.

Yeah, and it's unlikely to be a performance problem anyway. That function should be called only when we're low on memory..

Linus

#12 lore raw
Quoted 3 lines · Linus Torvalds

And it's not "read-only" - it's the "A" bit, not the "W" bit you should be clearing in "ptep_test_and_clear_young()".

Oh, I see, I misparsed your comment.. you were talking about changing "ptep_test_and_clear_dirty()" too..

That's certainly possible.

Linus

#13 lore raw
In reply to Linus Torvalds
Quoted 6 lines · Linus Torvalds
Quoted 5 lines · Benjamin Herrenschmidt
Quoted 4 lines

The dirty handling already does the TLB flush (in that case it's a correctness issue, not a hint). So it's only ptep_test_and_clear_young() that matters.

Quoted 8 lines
Quoted 3 lines

Yes, but it would be possible to optimize it some way on our beloved hash tables ;) (By marking the entry read-only in the hash instead of evicting it). Maybe not worth the pain though...

I don't think you should evict it, since
- you know the value it should have
- if you do the hash lookup anyway, you might as well just update the entry.

Yup, that is my point.

Quoted 2 lines

And it's not "read-only" - it's the "A" bit, not the "W" bit you should be clearing in "ptep_test_and_clear_young()".

In the above I was talking about dirty.

For accessed, we currently do not use the HW bit neither. Accessed = in the hash, not accessed = not in the hash. A bit basic, but the cost of faulting them back in isn't that bad. Still, I always found it a bit stupid that we end up having the harvesting of accessed bits actually evict pages that _are_ accessed, and thus potentially here to be accessed again ;)

Paul did some experiments using the HW bits and didn't see a great perf increase (or what is even a decrease ?), but I should try that again on ppc64 since there, we can much more quickly hit the proper hash slot (we store its index in one group within the PTE).

Another problem with using real A & D hash bits is that we may evict entries from the hash table (because both groups are full for a given hash value). In this case, we need to go back to the linux PTE to update the bits in there before we lose the A/D information from the hash. But I don't think the overhead here matters much, we only rarely do evicts.

Quoted 15 lines

I'll let Rik and Andrea argue that part - it's entirely possible that getting lots of positive results is a _good_ thing, if the same page is mapped multiple times. That would just make us less eager to unmap it, which sounds like potentially the right thign to do (it's also how the old non-rmap code worked, and I know Rik thought it was "unfair", but whatever).

Quoted 3 lines

Ok, right now, Anton is testing a patch from paulus where we do our own flush batching and do the flush inside ptep_test_and_clear_* That will at least fix the problem for us now.

Yeah, and it's unlikely to be a performance problem anyway. That function should be called only when we're low on memory..

Linus

Signature · 1 line
Benjamin Herrenschmidt <[email protected]>
#14 lore raw
Quoted 6 lines · Benjamin Herrenschmidt

For accessed, we currently do not use the HW bit neither. Accessed = in the hash, not accessed = not in the hash. A bit basic, but the cost of faulting them back in isn't that bad. Still, I always found it a bit stupid that we end up having the harvesting of accessed bits actually evict pages that _are_ accessed, and thus potentially here to be accessed again ;)

It's hard for me to evaluate how much the young bit matters by only thinking about it, I know for sure the heavily swapping behaviour on the alpha was noticeably less smooth than on x86 (alpha has^Hd no way to implement the young bit, not even like you do in software through hash faults). So I guess it's worthwhile for you to account for it even if in software (i.e. ppc not ppc64).

Quoted 2 lines

Paul did some experiments using the HW bits and didn't see a great perf increase (or what is even a decrease ?), but I should try that

It should be an I/O dominated workload anyways and it sounds like the hardware way involves hash manipulation too (it only avoids the fault to set it back on).

Quoted 3 lines
Quoted 3 lines

I'll let Rik and Andrea argue that part - it's entirely possible that getting lots of positive results is a _good_ thing, if the same page is mapped multiple times. That would just make us less eager to unmap it,

that sounds correct behaviour to me, if a page is mapped multiple times we should be eager in unmapping it. More precisely we should give every user the opportunity to increase the youngness of the page, so a page with multiple users will go away after a page with just a single user, assuming all users access their pages at the same frequency.

Returning to the "how to flush the tlb after clearing the young bit", at least on the x86 I find more desiderable to flush based on mm (in UP that's the most efficient and it provides an accurate behaviour, in SMP it maybe still to costly but sure a lot less costly than a broadcast per pte). In 2.4 with the pagetable scan the flush per mm is strightforward and it provides a very high probability of optimizing away an huge lot of spurious IPI broadcast. But even in 2.6 the vm is unmapping stuff with some aggressive clustering algorithm so that when it starts umapping stuff it drops quite some stuff and there's still a relevant probability that only a few mm have to be flushed, which in SMP can decrease a lot the need of IPIs. Not sure how these flush_tlb_mm ideas translates for ppc though.

The dirty and accessed bitflags instead are quite a different matter w.r.t to tlb flushing, we can't defer the tlb flush after atomically clearing the pte in smp while we clear the dirty bit. the tlb shootdown is the clustered version of that. the shootdown run a broadcast IPI not more than every 508 pte freed per mm. For the same reason we can try to coalesce the tlb flush post-clear-young with an mm flush, we can achieve a similar coalescing without the no need of an exact tlb shootdown like in the pte freeing.

#15 lore raw
Quoted 13 lines

Returning to the "how to flush the tlb after clearing the young bit", at least on the x86 I find more desiderable to flush based on mm (in UP that's the most efficient and it provides an accurate behaviour, in SMP it maybe still to costly but sure a lot less costly than a broadcast per pte). In 2.4 with the pagetable scan the flush per mm is strightforward and it provides a very high probability of optimizing away an huge lot of spurious IPI broadcast. But even in 2.6 the vm is unmapping stuff with some aggressive clustering algorithm so that when it starts umapping stuff it drops quite some stuff and there's still a relevant probability that only a few mm have to be flushed, which in SMP can decrease a lot the need of IPIs. Not sure how these flush_tlb_mm ideas translates for ppc though.

Since we use the hash as a TLB cache, we need to evict things from it where you would do a flush_tlb. A flush_tlb_mm (or a range) is fairly expensive. We have to calculate the hash value for each page and evict them all. Also, the "nice" thing with this hash is since we have the vsid's (kind of address space number), we can hold many processes translations in there for a long time.

On the other hand, we don't need IPIs for any kind of flush (the actual TLB flushes that we perform after evicting the hash entries do broadcast in HW).

Quoted 8 lines

The dirty and accessed bitflags instead are quite a different matter w.r.t to tlb flushing, we can't defer the tlb flush after atomically clearing the pte in smp while we clear the dirty bit. the tlb shootdown is the clustered version of that. the shootdown run a broadcast IPI not more than every 508 pte freed per mm. For the same reason we can try to coalesce the tlb flush post-clear-young with an mm flush, we can achieve a similar coalescing without the no need of an exact tlb shootdown like in the pte freeing

#16 lore raw
In reply to Andrea Arcangeli
Quoted 6 lines · Andrea Arcangeli

It's hard for me to evaluate how much the young bit matters by only thinking about it, I know for sure the heavily swapping behaviour on the alpha was noticeably less smooth than on x86 (alpha has^Hd no way to implement the young bit, not even like you do in software through hash faults). So I guess it's worthwhile for you to account for it even if in software (i.e. ppc not ppc64).

I have a vague notion it should be possible to turn off the PAL pagetable emulation and do these things yourself, though I'm not entirely clear on how practical this is to do (e.g. whether the real MMU's docs are public, whether the PAL code can be turned off at all, etc.). It would be a relatively large amount of arch code to bang out, and for a largely (and rather unfortunately) dead architecture at that.

Probably a moot point depending on the level of resistance to the idea (which seems to dominate technical concerns for a number of things) and how thin I'm spread. I've got a multia, but (a) multias suck and (b) it's stripped, so unless I feel like debugging swapping over the network, that's useless apart from making sure it boots and runs luserspace.

I guess the point of this was really a roundabout way to ask if there was enough information to either do that with or rule it out just to satisfy my own curiosity, since it's not likely I'll ever get around to actually trying to implement it.

-- wli

#17 lore raw
In reply to Linus Torvalds
Quoted 6 lines · Linus Torvalds

I'll let Rik and Andrea argue that part - it's entirely possible that getting lots of positive results is a _good_ thing, if the same page is mapped multiple times. That would just make us less eager to unmap it, which sounds like potentially the right thign to do (it's also how the old non-rmap code worked, and I know Rik thought it was "unfair", but whatever).

I'm really not sure which of the two behaviours would perform better. Chances are both behaviours will show some performance improvement over the other, depending on the workload...

Rik

Signature · 3 lines
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
#18 lore raw
Quoted 10 lines · Rik van Riel
Quoted 6 lines · Linus Torvalds

I'll let Rik and Andrea argue that part - it's entirely possible that getting lots of positive results is a _good_ thing, if the same page is mapped multiple times. That would just make us less eager to unmap it, which sounds like potentially the right thign to do (it's also how the old non-rmap code worked, and I know Rik thought it was "unfair", but whatever).

Quoted 5 lines

I'm really not sure which of the two behaviours would perform better. Chances are both behaviours will show some performance improvement over the other, depending on the workload...

The current behaviour seems better from a theoretical point of view. All we want to know is the reference pattern - whether it is one process referencing the page frequently or 100 processes referencing it infrequently shouldn't matter. And if we want to give mapped pages more preference over unmapped ones (they already have some preference, by the default value of /proc/sys/vm/swappiness), we have less radical ways of doing this.

But yes, it probably makes damn-all difference across a mix of workloads.

#19 lore raw
Quoted 1 line · Andrew Morton

The current behaviour seems better from a theoretical point of view.

It's certainly easier to understand when tuning the VM, indeed.

Quoted 3 lines

And if we want to give mapped pages more preference over unmapped ones (they already have some preference, by the default value of /proc/sys/vm/swappiness), we have less radical ways of doing this.

Agreed, the current swappiness is probably a better measure. More flexible and more easy to tune.

cheers,

Rik

Signature · 3 lines
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
#20 lore raw
In reply to Andrew Morton
Quoted 2 lines · Andrew Morton

The current behaviour seems better from a theoretical point of view.

I disagree. It's at least not obvious.

Quoted 4 lines

All
we want to know is the reference pattern - whether it is one process referencing the page frequently or 100 processes referencing it infrequently shouldn't matter.

I agree that those two cases should be the same. And in fact, those two cases _will_ be the same by my suggested change ("break out of 'page_referenced()' early")

However, you ignore the third case: a page that is frequently used by 100 processes.

Such a page behaves differently with the 'break early' behaviour, by pinnong the page more tightly.

And I think that's the right behaviour. At least that's not "obviously wrong".

It's not something to do in 2.6.x, but I disagree that it's clear-cut.

Linus

#21 lore raw
Quoted 16 lines
Quoted 1 line

The current behaviour seems better from a theoretical point of view.

I disagree. It's at least not obvious.

Quoted 4 lines

All
we want to know is the reference pattern - whether it is one process referencing the page frequently or 100 processes referencing it infrequently shouldn't matter.

I agree that those two cases should be the same. And in fact, those two cases _will_ be the same by my suggested change ("break out of 'page_referenced()' early")

However, you ignore the third case: a page that is frequently used by 100 processes.

Quoted 7 lines

Such a page behaves differently with the 'break early' behaviour, by pinnong the page more tightly.

And I think that's the right behaviour. At least that's not "obviously wrong".

It's not something to do in 2.6.x, but I disagree that it's clear-cut.

Could we at least stick a big fat comment explaining the current behaviour in there? The current behaviour is not at all obvious from reading the code. I'll try to write something if you like, but no doubt someone could do a better job than I.

M.

#22 lore raw
In reply to Andrew Morton
Quoted 4 lines · Andrew Morton

The current behaviour seems better from a theoretical point of view. All we want to know is the reference pattern - whether it is one process referencing the page frequently or 100 processes referencing it infrequently shouldn't matter. And if we want to give mapped pages more

It can matter. Evicting a page that is infrequently referenced by many processes increases the chance that all runnable processes block waiting for that same page later. The likelihood of that happening grows under memory pressure, when "infrequently" may actually be "quite often" and when disk I/O is congested (resulting in higher disk access times).

You won't have the same effect when evicting a page that is referenced by one process only, no matter how frequently.

Having all processes blocked is indeed one problem of 2.6 under memory pressure. I don't know what the cause is, though.

Roger

#23 lore raw
Quoted 7 lines · Roger Luethi

It can matter. Evicting a page that is infrequently referenced by many processes increases the chance that all runnable processes block waiting for that same page later. The likelihood of that happening grows under memory pressure, when "infrequently" may actually be "quite often" and when disk I/O is congested (resulting in higher disk access times). You won't have the same effect when evicting a page that is referenced by one process only, no matter how frequently.

Part of this is unrealistic; paging I/O being congested must be due to paging itself causing seeks without additional I/O load. Reading a single page once and then faulting that one page back into numerous process address spaces is only one I/O request, and so cannot seek in and of itself. So in this scenario, a convoy of processes on a single page is plausible; aggravated paging I/O seekiness is not. Did you have in mind some additional I/O load? Or do affected processes actually all fault before the one I/O completes, and so all block temporarily?

Quoted 2 lines · Roger Luethi

Having all processes blocked is indeed one problem of 2.6 under memory pressure. I don't know what the cause is, though.

Can you capture sysrq t while a situation like this is in progress?

-- wli

#24 lore raw
Quoted 9 lines · William Lee Irwin III
Quoted 7 lines · Roger Luethi

It can matter. Evicting a page that is infrequently referenced by many processes increases the chance that all runnable processes block waiting for that same page later. The likelihood of that happening grows under memory pressure, when "infrequently" may actually be "quite often" and when disk I/O is congested (resulting in higher disk access times). You won't have the same effect when evicting a page that is referenced by one process only, no matter how frequently.

Quoted 8 lines

Part of this is unrealistic; paging I/O being congested must be due to paging itself causing seeks without additional I/O load. Reading a single page once and then faulting that one page back into numerous process address spaces is only one I/O request, and so cannot seek in and of itself. So in this scenario, a convoy of processes on a single page is plausible; aggravated paging I/O seekiness is not. Did you have in mind some additional I/O load? Or do affected processes actually all fault before the one I/O completes, and so all block temporarily?

My previous message was meant as a warning of the assumption that the aggregated reference frequency is all that matters. I was merely pointing out how the number of processes referencing a page could affect performance as well. Reference frequency is used as an estimator for the _likelihood_ of a fault in the future, but the potential _impact_ of a fault grows with the number of processes that may block on it. It is one possible (though not necessarily the most likely) explanation for the symptoms I see with 2.6.

vmstat finds all processes blocked a lot more often in 2.6 than in 2.4, often for several seconds in a row. That only means something in comparison, of course, because it is anything but a precise measurement -- not only because of the 1 second snapshot granularity but also due to the fact that bookkeeping of running and blocked processes in the kernel is not accurate (processes may count as both blocked and running).

Typical log snippet for a kernel build under some 2.6.0-test release:

procs -----------memory---------- ---swap-- -----io---- --system-- ----cpu----

 r  b   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id wa
 9  3   6268 851814   1500   8992  440    0   996   348 1141   294 87 13  0  0
 9  3   6164 852816   1540   9088  352    0   456     0 1045   145 91  9  0  0
 9  6   6164   4044 853818   8112   60    0   100    28 1016    71 92  8  0  0
 4  6   6604 854820    924   7432  532  472   784   488 1096   626 57 43  0  0
 2  9   9248   3556 855921   6968 1044 2748  1640  2752 1283   412 74 13  0 13
 3  7   9248 857071    924   6864 1208    0  1720   108 1326   524 60 34  0  6
10  8  11164   2080 858438   5952 1068 1944  2040  2064 1623  1655 74 26  0  0
 0 11  13000 859563    356   5824  796 2032  1572  2036 1330   656 66 24  0 10
 0 10  16608   4064 861037   5868  832 3960  1836  3964 1755   725 42  9  0 49
 0 11  16604 862284    420   5920 1420    0  2216     4 1471   485 39  4  0 57
 7  4   9772  10656 863286   6644  552    0  1344    12 1112   250 56  5  0 39
 9  2   8228 864687    732   6960  296    0   632   108 1484   257 96  4  0  0
 8  3   8212  10656 865689   7176   80    0   320     0 1050   146 95  5  0  0

The trace above is not for the benchmark I referred to as kbuild in the past few weeks (it was taken under lighter load). Even so 2.6 exhibits significantly more periods with I/O wait and consequently takes longer than 2.4 to complete.

Quoted 4 lines
Quoted 2 lines

Having all processes blocked is indeed one problem of 2.6 under memory pressure. I don't know what the cause is, though.

Can you capture sysrq t while a situation like this is in progress?

What are you getting at? This may be easier for you to do because you know what you are looking for.

Roger

#25 lore raw
Quoted 8 lines · At some point in the past, I wrote:
Quoted 8 lines

Part of this is unrealistic; paging I/O being congested must be due to paging itself causing seeks without additional I/O load. Reading a single page once and then faulting that one page back into numerous process address spaces is only one I/O request, and so cannot seek in and of itself. So in this scenario, a convoy of processes on a single page is plausible; aggravated paging I/O seekiness is not. Did you have in mind some additional I/O load? Or do affected processes actually all fault before the one I/O completes, and so all block temporarily?

Quoted 8 lines · Roger Luethi

My previous message was meant as a warning of the assumption that the aggregated reference frequency is all that matters. I was merely pointing out how the number of processes referencing a page could affect performance as well. Reference frequency is used as an estimator for the _likelihood_ of a fault in the future, but the potential _impact_ of a fault grows with the number of processes that may block on it. It is one possible (though not necessarily the most likely) explanation for the symptoms I see with 2.6.

I guess caution against LFU is uncontroversial.

Quoted 7 lines · Roger Luethi

vmstat finds all processes blocked a lot more often in 2.6 than in 2.4, often for several seconds in a row. That only means something in comparison, of course, because it is anything but a precise measurement -- not only because of the 1 second snapshot granularity but also due to the fact that bookkeeping of running and blocked processes in the kernel is not accurate (processes may count as both blocked and running). Typical log snippet for a kernel build under some 2.6.0-test release:

I'm not convinced what vmstat gets out of 2.4 is entirely comparable to what it gets out of 2.6. "blocked" and "running" are collected very differently in 2.6. iowait shouldn't be collected on 2.4 at all.

This could probably be addressed by backporting 2.6's reporting methods to 2.4 so the two kernels use similar reporting mechanisms.

Quoted 15 lines · Roger Luethi

procs -----------memory---------- ---swap-- -----io---- --system-- ----cpu----

 r  b   swpd   free   buff  cache   si   so    bi    bo   in    cs us sy id wa
 9  3   6268 851814   1500   8992  440    0   996   348 1141   294 87 13  0  0
 9  3   6164 852816   1540   9088  352    0   456     0 1045   145 91  9  0  0
 9  6   6164   4044 853818   8112   60    0   100    28 1016    71 92  8  0  0
 4  6   6604 854820    924   7432  532  472   784   488 1096   626 57 43  0  0
 2  9   9248   3556 855921   6968 1044 2748  1640  2752 1283   412 74 13  0 13
 3  7   9248 857071    924   6864 1208    0  1720   108 1326   524 60 34  0  6
10  8  11164   2080 858438   5952 1068 1944  2040  2064 1623  1655 74 26  0  0
 0 11  13000 859563    356   5824  796 2032  1572  2036 1330   656 66 24  0 10
 0 10  16608   4064 861037   5868  832 3960  1836  3964 1755   725 42  9  0 49
 0 11  16604 862284    420   5920 1420    0  2216     4 1471   485 39  4  0 57
 7  4   9772  10656 863286   6644  552    0  1344    12 1112   250 56  5  0 39
 9  2   8228 864687    732   6960  296    0   632   108 1484   257 96  4  0  0
 8  3   8212  10656 865689   7176   80    0   320     0 1050   146 95  5  0  0
Quoted 4 lines

The trace above is not for the benchmark I referred to as kbuild in the past few weeks (it was taken under lighter load). Even so 2.6 exhibits significantly more periods with I/O wait and consequently takes longer than 2.4 to complete.

The oscillation in "free" and "buff" is very unusual. What is this box doing?

Quoted 1 line · William Lee Irwin III
Quoted 1 line

Can you capture sysrq t while a situation like this is in progress?

Quoted 2 lines · Roger Luethi

What are you getting at? This may be easier for you to do because you know what you are looking for.

I'm not looking for anything per se. It will say what codepaths tasks are blocked in and give an idea of what's going on around the system. kgdb can do something similar that might be more useful, since data can be examined also.

-- wli

#26 lore raw
Quoted 9 lines · William Lee Irwin III
Quoted 7 lines

the aggregated reference frequency is all that matters. I was merely pointing out how the number of processes referencing a page could affect performance as well. Reference frequency is used as an estimator for the _likelihood_ of a fault in the future, but the potential _impact_ of a fault grows with the number of processes that may block on it. It is one possible (though not necessarily the most likely) explanation for the symptoms I see with 2.6.

I guess caution against LFU is uncontroversial.

My bad. What I said is true for both LRU and LFU (they try to predict the probability of future references), but I wrote "frequency" because that happened to be on my mind (for unrelated reasons). The point was
basically: risk = probability * damage

Quoted 2 lines

I'm not convinced what vmstat gets out of 2.4 is entirely comparable to what it gets out of 2.6. "blocked" and "running" are collected very

Agreed. OTOH those readings are consistent with other observations I made. It should even be possible to add up the reported idle times and receive a ballpark figure for the slowdown compared to a system with more than enough memory.

Quoted 1 line

differently in 2.6. iowait shouldn't be collected on 2.4 at all.

True. If 2.4 reports idle time during a compile benchmark, though, it seems plausible to assume it is IO wait. And if 2.6 takes much longer than 2.4 to complete, it is due to time spend waiting for I/O (minus some difference in system overhead) -- the work done in user space is equal, after all.

Quoted 2 lines

This could probably be addressed by backporting 2.6's reporting methods to 2.4 so the two kernels use similar reporting mechanisms.

I don't think it's worth it. It wouldn't tell us anything we don't already know.

Quoted 2 lines

The oscillation in "free" and "buff" is very unusual. What is this box doing?

Oops, sorry. That trace is a few months old and I forgot I had used a hack to have timestamps in vmstat. The large numbers that are alternating are jiffies, the smaller numbers are the actual readings.

Roger

#27 lore raw
In reply to Roger Luethi
Quoted 13 lines · Roger Luethi
Quoted 4 lines · Andrew Morton

The current behaviour seems better from a theoretical point of view. All we want to know is the reference pattern - whether it is one process referencing the page frequently or 100 processes referencing it infrequently shouldn't matter. And if we want to give mapped pages more

It can matter. Evicting a page that is infrequently referenced by many processes increases the chance that all runnable processes block waiting for that same page later. The likelihood of that happening grows under memory pressure, when "infrequently" may actually be "quite often" and when disk I/O is congested (resulting in higher disk access times).

Quoted 6 lines

You won't have the same effect when evicting a page that is referenced by one process only, no matter how frequently.

Having all processes blocked is indeed one problem of 2.6 under memory pressure. I don't know what the cause is, though.

I usually work this sort of thing out by "random sampling". When everything is in steady state, break into kgdb and start looking at task backtraces, see where they are all sleeping.

If it's in the pagefault handler, go up to do_page_fault() and work out the faulting address. Compare that with /proc/pid/maps to see if it's libc or whatever.

Repeat the above N times until you have a decent feel for what's happening in there. It doesn't take long.

#28 lore raw
Quoted 6 lines · Andrew Morton
Quoted 2 lines

Having all processes blocked is indeed one problem of 2.6 under memory pressure. I don't know what the cause is, though.

I usually work this sort of thing out by "random sampling". When everything is in steady state, break into kgdb and start looking at task backtraces, see where they are all sleeping.

Well, there isn't really a steady state as such. On a loaded system there are periods during compile benchmarks where the system spends half the time and more in I/O wait, so some processes do get to run and do some minimal amount of work.

Quoted 6 lines

If it's in the pagefault handler, go up to do_page_fault() and work out the faulting address. Compare that with /proc/pid/maps to see if it's libc or whatever.

Repeat the above N times until you have a decent feel for what's happening in there. It doesn't take long.

I instrumented the kernel a while ago to log page fault handling (address, backing file if available) when the system became idle with all processes blocked. I can resurrect that code which would allow for larger samples. I'll post results if/when I get around to do it.

Roger

#29 lore raw
In reply to Linus Torvalds
Quoted 24 lines · Linus Torvalds
Quoted 4 lines · Benjamin Herrenschmidt

Or do what I propose here, that is have ptep_test_and_clear_* be responsible for the flush on archs where it is necessary, but then it would be nice to have more than the ptep as an argument...

The dirty handling already does the TLB flush (in that case it's a correctness issue, not a hint). So it's only ptep_test_and_clear_young() that matters.

I don't know whather that ever ends up being performance-critical, and I don't see what else could be passed into it. We literally don't _have_ anythign else than the pte.

But the ppc architecture could easily decide to walk the hash tables and invalidate in ptep_test_and_clear_young(). And if it ends up being a performance issue, it _appears_ that all users of "page_referenced()" (which is the only thing that does this) are actually using the return value as just a boolean. And it's entirely possible that we should break out of "page_referenced()" on the _first_ hit of "yes, this has been referenced".

Quoted 7 lines

That would make it much less CPU-intensive to make "ptep_test_and_clear_young()" slightly heavier to execute. It would also cause "page_referenced()" to not clear _all_ mapped reference bits at the same time - which might unfairly cause multi-used pages to stay in memory. On the other hand, that might be the _right_ behaviour.

Rik? Andrea?

I agree with you about the current code being optimal for x86 despite it's not accurate, as you said it doesn't need to be accurate since it's not a correctness matter. I'm not very concerned about the size of the tlb that Manfred mentioned, the snoops can't get past a cr3 overwrite, so the first mm flush will make sure the young bit will be marked again next time the page is accessed, no matter the size of the tlb and no matter what snooping it does. Snoops can't obviate the lack of ASN in the x86* arch.

In my opinion flushing the tlb for every page is definitely overkill in SMP due the flood of broadcast IPIs it generates (I actually did that and got bitten by the ipi flood in practice some year ago ;).

I believe flushing the tlb for every pte is reasonable only under #ifndef CONFIG_SMP.

something that can work for both cases SMP and UP is to keep track of which mm have to be flushed, and to flush the _whole_ mm, only after the pagetable walk is complete, this reduces the IPI broadcast to 1 per mm, not 1 per pte. This should improve it of an order of magnitude with common workloads. Flushing per-pte is probably overkill on UP too.

This is what I have in 2.4:

#ifndef CONFIG_SMP
	/* in SMP is too costly to send further IPIs */
	if (tlb_flush)
		flush_tlb_mm(mm);

#endif

Originally I was flushing the mm even in UP, but then somebody complained on some 4-way with some 8gigs and so I let it go completely lazy now in SMP by adding the ifndef around it.

However I've no proof that the #ifndef made any difference, so it could be the flush_tlb_mm is fine for SMP too. The above is just to go 100% safe in terms of scalability in the high end, while providing the most efficient and most accurate behaviour to UP (on UP all but one of those flush_tlb_mm are noops in terms of tlb cost).

the above flush_tlb_mm executes for every mm scan only if the inner code had to mark a pte as "old". in 2.4 that's trivial because we scan the mm in order, but a dumb algorithm to do it in 2.6 could be to add a bitflag to every mm and walking the mmlist and flush the mm with the bit on (though this dumb logic is an O(N) one with the number of mm).

I'm unsure if the tlb flushing (if any) should be in the architectural code or in the common code (there are pros and cons). For this specific case exactly because the flush should be per-mm (a "should" for UP and a "must" for SMP) I think doing it in the architectural code isn't preferable.

As a generic matter (not necessairly specific to the ptep_test_and_clear_young) I dislike any form cleverness and smartness and hiding in the architectural pte/tlb lib calls unless it's strictly necessary. To make an example s390 needs some additional complexity to exploit their per-physical-page dirty bit, that incidentally broke in subtle ways with the zero page with get_user_pages (that's fixed by now, but it took a while to figure out and it sure couldn't be trapped by reading the code, it bites you when it's too late). The problem is most people would only read the x86* implementation anyways (that is not a noop, it is just different), and in turn avoiding smartness and differences in the archs code increases the probability that the common code will work correctly everywhere. And you can think simpler by just reading the common code. For istance I would prefer an additional "flush_tlb_after_test_and_clear_young" than to hide it in ptep_test_and_clear_young. That would be self documenting, the hiding isn't and it could be forgotten by x86* programmers over time.