intel-iommu: nested vIOMMU, cleanups, bug fixes

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Quoted 3 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Is the added lock going to protect anything else beyond a g_hash_table?

If not, did you consider using qht instead of the lock + hash table? It would give you lockless lookups as well as scalable updates.

[Sorry if my question isn't relevant, I am not familiar with this code and just briefly skimmed over this series.

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
  include/hw/i386/intel_iommu.h |  8 ++++++++
  hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
  2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
      uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

Quoted 22 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
  include/hw/i386/intel_iommu.h |  8 ++++++++
  hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
  2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
      uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 10 lines

include/hw/i386/intel_iommu.h +8 -0

      uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns 0) */
      uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.
+     */
+    QemuMutex iommu_lock;

Some questions:

1) Do we need to protect context cache too?

2) Can we just reuse qemu BQL here?

3) I think the issue is common to all other kinds of IOMMU, so can we simply synchronize before calling ->translate() in memory.c. This seems a more common solution.

From: Peter Xu
Sent: Friday, April 27, 2018 2:26 PM

Quoted 2 lines · Jason Wang

Quoted 6 lines · Peter Xu

Quoted 5 lines

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The

safety

Quoted 3 lines

Quoted 3 lines

of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Quoted 9 lines

Review

Quoted 9 lines

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
  include/hw/i386/intel_iommu.h |  8 ++++++++
  hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
  2 files changed, 37 insertions(+), 2 deletions(-)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 5 lines

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 262

Quoted 5 lines

index 220697253f..1a8ba8e415 100644

include/hw/i386/intel_iommu.h +0 -0

@@ -262,6 +262,14 @@ struct IntelIOMMUState {
      uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes

*/

Quoted 1 line

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 263

Quoted 1 line

include/hw/i386/intel_iommu.h +0 -0

      uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns

0) */

Quoted 7 lines

Quoted 7 lines

include/hw/i386/intel_iommu.h +6 -0

      uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.

Quoted 6 lines

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 2 lines

include/hw/i386/intel_iommu.h +2 -0

+     */
+    QemuMutex iommu_lock;

Some questions:

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

For (1) the worst case is that the context entry cache be updated multiple times with the same value by multiple threads. IMHO that'll be fine too.

But yes for sure we can protect that too with the iommu lock.

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Quoted 1 line

3) I think the issue is common to all other kinds of IOMMU, so can we

simply

Quoted 2 lines

synchronize before calling ->translate() in memory.c. This seems a more common solution.

I suspect Power and s390 live well with that. I think it mean at least these platforms won't have problem in concurrency. I'm adding DavidG in loop in case there is further comment. IMHO we should just make sure IOMMU code be thread safe, and we fix problem if there is.

Thanks,

--
Peter Xu

Quoted 6 lines

From: Peter Xu
Sent: Friday, April 27, 2018 2:26 PM

Quoted 2 lines · Jason Wang

Quoted 10 lines

Quoted 6 lines · Peter Xu

Quoted 5 lines

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The

safety

Quoted 3 lines

Quoted 3 lines

of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

device page table definitely doesn't require protection, since it is in-memory structure managed by guest. However the reason above is not accurate - there is no way that guest OS can make sure no device uses non-present page entry, otherwise it doesn't require virtual IOMMU to protect itself. There could be bogus/ malicious drivers which surely may program the device to attempt so.

Quoted 11 lines

Quoted 10 lines

Review

Quoted 10 lines

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
  include/hw/i386/intel_iommu.h |  8 ++++++++
  hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
  2 files changed, 37 insertions(+), 2 deletions(-)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 15 lines

Quoted 5 lines

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 262

Quoted 5 lines

index 220697253f..1a8ba8e415 100644

include/hw/i386/intel_iommu.h +0 -0

@@ -262,6 +262,14 @@ struct IntelIOMMUState {
      uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes

*/

Quoted 1 line

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 263

Quoted 1 line

include/hw/i386/intel_iommu.h +0 -0

      uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns

0) */

Quoted 7 lines

Quoted 7 lines

include/hw/i386/intel_iommu.h +6 -0

      uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.

better if you can whitelist those paths here to clarify.

Quoted 11 lines

Quoted 7 lines

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 3 lines

include/hw/i386/intel_iommu.h +2 -0

+     */
+    QemuMutex iommu_lock;

Some questions:

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

Quoted 6 lines

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

again above cannot be assumed.

From: Peter Xu [mailto:[email protected]]
Sent: Friday, April 27, 2018 5:54 PM

Quoted 8 lines · Kevin

Quoted 8 lines

From: Peter Xu
Sent: Friday, April 27, 2018 2:26 PM

Quoted 4 lines · Jason Wang

Quoted 1 line · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the

only

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

Quoted 4 lines

thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The

safety

Quoted 2 lines

Quoted 2 lines

of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no

device

Quoted 8 lines

Quoted 1 line

Quoted 1 line

Quoted 1 line

will be using that page any more.

device page table definitely doesn't require protection, since it is in-memory structure managed by guest. However the reason above is not accurate - there is no way that guest OS can make sure no device uses non-present page entry, otherwise it doesn't require virtual IOMMU to protect itself. There could be bogus/ malicious drivers which surely may program the device to attempt so.

How about this:

Note that we don't need to protect device page tables since that's fully controlled by the guest kernel. However there is still possibilities that malicious drivers will still program the device to not disobey the rule. In that case QEMU can't really do anything useful, instead the guest itself will be responsible for all uncertainties.

Quoted 36 lines · Jason Wang

Quoted 22 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
   include/hw/i386/intel_iommu.h |  8 ++++++++
   hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
   2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
       uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 10 lines

include/hw/i386/intel_iommu.h +8 -0

       uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns 0) */
       uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.
+     */
+    QemuMutex iommu_lock;

Some questions:

Quoted 1 line

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

For (1) the worst case is that the context entry cache be updated multiple times with the same value by multiple threads. IMHO that'll be fine too.

But yes for sure we can protect that too with the iommu lock.

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Quoted 4 lines

3) I think the issue is common to all other kinds of IOMMU, so can we simply synchronize before calling ->translate() in memory.c. This seems a more common solution.

I suspect Power and s390 live well with that. I think it mean at least these platforms won't have problem in concurrency. I'm adding DavidG in loop in case there is further comment. IMHO we should just make sure IOMMU code be thread safe, and we fix problem if there is.

Thanks,

Quoted 54 lines · Peter Xu

Quoted 36 lines · Jason Wang

Quoted 22 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
   include/hw/i386/intel_iommu.h |  8 ++++++++
   hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
   2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
       uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 10 lines

include/hw/i386/intel_iommu.h +8 -0

       uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns 0) */
       uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.
+     */
+    QemuMutex iommu_lock;

Some questions:

Quoted 1 line

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

For (1) the worst case is that the context entry cache be updated multiple times with the same value by multiple threads. IMHO that'll be fine too.

But yes for sure we can protect that too with the iommu lock.

Quoted 4 lines

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Just a thought, using BQL may greatly simplify the code actually (consider we don't plan to remove BQL now).

Quoted 10 lines

Quoted 5 lines

3) I think the issue is common to all other kinds of IOMMU, so can we simply synchronize before calling ->translate() in memory.c. This seems a more common solution.

I suspect Power and s390 live well with that. I think it mean at least these platforms won't have problem in concurrency. I'm adding DavidG in loop in case there is further comment. IMHO we should just make sure IOMMU code be thread safe, and we fix problem if there is.

Quoted 2 lines

Thanks,

Yes, it needs some investigation, but we have other IOMMUs like AMD, and we could have a flag to bypass BQL if IOMMU can synchronize by itself.

Quoted 59 lines · Jason Wang

Quoted 57 lines · Peter Xu

Quoted 35 lines · Jason Wang

Quoted 22 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
    include/hw/i386/intel_iommu.h |  8 ++++++++
    hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
    2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
        uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 10 lines

include/hw/i386/intel_iommu.h +8 -0

        uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns 0) */
        uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.
+     */
+    QemuMutex iommu_lock;

Some questions:

Quoted 1 line

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

For (1) the worst case is that the context entry cache be updated multiple times with the same value by multiple threads. IMHO that'll be fine too.

But yes for sure we can protect that too with the iommu lock.

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Quoted 2 lines

Just a thought, using BQL may greatly simplify the code actually (consider we don't plan to remove BQL now).

Frankly speaking I don't understand why using BQL may greatly simplify the code... :( IMHO the lock here is really not a complicated one.

Note that IMO BQL is mostly helpful when we really want something to be run sequentially with some other things _already_ protected by BQL.

In this case, all the stuff is inside VT-d code itself (or other IOMMUs), why bother taking the BQL to make our life harder?

So, even if we want to provide a general lock for the translation procedure, I would prefer we add a per AddressSpace lock but not BQL.

However still that will need some extra flag showing that whether we need the protection of not. For example, we may need to expliclitly turn that off for Power and s390. Would that really worth it?

So my final preference is still current patch - we solve thread-safety problems in VT-d and IOMMU code. Again, we really should make sure all IOMMUs work with multithreads.

Quoted 8 lines

Quoted 8 lines

Quoted 3 lines

3) I think the issue is common to all other kinds of IOMMU, so can we simply synchronize before calling ->translate() in memory.c. This seems a more common solution.

I suspect Power and s390 live well with that. I think it mean at least these platforms won't have problem in concurrency. I'm adding DavidG in loop in case there is further comment. IMHO we should just make sure IOMMU code be thread safe, and we fix problem if there is.

Quoted 4 lines

Quoted 2 lines

Thanks,

Yes, it needs some investigation, but we have other IOMMUs like AMD, and we could have a flag to bypass BQL if IOMMU can synchronize by itself.

AMD is still only for experimental. If we really want to use it in production IMHO it'll need more testings and tunings not only on thread-safety but on other stuffs too. So again, we can just fix them when needed. I still don't see it a reason to depend on BQL here.

I'll see what others think about it.

CCing Paolo, Stefan and Fam too.

Thanks,

Quoted 60 lines · Peter Xu

Quoted 59 lines · Jason Wang

Quoted 57 lines · Peter Xu

Quoted 35 lines · Jason Wang

Quoted 22 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
    include/hw/i386/intel_iommu.h |  8 ++++++++
    hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
    2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
        uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 10 lines

