[PATCH] exponential backoff for blocked LOCK call polling

[PATCH] exponential backoff for blocked LOCK call polling

[Greg Banks]

[-- Attachment #1: Type: text/plain, Size: 261 bytes --]

G'day,

The attached patch makes the NLM client do exponential backoff
for the polling used to handle the case that the server has not
sent a GRANTED callback.

Greg.
-- 
Greg Banks, R&D Software Engineer, SGI Australian Software Group.
I don't speak for SGI.


[-- Attachment #2: gnb-nlm-block-backoff --]
[-- Type: text/plain, Size: 3369 bytes --]

Implement exponential backoff for the NLM client LOCK call polling
when the server doesn't send the client a GRANTED callback.

Signed-off-by: Greg Banks <gnb@melbourne.sgi.com>

Index: linux/fs/lockd/clntlock.c
===================================================================
--- linux.orig/fs/lockd/clntlock.c	Thu Oct 21 17:18:37 2004
+++ linux/fs/lockd/clntlock.c	Thu Oct 21 17:25:03 2004
@@ -45,7 +45,8 @@ static struct nlm_wait *	nlm_blocked;
  * Block on a lock
  */
 int
-nlmclnt_block(struct nlm_host *host, struct file_lock *fl, u32 *statp)
+nlmclnt_block(struct nlm_host *host, struct file_lock *fl, u32 *statp,
+	      int delay)
 {
 	struct nlm_wait	block, **head;
 	int		err;
@@ -64,12 +65,8 @@ nlmclnt_block(struct nlm_host *host, str
 	/* Go to sleep waiting for GRANT callback. Some servers seem
 	 * to lose callbacks, however, so we're going to poll from
 	 * time to time just to make sure.
-	 *
-	 * For now, the retry frequency is pretty high; normally 
-	 * a 1 minute timeout would do. See the comment before
-	 * nlmclnt_lock for an explanation.
 	 */
-	sleep_on_timeout(&block.b_wait, 30*HZ);
+	sleep_on_timeout(&block.b_wait, delay);
 
 	for (head = &nlm_blocked; *head; head = &(*head)->b_next) {
 		if (*head == &block) {
Index: linux/fs/lockd/clntproc.c
===================================================================
--- linux.orig/fs/lockd/clntproc.c	Mon Oct  4 14:35:14 2004
+++ linux/fs/lockd/clntproc.c	Thu Oct 21 17:26:43 2004
@@ -534,12 +534,16 @@ static void nlmclnt_locks_init_private(s
  * This is one of the lovely things about standards in the NFS area:
  * they're so soft and squishy you can't really blame HP for doing this.
  */
+#define NLM_LOCK_RETRY_DELAY_MIN	(110*HZ/100)
+#define NLM_LOCK_RETRY_DELAY_MAX	(64*NLM_LOCK_RETRY_DELAY_MIN)
+
 static int
 nlmclnt_lock(struct nlm_rqst *req, struct file_lock *fl)
 {
 	struct nlm_host	*host = req->a_host;
 	struct nlm_res	*resp = &req->a_res;
 	int		status;
+	int		delay = NLM_LOCK_RETRY_DELAY_MIN;
 
 	if (!host->h_monitored && nsm_monitor(host) < 0) {
 		printk(KERN_NOTICE "lockd: failed to monitor %s\n",
@@ -552,7 +556,13 @@ nlmclnt_lock(struct nlm_rqst *req, struc
 		if ((status = nlmclnt_call(req, NLMPROC_LOCK)) >= 0) {
 			if (resp->status != NLM_LCK_BLOCKED)
 				break;
-			status = nlmclnt_block(host, fl, &resp->status);
+			status = nlmclnt_block(host, fl, &resp->status, delay);
+			/* 
+			 * Use an exponential backoff strategy for best
+			 * compromise between response time and efficiency
+			 */
+			if (delay < NLM_LOCK_RETRY_DELAY_MAX)
+				delay <<= 1;
 		}
 		if (status < 0)
 			goto out;
Index: linux/include/linux/lockd/lockd.h
===================================================================
--- linux.orig/include/linux/lockd/lockd.h	Thu Oct 21 17:08:30 2004
+++ linux/include/linux/lockd/lockd.h	Thu Oct 21 17:23:43 2004
@@ -145,7 +145,7 @@ extern unsigned long		nlmsvc_timeout;
 struct nlm_rqst * nlmclnt_alloc_call(void);
 int		  nlmclnt_call(struct nlm_rqst *, u32);
 int		  nlmclnt_async_call(struct nlm_rqst *, u32, rpc_action);
-int		  nlmclnt_block(struct nlm_host *, struct file_lock *, u32 *);
+int		  nlmclnt_block(struct nlm_host *, struct file_lock *, u32 *, int);
 int		  nlmclnt_cancel(struct nlm_host *, struct file_lock *);
 u32		  nlmclnt_grant(struct nlm_lock *);
 void		  nlmclnt_recovery(struct nlm_host *, u32);

Re: [PATCH] exponential backoff for blocked LOCK call polling

[Ara.T.Howard]

On Tue, 26 Oct 2004, Greg Banks wrote:

> G'day,
>
> The attached patch makes the NLM client do exponential backoff
> for the polling used to handle the case that the server has not
> sent a GRANTED callback.
>
> Greg.
> --
> Greg Banks, R&D Software Engineer, SGI Australian Software Group.
> I don't speak for SGI.

i implemented something exactly like this in userland for some code for which
many ( > 30) hosts are competing for a lock.  i didn't want to use blocking
locks as the performance was terrible (seeing one host obtain the lock
thousands of time in a row).  instead i used non-blocking locks with the
following algorithim for backing off:

   - client becomes more and more patient (similar to your exponential backoff
     - mine is linear though)

   - client eventually becomes impatient again

if i read your code right it looks like, once max delay is reached, it stays
there.  this will mean that a client waiting a long time has an increasingly
significant change of being starved when a lock is under heavy contention
doesn't it?  in any case it seems like resetting the delay to min after
reaching max (becoming impatient again) may give better performance on average
than simply staying at max.

kind regards.

-a
--
===============================================================================
| EMAIL   :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
| PHONE   :: 303.497.6469
| When you do something, you should burn yourself completely, like a good
| bonfire, leaving no trace of yourself.  --Shunryu Suzuki
===============================================================================


-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH] exponential backoff for blocked LOCK call polling

[Greg Banks]

On Mon, Nov 08, 2004 at 10:27:19AM -0700, Ara.T.Howard wrote:
> On Tue, 26 Oct 2004, Greg Banks wrote:
> if i read your code right it looks like, once max delay is reached, it stays
> there.

Yes.

>  this will mean that a client waiting a long time has an increasingly
> significant change of being starved when a lock is under heavy contention
> doesn't it?

Not if the server has queued the lock request.  But then if the server
were correctly implemented it would probably be sending us a GRANTED
callback and we wouldn't need to poll.

>  in any case it seems like resetting the delay to min after
> reaching max (becoming impatient again) may give better performance on 
> average
> than simply staying at max.

Could do.  Do you want to do the patch?

Greg.
-- 
Greg Banks, R&D Software Engineer, SGI Australian Software Group.
I don't speak for SGI.


-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH] exponential backoff for blocked LOCK call polling

[Ara.T.Howard]

On Tue, 9 Nov 2004, Greg Banks wrote:

>>  this will mean that a client waiting a long time has an increasingly
>>  significant change of being starved when a lock is under heavy contention
>>  doesn't it?
>
> Not if the server has queued the lock request.  But then if the server were
> correctly implemented it would probably be sending us a GRANTED callback and
> we wouldn't need to poll.

i figured as much - wan't quite sure the reason for the poll...

>>  in any case it seems like resetting the delay to min after reaching max
>>  (becoming impatient again) may give better performance on average than
>>  simply staying at max.
>
> Could do.  Do you want to do the patch?

i could - but not for a week or more... all i was really thinking is

   delay =
     delay < NLM_LOCK_RETRY_DELAY_MAX ? delay << 1 : NLM_LOCK_RETRY_DELAY_MIN;

cheers.

-a
--
===============================================================================
| EMAIL   :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
| PHONE   :: 303.497.6469
| When you do something, you should burn yourself completely, like a good
| bonfire, leaving no trace of yourself.  --Shunryu Suzuki
===============================================================================


-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: [PATCH] exponential backoff for blocked LOCK call polling

[Olaf Kirch]

On Tue, Nov 09, 2004 at 09:54:11AM +1100, Greg Banks wrote:
> Not if the server has queued the lock request.  But then if the server
> were correctly implemented it would probably be sending us a GRANTED
> callback and we wouldn't need to poll.

The Linux lockd should send a GRANTED message. The only reason I
implemented polling was as a workaround against broken lockd's that would
never send GRANTED messages if you used the (synchronous) NLM_LOCK call
instead of the (asynchronous) NLM_LOCK_MSG. HPUX 10.something was one
of them.

I agree though that the polling code is bad because it masks potential
bugs in the Linux lockd.

Olaf
-- 
Olaf Kirch     | Things that make Monday morning interesting, #1:
okir@suse.de   |        "I want to use NFS over AX25, can you help me?"
---------------+ 


-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs