Re: [PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Vlastimil Babka]

On 11/17/2015 05:17 PM, Nathan Zimmer wrote:

When running the SPECint_rate gcc on some very large boxes it was noticed
that the system was spending lots of time in mpol_shared_policy_lookup.
The gamess benchmark can also show it and is what I mostly used to chase
down the issue since the setup for that I found a easier.

To be clear the binaries were on tmpfs because of disk I/O reqruirements.
We then used text replication to avoid icache misses and having all the
copies banging on the memory where the instruction code resides.
This results in us hitting a bottle neck in mpol_shared_policy_lookup
since lookup is serialised by the shared_policy lock.

I have only reproduced this on very large (3k+ cores) boxes.  The problem
starts showing up at just a few hundred ranks getting worse until it
threatens to livelock once it gets large enough.
For example on the gamess benchmark at 128 ranks this area consumes only
~1% of time, at 512 ranks it consumes nearly 13%, and at 2k ranks it is
over 90%.

To alleviate the contention on this area I converted the spinslock to a
rwlock.  This allows the large number of lookups to happen simultaneously.
The results were quite good reducing this to consumtion at max ranks to
around 2%.

Acked-by: David Rientjes 


Acked-by: Vlastimil Babka 

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Vlastimil Babka]

On 11/17/2015 05:17 PM, Nathan Zimmer wrote:

When running the SPECint_rate gcc on some very large boxes it was noticed
that the system was spending lots of time in mpol_shared_policy_lookup.
The gamess benchmark can also show it and is what I mostly used to chase
down the issue since the setup for that I found a easier.

To be clear the binaries were on tmpfs because of disk I/O reqruirements.
We then used text replication to avoid icache misses and having all the
copies banging on the memory where the instruction code resides.
This results in us hitting a bottle neck in mpol_shared_policy_lookup
since lookup is serialised by the shared_policy lock.

I have only reproduced this on very large (3k+ cores) boxes.  The problem
starts showing up at just a few hundred ranks getting worse until it
threatens to livelock once it gets large enough.
For example on the gamess benchmark at 128 ranks this area consumes only
~1% of time, at 512 ranks it consumes nearly 13%, and at 2k ranks it is
over 90%.

To alleviate the contention on this area I converted the spinslock to a
rwlock.  This allows the large number of lookups to happen simultaneously.
The results were quite good reducing this to consumtion at max ranks to
around 2%.

Acked-by: David Rientjes 


Acked-by: Vlastimil Babka 

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Vlastimil Babka]

On 11/18/2015 09:05 PM, Nathan Zimmer wrote:



On 11/18/2015 07:50 AM, Vlastimil Babka wrote:

At first glance it seems that RCU would be a good fit here and achieve even
better lookup scalability, have you considered it?



Originally that was my plan but when I saw how good the results were
with the rwlock, I chickened out and took the less prone to mistakes way.

I should also note that the 2% time left in system is not from this lookup
but another area.


Ah, I see, thanks!
Vlastimil


Nate



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Vlastimil Babka]

On 11/18/2015 09:05 PM, Nathan Zimmer wrote:



On 11/18/2015 07:50 AM, Vlastimil Babka wrote:

At first glance it seems that RCU would be a good fit here and achieve even
better lookup scalability, have you considered it?



Originally that was my plan but when I saw how good the results were
with the rwlock, I chickened out and took the less prone to mistakes way.

I should also note that the 2% time left in system is not from this lookup
but another area.


Ah, I see, thanks!
Vlastimil


Nate



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Vlastimil Babka]

On 11/17/2015 05:17 PM, Nathan Zimmer wrote:
> When running the SPECint_rate gcc on some very large boxes it was noticed
> that the system was spending lots of time in mpol_shared_policy_lookup.
> The gamess benchmark can also show it and is what I mostly used to chase
> down the issue since the setup for that I found a easier.
> 
> To be clear the binaries were on tmpfs because of disk I/O reqruirements.
> We then used text replication to avoid icache misses and having all the
> copies banging on the memory where the instruction code resides.
> This results in us hitting a bottle neck in mpol_shared_policy_lookup
> since lookup is serialised by the shared_policy lock.
> 
> I have only reproduced this on very large (3k+ cores) boxes.  The problem
> starts showing up at just a few hundred ranks getting worse until it
> threatens to livelock once it gets large enough.
> For example on the gamess benchmark at 128 ranks this area consumes only
> ~1% of time, at 512 ranks it consumes nearly 13%, and at 2k ranks it is
> over 90%.
> 
> To alleviate the contention on this area I converted the spinslock to a
> rwlock.  This allows the large number of lookups to happen simultaneously.
> The results were quite good reducing this to consumtion at max ranks to
> around 2%.