include/hw/i386/intel_iommu.h +8 -0

        uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns 0) */
        uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.
+     */
+    QemuMutex iommu_lock;

Some questions:

Quoted 1 line

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

For (1) the worst case is that the context entry cache be updated multiple times with the same value by multiple threads. IMHO that'll be fine too.

But yes for sure we can protect that too with the iommu lock.

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Quoted 7 lines

Quoted 2 lines

Just a thought, using BQL may greatly simplify the code actually (consider we don't plan to remove BQL now).

Frankly speaking I don't understand why using BQL may greatly simplify the code... :( IMHO the lock here is really not a complicated one.

Note that IMO BQL is mostly helpful when we really want something to be run sequentially with some other things _already_ protected by BQL.

Except for the translate path from dataplane, I belive all other codes were already protected by BQL.

Quoted 2 lines

In this case, all the stuff is inside VT-d code itself (or other IOMMUs), why bother taking the BQL to make our life harder?

It looks to me it was as simple as:

(quoted diff) +1 -0

@@ -494,6 +494,7 @@ static MemoryRegionSection
 flatview_do_translate(FlatView *fv,
      IOMMUMemoryRegionClass *imrc;
      hwaddr page_mask = (hwaddr)(-1);
      hwaddr plen = (hwaddr)(-1);
+    int locked = false;
 
      if (plen_out) {

         plen = *plen_out;

(quoted diff) +4 -0

@@ -510,8 +511,15 @@ static MemoryRegionSection
 flatview_do_translate(FlatView *fv,
          }
          imrc = memory_region_get_iommu_class_nocheck(iommu_mr);
 
+        if (!qemu_mutex_iothread_locked()) {
+            locked = true;
+            qemu_mutex_lock_iothread();
+        }

         iotlb = imrc->translate(iommu_mr, addr, is_write ? IOMMU_WO : IOMMU_RO); +        if (locked) {
+            qemu_mutex_unlock_iothread();
+        }
         addr = ((iotlb.translated_addr & ~iotlb.addr_mask) | (addr & iotlb.addr_mask)); page_mask &= iotlb.addr_mask;

Quoted 5 lines

So, even if we want to provide a general lock for the translation procedure, I would prefer we add a per AddressSpace lock but not BQL.

It could be, but it needs more work on each specific IOMMU codes.

Quoted 3 lines

However still that will need some extra flag showing that whether we need the protection of not. For example, we may need to expliclitly turn that off for Power and s390. Would that really worth it?

It would cost just several lines of code, anything wrong with this?

Quoted 14 lines

So my final preference is still current patch - we solve thread-safety problems in VT-d and IOMMU code. Again, we really should make sure all IOMMUs work with multithreads.

Quoted 8 lines

Quoted 8 lines

Quoted 3 lines

3) I think the issue is common to all other kinds of IOMMU, so can we simply synchronize before calling ->translate() in memory.c. This seems a more common solution.

I suspect Power and s390 live well with that. I think it mean at least these platforms won't have problem in concurrency. I'm adding DavidG in loop in case there is further comment. IMHO we should just make sure IOMMU code be thread safe, and we fix problem if there is.

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

Thanks,

Yes, it needs some investigation, but we have other IOMMUs like AMD, and we could have a flag to bypass BQL if IOMMU can synchronize by itself.

AMD is still only for experimental. If we really want to use it in production IMHO it'll need more testings and tunings not only on thread-safety but on other stuffs too. So again, we can just fix them when needed. I still don't see it a reason to depend on BQL here.

Well, it's not about BQL specifically, it's about whether we have or need a generic thread safety solution for all IOMMUs.

We have more IOMMUs than just AMD, s390 and ppc:

# git grep imrc-\>translate\ =
hw/alpha/typhoon.c:    imrc->translate = typhoon_translate_iommu;
hw/dma/rc4030.c:    imrc->translate = rc4030_dma_translate;
hw/i386/amd_iommu.c:    imrc->translate = amdvi_translate;
hw/i386/intel_iommu.c:    imrc->translate = vtd_iommu_translate;
hw/ppc/spapr_iommu.c:    imrc->translate = spapr_tce_translate_iommu;
hw/s390x/s390-pci-bus.c:    imrc->translate = s390_translate_iommu;
hw/sparc/sun4m_iommu.c:    imrc->translate = sun4m_translate_iommu;
hw/sparc64/sun4u_iommu.c:    imrc->translate = sun4u_translate_iommu;

And we know there will be more in the near future.

Quoted 89 lines · Jason Wang

Quoted 59 lines · Peter Xu

Quoted 58 lines · Jason Wang

Quoted 57 lines · Peter Xu

Quoted 35 lines · Jason Wang

Quoted 22 lines · Peter Xu

Add a per-iommu big lock to protect IOMMU status. Currently the only thing to be protected is the IOTLB cache, since that can be accessed even without BQL, e.g., in IO dataplane.

Note that device page tables should not need any protection. The safety of that should be provided by guest OS. E.g., when a page entry is freed, the guest OS should be responsible to make sure that no device will be using that page any more.

Reported-by Fam Zheng<[email protected]>

Signed-off-by Peter Xu<[email protected]>

---
     include/hw/i386/intel_iommu.h |  8 ++++++++
     hw/i386/intel_iommu.c         | 31 +++++++++++++++++++++++++++++--
     2 files changed, 37 insertions(+), 2 deletions(-)

include/hw/i386/intel_iommu.h +0 -0

index 220697253f..1a8ba8e415 100644
@@ -262,6 +262,14 @@ struct IntelIOMMUState {
         uint8_t w1cmask[DMAR_REG_SIZE]; /* RW1C(Write 1 to Clear) bytes */

include/hw/i386/intel_iommu.h struct IntelIOMMUState { · line 272

Quoted 10 lines

include/hw/i386/intel_iommu.h +8 -0

         uint8_t womask[DMAR_REG_SIZE];  /* WO (write only - read returns 0) */
         uint32_t version;
+    /*
+     * Protects IOMMU states in general.  Normally we don't need to
+     * take this lock when we are with BQL held.  However we have code
+     * paths that may run even without BQL.  In those cases, we need
+     * to take the lock when we have access to IOMMU state
+     * informations, e.g., the IOTLB.
+     */
+    QemuMutex iommu_lock;

Some questions:

Quoted 1 line

1) Do we need to protect context cache too?

IMHO the context cache entry should work even without lock. That's a bit trickly since we have two cases that this cache will be updated:

(1) first translation of the address space of a device
(2) invalidation of context entries

For (2) IMHO we don't need to worry about since guest OS should be controlling that part, say, device should not be doing any translation (DMA operations) when the context entry is invalidated.

For (1) the worst case is that the context entry cache be updated multiple times with the same value by multiple threads. IMHO that'll be fine too.

But yes for sure we can protect that too with the iommu lock.

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Quoted 7 lines

Quoted 2 lines

Just a thought, using BQL may greatly simplify the code actually (consider we don't plan to remove BQL now).

Frankly speaking I don't understand why using BQL may greatly simplify the code... :( IMHO the lock here is really not a complicated one.

Note that IMO BQL is mostly helpful when we really want something to be run sequentially with some other things _already_ protected by BQL.

Except for the translate path from dataplane, I belive all other codes were already protected by BQL.

Quoted 2 lines

In this case, all the stuff is inside VT-d code itself (or other IOMMUs), why bother taking the BQL to make our life harder?

It looks to me it was as simple as:

(quoted diff) +1 -0

@@ -494,6 +494,7 @@ static MemoryRegionSection
 flatview_do_translate(FlatView *fv,
      IOMMUMemoryRegionClass *imrc;
      hwaddr page_mask = (hwaddr)(-1);
      hwaddr plen = (hwaddr)(-1);
+    int locked = false;
 
      if (plen_out) {

         plen = *plen_out;

(quoted diff) +0 -0

@@ -510,8 +511,15 @@ static MemoryRegionSection
 flatview_do_translate(FlatView *fv,
          }
          imrc = memory_region_get_iommu_class_nocheck(iommu_mr);
 

Quoted 11 lines

(quoted diff) +7 -0

+        if (!qemu_mutex_iothread_locked()) {
+            locked = true;
+            qemu_mutex_lock_iothread();
+        }
          iotlb = imrc->translate(iommu_mr, addr, is_write ?
                                  IOMMU_WO : IOMMU_RO);
+        if (locked) {
+            qemu_mutex_unlock_iothread();
+        }
          addr = ((iotlb.translated_addr & ~iotlb.addr_mask)
                  | (addr & iotlb.addr_mask));

Quoted 1 line

         page_mask &= iotlb.addr_mask;

We'll need to add the flags thing too. How do we flag-out existing thread-safe IOMMUs?

Quoted 10 lines

Quoted 4 lines

So, even if we want to provide a general lock for the translation procedure, I would prefer we add a per AddressSpace lock but not BQL.

It could be, but it needs more work on each specific IOMMU codes.

Quoted 3 lines

However still that will need some extra flag showing that whether we need the protection of not. For example, we may need to expliclitly turn that off for Power and s390. Would that really worth it?

It would cost just several lines of code, anything wrong with this?

It's not about anything wrong; it's just about preference.

I never said BQL won't work here. It will work. But if you have spent tens of hours working on BQL-related problems maybe you'll have the same preference as me... :)

IMHO the point is to decide which might be simpler and more efficient in general, really.

Quoted 36 lines

Quoted 13 lines

So my final preference is still current patch - we solve thread-safety problems in VT-d and IOMMU code. Again, we really should make sure all IOMMUs work with multithreads.

Quoted 8 lines

Quoted 8 lines

Quoted 3 lines

3) I think the issue is common to all other kinds of IOMMU, so can we simply synchronize before calling ->translate() in memory.c. This seems a more common solution.

I suspect Power and s390 live well with that. I think it mean at least these platforms won't have problem in concurrency. I'm adding DavidG in loop in case there is further comment. IMHO we should just make sure IOMMU code be thread safe, and we fix problem if there is.

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

Thanks,

Yes, it needs some investigation, but we have other IOMMUs like AMD, and we could have a flag to bypass BQL if IOMMU can synchronize by itself.

AMD is still only for experimental. If we really want to use it in production IMHO it'll need more testings and tunings not only on thread-safety but on other stuffs too. So again, we can just fix them when needed. I still don't see it a reason to depend on BQL here.

Well, it's not about BQL specifically, it's about whether we have or need a generic thread safety solution for all IOMMUs.

We have more IOMMUs than just AMD, s390 and ppc:

# git grep imrc-\>translate\ =
hw/alpha/typhoon.c:    imrc->translate = typhoon_translate_iommu;
hw/dma/rc4030.c:    imrc->translate = rc4030_dma_translate;
hw/i386/amd_iommu.c:    imrc->translate = amdvi_translate;
hw/i386/intel_iommu.c:    imrc->translate = vtd_iommu_translate;
hw/ppc/spapr_iommu.c:    imrc->translate = spapr_tce_translate_iommu;
hw/s390x/s390-pci-bus.c:    imrc->translate = s390_translate_iommu;
hw/sparc/sun4m_iommu.c:    imrc->translate = sun4m_translate_iommu;
hw/sparc64/sun4u_iommu.c:    imrc->translate = sun4u_translate_iommu;

Quoted 1 line

And we know there will be more in the near future.

Again - here I would suggest we consider thread-safe when implementing new ones. I suppose it should not be a hard thing to achieve.

I don't have more and new input here since I have had some in previous posts already. If this is still during discussion before the next post, I'll pick this patch out of the series since this patch is not related to other patches at all, so can be dealt with isolatedly.

Thanks,

Well, it's not about BQL specifically, it's about whether we have or need a generic thread safety solution for all IOMMUs.

We have more IOMMUs than just AMD, s390 and ppc:

# git grep imrc-\>translate\ =
hw/alpha/typhoon.c:    imrc->translate = typhoon_translate_iommu;
hw/dma/rc4030.c:    imrc->translate = rc4030_dma_translate;
hw/i386/amd_iommu.c:    imrc->translate = amdvi_translate;
hw/i386/intel_iommu.c:    imrc->translate = vtd_iommu_translate;
hw/ppc/spapr_iommu.c:    imrc->translate = spapr_tce_translate_iommu;
hw/s390x/s390-pci-bus.c:    imrc->translate = s390_translate_iommu;
hw/sparc/sun4m_iommu.c:    imrc->translate = sun4m_translate_iommu;
hw/sparc64/sun4u_iommu.c:    imrc->translate = sun4u_translate_iommu;

On Sat, Apr 28, 2018 at 10:42:11AM +0800, Jason Wang wrote:

[...]

Quoted 5 lines

Well, it's not about BQL specifically, it's about whether we have or need a generic thread safety solution for all IOMMUs.

We have more IOMMUs than just AMD, s390 and ppc:

Quoted 9 lines

# git grep imrc-\>translate\ =
hw/alpha/typhoon.c:    imrc->translate = typhoon_translate_iommu;
hw/dma/rc4030.c:    imrc->translate = rc4030_dma_translate;
hw/i386/amd_iommu.c:    imrc->translate = amdvi_translate;
hw/i386/intel_iommu.c:    imrc->translate = vtd_iommu_translate;
hw/ppc/spapr_iommu.c:    imrc->translate = spapr_tce_translate_iommu;
hw/s390x/s390-pci-bus.c:    imrc->translate = s390_translate_iommu;
hw/sparc/sun4m_iommu.c:    imrc->translate = sun4m_translate_iommu;
hw/sparc64/sun4u_iommu.c:    imrc->translate = sun4u_translate_iommu;

Sorry I didn't notice this one. This point is valid. But again, we need to know whether they are thread-safe already. For VT-d, it never hurt to have this patch to fix its own problem, so above is not a reason to not have current patch, since it solves different problems. Basically I'll see the solution of above problem as a separate patch as current one.

Meanwhile, even if we want to provide a general protection on that, again I would prefer not using BQL but use some common and new iommu-lock. BQL can be a nightmare sometimes.

Thanks,

Quoted 9 lines

# git grep imrc-\>translate\ =
hw/alpha/typhoon.c:    imrc->translate = typhoon_translate_iommu;
hw/dma/rc4030.c:    imrc->translate = rc4030_dma_translate;
hw/i386/amd_iommu.c:    imrc->translate = amdvi_translate;
hw/i386/intel_iommu.c:    imrc->translate = vtd_iommu_translate;
hw/ppc/spapr_iommu.c:    imrc->translate = spapr_tce_translate_iommu;
hw/s390x/s390-pci-bus.c:    imrc->translate = s390_translate_iommu;
hw/sparc/sun4m_iommu.c:    imrc->translate = sun4m_translate_iommu;
hw/sparc64/sun4u_iommu.c:    imrc->translate = sun4u_translate_iommu;

Sorry I didn't notice this one. This point is valid. But again, we need to know whether they are thread-safe already. For VT-d, it never hurt to have this patch to fix its own problem, so above is not a reason to not have current patch, since it solves different problems. Basically I'll see the solution of above problem as a separate patch as current one.

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Just a thought, using BQL may greatly simplify the code actually (consider we don't plan to remove BQL now).

Frankly speaking I don't understand why using BQL may greatly simplify the code... :( IMHO the lock here is really not a complicated one.

Note that IMO BQL is mostly helpful when we really want something to be run sequentially with some other things _already_ protected by BQL. In this case, all the stuff is inside VT-d code itself (or other IOMMUs), why bother taking the BQL to make our life harder?

So, even if we want to provide a general lock for the translation procedure, I would prefer we add a per AddressSpace lock but not BQL. However still that will need some extra flag showing that whether we need the protection of not. For example, we may need to expliclitly turn that off for Power and s390. Would that really worth it?

So my final preference is still current patch - we solve thread-safety problems in VT-d and IOMMU code. Again, we really should make sure all IOMMUs work with multithreads.

Quoted 20 lines · Peter Xu

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

2) Can we just reuse qemu BQL here?

I would prefer not. As I mentioned, at least I have spent too much time on fighting BQL already. I really hope we can start to use isolated locks when capable. BQL is always the worst choice to me.

Just a thought, using BQL may greatly simplify the code actually (consider we don't plan to remove BQL now).

Frankly speaking I don't understand why using BQL may greatly simplify the code... :( IMHO the lock here is really not a complicated one.

Note that IMO BQL is mostly helpful when we really want something to be run sequentially with some other things _already_ protected by BQL. In this case, all the stuff is inside VT-d code itself (or other IOMMUs), why bother taking the BQL to make our life harder?

So, even if we want to provide a general lock for the translation procedure, I would prefer we add a per AddressSpace lock but not BQL. However still that will need some extra flag showing that whether we need the protection of not. For example, we may need to expliclitly turn that off for Power and s390. Would that really worth it?

Quoted 4 lines

So my final preference is still current patch - we solve thread-safety problems in VT-d and IOMMU code. Again, we really should make sure all IOMMUs work with multithreads.

I agree. In particular, using BQL is _worse_ because it has very strict lock ordering requirements. Using fine-grained locks is greatly preferred as long as:

1) they are leaves in the lock ordering

2) they are not kept across calls to external callbacks (or there are no external callbacks involved)

Introduce a simplest interval tree implementation based on GTree. Current implementation is mostly tailored to maintain and trace device mapped IOVA ranges, but still it might be useful to other modules in the future.

It is naive in that it even does not allow user to pass in private structs along with the ranges. However it's good in that the tree can do mergings of ranges when necessary when without such information.

Signed-off-by Peter Xu <[email protected]>

---
  include/qemu/interval-tree.h | 130 ++++++++++++++++++++++++++
  util/interval-tree.c         | 217 +++++++++++++++++++++++++++++++++++++++++++
  util/Makefile.objs           |   1 +
  3 files changed, 348 insertions(+)

create mode 100644 include/qemu/interval-tree.h
create mode 100644 util/interval-tree.c

include/qemu/interval-tree.h new file +130 -0

new file mode 100644
index 0000000000..4485f4b338
@@ -0,0 +1,130 @@
+/*
+ * An very simplified interval tree implementation based on GTree.
+ *
+ * Copyright 2018 Red Hat, Inc.
+ *
+ * Authors:
+ *  Peter Xu <[email protected]>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ */
+#ifndef __INTERVAL_TREE_H__
+#define __INTERVAL_TREE_H__
+
+/*
+ * Currently the interval tree will only allow to keep ranges
+ * information, and no extra user data is allowed for each element.  A
+ * benefit is that we can merge adjacent ranges internally within the
+ * tree.  It can save a lot of memory when the ranges are splitted but
+ * mostly continuous.
+ *
+ * Note that current implementation does not provide any thread
+ * protections.  Callers of the interval tree should be responsible
+ * for the thread safety issue.
+ */
+
+#include <glib.h>
+
+#define  IT_OK           (0)
+#define  IT_ERR_OVERLAP  (-1)
+
+typedef unsigned long long ITValue;
+typedef struct ITTree ITTree;
+typedef gboolean (*it_tree_iterator)(ITValue start, ITValue end);
+
+struct ITRange {
+    ITValue start;
+    ITValue end;
+};
+typedef struct ITRange ITRange;
+
+/**
+ * it_tree_new:
+ *
+ * Create a new interval tree.
+ *
+ * Returns: the tree pointer when succeeded, or NULL if error.
+ */
+ITTree *it_tree_new(void);
+
+/**
+ * it_tree_insert:
+ *
+ * @tree: the interval tree to insert
+ * @start: the start of range, inclusive
+ * @end: the end of range, inclusive
+ *
+ * Insert an interval range to the tree.  If there is overlapped
+ * ranges, IT_ERR_OVERLAP will be returned.
+ *
+ * Return: 0 if succeeded, or <0 if error.
+ */
+int it_tree_insert(ITTree *tree, ITValue start, ITValue end);
+
+/**
+ * it_tree_remove:
+ *
+ * @tree: the interval tree to remove range from
+ * @start: the start of range, inclusive
+ * @end: the end of range, inclusive
+ *
+ * Remove an range from the tree.  The range does not need to be
+ * exactly what has inserted.  All the ranges that are included in the
+ * provided range will be removed from the tree.
+ *
+ * Return: 0 if succeeded, or <0 if error.
+ */
+int it_tree_remove(ITTree *tree, ITValue start, ITValue end);
+
+/**
+ * it_tree_find:
+ *
+ * @tree: the interval tree to search from
+ * @start: the start of range, inclusive
+ * @end: the end of range, inclusive
+ *
+ * Search for a range in the interval tree that overlaps with the
+ * range specified.  Only the first found range will be returned.
+ *
+ * Return: ITRange if found, or NULL if not found.  Note: the returned
+ * ITRange pointer is maintained internally.  User should only read
+ * the content but never modify or free the content.
+ */
+ITRange *it_tree_find(ITTree *tree, ITValue start, ITValue end);
+
+/**
+ * it_tree_find_value:
+ *
+ * @tree: the interval tree to search from
+ * @value: the value to find
+ *
+ * Similar to it_tree_find(), but it tries to find range (value, value).
+ *
+ * Return: same as it_tree_find().
+ */
+ITRange *it_tree_find_value(ITTree *tree, ITValue value);
+
+/**
+ * it_tree_foreach:
+ *
+ * @tree: the interval tree to iterate on
+ * @iterator: the interator for the ranges, return true to stop
+ *
+ * Search for a range in the interval tree.
+ *
+ * Return: 1 if found any overlap, 0 if not, <0 if error.
+ */
+void it_tree_foreach(ITTree *tree, it_tree_iterator iterator);
+
+/**
+ * it_tree_destroy:
+ *
+ * @tree: the interval tree to destroy
+ *
+ * Destroy an existing interval tree.
+ *
+ * Return: None.
+ */
+void it_tree_destroy(ITTree *tree);
+
+#endif

util/interval-tree.c new file +116 -0

new file mode 100644
index 0000000000..0e7a37c2c6
@@ -0,0 +1,217 @@
+/*
+ * An very simplified interval tree implementation based on GTree.
+ *
+ * Copyright 2018 Red Hat, Inc.
+ *
+ * Authors:
+ *  Peter Xu <[email protected]>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ */
+
+#include <glib.h>
+#include "qemu/interval-tree.h"
+
+/*
+ * Each element of the internal tree is an ITRange.  It is shared
+ * between the key and value of the element, or we can see it a tree
+ * with keys only but no values.
+ */
+
+struct ITTree {
+    GTree *tree;
+};
+
+static int it_tree_compare(gconstpointer a, gconstpointer b, gpointer data)
+{
+    const ITRange *r1 = a, *r2 = b;
+
+    if (r1->start > r2->end) {
+        return 1;
+    }
+
+    if (r1->end < r2->start) {
+        return -1;
+    }
+
+    /* Overlapped */
+    return 0;
+}
+
+/* Find out intersection of range A and B, put into OUT */
+static inline void it_range_and(ITRange *out, ITRange *a, ITRange *b)
+{
+    out->start = MAX(a->start, b->start);
+    out->end = MIN(a->end, b->end);
+}
+
+static inline gboolean it_range_equal(ITRange *a, ITRange *b)
+{
+    return a->start == b->start && a->end == b->end;
+}
+
+/* Whether ITRange A is superset of B? */
+static inline gboolean it_range_cover(ITRange *a, ITRange *b)
+{
+    return a->start <= b->start && a->end >= b->end;
+}
+
+ITTree *it_tree_new(void)
+{
+    ITTree *ittree = g_new0(ITTree, 1);
+
+    /* We don't have values actually, no need to free */
+    ittree->tree = g_tree_new_full(it_tree_compare, NULL, g_free, NULL);
+
+    return ittree;
+}
+
+ITRange *it_tree_find(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange range;
+
+    g_assert(tree);
+
+    range.start = start;
+    range.end = end;
+
+    return g_tree_lookup(tree->tree, &range);
+}
+
+ITRange *it_tree_find_value(ITTree *tree, ITValue value)
+{
+    return it_tree_find(tree, value, value);
+}
+
+static inline void it_tree_insert_internal(GTree *gtree, ITRange *range)
+{
+    /* Key and value are sharing the same range data */
+    g_tree_insert(gtree, range, range);
+}
+
+int it_tree_insert(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange *range = g_new0(ITRange, 1), *overlap;
+    GTree *gtree;
+
+    g_assert(tree);
+    g_assert(start <= end);
+
+    gtree = tree->tree;
+
+    range->start = start;
+    range->end = end;
+
+    /* We don't allow to insert range that overlaps with existings */
+    if (g_tree_lookup(gtree, range)) {
+        g_free(range);
+        return IT_ERR_OVERLAP;
+    }
+
+    /* Merge left adjacent range */
+    overlap = it_tree_find_value(tree, start - 1);
+    if (overlap) {
+        range->start = overlap->start;
+        g_tree_remove(gtree, overlap);
+    }

util/interval-tree.c new file +73 -0

+
+    return IT_OK;
+}
+
+static gboolean it_tree_traverse(gpointer key, gpointer value,
+                                gpointer data)
+{
+    it_tree_iterator iterator = data;
+    ITRange *range = key;
+
+    g_assert(key == value);
+
+    return iterator(range->start, range->end);
+}
+
+void it_tree_foreach(ITTree *tree, it_tree_iterator iterator)
+{
+    g_assert(tree && iterator);
+    g_tree_foreach(tree->tree, it_tree_traverse, iterator);
+}
+
+/* Remove subset `range', which is part of `overlap'. */
+static void it_tree_remove_subset(GTree *gtree, const ITRange *overlap,
+                                  const ITRange *range)
+{
+    ITRange *range1, *range2;
+
+    if (overlap->start < range->start) {
+        range1 = g_new0(ITRange, 1);
+        range1->start = overlap->start;
+        range1->end = range->start - 1;
+    } else {
+        range1 = NULL;
+    }
+    if (range->end < overlap->end) {
+        range2 = g_new0(ITRange, 1);
+        range2->start = range->end + 1;
+        range2->end = overlap->end;
+    } else {
+        range2 = NULL;
+    }
+
+    g_tree_remove(gtree, overlap);
+
+    if (range1) {
+        it_tree_insert_internal(gtree, range1);
+    }
+    if (range2) {
+        it_tree_insert_internal(gtree, range2);
+    }
+}
+
+int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange range = { .start = start, .end = end }, *overlap, and;
+    GTree *gtree;
+
+    g_assert(tree);
+
+    gtree = tree->tree;
+    while ((overlap = g_tree_lookup(gtree, &range))) {
+        if (it_range_equal(overlap, &range)) {
+            /* Exactly what we want to remove; done */
+            g_tree_remove(gtree, overlap);
+            break;
+        } else if (it_range_cover(overlap, &range)) {
+            /* Split existing range into two; done */
+            it_tree_remove_subset(gtree, overlap, &range);
+            break;
+        } else if (it_range_cover(&range, overlap)) {
+            /* Drop this range and continue */
+            g_tree_remove(gtree, overlap);
+        } else {

util/interval-tree.c new file +8 -0

+    return IT_OK;
+}
+
+void it_tree_destroy(ITTree *tree)
+{
+    g_tree_destroy(tree->tree);
+    g_free(tree);
+}

util/Makefile.objs +1 -0

index 728c3541db..4ac33910ed 100644
@@ -47,4 +47,5 @@ util-obj-y += qht.o
  util-obj-y += range.o
  util-obj-y += stats64.o
  util-obj-y += systemd.o
+util-obj-y += interval-tree.o
  util-obj-$(CONFIG_LINUX) += vfio-helpers.o

util/interval-tree.c line 126

Quoted 9 lines

util/interval-tree.c new file +9 -0

+    /* Merge right adjacent range */
+    overlap = it_tree_find_value(tree, end + 1);
+    if (overlap) {
+        range->end = overlap->end;
+        g_tree_remove(gtree, overlap);
+    }
+
+    /* Key and value are sharing the same range data */
+    it_tree_insert_internal(gtree, range);

A small optimization here is to delay the allocation until you're sure there's not overlapping.

Quoted 26 lines

util/interval-tree.c new file +26 -0

+int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange range = { .start = start, .end = end }, *overlap, and;
+    GTree *gtree;
+
+    g_assert(tree);
+
+    gtree = tree->tree;
+    while ((overlap = g_tree_lookup(gtree, &range))) {
+        if (it_range_equal(overlap, &range)) {
+            /* Exactly what we want to remove; done */
+            g_tree_remove(gtree, overlap);
+            break;
+        } else if (it_range_cover(overlap, &range)) {
+            /* Split existing range into two; done */
+            it_tree_remove_subset(gtree, overlap, &range);
+            break;
+        } else if (it_range_cover(&range, overlap)) {
+            /* Drop this range and continue */
+            g_tree_remove(gtree, overlap);
+        } else {
+            /*
+             * The range to remove has intersection with existing
+             * ranges.  Remove part of the range and continue
+             */
+            it_range_and(&and, overlap, &range);

util/interval-tree.c line 209

Quoted 5 lines

util/interval-tree.c new file +5 -0

+            g_assert(and.start <= and.end);
+            it_tree_remove_subset(gtree, overlap, &and);
+        }
+    }
+

Looks like what we need here is just calculate the intersection part the remove it.

util/interval-tree.c line 189

Quoted 11 lines

util/interval-tree.c new file +11 -0

+int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange range = { .start = start, .end = end }, *overlap, and;
+    GTree *gtree;
+
+    g_assert(tree);
+
+    gtree = tree->tree;
+    while ((overlap = g_tree_lookup(gtree, &range))) {
+        if (it_range_equal(overlap, &range)) {
+            /* Exactly what we want to remove; done */

util/interval-tree.c line 192

Quoted 3 lines

util/interval-tree.c new file +3 -0

+            g_tree_remove(gtree, overlap);
+            break;
+        } else if (it_range_cover(overlap, &range)) {

util/interval-tree.c line 196

Quoted 4 lines

util/interval-tree.c new file +4 -0

+            /* Split existing range into two; done */
+            it_tree_remove_subset(gtree, overlap, &range);
+            break;
+        } else if (it_range_cover(&range, overlap)) {

util/interval-tree.c line 199

Quoted 3 lines

util/interval-tree.c new file +3 -0

+            /* Drop this range and continue */
+            g_tree_remove(gtree, overlap);
+        } else {

util/interval-tree.c line 209

Quoted 10 lines

util/interval-tree.c new file +10 -0

+            /*
+             * The range to remove has intersection with existing
+             * ranges.  Remove part of the range and continue
+             */
+            it_range_and(&and, overlap, &range);
+            g_assert(and.start <= and.end);
+            it_tree_remove_subset(gtree, overlap, &and);
+        }
+    }
+

Looks like what we need here is just calculate the intersection part the remove it.

On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote:

[...]

Quoted 11 lines

util/interval-tree.c line 189

Quoted 11 lines

util/interval-tree.c new file +11 -0

+int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange range = { .start = start, .end = end }, *overlap, and;
+    GTree *gtree;
+
+    g_assert(tree);
+
+    gtree = tree->tree;
+    while ((overlap = g_tree_lookup(gtree, &range))) {
+        if (it_range_equal(overlap, &range)) {
+            /* Exactly what we want to remove; done */

[1]

Quoted 3 lines

util/interval-tree.c line 192

Quoted 3 lines

util/interval-tree.c new file +3 -0

+            g_tree_remove(gtree, overlap);
+            break;
+        } else if (it_range_cover(overlap, &range)) {

[2]

Quoted 4 lines

util/interval-tree.c line 196

Quoted 4 lines

util/interval-tree.c new file +4 -0

+            /* Split existing range into two; done */
+            it_tree_remove_subset(gtree, overlap, &range);
+            break;
+        } else if (it_range_cover(&range, overlap)) {

[3]

Quoted 3 lines

util/interval-tree.c line 199

Quoted 3 lines

util/interval-tree.c new file +3 -0

+            /* Drop this range and continue */
+            g_tree_remove(gtree, overlap);
+        } else {

[4]

Quoted 10 lines

util/interval-tree.c line 209

Quoted 10 lines

util/interval-tree.c new file +10 -0

+            /*
+             * The range to remove has intersection with existing
+             * ranges.  Remove part of the range and continue
+             */
+            it_range_and(&and, overlap, &range);
+            g_assert(and.start <= and.end);
+            it_tree_remove_subset(gtree, overlap, &and);
+        }
+    }
+

Quoted 2 lines

Looks like what we need here is just calculate the intersection part the remove it.

Here after a second thought, I am thining whether it'll be good I use a general routine in [4] to replace all [1-4].

The problem is that if we do that we'll depend on the next g_tree_lookup() to detect case [1-2] (in that case we'll find nothing in the lookup, but still we'll need to walk the tree) to break the loop, while IMHO that sometimes can be more expensive than the if clauses, especially when the tree is a bit large (each branch needs a if clause actually) and also note that in our use case we really have lots of cases for [1] and [2].

I think I can merge [3] into [4], but I might consider keeping [1] and
[2] since I don't really know whether merging them would be better. Anyway we can do that as follow up enhancement after the series merged. But I think we'll need some performance benchmarks.

Jason, what do you think?

Regards,

Quoted 61 lines · Peter Xu

On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote:

[...]

Quoted 11 lines

util/interval-tree.c line 189

Quoted 11 lines

util/interval-tree.c new file +11 -0

+int it_tree_remove(ITTree *tree, ITValue start, ITValue end)
+{
+    ITRange range = { .start = start, .end = end }, *overlap, and;
+    GTree *gtree;
+
+    g_assert(tree);
+
+    gtree = tree->tree;
+    while ((overlap = g_tree_lookup(gtree, &range))) {
+        if (it_range_equal(overlap, &range)) {
+            /* Exactly what we want to remove; done */

[1]

Quoted 3 lines

util/interval-tree.c line 192

Quoted 3 lines

util/interval-tree.c new file +3 -0

+            g_tree_remove(gtree, overlap);
+            break;
+        } else if (it_range_cover(overlap, &range)) {

[2]

Quoted 4 lines

util/interval-tree.c line 196

Quoted 4 lines

util/interval-tree.c new file +4 -0

+            /* Split existing range into two; done */
+            it_tree_remove_subset(gtree, overlap, &range);
+            break;
+        } else if (it_range_cover(&range, overlap)) {

[3]

Quoted 3 lines

util/interval-tree.c line 199

Quoted 3 lines

util/interval-tree.c new file +3 -0

+            /* Drop this range and continue */
+            g_tree_remove(gtree, overlap);
+        } else {

[4]

Quoted 10 lines

util/interval-tree.c line 209

Quoted 10 lines

util/interval-tree.c new file +10 -0

+            /*
+             * The range to remove has intersection with existing
+             * ranges.  Remove part of the range and continue
+             */
+            it_range_and(&and, overlap, &range);
+            g_assert(and.start <= and.end);
+            it_tree_remove_subset(gtree, overlap, &and);
+        }
+    }
+

Quoted 2 lines

Looks like what we need here is just calculate the intersection part the remove it.

Here after a second thought, I am thining whether it'll be good I use a general routine in [4] to replace all [1-4].

The problem is that if we do that we'll depend on the next g_tree_lookup() to detect case [1-2] (in that case we'll find nothing in the lookup, but still we'll need to walk the tree) to break the loop, while IMHO that sometimes can be more expensive than the if clauses, especially when the tree is a bit large (each branch needs a if clause actually) and also note that in our use case we really have lots of cases for [1] and [2].

I think I can merge [3] into [4], but I might consider keeping [1] and
[2] since I don't really know whether merging them would be better. Anyway we can do that as follow up enhancement after the series merged. But I think we'll need some performance benchmarks.

Quoted 4 lines

Jason, what do you think?

Regards,

Sounds good (but I don't promise I won't have new comments :))

For each VTDAddressSpace, now we maintain what IOVA ranges we have mapped and what we have not. With that information, now we only send MAP or UNMAP when necessary. Say, we don't send MAP notifies if we know we have already mapped the range, meanwhile we don't send UNMAP notifies if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

include/hw/i386/intel_iommu.h +2 -0

index 486e205e79..09a2e94404 100644
@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +4 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+

hw/i386/intel_iommu.c +14 -0

+    } else {
+        if (!mapped) {
+            /* Skip since we didn't map this range at all */
+            trace_vtd_page_walk_one_skip_unmap(entry->iova, entry->addr_mask);
+            return 0;
+        }
+        it_tree_remove(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);
+    }
+
      trace_vtd_page_walk_one(level, entry->iova, entry->translated_addr,
                              entry->addr_mask, entry->perm);
+
      return hook_fn(entry, private);
  }
 

@@ -2798,6 +2823,7 @@ VTDAddressSpace *vtd_find_add_as(IntelIOMMUState *s, PCIBus *bus, int devfn)
          vtd_dev_as->devfn = (uint8_t)devfn;
          vtd_dev_as->iommu_state = s;
          vtd_dev_as->context_cache_entry.context_cache_gen = 0;
+        vtd_dev_as->iova_tree = it_tree_new();
 
          /*
           * Memory region relationships looks like (Address range shows

@@ -2894,6 +2920,8 @@ static void vtd_address_space_unmap(VTDAddressSpace *as, IOMMUNotifier *n)
                               VTD_PCI_FUNC(as->devfn),
                               entry.iova, size);
 
+    it_tree_remove(as->iova_tree, entry.iova, entry.iova + entry.addr_mask);
+
      memory_region_notify_one(n, &entry);
  }
 

hw/i386/trace-events +2 -0

index 22d44648af..677f83420d 100644
@@ -40,6 +40,8 @@ vtd_replay_ce_valid(uint8_t bus, uint8_t dev, uint8_t fn, uint16_t domain, uint6
  vtd_replay_ce_invalid(uint8_t bus, uint8_t dev, uint8_t fn) "replay invalid context device %02"PRIx8":%02"PRIx8".%02"PRIx8
  vtd_page_walk_level(uint64_t addr, uint32_t level, uint64_t start, uint64_t end) "walk (base=0x%"PRIx64", level=%"PRIu32") iova range 0x%"PRIx64" - 0x%"PRIx64
  vtd_page_walk_one(uint32_t level, uint64_t iova, uint64_t gpa, uint64_t mask, int perm) "detected page level 0x%"PRIx32" iova 0x%"PRIx64" -> gpa 0x%"PRIx64" mask 0x%"PRIx64" perm %d"
+vtd_page_walk_one_skip_map(uint64_t iova, uint64_t mask, uint64_t start, uint64_t end) "iova 0x%"PRIx64" mask 0x%"PRIx64" start 0x%"PRIx64" end 0x%"PRIx64
+vtd_page_walk_one_skip_unmap(uint64_t iova, uint64_t mask) "iova 0x%"PRIx64" mask 0x%"PRIx64
  vtd_page_walk_skip_read(uint64_t iova, uint64_t next) "Page walk skip iova 0x%"PRIx64" - 0x%"PRIx64" due to unable to read"
  vtd_page_walk_skip_perm(uint64_t iova, uint64_t next) "Page walk skip iova 0x%"PRIx64" - 0x%"PRIx64" due to perm empty"
  vtd_page_walk_skip_reserve(uint64_t iova, uint64_t next) "Page walk skip iova 0x%"PRIx64" - 0x%"PRIx64" due to rsrv set"

Quoted 46 lines · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges we have mapped and what we have not. With that information, now we only send MAP or UNMAP when necessary. Say, we don't send MAP notifies if we know we have already mapped the range, meanwhile we don't send UNMAP notifies if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

include/hw/i386/intel_iommu.h +2 -0

index 486e205e79..09a2e94404 100644
@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
  struct VTDBus {

hw/i386/intel_iommu.c +4 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
      assert(hook_fn);
+

hw/i386/intel_iommu.c typedef struct { · line 787

Quoted 10 lines

hw/i386/intel_iommu.c +10 -0

+    /* Update local IOVA mapped ranges */
+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry->addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

1) map A (iova) to B (pa)
2) invalidate A

