Discussion:
[Linuxptp-devel] [PATCH RFC 1/3] Add random delay to announce timeout.
Miroslav Lichvar
2013-10-14 16:09:40 UTC
Permalink
According to 9.2.6.11 of the spec the ANNOUNCE_RECEIPT_TIMEOUT_EXPIRES
timeout in addition to announceReceiptTimeoutInterval includes a random
number up to one announceInterval.

Add a new function for setting random timeout and use it in
port_set_announce_tmo().

Signed-off-by: Miroslav Lichvar <***@redhat.com>
---
port.c | 27 +++++++++++++++++++++++++--
port.h | 15 +++++++++++++++
2 files changed, 40 insertions(+), 2 deletions(-)

diff --git a/port.c b/port.c
index d98bb80..32dc22f 100644
--- a/port.c
+++ b/port.c
@@ -231,6 +231,29 @@ int set_tmo_lin(int fd, int seconds)
return timerfd_settime(fd, 0, &tmo, NULL);
}

+int set_tmo_random(int fd, int min, int span, int log_seconds)
+{
+ uint64_t value_ns, min_ns, span_ns;
+ struct itimerspec tmo = {
+ {0, 0}, {0, 0}
+ };
+
+ if (log_seconds >= 0) {
+ min_ns = min * NS_PER_SEC << log_seconds;
+ span_ns = span * NS_PER_SEC << log_seconds;
+ } else {
+ min_ns = min * NS_PER_SEC >> -log_seconds;
+ span_ns = span * NS_PER_SEC >> -log_seconds;
+ }
+
+ value_ns = min_ns + random() * (span_ns / RAND_MAX + 1) % (span_ns + 1);
+
+ tmo.it_value.tv_sec = value_ns / NS_PER_SEC;
+ tmo.it_value.tv_nsec = value_ns % NS_PER_SEC;
+
+ return timerfd_settime(fd, 0, &tmo, NULL);
+}
+
static void fc_clear(struct foreign_clock *fc)
{
struct ptp_message *m;
@@ -786,8 +809,8 @@ static void port_nrate_initialize(struct port *p)

static int port_set_announce_tmo(struct port *p)
{
- return set_tmo_log(p->fda.fd[FD_ANNOUNCE_TIMER],
- p->announceReceiptTimeout, p->logAnnounceInterval);
+ return set_tmo_random(p->fda.fd[FD_ANNOUNCE_TIMER],
+ p->announceReceiptTimeout, 1, p->logAnnounceInterval);
}

static int port_set_delay_tmo(struct port *p)
diff --git a/port.h b/port.h
index 5fef028..e781f24 100644
--- a/port.h
+++ b/port.h
@@ -174,6 +174,21 @@ enum port_state port_state(struct port *port);
int set_tmo_log(int fd, unsigned int scale, int log_seconds);

/**
+ * Utility function for setting a file descriptor timer.
+ *
+ * This function sets the timer 'fd' to a random value between M * 2^N and
+ * (M + S) * 2^N, where M is the value of the 'min' parameter, S is the value
+ * of the 'span' parameter, and N in the value of the 'log_seconds' parameter.
+ *
+ * @param fd A file descriptor previously opened with timerfd_create(2).
+ * @param min The minimum value for the timer.
+ * @param span The span value for the timer. Must be a positive value.
+ * @param log_seconds The exponential factor for the timer.
+ * @return Zero on success, non-zero otherwise.
+ */
+int set_tmo_random(int fd, int min, int span, int log_seconds);
+
+/**
* Utility function for setting or resetting a file descriptor timer.
*
* This function sets the timer 'fd' to the value of the 'seconds' parameter.
--
1.8.3.1
Miroslav Lichvar
2013-10-14 16:09:41 UTC
Permalink
Instead of maintaining a table of precalculated values, use the
set_tmo_random fuction to set the delay request timeout. It saves
memory and provides better granularity, but has a higher computational
cost. It follows the requirements from section 9.5.11.2 of the spec.

Signed-off-by: Miroslav Lichvar <***@redhat.com>
---
makefile | 2 +-
port.c | 15 +++------------
tmtab.c | 54 ------------------------------------------------------
tmtab.h | 56 --------------------------------------------------------
4 files changed, 4 insertions(+), 123 deletions(-)
delete mode 100644 tmtab.c
delete mode 100644 tmtab.h

diff --git a/makefile b/makefile
index d79a1df..f5fcc7b 100644
--- a/makefile
+++ b/makefile
@@ -33,7 +33,7 @@ CFLAGS = -Wall $(VER) $(INC) $(DEBUG) $(FEAT_CFLAGS) $(EXTRA_CFLAGS)
LDLIBS = -lm -lrt $(EXTRA_LDFLAGS)
PRG = ptp4l pmc phc2sys hwstamp_ctl
OBJ = bmc.o clock.o clockadj.o config.o fault.o fsm.o ptp4l.o mave.o \
- msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o stats.o tlv.o tmtab.o \
+ msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o stats.o tlv.o \
transport.o udp.o udp6.o uds.o util.o version.o

OBJECTS = $(OBJ) hwstamp_ctl.o phc2sys.o pmc.o pmc_common.o sysoff.o
diff --git a/port.c b/port.c
index 32dc22f..51f12f4 100644
--- a/port.c
+++ b/port.c
@@ -32,7 +32,6 @@
#include "print.h"
#include "sk.h"
#include "tlv.h"
-#include "tmtab.h"
#include "tmv.h"
#include "util.h"

@@ -80,7 +79,6 @@ struct port {
UInteger16 delayreq;
UInteger16 sync;
} seqnum;
- struct tmtab tmtab;
tmv_t peer_delay;
struct mave *avg_delay;
int log_sync_interval;
@@ -815,17 +813,13 @@ static int port_set_announce_tmo(struct port *p)

static int port_set_delay_tmo(struct port *p)
{
- struct itimerspec tmo = {
- {0, 0}, {0, 0}
- };
- int index;
if (p->delayMechanism == DM_P2P) {
return set_tmo_log(p->fda.fd[FD_DELAY_TIMER], 1,
p->logMinPdelayReqInterval);
+ } else {
+ return set_tmo_random(p->fda.fd[FD_DELAY_TIMER], 0, 2,
+ p->logMinDelayReqInterval);
}
- index = random() % TMTAB_MAX;
- tmo.it_value = p->tmtab.ts[index];
- return timerfd_settime(p->fda.fd[FD_DELAY_TIMER], 0, &tmo, NULL);
}

static int port_set_manno_tmo(struct port *p)
@@ -1327,8 +1321,6 @@ static int port_initialize(struct port *p)
p->logMinPdelayReqInterval = p->pod.logMinPdelayReqInterval;
p->neighborPropDelayThresh = p->pod.neighborPropDelayThresh;

- tmtab_init(&p->tmtab, 1 + p->logMinDelayReqInterval);
-
for (i = 0; i < N_TIMER_FDS; i++) {
fd[i] = -1;
}
@@ -1534,7 +1526,6 @@ static void process_delay_resp(struct port *p, struct ptp_message *m)
p->logMinDelayReqInterval = rsp->hdr.logMessageInterval;
pr_notice("port %hu: minimum delay request interval 2^%d",
portnum(p), p->logMinDelayReqInterval);
- tmtab_init(&p->tmtab, 1 + p->logMinDelayReqInterval);
}
}

diff --git a/tmtab.c b/tmtab.c
deleted file mode 100644
index 7fa9f50..0000000
--- a/tmtab.c
+++ /dev/null
@@ -1,54 +0,0 @@
-/**
- * @file tmtab.c
- * @note Copyright (C) 2011 Richard Cochran <***@gmail.com>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
- */
-#include "tmtab.h"
-#include "tmv.h"
-
-void tmtab_init(struct tmtab *tt, int log_seconds)
-{
- int i;
- struct timespec incr, ts = {0, 0};
- uint64_t max, min;
-
- if (log_seconds < 0) {
- log_seconds *= -1;
- for (i = 1, max = 500000000ULL; i < log_seconds; i++) {
- max >>= 1;
- }
- } else {
- for (i = 0, max = 1000000000ULL; i < log_seconds; i++) {
- max <<= 1;
- }
- }
-
- min = max / (TMTAB_MAX - 1ULL);
-
- incr.tv_sec = min / 1000000000ULL;
- incr.tv_nsec = min % 1000000000ULL;
-
- for (i = 0; i < TMTAB_MAX; i++) {
- ts.tv_sec += incr.tv_sec;
- ts.tv_nsec += incr.tv_nsec;
- while (ts.tv_nsec >= NS_PER_SEC) {
- ts.tv_nsec -= NS_PER_SEC;
- ts.tv_sec++;
- }
- tt->ts[i] = ts;
- }
-}
-
diff --git a/tmtab.h b/tmtab.h
deleted file mode 100644
index 9b80cc6..0000000
--- a/tmtab.h
+++ /dev/null
@@ -1,56 +0,0 @@
-/**
- * @file tmtab.h
- * @brief Implements a table of time out values.
- * @note Copyright (C) 2011 Richard Cochran <***@gmail.com>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
- */
-#ifndef HAVE_TMTAB_H
-#define HAVE_TMTAB_H
-
-#include <time.h>
-
-/*
- * Let 'D' be the logMinDelayReqInterval
- * and 'S' be the logSyncInterval.
- *
- * The delay request interval ranges from zero to 2^{D+1} seconds.
- * The standard requires that
- *
- * S <= D <= S+5
- *
- * and the timeout granularity not more than 2^{S-4} seconds.
- * Thus, the minimum required number of grains is given by
- *
- * 2^{D+1} / 2^{S-4} = 2^{D-S+5}
- *
- * and finds a minimum of 2^5 and a maximum of 2^10.
- *
- * The timeout table allows for the maximum number of grains required.
- *
- * Note that the table is made to be biased so that when sampling the
- * table randomly, the average delay value will be slightly larger
- * than logMinDelayReqInterval, in order to satisfy the wording of the
- * standard.
- */
-#define TMTAB_MAX 1024
-
-struct tmtab {
- struct timespec ts[TMTAB_MAX];
-};
-
-void tmtab_init(struct tmtab *tt, int log_seconds);
-
-#endif
--
1.8.3.1
Keller, Jacob E
2013-10-14 20:20:13 UTC
Permalink
Post by Miroslav Lichvar
Instead of maintaining a table of precalculated values, use the
set_tmo_random fuction to set the delay request timeout. It saves
memory and provides better granularity, but has a higher computational
cost. It follows the requirements from section 9.5.11.2 of the spec.
I think it makes a lot more sense, I can't imagine the computational
cost here being too much higher.
Post by Miroslav Lichvar
---
makefile | 2 +-
port.c | 15 +++------------
tmtab.c | 54 ------------------------------------------------------
tmtab.h | 56 --------------------------------------------------------
4 files changed, 4 insertions(+), 123 deletions(-)
delete mode 100644 tmtab.c
delete mode 100644 tmtab.h
diff --git a/makefile b/makefile
index d79a1df..f5fcc7b 100644
--- a/makefile
+++ b/makefile
@@ -33,7 +33,7 @@ CFLAGS = -Wall $(VER) $(INC) $(DEBUG) $(FEAT_CFLAGS) $(EXTRA_CFLAGS)
LDLIBS = -lm -lrt $(EXTRA_LDFLAGS)
PRG = ptp4l pmc phc2sys hwstamp_ctl
OBJ = bmc.o clock.o clockadj.o config.o fault.o fsm.o ptp4l.o mave.o \
- msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o stats.o tlv.o tmtab.o \
+ msg.o phc.o pi.o port.o print.o raw.o servo.o sk.o stats.o tlv.o \
transport.o udp.o udp6.o uds.o util.o version.o
OBJECTS = $(OBJ) hwstamp_ctl.o phc2sys.o pmc.o pmc_common.o sysoff.o
diff --git a/port.c b/port.c
index 32dc22f..51f12f4 100644
--- a/port.c
+++ b/port.c
@@ -32,7 +32,6 @@
#include "print.h"
#include "sk.h"
#include "tlv.h"
-#include "tmtab.h"
#include "tmv.h"
#include "util.h"
@@ -80,7 +79,6 @@ struct port {
UInteger16 delayreq;
UInteger16 sync;
} seqnum;
- struct tmtab tmtab;
tmv_t peer_delay;
struct mave *avg_delay;
int log_sync_interval;
@@ -815,17 +813,13 @@ static int port_set_announce_tmo(struct port *p)
static int port_set_delay_tmo(struct port *p)
{
- struct itimerspec tmo = {
- {0, 0}, {0, 0}
- };
- int index;
if (p->delayMechanism == DM_P2P) {
return set_tmo_log(p->fda.fd[FD_DELAY_TIMER], 1,
p->logMinPdelayReqInterval);
+ } else {
+ return set_tmo_random(p->fda.fd[FD_DELAY_TIMER], 0, 2,
+ p->logMinDelayReqInterval);
I think its safe to ignore my comment about renaming set_tmo_log since
now I understand it's used more and ac
Miroslav Lichvar
2013-10-14 16:09:42 UTC
Permalink
Include also nanoseconds from the current time in srandom() call. This
should significantly decrease the chance of two machines using the same
random sequence.

Signed-off-by: Miroslav Lichvar <***@redhat.com>
---
clock.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/clock.c b/clock.c
index 819421e..1ad1d5b 100644
--- a/clock.c
+++ b/clock.c
@@ -574,12 +574,14 @@ struct clock *clock_create(int phc_index, struct interface *iface, int count,
struct clock *c = &the_clock;
char phc[32];
struct interface udsif;
+ struct timespec ts;

memset(&udsif, 0, sizeof(udsif));
snprintf(udsif.name, sizeof(udsif.name), UDS_PATH);
udsif.transport = TRANS_UDS;

- srandom(time(NULL));
+ clock_gettime(CLOCK_REALTIME, &ts);
+ srandom(ts.tv_sec ^ ts.tv_nsec);

if (c->nports)
clock_destroy(c);
--
1.8.3.1
Richard Cochran
2013-10-14 17:31:32 UTC
Permalink
Post by Miroslav Lichvar
According to 9.2.6.11 of the spec the ANNOUNCE_RECEIPT_TIMEOUT_EXPIRES
timeout in addition to announceReceiptTimeoutInterval includes a random
number up to one announceInterval.
So I am not very inclined to take these patches. I mean, this
requirement from the standard is totally useless and pointless.
It has zero impact on the GM election result.

Actually, it is detrimental to the election, since it will cause some
masters to delay their announce messages for no good reason.

[But the third patch is okay.]

Thanks,
Richard
Miroslav Lichvar
2013-10-14 17:49:27 UTC
Permalink
Post by Richard Cochran
Post by Miroslav Lichvar
According to 9.2.6.11 of the spec the ANNOUNCE_RECEIPT_TIMEOUT_EXPIRES
timeout in addition to announceReceiptTimeoutInterval includes a random
number up to one announceInterval.
So I am not very inclined to take these patches. I mean, this
requirement from the standard is totally useless and pointless.
It has zero impact on the GM election result.
Actually, it is detrimental to the election, since it will cause some
masters to delay their announce messages for no good reason.
Maybe its purpose is to decrease the chance of multiple clocks
becoming masters at the same time. But I agree that shouldn't cause
any problems in the network.
Post by Richard Cochran
[But the third patch is okay.]
Would you be interested in a reworked version of the second patch?
8KB/16KB tmtab per port seems wasteful to me.
--
Miroslav Lichvar
Miroslav Lichvar
2013-10-15 09:27:59 UTC
Permalink
Post by Miroslav Lichvar
Post by Richard Cochran
So I am not very inclined to take these patches. I mean, this
requirement from the standard is totally useless and pointless.
It has zero impact on the GM election result.
Actually, it is detrimental to the election, since it will cause some
masters to delay their announce messages for no good reason.
Maybe its purpose is to decrease the chance of multiple clocks
becoming masters at the same time. But I agree that shouldn't cause
any problems in the network.
On second thought, it's probably there to avoid collisions on the
network when a large number of clocks sharing the same communication
path is powered on at the same time. The packets in the network should
be evenly distributed over time.

If the extra second in the delay is a problem, announceReceiptTimeout
can be set to 2.
--
Miroslav Lichvar
Richard Cochran
2013-10-16 11:07:13 UTC
Permalink
Post by Miroslav Lichvar
On second thought, it's probably there to avoid collisions on the
network when a large number of clocks sharing the same communication
path is powered on at the same time. The packets in the network should
be evenly distributed over time.
Yeah, that is probably the reason. Still, I would bet that the
announce messages will be "randomly" distributed over the space of
several milliseconds (at least) due to different network path delays,
local timer resolution, scheduling latency, and so on.

Even if one node should pick the wrong master due to a lost incoming
announce message, it will be corrected at the next announce message.

Thanks,
Richard
Miroslav Lichvar
2013-10-16 12:53:17 UTC
Permalink
Post by Richard Cochran
Post by Miroslav Lichvar
On second thought, it's probably there to avoid collisions on the
network when a large number of clocks sharing the same communication
path is powered on at the same time. The packets in the network should
be evenly distributed over time.
Yeah, that is probably the reason. Still, I would bet that the
announce messages will be "randomly" distributed over the space of
several milliseconds (at least) due to different network path delays,
local timer resolution, scheduling latency, and so on.
To some extent that could be said also for the delay request messages
if their timeout was fixed.
Post by Richard Cochran
Even if one node should pick the wrong master due to a lost incoming
announce message, it will be corrected at the next announce message.
It's not just that. The temporary network congestion might disrupt
other PTP domains or other applications sensitive to network latency.
There could be other systems/PTP implementations running on the
network and the burst in the processing of the announce messages might
not be desired.

I think we should follow that part of the spec. It's not that
expensive and the extra delay can be compensated with configuration.
--
Miroslav Lichvar
Richard Cochran
2013-10-16 11:29:46 UTC
Permalink
Post by Miroslav Lichvar
Would you be interested in a reworked version of the second patch?
8KB/16KB tmtab per port seems wasteful to me.
Maybe...

The reason for the tabular time out thing was to be avoid floating
point math at run time. (Some embedded machines lack a HW FP unit.)

Although I have been a bit lazy in enforcing this (like in stats.c),
the original idea was to offer an alternate pi.c with integer math.

I am not sure whether it is worth it to keep this option alive or
not. I need to think about this some more.

Thanks,
Richard
Miroslav Lichvar
2013-10-22 17:12:57 UTC
Permalink
Post by Richard Cochran
Post by Miroslav Lichvar
Would you be interested in a reworked version of the second patch?
8KB/16KB tmtab per port seems wasteful to me.
Maybe...
The reason for the tabular time out thing was to be avoid floating
point math at run time. (Some embedded machines lack a HW FP unit.)
Although I have been a bit lazy in enforcing this (like in stats.c),
the original idea was to offer an alternate pi.c with integer math.
The function I've proposed as tmtab replacement doesn't use floating
point math. It does use 64-bit integer division, but I doubt it would
make a measurable difference in the overall ptp4l CPU usage. I can try
to optimize it if that's the only blocking issue.
--
Miroslav Lichvar
Richard Cochran
2013-10-23 08:33:23 UTC
Permalink
Post by Miroslav Lichvar
Post by Richard Cochran
Post by Miroslav Lichvar
Would you be interested in a reworked version of the second patch?
8KB/16KB tmtab per port seems wasteful to me.
Maybe...
The reason for the tabular time out thing was to be avoid floating
point math at run time. (Some embedded machines lack a HW FP unit.)
Although I have been a bit lazy in enforcing this (like in stats.c),
the original idea was to offer an alternate pi.c with integer math.
The function I've proposed as tmtab replacement doesn't use floating
point math. It does use 64-bit integer division, but I doubt it would
make a measurable difference in the overall ptp4l CPU usage. I can try
to optimize it if that's the only blocking issue.
Yeah, I just noticed that yesterday when actually reading the
patch. But still, I wonder why you need to have two 64-bit divisions.
I'll comment on the patch itself later, to explain what I mean.

Thanks,
Richard
Keller, Jacob E
2013-10-14 20:17:27 UTC
Permalink
Post by Miroslav Lichvar
According to 9.2.6.11 of the spec the ANNOUNCE_RECEIPT_TIMEOUT_EXPIRES
timeout in addition to announceReceiptTimeoutInterval includes a random
number up to one announceInterval.
It's good to follow spec ofcourse, but any idea what the random timeout
buys us? Just curious.
Post by Miroslav Lichvar
Add a new function for setting random timeout and use it in
port_set_announce_tmo().
---
port.c | 27 +++++++++++++++++++++++++--
port.h | 15 +++++++++++++++
2 files changed, 40 insertions(+), 2 deletions(-)
diff --git a/port.c b/port.c
index d98bb80..32dc22f 100644
--- a/port.c
+++ b/port.c
@@ -231,6 +231,29 @@ int set_tmo_lin(int fd, int seconds)
return timerfd_settime(fd, 0, &tmo, NULL);
}
+int set_tmo_random(int fd, int min, int span, int log_seconds)
+{
Could this be named set_tmo_log_random instead? or something similar
which keeps the "log" portion of the name?
Post by Miroslav Lichvar
+ uint64_t value_ns, min_ns, span_ns;
+ struct itimerspec tmo = {
+ {0, 0}, {0, 0}
+ };
+
+ if (log_seconds >= 0) {
+ min_ns = min * NS_PER_SEC << log_seconds;
+ span_ns = span * NS_PER_SEC << log_seconds;
+ } else {
+ min_ns = min * NS_PER_SEC >> -log_seconds;
+ span_ns = span * NS_PER_SEC >> -log_seconds;
+ }
+
+ value_ns = min_ns + random() * (span_ns / RAND_MAX + 1) % (span_ns + 1);
+
+ tmo.it_value.tv_sec = value_ns / NS_PER_SEC;
+ tmo.it_value.tv_nsec = value_ns % NS_PER_SEC;
+
+ return timerfd_settime(fd, 0, &tmo, NULL);
+}
+
static void fc_clear(struct foreign_clock *fc)
{
struct ptp_message *m;
@@ -786,8 +809,8 @@ static void port_nrate_initialize(struct port *p)
static int port_set_announce_tmo(struct port *p)
{
- return set_tmo_log(p->fda.fd[FD_ANNOUNCE_TIMER],
- p->announceReceiptTimeout, p->logAnnounceInterval);
Curious if we still need the old set_tmo_log function in this case? Why
not just remove it, or modify it directly? Is it used somewhere else
also?
Post by Miroslav Lichvar
+ return set_tmo_random(p->fda.fd[FD_ANNOUNCE_TIMER],
+ p->announceReceiptTimeout, 1, p->logAnnounceInterval);
}
static int port_set_delay_tmo(struct port *p)
diff --git a/port.h b/port.h
index 5fef028..e781f24 100644
--- a/port.h
+++ b/port.h
@@ -174,6 +174,21 @@ enum port_state port_state(struct port *port);
int set_tmo_log(int fd, unsigned int scale, int log_seconds);
/**
+ * Utility function for setting a file descriptor timer.
+ *
+ * This function sets the timer 'fd' to a random value between M * 2^N and
+ * (M + S) * 2^N, where M is the value of the 'min' parameter, S is the value
+ * of the 'span' parameter, and N in the value of the 'log_seconds' parameter.
+ *
+ */
+int set_tmo_random(int fd, int min, int span, int log_seconds);
+
+/**
* Utility function for setting or resetting a file descriptor timer.
*
* This function sets the timer 'fd' to the value of the 'seconds' parameter.
Richard Cochran
2013-10-23 18:59:18 UTC
Permalink
Post by Miroslav Lichvar
+ value_ns = min_ns + random() * (span_ns / RAND_MAX + 1) % (span_ns + 1);
Can you explain this expression to me?

It looks like you are trying to cover two cases:

1. span > RAND_MAX: random() * (span_ns / RAND_MAX + 1)
2. span < RAND_MAX: % (span_ns + 1);

But I am not sure...

Thanks,
Richard
Miroslav Lichvar
2013-10-24 11:16:00 UTC
Permalink
Post by Richard Cochran
Post by Miroslav Lichvar
+ value_ns = min_ns + random() * (span_ns / RAND_MAX + 1) % (span_ns + 1);
Can you explain this expression to me?
1. span > RAND_MAX: random() * (span_ns / RAND_MAX + 1)
2. span < RAND_MAX: % (span_ns + 1);
Yes, that's how I meant it, while allowing arbitrary RAND_MAX.

Maybe it would be better to just assume a minimal RAND_MAX and fix the
granularity (to 15 bits?).

value_ns = min_ns + (span_ns * (random() % (1 << 15)) >> 15);

It's faster, more readable and there is no modulo bias (assuming
RAND_MAX is 2^n - 1).
--
Miroslav Lichvar
Miroslav Lichvar
2013-10-25 08:35:58 UTC
Permalink
Post by Miroslav Lichvar
Maybe it would be better to just assume a minimal RAND_MAX and fix the
granularity (to 15 bits?).
value_ns = min_ns + (span_ns * (random() % (1 << 15)) >> 15);
It's faster, more readable and there is no modulo bias (assuming
RAND_MAX is 2^n - 1).
The test suite fails when the function is used also for the delay
timeout. The problem is that it allows the result to be zero, which
disables the timeout.

This one should be better:

value_ns = min_ns + (span_ns * (random() % (1 << 15) + 1) >> 15);
--
Miroslav Lichvar
Richard Cochran
2013-10-25 10:27:49 UTC
Permalink
Post by Miroslav Lichvar
Post by Miroslav Lichvar
Maybe it would be better to just assume a minimal RAND_MAX and fix the
granularity (to 15 bits?).
value_ns = min_ns + (span_ns * (random() % (1 << 15)) >> 15);
It's faster, more readable and there is no modulo bias (assuming
RAND_MAX is 2^n - 1).
The test suite fails when the function is used also for the delay
timeout. The problem is that it allows the result to be zero, which
disables the timeout.
value_ns = min_ns + (span_ns * (random() % (1 << 15) + 1) >> 15);
I find this way easier to understand than the first version. Why did
you choose 15 bits and not, say 16 + 48 = 64?

Thanks,
Richard
Miroslav Lichvar
2013-10-25 11:03:45 UTC
Permalink
Post by Richard Cochran
Post by Miroslav Lichvar
value_ns = min_ns + (span_ns * (random() % (1 << 15) + 1) >> 15);
I find this way easier to understand than the first version. Why did
you choose 15 bits and not, say 16 + 48 = 64?
Because I don't know what is the smallest RAND_MAX we need to support.
I think I've read somewhere that a C standard requires it to be at
least 15 bits. If we know it will be always larger, we could use 16 or
perhaps even few bits more.

Or we could select from multiple versions with #if RAND_MAX >= x, but
I'm not sure it's worth the trouble.
--
Miroslav Lichvar
Richard Cochran
2013-10-25 11:45:18 UTC
Permalink
Post by Miroslav Lichvar
Post by Richard Cochran
Post by Miroslav Lichvar
value_ns = min_ns + (span_ns * (random() % (1 << 15) + 1) >> 15);
I find this way easier to understand than the first version. Why did
you choose 15 bits and not, say 16 + 48 = 64?
Because I don't know what is the smallest RAND_MAX we need to support.
I think I've read somewhere that a C standard requires it to be at
least 15 bits. If we know it will be always larger, we could use 16 or
perhaps even few bits more.
Or we could select from multiple versions with #if RAND_MAX >= x, but
I'm not sure it's worth the trouble.
Okay, I read that RAND_MAX must be at least 2^15, but glibc has it
defined as 2^31.

Using 15 bits is fine enough, since it allows a timer scheduling
granularity of 30 microseconds.

Thanks,
Richard
Miroslav Lichvar
2013-10-25 12:16:18 UTC
Permalink
Post by Richard Cochran
Post by Miroslav Lichvar
Post by Richard Cochran
I find this way easier to understand than the first version. Why did
you choose 15 bits and not, say 16 + 48 = 64?
Because I don't know what is the smallest RAND_MAX we need to support.
I think I've read somewhere that a C standard requires it to be at
least 15 bits. If we know it will be always larger, we could use 16 or
perhaps even few bits more.
Or we could select from multiple versions with #if RAND_MAX >= x, but
I'm not sure it's worth the trouble.
Okay, I read that RAND_MAX must be at least 2^15, but glibc has it
defined as 2^31.
Using 15 bits is fine enough, since it allows a timer scheduling
granularity of 30 microseconds.
Ok, thanks. I'll resend the series shortly.
--
Miroslav Lichvar
Loading...