Skip to contentSkip to conversation

gnttab: refactor locking for better scalability

RFC PATCH In review Matt Wilson 8 participants 21 messages Nov 12, 2013 – Jun 20, 2014

lore
Share & tools
lore
#0 lore raw

cover gnttab: refactor locking for better scalability

From: Matt Wilson <[email protected]>

As discussed in the Xen Developer Summit Storage Performance BoF, there is a lot of room for improvement in grant table locking. Anthony and I have been working on refactoring the locking over the past few weeks. The performance improvement is considerable and I'd like to hear from others if this approach is fundamentally wrong for some reason.

The previous single spinlock per grant table is split into multiple locks. The heavily modified components of the grant table (the maptrack state and the active entries) are now protected by their own spinlocks. The remaining elements of the grant table are read-mostly, so I modified the main grant table lock to be a rwlock to improve concurrency.

On the performance improvement: Without persistent grants, a domU with 24 VBDs plummbed to local HDDs in a streaming 2M write workload achieved 1,400 MB/sec before this change. Performance more than doubles with this patch, reaching 3,000 MB/sec before tuning and 3,600 MB/sec after adjusting event channel vCPU bindings.

I included the previously posted patch to __gnttab_unmap_common() in the series since it makes a bit more sense in this context, and the follow on refactor patch is on top of it.

DISCLAIMER: I ported this patch from a different Xen version earlier today, and I've only compile tested so far. In the original state we've pushed a lot of concurrent I/O through dom0 and haven't seen any stability issues.

Matt Wilson (2):
gnttab: lock the local grant table earlier in __gnttab_unmap_common()
gnttab: refactor locking for better scalability

 docs/misc/grant-tables.txt    |   56 +++++++-
 xen/arch/x86/mm.c             |    4 +-
 xen/common/grant_table.c      |  308 ++++++++++++++++++++++++++---------------
 xen/include/xen/grant_table.h |    9 +-
 4 files changed, 261 insertions(+), 116 deletions(-)
Signature · 1 line
1.7.9.5
#1 lore raw

RFC PATCH 1/2 gnttab: lock the local grant table earlier in __gnttab_unmap_common()

From: Matt Wilson <[email protected]>

Luckily today maptrack_limit never shrinks. But if at some point in the future this were to change, checking maptrack_limit without holding the grant table spinlock would no longer be safe.

---
v1->v2:
* updated summary to use "local" instead of "left"

---
 xen/common/grant_table.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
xen/common/grant_table.c +2 -1
index 21c6a14..ef10ff4 100644
@@ -842,15 +842,16 @@ __gnttab_unmap_common(
 
     op->frame = (unsigned long)(op->dev_bus_addr >> PAGE_SHIFT);
 
+    spin_lock(&lgt->lock);
     if ( unlikely(op->handle >= lgt->maptrack_limit) )
     {
+        spin_unlock(&lgt->lock);
         gdprintk(XENLOG_INFO, "Bad handle (%d).\n", op->handle);
         op->status = GNTST_bad_handle;
         return;
     }
 
     op->map = &maptrack_entry(lgt, op->handle);
-    spin_lock(&lgt->lock);
 
     if ( unlikely(!op->map->flags) )
     {
Signature · 1 line
1.7.9.5
#2 lore raw

RFC PATCH 2/2 gnttab: refactor locking for better scalability

In reply to Matt Wilson

From: Matt Wilson <[email protected]>

This patch refactors grant table locking. It splits the previous single spinlock per grant table into multiple locks. The heavily modified components of the grant table (the maptrack state and the active entries) are now protected by their own spinlocks. The remaining elements of the grant table are read-mostly, so the main grant table lock is modified to be a rwlock to improve concurrency.

Workloads with high grant table operation rates, especially map/unmap operations as used by blkback/blkfront when persistent grants are not supported, show marked improvement with these changes. A domU with 24 VBDs in a streaming 2M write workload achieved 1,400 MB/sec before this change. Performance more than doubles with this patch, reaching 3,000 MB/sec before tuning and 3,600 MB/sec after adjusting event channel vCPU bindings.

---
 docs/misc/grant-tables.txt    |   56 +++++++-
 xen/arch/x86/mm.c             |    4 +-
 xen/common/grant_table.c      |  309 ++++++++++++++++++++++++++---------------
 xen/include/xen/grant_table.h |    9 +-
 4 files changed, 261 insertions(+), 117 deletions(-)
docs/misc/grant-tables.txt +55 -1
index 19db4ec..54bcba5 100644
@@ -63,6 +63,7 @@ is complete.
   act->domid : remote domain being granted rights
   act->frame : machine frame being granted
   act->pin   : used to hold reference counts
+  act->lock  : spinlock used to serialize access to active entry state
 
  Map tracking
  ~~~~~~~~~~~~
@@ -74,7 +75,60 @@ is complete.
  matching map track entry is then removed, as if unmap had been invoked.
  These are not used by the transfer mechanism.
   map->domid         : owner of the mapped frame
-  map->ref_and_flags : grant reference, ro/rw, mapped for host or device access
+  map->ref           : grant reference
+  map->flags         : ro/rw, mapped for host or device access
+
+********************************************************************************
+ Locking
+ ~~~~~~~
+ Xen uses several locks to serialize access to the internal grant table state.
+
+  grant_table->lock          : rwlock used to prevent readers from accessing
+                               inconsistent grant table state such as current
+                               version, partially initialized active table pages,
+                               etc.
+  grant_table->maptrack_lock : spinlock used to protect the maptrack state
+  active_grant_entry->lock   : spinlock used to serialize modifications to
+                               active entries
+
+ The primary lock for the grant table is a read/write spinlock. All
+ functions that access members of struct grant_table must acquire a
+ read lock around critical sections. Any modification to the members
+ of struct grant_table (e.g., nr_status_frames, nr_grant_frames,
+ active frames, etc.) must only be made if the write lock is
+ held. These elements are read-mostly, and read critical sections can
+ be large, which makes a rwlock a good choice.
+
+ The maptrack state is protected by its own spinlock. Any access (read
+ or write) of struct grant_table members that have a "maptrack_"
+ prefix must be made while holding the maptrack lock. The maptrack
+ state can be rapidly modified under some workloads, and the critical
+ sections are very small, thus we use a spinlock to protect them.
+
+ Active entries are obtained by calling active_entry_acquire(gt, ref).
+ This function returns a pointer to the active entry after locking its
+ spinlock. The caller must hold the rwlock for the grant table in
+ question before calling active_entry_acquire(). This is because the
+ grant table can be dynamically extended via gnttab_grow_table() while
+ a domain is running and each entry's spinlock must initialized before
+ it is used. Additionally, when the local domain is running
+ paravirtualized under iommu=strict mode, the mapcount() function
+ needs the active entries of the remote domain to be unchanged. Thus
+ the mapcount() function must be called with the remote table write
+ lock held, which prevents modifications to active entries when these
+ rules are observed.
+
+ Once all access to the active entry is complete, release the lock by
+ calling active_entry_release(act).
+
+ Summary of rules for locking:
+  active_entry_acquire() and active_entry_release() can only be
+  called when holding the relevant grant table's lock. I.e.:
+    read_lock(&gt->lock);
+    act = active_entry_acquire(gt, ref);
+    ...
+    active_entry_release(act);
+    read_unlock(&gt->lock);
 
 ********************************************************************************
 
xen/arch/x86/mm.c +2 -2
index 43aaceb..bd7f331 100644
@@ -4537,7 +4537,7 @@ static int xenmem_add_to_physmap_once(
                 mfn = virt_to_mfn(d->shared_info);
             break;
         case XENMAPSPACE_grant_table:
-            spin_lock(&d->grant_table->lock);
+            write_lock(&d->grant_table->lock);
 
             if ( d->grant_table->gt_version == 0 )
                 d->grant_table->gt_version = 1;
@@ -4560,7 +4560,7 @@ static int xenmem_add_to_physmap_once(
                     mfn = virt_to_mfn(d->grant_table->shared_raw[idx]);
             }
 
-            spin_unlock(&d->grant_table->lock);
+            write_unlock(&d->grant_table->lock);
             break;
         case XENMAPSPACE_gmfn_range:
         case XENMAPSPACE_gmfn:
xen/common/grant_table.c +198 -111

806 lines not on this page · raw message

xen/include/xen/grant_table.h +6 -3
index 5941191..bb2828b 100644
@@ -84,8 +84,11 @@ struct grant_table {
     struct grant_mapping **maptrack;
     unsigned int          maptrack_head;
     unsigned int          maptrack_limit;
-    /* Lock protecting updates to active and shared grant tables. */
-    spinlock_t            lock;
+    /* Lock protecting the maptrack page list, head, and limit */
+    spinlock_t            maptrack_lock;
+    /* Lock protecting updates to grant table state (version, active
+       entry list, etc.) */
+    rwlock_t              lock;
     /* The defined versions are 1 and 2.  Set to 0 if we don't know
        what version to use yet. */
     unsigned              gt_version;
@@ -103,7 +106,7 @@ gnttab_release_mappings(
     struct domain *d);
 
 /* Increase the size of a domain's grant table.
- * Caller must hold d's grant table lock.
+ * Caller must hold d's grant table write lock.
  */
 int
 gnttab_grow_table(struct domain *d, unsigned int req_nr_frames);
Signature · 1 line
1.7.9.5
#3 lore raw
Quoted 11 lines · Matt Wilson

+ Locking
+ ~~~~~~~
+ Xen uses several locks to serialize access to the internal grant table state.

docs/misc/grant-tables.txt +4 -0
+
+  grant_table->lock          : rwlock used to prevent readers from accessing
+                               inconsistent grant table state such as current
+                               version, partially initialized active table

pages,

docs/misc/grant-tables.txt +2 -0
+                               etc.
+  grant_table->maptrack_lock : spinlock used to protect the maptrack state

docs/misc/grant-tables.txt is complete. · line 100

Quoted 10 lines
docs/misc/grant-tables.txt +10 -0
+  active_grant_entry->lock   : spinlock used to serialize modifications to
+                               active entries
+
+ The primary lock for the grant table is a read/write spinlock. All
+ functions that access members of struct grant_table must acquire a
+ read lock around critical sections. Any modification to the members
+ of struct grant_table (e.g., nr_status_frames, nr_grant_frames,
+ active frames, etc.) must only be made if the write lock is
+ held. These elements are read-mostly, and read critical sections can
+ be large, which makes a rwlock a good choice.

Is there any concern about writer starvation here? I know our spinlocks aren't 'fair' but our rwlocks are guaranteed to starve out writers if there is a steady continuous stream of readers. Perhaps we should write-bias our rwlock, or at least make that an option. We could get fancier but would probably hurt performance.

Looks like great work however!

-- Keir

#4 lore raw
Quoted 21 lines · Keir Fraser
Quoted 19 lines · Matt Wilson

+ Locking
+ ~~~~~~~
+ Xen uses several locks to serialize access to the internal grant table state.

docs/misc/grant-tables.txt +4 -0
+
+  grant_table->lock          : rwlock used to prevent readers from accessing
+                               inconsistent grant table state such as current
+                               version, partially initialized active table

pages,

docs/misc/grant-tables.txt +10 -0
+                               etc.
+  grant_table->maptrack_lock : spinlock used to protect the maptrack state
+  active_grant_entry->lock   : spinlock used to serialize modifications to
+                               active entries
+
+ The primary lock for the grant table is a read/write spinlock. All
+ functions that access members of struct grant_table must acquire a
+ read lock around critical sections. Any modification to the members
+ of struct grant_table (e.g., nr_status_frames, nr_grant_frames,
+ active frames, etc.) must only be made if the write lock is
Quoted 8 lines
Quoted 2 lines

+ held. These elements are read-mostly, and read critical sections can
+ be large, which makes a rwlock a good choice.

Is there any concern about writer starvation here? I know our spinlocks aren't 'fair' but our rwlocks are guaranteed to starve out writers if there is a steady continuous stream of readers. Perhaps we should write-bias our rwlock, or at least make that an option. We could get fancier but would probably hurt performance.

Yes, I'm a little concerned about writer starvation. But so far even in the presence of very frequent readers it seems like the infrequent writers are able to get the lock when they need to. However, I've not tested the iommu=strict path yet. I'm thinking that in that case there's just going to be frequent writers, so there's less risk of readers starving writers. For what it's worth, when mapcount() gets in the picture with persistent grants, I'd expect to see some pretty significant performance degradation for map/unmap operations. This was also observed in [1] under different circumstances.

But right now I'm more curious about cache line bouncing between all the readers. I've not done any study of inter-arrival times for typical workloads (much less some more extreme workloads like we've been testing), but lock profiling of grant table operations when a spinlock was used showed some pretty long hold times, which should translate fairly well to decent rwlock performance. I'm by no means an expert in this area so I'm eager to hear the thoughts of others.

I should also mention that some of the improvement I mentioned from 3,000 MB/s to 3,600 MB/s was due to avoiding the m2p override spinlock in dom0.

Quoted 1 line

Looks like great work however!

Thanks! I'm definitely interested to see some others' experience with these changes. I think that the double_gt_lock() caused a fair bit of contention on the local domain's grant table lock, which explains some of the poor performance with large numbers of vCPUs as seen in [2].

--msw

[1] http://scholarship.rice.edu/bitstream/handle/1911/71683/RAM-THESIS.pdf
[2] http://xenbits.xen.org/people/royger/persistent_grants/persistent_read24vcpus.png

#5 lore raw
Quoted 6 lines · Matt Wilson
Quoted 5 lines

Is there any concern about writer starvation here? I know our spinlocks aren't 'fair' but our rwlocks are guaranteed to starve out writers if there is a steady continuous stream of readers. Perhaps we should write-bias our rwlock, or at least make that an option. We could get fancier but would probably hurt performance.

Quoted 9 lines

Yes, I'm a little concerned about writer starvation. But so far even in the presence of very frequent readers it seems like the infrequent writers are able to get the lock when they need to. However, I've not tested the iommu=strict path yet. I'm thinking that in that case there's just going to be frequent writers, so there's less risk of readers starving writers. For what it's worth, when mapcount() gets in the picture with persistent grants, I'd expect to see some pretty significant performance degradation for map/unmap operations. This was also observed in [1] under different circumstances.

The average case isn't the only concern here, but also the worst case, which could maybe tie up a CPU for unbounded time. Could a malicious guest set up such a workload? I'm just thinking we don't want to end up with a DoS XSA on this down the line. :)

Quoted 7 lines

But right now I'm more curious about cache line bouncing between all the readers. I've not done any study of inter-arrival times for typical workloads (much less some more extreme workloads like we've been testing), but lock profiling of grant table operations when a spinlock was used showed some pretty long hold times, which should translate fairly well to decent rwlock performance. I'm by no means an expert in this area so I'm eager to hear the thoughts of others.

In the read-heavy case the only improvement would be with the old Linux-style biglock (spinlock per CPU; writers must take all spinlocks), or working out a lock-free scheme for readers (perhaps making use of RCU).

-- Keir

Quoted 3 lines

I should also mention that some of the improvement I mentioned from 3,000 MB/s to 3,600 MB/s was due to avoiding the m2p override spinlock in dom0.

#6 lore raw
Quoted 19 lines
Quoted 1 line
Quoted 1 line · Keir Fraser
Quoted 6 lines · Matt Wilson
Quoted 5 lines

Is there any concern about writer starvation here? I know our spinlocks aren't 'fair' but our rwlocks are guaranteed to starve out writers if there is a steady continuous stream of readers. Perhaps we should write-bias our rwlock, or at least make that an option. We could get fancier but would probably hurt performance.

Quoted 9 lines

Yes, I'm a little concerned about writer starvation. But so far even in the presence of very frequent readers it seems like the infrequent writers are able to get the lock when they need to. However, I've not tested the iommu=strict path yet. I'm thinking that in that case there's just going to be frequent writers, so there's less risk of readers starving writers. For what it's worth, when mapcount() gets in the picture with persistent grants, I'd expect to see some pretty significant performance degradation for map/unmap operations. This was also observed in [1] under different circumstances.

Quoted 4 lines

The average case isn't the only concern here, but also the worst case, which could maybe tie up a CPU for unbounded time. Could a malicious guest set up such a workload? I'm just thinking we don't want to end up with a DoS XSA on this down the line. :)

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

But of course, fairness for writers means that performance may drop again on the read paths, unless the write lock use is strictly limited to code paths not (normally) involved in I/O.

Jan

#7 lore raw
Quoted 18 lines · Jan Beulich
Quoted 13 lines
Quoted 1 line
Quoted 1 line · Keir Fraser
Quoted 9 lines · Matt Wilson

Yes, I'm a little concerned about writer starvation. But so far even in the presence of very frequent readers it seems like the infrequent writers are able to get the lock when they need to. However, I've not tested the iommu=strict path yet. I'm thinking that in that case there's just going to be frequent writers, so there's less risk of readers starving writers. For what it's worth, when mapcount() gets in the picture with persistent grants, I'd expect to see some pretty significant performance degradation for map/unmap operations. This was also observed in [1] under different circumstances.

Quoted 4 lines

The average case isn't the only concern here, but also the worst case, which could maybe tie up a CPU for unbounded time. Could a malicious guest set up such a workload? I'm just thinking we don't want to end up with a DoS XSA on this down the line. :)

Quoted 4 lines

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

Would queuing spinlocks (e.g. MCS locks) be even more preferable? Two atomic ops (cmpxchg) per critical region in the uncontended case. Each CPU spins on its own location so there's no cacheline carnage in the highly contended case (a problem with simple ticket spinlocks). And it builds on cmpxchg so the spinlock implementation has no arch-specific component (apart from cmpxchg, which we already have).

I have a queue-based rwlock design too, does require a spinlock lock/unlock per rwlock op though (i.e., 4 atomic ops per critical region in the uncontended case).

Quoted 3 lines

But of course, fairness for writers means that performance may drop again on the read paths, unless the write lock use is strictly limited to code paths not (normally) involved in I/O.

Yes indeed. Hence depending on other users of rwlock, just letting a writer set its flag and wait for in-flight readers to drain might be sufficient for now.

-- Keir

Quoted 2 lines

Jan

#8 lore raw
Quoted 12 lines · Keir Fraser
Quoted 4 lines

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

Would queuing spinlocks (e.g. MCS locks) be even more preferable? Two atomic ops (cmpxchg) per critical region in the uncontended case. Each CPU spins on its own location so there's no cacheline carnage in the highly contended case (a problem with simple ticket spinlocks). And it builds on cmpxchg so the spinlock implementation has no arch-specific component (apart from cmpxchg, which we already have).

Quoted 3 lines

I have a queue-based rwlock design too, does require a spinlock lock/unlock per rwlock op though (i.e., 4 atomic ops per critical region in the uncontended case).

Actually MCS has a multi-reader extension we could use, or there is another alternative by Krieger et al. My own design was intended to build on pthread primitives and wouldn't be as good as the existing solutions in the literature for purely spinning waiters.

-- Keir

#9 lore raw
Quoted 15 lines
Quoted 1 line
Quoted 1 line · Keir Fraser
Quoted 12 lines · Keir Fraser
Quoted 4 lines

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

Would queuing spinlocks (e.g. MCS locks) be even more preferable? Two atomic ops (cmpxchg) per critical region in the uncontended case. Each CPU spins on its own location so there's no cacheline carnage in the highly contended case (a problem with simple ticket spinlocks). And it builds on cmpxchg so the spinlock implementation has no arch-specific component (apart from cmpxchg, which we already have).

Quoted 8 lines
Quoted 3 lines

I have a queue-based rwlock design too, does require a spinlock lock/unlock per rwlock op though (i.e., 4 atomic ops per critical region in the uncontended case).

Actually MCS has a multi-reader extension we could use, or there is another alternative by Krieger et al. My own design was intended to build on pthread primitives and wouldn't be as good as the existing solutions in the literature for purely spinning waiters.

Sounds nice - are you going to spend time on implementing this then?

Jan

#10 lore raw
Quoted 19 lines · Jan Beulich
Quoted 19 lines
Quoted 1 line
Quoted 1 line · Keir Fraser
Quoted 15 lines · Keir Fraser
Quoted 4 lines

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

Would queuing spinlocks (e.g. MCS locks) be even more preferable? Two atomic ops (cmpxchg) per critical region in the uncontended case. Each CPU spins on its own location so there's no cacheline carnage in the highly contended case (a problem with simple ticket spinlocks). And it builds on cmpxchg so the spinlock implementation has no arch-specific component (apart from cmpxchg, which we already have).

I have a queue-based rwlock design too, does require a spinlock lock/unlock per rwlock op though (i.e., 4 atomic ops per critical region in the uncontended case).

Quoted 6 lines
Quoted 4 lines

Actually MCS has a multi-reader extension we could use, or there is another alternative by Krieger et al. My own design was intended to build on pthread primitives and wouldn't be as good as the existing solutions in the literature for purely spinning waiters.

Sounds nice - are you going to spend time on implementing this then?

Yes I'll look into it. Amazon's benchmarking of grant-table throughput will be a good testbed for performance of a different lock implementation.

-- Keir

Quoted 2 lines

Jan

#11 lore raw

We are very excited to see progress in this area following up from the discussions we had at the BoF. I will be happy to benchmark these patches in our environment as well.

Thanks,
Felipe

-----Original Message-----
From: Keir Fraser [mailto:[email protected]]
Sent: 12 November 2013 14:25
To: Jan Beulich
Cc: Anthony Liguori; Matt Wilson; Andrew Cooper; David Vrabel; Felipe Franciosi; Roger Pau Monne; Matt Wilson; [email protected]; Konrad Rzeszutek Wilk
Subject: Re: [RFC PATCH 2/2] gnttab: refactor locking for better scalability

<...>

Quoted 1 line

Sounds nice - are you going to spend time on implementing this then?

Yes I'll look into it. Amazon's benchmarking of grant-table throughput will be a good testbed for performance of a different lock implementation.

-- Keir

Quoted 2 lines

Jan

#12 lore raw
In reply to Keir Fraser
Quoted 26 lines · Keir Fraser
Quoted 24 lines · Jan Beulich
Quoted 23 lines
Quoted 1 line
Quoted 1 line · Keir Fraser
Quoted 12 lines · Keir Fraser
Quoted 4 lines

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

Would queuing spinlocks (e.g. MCS locks) be even more preferable? Two atomic ops (cmpxchg) per critical region in the uncontended case. Each CPU spins on its own location so there's no cacheline carnage in the highly contended case (a problem with simple ticket spinlocks). And it builds on cmpxchg so the spinlock implementation has no arch-specific component (apart from cmpxchg, which we already have).

Quoted 3 lines

I have a queue-based rwlock design too, does require a spinlock lock/unlock per rwlock op though (i.e., 4 atomic ops per critical region in the uncontended case).

Actually MCS has a multi-reader extension we could use, or there is another alternative by Krieger et al. My own design was intended to build on pthread primitives and wouldn't be as good as the existing solutions in the literature for purely spinning waiters.

Quoted 4 lines
Quoted 1 line

Sounds nice - are you going to spend time on implementing this then?

Yes I'll look into it. Amazon's benchmarking of grant-table throughput will be a good testbed for performance of a different lock implementation.

ping?

Quoted 12 lines

-- Keir

Quoted 2 lines

Jan

_______________________________________________
Xen-devel mailing list
[email protected]
http://lists.xen.org/xen-devel

#13 lore raw
Quoted 27 lines · Konrad Rzeszutek Wilk
Quoted 26 lines · Keir Fraser
Quoted 24 lines · Jan Beulich
Quoted 23 lines
Quoted 1 line
Quoted 1 line · Keir Fraser
Quoted 12 lines · Keir Fraser
Quoted 4 lines

And indeed I think we should be making our rwlocks fair for writers before pushing in the change here; I've been meaning to get to this for a while, but other stuff continues to require attention. I'm also of the opinion that we should switch to ticket spinlocks.

Would queuing spinlocks (e.g. MCS locks) be even more preferable? Two atomic ops (cmpxchg) per critical region in the uncontended case. Each CPU spins on its own location so there's no cacheline carnage in the highly contended case (a problem with simple ticket spinlocks). And it builds on cmpxchg so the spinlock implementation has no arch-specific component (apart from cmpxchg, which we already have).

Quoted 3 lines

I have a queue-based rwlock design too, does require a spinlock lock/unlock per rwlock op though (i.e., 4 atomic ops per critical region in the uncontended case).

Actually MCS has a multi-reader extension we could use, or there is another alternative by Krieger et al. My own design was intended to build on pthread primitives and wouldn't be as good as the existing solutions in the literature for purely spinning waiters.

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

Sounds nice - are you going to spend time on implementing this then?

Yes I'll look into it. Amazon's benchmarking of grant-table throughput will be a good testbed for performance of a different lock implementation.

ping?

Ooph. Sorry, I've not had any time to work on this since posting last year. Has there been any other discussion about a new locking primitive?

Konrad, are you looking for someone to rebase and break up the proposed patch as is?

--msw

#14 lore raw
In reply to Keir Fraser
Quoted 18 lines · Keir Fraser
Quoted 6 lines · Matt Wilson
Quoted 5 lines

Is there any concern about writer starvation here? I know our spinlocks aren't 'fair' but our rwlocks are guaranteed to starve out writers if there is a steady continuous stream of readers. Perhaps we should write-bias our rwlock, or at least make that an option. We could get fancier but would probably hurt performance.

Quoted 9 lines

Yes, I'm a little concerned about writer starvation. But so far even in the presence of very frequent readers it seems like the infrequent writers are able to get the lock when they need to. However, I've not tested the iommu=strict path yet. I'm thinking that in that case there's just going to be frequent writers, so there's less risk of readers starving writers. For what it's worth, when mapcount() gets in the picture with persistent grants, I'd expect to see some pretty significant performance degradation for map/unmap operations. This was also observed in [1] under different circumstances.

Quoted 4 lines

The average case isn't the only concern here, but also the worst case, which could maybe tie up a CPU for unbounded time. Could a malicious guest set up such a workload? I'm just thinking we don't want to end up with a DoS XSA on this down the line. :)

Indeed.

Quoted 19 lines
Quoted 7 lines

But right now I'm more curious about cache line bouncing between all the readers. I've not done any study of inter-arrival times for typical workloads (much less some more extreme workloads like we've been testing), but lock profiling of grant table operations when a spinlock was used showed some pretty long hold times, which should translate fairly well to decent rwlock performance. I'm by no means an expert in this area so I'm eager to hear the thoughts of others.

In the read-heavy case the only improvement would be with the old Linux-style biglock (spinlock per CPU; writers must take all spinlocks), or working out a lock-free scheme for readers (perhaps making use of RCU).

-- Keir

Quoted 3 lines

I should also mention that some of the improvement I mentioned from 3,000 MB/s to 3,600 MB/s was due to avoiding the m2p override spinlock in dom0.

#15 lore raw
In reply to Matt Wilson
Quoted 3 lines

I should also mention that some of the improvement I mentioned from 3,000 MB/s to 3,600 MB/s was due to avoiding the m2p override spinlock in dom0.

Could you post said patch please? I presume its pretty simple but I would like the credit to go to you guys.

#16 lore raw
Quoted 6 lines · Konrad Rzeszutek Wilk
Quoted 3 lines

I should also mention that some of the improvement I mentioned from 3,000 MB/s to 3,600 MB/s was due to avoiding the m2p override spinlock in dom0.

Could you post said patch please? I presume its pretty simple but I would like the credit to go to you guys.

Roger already posted it.

https://lkml.org/lkml/2013/11/5/121

I think we're just waiting for a repost with a more detailed commit message.

David

#17 lore raw
Quoted 5 lines · David Vrabel
Quoted 4 lines · Konrad Rzeszutek Wilk
Quoted 3 lines

I should also mention that some of the improvement I mentioned from 3,000 MB/s to 3,600 MB/s was due to avoiding the m2p override spinlock in dom0.

Quoted 8 lines
Quoted 2 lines

Could you post said patch please? I presume its pretty simple but I would like the credit to go to you guys.

Roger already posted it.

https://lkml.org/lkml/2013/11/5/121

I think we're just waiting for a repost with a more detailed commit message.

Roger's patch isn't correct. It doesn't actually restore the previous mfn because it's storing the new mfn in page private not the old one.

I have a patch that I'll post this afternoon.

Regards,

Anthony Liguori

Quoted 6 lines

David

_______________________________________________
Xen-devel mailing list
[email protected]
http://lists.xen.org/xen-devel

#18 lore raw
In reply to Matt Wilson
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Matt Wilson

From: Matt Wilson <[email protected]>

This patch refactors grant table locking. It splits the previous single spinlock per grant table into multiple locks. The heavily modified components of the grant table (the maptrack state and the active entries) are now protected by their own spinlocks. The remaining elements of the grant table are read-mostly, so the main grant table lock is modified to be a rwlock to improve concurrency.

Workloads with high grant table operation rates, especially map/unmap operations as used by blkback/blkfront when persistent grants are not supported, show marked improvement with these changes. A domU with 24 VBDs in a streaming 2M write workload achieved 1,400 MB/sec before this change. Performance more than doubles with this patch, reaching 3,000 MB/sec before tuning and 3,600 MB/sec after adjusting event channel vCPU bindings.

Quoted 1 line

I will have to take a thorough second look at this, but considering its size - would it be possible to split out the conversion of the main lock to an rw one into a third patch? Correctness of the second one wouldn't suffer from this.

And I'd also suggest converting all the maptrack_ fields into a separate sub-structure named maptrack. That'd not only guarantee things to be kept together, but may also allow passing the address of the sub-structure as argument to one or another helper function instead of the full structure's, thus making it more clear what such a function actually acts upon (and in particular what it does _not_ touch).

Jan

#19 lore raw
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Matt Wilson

From: Matt Wilson <[email protected]>

This patch refactors grant table locking. It splits the previous single spinlock per grant table into multiple locks. The heavily modified components of the grant table (the maptrack state and the active entries) are now protected by their own spinlocks. The remaining elements of the grant table are read-mostly, so the main grant table lock is modified to be a rwlock to improve concurrency.

Workloads with high grant table operation rates, especially map/unmap operations as used by blkback/blkfront when persistent grants are not supported, show marked improvement with these changes. A domU with 24 VBDs in a streaming 2M write workload achieved 1,400 MB/sec before this change. Performance more than doubles with this patch, reaching 3,000 MB/sec before tuning and 3,600 MB/sec after adjusting event channel vCPU bindings.

Quoted 6 lines
Quoted 1 line

I will have to take a thorough second look at this, but considering its size - would it be possible to split out the conversion of the main lock to an rw one into a third patch? Correctness of the second one wouldn't suffer from this.

Yes, I figured that there would be a request to break this up. I'll have to think hard for each change to make sure that nothing breaks (e.g., deadlock scenarios) for each step along the way. But this is a useful exercise.

It should be possible to first add the separate locking for maptrack, followed by fine grained locking for active entries, then finally moving the main grant table lock to a rwlock (or some other locking primitive should one become available).

Quoted 7 lines

And I'd also suggest converting all the maptrack_ fields into a separate sub-structure named maptrack. That'd not only guarantee things to be kept together, but may also allow passing the address of the sub-structure as argument to one or another helper function instead of the full structure's, thus making it more clear what such a function actually acts upon (and in particular what it does _not_ touch).

I agree. Do you have any thoughts on padding the spinlock out to a cache line to avoid false sharing of the other elements? The maptrack critical sections are extremely short, so there might not be any real need for this. I've not done any measurement of maptrack spinlock contention with this change yet. I vaguely remember Anthony doing some measurement on an early PoC version that didn't show contention. It's probably a premature optimization...

--msw

#20 lore raw
Quoted 3 lines
Quoted 1 line
Quoted 1 line · Matt Wilson

Do you have any thoughts on padding the spinlock out to a cache line to avoid false sharing of the other elements?

Wouldn't that be counter productive? Once you need to acquire the lock, you need ownership on the line anyway, and hence it seems desirable to have the other elements in the same cache line. Unless of course there are significant parts here that are read-mostly (but I concluded from your use of a spin lock rather than an rw one that there generally are modifications done when holding the lock).

What we may want to push out of it are elements outside the maptrack sub-structure.

Jan