3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it was allowed by the spec (though I think so).

From: Jason Wang [mailto:[email protected]]
Sent: Friday, April 27, 2018 2:08 PM

Quoted 2 lines · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges we have mapped and what we have not. With that information, now we only

send

Quoted 1 line

MAP or UNMAP when necessary. Say, we don't send MAP notifies if we

know

Quoted 1 line

we have already mapped the range, meanwhile we don't send UNMAP

notifies

Review

Quoted 10 lines

if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 36 lines

index 486e205e79..09a2e94404 100644

include/hw/i386/intel_iommu.h +2 -0

@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +5 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+
+    /* Update local IOVA mapped ranges */

hw/i386/intel_iommu.c typedef struct { · line 789

Quoted 10 lines

hw/i386/intel_iommu.c +9 -0

+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

1) map A (iova) to B (pa)
2) invalidate A
3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it was allowed by the spec (though I think so).

Quoted 71 lines

From: Jason Wang [mailto:[email protected]]
Sent: Friday, April 27, 2018 2:08 PM

Quoted 2 lines · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges we have mapped and what we have not. With that information, now we only

send

Quoted 1 line

MAP or UNMAP when necessary. Say, we don't send MAP notifies if we

know

Quoted 1 line

we have already mapped the range, meanwhile we don't send UNMAP

