OSDev.org

Hi all,
I have a question regarding tlb flush IPI delay.
As Brendan concluded:
<quote>
To summarise, each time you modify the paging structures (page table/s, page directory/s, etc), you'd:

• invalidate the TLB on the current CPU
• determine if the stale TLB entry could be used in an "unsafe" way:
  • if "no", then other CPUs can rely on their page fault handlers to invalidate the TLB entries and you don't need to do anything else
  • if "yes", then determine if any other CPUs could be effected by the change:
    • if "yes", then send an IPI to any/all other CPUs that could be effected, to ensure they invalidate their TLB too
    • if "no" (e.g. page belongs to a single-threaded process that can't be running on any other CPU) then you don't have to do anything else

</quote>
if any target CPUs will be effected by the change, before the IPI arrives late, if the target CPU is running.
Is it possible that it will access the stale TLB entry which has been modified by the sender.

Hi,

loki2441 wrote:if any target CPUs will be effected by the change, before the IPI arrives late, if the target CPU is running.
Is it possible that it will access the stale TLB entry which has been modified by the sender.

Yes.

However, in that case you've got larger problems anyway - e.g. multiple CPUs accessing the same data at the same time and screwing each other up because you didn't have anything protecting the data (spinlocks, mutexes, whatever). If you do have something protecting the data, then that same protection also protects against stale TLB usage.


Cheers,

Brendan

Brendan wrote: However, in that case you've got larger problems anyway - e.g. multiple CPUs accessing the same data at the same time and screwing each other up because you didn't have anything protecting the data (spinlocks, mutexes, whatever). If you do have something protecting the data, then that same protection also protects against stale TLB usage.

Thank you Brendan!
Why this is not a problem in Linux, I had checked the code there and did not see any locks related to the tlb entry.
I only see there is a lock to protect the modified mm and flush ipi messages stored in "union smp_flush_state".
I would really appreciate it if you could give me more details about how the stale tlb entry on target side is protected against usage before the tlb flush ipi arrives?
Thanks for your time!

Hi,

loki2441 wrote:I would really appreciate it if you could give me more details about how the stale tlb entry on target side is protected against usage before the tlb flush ipi arrives?

Can you think of any scenario where it's possible for a CPU to use a stale TLB before its invalidated, where there isn't also some sort of additional/unrelated concurrency problem that needs to be fixed?

If nothing prevents a CPU from accessing the data immediately after another CPU has modified a page table entry (but before the "multi-CPU TLB shootdown" happens); then nothing prevents a CPU from accessing the data immediately before another CPU modifies the page table entry either.

If a CPU can access the data immediately before another CPU modifies the page table entry, then there's an additional/unrelated concurrency problem that needs to be fixed. For example, maybe the first CPU is writing data immediately before another CPU frees the page and data is being lost, or maybe the first CPU is reading data from memory that hasn't been allocated yet. Either way there's something wrong that doesn't have anything to do with stale TLB entries.


Cheers,

Brendan

Brendan wrote:Hi,

loki2441 wrote:I would really appreciate it if you could give me more details about how the stale tlb entry on target side is protected against usage before the tlb flush ipi arrives?

Can you think of any scenario where it's possible for a CPU to use a stale TLB before its invalidated, where there isn't also some sort of additional/unrelated concurrency problem that needs to be fixed?

Thank you Brendan!
Please correct me! Here is one scenario that bugs me a lot recently.
1): Process 1 thread#1 locks the mm or pte
2): Process 1 thread#1 frees the pte related page.
3): Process 1 thread#1 invalidates the local tlb
4): Process 1 thread#1 sends IPIs to other CPU to invalidate the related tlb entry

In the time between step 3) and step 4).
5): Process 1 thread#2 wants to write to the pte related page. It will find that this page is readable and writable.
6): Process 1 thread#2 will get the physical address from the tlb entry and write data to it(which is stale already).

I think there should be something I don't know that prevents the TLB access in step 5) and 6).
Thanks for your time!

Rearrange those events so that step 5 and 6 happen before step 1. What has changed? Nothing.

The only thing of importance is that the thread doing the invalidation wait for the TLB shootdown to complete before it actually goes and does anything with the page it just freed (say, put it on a free list)

Thank you Owen!

Owen wrote:Rearrange those events so that step 5 and 6 happen before step 1. What has changed? Nothing.

The only thing of importance is that the thread doing the invalidation wait for the TLB shootdown to complete before it actually goes and does anything with the page it just freed (say, put it on a free list)

I know what you mean.
The thread doing the invalidation wait for the TLB shootdown to complete is trying to make this operation atomic on the IPI send side. But on the IPI receive side, if the IPI transfers pretty slow, the pte has been modified and tlb entry has been invalidated on sender side. If the IPI receive side access the related tlb before IPI arrives. That will give me some problem.

Hi,

loki2441 wrote:

Owen wrote:Rearrange those events so that step 5 and 6 happen before step 1. What has changed? Nothing.

The only thing of importance is that the thread doing the invalidation wait for the TLB shootdown to complete before it actually goes and does anything with the page it just freed (say, put it on a free list)

I know what you mean.

Owen is correct - in this case it makes no difference if step 5 happens before step 1 or between steps 3 and 4.

Let's make it worse (so that it actually does matter)!

1): Process 1 thread#1 locks the mm or pte
2): Process 1 thread#1 frees the pte related page.
3): Process 1 thread#1 invalidates the local tlb
4): Process 1 thread#1 sends IPIs to other CPU to invalidate the related tlb entry

In the time between step 3) and step 4).
5): Process 1 thread#2 wants to write to the pte related page. It will find that this page is readable and writable.
6): Process 1 thread#2 will get the physical address from the tlb entry and write data to it (which is fine).
7): Process 1 thread#2 receives the IPI and does the TLB invalidation
8 ): Process 1 thread#2 attempts to read the data it wrote in step 5 and gets a page fault

Now let's think about this - we do have a problem, but the problem is that thread #2 is using data while thread #1 is freeing it. There's no way to fix the "freeing while in use" problem without also (accidentally) making it impossible for the second thread to use stale TLB entries.

Of course we didn't really need to make the original worse, because the "freeing while in use" problem already existed - step 5 could have easily happened any time after step 4 (thread #2 attempts to write to an already freed page).


Cheers,

Brendan

Thanks a lot Brendan and Owen!
I really appreciate it.

Brendan wrote:Hi,

loki2441 wrote:

Owen wrote:Rearrange those events so that step 5 and 6 happen before step 1. What has changed? Nothing.

The only thing of importance is that the thread doing the invalidation wait for the TLB shootdown to complete before it actually goes and does anything with the page it just freed (say, put it on a free list)

I know what you mean.

Owen is correct - in this case it makes no difference if step 5 happens before step 1 or between steps 3 and 4.

Let's make it worse (so that it actually does matter)!

1): Process 1 thread#1 locks the mm or pte
2): Process 1 thread#1 frees the pte related page.
3): Process 1 thread#1 invalidates the local tlb
4): Process 1 thread#1 sends IPIs to other CPU to invalidate the related tlb entry

In the time between step 3) and step 4).
5): Process 1 thread#2 wants to write to the pte related page. It will find that this page is readable and writable.
6): Process 1 thread#2 will get the physical address from the tlb entry and write data to it (which is fine).
7): Process 1 thread#2 receives the IPI and does the TLB invalidation
8 ): Process 1 thread#2 attempts to read the data it wrote in step 5 and gets a page fault

Now let's think about this - we do have a problem, but the problem is that thread #2 is using data while thread #1 is freeing it. There's no way to fix the "freeing while in use" problem without also (accidentally) making it impossible for the second thread to use stale TLB entries.

Of course we didn't really need to make the original worse, because the "freeing while in use" problem already existed - step 5 could have easily happened any time after step 4 (thread #2 attempts to write to an already freed page).


Cheers,

Brendan