[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnunet-scheme] 163/324: util/time: Add time units and implement bounded
From: |
gnunet |
Subject: |
[gnunet-scheme] 163/324: util/time: Add time units and implement bounded exponential back-off. |
Date: |
Tue, 21 Sep 2021 13:23:23 +0200 |
This is an automated email from the git hooks/post-receive script.
maxime-devos pushed a commit to branch master
in repository gnunet-scheme.
commit 29b659cc79f84840d639f802ad5e361ec2daf79b
Author: Maxime Devos <maximedevos@telenet.be>
AuthorDate: Tue Aug 10 20:35:35 2021 +0200
util/time: Add time units and implement bounded exponential back-off.
* gnu/gnunet/util/time.scm: New module.
* Makefile.am (modules): Add it.
* tests/time.scm: New tests.
* Makefile.am (SCM_TESTS): Add them.
---
Makefile.am | 2 ++
README.org | 2 ++
gnu/gnunet/util/time.scm | 53 +++++++++++++++++++++++++++++++++++
tests/time.scm | 73 ++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 130 insertions(+)
diff --git a/Makefile.am b/Makefile.am
index 8d61084..8a4801c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -58,6 +58,7 @@ modules = \
gnu/gnunet/config/db.scm \
\
gnu/gnunet/util/cmsg.scm \
+ gnu/gnunet/util/time.scm \
gnu/gnunet/icmp/struct.scm \
\
gnu/gnunet/util/struct.scm \
@@ -113,6 +114,7 @@ SCM_TESTS = \
tests/config-expand.scm \
tests/config-db.scm \
tests/netstruct.scm \
+ tests/time.scm \
tests/tokeniser.scm
SCM_TESTS_ENVIRONMENT = \
diff --git a/README.org b/README.org
index 884fd8c..a78b48a 100644
--- a/README.org
+++ b/README.org
@@ -178,6 +178,8 @@
TODO: IP_PKTINFO for interface address, scope ...
TODO: message queue based upon this
TODO: nice abstraction for network errors
+** Relative time manipulation :test:good:
+ + gnu/gnunet/time.scm: Time units and exponential back-off.
* Conventions
** Fibers, capabilities and ambient authority
Modules are expected to use ‘fibers’ for concurrency.
diff --git a/gnu/gnunet/util/time.scm b/gnu/gnunet/util/time.scm
new file mode 100644
index 0000000..92448f6
--- /dev/null
+++ b/gnu/gnunet/util/time.scm
@@ -0,0 +1,53 @@
+;; This file is part of GNUnet.
+;; Copyright (C) 2001-2013, 2018 GNUnet e.V.
+;;
+;; GNUnet is free software: you can redistribute it and/or modify it
+;; under the terms of the GNU Affero General Public License as published
+;; by the Free Software Foundation, either version 3 of the License,
+;; or (at your option) any later version.
+;;
+;; GNUnet 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
+;; Affero General Public License for more details.
+;;
+;; You should have received a copy of the GNU Affero General Public License
+;; along with this program. If not, see <http://www.gnu.org/licenses/>.
+;;
+;; SPDX-License-Identifier: AGPL3.0-or-later
+
+;; C file: util/time.c
+;; Author: Christian Grothoff
+;; Partially adapted to Scheme by Maxime Devos
+;; Synopsis: procedures for handling time and time arithmetic
+
+(define-library (gnu gnunet util time)
+ (export time-unit:zero time-unit:microsecond time-unit:millisecond
+ time-unit:second time-unit:minute time-unit:hour
+ standard-back-off)
+ (import (only (rnrs base)
+ assert integer? exact <= define begin min * max
+ and exact? >= /))
+ (begin
+ (define time-unit:zero 0)
+ (define time-unit:microsecond 1)
+ (define time-unit:millisecond 1000)
+ (define time-unit:second (* 1000 1000))
+ (define time-unit:minute (* 60 time-unit:second))
+ (define time-unit:hour (* 60 time-unit:minute))
+
+ (define (exact-natural? x)
+ (and (integer? x) (exact? x) (>= x 0)))
+
+ ;; Treshold after which exponential backoff should not increase
+ ;; (15 minutes).
+ (define standard-exponential-backoff-treshold
+ (/ time-unit:hour 4))
+
+ (define (standard-back-off relative-time)
+ "Perform our standard exponential back-off calculation, starting at
+1 millisecond and then going by a factor of 2 up unto a maximum of 15 minutes.
+The current backoff time is @var{relative-time}. Initially it is zero."
+ (assert (exact-natural? relative-time))
+ (min standard-exponential-backoff-treshold
+ (* 2 (max time-unit:millisecond relative-time))))))
diff --git a/tests/time.scm b/tests/time.scm
new file mode 100644
index 0000000..9edceeb
--- /dev/null
+++ b/tests/time.scm
@@ -0,0 +1,73 @@
+;; This file is part of scheme-GNUnet, a partial Scheme port of GNUnet.
+;; Copyright (C) 2021 Maxime Devos <maximedevos@telenet.be>
+;;
+;; scheme-GNUnet is free software: you can redistribute it and/or modify it
+;; under the terms of the GNU Affero General Public License as published
+;; by the Free Software Foundation, either version 3 of the License,
+;; or (at your option) any later version.
+;;
+;; scheme-GNUnet 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
+;; Affero General Public License for more details.
+;;
+;; You should have received a copy of the GNU Affero General Public License
+;; along with this program. If not, see <http://www.gnu.org/licenses/>.
+;;
+;; SPDX-License-Identifier: AGPL-3.0-or-later
+(import (gnu gnunet util time)
+ (srfi srfi-26)
+ (srfi srfi-43))
+
+(test-begin "time")
+
+(test-equal "back-off factor correct"
+ 2
+ (/ (standard-back-off (* 2 time-unit:second))
+ (standard-back-off time-unit:second)))
+
+(test-assert "not stuck at zero"
+ (> (standard-back-off 0)))
+
+(define %small-relative-times
+ (list time-unit:millisecond time-unit:second
+ time-unit:minute))
+
+(define %very-small-relative-times
+ (map (cut * <> time-unit:microsecond)
+ '(0 1 2 3 4 #e1e1 #e1e2 #e1e3)))
+
+(test-equal "minimum is 1 milliseconds"
+ (map standard-back-off %very-small-relative-times)
+ (map (const (standard-back-off time-unit:millisecond))
+ %very-small-relative-times))
+
+(test-equal "back-off is (at first) exponential (factor: 2)"
+ (map (cut * 2 <>) %small-relative-times)
+ (map standard-back-off %small-relative-times))
+
+(test-assert "15 minutes is a fixed point"
+ (standard-back-off (* 15 time-unit:minute)))
+
+(define deltas '(1 2 3 #e1e1 #e1e3 #e1e4 #e1e5 #e1e9 #e1e20))
+(test-equal "bounded to 15 minutes"
+ (map (const (* 15 time-unit:minute)) deltas)
+ (map (compose standard-back-off (cut + (* 15 time-unit:minute) <>))
+ deltas))
+
+(define %fractions>=1/2 '(1/2 3/4 5/8 9/16 17/32))
+(test-equal "bounded to 15 minutes (slightly smaller start time)"
+ (map (compose standard-back-off
+ (cut * <> (* 15 time-unit:minute))) %fractions>=1/2)
+ (map (const (* 15 time-unit:minute)) %fractions>=1/2))
+
+(test-error "no inexact numbers"
+ (standard-back-off 0.0))
+
+(test-error "no integers rationals"
+ (standard-back-off 0.0))
+
+(test-error "no strictly negative numbers"
+ (standard-back-off -1))
+
+(test-end "time")
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
- [gnunet-scheme] 153/324: concurrency: repeated-conditions: New module., (continued)
- [gnunet-scheme] 153/324: concurrency: repeated-conditions: New module., gnunet, 2021/09/21
- [gnunet-scheme] 158/324: mq-impl/stream: Add modules and tests to 'Makefile.am'., gnunet, 2021/09/21
- [gnunet-scheme] 167/324: README: Graduate 'Message queues' to :test:good:, gnunet, 2021/09/21
- [gnunet-scheme] 146/324: mq: envelope: Allow testing whether an envelope is cancelled., gnunet, 2021/09/21
- [gnunet-scheme] 173/324: netstruct/procedural: Support IEEE doubles., gnunet, 2021/09/21
- [gnunet-scheme] 164/324: repeated-condition: Make less fragile to SRFI-88., gnunet, 2021/09/21
- [gnunet-scheme] 170/324: bv-slice: Support IEEE doubles., gnunet, 2021/09/21
- [gnunet-scheme] 180/324: doc: Start writing some documentation., gnunet, 2021/09/21
- [gnunet-scheme] 184/324: cmsg: Fix broken tests., gnunet, 2021/09/21
- [gnunet-scheme] 185/324: tests/utils: Use set-value! instead of hashtable-set!., gnunet, 2021/09/21
- [gnunet-scheme] 163/324: util/time: Add time units and implement bounded exponential back-off.,
gnunet <=
- [gnunet-scheme] 169/324: mq-stream: Allow turning ports into message queues., gnunet, 2021/09/21
- [gnunet-scheme] 177/324: nse/client: Implement connecting to the NSE service., gnunet, 2021/09/21
- [gnunet-scheme] 181/324: ROADMAP: Start a TODO list for version 0.1., gnunet, 2021/09/21
- [gnunet-scheme] 183/324: tests/utils: Use a better hash function., gnunet, 2021/09/21
- [gnunet-scheme] 182/324: doc: Document the asynchronuousity of connecting., gnunet, 2021/09/21
- [gnunet-scheme] 189/324: ROADMAP: Mark ‘Document NSE’ as done, gnunet, 2021/09/21
- [gnunet-scheme] 188/324: nse/client: Document the optionality of callbacks., gnunet, 2021/09/21
- [gnunet-scheme] 187/324: doc: Document the ‘network size estimation’ API., gnunet, 2021/09/21
- [gnunet-scheme] 197/324: mq-impl/stream: Stop all fibers when EOF is reached (part 2)., gnunet, 2021/09/21
- [gnunet-scheme] 165/324: mq-impl/stream: Implement connecting to unix sockets., gnunet, 2021/09/21