[PATCH mh/lockfile-retry] lockfile: replace random() by rand()

[PATCH mh/lockfile-retry] lockfile: replace random() by rand()

[Johannes Sixt]

On Windows, we do not have functions srandom() and random(). Use srand()
and rand(). These functions produce random numbers of lesser quality,
but for the purpose (a retry time-out) they are still good enough.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
There you have it: Look the other way for a while, and people start
using exotic stuff... ;)

This is a build breakage of master on Windows. There are also a few
new test suite failures. On of them is in t1404#2, indicating that
a DF conflict takes a different error path. I haven't debugged, yet.
The lock file retry test fails, too. I'll report back as time permits.

 lockfile.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lockfile.c b/lockfile.c
index 5a93bc7..ee5cb01 100644
--- a/lockfile.c
+++ b/lockfile.c
@@ -191,7 +191,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 		return lock_file(lk, path, flags);
 
 	if (!random_initialized) {
-		srandom((unsigned int)getpid());
+		srand((unsigned int)getpid());
 		random_initialized = 1;
 	}
 
@@ -218,7 +218,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 
 		backoff_ms = multiplier * INITIAL_BACKOFF_MS;
 		/* back off for between 0.75*backoff_ms and 1.25*backoff_ms */
-		wait_us = (750 + random() % 500) * backoff_ms;
+		wait_us = (750 + rand() % 500) * backoff_ms;
 		sleep_microseconds(wait_us);
 		remaining_us -= wait_us;
 
-- 
2.3.2.245.gb5bf9d3

Re: [PATCH mh/lockfile-retry] lockfile: replace random() by rand()

[Junio C Hamano]

Johannes Sixt <j6t@kdbg.org> writes:

> There you have it: Look the other way for a while, and people start
> using exotic stuff... ;)

Is it exotic to have random/srandom?  Both are in POSIX and 4BSD;
admittedly rand/srand are written down in C89 and later, so they
might be more portable, but I recall the prevailing wisdom is to
favor random over rand for quality of randomness and portability, so
I am wondering if it may be a better approach to keep the code as-is
and do a compat/random.c based on either rand/srand (or use posix
sample implementation [*1*]).


[Reference]

*1* http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html



>
> This is a build breakage of master on Windows. There are also a few
> new test suite failures. On of them is in t1404#2, indicating that
> a DF conflict takes a different error path. I haven't debugged, yet.
> The lock file retry test fails, too. I'll report back as time permits.
>
>  lockfile.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/lockfile.c b/lockfile.c
> index 5a93bc7..ee5cb01 100644
> --- a/lockfile.c
> +++ b/lockfile.c
> @@ -191,7 +191,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
>  		return lock_file(lk, path, flags);
>  
>  	if (!random_initialized) {
> -		srandom((unsigned int)getpid());
> +		srand((unsigned int)getpid());
>  		random_initialized = 1;
>  	}
>  
> @@ -218,7 +218,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
>  
>  		backoff_ms = multiplier * INITIAL_BACKOFF_MS;
>  		/* back off for between 0.75*backoff_ms and 1.25*backoff_ms */
> -		wait_us = (750 + random() % 500) * backoff_ms;
> +		wait_us = (750 + rand() % 500) * backoff_ms;
>  		sleep_microseconds(wait_us);
>  		remaining_us -= wait_us;

Re: [PATCH mh/lockfile-retry] lockfile: replace random() by rand()

[Johannes Sixt]

Am 30.05.2015 um 19:12 schrieb Junio C Hamano:
> Johannes Sixt <j6t@kdbg.org> writes:
>
>> There you have it: Look the other way for a while, and people start
>> using exotic stuff... ;)
>
> Is it exotic to have random/srandom?  Both are in POSIX and 4BSD;
> admittedly rand/srand are written down in C89 and later, so they
> might be more portable, but I recall the prevailing wisdom is to
> favor random over rand for quality of randomness and portability, so
> I am wondering if it may be a better approach to keep the code as-is
> and do a compat/random.c based on either rand/srand (or use posix
> sample implementation [*1*]).

For our purposes here, the linear congruence of rand() is certainly 
sufficient. At this time, compatibility functions for random/srandom 
would just mean a lot of work for little gain.

>
>
> [Reference]
>
> *1* http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html
>
>
>
>>
>> This is a build breakage of master on Windows. There are also a few
>> new test suite failures. On of them is in t1404#2, indicating that
>> a DF conflict takes a different error path. I haven't debugged, yet.
>> The lock file retry test fails, too. I'll report back as time permits.
>>
>>   lockfile.c | 4 ++--
>>   1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/lockfile.c b/lockfile.c
>> index 5a93bc7..ee5cb01 100644
>> --- a/lockfile.c
>> +++ b/lockfile.c
>> @@ -191,7 +191,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
>>   		return lock_file(lk, path, flags);
>>
>>   	if (!random_initialized) {
>> -		srandom((unsigned int)getpid());
>> +		srand((unsigned int)getpid());
>>   		random_initialized = 1;
>>   	}
>>
>> @@ -218,7 +218,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
>>
>>   		backoff_ms = multiplier * INITIAL_BACKOFF_MS;
>>   		/* back off for between 0.75*backoff_ms and 1.25*backoff_ms */
>> -		wait_us = (750 + random() % 500) * backoff_ms;
>> +		wait_us = (750 + rand() % 500) * backoff_ms;
>>   		sleep_microseconds(wait_us);
>>   		remaining_us -= wait_us;
>

-- Hannes

Re: [PATCH mh/lockfile-retry] lockfile: replace random() by rand()

[Michael Haggerty]

On 06/04/2015 10:40 AM, Johannes Sixt wrote:
> Am 30.05.2015 um 19:12 schrieb Junio C Hamano:
>> Johannes Sixt <j6t@kdbg.org> writes:
>>
>>> There you have it: Look the other way for a while, and people start
>>> using exotic stuff... ;)
>>
>> Is it exotic to have random/srandom?  Both are in POSIX and 4BSD;
>> admittedly rand/srand are written down in C89 and later, so they
>> might be more portable, but I recall the prevailing wisdom is to
>> favor random over rand for quality of randomness and portability, so
>> I am wondering if it may be a better approach to keep the code as-is
>> and do a compat/random.c based on either rand/srand (or use posix
>> sample implementation [*1*]).
> 
> For our purposes here, the linear congruence of rand() is certainly
> sufficient. At this time, compatibility functions for random/srandom
> would just mean a lot of work for little gain.

We *certainly* don't require high-quality random numbers for this
application. Regarding portability, there is one definite point in favor
of rand() (it's available on Windows) vs. Junio's recollection that
random() might have portability advantages, presumably on other platforms.

Maybe the easiest thing would be to switch to using rand() and see if
the OS/2 and VMS users complain ;-)

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu

Re: [PATCH mh/lockfile-retry] lockfile: replace random() by rand()

[Junio C Hamano]

On Thu, Jun 4, 2015 at 4:42 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> On 06/04/2015 10:40 AM, Johannes Sixt wrote:
> We *certainly* don't require high-quality random numbers for this
> application. Regarding portability, there is one definite point in favor
> of rand() (it's available on Windows) vs. Junio's recollection that
> random() might have portability advantages, presumably on other platforms.

I agree that anything is OK in this codepath. I just suspected that whichever
one we pick, there would be somebody who says "oh, my system lacks it",
and we will end up adding one of compat/{rand,random}.c to emulate.

And when I anticipated that future, my inclination was to prefer random(),
not rand(), used in the code, not the other way around. Yes, both are in
POSIX, but I was getting the impression that rand() is on its way out
(and rand_r() is already marked as obsolete).

> Maybe the easiest thing would be to switch to using rand() and see if
> the OS/2 and VMS users complain ;-)

We can certainly go that route and I am fine with that as the solution for
today, as long as somebody will remember this discussion when that
complaint comes, and make compat/random.c, and switch the
in-code use to random(), instead of sticking to use of rand() in code.

[PATCH 0/4] Fix file locking with retry and timeout on Windows

[Johannes Sixt]

The first patch is the same that I posted earlier. It fixes a build
failure on Windows on master due to missing random/srandom.

The remaining 3 patches replace the select() invocation that waits
for a short time period by the version with poll() that we already
use in help.c. This is necessary because a select() call where all
three sets of file descriptors are empty is not supported on Windows.

Johannes Sixt (4):
  lockfile: replace random() by rand()
  help.c: wrap wait-only poll() invocation in sleep_millisec()
  lockfile: convert retry timeout computations to millisecond
  lockfile: wait using sleep_millisec() instead of select()

 cache.h    |  1 +
 help.c     |  2 +-
 lockfile.c | 31 +++++++++----------------------
 wrapper.c  |  5 +++++
 4 files changed, 16 insertions(+), 23 deletions(-)

-- 
2.3.2.245.gb5bf9d3

[PATCH 1/4] lockfile: replace random() by rand()

[Johannes Sixt]

On Windows, we do not have functions srandom() and random(). Use srand()
and rand(). These functions produce random numbers of lesser quality,
but for the purpose (a retry time-out) they are still good enough.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
 This is the same version I posted earlier.

 lockfile.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lockfile.c b/lockfile.c
index 30e65e9..738f202 100644
--- a/lockfile.c
+++ b/lockfile.c
@@ -191,7 +191,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 		return lock_file(lk, path, flags);
 
 	if (!random_initialized) {
-		srandom((unsigned int)getpid());
+		srand((unsigned int)getpid());
 		random_initialized = 1;
 	}
 
@@ -218,7 +218,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 
 		backoff_ms = multiplier * INITIAL_BACKOFF_MS;
 		/* back off for between 0.75*backoff_ms and 1.25*backoff_ms */
-		wait_us = (750 + random() % 500) * backoff_ms;
+		wait_us = (750 + rand() % 500) * backoff_ms;
 		sleep_microseconds(wait_us);
 		remaining_us -= wait_us;
 
-- 
2.3.2.245.gb5bf9d3

[PATCH 2/4] help.c: wrap wait-only poll() invocation in sleep_millisec()

[Johannes Sixt]

We want to use the new function elsewhere in a moment.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
 cache.h   | 1 +
 help.c    | 2 +-
 wrapper.c | 5 +++++
 3 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/cache.h b/cache.h
index 54f108a..328cdb7 100644
--- a/cache.h
+++ b/cache.h
@@ -1680,5 +1680,6 @@ int stat_validity_check(struct stat_validity *sv, const char *path);
 void stat_validity_update(struct stat_validity *sv, int fd);
 
 int versioncmp(const char *s1, const char *s2);
+void sleep_millisec(int millisec);
 
 #endif /* CACHE_H */
diff --git a/help.c b/help.c
index 2072a87..de1279b 100644
--- a/help.c
+++ b/help.c
@@ -372,7 +372,7 @@ const char *help_unknown_cmd(const char *cmd)
 		if (autocorrect > 0) {
 			fprintf_ln(stderr, _("in %0.1f seconds automatically..."),
 				(float)autocorrect/10.0);
-			poll(NULL, 0, autocorrect * 100);
+			sleep_millisec(autocorrect * 100);
 		}
 		return assumed;
 	}
diff --git a/wrapper.c b/wrapper.c
index c1a663f..ff49807 100644
--- a/wrapper.c
+++ b/wrapper.c
@@ -595,3 +595,8 @@ int write_file(const char *path, int fatal, const char *fmt, ...)
 	}
 	return 0;
 }
+
+void sleep_millisec(int millisec)
+{
+	poll(NULL, 0, millisec);
+}
-- 
2.3.2.245.gb5bf9d3

[PATCH 3/4] lockfile: convert retry timeout computations to millisecond

[Johannes Sixt]

When the goal is to wait for some random amount of time up to one
second, it is not necessary to compute with microsecond precision.
This is a preparation to re-use sleep_millisec().

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
 lockfile.c | 21 ++++++++-------------
 1 file changed, 8 insertions(+), 13 deletions(-)

diff --git a/lockfile.c b/lockfile.c
index 738f202..3f5b699 100644
--- a/lockfile.c
+++ b/lockfile.c
@@ -184,7 +184,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 {
 	int n = 1;
 	int multiplier = 1;
-	long remaining_us = 0;
+	long remaining_ms = 0;
 	static int random_initialized = 0;
 
 	if (timeout_ms == 0)
@@ -195,16 +195,11 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 		random_initialized = 1;
 	}
 
-	if (timeout_ms > 0) {
-		/* avoid overflow */
-		if (timeout_ms <= LONG_MAX / 1000)
-			remaining_us = timeout_ms * 1000;
-		else
-			remaining_us = LONG_MAX;
-	}
+	if (timeout_ms > 0)
+		remaining_ms = timeout_ms;
 
 	while (1) {
-		long backoff_ms, wait_us;
+		long backoff_ms, wait_ms;
 		int fd;
 
 		fd = lock_file(lk, path, flags);
@@ -213,14 +208,14 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 			return fd; /* success */
 		else if (errno != EEXIST)
 			return -1; /* failure other than lock held */
-		else if (timeout_ms > 0 && remaining_us <= 0)
+		else if (timeout_ms > 0 && remaining_ms <= 0)
 			return -1; /* failure due to timeout */
 
 		backoff_ms = multiplier * INITIAL_BACKOFF_MS;
 		/* back off for between 0.75*backoff_ms and 1.25*backoff_ms */
-		wait_us = (750 + rand() % 500) * backoff_ms;
-		sleep_microseconds(wait_us);
-		remaining_us -= wait_us;
+		wait_ms = (750 + rand() % 500) * backoff_ms / 1000;
+		sleep_microseconds(wait_ms*1000);
+		remaining_ms -= wait_ms;
 
 		/* Recursion: (n+1)^2 = n^2 + 2n + 1 */
 		multiplier += 2*n + 1;
-- 
2.3.2.245.gb5bf9d3

[PATCH 4/4] lockfile: wait using sleep_millisec() instead of select()

[Johannes Sixt]

Use the new function sleep_millisec() to delay execution for a short
time. This avoids the invocation of select() with just a timeout, but
no file descriptors. Such a use of select() is quit with EINVAL on
Windows, leading to no delay at all.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
 lockfile.c | 10 +---------
 1 file changed, 1 insertion(+), 9 deletions(-)

diff --git a/lockfile.c b/lockfile.c
index 3f5b699..fb78bda 100644
--- a/lockfile.c
+++ b/lockfile.c
@@ -157,14 +157,6 @@ static int lock_file(struct lock_file *lk, const char *path, int flags)
 	return lk->fd;
 }
 
-static int sleep_microseconds(long us)
-{
-	struct timeval tv;
-	tv.tv_sec = 0;
-	tv.tv_usec = us;
-	return select(0, NULL, NULL, NULL, &tv);
-}
-
 /*
  * Constants defining the gaps between attempts to lock a file. The
  * first backoff period is approximately INITIAL_BACKOFF_MS
@@ -214,7 +206,7 @@ static int lock_file_timeout(struct lock_file *lk, const char *path,
 		backoff_ms = multiplier * INITIAL_BACKOFF_MS;
 		/* back off for between 0.75*backoff_ms and 1.25*backoff_ms */
 		wait_ms = (750 + rand() % 500) * backoff_ms / 1000;
-		sleep_microseconds(wait_ms*1000);
+		sleep_millisec(wait_ms);
 		remaining_ms -= wait_ms;
 
 		/* Recursion: (n+1)^2 = n^2 + 2n + 1 */
-- 
2.3.2.245.gb5bf9d3

Re: [PATCH 0/4] Fix file locking with retry and timeout on Windows

[Junio C Hamano]

Johannes Sixt <j6t@kdbg.org> writes:

> The remaining 3 patches replace the select() invocation that waits
> for a short time period by the version with poll() that we already
> use in help.c. This is necessary because a select() call where all
> three sets of file descriptors are empty is not supported on Windows.

Thanks.

The use of both select() and poll() in our code has been bugging me
for a long time (but wasn't irritating enough to make me do anything
about it).

>
> Johannes Sixt (4):
>   lockfile: replace random() by rand()
>   help.c: wrap wait-only poll() invocation in sleep_millisec()
>   lockfile: convert retry timeout computations to millisecond
>   lockfile: wait using sleep_millisec() instead of select()
>
>  cache.h    |  1 +
>  help.c     |  2 +-
>  lockfile.c | 31 +++++++++----------------------
>  wrapper.c  |  5 +++++
>  4 files changed, 16 insertions(+), 23 deletions(-)

Re: [PATCH 0/4] Fix file locking with retry and timeout on Windows

[Michael Haggerty]

On 06/05/2015 09:45 PM, Johannes Sixt wrote:
> The first patch is the same that I posted earlier. It fixes a build
> failure on Windows on master due to missing random/srandom.
> 
> The remaining 3 patches replace the select() invocation that waits
> for a short time period by the version with poll() that we already
> use in help.c. This is necessary because a select() call where all
> three sets of file descriptors are empty is not supported on Windows.
> 
> Johannes Sixt (4):
>   lockfile: replace random() by rand()
>   help.c: wrap wait-only poll() invocation in sleep_millisec()
>   lockfile: convert retry timeout computations to millisecond
>   lockfile: wait using sleep_millisec() instead of select()
> 
>  cache.h    |  1 +
>  help.c     |  2 +-
>  lockfile.c | 31 +++++++++----------------------
>  wrapper.c  |  5 +++++
>  4 files changed, 16 insertions(+), 23 deletions(-)

The whole series looks good to me. Johannes, thanks for taking care of this.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu