[Linuxptp-devel] [PATCHv2 0/3] Random PTP timeouts.

[Miroslav Lichvar]

Changes in v2:
- fixed bug with disabled timer when random() returns zero
- changed calculation of the random value

These three patches are related to random PTP timeouts.

Miroslav Lichvar (3):
Add random delay to announce timeout.
Drop tmtab module.
Make random() more random between machines.

clock.c | 4 +++-
makefile | 2 +-
port.c | 42 ++++++++++++++++++++++++++++--------------
port.h | 15 +++++++++++++++
tmtab.c | 54 ------------------------------------------------------
tmtab.h | 56 --------------------------------------------------------
6 files changed, 47 insertions(+), 126 deletions(-)
delete mode 100644 tmtab.c
delete mode 100644 tmtab.h

[Miroslav Lichvar]

Instead of maintaining a table of precalculated values, use the
newly added set_tmo_random() function to set the delay request timeout.
It saves some memory and improves the timeout 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 e2f319d..39c285d 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

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

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..e2f319d 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 + (span_ns * (random() % (1 << 15) + 1) >> 15);
+
+ 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.

[Miroslav Lichvar]

Include also nanoseconds from the current time in the 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);

[Richard Cochran]

Post by Miroslav Lichvar
- fixed bug with disabled timer when random() returns zero
- changed calculation of the random value
These three patches are related to random PTP timeouts.

So I will merge this series, but before the tmtab module goes away I
wanted to document the performance benefit (or lack thereof) of the
tmtab method. I hacked a simple benchmark (see below) and ran it on
three different machines.

** Intel(R) Atom(TM) CPU N570 @ 1.66GHz

old: time 0.083613 sec, 0.000000084 per call
new: time 0.215577 sec, 0.000000216 per call

** Beagle Bone White

old: time 0.301510 sec, 0.000000302 per call
new: time 1.083405 sec, 0.000001083 per call

** Freescale Coldfire MCF5234

old: time 13.481529 sec, 0.000013482 per call
new: time 98.643505 sec, 0.000098644 per call

So the tmtab code is several times faster, but Miroslav's new code is
cleaner, and the absolute cost of one call is reasonable, even on the
slowest machine.

Thanks,
Richard

---
commit 80b1f8fe304addd556db66c4e522189dc4070f4f
Author: Richard Cochran <***@gmail.com>
Date: Thu Nov 21 16:51:13 2013 +0100

hack in some benchmark code.

diff --git a/clock.c b/clock.c
index 74d5c77..f982b1f 100644
--- a/clock.c
+++ b/clock.c
@@ -39,6 +39,11 @@
#include "uds.h"
#include "util.h"

+int phony(struct timespec *ts)
+{
+ return 0;
+}
+
#define CLK_N_PORTS (MAX_PORTS + 1) /* plus one for the UDS interface */
#define N_CLOCK_PFD (N_POLLFD + 1) /* one extra per port, for the fault timer */
#define MAVE_LENGTH 10
diff --git a/port.c b/port.c
index dcd3f00..a463639 100644
--- a/port.c
+++ b/port.c
@@ -251,7 +251,7 @@ int set_tmo_random(int fd, int min, int span, int log_seconds)
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);
+ return phony(&tmo.it_value);
}

static void fc_clear(struct foreign_clock *fc)
diff --git a/port.h b/port.h
index e781f24..3a790ba 100644
--- a/port.h
+++ b/port.h
@@ -221,4 +221,6 @@ enum fault_type last_fault_type(struct port *port);
int fault_interval(struct port *port, enum fault_type ft,
struct fault_interval *i);

+int phony(struct timespec *ts);
+
#endif
diff --git a/ptp4l.c b/ptp4l.c
index c828bb4..f63b398 100644
--- a/ptp4l.c
+++ b/ptp4l.c
@@ -36,6 +36,58 @@
#include "util.h"
#include "version.h"

+#include <sys/time.h>
+#include "tmtab.h"
+#include "port.h"
+#define LOG_MIN_DELAY_REQ_INTERVAL 0
+#define NLOOPS 1000000
+
+static struct timeval t1, t2;
+
+static void b1(void)
+{
+ int i;
+ int index;
+ struct itimerspec tmo = {
+ {0, 0}, {0, 0}
+ };
+ struct tmtab tmtab;
+ tmtab_init(&tmtab, 1 + LOG_MIN_DELAY_REQ_INTERVAL);
+
+ gettimeofday(&t1, NULL);
+ for (i = 0; i < NLOOPS; i++) {
+ index = random() % TMTAB_MAX;
+ tmo.it_value = tmtab.ts[index];
+ phony(&tmo.it_value);
+ }
+ gettimeofday(&t2, NULL);
+}
+
+static void b2(void)
+{
+ int i;
+ gettimeofday(&t1, NULL);
+ for (i = 0; i < NLOOPS; i++) {
+ set_tmo_random(0, 0, 2, LOG_MIN_DELAY_REQ_INTERVAL);
+ }
+ gettimeofday(&t2, NULL);
+}
+
+static int benchmark(void)
+{
+ double interval;
+
+ b1();
+ interval = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) / 1e6;
+ printf("time %f sec, %.9f per call\n", interval, interval / NLOOPS);
+
+ b2();
+ interval = (t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec) / 1e6;
+ printf("time %f sec, %.9f per call\n", interval, interval / NLOOPS);
+
+ return 0;
+}
+
int assume_two_step = 0;

static int running = 1;
@@ -175,6 +227,8 @@ int main(int argc, char *argv[])
struct defaultDS *ds = &cfg_settings.dds.dds;
int phc_index = -1, required_modes = 0;

+return benchmark();
+
if (SIG_ERR == signal(SIGINT, handle_int_quit_term)) {
fprintf(stderr, "cannot handle SIGINT\n");
return -1;

[Miroslav Lichvar]

Post by Richard Cochran
So the tmtab code is several times faster, but Miroslav's new code is
cleaner, and the absolute cost of one call is reasonable, even on the
slowest machine.

Thanks for looking into it, Richard.