At first glance it seems that RCU would be a good fit here and achieve even
better lookup scalability, have you considered it?

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Vlastimil Babka]

On 11/17/2015 05:17 PM, Nathan Zimmer wrote:
> When running the SPECint_rate gcc on some very large boxes it was noticed
> that the system was spending lots of time in mpol_shared_policy_lookup.
> The gamess benchmark can also show it and is what I mostly used to chase
> down the issue since the setup for that I found a easier.
> 
> To be clear the binaries were on tmpfs because of disk I/O reqruirements.
> We then used text replication to avoid icache misses and having all the
> copies banging on the memory where the instruction code resides.
> This results in us hitting a bottle neck in mpol_shared_policy_lookup
> since lookup is serialised by the shared_policy lock.
> 
> I have only reproduced this on very large (3k+ cores) boxes.  The problem
> starts showing up at just a few hundred ranks getting worse until it
> threatens to livelock once it gets large enough.
> For example on the gamess benchmark at 128 ranks this area consumes only
> ~1% of time, at 512 ranks it consumes nearly 13%, and at 2k ranks it is
> over 90%.
> 
> To alleviate the contention on this area I converted the spinslock to a
> rwlock.  This allows the large number of lookups to happen simultaneously.
> The results were quite good reducing this to consumtion at max ranks to
> around 2%.

At first glance it seems that RCU would be a good fit here and achieve even
better lookup scalability, have you considered it?

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Nathan Zimmer]

When running the SPECint_rate gcc on some very large boxes it was noticed
that the system was spending lots of time in mpol_shared_policy_lookup.
The gamess benchmark can also show it and is what I mostly used to chase
down the issue since the setup for that I found a easier.

To be clear the binaries were on tmpfs because of disk I/O reqruirements.
We then used text replication to avoid icache misses and having all the
copies banging on the memory where the instruction code resides.
This results in us hitting a bottle neck in mpol_shared_policy_lookup
since lookup is serialised by the shared_policy lock.

I have only reproduced this on very large (3k+ cores) boxes.  The problem
starts showing up at just a few hundred ranks getting worse until it
threatens to livelock once it gets large enough.
For example on the gamess benchmark at 128 ranks this area consumes only
~1% of time, at 512 ranks it consumes nearly 13%, and at 2k ranks it is
over 90%.

To alleviate the contention on this area I converted the spinslock to a
rwlock.  This allows the large number of lookups to happen simultaneously.
The results were quite good reducing this to consumtion at max ranks to
around 2%.

Acked-by: David Rientjes 
Cc: Andrew Morton 
Cc: Nadia Yvette Chambers 
Cc: Naoya Horiguchi 
Cc: Mel Gorman 
Cc: "Aneesh Kumar K.V" 
Cc: linux-kernel@vger.kernel.org
Cc: linux...@kvack.org
Signed-off-by: Nathan Zimmer 
---
 fs/hugetlbfs/inode.c  |  2 +-
 include/linux/mempolicy.h |  2 +-
 mm/mempolicy.c| 20 ++--
 3 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c
index 316adb9..ab7b155 100644
--- a/fs/hugetlbfs/inode.c
+++ b/fs/hugetlbfs/inode.c
@@ -739,7 +739,7 @@ static struct inode *hugetlbfs_get_inode(struct super_block 
*sb,
/*
 * The policy is initialized here even if we are creating a
 * private inode because initialization simply creates an
-* an empty rb tree and calls spin_lock_init(), later when we
+* an empty rb tree and calls rwlock_init(), later when we
 * call mpol_free_shared_policy() it will just return because
 * the rb tree will still be empty.
 */
diff --git a/include/linux/mempolicy.h b/include/linux/mempolicy.h
index 3d385c8..2696c1f 100644
--- a/include/linux/mempolicy.h
+++ b/include/linux/mempolicy.h
@@ -122,7 +122,7 @@ struct sp_node {
 
 struct shared_policy {
struct rb_root root;
-   spinlock_t lock;
+   rwlock_t lock;
 };
 
 int vma_dup_policy(struct vm_area_struct *src, struct vm_area_struct *dst);
diff --git a/mm/mempolicy.c b/mm/mempolicy.c
index 87a1779..197d917 100644
--- a/mm/mempolicy.c
+++ b/mm/mempolicy.c
@@ -2142,7 +2142,7 @@ bool __mpol_equal(struct mempolicy *a, struct mempolicy 
*b)
  *
  * Remember policies even when nobody has shared memory mapped.
  * The policies are kept in Red-Black tree linked from the inode.
- * They are protected by the sp->lock spinlock, which should be held
+ * They are protected by the sp->lock rwlock, which should be held
  * for any accesses to the tree.
  */
 
@@ -2179,7 +2179,7 @@ sp_lookup(struct shared_policy *sp, unsigned long start, 
unsigned long end)
 }
 
 /* Insert a new shared policy into the list. */
-/* Caller holds sp->lock */
+/* Caller holds the write of sp->lock */
 static void sp_insert(struct shared_policy *sp, struct sp_node *new)
 {
struct rb_node **p = >root.rb_node;
@@ -2211,13 +2211,13 @@ mpol_shared_policy_lookup(struct shared_policy *sp, 
unsigned long idx)
 
if (!sp->root.rb_node)
return NULL;
-   spin_lock(>lock);
+   read_lock(>lock);
sn = sp_lookup(sp, idx, idx+1);
if (sn) {
mpol_get(sn->policy);
pol = sn->policy;
}
-   spin_unlock(>lock);
+   read_unlock(>lock);
return pol;
 }
 
@@ -2360,7 +2360,7 @@ static int shared_policy_replace(struct shared_policy 
*sp, unsigned long start,
int ret = 0;
 
 restart:
-   spin_lock(>lock);
+   write_lock(>lock);
n = sp_lookup(sp, start, end);
/* Take care of old policies in the same range. */
while (n && n->start < end) {
@@ -2393,7 +2393,7 @@ restart:
}
if (new)
sp_insert(sp, new);
-   spin_unlock(>lock);
+   write_unlock(>lock);
ret = 0;
 
 err_out:
@@ -2405,7 +2405,7 @@ err_out:
return ret;
 
 alloc_new:
-   spin_unlock(>lock);
+   write_unlock(>lock);
ret = -ENOMEM;
n_new = kmem_cache_alloc(sn_cache, GFP_KERNEL);
if (!n_new)
@@ -2431,7 +2431,7 @@ void mpol_shared_policy_init(struct shared_policy *sp, 
struct mempolicy *mpol)
int ret;
 
sp->root = RB_ROOT; /* empty tree == default mempolicy */
-   spin_lock_init(>lock);
+   rwlock_init(>lock);
 
if (mpol) {
struct 

[PATCH] mempolicy: convert the shared_policy lock to a rwlock

[Nathan Zimmer]

When running the SPECint_rate gcc on some very large boxes it was noticed
that the system was spending lots of time in mpol_shared_policy_lookup.
The gamess benchmark can also show it and is what I mostly used to chase
down the issue since the setup for that I found a easier.

To be clear the binaries were on tmpfs because of disk I/O reqruirements.
We then used text replication to avoid icache misses and having all the
copies banging on the memory where the instruction code resides.
This results in us hitting a bottle neck in mpol_shared_policy_lookup
since lookup is serialised by the shared_policy lock.

I have only reproduced this on very large (3k+ cores) boxes.  The problem
starts showing up at just a few hundred ranks getting worse until it
threatens to livelock once it gets large enough.
For example on the gamess benchmark at 128 ranks this area consumes only
~1% of time, at 512 ranks it consumes nearly 13%, and at 2k ranks it is
over 90%.

To alleviate the contention on this area I converted the spinslock to a
rwlock.  This allows the large number of lookups to happen simultaneously.
The results were quite good reducing this to consumtion at max ranks to
around 2%.

Acked-by: David Rientjes 
Cc: Andrew Morton 
Cc: Nadia Yvette Chambers 
Cc: Naoya Horiguchi 
Cc: Mel Gorman 
Cc: "Aneesh Kumar K.V" 
Cc: linux-kernel@vger.kernel.org
Cc: linux...@kvack.org
Signed-off-by: Nathan Zimmer 
---
 fs/hugetlbfs/inode.c  |  2 +-
 include/linux/mempolicy.h |  2 +-
 mm/mempolicy.c| 20 ++--
 3 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/fs/hugetlbfs/inode.c b/fs/hugetlbfs/inode.c
index 316adb9..ab7b155 100644
--- a/fs/hugetlbfs/inode.c
+++ b/fs/hugetlbfs/inode.c
@@ -739,7 +739,7 @@ static struct inode *hugetlbfs_get_inode(struct super_block 
*sb,
/*
 * The policy is initialized here even if we are creating a
 * private inode because initialization simply creates an
-* an empty rb tree and calls spin_lock_init(), later when we
+* an empty rb tree and calls rwlock_init(), later when we
 * call mpol_free_shared_policy() it will just return because
 * the rb tree will still be empty.
 */
diff --git a/include/linux/mempolicy.h b/include/linux/mempolicy.h
index 3d385c8..2696c1f 100644
--- a/include/linux/mempolicy.h
+++ b/include/linux/mempolicy.h
@@ -122,7 +122,7 @@ struct sp_node {
 
 struct shared_policy {
struct rb_root root;
-   spinlock_t lock;
+   rwlock_t lock;
 };
 
 int vma_dup_policy(struct vm_area_struct *src, struct vm_area_struct *dst);
diff --git a/mm/mempolicy.c b/mm/mempolicy.c
index 87a1779..197d917 100644
--- a/mm/mempolicy.c
+++ b/mm/mempolicy.c
@@ -2142,7 +2142,7 @@ bool __mpol_equal(struct mempolicy *a, struct mempolicy 
*b)
  *
  * Remember policies even when nobody has shared memory mapped.
  * The policies are kept in Red-Black tree linked from the inode.
- * They are protected by the sp->lock spinlock, which should be held
+ * They are protected by the sp->lock rwlock, which should be held
  * for any accesses to the tree.
  */
 
@@ -2179,7 +2179,7 @@ sp_lookup(struct shared_policy *sp, unsigned long start, 
unsigned long end)
 }
 
 /* Insert a new shared policy into the list. */
-/* Caller holds sp->lock */
+/* Caller holds the write of sp->lock */
 static void sp_insert(struct shared_policy *sp, struct sp_node *new)
 {
struct rb_node **p = >root.rb_node;
@@ -2211,13 +2211,13 @@ mpol_shared_policy_lookup(struct shared_policy *sp, 
unsigned long idx)
 
if (!sp->root.rb_node)
return NULL;
-   spin_lock(>lock);
+   read_lock(>lock);
sn = sp_lookup(sp, idx, idx+1);
if (sn) {
mpol_get(sn->policy);
pol = sn->policy;
}
-   spin_unlock(>lock);
+   read_unlock(>lock);
return pol;
 }
 
@@ -2360,7 +2360,7 @@ static int shared_policy_replace(struct shared_policy 
*sp, unsigned long start,
int ret = 0;
 
 restart:
-   spin_lock(>lock);
+   write_lock(>lock);
n = sp_lookup(sp, start, end);
/* Take care of old policies in the same range. */
while (n && n->start < end) {
@@ -2393,7 +2393,7 @@ restart:
}
if (new)
sp_insert(sp, new);
-   spin_unlock(>lock);
+   write_unlock(>lock);
ret = 0;
 
 err_out:
@@ -2405,7 +2405,7 @@ err_out:
return ret;
 
 alloc_new:
-   spin_unlock(>lock);
+   write_unlock(>lock);
ret = -ENOMEM;
n_new = kmem_cache_alloc(sn_cache, GFP_KERNEL);
if (!n_new)
@@ -2431,7 +2431,7 @@ void mpol_shared_policy_init(struct shared_policy *sp, 
struct mempolicy *mpol)
int ret;
 
sp->root =