threads / patch / 39464

patchlockfile: replace random() by rand()

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

## tl;dr

12 messages between May 30, 2015 and Jun 5, 2015. Diffs are folded; open one to read it.

replies: 11people: 3as markdown or json

Johannes Sixt· May 30, 2015, 06:23 UTC · lore

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(-)
Show changes to lockfile.c +2 −2
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
Junio C Hamano· May 30, 2015, 17:12 UTC · re: Johannes Sixt · lore

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

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
Show 30 quoted lines
>
> 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;
Johannes Sixt· Jun 4, 2015, 08:40 UTC · re: Junio C Hamano · lore

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

Am 30.05.2015 um 19:12 schrieb Junio C Hamano:
Show 12 quoted lines
> 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.

Show 39 quoted lines
>
>
> [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
Michael Haggerty· Jun 4, 2015, 11:42 UTC · re: Johannes Sixt · lore

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

On 06/04/2015 10:40 AM, Johannes Sixt wrote:
Show 17 quoted lines
> 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
Junio C Hamano· Jun 4, 2015, 15:57 UTC · re: Michael Haggerty · lore

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

On Thu, Jun 4, 2015 at 4:42 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
Show 5 quoted lines
> 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.

Johannes Sixt· Jun 5, 2015, 19:45 UTC · re: Johannes Sixt · lore

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

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
Junio C Hamano· Jun 5, 2015, 19:57 UTC · re: Johannes Sixt · lore

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

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).

Show 12 quoted lines
>
> 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(-)
Michael Haggerty· Jun 5, 2015, 20:14 UTC · re: Johannes Sixt · lore

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

On 06/05/2015 09:45 PM, Johannes Sixt wrote:
Show 19 quoted lines
> 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
Johannes Sixt· Jun 5, 2015, 19:45 UTC · re: Johannes Sixt · lore

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

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(-)
Show changes to lockfile.c +2 −2
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
Johannes Sixt· Jun 5, 2015, 19:45 UTC · re: Johannes Sixt · lore

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

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(-)
Show changes to 3 files +7 −1

cache.h, help.c, wrapper.c

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
Johannes Sixt· Jun 5, 2015, 19:45 UTC · re: Johannes Sixt · lore

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

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(-)
Show changes to lockfile.c +8 −13
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
Johannes Sixt· Jun 5, 2015, 19:45 UTC · re: Johannes Sixt · lore

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

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(-)
Show changes to lockfile.c +1 −9
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

← back to recent threads