notifies

Review

Quoted 10 lines

if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 36 lines

index 486e205e79..09a2e94404 100644

include/hw/i386/intel_iommu.h +2 -0

@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +5 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+
+    /* Update local IOVA mapped ranges */

hw/i386/intel_iommu.c typedef struct { · line 789

Quoted 10 lines

hw/i386/intel_iommu.c +9 -0

+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

Quoted 8 lines

1) map A (iova) to B (pa)
2) invalidate A
3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it was allowed by the spec (though I think so).

I thought it was wrong in a glimpse, but then changed my mind after another thinking. As long as device driver can quiescent the device to not access A (iova) within above window, then above sequence has no problem since any stale mappings (A->B) added before step 4) won't be used and then will get flushed after step 4). Regarding to that actually the 1st invalidation can be skipped:

1) map A (iova) to B (pa)
2) driver programs device to use A
3) driver programs device to not use A
4) map A (iova) to C (pa)

	A->B may be still valid in IOTLB

5) invalidate A
6) driver programs device to use A

From: Peter Xu [mailto:[email protected]]
Sent: Friday, April 27, 2018 3:28 PM

Quoted 5 lines · Kevin

Quoted 5 lines

From: Jason Wang [mailto:[email protected]]
Sent: Friday, April 27, 2018 2:08 PM

Quoted 1 line · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges we

have

Quoted 3 lines

Quoted 3 lines

Quoted 1 line

mapped and what we have not. With that information, now we only

send

Quoted 1 line

MAP or UNMAP when necessary. Say, we don't send MAP notifies if

we

Quoted 2 lines

Quoted 2 lines

know

Quoted 1 line

we have already mapped the range, meanwhile we don't send

UNMAP

Quoted 61 lines

Quoted 61 lines

notifies

Review

Quoted 10 lines

if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 36 lines

index 486e205e79..09a2e94404 100644

include/hw/i386/intel_iommu.h +2 -0

@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +5 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+
+    /* Update local IOVA mapped ranges */

hw/i386/intel_iommu.c typedef struct { · line 789

Quoted 10 lines

hw/i386/intel_iommu.c +9 -0

+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

Quoted 8 lines

Quoted 8 lines

1) map A (iova) to B (pa)
2) invalidate A
3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it was allowed by the spec (though I think so).

Hi, Kevin,

Thanks for joining the discussion.

Quoted 8 lines

I thought it was wrong in a glimpse, but then changed my mind after another thinking. As long as device driver can quiescent the device to not access A (iova) within above window, then above sequence has no problem since any stale mappings (A->B) added before step 4) won't be used and then will get flushed after step 4). Regarding to that actually the 1st invalidation can be skipped:

Quoted 7 lines

1) map A (iova) to B (pa)
2) driver programs device to use A
3) driver programs device to not use A
4) map A (iova) to C (pa)

	A->B may be still valid in IOTLB

5) invalidate A
6) driver programs device to use A

Note that IMHO this is a bit different from Jason's example, and it'll be fine. Current code should work well with this scenario since the emulation code will not aware of the map A until step (5). Then we'll have the correct mapping.

While for Jason's example it's exactly the extra PSI that might cause stale mappings (though again I think it's still problematic...).

Actually I think I can just fix up the code even if Jason's case happens by unmapping that first then remap:

hw/i386/intel_iommu.c +14 -6

index 31e9b52452..2a9584f9d8 100644
@@ -778,13 +778,21 @@ static int vtd_page_walk_one(IOMMUTLBEntry
 *entry, int level,
     /* Update local IOVA mapped ranges */
     if (entry->perm) {
         if (mapped) {
-            /* Skip since we have already mapped this range */
-            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 >addr_mask,
-                                             mapped->start, mapped->end);
-            return 0;
+            int ret;
+            /* Cache the write permission */
+            IOMMUAccessFlags flags = entry->perm;
+
+            /* UNMAP the old first then remap.  No need to touch IOVA tree */
+            entry->perm = IOMMU_NONE;
+            ret = hook_fn(entry, private);
+            if (ret) {
+                return ret;
+            }
+            entry->perm = flags;
+        } else {
+            it_tree_insert(as->iova_tree, entry->iova,
+                           entry->iova + entry->addr_mask);
         }
-        it_tree_insert(as->iova_tree, entry->iova,
-                       entry->iova + entry->addr_mask);
     } else {

         if (!mapped) {
             /* Skip since we didn't map this range at all */

If we really think it necessary, I can squash this in, though this is a bit ugly. But I just want to confirm whether this would be anything we want...

Quoted 107 lines

From: Peter Xu [mailto:[email protected]]
Sent: Friday, April 27, 2018 3:28 PM

Quoted 5 lines · Kevin

Quoted 5 lines

From: Jason Wang [mailto:[email protected]]
Sent: Friday, April 27, 2018 2:08 PM

Quoted 1 line · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges we

have

Quoted 3 lines

Quoted 3 lines

Quoted 1 line

mapped and what we have not. With that information, now we only

send

Quoted 1 line

MAP or UNMAP when necessary. Say, we don't send MAP notifies if

we

Quoted 2 lines

Quoted 2 lines

know

Quoted 1 line

we have already mapped the range, meanwhile we don't send

UNMAP

Quoted 61 lines

Quoted 61 lines

notifies

Review

Quoted 10 lines

if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 36 lines

index 486e205e79..09a2e94404 100644

include/hw/i386/intel_iommu.h +2 -0

@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +5 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+
+    /* Update local IOVA mapped ranges */

hw/i386/intel_iommu.c typedef struct { · line 789

Quoted 10 lines

hw/i386/intel_iommu.c +9 -0

+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

Quoted 8 lines

Quoted 8 lines

1) map A (iova) to B (pa)
2) invalidate A
3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it was allowed by the spec (though I think so).

Hi, Kevin,

Thanks for joining the discussion.

Quoted 8 lines

I thought it was wrong in a glimpse, but then changed my mind after another thinking. As long as device driver can quiescent the device to not access A (iova) within above window, then above sequence has no problem since any stale mappings (A->B) added before step 4) won't be used and then will get flushed after step 4). Regarding to that actually the 1st invalidation can be skipped:

Quoted 7 lines

1) map A (iova) to B (pa)
2) driver programs device to use A
3) driver programs device to not use A
4) map A (iova) to C (pa)

	A->B may be still valid in IOTLB

5) invalidate A
6) driver programs device to use A

Quoted 4 lines

Note that IMHO this is a bit different from Jason's example, and it'll be fine. Current code should work well with this scenario since the emulation code will not aware of the map A until step (5). Then we'll have the correct mapping.

you are right. we still need the extra PSI otherwise the 1st mapping is problematic for use. So back to Jason's example.

Quoted 3 lines

While for Jason's example it's exactly the extra PSI that might cause stale mappings (though again I think it's still problematic...).

problematic in software side (e.g. that way IOMMU core relies on device drivers which conflict with the value of using IOMMU) but it is OK from hardware p.o.v. btw the extra PSI itself doesn't cause stale mapping. Instead it is device activity after that PSI may cause it.

Quoted 39 lines

Actually I think I can just fix up the code even if Jason's case happens by unmapping that first then remap:

hw/i386/intel_iommu.c +14 -6

index 31e9b52452..2a9584f9d8 100644
@@ -778,13 +778,21 @@ static int vtd_page_walk_one(IOMMUTLBEntry
 *entry, int level,
     /* Update local IOVA mapped ranges */
     if (entry->perm) {
         if (mapped) {
-            /* Skip since we have already mapped this range */
-            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 >addr_mask,
-                                             mapped->start, mapped->end);
-            return 0;
+            int ret;
+            /* Cache the write permission */
+            IOMMUAccessFlags flags = entry->perm;
+
+            /* UNMAP the old first then remap.  No need to touch IOVA tree */
+            entry->perm = IOMMU_NONE;
+            ret = hook_fn(entry, private);
+            if (ret) {
+                return ret;
+            }
+            entry->perm = flags;
+        } else {
+            it_tree_insert(as->iova_tree, entry->iova,
+                           entry->iova + entry->addr_mask);
         }
-        it_tree_insert(as->iova_tree, entry->iova,
-                       entry->iova + entry->addr_mask);
     } else {

         if (!mapped) {
             /* Skip since we didn't map this range at all */

Quoted 4 lines

If we really think it necessary, I can squash this in, though this is a bit ugly. But I just want to confirm whether this would be anything we want...

I didn’t look into your actual code yet. If others think above change is OK then it's definitely good as we conform to hardware behavior here. Otherwise if there is a way to detect such unusual usage and then adopt some action (say kill the VM), it's also fine since user knows he runs a bad OS which is not supported by Qemu. It's just not good if such situation is not handled, which leads to some undefined behavior which nobody knows the reason w/o hard debug into. :-)

Quoted 168 lines · Kevin

Quoted 107 lines

From: Peter Xu [mailto:[email protected]]
Sent: Friday, April 27, 2018 3:28 PM

Quoted 5 lines · Kevin

Quoted 5 lines

From: Jason Wang [mailto:[email protected]]
Sent: Friday, April 27, 2018 2:08 PM

Quoted 1 line · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges we

have

Quoted 3 lines

Quoted 3 lines

Quoted 1 line

mapped and what we have not. With that information, now we only

send

Quoted 1 line

MAP or UNMAP when necessary. Say, we don't send MAP notifies if

we

Quoted 2 lines

Quoted 2 lines

know

Quoted 1 line

we have already mapped the range, meanwhile we don't send

UNMAP

Quoted 61 lines

Quoted 61 lines

notifies

Review

Quoted 10 lines

if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28 ++++++++++++++++++++++++++++
  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 36 lines

index 486e205e79..09a2e94404 100644

include/hw/i386/intel_iommu.h +2 -0

@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +5 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+
+    /* Update local IOVA mapped ranges */

hw/i386/intel_iommu.c typedef struct { · line 789

Quoted 10 lines

hw/i386/intel_iommu.c +9 -0

+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

Quoted 8 lines

Quoted 8 lines

1) map A (iova) to B (pa)
2) invalidate A
3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it was allowed by the spec (though I think so).

Hi, Kevin,

Thanks for joining the discussion.

Quoted 8 lines

I thought it was wrong in a glimpse, but then changed my mind after another thinking. As long as device driver can quiescent the device to not access A (iova) within above window, then above sequence has no problem since any stale mappings (A->B) added before step 4) won't be used and then will get flushed after step 4). Regarding to that actually the 1st invalidation can be skipped:

Quoted 7 lines

1) map A (iova) to B (pa)
2) driver programs device to use A
3) driver programs device to not use A
4) map A (iova) to C (pa)

	A->B may be still valid in IOTLB

5) invalidate A
6) driver programs device to use A

Quoted 4 lines

Note that IMHO this is a bit different from Jason's example, and it'll be fine. Current code should work well with this scenario since the emulation code will not aware of the map A until step (5). Then we'll have the correct mapping.

you are right. we still need the extra PSI otherwise the 1st mapping is problematic for use. So back to Jason's example.

Quoted 3 lines

While for Jason's example it's exactly the extra PSI that might cause stale mappings (though again I think it's still problematic...).

problematic in software side (e.g. that way IOMMU core relies on device drivers which conflict with the value of using IOMMU) but it is OK from hardware p.o.v. btw the extra PSI itself doesn't cause stale mapping. Instead it is device activity after that PSI may cause it.

Quoted 39 lines

Actually I think I can just fix up the code even if Jason's case happens by unmapping that first then remap:

hw/i386/intel_iommu.c +14 -6

index 31e9b52452..2a9584f9d8 100644
@@ -778,13 +778,21 @@ static int vtd_page_walk_one(IOMMUTLBEntry
 *entry, int level,
     /* Update local IOVA mapped ranges */
     if (entry->perm) {
         if (mapped) {
-            /* Skip since we have already mapped this range */
-            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 >addr_mask,
-                                             mapped->start, mapped->end);
-            return 0;
+            int ret;
+            /* Cache the write permission */
+            IOMMUAccessFlags flags = entry->perm;
+
+            /* UNMAP the old first then remap.  No need to touch IOVA tree */
+            entry->perm = IOMMU_NONE;
+            ret = hook_fn(entry, private);
+            if (ret) {
+                return ret;
+            }
+            entry->perm = flags;
+        } else {
+            it_tree_insert(as->iova_tree, entry->iova,
+                           entry->iova + entry->addr_mask);
         }
-        it_tree_insert(as->iova_tree, entry->iova,
-                       entry->iova + entry->addr_mask);
     } else {

         if (!mapped) {
             /* Skip since we didn't map this range at all */

Quoted 4 lines

If we really think it necessary, I can squash this in, though this is a bit ugly. But I just want to confirm whether this would be anything we want...

Quoted 8 lines

I didn’t look into your actual code yet. If others think above change is OK then it's definitely good as we conform to hardware behavior here. Otherwise if there is a way to detect such unusual usage and then adopt some action (say kill the VM), it's also fine since user knows he runs a bad OS which is not supported by Qemu. It's just not good if such situation is not handled, which leads to some undefined behavior which nobody knows the reason w/o hard debug into. :-)

Yeah, then let me do this. :)

Jason, would you be good with above change squashed?

From: Peter Xu [mailto:[email protected]]
Sent: Friday, April 27, 2018 7:40 PM

Quoted 10 lines · Peter Xu

Quoted 9 lines · Kevin

Quoted 9 lines

From: Peter Xu [mailto:[email protected]]
Sent: Friday, April 27, 2018 3:28 PM

Quoted 5 lines · Kevin

Quoted 5 lines

From: Jason Wang [mailto:[email protected]]
Sent: Friday, April 27, 2018 2:08 PM

Quoted 1 line · Peter Xu

For each VTDAddressSpace, now we maintain what IOVA ranges

we

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

have

Quoted 1 line

Quoted 1 line

Quoted 1 line

mapped and what we have not. With that information, now we

only

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

send

Quoted 1 line

MAP or UNMAP when necessary. Say, we don't send MAP

notifies if

Quoted 11 lines

Quoted 11 lines

Quoted 11 lines

we

Quoted 2 lines

Quoted 2 lines

know

Quoted 1 line

we have already mapped the range, meanwhile we don't send

UNMAP

Quoted 7 lines

Quoted 7 lines

notifies

Quoted 6 lines

if we know we never mapped the range at all.

Signed-off-by Peter Xu <[email protected]>

---
  include/hw/i386/intel_iommu.h |  2 ++
  hw/i386/intel_iommu.c         | 28

++++++++++++++++++++++++++++

Quoted 54 lines

Quoted 54 lines

Quoted 54 lines

Quoted 54 lines

Quoted 54 lines

Review

Quoted 4 lines

  hw/i386/trace-events          |  2 ++
  3 files changed, 32 insertions(+)

(quoted diff) +0 -0

b/include/hw/i386/intel_iommu.h

Quoted 36 lines

index 486e205e79..09a2e94404 100644

include/hw/i386/intel_iommu.h +2 -0

@@ -27,6 +27,7 @@
  #include "hw/i386/ioapic.h"
  #include "hw/pci/msi.h"
  #include "hw/sysbus.h"
+#include "qemu/interval-tree.h"
 
  #define TYPE_INTEL_IOMMU_DEVICE "intel-iommu"
  #define INTEL_IOMMU_DEVICE(obj) \

@@ -95,6 +96,7 @@ struct VTDAddressSpace {
      QLIST_ENTRY(VTDAddressSpace) next;
      /* Superset of notifier flags that this address space has */
      IOMMUNotifierFlag notifier_flags;
+    ITTree *iova_tree;          /* Traces mapped IOVA ranges */
  };
 
  struct VTDBus {

hw/i386/intel_iommu.c +5 -0

index a19c18b8d4..8f396a5d13 100644
@@ -768,12 +768,37 @@ typedef struct {
  static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,
                               vtd_page_walk_info *info)
  {
+    VTDAddressSpace *as = info->as;
      vtd_page_walk_hook hook_fn = info->hook_fn;
      void *private = info->private;
+    ITRange *mapped = it_tree_find(as->iova_tree, entry->iova,
+                                   entry->iova + entry->addr_mask);
 
      assert(hook_fn);
+
+    /* Update local IOVA mapped ranges */

hw/i386/intel_iommu.c typedef struct { · line 789

Quoted 10 lines

hw/i386/intel_iommu.c +9 -0

+    if (entry->perm) {
+        if (mapped) {
+            /* Skip since we have already mapped this range */
+            trace_vtd_page_walk_one_skip_map(entry->iova, entry-
 addr_mask,
+                                             mapped->start, mapped->end);
+            return 0;
+        }
+        it_tree_insert(as->iova_tree, entry->iova,
+                       entry->iova + entry->addr_mask);

I was consider a case e.g:

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

1) map A (iova) to B (pa)
2) invalidate A
3) map A (iova) to C (pa)
4) invalidate A

In this case, we will probably miss a walk here. But I'm not sure it

was

Quoted 41 lines

Quoted 41 lines

Quoted 23 lines

Quoted 2 lines

Quoted 2 lines

allowed by the spec (though I think so).

Hi, Kevin,

Thanks for joining the discussion.

Quoted 8 lines

I thought it was wrong in a glimpse, but then changed my mind after another thinking. As long as device driver can quiescent the device to not access A (iova) within above window, then above sequence has no problem since any stale mappings (A->B) added before step 4) won't be used and then will get flushed after step 4). Regarding to that actually the 1st invalidation can be skipped:

Quoted 7 lines

1) map A (iova) to B (pa)
2) driver programs device to use A
3) driver programs device to not use A
4) map A (iova) to C (pa)

	A->B may be still valid in IOTLB

5) invalidate A
6) driver programs device to use A

Quoted 4 lines

Note that IMHO this is a bit different from Jason's example, and it'll be fine. Current code should work well with this scenario since the emulation code will not aware of the map A until step (5). Then we'll have the correct mapping.

you are right. we still need the extra PSI otherwise the 1st mapping is problematic for use. So back to Jason's example.

Quoted 3 lines

While for Jason's example it's exactly the extra PSI that might cause stale mappings (though again I think it's still problematic...).

problematic in software side (e.g. that way IOMMU core relies on device drivers which conflict with the value of using IOMMU) but it is OK from hardware p.o.v. btw the extra PSI itself doesn't cause stale mapping. Instead it is device activity after that PSI may cause it.

Quoted 1 line

Quoted 8 lines

Quoted 8 lines

hw/i386/intel_iommu.c static int

Quoted 8 lines

Actually I think I can just fix up the code even if Jason's case happens by unmapping that first then remap:

hw/i386/intel_iommu.c +0 -0

index 31e9b52452..2a9584f9d8 100644
@@ -778,13 +778,21 @@ static int

vtd_page_walk_one(IOMMUTLBEntry

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

hw/i386/intel_iommu.c +0 -2

 *entry, int level,
     /* Update local IOVA mapped ranges */
     if (entry->perm) {
         if (mapped) {
-            /* Skip since we have already mapped this range */
-            trace_vtd_page_walk_one_skip_map(entry->iova, entry-

Quoted 8 lines

Quoted 8 lines

hw/i386/intel_iommu.c static int vtd_page_walk_one(IOMMUTLBEntry *entry, int level,

Quoted 8 lines

hw/i386/intel_iommu.c +5 -2

 >addr_mask,
-                                             mapped->start, mapped->end);
-            return 0;
+            int ret;
+            /* Cache the write permission */
+            IOMMUAccessFlags flags = entry->perm;
+
+            /* UNMAP the old first then remap.  No need to touch IOVA

tree */

Quoted 30 lines

Quoted 21 lines

Quoted 16 lines

hw/i386/intel_iommu.c +9 -2

+            entry->perm = IOMMU_NONE;
+            ret = hook_fn(entry, private);
+            if (ret) {
+                return ret;
+            }
+            entry->perm = flags;
+        } else {
+            it_tree_insert(as->iova_tree, entry->iova,
+                           entry->iova + entry->addr_mask);
         }
-        it_tree_insert(as->iova_tree, entry->iova,
-                       entry->iova + entry->addr_mask);
     } else {

         if (!mapped) {
             /* Skip since we didn't map this range at all */

Quoted 4 lines

If we really think it necessary, I can squash this in, though this is a bit ugly. But I just want to confirm whether this would be anything we want...

Quoted 8 lines

I didn’t look into your actual code yet. If others think above change is OK then it's definitely good as we conform to hardware behavior here. Otherwise if there is a way to detect such unusual usage and then adopt some action (say kill the VM), it's also fine since user knows he runs a bad OS which is not supported by Qemu. It's just not good if such situation is not handled, which leads to some undefined behavior which nobody knows the reason w/o hard debug into. :-)

Quoted 3 lines

Yeah, then let me do this. :)

Jason, would you be good with above change squashed?

Self NAK on this...

More than half of the whole series tries to solve the solo problem that we unmapped some pages that were already mapped, which proved to
be wrong. Now if we squash the change we will do the same wrong thing, so we'll still have a very small window that the remapped page be missing from a device's POV.

Now to solve this I suppose we'll need to cache every translation then we can know whether a mapping has changed, and we only remap when it really has changed. But I'm afraid that can be a big amount of data for nested guests. For a most common 4G L2 guest, I think the worst case (e.g., no huge page at all, no continuous pages) is 4G/4K=1M entries in that tree.

Is it really worth it to solve this possibly-buggy-guest-OS problem with such a overhead? I don't know..

I'm not sure whether it's still acceptable that we put this issue aside. We should know that normal OSs should not do this, and if they do, IMHO it proves a buggy OS already (so even from hardware POV we allow this, from software POV it should still be problematic), then it'll have problem for sure, but only within the VM itself, and it won't affect other VMs or the host. That sounds still reasonable to me so far.

Of course I'm always willing to listen to more advice on this.

Thanks,

--
Peter Xu

Quoted 9 lines

Self NAK on this...

More than half of the whole series tries to solve the solo problem that we unmapped some pages that were already mapped, which proved to
be wrong. Now if we squash the change we will do the same wrong thing, so we'll still have a very small window that the remapped page be missing from a device's POV.

Quoted 6 lines

Now to solve this I suppose we'll need to cache every translation then we can know whether a mapping has changed, and we only remap when it really has changed. But I'm afraid that can be a big amount of data for nested guests. For a most common 4G L2 guest, I think the worst case (e.g., no huge page at all, no continuous pages) is 4G/4K=1M entries in that tree.

I think one key factor to think about is the effect of PSI. From VT-d spec, all internal caches (IOTLB entries, paging-structure cache entries, etc.) associated with specified address range must be flushed accordingly, i.e. no cache on stale mapping. Now per-device iova ranges is new type of cache introduced by Qemu VT-d. It doesn't cache actual mapping but its purpose is to decide whether to notify VFIO for updated mapping. In this manner if we don't differentiate whether an entry is for stale mapping, looks the definition of PSI is broken.

ask another question. In reality how much improvement this patch can bring, i.e. is it usual to see guest map on an already mapped region, or unmap an already unmapped region?

Quoted 4 lines

Is it really worth it to solve this possibly-buggy-guest-OS problem with such a overhead? I don't know..

If adding overhead removes the benefit of this patch, then definitely not a good thing.

Quoted 9 lines

I'm not sure whether it's still acceptable that we put this issue aside. We should know that normal OSs should not do this, and if they do, IMHO it proves a buggy OS already (so even from hardware POV we allow this, from software POV it should still be problematic), then it'll have problem for sure, but only within the VM itself, and it won't affect other VMs or the host. That sounds still reasonable to me so far.

As said earlier, what I'm worried is whether there is a way to detect such case when your assumption is violated. usually emulation can choose to not implement all the features which are supported on the real device, but it's done in a way that non-supported features/behaviors can be reported to guest (based on spec definition) thus guest knows the expectation from the emulated device...

IMHO the guest can't really detect this, but it'll found that the device is not working functionally if it's doing something like what Jason has mentioned.

Actually now I have had an idea if we really want to live well even with Jason's example: maybe we'll need to identify PSI/DSI. For DSI, we don't remap for mapped pages; for PSI, we unmap and remap the mapped pages. That'll complicate the stuff a bit, but it should satisfy all the people.

Thanks,

Quoted 10 lines · Peter Xu

IMHO the guest can't really detect this, but it'll found that the device is not working functionally if it's doing something like what Jason has mentioned.

Actually now I have had an idea if we really want to live well even with Jason's example: maybe we'll need to identify PSI/DSI. For DSI, we don't remap for mapped pages; for PSI, we unmap and remap the mapped pages. That'll complicate the stuff a bit, but it should satisfy all the people.

Quoted 1 line

Thanks,

So it looks like there will be still unnecessary unamps.

How about record the mappings in the tree too?

Quoted 12 lines · Jason Wang

Quoted 10 lines · Peter Xu

IMHO the guest can't really detect this, but it'll found that the device is not working functionally if it's doing something like what Jason has mentioned.

Actually now I have had an idea if we really want to live well even with Jason's example: maybe we'll need to identify PSI/DSI. For DSI, we don't remap for mapped pages; for PSI, we unmap and remap the mapped pages. That'll complicate the stuff a bit, but it should satisfy all the people.

Quoted 2 lines

Quoted 1 line

Thanks,

So it looks like there will be still unnecessary unamps.

Could I ask what do you mean by "unecessary unmaps"?

Quoted 1 line

How about record the mappings in the tree too?

As I mentioned, for L1 guest (e.g., DPDK applications running in L1) it'll be fine. But I'm just afraid we will have other use cases, like the L2 guests. That might need tons of the mapping entries in the worst case scenario.

Quoted 13 lines · Peter Xu

Quoted 12 lines · Jason Wang

Quoted 10 lines · Peter Xu

IMHO the guest can't really detect this, but it'll found that the device is not working functionally if it's doing something like what Jason has mentioned.

Actually now I have had an idea if we really want to live well even with Jason's example: maybe we'll need to identify PSI/DSI. For DSI, we don't remap for mapped pages; for PSI, we unmap and remap the mapped pages. That'll complicate the stuff a bit, but it should satisfy all the people.

Quoted 3 lines

Quoted 2 lines

Quoted 1 line

Thanks,

So it looks like there will be still unnecessary unamps.

Could I ask what do you mean by "unecessary unmaps"?

It's for "for PSI, we unmap and remap the mapped pages". So for the first "unmap" how do you know it was really necessary without knowing the state of current shadow page table?

Quoted 7 lines

Quoted 2 lines

How about record the mappings in the tree too?

As I mentioned, for L1 guest (e.g., DPDK applications running in L1) it'll be fine. But I'm just afraid we will have other use cases, like the L2 guests. That might need tons of the mapping entries in the worst case scenario.

Yes, but that's the price of shadow page tables.

Quoted 14 lines · Jason Wang

Quoted 12 lines · Peter Xu

Quoted 11 lines · Jason Wang

Quoted 10 lines · Peter Xu

IMHO the guest can't really detect this, but it'll found that the device is not working functionally if it's doing something like what Jason has mentioned.

Actually now I have had an idea if we really want to live well even with Jason's example: maybe we'll need to identify PSI/DSI. For DSI, we don't remap for mapped pages; for PSI, we unmap and remap the mapped pages. That'll complicate the stuff a bit, but it should satisfy all the people.

Quoted 6 lines

Quoted 3 lines

Quoted 2 lines

Quoted 1 line

Thanks,

So it looks like there will be still unnecessary unamps.

Could I ask what do you mean by "unecessary unmaps"?

It's for "for PSI, we unmap and remap the mapped pages". So for the first "unmap" how do you know it was really necessary without knowing the state of current shadow page table?

I don't. Could I just unmap it anyway? Say, now the guest _modified_ the PTE already. Yes I think it's following the spec, but it is really _unsafe_. We can know that from what it has done already. Then I really think a unmap+map would be good enough for us... After all that behavior can cause DMA error even on real hardwares. It can never tell.

Quoted 8 lines

Quoted 7 lines

Quoted 2 lines

How about record the mappings in the tree too?

As I mentioned, for L1 guest (e.g., DPDK applications running in L1) it'll be fine. But I'm just afraid we will have other use cases, like the L2 guests. That might need tons of the mapping entries in the worst case scenario.

Yes, but that's the price of shadow page tables.

So that's why I would like to propose this mergable interval tree. It might greatly reduce the price if we can reach a consensus on how we should treat those strange-behaved guest OSs. Thanks,

Quoted 21 lines · Peter Xu

Quoted 14 lines · Jason Wang

Quoted 12 lines · Peter Xu

Quoted 11 lines · Jason Wang

Quoted 10 lines · Peter Xu

IMHO the guest can't really detect this, but it'll found that the device is not working functionally if it's doing something like what Jason has mentioned.

Actually now I have had an idea if we really want to live well even with Jason's example: maybe we'll need to identify PSI/DSI. For DSI, we don't remap for mapped pages; for PSI, we unmap and remap the mapped pages. That'll complicate the stuff a bit, but it should satisfy all the people.

Quoted 6 lines

Quoted 3 lines

Quoted 2 lines

Quoted 1 line

Thanks,

So it looks like there will be still unnecessary unamps.

Could I ask what do you mean by "unecessary unmaps"?

It's for "for PSI, we unmap and remap the mapped pages". So for the first "unmap" how do you know it was really necessary without knowing the state of current shadow page table?

Quoted 6 lines

I don't. Could I just unmap it anyway? Say, now the guest _modified_ the PTE already. Yes I think it's following the spec, but it is really _unsafe_. We can know that from what it has done already. Then I really think a unmap+map would be good enough for us... After all that behavior can cause DMA error even on real hardwares. It can never tell.

I mean for following case: