[Patch v2 0/3] iommu: reduce spinlock contention on fast path

[Patch v2 0/3] iommu: reduce spinlock contention on fast path

[Cong Wang]

This patchset contains three small optimizations for the global spinlock
contention in IOVA cache. Our memcache perf test shows this reduced its
p999 latency down by 45% on AMD when IOMMU is enabled.

Cong Wang (3):
  iommu: match the original algorithm
  iommu: optimize iova_magazine_free_pfns()
  iommu: avoid taking iova_rbtree_lock twice

---
 drivers/iommu/iova.c | 75 ++++++++++++++++++++++++++------------------
 1 file changed, 45 insertions(+), 30 deletions(-)

-- 
2.21.0

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

[Patch v2 1/3] iommu: match the original algorithm

[Cong Wang]

The IOVA cache algorithm implemented in IOMMU code does not
exactly match the original algorithm described in the paper.

Particularly, it doesn't need to free the loaded empty magazine
when trying to put it back to global depot. To make it work, we
have to pre-allocate magazines in the depot and only recycle them
when all of them are full.

Before this patch, rcache->depot[] contains either full or
freed entries, after this patch, it contains either full or
empty (but allocated) entries.

Cc: Joerg Roedel <joro@8bytes.org>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 drivers/iommu/iova.c | 45 +++++++++++++++++++++++++++-----------------
 1 file changed, 28 insertions(+), 17 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 41c605b0058f..cb473ddce4cf 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -862,12 +862,16 @@ static void init_iova_rcaches(struct iova_domain *iovad)
 	struct iova_cpu_rcache *cpu_rcache;
 	struct iova_rcache *rcache;
 	unsigned int cpu;
-	int i;
+	int i, j;
 
 	for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
 		rcache = &iovad->rcaches[i];
 		spin_lock_init(&rcache->lock);
 		rcache->depot_size = 0;
+		for (j = 0; j < MAX_GLOBAL_MAGS; ++j) {
+			rcache->depot[j] = iova_magazine_alloc(GFP_KERNEL);
+			WARN_ON(!rcache->depot[j]);
+		}
 		rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
 		if (WARN_ON(!rcache->cpu_rcaches))
 			continue;
@@ -900,24 +904,30 @@ static bool __iova_rcache_insert(struct iova_domain *iovad,
 
 	if (!iova_magazine_full(cpu_rcache->loaded)) {
 		can_insert = true;
-	} else if (!iova_magazine_full(cpu_rcache->prev)) {
+	} else if (iova_magazine_empty(cpu_rcache->prev)) {
 		swap(cpu_rcache->prev, cpu_rcache->loaded);
 		can_insert = true;
 	} else {
-		struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
+		spin_lock(&rcache->lock);
+		if (rcache->depot_size < MAX_GLOBAL_MAGS) {
+			swap(rcache->depot[rcache->depot_size], cpu_rcache->prev);
+			swap(cpu_rcache->prev, cpu_rcache->loaded);
+			rcache->depot_size++;
+			can_insert = true;
+		} else {
+			mag_to_free = cpu_rcache->loaded;
+		}
+		spin_unlock(&rcache->lock);
+
+		if (mag_to_free) {
+			struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
 
-		if (new_mag) {
-			spin_lock(&rcache->lock);
-			if (rcache->depot_size < MAX_GLOBAL_MAGS) {
-				rcache->depot[rcache->depot_size++] =
-						cpu_rcache->loaded;
+			if (new_mag) {
+				cpu_rcache->loaded = new_mag;
+				can_insert = true;
 			} else {
-				mag_to_free = cpu_rcache->loaded;
+				mag_to_free = NULL;
 			}
-			spin_unlock(&rcache->lock);
-
-			cpu_rcache->loaded = new_mag;
-			can_insert = true;
 		}
 	}
 
@@ -963,14 +973,15 @@ static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
 
 	if (!iova_magazine_empty(cpu_rcache->loaded)) {
 		has_pfn = true;
-	} else if (!iova_magazine_empty(cpu_rcache->prev)) {
+	} else if (iova_magazine_full(cpu_rcache->prev)) {
 		swap(cpu_rcache->prev, cpu_rcache->loaded);
 		has_pfn = true;
 	} else {
 		spin_lock(&rcache->lock);
 		if (rcache->depot_size > 0) {
-			iova_magazine_free(cpu_rcache->loaded);
-			cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
+			swap(rcache->depot[rcache->depot_size - 1], cpu_rcache->prev);
+			swap(cpu_rcache->prev, cpu_rcache->loaded);
+			rcache->depot_size--;
 			has_pfn = true;
 		}
 		spin_unlock(&rcache->lock);
@@ -1019,7 +1030,7 @@ static void free_iova_rcaches(struct iova_domain *iovad)
 			iova_magazine_free(cpu_rcache->prev);
 		}
 		free_percpu(rcache->cpu_rcaches);
-		for (j = 0; j < rcache->depot_size; ++j)
+		for (j = 0; j < MAX_GLOBAL_MAGS; ++j)
 			iova_magazine_free(rcache->depot[j]);
 	}
 }
-- 
2.21.0

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 1/3] iommu: match the original algorithm

[John Garry]

On 29/11/2019 00:48, Cong Wang wrote:
> The IOVA cache algorithm implemented in IOMMU code does not
> exactly match the original algorithm described in the paper.
> 

which paper?

> Particularly, it doesn't need to free the loaded empty magazine
> when trying to put it back to global depot. To make it work, we
> have to pre-allocate magazines in the depot and only recycle them
> when all of them are full.
> 
> Before this patch, rcache->depot[] contains either full or
> freed entries, after this patch, it contains either full or
> empty (but allocated) entries.

I *quickly* tested this patch and got a small performance gain.

> 
> Cc: Joerg Roedel <joro@8bytes.org>
> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
> ---
>   drivers/iommu/iova.c | 45 +++++++++++++++++++++++++++-----------------
>   1 file changed, 28 insertions(+), 17 deletions(-)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index 41c605b0058f..cb473ddce4cf 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -862,12 +862,16 @@ static void init_iova_rcaches(struct iova_domain *iovad)
>   	struct iova_cpu_rcache *cpu_rcache;
>   	struct iova_rcache *rcache;
>   	unsigned int cpu;
> -	int i;
> +	int i, j;
>   
>   	for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
>   		rcache = &iovad->rcaches[i];
>   		spin_lock_init(&rcache->lock);
>   		rcache->depot_size = 0;
> +		for (j = 0; j < MAX_GLOBAL_MAGS; ++j) {
> +			rcache->depot[j] = iova_magazine_alloc(GFP_KERNEL);
> +			WARN_ON(!rcache->depot[j]);
> +		}
>   		rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
>   		if (WARN_ON(!rcache->cpu_rcaches))
>   			continue;
> @@ -900,24 +904,30 @@ static bool __iova_rcache_insert(struct iova_domain *iovad,
>   
>   	if (!iova_magazine_full(cpu_rcache->loaded)) {
>   		can_insert = true;
> -	} else if (!iova_magazine_full(cpu_rcache->prev)) {
> +	} else if (iova_magazine_empty(cpu_rcache->prev)) {

is this change strictly necessary?

>   		swap(cpu_rcache->prev, cpu_rcache->loaded);
>   		can_insert = true;
>   	} else {
> -		struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
> +		spin_lock(&rcache->lock);
> +		if (rcache->depot_size < MAX_GLOBAL_MAGS) {
> +			swap(rcache->depot[rcache->depot_size], cpu_rcache->prev);
> +			swap(cpu_rcache->prev, cpu_rcache->loaded);
> +			rcache->depot_size++;
> +			can_insert = true;
> +		} else {
> +			mag_to_free = cpu_rcache->loaded;
> +		}
> +		spin_unlock(&rcache->lock);
> +
> +		if (mag_to_free) {
> +			struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
>   
> -		if (new_mag) {
> -			spin_lock(&rcache->lock);
> -			if (rcache->depot_size < MAX_GLOBAL_MAGS) {
> -				rcache->depot[rcache->depot_size++] =
> -						cpu_rcache->loaded;
> +			if (new_mag) {
> +				cpu_rcache->loaded = new_mag;
> +				can_insert = true;
>   			} else {
> -				mag_to_free = cpu_rcache->loaded;
> +				mag_to_free = NULL;
>   			}
> -			spin_unlock(&rcache->lock);
> -
> -			cpu_rcache->loaded = new_mag;
> -			can_insert = true;
>   		}
>   	}
>   
> @@ -963,14 +973,15 @@ static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
>   
>   	if (!iova_magazine_empty(cpu_rcache->loaded)) {
>   		has_pfn = true;
> -	} else if (!iova_magazine_empty(cpu_rcache->prev)) {
> +	} else if (iova_magazine_full(cpu_rcache->prev)) {
>   		swap(cpu_rcache->prev, cpu_rcache->loaded);
>   		has_pfn = true;
>   	} else {
>   		spin_lock(&rcache->lock);
>   		if (rcache->depot_size > 0) {
> -			iova_magazine_free(cpu_rcache->loaded);

it is good to remove this from under the lock, apart from this change

> -			cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
> +			swap(rcache->depot[rcache->depot_size - 1], cpu_rcache->prev);
> +			swap(cpu_rcache->prev, cpu_rcache->loaded);
> +			rcache->depot_size--;

I'm not sure how appropriate the name "depot_size" is any longer.

>   			has_pfn = true;
>   		}
>   		spin_unlock(&rcache->lock);
> @@ -1019,7 +1030,7 @@ static void free_iova_rcaches(struct iova_domain *iovad)
>   			iova_magazine_free(cpu_rcache->prev);
>   		}
>   		free_percpu(rcache->cpu_rcaches);
> -		for (j = 0; j < rcache->depot_size; ++j)
> +		for (j = 0; j < MAX_GLOBAL_MAGS; ++j)
>   			iova_magazine_free(rcache->depot[j]);
>   	}
>   }
> 

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 1/3] iommu: match the original algorithm

[Cong Wang]

On Fri, Nov 29, 2019 at 6:43 AM John Garry <john.garry@huawei.com> wrote:
>
> On 29/11/2019 00:48, Cong Wang wrote:
> > The IOVA cache algorithm implemented in IOMMU code does not
> > exactly match the original algorithm described in the paper.
> >
>
> which paper?

It's in drivers/iommu/iova.c, from line 769:

 769 /*
 770  * Magazine caches for IOVA ranges.  For an introduction to magazines,
 771  * see the USENIX 2001 paper "Magazines and Vmem: Extending the Slab
 772  * Allocator to Many CPUs and Arbitrary Resources" by Bonwick and Adams.
 773  * For simplicity, we use a static magazine size and don't implement the
 774  * dynamic size tuning described in the paper.
 775  */


>
> > Particularly, it doesn't need to free the loaded empty magazine
> > when trying to put it back to global depot. To make it work, we
> > have to pre-allocate magazines in the depot and only recycle them
> > when all of them are full.
> >
> > Before this patch, rcache->depot[] contains either full or
> > freed entries, after this patch, it contains either full or
> > empty (but allocated) entries.
>
> I *quickly* tested this patch and got a small performance gain.

Thanks for testing! It requires a different workload to see bigger gain,
in our case, 24 memcache.parallel servers with 120 clients.


>
> >
> > Cc: Joerg Roedel <joro@8bytes.org>
> > Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
> > ---
> >   drivers/iommu/iova.c | 45 +++++++++++++++++++++++++++-----------------
> >   1 file changed, 28 insertions(+), 17 deletions(-)
> >
> > diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> > index 41c605b0058f..cb473ddce4cf 100644
> > --- a/drivers/iommu/iova.c
> > +++ b/drivers/iommu/iova.c
> > @@ -862,12 +862,16 @@ static void init_iova_rcaches(struct iova_domain *iovad)
> >       struct iova_cpu_rcache *cpu_rcache;
> >       struct iova_rcache *rcache;
> >       unsigned int cpu;
> > -     int i;
> > +     int i, j;
> >
> >       for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
> >               rcache = &iovad->rcaches[i];
> >               spin_lock_init(&rcache->lock);
> >               rcache->depot_size = 0;
> > +             for (j = 0; j < MAX_GLOBAL_MAGS; ++j) {
> > +                     rcache->depot[j] = iova_magazine_alloc(GFP_KERNEL);
> > +                     WARN_ON(!rcache->depot[j]);
> > +             }
> >               rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
> >               if (WARN_ON(!rcache->cpu_rcaches))
> >                       continue;
> > @@ -900,24 +904,30 @@ static bool __iova_rcache_insert(struct iova_domain *iovad,
> >
> >       if (!iova_magazine_full(cpu_rcache->loaded)) {
> >               can_insert = true;
> > -     } else if (!iova_magazine_full(cpu_rcache->prev)) {
> > +     } else if (iova_magazine_empty(cpu_rcache->prev)) {
>
> is this change strictly necessary?

Yes, because it is what described in the paper. But it should be
functionally same because cpu_rcache->prev is either full or empty.



>
> >               swap(cpu_rcache->prev, cpu_rcache->loaded);
> >               can_insert = true;
> >       } else {
> > -             struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
> > +             spin_lock(&rcache->lock);
> > +             if (rcache->depot_size < MAX_GLOBAL_MAGS) {
> > +                     swap(rcache->depot[rcache->depot_size], cpu_rcache->prev);
> > +                     swap(cpu_rcache->prev, cpu_rcache->loaded);
> > +                     rcache->depot_size++;
> > +                     can_insert = true;
> > +             } else {
> > +                     mag_to_free = cpu_rcache->loaded;
> > +             }
> > +             spin_unlock(&rcache->lock);
> > +
> > +             if (mag_to_free) {
> > +                     struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
> >
> > -             if (new_mag) {
> > -                     spin_lock(&rcache->lock);
> > -                     if (rcache->depot_size < MAX_GLOBAL_MAGS) {
> > -                             rcache->depot[rcache->depot_size++] =
> > -                                             cpu_rcache->loaded;
> > +                     if (new_mag) {
> > +                             cpu_rcache->loaded = new_mag;
> > +                             can_insert = true;
> >                       } else {
> > -                             mag_to_free = cpu_rcache->loaded;
> > +                             mag_to_free = NULL;
> >                       }
> > -                     spin_unlock(&rcache->lock);
> > -
> > -                     cpu_rcache->loaded = new_mag;
> > -                     can_insert = true;
> >               }
> >       }
> >
> > @@ -963,14 +973,15 @@ static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
> >
> >       if (!iova_magazine_empty(cpu_rcache->loaded)) {
> >               has_pfn = true;
> > -     } else if (!iova_magazine_empty(cpu_rcache->prev)) {
> > +     } else if (iova_magazine_full(cpu_rcache->prev)) {
> >               swap(cpu_rcache->prev, cpu_rcache->loaded);
> >               has_pfn = true;
> >       } else {
> >               spin_lock(&rcache->lock);
> >               if (rcache->depot_size > 0) {
> > -                     iova_magazine_free(cpu_rcache->loaded);
>
> it is good to remove this from under the lock, apart from this change
>
> > -                     cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
> > +                     swap(rcache->depot[rcache->depot_size - 1], cpu_rcache->prev);
> > +                     swap(cpu_rcache->prev, cpu_rcache->loaded);
> > +                     rcache->depot_size--;
>
> I'm not sure how appropriate the name "depot_size" is any longer.

I think it is still okay, because empty ones don't count. However if you
have better names, I am open to your suggestion.

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 1/3] iommu: match the original algorithm

[John Garry]

On 30/11/2019 05:58, Cong Wang wrote:
> On Fri, Nov 29, 2019 at 6:43 AM John Garry <john.garry@huawei.com> wrote:
>>
>> On 29/11/2019 00:48, Cong Wang wrote:
>>> The IOVA cache algorithm implemented in IOMMU code does not
>>> exactly match the original algorithm described in the paper.
>>>
>>
>> which paper?
> 
> It's in drivers/iommu/iova.c, from line 769:
> 
>   769 /*
>   770  * Magazine caches for IOVA ranges.  For an introduction to magazines,
>   771  * see the USENIX 2001 paper "Magazines and Vmem: Extending the Slab
>   772  * Allocator to Many CPUs and Arbitrary Resources" by Bonwick and Adams.
>   773  * For simplicity, we use a static magazine size and don't implement the
>   774  * dynamic size tuning described in the paper.
>   775  */
> 
> 
>>
>>> Particularly, it doesn't need to free the loaded empty magazine
>>> when trying to put it back to global depot. To make it work, we
>>> have to pre-allocate magazines in the depot and only recycle them
>>> when all of them are full.
>>>
>>> Before this patch, rcache->depot[] contains either full or
>>> freed entries, after this patch, it contains either full or
>>> empty (but allocated) entries.
>>
>> I *quickly* tested this patch and got a small performance gain.
> 
> Thanks for testing! It requires a different workload to see bigger gain,
> in our case, 24 memcache.parallel servers with 120 clients.
> 

So in fact I was getting a ~10% throughput boost for my storage test. 
Seems more than I would expect/hope for. I would need to test more.

> 
>>
>>>
>>> Cc: Joerg Roedel <joro@8bytes.org>
>>> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
>>> ---
>>>    drivers/iommu/iova.c | 45 +++++++++++++++++++++++++++-----------------
>>>    1 file changed, 28 insertions(+), 17 deletions(-)
>>>
>>> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
>>> index 41c605b0058f..cb473ddce4cf 100644
>>> --- a/drivers/iommu/iova.c
>>> +++ b/drivers/iommu/iova.c
>>> @@ -862,12 +862,16 @@ static void init_iova_rcaches(struct iova_domain *iovad)
>>>        struct iova_cpu_rcache *cpu_rcache;
>>>        struct iova_rcache *rcache;
>>>        unsigned int cpu;
>>> -     int i;
>>> +     int i, j;
>>>
>>>        for (i = 0; i < IOVA_RANGE_CACHE_MAX_SIZE; ++i) {
>>>                rcache = &iovad->rcaches[i];
>>>                spin_lock_init(&rcache->lock);
>>>                rcache->depot_size = 0;
>>> +             for (j = 0; j < MAX_GLOBAL_MAGS; ++j) {
>>> +                     rcache->depot[j] = iova_magazine_alloc(GFP_KERNEL);
>>> +                     WARN_ON(!rcache->depot[j]);
>>> +             }
>>>                rcache->cpu_rcaches = __alloc_percpu(sizeof(*cpu_rcache), cache_line_size());
>>>                if (WARN_ON(!rcache->cpu_rcaches))
>>>                        continue;
>>> @@ -900,24 +904,30 @@ static bool __iova_rcache_insert(struct iova_domain *iovad,
>>>
>>>        if (!iova_magazine_full(cpu_rcache->loaded)) {
>>>                can_insert = true;
>>> -     } else if (!iova_magazine_full(cpu_rcache->prev)) {
>>> +     } else if (iova_magazine_empty(cpu_rcache->prev)) {
>>
>> is this change strictly necessary?
> 
> Yes, because it is what described in the paper. But it should be
> functionally same because cpu_rcache->prev is either full or empty.

That is was what I was getting at.

> 
> 
> 
>>
>>>                swap(cpu_rcache->prev, cpu_rcache->loaded);
>>>                can_insert = true;
>>>        } else {
>>> -             struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);

Apart from this change, did anyone ever consider kmem cache for the 
magazines?

>>> +             spin_lock(&rcache->lock);
>>> +             if (rcache->depot_size < MAX_GLOBAL_MAGS) {
>>> +                     swap(rcache->depot[rcache->depot_size], cpu_rcache->prev);
>>> +                     swap(cpu_rcache->prev, cpu_rcache->loaded);
>>> +                     rcache->depot_size++;
>>> +                     can_insert = true;
>>> +             } else {
>>> +                     mag_to_free = cpu_rcache->loaded;
>>> +             }
>>> +             spin_unlock(&rcache->lock);
>>> +
>>> +             if (mag_to_free) {
>>> +                     struct iova_magazine *new_mag = iova_magazine_alloc(GFP_ATOMIC);
>>>
>>> -             if (new_mag) {
>>> -                     spin_lock(&rcache->lock);
>>> -                     if (rcache->depot_size < MAX_GLOBAL_MAGS) {
>>> -                             rcache->depot[rcache->depot_size++] =
>>> -                                             cpu_rcache->loaded;
>>> +                     if (new_mag) {
>>> +                             cpu_rcache->loaded = new_mag;
>>> +                             can_insert = true;
>>>                        } else {
>>> -                             mag_to_free = cpu_rcache->loaded;
>>> +                             mag_to_free = NULL;
>>>                        }
>>> -                     spin_unlock(&rcache->lock);
>>> -
>>> -                     cpu_rcache->loaded = new_mag;
>>> -                     can_insert = true;
>>>                }
>>>        }
>>>
>>> @@ -963,14 +973,15 @@ static unsigned long __iova_rcache_get(struct iova_rcache *rcache,
>>>
>>>        if (!iova_magazine_empty(cpu_rcache->loaded)) {
>>>                has_pfn = true;
>>> -     } else if (!iova_magazine_empty(cpu_rcache->prev)) {
>>> +     } else if (iova_magazine_full(cpu_rcache->prev)) {
>>>                swap(cpu_rcache->prev, cpu_rcache->loaded);
>>>                has_pfn = true;
>>>        } else {
>>>                spin_lock(&rcache->lock);
>>>                if (rcache->depot_size > 0) {
>>> -                     iova_magazine_free(cpu_rcache->loaded);
>>
>> it is good to remove this from under the lock, apart from this change
>>
>>> -                     cpu_rcache->loaded = rcache->depot[--rcache->depot_size];
>>> +                     swap(rcache->depot[rcache->depot_size - 1], cpu_rcache->prev);
>>> +                     swap(cpu_rcache->prev, cpu_rcache->loaded);

I wonder if not using swap() at all is neater here.

>>> +                     rcache->depot_size--;
>>
>> I'm not sure how appropriate the name "depot_size" is any longer.
> 
> I think it is still okay, because empty ones don't count. However if you
> have better names, I am open to your suggestion.

Yeah, probably.

thanks,
John

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 1/3] iommu: match the original algorithm

[Cong Wang]

On Mon, Dec 2, 2019 at 2:55 AM John Garry <john.garry@huawei.com> wrote:
> Apart from this change, did anyone ever consider kmem cache for the
> magazines?

You can always make any changes you want after this patch,
I can't do all optimizations in one single patch. :)

So, I will leave this to you.

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 1/3] iommu: match the original algorithm

[Christoph Hellwig]

I think a subject line better describes what you change, no that
it matches an original algorithm.  The fact that the fix matches
the original algorithm can go somewhere towards the commit log,
preferably with a reference to the actual paper.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 1/3] iommu: match the original algorithm

[Cong Wang]

On Mon, Dec 2, 2019 at 8:58 AM Christoph Hellwig <hch@infradead.org> wrote:
>
> I think a subject line better describes what you change, no that
> it matches an original algorithm.  The fact that the fix matches
> the original algorithm can go somewhere towards the commit log,
> preferably with a reference to the actual paper.

Ok, I will change subject to "iommu: avoid unnecessary magazine allocations".

And I will put the title of the paper in the commit log even though
it is already in the code comment.

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

[Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[Cong Wang]

If the maganize is empty, iova_magazine_free_pfns() should
be a nop, however it misses the case of mag->size==0. So we
should just call iova_magazine_empty().

This should reduce the contention on iovad->iova_rbtree_lock
a little bit.

Cc: Joerg Roedel <joro@8bytes.org>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 drivers/iommu/iova.c | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index cb473ddce4cf..184d4c0e20b5 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -797,13 +797,23 @@ static void iova_magazine_free(struct iova_magazine *mag)
 	kfree(mag);
 }
 
+static bool iova_magazine_full(struct iova_magazine *mag)
+{
+	return (mag && mag->size == IOVA_MAG_SIZE);
+}
+
+static bool iova_magazine_empty(struct iova_magazine *mag)
+{
+	return (!mag || mag->size == 0);
+}
+
 static void
 iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 {
 	unsigned long flags;
 	int i;
 
-	if (!mag)
+	if (iova_magazine_empty(mag))
 		return;
 
 	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
@@ -820,16 +830,6 @@ iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
 	mag->size = 0;
 }
 
-static bool iova_magazine_full(struct iova_magazine *mag)
-{
-	return (mag && mag->size == IOVA_MAG_SIZE);
-}
-
-static bool iova_magazine_empty(struct iova_magazine *mag)
-{
-	return (!mag || mag->size == 0);
-}
-
 static unsigned long iova_magazine_pop(struct iova_magazine *mag,
 				       unsigned long limit_pfn)
 {
-- 
2.21.0

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[John Garry]

On 29/11/2019 00:48, Cong Wang wrote:
> If the maganize is empty, iova_magazine_free_pfns() should

magazine

> be a nop, however it misses the case of mag->size==0. So we
> should just call iova_magazine_empty().
> 
> This should reduce the contention on iovad->iova_rbtree_lock
> a little bit.
> 
> Cc: Joerg Roedel <joro@8bytes.org>
> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
> ---
>   drivers/iommu/iova.c | 22 +++++++++++-----------
>   1 file changed, 11 insertions(+), 11 deletions(-)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index cb473ddce4cf..184d4c0e20b5 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -797,13 +797,23 @@ static void iova_magazine_free(struct iova_magazine *mag)
>   	kfree(mag);
>   }
>   
> +static bool iova_magazine_full(struct iova_magazine *mag)
> +{
> +	return (mag && mag->size == IOVA_MAG_SIZE);
> +}
> +
> +static bool iova_magazine_empty(struct iova_magazine *mag)
> +{
> +	return (!mag || mag->size == 0);
> +}
> +
>   static void
>   iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
>   {
>   	unsigned long flags;
>   	int i;
>   
> -	if (!mag)
> +	if (iova_magazine_empty(mag))

The only hot path we this call is 
__iova_rcache_insert()->iova_magazine_free_pfns(mag_to_free) and 
mag_to_free is full in this case, so I am sure how the additional check 
helps, right?

Thanks,
John

>   		return;
>   
>   	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
> @@ -820,16 +830,6 @@ iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
>   	mag->size = 0;
>   }
>   
> -static bool iova_magazine_full(struct iova_magazine *mag)
> -{
> -	return (mag && mag->size == IOVA_MAG_SIZE);
> -}
> -
> -static bool iova_magazine_empty(struct iova_magazine *mag)
> -{
> -	return (!mag || mag->size == 0);
> -}
> -
>   static unsigned long iova_magazine_pop(struct iova_magazine *mag,
>   				       unsigned long limit_pfn)
>   {
> 

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[Cong Wang]

On Fri, Nov 29, 2019 at 5:24 AM John Garry <john.garry@huawei.com> wrote:
>
> On 29/11/2019 00:48, Cong Wang wrote:
> > If the maganize is empty, iova_magazine_free_pfns() should
>
> magazine

Good catch!

>
> > be a nop, however it misses the case of mag->size==0. So we
> > should just call iova_magazine_empty().
> >
> > This should reduce the contention on iovad->iova_rbtree_lock
> > a little bit.
> >
> > Cc: Joerg Roedel <joro@8bytes.org>
> > Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
> > ---
> >   drivers/iommu/iova.c | 22 +++++++++++-----------
> >   1 file changed, 11 insertions(+), 11 deletions(-)
> >
> > diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> > index cb473ddce4cf..184d4c0e20b5 100644
> > --- a/drivers/iommu/iova.c
> > +++ b/drivers/iommu/iova.c
> > @@ -797,13 +797,23 @@ static void iova_magazine_free(struct iova_magazine *mag)
> >       kfree(mag);
> >   }
> >
> > +static bool iova_magazine_full(struct iova_magazine *mag)
> > +{
> > +     return (mag && mag->size == IOVA_MAG_SIZE);
> > +}
> > +
> > +static bool iova_magazine_empty(struct iova_magazine *mag)
> > +{
> > +     return (!mag || mag->size == 0);
> > +}
> > +
> >   static void
> >   iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
> >   {
> >       unsigned long flags;
> >       int i;
> >
> > -     if (!mag)
> > +     if (iova_magazine_empty(mag))
>
> The only hot path we this call is
> __iova_rcache_insert()->iova_magazine_free_pfns(mag_to_free) and
> mag_to_free is full in this case, so I am sure how the additional check
> helps, right?

This is what I mean by "a little bit" in changelog, did you miss it or
misunderstand it? :)

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[John Garry]

On 30/11/2019 06:02, Cong Wang wrote:
> On Fri, Nov 29, 2019 at 5:24 AM John Garry <john.garry@huawei.com> wrote:
>>
>> On 29/11/2019 00:48, Cong Wang wrote:
>>> If the maganize is empty, iova_magazine_free_pfns() should
>>
>> magazine
> 
> Good catch!
> 
>>
>>> be a nop, however it misses the case of mag->size==0. So we
>>> should just call iova_magazine_empty().
>>>
>>> This should reduce the contention on iovad->iova_rbtree_lock
>>> a little bit.
>>>
>>> Cc: Joerg Roedel <joro@8bytes.org>
>>> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
>>> ---
>>>    drivers/iommu/iova.c | 22 +++++++++++-----------
>>>    1 file changed, 11 insertions(+), 11 deletions(-)
>>>
>>> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
>>> index cb473ddce4cf..184d4c0e20b5 100644
>>> --- a/drivers/iommu/iova.c
>>> +++ b/drivers/iommu/iova.c
>>> @@ -797,13 +797,23 @@ static void iova_magazine_free(struct iova_magazine *mag)
>>>        kfree(mag);
>>>    }
>>>
>>> +static bool iova_magazine_full(struct iova_magazine *mag)
>>> +{
>>> +     return (mag && mag->size == IOVA_MAG_SIZE);
>>> +}
>>> +
>>> +static bool iova_magazine_empty(struct iova_magazine *mag)
>>> +{
>>> +     return (!mag || mag->size == 0);
>>> +}
>>> +
>>>    static void
>>>    iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
>>>    {
>>>        unsigned long flags;
>>>        int i;
>>>
>>> -     if (!mag)
>>> +     if (iova_magazine_empty(mag))
>>
>> The only hot path we this call is
>> __iova_rcache_insert()->iova_magazine_free_pfns(mag_to_free) and
>> mag_to_free is full in this case, so I am sure how the additional check
>> helps, right?
> 
> This is what I mean by "a little bit" in changelog, did you miss it or
> misunderstand it? :)

I was concerned that in the fastpath we actually make things very 
marginally slower by adding a check which will fail.

Thanks,
John

> 
> Thanks.
> .
> 

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[Cong Wang]

On Mon, Dec 2, 2019 at 2:02 AM John Garry <john.garry@huawei.com> wrote:
>
> On 30/11/2019 06:02, Cong Wang wrote:
> > On Fri, Nov 29, 2019 at 5:24 AM John Garry <john.garry@huawei.com> wrote:
> >>
> >> On 29/11/2019 00:48, Cong Wang wrote:
> >>> If the maganize is empty, iova_magazine_free_pfns() should
> >>
> >> magazine
> >
> > Good catch!
> >
> >>
> >>> be a nop, however it misses the case of mag->size==0. So we
> >>> should just call iova_magazine_empty().
> >>>
> >>> This should reduce the contention on iovad->iova_rbtree_lock
> >>> a little bit.
> >>>
> >>> Cc: Joerg Roedel <joro@8bytes.org>
> >>> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
> >>> ---
> >>>    drivers/iommu/iova.c | 22 +++++++++++-----------
> >>>    1 file changed, 11 insertions(+), 11 deletions(-)
> >>>
> >>> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> >>> index cb473ddce4cf..184d4c0e20b5 100644
> >>> --- a/drivers/iommu/iova.c
> >>> +++ b/drivers/iommu/iova.c
> >>> @@ -797,13 +797,23 @@ static void iova_magazine_free(struct iova_magazine *mag)
> >>>        kfree(mag);
> >>>    }
> >>>
> >>> +static bool iova_magazine_full(struct iova_magazine *mag)
> >>> +{
> >>> +     return (mag && mag->size == IOVA_MAG_SIZE);
> >>> +}
> >>> +
> >>> +static bool iova_magazine_empty(struct iova_magazine *mag)
> >>> +{
> >>> +     return (!mag || mag->size == 0);
> >>> +}
> >>> +
> >>>    static void
> >>>    iova_magazine_free_pfns(struct iova_magazine *mag, struct iova_domain *iovad)
> >>>    {
> >>>        unsigned long flags;
> >>>        int i;
> >>>
> >>> -     if (!mag)
> >>> +     if (iova_magazine_empty(mag))
> >>
> >> The only hot path we this call is
> >> __iova_rcache_insert()->iova_magazine_free_pfns(mag_to_free) and
> >> mag_to_free is full in this case, so I am sure how the additional check
> >> helps, right?
> >
> > This is what I mean by "a little bit" in changelog, did you miss it or
> > misunderstand it? :)
>
> I was concerned that in the fastpath we actually make things very
> marginally slower by adding a check which will fail.

The check is done without any locking, so it is cheap. And it is a
common pattern that we do a check without lock and do a second same
check with lock:

https://en.wikipedia.org/wiki/Double-checked_locking

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[Christoph Hellwig]

> +	return (mag && mag->size == IOVA_MAG_SIZE);

> +	return (!mag || mag->size == 0);

No need for the braces in both cases.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 2/3] iommu: optimize iova_magazine_free_pfns()

[Cong Wang]

On Mon, Dec 2, 2019 at 8:59 AM Christoph Hellwig <hch@infradead.org> wrote:
>
> > +     return (mag && mag->size == IOVA_MAG_SIZE);
>
> > +     return (!mag || mag->size == 0);
>
> No need for the braces in both cases.

The current code is already this, I don't want to mix coding style
changes with a non-coding-style change. You can always remove
them in a separated patch if you feel necessary.

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

[Patch v2 3/3] iommu: avoid taking iova_rbtree_lock twice

[Cong Wang]

Both find_iova() and __free_iova() take iova_rbtree_lock,
there is no reason to take and release it twice inside
free_iova().

Fold them into the critical section by calling the unlock
versions instead.

Cc: Joerg Roedel <joro@8bytes.org>
Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
---
 drivers/iommu/iova.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
index 184d4c0e20b5..f46f8f794678 100644
--- a/drivers/iommu/iova.c
+++ b/drivers/iommu/iova.c
@@ -390,10 +390,14 @@ EXPORT_SYMBOL_GPL(__free_iova);
 void
 free_iova(struct iova_domain *iovad, unsigned long pfn)
 {
-	struct iova *iova = find_iova(iovad, pfn);
+	unsigned long flags;
+	struct iova *iova;
 
+	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
+	iova = private_find_iova(iovad, pfn);
 	if (iova)
-		__free_iova(iovad, iova);
+		private_free_iova(iovad, iova);
+	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
 
 }
 EXPORT_SYMBOL_GPL(free_iova);
-- 
2.21.0

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 3/3] iommu: avoid taking iova_rbtree_lock twice

[John Garry]

On 29/11/2019 00:48, Cong Wang wrote:
> Both find_iova() and __free_iova() take iova_rbtree_lock,
> there is no reason to take and release it twice inside
> free_iova().
> 
> Fold them into the critical section by calling the unlock
> versions instead.

Since generally the iova would be non-NULL, this seems a reasonable 
change (which could be mentioned in the commit log)

John

> 
> Cc: Joerg Roedel <joro@8bytes.org>
> Signed-off-by: Cong Wang <xiyou.wangcong@gmail.com>
> ---
>   drivers/iommu/iova.c | 8 ++++++--
>   1 file changed, 6 insertions(+), 2 deletions(-)
> 
> diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c
> index 184d4c0e20b5..f46f8f794678 100644
> --- a/drivers/iommu/iova.c
> +++ b/drivers/iommu/iova.c
> @@ -390,10 +390,14 @@ EXPORT_SYMBOL_GPL(__free_iova);
>   void
>   free_iova(struct iova_domain *iovad, unsigned long pfn)
>   {
> -	struct iova *iova = find_iova(iovad, pfn);
> +	unsigned long flags;
> +	struct iova *iova;
>   
> +	spin_lock_irqsave(&iovad->iova_rbtree_lock, flags);
> +	iova = private_find_iova(iovad, pfn);
>   	if (iova)
> -		__free_iova(iovad, iova);
> +		private_free_iova(iovad, iova);
> +	spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags);
>   
>   }
>   EXPORT_SYMBOL_GPL(free_iova);
> 

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 3/3] iommu: avoid taking iova_rbtree_lock twice

[Cong Wang]

On Fri, Nov 29, 2019 at 5:34 AM John Garry <john.garry@huawei.com> wrote:
>
> On 29/11/2019 00:48, Cong Wang wrote:
> > Both find_iova() and __free_iova() take iova_rbtree_lock,
> > there is no reason to take and release it twice inside
> > free_iova().
> >
> > Fold them into the critical section by calling the unlock
> > versions instead.
>
> Since generally the iova would be non-NULL, this seems a reasonable
> change (which could be mentioned in the commit log)

I think it is too obvious to mention it. There are many things we can
mention but we should only mention what's necessary, right?

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 0/3] iommu: reduce spinlock contention on fast path

[Joerg Roedel]

On Thu, Nov 28, 2019 at 04:48:52PM -0800, Cong Wang wrote:
> This patchset contains three small optimizations for the global spinlock
> contention in IOVA cache. Our memcache perf test shows this reduced its
> p999 latency down by 45% on AMD when IOMMU is enabled.

Sounds nice. Can you please re-send with Robin Murphy on Cc? Robin, can
you have a look at these IOVA changes please?

Thanks,

	Joerg

_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu

Re: [Patch v2 0/3] iommu: reduce spinlock contention on fast path

[Cong Wang]

On Tue, Dec 17, 2019 at 1:43 AM Joerg Roedel <joro@8bytes.org> wrote:
>
> On Thu, Nov 28, 2019 at 04:48:52PM -0800, Cong Wang wrote:
> > This patchset contains three small optimizations for the global spinlock
> > contention in IOVA cache. Our memcache perf test shows this reduced its
> > p999 latency down by 45% on AMD when IOMMU is enabled.
>
> Sounds nice. Can you please re-send with Robin Murphy on Cc? Robin, can
> you have a look at these IOVA changes please?

I will resend V3 with Robin Cc'ed.

Thanks.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu