diff options
113 files changed, 6048 insertions, 409 deletions
diff --git a/.gitignore b/.gitignore index b141e80e89..7900141ceb 100644 --- a/.gitignore +++ b/.gitignore @@ -180,6 +180,7 @@ uptime-*.json /src/test/test-memwipe /src/test/test-ntor-cl /src/test/test-switch-id +/src/test/test-timers /src/test/test_workqueue /src/test/test.exe /src/test/test-slow.exe @@ -188,6 +189,7 @@ uptime-*.json /src/test/test-ntor-cl.exe /src/test/test-memwipe.exe /src/test/test-switch-id.exe +/src/test/test-timers.exe /src/test/test_workqueue.exe /src/test/test_zero_length_keys.sh /src/test/test_ntor.sh @@ -1,3 +1,6 @@ +Changes in version 0.2.9.1-alpha - 2016-??-?? + + Changes in version 0.2.8.2-alpha - 2016-03-28 Tor 0.2.8.2-alpha is the second alpha in its series. It fixes numerous bugs in earlier versions of Tor, including some that prevented diff --git a/Makefile.am b/Makefile.am index cd88264264..13ba00d4b5 100644 --- a/Makefile.am +++ b/Makefile.am @@ -19,9 +19,9 @@ AM_CFLAGS = @TOR_SYSTEMD_CFLAGS@ SHELL = @SHELL@ if COVERAGE_ENABLED -TESTING_TOR_BINARY="$(top_builddir)/src/or/tor-cov" +TESTING_TOR_BINARY=$(top_builddir)/src/or/tor-cov$(EXEEXT) else -TESTING_TOR_BINARY="$(top_builddir)/src/or/tor" +TESTING_TOR_BINARY=$(top_builddir)/src/or/tor$(EXEEXT) endif include src/include.am @@ -93,7 +93,7 @@ need-chutney-path: # Note that test-network requires a copy of Chutney in $CHUTNEY_PATH. # Chutney can be cloned from https://git.torproject.org/chutney.git . -test-network: need-chutney-path all +test-network: need-chutney-path $(TESTING_TOR_BINARY) src/tools/tor-gencert $(top_srcdir)/src/test/test-network.sh $(TEST_NETWORK_FLAGS) # Run all available tests using automake's test-driver @@ -101,7 +101,7 @@ test-network: need-chutney-path all # some IPv6 tests will fail without an IPv6 DNS server (see #16971 and #17011) # only run mixed tests if we have a tor-stable binary # see #17015 for autodetection of different tor versions -test-network-all: need-chutney-path all test-driver +test-network-all: need-chutney-path test-driver $(TESTING_TOR_BINARY) src/tools/tor-gencert mkdir -p $(TEST_NETWORK_ALL_LOG_DIR) @flavors="$(TEST_CHUTNEY_FLAVORS)"; \ if ping6 -q -c 1 -o ::1 >/dev/null 2>&1; then \ @@ -134,11 +134,11 @@ need-stem-path: exit 1; \ fi -test-stem: need-stem-path all - @$(PYTHON) "$$STEM_SOURCE_DIR"/run_tests.py --tor $(TESTING_TOR_BINARY) --all --log notice --target RUN_ALL; +test-stem: need-stem-path $(TESTING_TOR_BINARY) + @$(PYTHON) "$$STEM_SOURCE_DIR"/run_tests.py --tor "$(TESTING_TOR_BINARY)" --all --log notice --target RUN_ALL; -test-stem-full: need-stem-path all - @$(PYTHON) "$$STEM_SOURCE_DIR"/run_tests.py --tor $(TESTING_TOR_BINARY) --all --log notice --target RUN_ALL,ONLINE -v; +test-stem-full: need-stem-path $(TESTING_TOR_BINARY) + @$(PYTHON) "$$STEM_SOURCE_DIR"/run_tests.py --tor "$(TESTING_TOR_BINARY)" --all --log notice --target RUN_ALL,ONLINE -v; test-full: need-stem-path need-chutney-path check test-network test-stem diff --git a/changes/assert_nonfatal b/changes/assert_nonfatal new file mode 100644 index 0000000000..0cbee4419b --- /dev/null +++ b/changes/assert_nonfatal @@ -0,0 +1,5 @@ + o Minor features (safety, debugging): + + * Add a set of macros to check nonfatal assertions, for internal + use. Migrating more of our checks to these should help us avoid + needless crash bugs. Closes ticket 18613. diff --git a/changes/bug13239 b/changes/bug13239 new file mode 100644 index 0000000000..17030c923a --- /dev/null +++ b/changes/bug13239 @@ -0,0 +1,4 @@ + o Minor bugfixes (hidden service client): + - Increase the minimum number of internal circuits we preemptively build + from 2 to 3 so they are available when a client connects to another + onion service. Fixes bug 13239; bugfix on tor-0.1.0.1-rc~460. diff --git a/changes/bug14334 b/changes/bug14334 new file mode 100644 index 0000000000..c53781ecf2 --- /dev/null +++ b/changes/bug14334 @@ -0,0 +1,4 @@ + o Minor bugfixes (guards): + - Don't mark guards as unreachable if connection_connect() fails. That + function fails for local reasons, so it shouldn't reveal anything about + the status of the guard. Fixes bug #14334; bugfix on 0.2.3.10-alpha. diff --git a/changes/bug18240 b/changes/bug18240 new file mode 100644 index 0000000000..6be7ba18de --- /dev/null +++ b/changes/bug18240 @@ -0,0 +1,5 @@ + o Minor bugfixes (build): + - Make the test-stem and test-network targets depend only on the + tor binary to be tested. Previously, they depended on "make all". + Fixes bug 18240; bugfix on 0.2.8.2-alpha. + Based on a patch from "cypherpunks". diff --git a/changes/bug18300 b/changes/bug18300 new file mode 100644 index 0000000000..791752ae0b --- /dev/null +++ b/changes/bug18300 @@ -0,0 +1,3 @@ + o Minor features (logging): + - Provide a more useful warning message when configured with an + invalid Nickname. Closes ticket 18300; patch from "icanhasaccount". diff --git a/changes/bug18815 b/changes/bug18815 new file mode 100644 index 0000000000..cb504b2a8e --- /dev/null +++ b/changes/bug18815 @@ -0,0 +1,3 @@ + o Minor features (performance): + - When fetching a consensus for the first time, use optimistic data. + This saves a round-trip during startup. Closes ticket 18815. diff --git a/changes/bug18889 b/changes/bug18889 new file mode 100644 index 0000000000..45b09921d6 --- /dev/null +++ b/changes/bug18889 @@ -0,0 +1,2 @@ + o Code simplification and refactoring: + - Remove redundant declarations of the MIN macro. Closes ticket 18889. diff --git a/changes/bug18934 b/changes/bug18934 new file mode 100644 index 0000000000..fba703e5a4 --- /dev/null +++ b/changes/bug18934 @@ -0,0 +1,3 @@ + o Minor features (testing): + - Let backtrace tests work correctly under AddressSanitizer. + Fixes part of bug 18934. diff --git a/changes/feature15588 b/changes/feature15588 new file mode 100644 index 0000000000..b5563079e1 --- /dev/null +++ b/changes/feature15588 @@ -0,0 +1,4 @@ + o Minor features (controller): + - Add support for configuring basic client authorization on hidden + services created with the ADD_ONION control command. + Implements ticket 15588. Patch by "special". diff --git a/changes/feature18624 b/changes/feature18624 new file mode 100644 index 0000000000..a3be90f745 --- /dev/null +++ b/changes/feature18624 @@ -0,0 +1,7 @@ + o Minor features: + - Directory authorities now only give the Guard flag to a relay if + they are also giving it the Stable flag. This change allows us to + simplify path selection for clients, and it should have minimal + effect in practice since >99% of Guards already have the Stable + flag. Implements ticket 18624. + diff --git a/changes/feature18685 b/changes/feature18685 new file mode 100644 index 0000000000..bc0d1be8e5 --- /dev/null +++ b/changes/feature18685 @@ -0,0 +1,3 @@ + o Minor features (controller): + - Fire a `STATUS_SERVER` event whenever the hibernation status changes + between "awake"/"soft"/"hard". Closes ticket 18685. diff --git a/changes/feature18760 b/changes/feature18760 new file mode 100644 index 0000000000..e6e8f6aad3 --- /dev/null +++ b/changes/feature18760 @@ -0,0 +1,6 @@ + o Minor features: + - When the directory authorities refuse a bad relay's descriptor, + encourage the relay operator to contact us. Many relay operators + won't notice this line in their logs, but it's a win if even a + few learn why we don't like what their relay was doing. Resolves + ticket 18760. diff --git a/changes/feature18998 b/changes/feature18998 new file mode 100644 index 0000000000..a2679c016c --- /dev/null +++ b/changes/feature18998 @@ -0,0 +1,5 @@ + o Minor features: + - Stop being so strict about the payload length of "rendezvous1" + cells. We used to be locked in to the "tap" handshake length, + and now we can handle better handshakes like "ntor". Resolves + ticket 18998. diff --git a/changes/lcov_excl b/changes/lcov_excl new file mode 100644 index 0000000000..474181cfa3 --- /dev/null +++ b/changes/lcov_excl @@ -0,0 +1,7 @@ + o Minor features (testing): + - Use the lcov convention for marking lines as unreachable, so that + we don't count them when we're generating test coverage data. + Update our coverage tools to understand this convention. + Closes ticket #16792. + + diff --git a/changes/ticket16698 b/changes/ticket16698 new file mode 100644 index 0000000000..5057050c16 --- /dev/null +++ b/changes/ticket16698 @@ -0,0 +1,3 @@ + o Code simplification and refactoring: + - Split the 600-line directory_handle_command_get function into + separate functions for different URL types. Closes ticket 16698. diff --git a/changes/ticket18462 b/changes/ticket18462 new file mode 100644 index 0000000000..04e7e60e0b --- /dev/null +++ b/changes/ticket18462 @@ -0,0 +1,3 @@ + o Code simplification and refactoring: + - Rename tor_dup_addr() to tor_addr_to_str_dup() to avoid confusion. + Closes ticket #18462; patch from "icanhasaccount". diff --git a/changes/timeouts b/changes/timeouts new file mode 100644 index 0000000000..dc8f724974 --- /dev/null +++ b/changes/timeouts @@ -0,0 +1,7 @@ + o Minor features (infrastructure): + - Tor now includes an improved timer backend, so that we can efficiently + support tens or hundreds of thousands of concurrent timers, as will be + needed for some of our planned anti-traffic-analysis work. This code + is based on William Ahern's "timeout.c" project, which implements + a "tickless hierarchical timing wheel". Closes ticket #18365. + diff --git a/configure.ac b/configure.ac index a487948745..bd50577418 100644 --- a/configure.ac +++ b/configure.ac @@ -4,7 +4,7 @@ dnl Copyright (c) 2007-2015, The Tor Project, Inc. dnl See LICENSE for licensing information AC_PREREQ([2.63]) -AC_INIT([tor],[0.2.8.2-alpha-dev]) +AC_INIT([tor],[0.2.9.0-alpha-dev]) AC_CONFIG_SRCDIR([src/or/main.c]) AC_CONFIG_MACRO_DIR([m4]) diff --git a/contrib/win32build/tor-mingw.nsi.in b/contrib/win32build/tor-mingw.nsi.in index 1ddec0e761..47fb7e0cd2 100644 --- a/contrib/win32build/tor-mingw.nsi.in +++ b/contrib/win32build/tor-mingw.nsi.in @@ -8,7 +8,7 @@ !include "LogicLib.nsh" !include "FileFunc.nsh" !insertmacro GetParameters -!define VERSION "0.2.8.2-alpha-dev" +!define VERSION "0.2.9.0-alpha-dev" !define INSTALLER "tor-${VERSION}-win32.exe" !define WEBSITE "https://www.torproject.org/" !define LICENSE "LICENSE" diff --git a/doc/HACKING/ReleasingTor.md b/doc/HACKING/ReleasingTor.md index 2378aef568..5cfd238d02 100644 --- a/doc/HACKING/ReleasingTor.md +++ b/doc/HACKING/ReleasingTor.md @@ -4,13 +4,42 @@ Putting out a new release Here are the steps Roger takes when putting out a new Tor release: +=== 0. Preliminaries + +1. Get at least three of weasel/arma/Sebastian/Sina to put the new + version number in their approved versions list. + + +=== I. Make sure it works + 1. Use it for a while, as a client, as a relay, as a hidden service, and as a directory authority. See if it has any obvious bugs, and resolve those. As applicable, merge the `maint-X` branch into the `release-X` branch. -2. Gather the `changes/*` files into a changelog entry, rewriting many +2. Are all of the jenkins builders happy? See jenkins.torproject.org. + + What about the bsd buildbots? + See http://buildbot.pixelminers.net/builders/ + + What about Coverity Scan? + + Is make check-spaces happy? + + Does 'make distcheck' compain? + + How about 'make test-stem' and 'make test-network'? + + - Are all those tests still happy with --enable-expensive-hardening ? + + Any memory leaks? + + +=== II. Write a changelog. + + +1. Gather the `changes/*` files into a changelog entry, rewriting many of them and reordering to focus on what users and funders would find interesting and understandable. @@ -62,13 +91,13 @@ Here are the steps Roger takes when putting out a new Tor release: 7. Run `./scripts/maint/format_changelog.py` to make it prettier. -3. Compose a short release blurb to highlight the user-facing +2. Compose a short release blurb to highlight the user-facing changes. Insert said release blurb into the ChangeLog stanza. If it's a stable release, add it to the ReleaseNotes file too. If we're adding to a release-0.2.x branch, manually commit the changelogs to the later git branches too. - If you're doing the first stable release in a series, you need to +3. If you're doing the first stable release in a series, you need to create a ReleaseNotes for the series as a whole. To get started there, copy all of the Changelog entries from the series into a new file, and run `./scripts/maint/sortChanges.py` on it. That will @@ -78,7 +107,10 @@ Here are the steps Roger takes when putting out a new Tor release: to start sorting and condensing entries. (Generally, we don't edit the text of existing entries, though.) -4. In `maint-0.2.x`, bump the version number in `configure.ac` and run + +=== III. Making the source release. + +1. In `maint-0.2.x`, bump the version number in `configure.ac` and run `scripts/maint/updateVersions.pl` to update version numbers in other places, and commit. Then merge `maint-0.2.x` into `release-0.2.x`. @@ -86,20 +118,19 @@ Here are the steps Roger takes when putting out a new Tor release: either `make`, or `perl scripts/maint/updateVersions.pl`, depending on your version.) -5. Make distcheck, put the tarball up somewhere, and tell `#tor` about +2. Make distcheck, put the tarball up somewhere, and tell `#tor` about it. Wait a while to see if anybody has problems building it. Try to get Sebastian or somebody to try building it on Windows. -6. Get at least two of weasel/arma/Sebastian to put the new version number - in their approved versions list. +=== IV. Commit, upload, announce -7. Sign the tarball, then sign and push the git tag: +1. Sign the tarball, then sign and push the git tag: gpg -ba <the_tarball> git tag -u <keyid> tor-0.2.x.y-status git push origin tag tor-0.2.x.y-status -8. scp the tarball and its sig to the dist website, i.e. +2. scp the tarball and its sig to the dist website, i.e. `/srv/dist-master.torproject.org/htdocs/` on dist-master. When you want it to go live, you run "static-update-component dist.torproject.org" on dist-master. @@ -110,7 +141,7 @@ Here are the steps Roger takes when putting out a new Tor release: once. Nonetheless, do not call your version "alpha" if it is stable, or people will get confused.) -9. Email the packagers (cc'ing tor-assistants) that a new tarball is up. +3. Email the packagers (cc'ing tor-assistants) that a new tarball is up. The current list of packagers is: - {weasel,gk,mikeperry} at torproject dot org @@ -120,24 +151,29 @@ Here are the steps Roger takes when putting out a new Tor release: - {lfleischer} at archlinux dot org - {tails-dev} at boum dot org -10. Add the version number to Trac. To do this, go to Trac, log in, +4. Add the version number to Trac. To do this, go to Trac, log in, select "Admin" near the top of the screen, then select "Versions" from the menu on the left. At the right, there will be an "Add version" box. By convention, we enter the version in the form "Tor: 0.2.2.23-alpha" (or whatever the version is), and we select the date as the date in the ChangeLog. -11. Forward-port the ChangeLog (and ReleaseNotes if appropriate). - -12. Wait up to a day or two (for a development release), or until most +5. Wait up to a day or two (for a development release), or until most packages are up (for a stable release), and mail the release blurb and changelog to tor-talk or tor-announce. (We might be moving to faster announcements, but don't announce until the website is at least updated.) -13. If it's a stable release, bump the version number in the `maint-x.y.z` + +=== V. Aftermath and cleanup + +1. If it's a stable release, bump the version number in the `maint-x.y.z` branch to "newversion-dev", and do a `merge -s ours` merge to avoid taking that change into master. Do a similar `merge -s theirs` merge to get the change (and only that change) into release. (Some of the build scripts require that maint merge cleanly into release.) + +2. Forward-port the ChangeLog (and ReleaseNotes if appropriate). + + diff --git a/doc/HACKING/WritingTests.md b/doc/HACKING/WritingTests.md index 4e98d3d645..7bcadc6087 100644 --- a/doc/HACKING/WritingTests.md +++ b/doc/HACKING/WritingTests.md @@ -109,6 +109,19 @@ To count new or modified uncovered lines in D2, you can run: ./scripts/test/cov-diff ${D1} ${D2}" | grep '^+ *\#' | wc -l +### Marking lines as unreachable by tests + +You can mark a specific line as unreachable by using the special +string LCOV_EXCL_LINE. You can mark a range of lines as unreachable +with LCOV_EXCL_START... LCOV_EXCL_STOP. Note that older versions of +lcov don't understand these lines. + +You can post-process .gcov files to make these lines 'unreached' by +running ./scripts/test/cov-exclude on them. + +Note: you should never do this unless the line is meant to 100% +unreachable by actual code. + What kinds of test should I write? ---------------------------------- @@ -417,18 +430,50 @@ makefile exports them. Writing integration tests with Stem ----------------------------------- -The 'stem' library includes extensive unit tests for the Tor controller -protocol. - -For more information on writing new tests for stem, have a look around -the `test/*` directory in stem, and find a good example to emulate. You -might want to start with -`https://gitweb.torproject.org/stem.git/tree/test/integ/control/controller.py` -to improve Tor's test coverage. - +The 'stem' library includes extensive tests for the Tor controller protocol. You can run stem tests from tor with `make test-stem`, or see `https://stem.torproject.org/faq.html#how-do-i-run-the-tests`. +To see what tests are available, have a look around the `test/*` directory in +stem. The first thing you'll notice is that there are both `unit` and `integ` +tests. The former are for tests of the facilities provided by stem itself that +can be tested on their own, without the need to hook up a tor process. These +are less relevant, unless you want to develop a new stem feature. The latter, +however, are a very useful tool to write tests for controller features. They +provide a default environment with a connected tor instance that can be +modified and queried. Adding more integration tests is a great way to increase +the test coverage inside Tor, especially for controller features. + +Let's assume you actually want to write a test for a previously untested +controller feature. I'm picking the `exit-policy/*` GETINFO queries. Since +these are a controller feature that we want to write an integration test for, +the right file to modify is +`https://gitweb.torproject.org/stem.git/tree/test/integ/control/controller.py`. + +First off we notice that there is an integration test called +`test_get_exit_policy()` that's already written. This exercises the interaction +of stem's `Controller.get_exit_policy()` method, and is not relevant for our +test since there are no stem methods to make use of all `exit-policy/*` +queries (if there were, likely they'd be tested already. Maybe you want to +write a stem feature, but I chose to just add tests). + +Our test requires a tor controller connection, so we'll use the +`@require_controller` annotation for our `test_exit_policy()` method. We need a +controller instance, which we get from +`test.runner.get_runner().get_tor_controller()`. The attached Tor instance is +configured as a client, but the exit-policy GETINFO queries need a relay to +work, so we have to change the config (using `controller.set_options()`). This +is OK for us to do, we just have to remember to set DisableNetwork so we don't +actually start an exit relay and also to undo the changes we made (by calling +`controller.reset_conf()` at the end of our test). Additionally, we have to +configure a static Address for Tor to use, because it refuses to build a +descriptor when it can't guess a suitable IP address. Unfortunately, these +kinds of tripwires are everywhere. Don't forget to file appropriate tickets if +you notice any strange behaviour that seems totally unreasonable. + +Check out the `test_exit_policy()` function in abovementioned file to see the +final implementation for this test. + System testing with Chutney --------------------------- diff --git a/scripts/test/cov-diff b/scripts/test/cov-diff index 48dbec9d54..7da7f0be9d 100755 --- a/scripts/test/cov-diff +++ b/scripts/test/cov-diff @@ -9,8 +9,8 @@ DIRB="$2" for A in $DIRA/*; do B=$DIRB/`basename $A` - perl -pe 's/^\s*\d+:/ 1:/; s/^([^:]+:)[\d\s]+:/$1/; s/^ *-:(Runs|Programs):.*//;' "$A" > "$A.tmp" - perl -pe 's/^\s*\d+:/ 1:/; s/^([^:]+:)[\d\s]+:/$1/; s/^ *-:(Runs|Programs):.*//;' "$B" > "$B.tmp" + perl -pe 's/^\s*\!*\d+:/ 1:/; s/^([^:]+:)[\d\s]+:/$1/; s/^ *-:(Runs|Programs):.*//;' "$A" > "$A.tmp" + perl -pe 's/^\s*\!*\d+:/ 1:/; s/^([^:]+:)[\d\s]+:/$1/; s/^ *-:(Runs|Programs):.*//;' "$B" > "$B.tmp" diff -u "$A.tmp" "$B.tmp" rm "$A.tmp" "$B.tmp" done diff --git a/scripts/test/cov-exclude b/scripts/test/cov-exclude new file mode 100755 index 0000000000..5117f11ec4 --- /dev/null +++ b/scripts/test/cov-exclude @@ -0,0 +1,28 @@ +#!/usr/bin/perl -p -i + +use warnings; +use strict; +our $excluding; + +# This script is meant to post-process a .gcov file for an input source +# that was annotated with LCOV_EXCL_START, LCOV_EXCL_STOP, and LCOV_EXCL_LINE +# entries. It doesn't understand the LCOV_EXCL_BR* variations. +# +# It replaces unreached reached lines with x:, and reached excluded lines +# with !!!num:. + +BEGIN { our $excluding = 0; } + +if (m/LCOV_EXCL_START/) { + $excluding = 1; +} +if ($excluding and m/LCOV_EXCL_STOP/) { + $excluding = 0; +} + +my $exclude_this = (m/LCOV_EXCL_LINE/); + +if ($excluding or $exclude_this) { + s{^\s*\#\#+:}{ x:}; + s{^ (\s*)(\d+):}{$1!!!$2:}; +} diff --git a/src/common/address.c b/src/common/address.c index 793a40effc..a6e0f3f491 100644 --- a/src/common/address.c +++ b/src/common/address.c @@ -1172,7 +1172,7 @@ tor_addr_hash(const tor_addr_t *addr) /** Return a newly allocated string with a representation of <b>addr</b>. */ char * -tor_dup_addr(const tor_addr_t *addr) +tor_addr_to_str_dup(const tor_addr_t *addr) { char buf[TOR_ADDR_BUF_LEN]; if (tor_addr_to_str(buf, addr, sizeof(buf), 0)) { diff --git a/src/common/address.h b/src/common/address.h index 53712bde02..3de67e1c74 100644 --- a/src/common/address.h +++ b/src/common/address.h @@ -179,7 +179,7 @@ tor_addr_eq_ipv4h(const tor_addr_t *a, uint32_t u) #define TOR_ADDR_BUF_LEN 48 int tor_addr_lookup(const char *name, uint16_t family, tor_addr_t *addr_out); -char *tor_dup_addr(const tor_addr_t *addr) ATTR_MALLOC; +char *tor_addr_to_str_dup(const tor_addr_t *addr) ATTR_MALLOC; /** Wrapper function of fmt_addr_impl(). It does not decorate IPv6 * addresses. */ diff --git a/src/common/compat.h b/src/common/compat.h index 8cf84580c6..b6ee4106db 100644 --- a/src/common/compat.h +++ b/src/common/compat.h @@ -430,7 +430,7 @@ typedef int socklen_t; #ifdef _WIN32 /* XXX Actually, this should arguably be SOCKET; we use intptr_t here so that - * any inadvertant checks for the socket being <= 0 or > 0 will probably + * any inadvertent checks for the socket being <= 0 or > 0 will probably * still work. */ #define tor_socket_t intptr_t #define TOR_SOCKET_T_FORMAT INTPTR_T_FORMAT diff --git a/src/common/crypto.c b/src/common/crypto.c index d2a42698cb..65a575ebea 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -134,7 +134,7 @@ crypto_get_rsa_padding_overhead(int padding) switch (padding) { case RSA_PKCS1_OAEP_PADDING: return PKCS1_OAEP_PADDING_OVERHEAD; - default: tor_assert(0); return -1; + default: tor_assert(0); return -1; // LCOV_EXCL_LINE } } @@ -146,7 +146,7 @@ crypto_get_rsa_padding(int padding) switch (padding) { case PK_PKCS1_OAEP_PADDING: return RSA_PKCS1_OAEP_PADDING; - default: tor_assert(0); return -1; + default: tor_assert(0); return -1; // LCOV_EXCL_LINE } } @@ -1739,8 +1739,8 @@ crypto_digest_algorithm_get_length(digest_algorithm_t alg) case DIGEST_SHA3_512: return DIGEST512_LEN; default: - tor_assert(0); - return 0; /* Unreachable */ + tor_assert(0); // LCOV_EXCL_LINE + return 0; /* Unreachable */ // LCOV_EXCL_LINE } } @@ -1783,8 +1783,8 @@ crypto_digest_alloc_bytes(digest_algorithm_t alg) case DIGEST_SHA3_512: return END_OF_FIELD(d.sha3); default: - tor_assert(0); - return 0; + tor_assert(0); // LCOV_EXCL_LINE + return 0; // LCOV_EXCL_LINE } #undef END_OF_FIELD #undef STRUCT_FIELD_SIZE @@ -1914,6 +1914,7 @@ crypto_digest_get_digest(crypto_digest_t *digest, case DIGEST_SHA512: SHA512_Final(r, &tmpenv.d.sha512); break; +//LCOV_EXCL_START case DIGEST_SHA3_256: /* FALLSTHROUGH */ case DIGEST_SHA3_512: log_warn(LD_BUG, "Handling unexpected algorithm %d", digest->algorithm); @@ -1921,6 +1922,7 @@ crypto_digest_get_digest(crypto_digest_t *digest, default: tor_assert(0); /* Unreachable. */ break; +//LCOV_EXCL_STOP } memcpy(out, r, out_len); memwipe(r, 0, sizeof(r)); @@ -2382,8 +2384,6 @@ tor_check_dh_key(int severity, BIGNUM *bn) return -1; } -#undef MIN -#define MIN(a,b) ((a)<(b)?(a):(b)) /** Given a DH key exchange object, and our peer's value of g^y (as a * <b>pubkey_len</b>-byte value in <b>pubkey</b>) generate * <b>secret_bytes_out</b> bytes of shared key material and write them @@ -2760,10 +2760,12 @@ crypto_strongest_rand(uint8_t *out, size_t out_len) while (out_len) { crypto_rand((char*) inp, DLEN); if (crypto_strongest_rand_raw(inp+DLEN, DLEN) < 0) { + // LCOV_EXCL_START log_err(LD_CRYPTO, "Failed to load strong entropy when generating an " "important key. Exiting."); /* Die with an assertion so we get a stack trace. */ tor_assert(0); + // LCOV_EXCL_STOP } if (out_len >= DLEN) { SHA512(inp, sizeof(inp), out); diff --git a/src/common/crypto_s2k.c b/src/common/crypto_s2k.c index a9140c7553..149c39344c 100644 --- a/src/common/crypto_s2k.c +++ b/src/common/crypto_s2k.c @@ -57,7 +57,8 @@ #define SCRYPT_KEY_LEN 32 /** Given an algorithm ID (one of S2K_TYPE_*), return the length of the - * specifier part of it, without the prefix type byte. */ + * specifier part of it, without the prefix type byte. Return -1 if it is not + * a valid algorithm ID. */ static int secret_to_key_spec_len(uint8_t type) { @@ -86,7 +87,8 @@ secret_to_key_key_len(uint8_t type) case S2K_TYPE_SCRYPT: return DIGEST256_LEN; default: - return -1; + tor_fragile_assert(); // LCOV_EXCL_LINE + return -1; // LCOV_EXCL_LINE } } diff --git a/src/common/handles.h b/src/common/handles.h new file mode 100644 index 0000000000..1ee2322579 --- /dev/null +++ b/src/common/handles.h @@ -0,0 +1,153 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file handles.h + * \brief Macros for C weak-handle implementation. + * + * A 'handle' is a pointer to an object that is allowed to go away while + * the handle stays alive. When you dereference the handle, you might get + * the object, or you might get "NULL". + * + * Use this pattern when an object has a single obvious lifespan, so you don't + * want to use reference counting, but when other objects might need to refer + * to the first object without caring about its lifetime. + * + * To enable a type to have handles, add a HANDLE_ENTRY() field in its + * definition, as in: + * + * struct walrus { + * HANDLE_ENTRY(wlr, walrus); + * // ... + * }; + * + * And invoke HANDLE_DECL(wlr, walrus, [static]) to declare the handle + * manipulation functions (typically in a header): + * + * // opaque handle to walrus. + * typedef struct wlr_handle_t wlr_handle_t; + * + * // make a new handle + * struct wlr_handle_t *wlr_handle_new(struct walrus *); + * + * // release a handle + * void wlr_handle_free(wlr_handle_t *); + * + * // return the pointed-to walrus, or NULL. + * struct walrus *wlr_handle_get(wlr_handle_t *). + * + * // call this function when you're about to free the walrus; + * // it invalidates all handles. (IF YOU DON'T, YOU WILL HAVE + * // DANGLING REFERENCES) + * void wlr_handles_clear(struct walrus *); + * + * Finally, use HANDLE_IMPL() to define the above functions in some + * appropriate C file: HANDLE_IMPL(wlr, walrus, [static]) + * + **/ + +#ifndef TOR_HANDLE_H +#define TOR_HANDLE_H + +#include "orconfig.h" +#include "tor_queue.h" +#include "util.h" + +#define HANDLE_ENTRY(name, structname) \ + struct name ## _handle_head_t *handle_head + +#define HANDLE_DECL(name, structname, linkage) \ + typedef struct name ## _handle_t name ## _handle_t; \ + linkage name ## _handle_t *name ## _handle_new(struct structname *object); \ + linkage void name ## _handle_free(name ## _handle_t *); \ + linkage struct structname *name ## _handle_get(name ## _handle_t *); \ + linkage void name ## _handles_clear(struct structname *object); + +/* + * Implementation notes: there are lots of possible implementations here. We + * could keep a linked list of handles, each with a backpointer to the object, + * and set all of their backpointers to NULL when the object is freed. Or we + * could have the clear function invalidate the object, but not actually let + * the object get freed until the all the handles went away. We could even + * have a hash-table mapping unique identifiers to objects, and have each + * handle be a copy of the unique identifier. (We'll want to build that last + * one eventually if we want cross-process handles.) + * + * But instead we're opting for a single independent 'head' that knows how + * many handles there are, and where the object is (or isn't). This makes + * all of our functions O(1), and most as fast as a single pointer access. + * + * The handles themselves are opaque structures holding a pointer to the head. + * We could instead have each foo_handle_t* be identical to foo_handle_head_t + * *, and save some allocations ... but doing so would make handle leaks + * harder to debug. As it stands, every handle leak is a memory leak, and + * existing memory debugging tools should help with those. We can revisit + * this decision if handles are too slow. + */ + +#define HANDLE_IMPL(name, structname, linkage) \ + /* The 'head' object for a handle-accessible type. This object */ \ + /* persists for as long as the object, or any handles, exist. */ \ + typedef struct name ## _handle_head_t { \ + struct structname *object; /* pointed-to object, or NULL */ \ + unsigned int references; /* number of existing handles */ \ + } name ## _handle_head_t; \ + \ + struct name ## _handle_t { \ + struct name ## _handle_head_t *head; /* reference to the 'head'. */ \ + }; \ + \ + linkage struct name ## _handle_t * \ + name ## _handle_new(struct structname *object) \ + { \ + tor_assert(object); \ + name ## _handle_head_t *head = object->handle_head; \ + if (PREDICT_UNLIKELY(head == NULL)) { \ + head = object->handle_head = tor_malloc_zero(sizeof(*head)); \ + head->object = object; \ + } \ + name ## _handle_t *new_ref = tor_malloc_zero(sizeof(*new_ref)); \ + new_ref->head = head; \ + ++head->references; \ + return new_ref; \ + } \ + \ + linkage void \ + name ## _handle_free(struct name ## _handle_t *ref) \ + { \ + if (! ref) return; \ + name ## _handle_head_t *head = ref->head; \ + tor_assert(head); \ + --head->references; \ + tor_free(ref); \ + if (head->object == NULL && head->references == 0) { \ + tor_free(head); \ + return; \ + } \ + } \ + \ + linkage struct structname * \ + name ## _handle_get(struct name ## _handle_t *ref) \ + { \ + tor_assert(ref); \ + name ## _handle_head_t *head = ref->head; \ + tor_assert(head); \ + return head->object; \ + } \ + \ + linkage void \ + name ## _handles_clear(struct structname *object) \ + { \ + tor_assert(object); \ + name ## _handle_head_t *head = object->handle_head; \ + if (! head) \ + return; \ + object->handle_head = NULL; \ + head->object = NULL; \ + if (head->references == 0) { \ + tor_free(head); \ + } \ + } + +#endif /* TOR_HANDLE_H */ + diff --git a/src/common/include.am b/src/common/include.am index 5afb30da6a..f7c486d24a 100644 --- a/src/common/include.am +++ b/src/common/include.am @@ -67,13 +67,14 @@ LIBOR_A_SOURCES = \ src/common/di_ops.c \ src/common/log.c \ src/common/memarea.c \ + src/common/pubsub.c \ src/common/util.c \ + src/common/util_bug.c \ src/common/util_format.c \ src/common/util_process.c \ src/common/sandbox.c \ src/common/workqueue.c \ src/ext/csiphash.c \ - src/ext/trunnel/trunnel.c \ $(libor_extra_source) \ $(threads_impl_source) \ $(readpassphrase_source) @@ -89,13 +90,14 @@ LIBOR_CRYPTO_A_SOURCES = \ src/common/crypto_format.c \ src/common/torgzip.c \ src/common/tortls.c \ - src/trunnel/pwbox.c \ src/common/crypto_curve25519.c \ src/common/crypto_ed25519.c LIBOR_EVENT_A_SOURCES = \ src/common/compat_libevent.c \ - src/common/procmon.c + src/common/procmon.c \ + src/common/timers.c \ + src/ext/timeouts/timeout.c src_common_libor_a_SOURCES = $(LIBOR_A_SOURCES) src_common_libor_crypto_a_SOURCES = $(LIBOR_CRYPTO_A_SOURCES) @@ -129,16 +131,20 @@ COMMONHEADERS = \ src/common/crypto_pwbox.h \ src/common/crypto_s2k.h \ src/common/di_ops.h \ + src/common/handles.h \ src/common/memarea.h \ src/common/linux_syscalls.inc \ src/common/procmon.h \ + src/common/pubsub.h \ src/common/sandbox.h \ src/common/testsupport.h \ + src/common/timers.h \ src/common/torgzip.h \ src/common/torint.h \ src/common/torlog.h \ src/common/tortls.h \ src/common/util.h \ + src/common/util_bug.h \ src/common/util_format.h \ src/common/util_process.h \ src/common/workqueue.h diff --git a/src/common/memarea.c b/src/common/memarea.c index 0a3fd009b0..61117288c3 100644 --- a/src/common/memarea.c +++ b/src/common/memarea.c @@ -132,7 +132,7 @@ alloc_chunk(size_t sz) /** Release <b>chunk</b> from a memarea. */ static void -chunk_free_unchecked(memarea_chunk_t *chunk) +memarea_chunk_free_unchecked(memarea_chunk_t *chunk) { CHECK_SENTINEL(chunk); tor_free(chunk); @@ -155,7 +155,7 @@ memarea_drop_all(memarea_t *area) memarea_chunk_t *chunk, *next; for (chunk = area->first; chunk; chunk = next) { next = chunk->next_chunk; - chunk_free_unchecked(chunk); + memarea_chunk_free_unchecked(chunk); } area->first = NULL; /*fail fast on */ tor_free(area); @@ -171,7 +171,7 @@ memarea_clear(memarea_t *area) if (area->first->next_chunk) { for (chunk = area->first->next_chunk; chunk; chunk = next) { next = chunk->next_chunk; - chunk_free_unchecked(chunk); + memarea_chunk_free_unchecked(chunk); } area->first->next_chunk = NULL; } diff --git a/src/common/pubsub.c b/src/common/pubsub.c new file mode 100644 index 0000000000..b3faf40e00 --- /dev/null +++ b/src/common/pubsub.c @@ -0,0 +1,129 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file pubsub.c + * + * \brief DOCDOC + */ + +#include "orconfig.h" +#include "pubsub.h" +#include "container.h" + +/** Helper: insert <b>s</b> into <b>topic's</b> list of subscribers, keeping + * them sorted in priority order. */ +static void +subscriber_insert(pubsub_topic_t *topic, pubsub_subscriber_t *s) +{ + int i; + smartlist_t *sl = topic->subscribers; + for (i = 0; i < smartlist_len(sl); ++i) { + pubsub_subscriber_t *other = smartlist_get(sl, i); + if (s->priority < other->priority) { + break; + } + } + smartlist_insert(sl, i, s); +} + +/** + * Add a new subscriber to <b>topic</b>, where (when an event is triggered), + * we'll notify the function <b>fn</b> by passing it <b>subscriber_data</b>. + * Return a handle to the subscribe which can later be passed to + * pubsub_unsubscribe_(). + * + * Functions are called in priority order, from lowest to highest. + * + * See pubsub.h for <b>subscribe_flags</b>. + */ +const pubsub_subscriber_t * +pubsub_subscribe_(pubsub_topic_t *topic, + pubsub_subscriber_fn_t fn, + void *subscriber_data, + unsigned subscribe_flags, + unsigned priority) +{ + tor_assert(! topic->locked); + if (subscribe_flags & SUBSCRIBE_ATSTART) { + tor_assert(topic->n_events_fired == 0); + } + pubsub_subscriber_t *r = tor_malloc_zero(sizeof(*r)); + r->priority = priority; + r->subscriber_flags = subscribe_flags; + r->fn = fn; + r->subscriber_data = subscriber_data; + if (topic->subscribers == NULL) { + topic->subscribers = smartlist_new(); + } + subscriber_insert(topic, r); + return r; +} + +/** + * Remove the subscriber <b>s</b> from <b>topic</b>. After calling this + * function, <b>s</b> may no longer be used. + */ +int +pubsub_unsubscribe_(pubsub_topic_t *topic, + const pubsub_subscriber_t *s) +{ + tor_assert(! topic->locked); + smartlist_t *sl = topic->subscribers; + if (sl == NULL) + return -1; + int i = smartlist_pos(sl, s); + if (i == -1) + return -1; + pubsub_subscriber_t *tmp = smartlist_get(sl, i); + tor_assert(tmp == s); + smartlist_del_keeporder(sl, i); + tor_free(tmp); + return 0; +} + +/** + * For every subscriber s in <b>topic</b>, invoke notify_fn on s and + * event_data. Return 0 if there were no nonzero return values, and -1 if + * there were any. + */ +int +pubsub_notify_(pubsub_topic_t *topic, pubsub_notify_fn_t notify_fn, + void *event_data, unsigned notify_flags) +{ + tor_assert(! topic->locked); + (void) notify_flags; + smartlist_t *sl = topic->subscribers; + int n_bad = 0; + ++topic->n_events_fired; + if (sl == NULL) + return -1; + topic->locked = 1; + SMARTLIST_FOREACH_BEGIN(sl, pubsub_subscriber_t *, s) { + int r = notify_fn(s, event_data); + if (r != 0) + ++n_bad; + } SMARTLIST_FOREACH_END(s); + topic->locked = 0; + return (n_bad == 0) ? 0 : -1; +} + +/** + * Release all storage held by <b>topic</b>. + */ +void +pubsub_clear_(pubsub_topic_t *topic) +{ + tor_assert(! topic->locked); + + smartlist_t *sl = topic->subscribers; + if (sl == NULL) + return; + SMARTLIST_FOREACH_BEGIN(sl, pubsub_subscriber_t *, s) { + tor_free(s); + } SMARTLIST_FOREACH_END(s); + smartlist_free(sl); + topic->subscribers = NULL; + topic->n_events_fired = 0; +} + diff --git a/src/common/pubsub.h b/src/common/pubsub.h new file mode 100644 index 0000000000..09e492ec4f --- /dev/null +++ b/src/common/pubsub.h @@ -0,0 +1,177 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file pubsub.h + * \brief Macros to implement publish/subscribe abstractions. + * + * To use these macros, call DECLARE_PUBSUB_TOPIC() with an identifier to use + * as your topic. Below, I'm going to assume you say DECLARE_PUBSUB_TOPIC(T). + * + * Doing this will declare the following types: + * typedef struct T_event_data_t T_event_data_t; // you define this struct + * typedef struct T_subscriber_data_t T_subscriber_data_t; // this one too. + * typedef struct T_subscriber_t T_subscriber_t; // opaque + * typedef int (*T_subscriber_fn_t)(T_event_data_t*, T_subscriber_data_t*); + * + * and it will declare the following functions: + * const T_subscriber_t *T_subscribe(T_subscriber_fn_t, + * T_subscriber_data_t *, + * unsigned flags, + * unsigned priority); + * int T_unsubscribe(const T_subscriber_t *) + * + * Elsewhere you can say DECLARE_NOTIFY_PUBSUB_TOPIC(static, T), which declares: + * static int T_notify(T_event_data_t *, unsigned notify_flags); + * static void T_clear(void); + * + * And in some C file, you would define these functions with: + * IMPLEMENT_PUBSUB_TOPIC(static, T). + * + * The implementations will be small typesafe wrappers over generic versions + * of the above functions. + * + * To use the typesafe functions, you add any number of subscribers with + * T_subscribe(). Each has an associated function pointer, data pointer, + * and priority. Later, you can invoke T_notify() to declare that the + * event has occurred. Each of the subscribers will be invoked once. + **/ + +#ifndef TOR_PUBSUB_H +#define TOR_PUBSUB_H + +#include "torint.h" + +/** + * Flag for T_subscribe: die with an assertion failure if the event + * have ever been published before. Used when a subscriber must absolutely + * never have missed an event. + */ +#define SUBSCRIBE_ATSTART (1u<<0) + +#define DECLARE_PUBSUB_STRUCT_TYPES(name) \ + /* You define this type. */ \ + typedef struct name ## _event_data_t name ## _event_data_t; \ + /* You define this type. */ \ + typedef struct name ## _subscriber_data_t name ## _subscriber_data_t; + +#define DECLARE_PUBSUB_TOPIC(name) \ + /* This type is opaque. */ \ + typedef struct name ## _subscriber_t name ## _subscriber_t; \ + /* You declare functions matching this type. */ \ + typedef int (*name ## _subscriber_fn_t)( \ + name ## _event_data_t *data, \ + name ## _subscriber_data_t *extra); \ + /* Call this function to subscribe to a topic. */ \ + const name ## _subscriber_t *name ## _subscribe( \ + name##_subscriber_fn_t subscriber, \ + name##_subscriber_data_t *extra_data, \ + unsigned flags, \ + unsigned priority); \ + /* Call this function to unsubscribe from a topic. */ \ + int name ## _unsubscribe(const name##_subscriber_t *s); + +#define DECLARE_NOTIFY_PUBSUB_TOPIC(linkage, name) \ + /* Call this function to notify all subscribers. Flags not yet used. */ \ + linkage int name ## _notify(name ## _event_data_t *data, unsigned flags); \ + /* Call this function to release storage held by the topic. */ \ + linkage void name ## _clear(void); + +/** + * Type used to hold a generic function for a subscriber. + * + * [Yes, it is safe to cast to this, so long as we cast back to the original + * type before calling. From C99: "A pointer to a function of one type may be + * converted to a pointer to a function of another type and back again; the + * result shall compare equal to the original pointer."] +*/ +typedef int (*pubsub_subscriber_fn_t)(void *, void *); + +/** + * Helper type to implement pubsub abstraction. Don't use this directly. + * It represents a subscriber. + */ +typedef struct pubsub_subscriber_t { + /** Function to invoke when the event triggers. */ + pubsub_subscriber_fn_t fn; + /** Data associated with this subscriber. */ + void *subscriber_data; + /** Priority for this subscriber. Low priorities happen first. */ + unsigned priority; + /** Flags set on this subscriber. Not yet used.*/ + unsigned subscriber_flags; +} pubsub_subscriber_t; + +/** + * Helper type to implement pubsub abstraction. Don't use this directly. + * It represents a topic, and keeps a record of subscribers. + */ +typedef struct pubsub_topic_t { + /** List of subscribers to this topic. May be NULL. */ + struct smartlist_t *subscribers; + /** Total number of times that pubsub_notify_() has ever been called on this + * topic. */ + uint64_t n_events_fired; + /** True iff we're running 'notify' on this topic, and shouldn't allow + * any concurrent modifications or events. */ + unsigned locked; +} pubsub_topic_t; + +const pubsub_subscriber_t *pubsub_subscribe_(pubsub_topic_t *topic, + pubsub_subscriber_fn_t fn, + void *subscriber_data, + unsigned subscribe_flags, + unsigned priority); +int pubsub_unsubscribe_(pubsub_topic_t *topic, const pubsub_subscriber_t *sub); +void pubsub_clear_(pubsub_topic_t *topic); +typedef int (*pubsub_notify_fn_t)(pubsub_subscriber_t *subscriber, + void *notify_data); +int pubsub_notify_(pubsub_topic_t *topic, pubsub_notify_fn_t notify_fn, + void *notify_data, unsigned notify_flags); + +#define IMPLEMENT_PUBSUB_TOPIC(notify_linkage, name) \ + static pubsub_topic_t name ## _topic_ = { NULL, 0, 0 }; \ + const name ## _subscriber_t * \ + name ## _subscribe(name##_subscriber_fn_t subscriber, \ + name##_subscriber_data_t *extra_data, \ + unsigned flags, \ + unsigned priority) \ + { \ + const pubsub_subscriber_t *s; \ + s = pubsub_subscribe_(&name##_topic_, \ + (pubsub_subscriber_fn_t)subscriber, \ + extra_data, \ + flags, \ + priority); \ + return (const name##_subscriber_t *)s; \ + } \ + int \ + name ## _unsubscribe(const name##_subscriber_t *subscriber) \ + { \ + return pubsub_unsubscribe_(&name##_topic_, \ + (const pubsub_subscriber_t *)subscriber); \ + } \ + static int \ + name##_call_the_notify_fn_(pubsub_subscriber_t *subscriber, \ + void *notify_data) \ + { \ + name ## _subscriber_fn_t fn; \ + fn = (name ## _subscriber_fn_t) subscriber->fn; \ + return fn(notify_data, subscriber->subscriber_data); \ + } \ + notify_linkage int \ + name ## _notify(name ## _event_data_t *event_data, unsigned flags) \ + { \ + return pubsub_notify_(&name##_topic_, \ + name##_call_the_notify_fn_, \ + event_data, \ + flags); \ + } \ + notify_linkage void \ + name ## _clear(void) \ + { \ + pubsub_clear_(&name##_topic_); \ + } + +#endif /* TOR_PUBSUB_H */ + diff --git a/src/common/timers.c b/src/common/timers.c new file mode 100644 index 0000000000..5d8d1feafd --- /dev/null +++ b/src/common/timers.c @@ -0,0 +1,297 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file timers.c + * \brief Wrapper around William Ahern's fast hierarchical timer wheel + * implementation, to tie it in with a libevent backend. + * + * Only use these functions from the main thread. + * + * The main advantage of tor_timer_t over using libevent's timers is that + * they're way more efficient if we need to have thousands or millions of + * them. For more information, see + * http://www.25thandclement.com/~william/projects/timeout.c.html + * + * Periodic timers are available in the backend, but I've turned them off. + * We can turn them back on if needed. + */ + +/* Notes: + * + * The use of tor_gettimeofday_cached_monotonic() is kind of ugly. It would + * be neat to fix it. + * + * Having a way to free all timers on shutdown would free people from the + * need to track them. Not sure if that's clever though. + * + * In an ideal world, Libevent would just switch to use this backend, and we + * could throw this file away. But even if Libevent does switch, we'll be + * stuck with legacy libevents for some time. + */ + +#include "orconfig.h" + +#include "compat.h" +#include "compat_libevent.h" +#include "timers.h" +#include "torlog.h" +#include "util.h" + +#ifdef HAVE_EVENT2_EVENT_H +#include <event2/event.h> +#else +#include <event.h> +#endif + +struct timeout_cb { + timer_cb_fn_t cb; + void *arg; +}; + +/* + * These definitions are for timeouts.c and timeouts.h. + */ +#ifdef __GNUC__ +/* We're not exposing any of the functions outside this file. */ +#define TIMEOUT_PUBLIC __attribute__((__unused__)) static +#else +/* We're not exposing any of the functions outside this file. */ +#define TIMEOUT_PUBLIC static +#endif +/* We're not using periodic events. */ +#define TIMEOUT_DISABLE_INTERVALS +/* We always know the global_timeouts object, so we don't need each timeout + * to keep a pointer to it. */ +#define TIMEOUT_DISABLE_RELATIVE_ACCESS +/* We're providing our own struct timeout_cb. */ +#define TIMEOUT_CB_OVERRIDE +/* We're going to support timers that are pretty far out in advance. Making + * this big can be inefficient, but having a significant number of timers + * above TIMEOUT_MAX can also be super-inefficent. Choosing 5 here sets + * timeout_max to 2^30 ticks, or 29 hours with our value for USEC_PER_TICK */ +#define WHEEL_NUM 5 +#include "src/ext/timeouts/timeout.c" + +static struct timeouts *global_timeouts = NULL; +static struct event *global_timer_event = NULL; + +/** We need to choose this value carefully. Because we're using timer wheels, + * it actually costs us to have extra resolution we don't use. So for now, + * I'm going to define our resolution as .1 msec, and hope that's good enough. + * + * Note that two of the most popular libevent backends (epoll without timerfd, + * and windows select), simply can't support sub-millisecond resolution, + * do this is optimistic for a lot of users. + */ +#define USEC_PER_TICK 100 + +/** One million microseconds in a second */ +#define USEC_PER_SEC 1000000 + +/** Check at least once every N seconds. */ +#define MIN_CHECK_SECONDS 3600 + +/** Check at least once every N ticks. */ +#define MIN_CHECK_TICKS \ + (((timeout_t)MIN_CHECK_SECONDS) * (1000000 / USEC_PER_TICK)) + +/** + * Convert the timeval in <b>tv</b> to a timeout_t, and return it. + * + * The output resolution is set by USEC_PER_TICK, and the time corresponding + * to 0 is the same as the time corresponding to 0 from + * tor_gettimeofday_cached_monotonic(). + */ +static timeout_t +tv_to_timeout(const struct timeval *tv) +{ + uint64_t usec = tv->tv_usec; + usec += ((uint64_t)USEC_PER_SEC) * tv->tv_sec; + return usec / USEC_PER_TICK; +} + +/** + * Convert the timeout in <b>t</b> to a timeval in <b>tv_out</b> + */ +static void +timeout_to_tv(timeout_t t, struct timeval *tv_out) +{ + t *= USEC_PER_TICK; + tv_out->tv_usec = (int)(t % USEC_PER_SEC); + tv_out->tv_sec = (time_t)(t / USEC_PER_SEC); +} + +/** + * Update the timer <b>tv</b> to the current time in <b>tv</b>. + */ +static void +timer_advance_to_cur_time(const struct timeval *tv) +{ + timeout_t cur_tick = tv_to_timeout(tv); + if (BUG(cur_tick < timeouts_get_curtime(global_timeouts))) { + cur_tick = timeouts_get_curtime(global_timeouts); // LCOV_EXCL_LINE + } + timeouts_update(global_timeouts, cur_tick); +} + +/** + * Adjust the time at which the libevent timer should fire based on + * the next-expiring time in <b>global_timeouts</b> + */ +static void +libevent_timer_reschedule(void) +{ + struct timeval now; + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + timeout_t delay = timeouts_timeout(global_timeouts); + struct timeval d; + if (delay > MIN_CHECK_TICKS) + delay = MIN_CHECK_TICKS; + timeout_to_tv(delay, &d); + event_add(global_timer_event, &d); +} + +/** + * Invoked when the libevent timer has expired: see which tor_timer_t events + * have fired, activate their callbacks, and reschedule the libevent timer. + */ +static void +libevent_timer_callback(evutil_socket_t fd, short what, void *arg) +{ + (void)fd; + (void)what; + (void)arg; + + struct timeval now; + tor_gettimeofday_cache_clear(); + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + tor_timer_t *t; + while ((t = timeouts_get(global_timeouts))) { + t->callback.cb(t, t->callback.arg, &now); + } + + tor_gettimeofday_cache_clear(); + libevent_timer_reschedule(); +} + +/** + * Initialize the timers subsystem. Requires that libevent has already been + * initialized. + */ +void +timers_initialize(void) +{ + if (BUG(global_timeouts)) + return; // LCOV_EXCL_LINE + + timeout_error_t err; + global_timeouts = timeouts_open(0, &err); + if (!global_timeouts) { + // LCOV_EXCL_START -- this can only fail on malloc failure. + log_err(LD_BUG, "Unable to open timer backend: %s", strerror(err)); + tor_assert(0); + // LCOV_EXCL_STOP + } + + struct event *timer_event; + timer_event = tor_event_new(tor_libevent_get_base(), + -1, 0, libevent_timer_callback, NULL); + tor_assert(timer_event); + global_timer_event = timer_event; + + libevent_timer_reschedule(); +} + +/** + * Release all storage held in the timers subsystem. Does not fire timers. + */ +void +timers_shutdown(void) +{ + if (global_timer_event) { + tor_event_free(global_timer_event); + global_timer_event = NULL; + } + if (global_timeouts) { + timeouts_close(global_timeouts); + global_timeouts = NULL; + } +} + +/** + * Allocate and return a new timer, with given callback and argument. + */ +tor_timer_t * +timer_new(timer_cb_fn_t cb, void *arg) +{ + tor_timer_t *t = tor_malloc(sizeof(tor_timer_t)); + timeout_init(t, 0); + timer_set_cb(t, cb, arg); + return t; +} + +/** + * Release all storage held by <b>t</b>, and unschedule it if was already + * scheduled. + */ +void +timer_free(tor_timer_t *t) +{ + if (! t) + return; + + timeouts_del(global_timeouts, t); + tor_free(t); +} + +/** + * Change the callback and argument associated with a timer <b>t</b>. + */ +void +timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg) +{ + t->callback.cb = cb; + t->callback.arg = arg; +} + +/** + * Schedule the timer t to fire at the current time plus a delay of <b>tv</b>. + * All times are relative to tor_gettimeofday_cached_monotonic. + */ +void +timer_schedule(tor_timer_t *t, const struct timeval *tv) +{ + const timeout_t when = tv_to_timeout(tv); + struct timeval now; + tor_gettimeofday_cached_monotonic(&now); + timer_advance_to_cur_time(&now); + + /* Take the old timeout value. */ + timeout_t to = timeouts_timeout(global_timeouts); + + timeouts_add(global_timeouts, t, when); + + /* Should we update the libevent timer? */ + if (to <= when) { + return; /* we're already going to fire before this timer would trigger. */ + } + libevent_timer_reschedule(); +} + +/** + * Cancel the timer <b>t</b> if it is currently scheduled. (It's okay to call + * this on an unscheduled timer. + */ +void +timer_disable(tor_timer_t *t) +{ + timeouts_del(global_timeouts, t); + /* We don't reschedule the libevent timer here, since it's okay if it fires + * early. */ +} + diff --git a/src/common/timers.h b/src/common/timers.h new file mode 100644 index 0000000000..594cf38a64 --- /dev/null +++ b/src/common/timers.h @@ -0,0 +1,22 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_TIMERS_H +#define TOR_TIMERS_H + +#include "orconfig.h" +#include "testsupport.h" + +typedef struct timeout tor_timer_t; +typedef void (*timer_cb_fn_t)(tor_timer_t *, void *, const struct timeval *); +tor_timer_t *timer_new(timer_cb_fn_t cb, void *arg); +void timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg); +void timer_schedule(tor_timer_t *t, const struct timeval *delay); +void timer_disable(tor_timer_t *t); +void timer_free(tor_timer_t *t); + +void timers_initialize(void); +void timers_shutdown(void); + +#endif + diff --git a/src/common/util.c b/src/common/util.c index 008c682b3b..fa2953cc30 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -105,23 +105,6 @@ #endif /* ===== - * Assertion helper. - * ===== */ -/** Helper for tor_assert: report the assertion failure. */ -void -tor_assertion_failed_(const char *fname, unsigned int line, - const char *func, const char *expr) -{ - char buf[256]; - log_err(LD_BUG, "%s:%u: %s: Assertion %s failed; aborting.", - fname, line, func, expr); - tor_snprintf(buf, sizeof(buf), - "Assertion %s failed in %s at %s:%u", - expr, func, fname, line); - log_backtrace(LOG_ERR, LD_BUG, buf); -} - -/* ===== * Memory management * ===== */ #ifdef USE_DMALLOC diff --git a/src/common/util.h b/src/common/util.h index ebcf88b32d..814c8622a2 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -22,6 +22,7 @@ /* for the correct alias to struct stat */ #include <sys/stat.h> #endif +#include "util_bug.h" #ifndef O_BINARY #define O_BINARY 0 @@ -33,41 +34,6 @@ #define O_NOFOLLOW 0 #endif -/* Replace assert() with a variant that sends failures to the log before - * calling assert() normally. - */ -#ifdef NDEBUG -/* Nobody should ever want to build with NDEBUG set. 99% of our asserts will - * be outside the critical path anyway, so it's silly to disable bug-checking - * throughout the entire program just because a few asserts are slowing you - * down. Profile, optimize the critical path, and keep debugging on. - * - * And I'm not just saying that because some of our asserts check - * security-critical properties. - */ -#error "Sorry; we don't support building with NDEBUG." -#endif - -/* Sometimes we don't want to use assertions during branch coverage tests; it - * leads to tons of unreached branches which in reality are only assertions we - * didn't hit. */ -#if defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) -#define tor_assert(a) STMT_BEGIN \ - (void)(a); \ - STMT_END -#else -/** Like assert(3), but send assertion failures to the log as well as to - * stderr. */ -#define tor_assert(expr) STMT_BEGIN \ - if (PREDICT_UNLIKELY(!(expr))) { \ - tor_assertion_failed_(SHORT_FILE__, __LINE__, __func__, #expr); \ - abort(); \ - } STMT_END -#endif - -void tor_assertion_failed_(const char *fname, unsigned int line, - const char *func, const char *expr); - /* If we're building with dmalloc, we want all of our memory allocation * functions to take an extra file/line pair of arguments. If not, not. * We define DMALLOC_PARAMS to the extra parameters to insert in the @@ -81,11 +47,6 @@ void tor_assertion_failed_(const char *fname, unsigned int line, #define DMALLOC_ARGS #endif -/** Define this if you want Tor to crash when any problem comes up, - * so you can get a coredump and track things down. */ -// #define tor_fragile_assert() tor_assert(0) -#define tor_fragile_assert() - /* Memory management */ void *tor_malloc_(size_t size DMALLOC_PARAMS) ATTR_MALLOC; void *tor_malloc_zero_(size_t size DMALLOC_PARAMS) ATTR_MALLOC; diff --git a/src/common/util_bug.c b/src/common/util_bug.c new file mode 100644 index 0000000000..e3e1d6df90 --- /dev/null +++ b/src/common/util_bug.c @@ -0,0 +1,53 @@ +/* Copyright (c) 2003, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file util_bug.c + **/ + +#include "orconfig.h" +#include "util_bug.h" +#include "torlog.h" +#include "backtrace.h" + +/** Helper for tor_assert: report the assertion failure. */ +void +tor_assertion_failed_(const char *fname, unsigned int line, + const char *func, const char *expr) +{ + char buf[256]; + log_err(LD_BUG, "%s:%u: %s: Assertion %s failed; aborting.", + fname, line, func, expr); + tor_snprintf(buf, sizeof(buf), + "Assertion %s failed in %s at %s:%u", + expr, func, fname, line); + log_backtrace(LOG_ERR, LD_BUG, buf); +} + +/** Helper for tor_assert_nonfatal: report the assertion failure. */ +void +tor_bug_occurred_(const char *fname, unsigned int line, + const char *func, const char *expr, + int once) +{ + char buf[256]; + const char *once_str = once ? + " (Future instances of this warning will be silenced.)": ""; + if (! expr) { + log_warn(LD_BUG, "%s:%u: %s: This line should not have been reached.%s", + fname, line, func, once_str); + tor_snprintf(buf, sizeof(buf), + "Line unexpectedly reached at %s at %s:%u", + func, fname, line); + } else { + log_warn(LD_BUG, "%s:%u: %s: Non-fatal assertion %s failed.%s", + fname, line, func, expr, once_str); + tor_snprintf(buf, sizeof(buf), + "Non-fatal assertion %s failed in %s at %s:%u", + expr, func, fname, line); + } + log_backtrace(LOG_WARN, LD_BUG, buf); +} + diff --git a/src/common/util_bug.h b/src/common/util_bug.h new file mode 100644 index 0000000000..36056aa4bd --- /dev/null +++ b/src/common/util_bug.h @@ -0,0 +1,150 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file util_bug.h + **/ + +#ifndef TOR_UTIL_BUG_H +#define TOR_UTIL_BUG_H + +#include "orconfig.h" +#include "compat.h" +#include "testsupport.h" + +/* Replace assert() with a variant that sends failures to the log before + * calling assert() normally. + */ +#ifdef NDEBUG +/* Nobody should ever want to build with NDEBUG set. 99% of our asserts will + * be outside the critical path anyway, so it's silly to disable bug-checking + * throughout the entire program just because a few asserts are slowing you + * down. Profile, optimize the critical path, and keep debugging on. + * + * And I'm not just saying that because some of our asserts check + * security-critical properties. + */ +#error "Sorry; we don't support building with NDEBUG." +#endif + +/* Sometimes we don't want to use assertions during branch coverage tests; it + * leads to tons of unreached branches which in reality are only assertions we + * didn't hit. */ +#if defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) +#define tor_assert(a) STMT_BEGIN \ + (void)(a); \ + STMT_END +#else +/** Like assert(3), but send assertion failures to the log as well as to + * stderr. */ +#define tor_assert(expr) STMT_BEGIN \ + if (PREDICT_UNLIKELY(!(expr))) { \ + tor_assertion_failed_(SHORT_FILE__, __LINE__, __func__, #expr); \ + abort(); \ + } STMT_END +#endif + +#define tor_assert_unreached() tor_assert(0) + +/* Non-fatal bug assertions. The "unreached" variants mean "this line should + * never be reached." The "once" variants mean "Don't log a warning more than + * once". + * + * The 'BUG' macro checks a boolean condition and logs an error message if it + * is true. Example usage: + * if (BUG(x == NULL)) + * return -1; + */ + +#ifdef ALL_BUGS_ARE_FATAL +#define tor_assert_nonfatal_unreached() tor_assert(0) +#define tor_assert_nonfatal(cond) tor_assert((cond)) +#define tor_assert_nonfatal_unreached_once() tor_assert(0) +#define tor_assert_nonfatal_once(cond) tor_assert((cond)) +#define BUG(cond) \ + (PREDICT_UNLIKELY(cond) ? \ + (tor_assertion_failed_(SHORT_FILE__,__LINE__,__func__,#cond), abort(), 1) \ + : 0) +#elif defined(TOR_UNIT_TESTS) && defined(DISABLE_ASSERTS_IN_UNIT_TESTS) +#define tor_assert_nonfatal_unreached() STMT_NIL +#define tor_assert_nonfatal(cond) ((void)(cond)) +#define tor_assert_nonfatal_unreached_once() STMT_NIL +#define tor_assert_nonfatal_once(cond) ((void)(cond)) +#define BUG(cond) (PREDICT_UNLIKELY(cond) ? 1 : 0) +#else /* Normal case, !ALL_BUGS_ARE_FATAL, !DISABLE_ASSERTS_IN_UNIT_TESTS */ +#define tor_assert_nonfatal_unreached() STMT_BEGIN \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, NULL, 0); \ + STMT_END +#define tor_assert_nonfatal(cond) STMT_BEGIN \ + if (PREDICT_UNLIKELY(!(cond))) { \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 0); \ + } \ + STMT_END +#define tor_assert_nonfatal_unreached_once() STMT_BEGIN \ + static int warning_logged__ = 0; \ + if (!warning_logged__) { \ + warning_logged__ = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, NULL, 1); \ + } \ + STMT_END +#define tor_assert_nonfatal_once(cond) STMT_BEGIN \ + static int warning_logged__ = 0; \ + if (!warning_logged__ && PREDICT_UNLIKELY(!(cond))) { \ + warning_logged__ = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1); \ + } \ + STMT_END +#define BUG(cond) \ + (PREDICT_UNLIKELY(cond) ? \ + (tor_bug_occurred_(SHORT_FILE__,__LINE__,__func__,#cond,0), 1) \ + : 0) +#endif + +#ifdef __GNUC__ +#define IF_BUG_ONCE__(cond,var) \ + if (({ \ + static int var = 0; \ + int bool_result = (cond); \ + if (PREDICT_UNLIKELY(bool_result) && !var) { \ + var = 1; \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1); \ + } \ + PREDICT_UNLIKELY(bool_result); })) +#else +#define IF_BUG_ONCE__(cond,var) \ + static int var = 0; \ + if (PREDICT_UNLIKELY(cond)) ? \ + (var ? 1 : \ + (var=1, \ + tor_bug_occurred_(SHORT_FILE__, __LINE__, __func__, #cond, 1), \ + 1)) \ + : 0) +#endif +#define IF_BUG_ONCE_VARNAME_(a) \ + warning_logged_on_ ## a ## __ +#define IF_BUG_ONCE_VARNAME__(a) \ + IF_BUG_ONCE_VARNAME_(a) + +/** This macro behaves as 'if (bug(x))', except that it only logs its + * warning once, no matter how many times it triggers. + */ + +#define IF_BUG_ONCE(cond) \ + IF_BUG_ONCE__((cond), \ + IF_BUG_ONCE_VARNAME__(__LINE__)) + +/** Define this if you want Tor to crash when any problem comes up, + * so you can get a coredump and track things down. */ +// #define tor_fragile_assert() tor_assert_unreached(0) +#define tor_fragile_assert() tor_assert_nonfatal_unreached_once() + +void tor_assertion_failed_(const char *fname, unsigned int line, + const char *func, const char *expr); +void tor_bug_occurred_(const char *fname, unsigned int line, + const char *func, const char *expr, + int once); + +#endif + diff --git a/src/config/torrc.minimal.in-staging b/src/config/torrc.minimal.in-staging index 248cb5cf02..d4dfd5f6bb 100644 --- a/src/config/torrc.minimal.in-staging +++ b/src/config/torrc.minimal.in-staging @@ -98,6 +98,8 @@ # OutboundBindAddress 10.0.0.5 ## A handle for your relay, so people don't have to refer to it by key. +## Nicknames must be between 1 and 19 characters inclusive, and must +## contain only the characters [a-zA-Z0-9]. #Nickname ididnteditheconfig ## Define these to limit how much relayed traffic you will allow. Your diff --git a/src/config/torrc.sample.in b/src/config/torrc.sample.in index 248cb5cf02..d4dfd5f6bb 100644 --- a/src/config/torrc.sample.in +++ b/src/config/torrc.sample.in @@ -98,6 +98,8 @@ # OutboundBindAddress 10.0.0.5 ## A handle for your relay, so people don't have to refer to it by key. +## Nicknames must be between 1 and 19 characters inclusive, and must +## contain only the characters [a-zA-Z0-9]. #Nickname ididnteditheconfig ## Define these to limit how much relayed traffic you will allow. Your diff --git a/src/ext/README b/src/ext/README index 7ce1bc3b74..c180927b86 100644 --- a/src/ext/README +++ b/src/ext/README @@ -73,3 +73,7 @@ readpassphrase.[ch] Portable readpassphrase implementation from OpenSSH portable, version 6.8p1. + +timeouts/ + + William Ahern's hierarchical timer-wheel implementation. MIT license. diff --git a/src/ext/ed25519/donna/ed25519_tor.c b/src/ext/ed25519/donna/ed25519_tor.c index 52b259dfe1..07f6a0f23a 100644 --- a/src/ext/ed25519/donna/ed25519_tor.c +++ b/src/ext/ed25519/donna/ed25519_tor.c @@ -44,7 +44,8 @@ typedef unsigned char ed25519_signature[64]; typedef unsigned char ed25519_public_key[32]; typedef unsigned char ed25519_secret_key[32]; -static void gettweak(unsigned char *out, const unsigned char *param); +static void ed25519_donna_gettweak(unsigned char *out, + const unsigned char *param); static int ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen, const ed25519_public_key pk, const ed25519_signature RS); @@ -242,7 +243,7 @@ ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen, } static void -gettweak(unsigned char *out, const unsigned char *param) +ed25519_donna_gettweak(unsigned char *out, const unsigned char *param) { static const char str[] = "Derive temporary signing key"; ed25519_hash_context ctx; @@ -266,7 +267,7 @@ ed25519_donna_blind_secret_key(unsigned char *out, const unsigned char *inp, ed25519_hash_context ctx; bignum256modm ALIGN(16) sk, t; - gettweak(tweak, param); + ed25519_donna_gettweak(tweak, param); expand256_modm(t, tweak, 32); expand256_modm(sk, inp, 32); @@ -297,7 +298,7 @@ ed25519_donna_blind_public_key(unsigned char *out, const unsigned char *inp, ge25519 ALIGN(16) A, Aprime; bignum256modm ALIGN(16) t; - gettweak(tweak, param); + ed25519_donna_gettweak(tweak, param); expand256_modm(t, tweak, 32); /* No "ge25519_unpack", negate the public key. */ diff --git a/src/ext/ed25519/ref10/blinding.c b/src/ext/ed25519/ref10/blinding.c index 4d9a9cbbe7..ee3e8666fa 100644 --- a/src/ext/ed25519/ref10/blinding.c +++ b/src/ext/ed25519/ref10/blinding.c @@ -10,7 +10,7 @@ #include "crypto.h" static void -gettweak(unsigned char *out, const unsigned char *param) +ed25519_ref10_gettweak(unsigned char *out, const unsigned char *param) { const char str[] = "Derive temporary signing key"; crypto_hash_sha512_2(out, (const unsigned char*)str, strlen(str), param, 32); @@ -26,7 +26,7 @@ int ed25519_ref10_blind_secret_key(unsigned char *out, const char str[] = "Derive temporary signing key hash input"; unsigned char tweak[64]; unsigned char zero[32]; - gettweak(tweak, param); + ed25519_ref10_gettweak(tweak, param); memset(zero, 0, 32); sc_muladd(out, inp, tweak, zero); @@ -50,7 +50,7 @@ int ed25519_ref10_blind_public_key(unsigned char *out, ge_p3 A; ge_p2 Aprime; - gettweak(tweak, param); + ed25519_ref10_gettweak(tweak, param); memset(zero, 0, sizeof(zero)); /* Not the greatest implementation of all of this. I wish I had diff --git a/src/ext/include.am b/src/ext/include.am index bf678f2c9d..708f550ba0 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -12,7 +12,11 @@ EXTHEADERS = \ src/ext/strlcpy.c \ src/ext/tinytest_macros.h \ src/ext/tor_queue.h \ - src/ext/siphash.h + src/ext/siphash.h \ + src/ext/timeouts/timeout.h \ + src/ext/timeouts/timeout-debug.h \ + src/ext/timeouts/timeout-bitops.c \ + src/ext/timeouts/timeout.c noinst_HEADERS+= $(EXTHEADERS) @@ -148,3 +152,21 @@ noinst_HEADERS += $(LIBKECCAK_TINY_HDRS) LIBKECCAK_TINY=src/ext/keccak-tiny/libkeccak-tiny.a noinst_LIBRARIES += $(LIBKECCAK_TINY) +EXTRA_DIST += \ + src/ext/timeouts/bench/bench-add.lua \ + src/ext/timeouts/bench/bench-aux.lua \ + src/ext/timeouts/bench/bench.c \ + src/ext/timeouts/bench/bench-del.lua \ + src/ext/timeouts/bench/bench-expire.lua \ + src/ext/timeouts/bench/bench.h \ + src/ext/timeouts/bench/bench-heap.c \ + src/ext/timeouts/bench/bench-llrb.c \ + src/ext/timeouts/bench/bench.plt \ + src/ext/timeouts/bench/bench-wheel.c \ + src/ext/timeouts/bench/Rules.mk \ + src/ext/timeouts/lua/Rules.mk \ + src/ext/timeouts/lua/timeout-lua.c \ + src/ext/timeouts/Makefile \ + src/ext/timeouts/Rules.shrc \ + src/ext/timeouts/test-timeout.c + diff --git a/src/ext/timeouts/Makefile b/src/ext/timeouts/Makefile new file mode 100644 index 0000000000..554ebb9ddd --- /dev/null +++ b/src/ext/timeouts/Makefile @@ -0,0 +1,68 @@ +# NOTE: GNU Make 3.81 won't export MAKEFLAGS if .POSIX is specified, but +# Solaris make won't export MAKEFLAGS unless .POSIX is specified. +$(firstword ignore).POSIX: + +.DEFAULT_GOAL = all + +.SUFFIXES: + +all: + +# +# USER-MODIFIABLE MACROS +# +top_srcdir = . +top_builddir = . + +CFLAGS = -O2 -march=native -g -Wall -Wextra -Wno-unused-parameter -Wno-unused-function +SOFLAGS = $$(auto_soflags) +LIBS = $$(auto_libs) + +ALL_CPPFLAGS = -I$(top_srcdir) -DWHEEL_BIT=$(WHEEL_BIT) -DWHEEL_NUM=$(WHEEL_NUM) $(CPPFLAGS) +ALL_CFLAGS = $(CFLAGS) +ALL_SOFLAGS = $(SOFLAGS) +ALL_LDFLAGS = $(LDFLAGS) +ALL_LIBS = $(LIBS) + +LUA_API = 5.3 +LUA = lua +LUA51_CPPFLAGS = $(LUA_CPPFLAGS) +LUA52_CPPFLAGS = $(LUA_CPPFLAGS) +LUA53_CPPFLAGS = $(LUA_CPPFLAGS) + +WHEEL_BIT = 6 +WHEEL_NUM = 4 + +RM = rm -f + +# END MACROS + +SHRC = \ + top_srcdir="$(top_srcdir)"; \ + top_builddir="$(top_builddir)"; \ + . "$${top_srcdir}/Rules.shrc" + +LUA_APIS = 5.1 5.2 5.3 + +include $(top_srcdir)/lua/Rules.mk +include $(top_srcdir)/bench/Rules.mk + +all: test-timeout + +timeout.o: $(top_srcdir)/timeout.c +test-timeout.o: $(top_srcdir)/test-timeout.c + +timeout.o test-timeout.o: + @$(SHRC); echo_cmd $(CC) $(ALL_CFLAGS) -c -o $@ $${top_srcdir}/$(@F:%.o=%.c) $(ALL_CPPFLAGS) + +test-timeout: timeout.o test-timeout.o + @$(SHRC); echo_cmd $(CC) $(ALL_CPPFLAGS) $(ALL_CFLAGS) -o $@ timeout.o test-timeout.o + +.PHONY: clean clean~ + +clean: + $(RM) $(top_builddir)/test-timeout $(top_builddir)/*.o + $(RM) -r $(top_builddir)/*.dSYM + +clean~: + find $(top_builddir) $(top_srcdir) -name "*~" -exec $(RM) -- {} "+" diff --git a/src/ext/timeouts/Rules.shrc b/src/ext/timeouts/Rules.shrc new file mode 100644 index 0000000000..ece75d42d4 --- /dev/null +++ b/src/ext/timeouts/Rules.shrc @@ -0,0 +1,40 @@ +# convert to absolute paths +top_srcdir="$(cd "${top_srcdir}" && pwd -L)" +top_builddir="$(cd "${top_builddir}" && pwd -L)" + +# Paths for Lua modules (benchmarks and installed modules) +export LUA_CPATH="${top_builddir}/lua/5.1/?.so;${top_builddir}/bench/?.so;;" +export LUA_PATH="${top_srcdir}/lua/?.lua;${top_srcdir}/bench/?.lua;;" +export LUA_CPATH_5_2="${top_builddir}/lua/5.2/?.so;${top_builddir}/bench/?.so;;" +export LUA_PATH_5_2="${top_srcdir}/lua/?.lua;${top_srcdir}/bench/?.lua;;" +export LUA_CPATH_5_3="${top_builddir}/lua/5.3/?.so;${top_builddir}/bench/?.so;;" +export LUA_PATH_5_3="${top_srcdir}/lua/?.lua;${top_srcdir}/bench/?.lua;;" + +# preserve stdout so we can print commands to terminal +exec 9>&1; +echo_cmd() { + printf "%s\n" "$*" >&9; + "$@"; +} + +auto_soflags() { + case "$(uname -s)" in + Darwin) + printf -- "-bundle -undefined dynamic_lookup" + ;; + *) + printf -- "-fPIC -shared" + ;; + esac +} + +auto_libs() { + case "$(uname -s)" in + Linux) + printf -- "-lrt" + ;; + *) + ;; + esac +} + diff --git a/src/ext/timeouts/bench/Rules.mk b/src/ext/timeouts/bench/Rules.mk new file mode 100644 index 0000000000..3ee72f3eff --- /dev/null +++ b/src/ext/timeouts/bench/Rules.mk @@ -0,0 +1,49 @@ +BENCH_MODS = bench.so $(BENCH_ALGOS:%=bench-%.so) +BENCH_ALGOS = wheel heap llrb +BENCH_OPS = add del expire + +$(top_builddir)/bench/bench.so: $(top_srcdir)/bench/bench.c +$(top_builddir)/bench/bench-wheel.so: $(top_srcdir)/bench/bench-wheel.c +$(top_builddir)/bench/bench-heap.so: $(top_srcdir)/bench/bench-heap.c +$(top_builddir)/bench/bench-llrb.so: $(top_srcdir)/bench/bench-llrb.c + +$(BENCH_MODS:%=$(top_builddir)/bench/%): $(top_srcdir)/timeout.h $(top_srcdir)/timeout.c $(top_srcdir)/bench/bench.h + mkdir -p $(@D) + @$(SHRC); echo_cmd $(CC) -o $@ $(top_srcdir)/bench/$(@F:%.so=%.c) $(ALL_CPPFLAGS) $(ALL_CFLAGS) $(ALL_SOFLAGS) $(ALL_LDFLAGS) $(ALL_LIBS) + +$(BENCH_OPS:%=$(top_builddir)/bench/wheel-%.dat): $(top_builddir)/bench/bench-wheel.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua +$(BENCH_OPS:%=$(top_builddir)/bench/heap-%.dat): $(top_builddir)/bench/bench-heap.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua +$(BENCH_OPS:%=$(top_builddir)/bench/llrb-%.dat): $(top_builddir)/bench/bench-llrb.so $(top_builddir)/bench/bench.so $(top_srcdir)/bench/bench-aux.lua + +$(BENCH_ALGOS:%=$(top_builddir)/bench/%-add.dat): $(top_srcdir)/bench/bench-add.lua + @$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-add.lua $${top_builddir}/bench/bench-$(@F:%-add.dat=%).so > $(@F).tmp + mv $@.tmp $@ + +$(BENCH_ALGOS:%=$(top_builddir)/bench/%-del.dat): $(top_srcdir)/bench/bench-del.lua + @$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-del.lua $${top_builddir}/bench/bench-$(@F:%-del.dat=%).so > $(@F).tmp + mv $@.tmp $@ + +$(BENCH_ALGOS:%=$(top_builddir)/bench/%-expire.dat): $(top_srcdir)/bench/bench-expire.lua + @$(SHRC); echo_cmd cd $(@D) && echo_cmd $(LUA) $${top_srcdir}/bench/bench-expire.lua $${top_builddir}/bench/bench-$(@F:%-expire.dat=%).so > $(@F).tmp + mv $@.tmp $@ + +$(top_builddir)/bench/bench.eps: \ + $(BENCH_OPS:%=$(top_builddir)/bench/wheel-%.dat) \ + $(BENCH_OPS:%=$(top_builddir)/bench/heap-%.dat) +# $(BENCH_OPS:%=$(top_builddir)/bench/llrb-%.dat) + +$(top_builddir)/bench/bench.eps: $(top_srcdir)/bench/bench.plt + @$(SHRC); echo_cmd cd $(@D) && echo_cmd gnuplot $${top_srcdir}/bench/bench.plt > $(@F).tmp + mv $@.tmp $@ + +$(top_builddir)/bench/bench.pdf: $(top_builddir)/bench/bench.eps + @$(SHRC); echo_cmd ps2pdf $${top_builddir}/bench/bench.eps $@ + +bench-mods: $(BENCH_MODS:%=$(top_builddir)/bench/%) + +bench-all: $(top_builddir)/bench/bench.pdf + +bench-clean: + $(RM) -r $(top_builddir)/bench/*.so $(top_builddir)/bench/*.dSYM + $(RM) $(top_builddir)/bench/*.dat $(top_builddir)/bench/*.tmp + $(RM) $(top_builddir)/bench/bench.{eps,pdf} diff --git a/src/ext/timeouts/bench/bench-add.lua b/src/ext/timeouts/bench/bench-add.lua new file mode 100755 index 0000000000..64a921d3de --- /dev/null +++ b/src/ext/timeouts/bench/bench-add.lua @@ -0,0 +1,30 @@ +#!/usr/bin/env lua + +local bench = require"bench" +local aux = require"bench-aux" + +local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so") +local limit = tonumber(aux.optenv("BENCH_N", 1000000)) +local step = tonumber(aux.optenv("BENCH_S", limit / 100)) +local exp_step = tonumber(aux.optenv("BENCH_E", 1.0)) +local verbose = aux.toboolean(os.getenv("BENCH_V", false)) + +local B = bench.new(lib, count, nil, verbose) +local fill_count, fill_last = B:fill(limit) + +for i=0,limit,step do + local exp_elapsed, fill_elapsed, fill_rate + + -- expire all timeouts + --exp_elapsed = aux.time(B.expire, B, fill_count, fill_last * exp_step) + exp_elapsed = aux.time(B.del, B, 0, fill_count) + assert(B:empty()) + + -- add i timeouts + fill_elapsed, fill_count, fill_last = aux.time(B.fill, B, i) + assert(fill_count == i) + fill_rate = fill_elapsed > 0 and (fill_count / fill_elapsed) or 0 + + local fmt = verbose and "%d\t%f\t(%d/s)\t(exp:%f)" or "%d\t%f" + aux.say(fmt, i, fill_elapsed, fill_rate, exp_elapsed) +end diff --git a/src/ext/timeouts/bench/bench-aux.lua b/src/ext/timeouts/bench/bench-aux.lua new file mode 100644 index 0000000000..6321247421 --- /dev/null +++ b/src/ext/timeouts/bench/bench-aux.lua @@ -0,0 +1,30 @@ +local bench = require"bench" +local clock = bench.clock + +local aux = {} + +local function time_return(begun, ...) + local duration = clock() - begun + return duration, ... +end + +function aux.time(f, ...) + local begun = clock() + return time_return(begun, f(...)) +end + +function aux.say(...) + print(string.format(...)) +end + +function aux.toboolean(s) + return tostring(s):match("^[1TtYy]") and true or false +end + +function aux.optenv(k, def) + local s = os.getenv(k) + + return (s and #s > 0 and s) or def +end + +return aux diff --git a/src/ext/timeouts/bench/bench-del.lua b/src/ext/timeouts/bench/bench-del.lua new file mode 100755 index 0000000000..4306745f21 --- /dev/null +++ b/src/ext/timeouts/bench/bench-del.lua @@ -0,0 +1,25 @@ +#!/usr/bin/env lua + +local bench = require"bench" +local aux = require"bench-aux" + +local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so") +local limit = tonumber(aux.optenv("BENCH_N", 1000000)) +local step = tonumber(aux.optenv("BENCH_S", limit / 100)) +local verbose = aux.toboolean(os.getenv("BENCH_V", false)) + +local B = bench.new(lib, count) + +for i=0,limit,step do + -- add i timeouts + local fill_elapsed, fill_count = aux.time(B.fill, B, i, 60 * 1000000) + assert(i == fill_count) + + --- delete i timeouts + local del_elapsed = aux.time(B.del, B, 0, fill_count) + assert(B:empty()) + local del_rate = i > 0 and i / del_elapsed or 0 + + local fmt = verbose and "%d\t%f\t(%d/s)\t(fill:%f)" or "%d\t%f" + aux.say(fmt, i, del_elapsed, del_rate, fill_elapsed) +end diff --git a/src/ext/timeouts/bench/bench-expire.lua b/src/ext/timeouts/bench/bench-expire.lua new file mode 100755 index 0000000000..3e6374ed52 --- /dev/null +++ b/src/ext/timeouts/bench/bench-expire.lua @@ -0,0 +1,29 @@ +#!/usr/bin/env lua + +local bench = require"bench" +local aux = require"bench-aux" + +local lib = ... or aux.optenv("BENCH_L", "bench-wheel.so") +local limit = tonumber(aux.optenv("BENCH_N", 1000000)) +local step = tonumber(aux.optenv("BENCH_S", limit / 100)) +-- expire 1/1000 * #timeouts per clock update +local exp_step = tonumber(aux.optenv("BENCH_E", 0.0001)) +local verbose = aux.toboolean(os.getenv("BENCH_V", false)) + +local B = require"bench".new(lib, count) + +for i=0,limit,step do + -- add i timeouts + local fill_elapsed, fill_count, fill_last = aux.time(B.fill, B, i) + + -- expire timeouts by iteratively updating clock. exp_step is the + -- approximate number of timeouts (as a fraction of the total number + -- of timeouts) that will expire per update. + local exp_elapsed, exp_count = aux.time(B.expire, B, fill_count, math.floor(fill_last * exp_step)) + assert(exp_count == i) + assert(B:empty()) + local exp_rate = i > 0 and i / exp_elapsed or 0 + + local fmt = verbose and "%d\t%f\t(%d/s)\t(fill:%f)" or "%d\t%f" + aux.say(fmt, i, exp_elapsed, exp_rate, fill_elapsed) +end diff --git a/src/ext/timeouts/bench/bench-heap.c b/src/ext/timeouts/bench/bench-heap.c new file mode 100644 index 0000000000..f1166a4d7e --- /dev/null +++ b/src/ext/timeouts/bench/bench-heap.c @@ -0,0 +1,236 @@ +/* + * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef _MIN_HEAP_H_ +#define _MIN_HEAP_H_ + +#include <stdlib.h> +#include <err.h> +#include "timeout.h" +#include "bench.h" + +#define min_heap_idx interval + +typedef timeout_t min_heap_idx_t; + +typedef struct min_heap +{ + struct timeout** p; + unsigned n, a; + timeout_t curtime; +} min_heap_t; + +static inline void min_heap_ctor(min_heap_t* s); +static inline void min_heap_dtor(min_heap_t* s); +static inline void min_heap_elem_init(struct timeout* e); +static inline int min_heap_elem_greater(struct timeout *a, struct timeout *b); +static inline int min_heap_empty(min_heap_t* s); +static inline unsigned min_heap_size(min_heap_t* s); +static inline struct timeout* min_heap_top(min_heap_t* s); +static inline int min_heap_reserve(min_heap_t* s, unsigned n); +static inline int min_heap_push(min_heap_t* s, struct timeout* e); +static inline struct timeout* min_heap_pop(min_heap_t* s); +static inline int min_heap_erase(min_heap_t* s, struct timeout* e); +static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e); +static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e); + +int min_heap_elem_greater(struct timeout *a, struct timeout *b) +{ + return a->expires > b->expires; +} + +void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } +void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); } +void min_heap_elem_init(struct timeout* e) { e->min_heap_idx = -1; } +int min_heap_empty(min_heap_t* s) { return 0u == s->n; } +unsigned min_heap_size(min_heap_t* s) { return s->n; } +struct timeout* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; } + +int min_heap_push(min_heap_t* s, struct timeout* e) +{ + if(min_heap_reserve(s, s->n + 1)) + return -1; + min_heap_shift_up_(s, s->n++, e); + return 0; +} + +struct timeout* min_heap_pop(min_heap_t* s) +{ + if(s->n) + { + struct timeout* e = *s->p; + min_heap_shift_down_(s, 0u, s->p[--s->n]); + e->min_heap_idx = -1; + return e; + } + return 0; +} + +int min_heap_erase(min_heap_t* s, struct timeout* e) +{ + if(((min_heap_idx_t)-1) != e->min_heap_idx) + { + struct timeout *last = s->p[--s->n]; + unsigned parent = (e->min_heap_idx - 1) / 2; + /* we replace e with the last element in the heap. We might need to + shift it upward if it is less than its parent, or downward if it is + greater than one or both its children. Since the children are known + to be less than the parent, it can't need to shift both up and + down. */ + if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) + min_heap_shift_up_(s, e->min_heap_idx, last); + else + min_heap_shift_down_(s, e->min_heap_idx, last); + e->min_heap_idx = -1; + return 0; + } + return -1; +} + +int min_heap_reserve(min_heap_t* s, unsigned n) +{ + if(s->a < n) + { + struct timeout** p; + unsigned a = s->a ? s->a * 2 : 8; + if(a < n) + a = n; + if(!(p = (struct timeout**)realloc(s->p, a * sizeof *p))) + return -1; + s->p = p; + s->a = a; + } + return 0; +} + +void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e) +{ + unsigned parent = (hole_index - 1) / 2; + while(hole_index && min_heap_elem_greater(s->p[parent], e)) + { + (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index; + hole_index = parent; + parent = (hole_index - 1) / 2; + } + (s->p[hole_index] = e)->min_heap_idx = hole_index; +} + +void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e) +{ + unsigned min_child = 2 * (hole_index + 1); + while(min_child <= s->n) + { + min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); + if(!(min_heap_elem_greater(e, s->p[min_child]))) + break; + (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index; + hole_index = min_child; + min_child = 2 * (hole_index + 1); + } + min_heap_shift_up_(s, hole_index, e); +} + +#endif /* _MIN_HEAP_H_ */ + + +static void *init(struct timeout *timeout, size_t count, int verbose) { + min_heap_t *H; + size_t i; + + H = calloc(1, sizeof *H); + + min_heap_ctor(H); + if (0 != min_heap_reserve(H, count)) + err(1, "realloc"); + + for (i = 0; i < count; i++) { + min_heap_elem_init(&timeout[i]); + } + + return H; +} /* init() */ + + +static void add(void *ctx, struct timeout *to, timeout_t expires) { + min_heap_t *H = ctx; + min_heap_erase(H, to); + to->expires = H->curtime + expires; + if (0 != min_heap_push(H, to)) + err(1, "realloc"); +} /* add() */ + + +static void del(void *ctx, struct timeout *to) { + min_heap_erase(ctx, to); +} /* del() */ + + +static struct timeout *get(void *ctx) { + min_heap_t *H = ctx; + struct timeout *to; + + if ((to = min_heap_top(H)) && to->expires <= H->curtime) + return min_heap_pop(H); + + return NULL; +} /* get() */ + + +static void update(void *ctx, timeout_t ts) { + min_heap_t *H = ctx; + H->curtime = ts; +} /* update() */ + + +static void check(void *ctx) { + return; +} /* check() */ + + +static int empty(void *ctx) { + min_heap_t *H = ctx; + + return (NULL == min_heap_top(H)); +} /* empty() */ + + +static void destroy(void *H) { + free(H); + return; +} /* destroy() */ + + +const struct benchops benchops = { + .init = &init, + .add = &add, + .del = &del, + .get = &get, + .update = &update, + .check = &check, + .empty = &empty, + .destroy = &destroy, +}; + diff --git a/src/ext/timeouts/bench/bench-llrb.c b/src/ext/timeouts/bench/bench-llrb.c new file mode 100644 index 0000000000..bdb02f0704 --- /dev/null +++ b/src/ext/timeouts/bench/bench-llrb.c @@ -0,0 +1,425 @@ +/* ========================================================================== + * llrb.h - Iterative Left-leaning Red-Black Tree. + * -------------------------------------------------------------------------- + * Copyright (c) 2011, 2013 William Ahern <william@25thandClement.com> + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * -------------------------------------------------------------------------- + * CREDITS: + * o Algorithm courtesy of Robert Sedgewick, "Left-leaning Red-Black + * Trees" (September 2008); and Robert Sedgewick and Kevin Wayne, + * Algorithms (4th ed. 2011). + * + * Sedgewick touts the simplicity of the recursive implementation, + * but at least for the 2-3 tree variant the iterative approach is + * almost line-for-line identical. The magic of C pointers helps; + * it'd be uglier with Java. + * + * A couple of missing NULL checks were added to Sedgewick's deletion + * example, and insert was optimized to short-circuit rotations when + * walking up the tree. + * + * o Code implemented in the fashion of Niels Provos' excellent *BSD + * sys/tree.h pre-processor library. + * + * Regarding relative performance, I've refrained from sharing my own + * benchmarks. Differences in run-time speed were too correlated to + * compiler options and other external factors. + * + * Provos' delete implementation doesn't need to start at the root of + * the tree. However, RB_REMOVE must be passed the actual node to be + * removed. LLRB_REMOVE merely requires a key, much like + * RB_FIND/LLRB_FIND. + * ========================================================================== + */ +#ifndef LLRB_H +#define LLRB_H + +#define LLRB_VENDOR "william@25thandClement.com" +#define LLRB_VERSION 0x20130925 + +#ifndef LLRB_STATIC +#ifdef __GNUC__ +#define LLRB_STATIC __attribute__((__unused__)) static +#else +#define LLRB_STATIC static +#endif +#endif + +#define LLRB_HEAD(name, type) \ +struct name { struct type *rbh_root; } + +#define LLRB_INITIALIZER(root) { 0 } + +#define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0) + +#define LLRB_BLACK 0 +#define LLRB_RED 1 + +#define LLRB_ENTRY(type) \ +struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; } + +#define LLRB_LEFT(elm, field) (elm)->field.rbe_left +#define LLRB_RIGHT(elm, field) (elm)->field.rbe_right +#define LLRB_PARENT(elm, field) (elm)->field.rbe_parent +#define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field)) +#define LLRB_COLOR(elm, field) (elm)->field.rbe_color +#define LLRB_ROOT(head) (head)->rbh_root +#define LLRB_EMPTY(head) ((head)->rbh_root == 0) +#define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED) + +#define LLRB_PROTOTYPE(name, type, field, cmp) \ + LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,) +#define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \ + LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC) +#define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ +attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \ +attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \ +attr struct type *name##_LLRB_FIND(struct name *, struct type *); \ +attr struct type *name##_LLRB_MIN(struct type *); \ +attr struct type *name##_LLRB_MAX(struct type *); \ +attr struct type *name##_LLRB_NEXT(struct type *); + +#define LLRB_GENERATE(name, type, field, cmp) \ + LLRB_GENERATE_INTERNAL(name, type, field, cmp,) +#define LLRB_GENERATE_STATIC(name, type, field, cmp) \ + LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC) +#define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ +static inline void name##_LLRB_ROTL(struct type **pivot) { \ + struct type *a = *pivot; \ + struct type *b = LLRB_RIGHT(a, field); \ + if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \ + LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \ + LLRB_LEFT(b, field) = a; \ + LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \ + LLRB_COLOR(a, field) = LLRB_RED; \ + LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \ + LLRB_PARENT(a, field) = b; \ + *pivot = b; \ +} \ +static inline void name##_LLRB_ROTR(struct type **pivot) { \ + struct type *b = *pivot; \ + struct type *a = LLRB_LEFT(b, field); \ + if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \ + LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \ + LLRB_RIGHT(a, field) = b; \ + LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \ + LLRB_COLOR(b, field) = LLRB_RED; \ + LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \ + LLRB_PARENT(b, field) = a; \ + *pivot = a; \ +} \ +static inline void name##_LLRB_FLIP(struct type *root) { \ + LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \ + LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \ + LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \ +} \ +static inline void name##_LLRB_FIXUP(struct type **root) { \ + if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \ + name##_LLRB_ROTL(root); \ + if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \ + name##_LLRB_ROTR(root); \ + if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \ + name##_LLRB_FLIP(*root); \ +} \ +attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \ + struct type **root = &LLRB_ROOT(head); \ + struct type *parent = 0; \ + while (*root) { \ + int comp = (cmp)((elm), (*root)); \ + parent = *root; \ + if (comp < 0) \ + root = &LLRB_LEFT(*root, field); \ + else if (comp > 0) \ + root = &LLRB_RIGHT(*root, field); \ + else \ + return *root; \ + } \ + LLRB_LEFT((elm), field) = 0; \ + LLRB_RIGHT((elm), field) = 0; \ + LLRB_COLOR((elm), field) = LLRB_RED; \ + LLRB_PARENT((elm), field) = parent; \ + *root = (elm); \ + while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \ + root = LLRB_EDGE(head, parent, field); \ + parent = LLRB_PARENT(parent, field); \ + name##_LLRB_FIXUP(root); \ + } \ + LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \ + return 0; \ +} \ +static inline void name##_LLRB_MOVL(struct type **pivot) { \ + name##_LLRB_FLIP(*pivot); \ + if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \ + name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \ + name##_LLRB_ROTL(pivot); \ + name##_LLRB_FLIP(*pivot); \ + } \ +} \ +static inline void name##_LLRB_MOVR(struct type **pivot) { \ + name##_LLRB_FLIP(*pivot); \ + if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \ + name##_LLRB_ROTR(pivot); \ + name##_LLRB_FLIP(*pivot); \ + } \ +} \ +static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \ + struct type **pivot = root, *deleted, *parent; \ + while (LLRB_LEFT(*pivot, field)) { \ + if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \ + name##_LLRB_MOVL(pivot); \ + pivot = &LLRB_LEFT(*pivot, field); \ + } \ + deleted = *pivot; \ + parent = LLRB_PARENT(*pivot, field); \ + *pivot = 0; \ + while (root != pivot) { \ + pivot = LLRB_EDGE(head, parent, field); \ + parent = LLRB_PARENT(parent, field); \ + name##_LLRB_FIXUP(pivot); \ + } \ + return deleted; \ +} \ +attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \ + struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \ + int comp; \ + while (*root) { \ + parent = LLRB_PARENT(*root, field); \ + comp = (cmp)(elm, *root); \ + if (comp < 0) { \ + if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \ + name##_LLRB_MOVL(root); \ + root = &LLRB_LEFT(*root, field); \ + } else { \ + if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \ + name##_LLRB_ROTR(root); \ + comp = (cmp)(elm, *root); \ + } \ + if (!comp && !LLRB_RIGHT(*root, field)) { \ + deleted = *root; \ + *root = 0; \ + break; \ + } \ + if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \ + name##_LLRB_MOVR(root); \ + comp = (cmp)(elm, *root); \ + } \ + if (!comp) { \ + struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \ + LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \ + LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \ + if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \ + LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \ + if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \ + LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \ + deleted = *root; \ + *root = orphan; \ + parent = *root; \ + break; \ + } else \ + root = &LLRB_RIGHT(*root, field); \ + } \ + } \ + while (parent) { \ + root = LLRB_EDGE(head, parent, field); \ + parent = LLRB_PARENT(parent, field); \ + name##_LLRB_FIXUP(root); \ + } \ + if (LLRB_ROOT(head)) \ + LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \ + return deleted; \ +} \ +attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \ + struct type *elm = LLRB_ROOT(head); \ + while (elm) { \ + int comp = (cmp)(key, elm); \ + if (comp < 0) \ + elm = LLRB_LEFT(elm, field); \ + else if (comp > 0) \ + elm = LLRB_RIGHT(elm, field); \ + else \ + return elm; \ + } \ + return 0; \ +} \ +attr struct type *name##_LLRB_MIN(struct type *elm) { \ + while (elm && LLRB_LEFT(elm, field)) \ + elm = LLRB_LEFT(elm, field); \ + return elm; \ +} \ +attr struct type *name##_LLRB_MAX(struct type *elm) { \ + while (elm && LLRB_RIGHT(elm, field)) \ + elm = LLRB_RIGHT(elm, field); \ + return elm; \ +} \ +attr struct type *name##_LLRB_NEXT(struct type *elm) { \ + if (LLRB_RIGHT(elm, field)) { \ + return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \ + } else if (LLRB_PARENT(elm, field)) { \ + if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \ + return LLRB_PARENT(elm, field); \ + while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \ + elm = LLRB_PARENT(elm, field); \ + return LLRB_PARENT(elm, field); \ + } else return 0; \ +} + +#define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm)) +#define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm)) +#define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm)) +#define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm)) +#define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head))) +#define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head))) +#define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm)) + +#define LLRB_FOREACH(elm, name, head) \ +for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm))) + +#endif /* LLRB_H */ + + +#include <stdlib.h> + +#include "timeout.h" +#include "bench.h" + + +struct rbtimeout { + timeout_t expires; + + int pending; + + LLRB_ENTRY(rbtimeout) rbe; +}; + +struct rbtimeouts { + timeout_t curtime; + LLRB_HEAD(tree, rbtimeout) tree; +}; + + +static int timeoutcmp(struct rbtimeout *a, struct rbtimeout *b) { + if (a->expires < b->expires) { + return -1; + } else if (a->expires > b->expires) { + return 1; + } else if (a < b) { + return -1; + } else if (a > b) { + return 1; + } else { + return 0; + } +} /* timeoutcmp() */ + +LLRB_GENERATE_STATIC(tree, rbtimeout, rbe, timeoutcmp) + +static void *init(struct timeout *timeout, size_t count, int verbose) { + struct rbtimeouts *T; + size_t i; + + T = malloc(sizeof *T); + T->curtime = 0; + LLRB_INIT(&T->tree); + + for (i = 0; i < count; i++) { + struct rbtimeout *to = (void *)&timeout[i]; + to->expires = 0; + to->pending = 0; + } + + return T; +} /* init() */ + + +static void add(void *ctx, struct timeout *_to, timeout_t expires) { + struct rbtimeouts *T = ctx; + struct rbtimeout *to = (void *)_to; + + if (to->pending) + LLRB_REMOVE(tree, &T->tree, to); + + to->expires = T->curtime + expires; + LLRB_INSERT(tree, &T->tree, to); + to->pending = 1; +} /* add() */ + + +static void del(void *ctx, struct timeout *_to) { + struct rbtimeouts *T = ctx; + struct rbtimeout *to = (void *)_to; + + LLRB_REMOVE(tree, &T->tree, to); + to->pending = 0; + to->expires = 0; +} /* del() */ + + +static struct timeout *get(void *ctx) { + struct rbtimeouts *T = ctx; + struct rbtimeout *to; + + if ((to = LLRB_MIN(tree, &T->tree)) && to->expires <= T->curtime) { + LLRB_REMOVE(tree, &T->tree, to); + to->pending = 0; + to->expires = 0; + + return (void *)to; + } + + return NULL; +} /* get() */ + + +static void update(void *ctx, timeout_t ts) { + struct rbtimeouts *T = ctx; + T->curtime = ts; +} /* update() */ + + +static void check(void *ctx) { + return; +} /* check() */ + + +static int empty(void *ctx) { + struct rbtimeouts *T = ctx; + + return LLRB_EMPTY(&T->tree); +} /* empty() */ + + +static void destroy(void *ctx) { + free(ctx); + return; +} /* destroy() */ + + +const struct benchops benchops = { + .init = &init, + .add = &add, + .del = &del, + .get = &get, + .update = &update, + .check = &check, + .empty = &empty, + .destroy = &destroy, +}; + diff --git a/src/ext/timeouts/bench/bench-wheel.c b/src/ext/timeouts/bench/bench-wheel.c new file mode 100644 index 0000000000..0cba1af83e --- /dev/null +++ b/src/ext/timeouts/bench/bench-wheel.c @@ -0,0 +1,81 @@ +#include <stdlib.h> + +#define TIMEOUT_PUBLIC static + +#include "timeout.h" +#include "timeout.c" +#include "bench.h" + + +static void *init(struct timeout *timeout, size_t count, int verbose) { + struct timeouts *T; + size_t i; + int error; + + T = timeouts_open(TIMEOUT_mHZ, &error); + + for (i = 0; i < count; i++) { + timeout_init(&timeout[i], 0); + } + +#if TIMEOUT_DEBUG - 0 + timeout_debug = verbose; +#endif + + return T; +} /* init() */ + + +static void add(void *T, struct timeout *to, timeout_t expires) { + timeouts_add(T, to, expires); +} /* add() */ + + +static void del(void *T, struct timeout *to) { + timeouts_del(T, to); +} /* del() */ + + +static struct timeout *get(void *T) { + return timeouts_get(T); +} /* get() */ + + +static void update(void *T, timeout_t ts) { + timeouts_update(T, ts); +} /* update() */ + + +static void (check)(void *T) { + if (!timeouts_check(T, stderr)) + _Exit(1); +} /* check() */ + + +static int empty(void *T) { + return !(timeouts_pending(T) || timeouts_expired(T)); +} /* empty() */ + + +static struct timeout *next(void *T, struct timeouts_it *it) { + return timeouts_next(T, it); +} /* next() */ + + +static void destroy(void *T) { + timeouts_close(T); +} /* destroy() */ + + +const struct benchops benchops = { + .init = &init, + .add = &add, + .del = &del, + .get = &get, + .update = &update, + .check = &check, + .empty = &empty, + .next = &next, + .destroy = &destroy +}; + diff --git a/src/ext/timeouts/bench/bench.c b/src/ext/timeouts/bench/bench.c new file mode 100644 index 0000000000..0d4cee44a0 --- /dev/null +++ b/src/ext/timeouts/bench/bench.c @@ -0,0 +1,293 @@ +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <errno.h> +#include <unistd.h> +#include <dlfcn.h> + +#if __APPLE__ +#include <mach/mach_time.h> +#endif + +#include <lua.h> +#include <lualib.h> +#include <lauxlib.h> + +#include "timeout.h" +#include "bench.h" + +#if LUA_VERSION_NUM < 502 +static int lua_absindex(lua_State *L, int idx) { + return (idx > 0 || idx <= LUA_REGISTRYINDEX)? idx : lua_gettop(L) + idx + 1; +} /* lua_absindex() */ + +static void luaL_setfuncs(lua_State *L, const luaL_Reg *l, int nup) { + int i, t = lua_absindex(L, -1 - nup); + + for (; l->name; l++) { + for (i = 0; i < nup; i++) + lua_pushvalue(L, -nup); + lua_pushcclosure(L, l->func, nup); + lua_setfield(L, t, l->name); + } + + lua_pop(L, nup); +} /* luaL_setfuncs() */ + +#define luaL_newlibtable(L, l) \ + lua_createtable(L, 0, (sizeof (l) / sizeof *(l)) - 1) + +#define luaL_newlib(L, l) \ + (luaL_newlibtable((L), (l)), luaL_setfuncs((L), (l), 0)) +#endif + +#ifndef MAX +#define MAX(a, b) (((a) > (b))? (a) : (b)) +#endif + + +struct bench { + const char *path; + void *solib; + size_t count; + timeout_t timeout_max; + int verbose; + + void *state; + struct timeout *timeout; + struct benchops ops; + timeout_t curtime; +}; /* struct bench */ + + +#if __APPLE__ +static mach_timebase_info_data_t timebase; +#endif + + +static int long long monotime(void) { +#if __APPLE__ + unsigned long long abt; + + abt = mach_absolute_time(); + abt = abt * timebase.numer / timebase.denom; + + return abt / 1000LL; +#else + struct timespec ts; + + clock_gettime(CLOCK_MONOTONIC, &ts); + + return (ts.tv_sec * 1000000L) + (ts.tv_nsec / 1000L); +#endif +} /* monotime() */ + + +static int bench_clock(lua_State *L) { + lua_pushnumber(L, (double)monotime() / 1000000L); + + return 1; +} /* bench_clock() */ + + +static int bench_new(lua_State *L) { + const char *path = luaL_checkstring(L, 1); + size_t count = luaL_optinteger(L, 2, 1000000); + timeout_t timeout_max = luaL_optinteger(L, 3, 300 * 1000000L); + int verbose = (lua_isnone(L, 4))? 0 : lua_toboolean(L, 4); + struct bench *B; + struct benchops *ops; + + B = lua_newuserdata(L, sizeof *B); + memset(B, 0, sizeof *B); + + luaL_getmetatable(L, "BENCH*"); + lua_setmetatable(L, -2); + + B->count = count; + B->timeout_max = timeout_max; + B->verbose = verbose; + + if (!(B->timeout = calloc(count, sizeof *B->timeout))) + return luaL_error(L, "%s", strerror(errno)); + + if (!(B->solib = dlopen(path, RTLD_NOW|RTLD_LOCAL))) + return luaL_error(L, "%s: %s", path, dlerror()); + + if (!(ops = dlsym(B->solib, "benchops"))) + return luaL_error(L, "%s: %s", path, dlerror()); + + B->ops = *ops; + B->state = B->ops.init(B->timeout, B->count, B->verbose); + + return 1; +} /* bench_new() */ + + +static int bench_add(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + unsigned i; + timeout_t t; + + i = (lua_isnoneornil(L, 2))? random() % B->count : (unsigned)luaL_checkinteger(L, 2); + t = (lua_isnoneornil(L, 3))? random() % B->timeout_max : (unsigned)luaL_checkinteger(L, 3); + + B->ops.add(B->state, &B->timeout[i], t); + + return 0; +} /* bench_add() */ + + +static int bench_del(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + size_t i = luaL_optinteger(L, 2, random() % B->count); + size_t j = luaL_optinteger(L, 3, i); + + while (i <= j && i < B->count) { + B->ops.del(B->state, &B->timeout[i]); + ++i; + } + + return 0; +} /* bench_del() */ + + +static int bench_fill(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + size_t count = luaL_optinteger(L, 2, B->count); + long timeout_inc = luaL_optinteger(L, 3, -1), timeout_max = 0, timeout; + size_t i; + + if (timeout_inc < 0) { + for (i = 0; i < count; i++) { + timeout = random() % B->timeout_max; + B->ops.add(B->state, &B->timeout[i], timeout); + timeout_max = MAX(timeout, timeout_max); + } + } else { + for (i = 0; i < count; i++) { + timeout = timeout_inc + i; + B->ops.add(B->state, &B->timeout[i], timeout_inc + i); + timeout_max = MAX(timeout, timeout_max); + } + } + + lua_pushinteger(L, (lua_Integer)count); + lua_pushinteger(L, (lua_Integer)timeout_max); + + return 2; +} /* bench_fill() */ + + +static int bench_expire(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + unsigned count = luaL_optinteger(L, 2, B->count); + unsigned step = luaL_optinteger(L, 3, 300000); + size_t i = 0; + + while (i < count && !B->ops.empty(B->state)) { + B->curtime += step; + B->ops.update(B->state, B->curtime); + + while (B->ops.get(B->state)) + i++; + } + + lua_pushinteger(L, (lua_Integer)i); + + return 1; +} /* bench_expire() */ + + +static int bench_empty(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + + lua_pushboolean(L, B->ops.empty(B->state)); + + return 1; +} /* bench_empty() */ + + +static int bench__next(lua_State *L) { + struct bench *B = lua_touserdata(L, lua_upvalueindex(1)); + struct timeouts_it *it = lua_touserdata(L, lua_upvalueindex(2)); + struct timeout *to; + + if (!B->ops.next || !(to = B->ops.next(B->state, it))) + return 0; + + lua_pushinteger(L, luaL_optinteger(L, 2, 0) + 1); + + lua_newtable(L); + lua_pushinteger(L, to->expires); + lua_setfield(L, -2, "expires"); + + return 2; +} /* bench__next() */ + +static int bench__pairs(lua_State *L) { + struct timeouts_it *it; + + lua_settop(L, 1); + + it = lua_newuserdata(L, sizeof *it); + TIMEOUTS_IT_INIT(it, TIMEOUTS_ALL); + + lua_pushcclosure(L, &bench__next, 2); + lua_pushvalue(L, 1); + lua_pushinteger(L, 0); + + return 3; +} /* bench__pairs() */ + + +static int bench__gc(lua_State *L) { + struct bench *B = lua_touserdata(L, 1); + + if (B->state) { + B->ops.destroy(B->state); + B->state = NULL; + } + + return 0; +} /* bench__gc() */ + + +static const luaL_Reg bench_methods[] = { + { "add", &bench_add }, + { "del", &bench_del }, + { "fill", &bench_fill }, + { "expire", &bench_expire }, + { "empty", &bench_empty }, + { "close", &bench__gc }, + { NULL, NULL } +}; + +static const luaL_Reg bench_metatable[] = { + { "__pairs", &bench__pairs }, + { "__gc", &bench__gc }, + { NULL, NULL } +}; + +static const luaL_Reg bench_globals[] = { + { "new", &bench_new }, + { "clock", &bench_clock }, + { NULL, NULL } +}; + +int luaopen_bench(lua_State *L) { +#if __APPLE__ + mach_timebase_info(&timebase); +#endif + + if (luaL_newmetatable(L, "BENCH*")) { + luaL_setfuncs(L, bench_metatable, 0); + luaL_newlib(L, bench_methods); + lua_setfield(L, -2, "__index"); + } + + luaL_newlib(L, bench_globals); + + return 1; +} /* luaopen_bench() */ + diff --git a/src/ext/timeouts/bench/bench.h b/src/ext/timeouts/bench/bench.h new file mode 100644 index 0000000000..bc1f7cf177 --- /dev/null +++ b/src/ext/timeouts/bench/bench.h @@ -0,0 +1,11 @@ +struct benchops { + void *(*init)(struct timeout *, size_t, int); + void (*add)(void *, struct timeout *, timeout_t); + void (*del)(void *, struct timeout *); + struct timeout *(*get)(void *); + void (*update)(void *, timeout_t); + void (*check)(void *); + int (*empty)(void *); + struct timeout *(*next)(void *, struct timeouts_it *); + void (*destroy)(void *); +}; /* struct benchops() */ diff --git a/src/ext/timeouts/bench/bench.plt b/src/ext/timeouts/bench/bench.plt new file mode 100644 index 0000000000..6e143c65e1 --- /dev/null +++ b/src/ext/timeouts/bench/bench.plt @@ -0,0 +1,19 @@ +set terminal postscript color + +set key top left +set xlabel "Number of timeouts" +set ylabel "Time\n(microseconds)" +#set logscale x + +set title "Time spent installing timeouts" font ",20" +plot 'heap-add.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \ + 'wheel-add.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green" + +set title "Time spent deleting timeouts" font ",20" +plot 'heap-del.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \ + 'wheel-del.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green" + +set title "Time spent expiring timeouts\n(by iteratively updating clock ~1000 times)" font ",20" +plot 'heap-expire.dat' using 1:($2*1000000) title "min-heap" with lines ls 1 lw 3 lc "red", \ + 'wheel-expire.dat' using 1:($2*1000000) title "hierarchical wheel" with lines ls 1 lw 3 lc "forest-green" + diff --git a/src/ext/timeouts/lua/Rules.mk b/src/ext/timeouts/lua/Rules.mk new file mode 100644 index 0000000000..0f06fce30b --- /dev/null +++ b/src/ext/timeouts/lua/Rules.mk @@ -0,0 +1,20 @@ +$(LUA_APIS:%=$(top_builddir)/lua/%/timeout.so): $(top_srcdir)/lua/timeout-lua.c $(top_srcdir)/timeout.h $(top_srcdir)/timeout.c + mkdir -p $(@D) + @$(SHRC); echo_cmd $(CC) -o $@ $(top_srcdir)/lua/timeout-lua.c -I$(top_srcdir) -DWHEEL_BIT=$(WHEEL_BIT) -DWHEEL_NUM=$(WHEEL_NUM) $(LUA53_CPPFLAGS) $(ALL_CPPFLAGS) $(ALL_CFLAGS) $(ALL_SOFLAGS) $(ALL_LDFLAGS) $(ALL_LIBS) + +$(top_builddir)/lua/5.1/timeouts.so: $(top_builddir)/lua/5.1/timeout.so +$(top_builddir)/lua/5.2/timeouts.so: $(top_builddir)/lua/5.2/timeout.so +$(top_builddir)/lua/5.3/timeouts.so: $(top_builddir)/lua/5.3/timeout.so + +$(LUA_APIS:%=$(top_builddir)/lua/%/timeouts.so): + cd $(@D) && ln -fs timeout.so timeouts.so + +lua-5.1: $(top_builddir)/lua/5.1/timeout.so $(top_builddir)/lua/5.1/timeouts.so +lua-5.2: $(top_builddir)/lua/5.2/timeout.so $(top_builddir)/lua/5.2/timeouts.so +lua-5.3: $(top_builddir)/lua/5.3/timeout.so $(top_builddir)/lua/5.3/timeouts.so + +lua-clean: + $(RM) -r $(top_builddir)/lua/5.? + +clean: lua-clean + diff --git a/src/ext/timeouts/lua/timeout-lua.c b/src/ext/timeouts/lua/timeout-lua.c new file mode 100644 index 0000000000..4d4e54cba6 --- /dev/null +++ b/src/ext/timeouts/lua/timeout-lua.c @@ -0,0 +1,396 @@ +#include <assert.h> +#include <string.h> + +#include <lua.h> +#include <lualib.h> +#include <lauxlib.h> + +#if LUA_VERSION_NUM != 503 +#error only Lua 5.3 supported +#endif + +#define TIMEOUT_PUBLIC static +#include "timeout.h" +#include "timeout.c" + +#define TIMEOUT_METANAME "struct timeout" +#define TIMEOUTS_METANAME "struct timeouts*" + +static struct timeout * +to_checkudata(lua_State *L, int index) +{ + return luaL_checkudata(L, index, TIMEOUT_METANAME); +} + +static struct timeouts * +tos_checkudata(lua_State *L, int index) +{ + return *(struct timeouts **)luaL_checkudata(L, index, TIMEOUTS_METANAME); +} + +static void +tos_bind(lua_State *L, int tos_index, int to_index) +{ + lua_getuservalue(L, tos_index); + lua_pushlightuserdata(L, to_checkudata(L, to_index)); + lua_pushvalue(L, to_index); + lua_rawset(L, -3); + lua_pop(L, 1); +} + +static void +tos_unbind(lua_State *L, int tos_index, int to_index) +{ + lua_getuservalue(L, tos_index); + lua_pushlightuserdata(L, to_checkudata(L, to_index)); + lua_pushnil(L); + lua_rawset(L, -3); + lua_pop(L, 1); +} + +static int +to__index(lua_State *L) +{ + struct timeout *to = to_checkudata(L, 1); + + if (lua_type(L, 2 == LUA_TSTRING)) { + const char *key = lua_tostring(L, 2); + + if (!strcmp(key, "flags")) { + lua_pushinteger(L, to->flags); + + return 1; + } else if (!strcmp(key, "expires")) { + lua_pushinteger(L, to->expires); + + return 1; + } + } + + if (LUA_TNIL != lua_getuservalue(L, 1)) { + lua_pushvalue(L, 2); + if (LUA_TNIL != lua_rawget(L, -2)) + return 1; + } + + lua_pushvalue(L, 2); + if (LUA_TNIL != lua_rawget(L, lua_upvalueindex(1))) + return 1; + + return 0; +} + +static int +to__newindex(lua_State *L) +{ + if (LUA_TNIL == lua_getuservalue(L, 1)) { + lua_newtable(L); + lua_pushvalue(L, -1); + lua_setuservalue(L, 1); + } + + lua_pushvalue(L, 2); + lua_pushvalue(L, 3); + lua_rawset(L, -3); + + return 0; +} + +static int +to__gc(lua_State *L) +{ + struct timeout *to = to_checkudata(L, 1); + + /* + * NB: On script exit it's possible for a timeout to still be + * associated with a timeouts object, particularly when the timeouts + * object was created first. + */ + timeout_del(to); + + return 0; +} + +static int +to_new(lua_State *L) +{ + int flags = luaL_optinteger(L, 1, 0); + struct timeout *to; + + to = lua_newuserdata(L, sizeof *to); + timeout_init(to, flags); + luaL_setmetatable(L, TIMEOUT_METANAME); + + return 1; +} + +static const luaL_Reg to_methods[] = { + { NULL, NULL }, +}; + +static const luaL_Reg to_metatable[] = { + { "__index", &to__index }, + { "__newindex", &to__newindex }, + { "__gc", &to__gc }, + { NULL, NULL }, +}; + +static const luaL_Reg to_globals[] = { + { "new", &to_new }, + { NULL, NULL }, +}; + +static void +to_newmetatable(lua_State *L) +{ + if (luaL_newmetatable(L, TIMEOUT_METANAME)) { + /* + * fill metamethod table, capturing the methods table as an + * upvalue for use by __index metamethod + */ + luaL_newlib(L, to_methods); + luaL_setfuncs(L, to_metatable, 1); + } +} + +int +luaopen_timeout(lua_State *L) +{ + to_newmetatable(L); + + luaL_newlib(L, to_globals); + lua_pushinteger(L, TIMEOUT_INT); + lua_setfield(L, -2, "INT"); + lua_pushinteger(L, TIMEOUT_ABS); + lua_setfield(L, -2, "ABS"); + + return 1; +} + +static int +tos_update(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + lua_Number n = luaL_checknumber(L, 2); + + timeouts_update(T, timeouts_f2i(T, n)); + + lua_pushvalue(L, 1); + + return 1; +} + +static int +tos_step(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + lua_Number n = luaL_checknumber(L, 2); + + timeouts_step(T, timeouts_f2i(T, n)); + + lua_pushvalue(L, 1); + + return 1; +} + +static int +tos_timeout(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushnumber(L, timeouts_i2f(T, timeouts_timeout(T))); + + return 1; +} + +static int +tos_add(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + struct timeout *to = to_checkudata(L, 2); + lua_Number timeout = luaL_checknumber(L, 3); + + tos_bind(L, 1, 2); + timeouts_addf(T, to, timeout); + + return lua_pushvalue(L, 1), 1; +} + +static int +tos_del(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + struct timeout *to = to_checkudata(L, 2); + + timeouts_del(T, to); + tos_unbind(L, 1, 2); + + return lua_pushvalue(L, 1), 1; +} + +static int +tos_get(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + struct timeout *to; + + if (!(to = timeouts_get(T))) + return 0; + + lua_getuservalue(L, 1); + lua_rawgetp(L, -1, to); + + if (!timeout_pending(to)) + tos_unbind(L, 1, lua_absindex(L, -1)); + + return 1; +} + +static int +tos_pending(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushboolean(L, timeouts_pending(T)); + + return 1; +} + +static int +tos_expired(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushboolean(L, timeouts_expired(T)); + + return 1; +} + +static int +tos_check(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, 1); + + lua_pushboolean(L, timeouts_check(T, NULL)); + + return 1; +} + +static int +tos__next(lua_State *L) +{ + struct timeouts *T = tos_checkudata(L, lua_upvalueindex(1)); + struct timeouts_it *it = lua_touserdata(L, lua_upvalueindex(2)); + struct timeout *to; + + if (!(to = timeouts_next(T, it))) + return 0; + + lua_getuservalue(L, lua_upvalueindex(1)); + lua_rawgetp(L, -1, to); + + return 1; +} + +static int +tos_timeouts(lua_State *L) +{ + int flags = luaL_checkinteger(L, 2); + struct timeouts_it *it; + + tos_checkudata(L, 1); + lua_pushvalue(L, 1); + it = lua_newuserdata(L, sizeof *it); + TIMEOUTS_IT_INIT(it, flags); + lua_pushcclosure(L, &tos__next, 2); + + return 1; +} + +static int +tos__gc(lua_State *L) +{ + struct timeouts **tos = luaL_checkudata(L, 1, TIMEOUTS_METANAME); + struct timeout *to; + + TIMEOUTS_FOREACH(to, *tos, TIMEOUTS_ALL) { + timeouts_del(*tos, to); + } + + timeouts_close(*tos); + *tos = NULL; + + return 0; +} + +static int +tos_new(lua_State *L) +{ + timeout_t hz = luaL_optinteger(L, 1, 0); + struct timeouts **T; + int error; + + T = lua_newuserdata(L, sizeof *T); + luaL_setmetatable(L, TIMEOUTS_METANAME); + + lua_newtable(L); + lua_setuservalue(L, -2); + + if (!(*T = timeouts_open(hz, &error))) + return luaL_error(L, "%s", strerror(error)); + + return 1; +} + +static const luaL_Reg tos_methods[] = { + { "update", &tos_update }, + { "step", &tos_step }, + { "timeout", &tos_timeout }, + { "add", &tos_add }, + { "del", &tos_del }, + { "get", &tos_get }, + { "pending", &tos_pending }, + { "expired", &tos_expired }, + { "check", &tos_check }, + { "timeouts", &tos_timeouts }, + { NULL, NULL }, +}; + +static const luaL_Reg tos_metatable[] = { + { "__gc", &tos__gc }, + { NULL, NULL }, +}; + +static const luaL_Reg tos_globals[] = { + { "new", &tos_new }, + { NULL, NULL }, +}; + +static void +tos_newmetatable(lua_State *L) +{ + if (luaL_newmetatable(L, TIMEOUTS_METANAME)) { + luaL_setfuncs(L, tos_metatable, 0); + luaL_newlib(L, tos_methods); + lua_setfield(L, -2, "__index"); + } +} + +int +luaopen_timeouts(lua_State *L) +{ + to_newmetatable(L); + tos_newmetatable(L); + + luaL_newlib(L, tos_globals); + lua_pushinteger(L, TIMEOUTS_PENDING); + lua_setfield(L, -2, "PENDING"); + lua_pushinteger(L, TIMEOUTS_EXPIRED); + lua_setfield(L, -2, "EXPIRED"); + lua_pushinteger(L, TIMEOUTS_ALL); + lua_setfield(L, -2, "ALL"); + lua_pushinteger(L, TIMEOUTS_CLEAR); + lua_setfield(L, -2, "CLEAR"); + + return 1; +} diff --git a/src/ext/timeouts/test-timeout.c b/src/ext/timeouts/test-timeout.c new file mode 100644 index 0000000000..8077129376 --- /dev/null +++ b/src/ext/timeouts/test-timeout.c @@ -0,0 +1,530 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> +#include <limits.h> + +#include "timeout.h" + +#define THE_END_OF_TIME ((timeout_t)-1) + +static int check_misc(void) { + if (TIMEOUT_VERSION != timeout_version()) + return 1; + if (TIMEOUT_V_REL != timeout_v_rel()) + return 1; + if (TIMEOUT_V_API != timeout_v_api()) + return 1; + if (TIMEOUT_V_ABI != timeout_v_abi()) + return 1; + if (strcmp(timeout_vendor(), TIMEOUT_VENDOR)) + return 1; + return 0; +} + +static int check_open_close(timeout_t hz_set, timeout_t hz_expect) { + int err=0; + struct timeouts *tos = timeouts_open(hz_set, &err); + if (!tos) + return 1; + if (err) + return 1; + if (hz_expect != timeouts_hz(tos)) + return 1; + timeouts_close(tos); + return 0; +} + +/* Not very random */ +static timeout_t random_to(timeout_t min, timeout_t max) +{ + if (max <= min) + return min; + /* Not actually all that random, but should exercise the code. */ + timeout_t rand64 = random() * (timeout_t)INT_MAX + random(); + return min + (rand64 % (max-min)); +} + +/* configuration for check_randomized */ +struct rand_cfg { + /* When creating timeouts, smallest possible delay */ + timeout_t min_timeout; + /* When creating timeouts, largest possible delay */ + timeout_t max_timeout; + /* First time to start the clock at. */ + timeout_t start_at; + /* Do not advance the clock past this time. */ + timeout_t end_at; + /* Number of timeouts to create and monitor. */ + int n_timeouts; + /* Advance the clock by no more than this each step. */ + timeout_t max_step; + /* Use relative timers and stepping */ + int relative; + /* Every time the clock ticks, try removing this many timeouts at + * random. */ + int try_removing; + /* When we're done, advance the clock to the end of time. */ + int finalize; +}; + +static int check_randomized(const struct rand_cfg *cfg) +{ +#define FAIL() do { \ + printf("Failure on line %d\n", __LINE__); \ + goto done; \ + } while (0) + + int i, err; + int rv = 1; + struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout)); + timeout_t *timeouts = calloc(cfg->n_timeouts, sizeof(timeout_t)); + uint8_t *fired = calloc(cfg->n_timeouts, sizeof(uint8_t)); + uint8_t *found = calloc(cfg->n_timeouts, sizeof(uint8_t)); + uint8_t *deleted = calloc(cfg->n_timeouts, sizeof(uint8_t)); + struct timeouts *tos = timeouts_open(0, &err); + timeout_t now = cfg->start_at; + int n_added_pending = 0, cnt_added_pending = 0; + int n_added_expired = 0, cnt_added_expired = 0; + struct timeouts_it it_p, it_e, it_all; + int p_done = 0, e_done = 0, all_done = 0; + struct timeout *to = NULL; + const int rel = cfg->relative; + + if (!t || !timeouts || !tos || !fired || !found || !deleted) + FAIL(); + timeouts_update(tos, cfg->start_at); + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (&t[i] != timeout_init(&t[i], rel ? 0 : TIMEOUT_ABS)) + FAIL(); + if (timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + + timeouts[i] = random_to(cfg->min_timeout, cfg->max_timeout); + + timeouts_add(tos, &t[i], timeouts[i] - (rel ? now : 0)); + if (timeouts[i] <= cfg->start_at) { + if (timeout_pending(&t[i])) + FAIL(); + if (! timeout_expired(&t[i])) + FAIL(); + ++n_added_expired; + } else { + if (! timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + ++n_added_pending; + } + } + + if (!!n_added_pending != timeouts_pending(tos)) + FAIL(); + if (!!n_added_expired != timeouts_expired(tos)) + FAIL(); + + /* Test foreach, interleaving a few iterators. */ + TIMEOUTS_IT_INIT(&it_p, TIMEOUTS_PENDING); + TIMEOUTS_IT_INIT(&it_e, TIMEOUTS_EXPIRED); + TIMEOUTS_IT_INIT(&it_all, TIMEOUTS_ALL); + while (! (p_done && e_done && all_done)) { + if (!p_done) { + to = timeouts_next(tos, &it_p); + if (to) { + i = to - &t[0]; + ++found[i]; + ++cnt_added_pending; + } else { + p_done = 1; + } + } + if (!e_done) { + to = timeouts_next(tos, &it_e); + if (to) { + i = to - &t[0]; + ++found[i]; + ++cnt_added_expired; + } else { + e_done = 1; + } + } + if (!all_done) { + to = timeouts_next(tos, &it_all); + if (to) { + i = to - &t[0]; + ++found[i]; + } else { + all_done = 1; + } + } + } + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (found[i] != 2) + FAIL(); + } + if (cnt_added_expired != n_added_expired) + FAIL(); + if (cnt_added_pending != n_added_pending) + FAIL(); + + while (NULL != (to = timeouts_get(tos))) { + i = to - &t[0]; + assert(&t[i] == to); + if (timeouts[i] > cfg->start_at) + FAIL(); /* shouldn't have happened yet */ + + --n_added_expired; /* drop expired timeouts. */ + ++fired[i]; + } + + if (n_added_expired != 0) + FAIL(); + + while (now < cfg->end_at) { + int n_fired_this_time = 0; + timeout_t first_at = timeouts_timeout(tos) + now; + + timeout_t oldtime = now; + timeout_t step = random_to(1, cfg->max_step); + int another; + now += step; + if (rel) + timeouts_step(tos, step); + else + timeouts_update(tos, now); + + for (i = 0; i < cfg->try_removing; ++i) { + int idx = random() % cfg->n_timeouts; + if (! fired[idx]) { + timeout_del(&t[idx]); + ++deleted[idx]; + } + } + + another = (timeouts_timeout(tos) == 0); + + while (NULL != (to = timeouts_get(tos))) { + if (! another) + FAIL(); /* Thought we saw the last one! */ + i = to - &t[0]; + assert(&t[i] == to); + if (timeouts[i] > now) + FAIL(); /* shouldn't have happened yet */ + if (timeouts[i] <= oldtime) + FAIL(); /* should have happened already */ + if (timeouts[i] < first_at) + FAIL(); /* first_at should've been earlier */ + fired[i]++; + n_fired_this_time++; + another = (timeouts_timeout(tos) == 0); + } + if (n_fired_this_time && first_at > now) + FAIL(); /* first_at should've been earlier */ + if (another) + FAIL(); /* Huh? We think there are more? */ + if (!timeouts_check(tos, stderr)) + FAIL(); + } + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (fired[i] > 1) + FAIL(); /* Nothing fired twice. */ + if (timeouts[i] <= now) { + if (!(fired[i] || deleted[i])) + FAIL(); + } else { + if (fired[i]) + FAIL(); + } + if (fired[i] && deleted[i]) + FAIL(); + if (cfg->finalize > 1) { + if (!fired[i]) + timeout_del(&t[i]); + } + } + + /* Now nothing more should fire between now and the end of time. */ + if (cfg->finalize) { + timeouts_update(tos, THE_END_OF_TIME); + if (cfg->finalize > 1) { + if (timeouts_get(tos)) + FAIL(); + TIMEOUTS_FOREACH(to, tos, TIMEOUTS_ALL) + FAIL(); + } + } + rv = 0; + + done: + if (tos) timeouts_close(tos); + if (t) free(t); + if (timeouts) free(timeouts); + if (fired) free(fired); + if (found) free(found); + if (deleted) free(deleted); + return rv; +} + +struct intervals_cfg { + const timeout_t *timeouts; + int n_timeouts; + timeout_t start_at; + timeout_t end_at; + timeout_t skip; +}; + +int +check_intervals(struct intervals_cfg *cfg) +{ + int i, err; + int rv = 1; + struct timeout *to; + struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout)); + unsigned *fired = calloc(cfg->n_timeouts, sizeof(unsigned)); + struct timeouts *tos = timeouts_open(0, &err); + + timeout_t now = cfg->start_at; + if (!t || !tos || !fired) + FAIL(); + + timeouts_update(tos, now); + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (&t[i] != timeout_init(&t[i], TIMEOUT_INT)) + FAIL(); + if (timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + + timeouts_add(tos, &t[i], cfg->timeouts[i]); + if (! timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + } + + while (now < cfg->end_at) { + timeout_t delay = timeouts_timeout(tos); + if (cfg->skip && delay < cfg->skip) + delay = cfg->skip; + timeouts_step(tos, delay); + now += delay; + + while (NULL != (to = timeouts_get(tos))) { + i = to - &t[0]; + assert(&t[i] == to); + fired[i]++; + if (0 != (to->expires - cfg->start_at) % cfg->timeouts[i]) + FAIL(); + if (to->expires <= now) + FAIL(); + if (to->expires > now + cfg->timeouts[i]) + FAIL(); + } + if (!timeouts_check(tos, stderr)) + FAIL(); + } + + timeout_t duration = now - cfg->start_at; + for (i = 0; i < cfg->n_timeouts; ++i) { + if (cfg->skip) { + if (fired[i] > duration / cfg->timeouts[i]) + FAIL(); + } else { + if (fired[i] != duration / cfg->timeouts[i]) + FAIL(); + } + if (!timeout_pending(&t[i])) + FAIL(); + } + + rv = 0; + done: + if (t) free(t); + if (fired) free(fired); + if (tos) free(tos); + return rv; +} + +int +main(int argc, char **argv) +{ + int j; + int n_failed = 0; +#define DO(fn) do { \ + printf("."); fflush(stdout); \ + if (fn) { \ + ++n_failed; \ + printf("%s failed\n", #fn); \ + } \ + } while (0) + +#define DO_N(n, fn) do { \ + for (j = 0; j < (n); ++j) { \ + DO(fn); \ + } \ + } while (0) + + DO(check_misc()); + DO(check_open_close(1000, 1000)); + DO(check_open_close(0, TIMEOUT_mHZ)); + + struct rand_cfg cfg1 = { + .min_timeout = 1, + .max_timeout = 100, + .start_at = 5, + .end_at = 1000, + .n_timeouts = 1000, + .max_step = 10, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(300,check_randomized(&cfg1)); + + struct rand_cfg cfg2 = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 2, + }; + DO_N(300,check_randomized(&cfg2)); + + struct rand_cfg cfg2b = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 1, + }; + DO_N(300,check_randomized(&cfg2b)); + + struct rand_cfg cfg2c = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 0, + }; + DO_N(300,check_randomized(&cfg2c)); + + struct rand_cfg cfg3 = { + .min_timeout = 2000, + .max_timeout = ((uint64_t)1) << 50, + .start_at = 100, + .end_at = ((uint64_t)1) << 49, + .n_timeouts = 1000, + .max_step = 1<<31, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg3)); + + struct rand_cfg cfg3b = { + .min_timeout = ((uint64_t)1) << 50, + .max_timeout = ((uint64_t)1) << 52, + .start_at = 100, + .end_at = ((uint64_t)1) << 53, + .n_timeouts = 1000, + .max_step = ((uint64_t)1)<<48, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg3b)); + + struct rand_cfg cfg4 = { + .min_timeout = 2000, + .max_timeout = ((uint64_t)1) << 30, + .start_at = 100, + .end_at = ((uint64_t)1) << 26, + .n_timeouts = 10000, + .max_step = 1<<16, + .relative = 0, + .try_removing = 3, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg4)); + + const timeout_t primes[] = { + 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53, + 59,61,67,71,73,79,83,89,97 + }; + const timeout_t factors_of_1337[] = { + 1, 7, 191, 1337 + }; + const timeout_t multiples_of_five[] = { + 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 + }; + + struct intervals_cfg icfg1 = { + .timeouts = primes, + .n_timeouts = sizeof(primes)/sizeof(timeout_t), + .start_at = 50, + .end_at = 5322, + .skip = 0, + }; + DO(check_intervals(&icfg1)); + + struct intervals_cfg icfg2 = { + .timeouts = factors_of_1337, + .n_timeouts = sizeof(factors_of_1337)/sizeof(timeout_t), + .start_at = 50, + .end_at = 50000, + .skip = 0, + }; + DO(check_intervals(&icfg2)); + + struct intervals_cfg icfg3 = { + .timeouts = multiples_of_five, + .n_timeouts = sizeof(multiples_of_five)/sizeof(timeout_t), + .start_at = 49, + .end_at = 5333, + .skip = 0, + }; + DO(check_intervals(&icfg3)); + + struct intervals_cfg icfg4 = { + .timeouts = primes, + .n_timeouts = sizeof(primes)/sizeof(timeout_t), + .start_at = 50, + .end_at = 5322, + .skip = 16, + }; + DO(check_intervals(&icfg4)); + + if (n_failed) { + puts("\nFAIL"); + } else { + puts("\nOK"); + } + return !!n_failed; +} + +/* TODO: + + * Solve PR#3. + + * Investigate whether any untaken branches are possible. + + */ diff --git a/src/ext/timeouts/timeout-bitops.c b/src/ext/timeouts/timeout-bitops.c new file mode 100644 index 0000000000..a018f33b95 --- /dev/null +++ b/src/ext/timeouts/timeout-bitops.c @@ -0,0 +1,254 @@ +#include <stdint.h> +#include <limits.h> +#ifdef _MSC_VER +#include <intrin.h> /* _BitScanForward, _BitScanReverse */ +#endif + +/* First define ctz and clz functions; these are compiler-dependent if + * you want them to be fast. */ +#if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS) + +#ifndef LONG_BIT +#define LONG_BIT (SIZEOF_LONG*CHAR_BIT) +#endif + +/* On GCC and clang and some others, we can use __builtin functions. They + * are not defined for n==0, but timeout.s never calls them with n==0. */ + +#define ctz64(n) __builtin_ctzll(n) +#define clz64(n) __builtin_clzll(n) +#if LONG_BIT == 32 +#define ctz32(n) __builtin_ctzl(n) +#define clz32(n) __builtin_clzl(n) +#else +#define ctz32(n) __builtin_ctz(n) +#define clz32(n) __builtin_clz(n) +#endif + +#elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS) + +/* On MSVC, we have these handy functions. We can ignore their return + * values, since we will never supply val == 0. */ + +static __inline int ctz32(unsigned long val) +{ + DWORD zeros = 0; + _BitScanForward(&zeros, val); + return zeros; +} +static __inline int clz32(unsigned long val) +{ + DWORD zeros = 0; + _BitScanReverse(&zeros, val); + return zeros; +} +#ifdef _WIN64 +/* According to the documentation, these only exist on Win64. */ +static __inline int ctz64(uint64_t val) +{ + DWORD zeros = 0; + _BitScanForward64(&zeros, val); + return zeros; +} +static __inline int clz64(uint64_t val) +{ + DWORD zeros = 0; + _BitScanReverse64(&zeros, val); + return zeros; +} +#else +static __inline int ctz64(uint64_t val) +{ + uint32_t lo = (uint32_t) val; + uint32_t hi = (uint32_t) (val >> 32); + return lo ? ctz32(lo) : 32 + ctz32(hi); +} +static __inline int clz64(uint64_t val) +{ + uint32_t lo = (uint32_t) val; + uint32_t hi = (uint32_t) (val >> 32); + return hi ? clz32(hi) : 32 + clz32(lo); +} +#endif + +/* End of MSVC case. */ + +#else + +/* TODO: There are more clever ways to do this in the generic case. */ + + +#define process_(one, cz_bits, bits) \ + if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; } + +#define process64(bits) process_((UINT64_C(1)), 64, (bits)) +static inline int clz64(uint64_t x) +{ + int rv = 0; + + process64(32); + process64(16); + process64(8); + process64(4); + process64(2); + process64(1); + return rv; +} +#define process32(bits) process_((UINT32_C(1)), 32, (bits)) +static inline int clz32(uint32_t x) +{ + int rv = 0; + + process32(16); + process32(8); + process32(4); + process32(2); + process32(1); + return rv; +} + +#undef process_ +#undef process32 +#undef process64 +#define process_(one, bits) \ + if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; } + +#define process64(bits) process_((UINT64_C(1)), bits) +static inline int ctz64(uint64_t x) +{ + int rv = 0; + + process64(32); + process64(16); + process64(8); + process64(4); + process64(2); + process64(1); + return rv; +} + +#define process32(bits) process_((UINT32_C(1)), bits) +static inline int ctz32(uint32_t x) +{ + int rv = 0; + + process32(16); + process32(8); + process32(4); + process32(2); + process32(1); + return rv; +} + +#undef process32 +#undef process64 +#undef process_ + +/* End of generic case */ + +#endif /* End of defining ctz */ + +#ifdef TEST_BITOPS +#include <stdio.h> +#include <stdlib.h> + +static uint64_t testcases[] = { + 13371337 * 10, + 100, + 385789752, + 82574, + (((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101 +}; + +static int +naive_clz(int bits, uint64_t v) +{ + int r = 0; + uint64_t bit = ((uint64_t)1) << (bits-1); + while (bit && 0 == (v & bit)) { + r++; + bit >>= 1; + } + /* printf("clz(%d,%lx) -> %d\n", bits, v, r); */ + return r; +} + +static int +naive_ctz(int bits, uint64_t v) +{ + int r = 0; + uint64_t bit = 1; + while (bit && 0 == (v & bit)) { + r++; + bit <<= 1; + if (r == bits) + break; + } + /* printf("ctz(%d,%lx) -> %d\n", bits, v, r); */ + return r; +} + +static int +check(uint64_t vv) +{ + uint32_t v32 = (uint32_t) vv; + + if (vv == 0) + return 1; /* c[tl]z64(0) is undefined. */ + + if (ctz64(vv) != naive_ctz(64, vv)) { + printf("mismatch with ctz64: %d\n", ctz64(vv)); + exit(1); + return 0; + } + if (clz64(vv) != naive_clz(64, vv)) { + printf("mismatch with clz64: %d\n", clz64(vv)); + exit(1); + return 0; + } + + if (v32 == 0) + return 1; /* c[lt]z(0) is undefined. */ + + if (ctz32(v32) != naive_ctz(32, v32)) { + printf("mismatch with ctz32: %d\n", ctz32(v32)); + exit(1); + return 0; + } + if (clz32(v32) != naive_clz(32, v32)) { + printf("mismatch with clz32: %d\n", clz32(v32)); + exit(1); + return 0; + } + return 1; +} + +int +main(int c, char **v) +{ + unsigned int i; + const unsigned int n = sizeof(testcases)/sizeof(testcases[0]); + int result = 0; + + for (i = 0; i <= 63; ++i) { + uint64_t x = 1 << i; + if (!check(x)) + result = 1; + --x; + if (!check(x)) + result = 1; + } + + for (i = 0; i < n; ++i) { + if (! check(testcases[i])) + result = 1; + } + if (result) { + puts("FAIL"); + } else { + puts("OK"); + } + return result; +} +#endif + diff --git a/src/ext/timeouts/timeout-debug.h b/src/ext/timeouts/timeout-debug.h new file mode 100644 index 0000000000..fc727a6b42 --- /dev/null +++ b/src/ext/timeouts/timeout-debug.h @@ -0,0 +1,77 @@ +/* + * D E B U G R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if TIMEOUT_DEBUG - 0 +#include <stdlib.h> +#include <stdio.h> + +#undef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 1 +#define DEBUG_LEVEL timeout_debug + +static int timeout_debug; + +#define SAYit_(lvl, fmt, ...) do { \ + if (DEBUG_LEVEL >= (lvl)) \ + fprintf(stderr, fmt "%s", __FILE__, __LINE__, __func__, __VA_ARGS__); \ +} while (0) + +#define SAYit(lvl, ...) SAYit_((lvl), "%s:%d:%s: " __VA_ARGS__, "\n") + +#define PANIC(...) do { \ + SAYit(0, __VA_ARGS__); \ + _Exit(EXIT_FAILURE); \ +} while (0) +#else +#undef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 0 +#define DEBUG_LEVEL 0 + +#define SAYit(...) (void)0 +#endif + +#define SAY(...) SAYit(1, __VA_ARGS__) +#define HAI SAY("HAI") + + +static inline char *fmt_(char *buf, uint64_t ts, int wheel_bit, int wheel_num) { + char *p = buf; + int wheel, n, i; + + for (wheel = wheel_num - 2; wheel >= 0; wheel--) { + n = ((1 << wheel_bit) - 1) & (ts >> (wheel * WHEEL_BIT)); + + for (i = wheel_bit - 1; i >= 0; i--) { + *p++ = '0' + !!(n & (1 << i)); + } + + if (wheel != 0) + *p++ = ':'; + } + + *p = 0; + + return buf; +} /* fmt_() */ + +#define fmt(ts) fmt_(((char[((1 << WHEEL_BIT) * WHEEL_NUM) + WHEEL_NUM + 1]){ 0 }), (ts), WHEEL_BIT, WHEEL_NUM) + + +static inline char *bin64_(char *buf, uint64_t n, int wheel_bit) { + char *p = buf; + int i; + + for (i = 0; i < (1 << wheel_bit); i++) { + *p++ = "01"[0x1 & (n >> (((1 << wheel_bit) - 1) - i))]; + } + + *p = 0; + + return buf; +} /* bin64_() */ + +#define bin64(ts) bin64_(((char[((1 << WHEEL_BIT) * WHEEL_NUM) + 1]){ 0 }), (ts), WHEEL_BIT) + + diff --git a/src/ext/timeouts/timeout.c b/src/ext/timeouts/timeout.c new file mode 100644 index 0000000000..bd463a700d --- /dev/null +++ b/src/ext/timeouts/timeout.c @@ -0,0 +1,754 @@ +/* ========================================================================== + * timeout.c - Tickless hierarchical timing wheel. + * -------------------------------------------------------------------------- + * Copyright (c) 2013, 2014 William Ahern + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * ========================================================================== + */ +#ifdef HAVE_CONFIG_H +#include "orconfig.h" +#endif +#include <limits.h> /* CHAR_BIT */ + +#include <stddef.h> /* NULL */ +#include <stdlib.h> /* malloc(3) free(3) */ +#include <stdio.h> /* FILE fprintf(3) */ + +#include <inttypes.h> /* UINT64_C uint64_t */ + +#include <string.h> /* memset(3) */ + +#include <errno.h> /* errno */ + +#include "tor_queue.h" /* TAILQ(3) */ + +#include "timeout.h" + +#ifndef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 0 +#endif + +#if TIMEOUT_DEBUG - 0 +#include "timeout-debug.h" +#endif + +#ifdef TIMEOUT_DISABLE_RELATIVE_ACCESS +#define TO_SET_TIMEOUTS(to, T) ((void)0) +#else +#define TO_SET_TIMEOUTS(to, T) ((to)->timeouts = (T)) +#endif + +/* + * A N C I L L A R Y R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#define abstime_t timeout_t /* for documentation purposes */ +#define reltime_t timeout_t /* "" */ + +#if !defined countof +#define countof(a) (sizeof (a) / sizeof *(a)) +#endif + +#if !defined endof +#define endof(a) (&(a)[countof(a)]) +#endif + +#if !defined MIN +#define MIN(a, b) (((a) < (b))? (a) : (b)) +#endif + +#if !defined MAX +#define MAX(a, b) (((a) > (b))? (a) : (b)) +#endif + +#if !defined TOR_TAILQ_CONCAT +#define TOR_TAILQ_CONCAT(head1, head2, field) do { \ + if (!TOR_TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TOR_TAILQ_INIT((head2)); \ + } \ +} while (0) +#endif + +#if !defined TOR_TAILQ_FOREACH_SAFE +#define TOR_TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TOR_TAILQ_FIRST(head); \ + (var) && ((tvar) = TOR_TAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) +#endif + + +/* + * B I T M A N I P U L A T I O N R O U T I N E S + * + * The macros and routines below implement wheel parameterization. The + * inputs are: + * + * WHEEL_BIT - The number of value bits mapped in each wheel. The + * lowest-order WHEEL_BIT bits index the lowest-order (highest + * resolution) wheel, the next group of WHEEL_BIT bits the + * higher wheel, etc. + * + * WHEEL_NUM - The number of wheels. WHEEL_BIT * WHEEL_NUM = the number of + * value bits used by all the wheels. For the default of 6 and + * 4, only the low 24 bits are processed. Any timeout value + * larger than this will cycle through again. + * + * The implementation uses bit fields to remember which slot in each wheel + * is populated, and to generate masks of expiring slots according to the + * current update interval (i.e. the "tickless" aspect). The slots to + * process in a wheel are (populated-set & interval-mask). + * + * WHEEL_BIT cannot be larger than 6 bits because 2^6 -> 64 is the largest + * number of slots which can be tracked in a uint64_t integer bit field. + * WHEEL_BIT cannot be smaller than 3 bits because of our rotr and rotl + * routines, which only operate on all the value bits in an integer, and + * there's no integer smaller than uint8_t. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if !defined WHEEL_BIT +#define WHEEL_BIT 6 +#endif + +#if !defined WHEEL_NUM +#define WHEEL_NUM 4 +#endif + +#define WHEEL_LEN (1U << WHEEL_BIT) +#define WHEEL_MAX (WHEEL_LEN - 1) +#define WHEEL_MASK (WHEEL_LEN - 1) +#define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1) + +#include "timeout-bitops.c" + +#if WHEEL_BIT == 6 +#define ctz(n) ctz64(n) +#define clz(n) clz64(n) +#define fls(n) ((int)(64 - clz64(n))) +#else +#define ctz(n) ctz32(n) +#define clz(n) clz32(n) +#define fls(n) ((int)(32 - clz32(n))) +#endif + +#if WHEEL_BIT == 6 +#define WHEEL_C(n) UINT64_C(n) +#define WHEEL_PRIu PRIu64 +#define WHEEL_PRIx PRIx64 + +typedef uint64_t wheel_t; + +#elif WHEEL_BIT == 5 + +#define WHEEL_C(n) UINT32_C(n) +#define WHEEL_PRIu PRIu32 +#define WHEEL_PRIx PRIx32 + +typedef uint32_t wheel_t; + +#elif WHEEL_BIT == 4 + +#define WHEEL_C(n) UINT16_C(n) +#define WHEEL_PRIu PRIu16 +#define WHEEL_PRIx PRIx16 + +typedef uint16_t wheel_t; + +#elif WHEEL_BIT == 3 + +#define WHEEL_C(n) UINT8_C(n) +#define WHEEL_PRIu PRIu8 +#define WHEEL_PRIx PRIx8 + +typedef uint8_t wheel_t; + +#else +#error invalid WHEEL_BIT value +#endif + + +static inline wheel_t rotl(const wheel_t v, int c) { + if (!(c &= (sizeof v * CHAR_BIT - 1))) + return v; + + return (v << c) | (v >> (sizeof v * CHAR_BIT - c)); +} /* rotl() */ + + +static inline wheel_t rotr(const wheel_t v, int c) { + if (!(c &= (sizeof v * CHAR_BIT - 1))) + return v; + + return (v >> c) | (v << (sizeof v * CHAR_BIT - c)); +} /* rotr() */ + + +/* + * T I M E R R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TOR_TAILQ_HEAD(timeout_list, timeout); + +struct timeouts { + struct timeout_list wheel[WHEEL_NUM][WHEEL_LEN], expired; + + wheel_t pending[WHEEL_NUM]; + + timeout_t curtime; + timeout_t hertz; +}; /* struct timeouts */ + + +static struct timeouts *timeouts_init(struct timeouts *T, timeout_t hz) { + unsigned i, j; + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TOR_TAILQ_INIT(&T->wheel[i][j]); + } + } + + TOR_TAILQ_INIT(&T->expired); + + for (i = 0; i < countof(T->pending); i++) { + T->pending[i] = 0; + } + + T->curtime = 0; + T->hertz = (hz)? hz : TIMEOUT_mHZ; + + return T; +} /* timeouts_init() */ + + +TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t hz, int *error) { + struct timeouts *T; + + if ((T = malloc(sizeof *T))) + return timeouts_init(T, hz); + + *error = errno; + + return NULL; +} /* timeouts_open() */ + + +static void timeouts_reset(struct timeouts *T) { + struct timeout_list reset; + struct timeout *to; + unsigned i, j; + + TOR_TAILQ_INIT(&reset); + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TOR_TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe); + } + } + + TOR_TAILQ_CONCAT(&reset, &T->expired, tqe); + + TOR_TAILQ_FOREACH(to, &reset, tqe) { + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + } +} /* timeouts_reset() */ + + +TIMEOUT_PUBLIC void timeouts_close(struct timeouts *T) { + /* + * NOTE: Delete installed timeouts so timeout_pending() and + * timeout_expired() worked as expected. + */ + timeouts_reset(T); + + free(T); +} /* timeouts_close() */ + + +TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) { + return T->hertz; +} /* timeouts_hz() */ + + +TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) { + if (to->pending) { + TOR_TAILQ_REMOVE(to->pending, to, tqe); + + if (to->pending != &T->expired && TOR_TAILQ_EMPTY(to->pending)) { + ptrdiff_t index = to->pending - &T->wheel[0][0]; + int wheel = (int) (index / WHEEL_LEN); + int slot = index % WHEEL_LEN; + + T->pending[wheel] &= ~(WHEEL_C(1) << slot); + } + + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + } +} /* timeouts_del() */ + + +static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) { + return to->expires - T->curtime; +} /* timeout_rem() */ + + +static inline int timeout_wheel(timeout_t timeout) { + /* must be called with timeout != 0, so fls input is nonzero */ + return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT; +} /* timeout_wheel() */ + + +static inline int timeout_slot(int wheel, timeout_t expires) { + return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel); +} /* timeout_slot() */ + + +static void timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires) { + timeout_t rem; + int wheel, slot; + + timeouts_del(T, to); + + to->expires = expires; + + TO_SET_TIMEOUTS(to, T); + + if (expires > T->curtime) { + rem = timeout_rem(T, to); + + /* rem is nonzero since: + * rem == timeout_rem(T,to), + * == to->expires - T->curtime + * and above we have expires > T->curtime. + */ + wheel = timeout_wheel(rem); + slot = timeout_slot(wheel, to->expires); + + to->pending = &T->wheel[wheel][slot]; + TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe); + + T->pending[wheel] |= WHEEL_C(1) << slot; + } else { + to->pending = &T->expired; + TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe); + } +} /* timeouts_sched() */ + + +#ifndef TIMEOUT_DISABLE_INTERVALS +static void timeouts_readd(struct timeouts *T, struct timeout *to) { + to->expires += to->interval; + + if (to->expires <= T->curtime) { + /* If we've missed the next firing of this timeout, reschedule + * it to occur at the next multiple of its interval after + * the last time that it fired. + */ + timeout_t n = T->curtime - to->expires; + timeout_t r = n % to->interval; + to->expires = T->curtime + (to->interval - r); + } + + timeouts_sched(T, to, to->expires); +} /* timeouts_readd() */ +#endif + + +TIMEOUT_PUBLIC void timeouts_add(struct timeouts *T, struct timeout *to, timeout_t timeout) { +#ifndef TIMEOUT_DISABLE_INTERVALS + if (to->flags & TIMEOUT_INT) + to->interval = MAX(1, timeout); +#endif + + if (to->flags & TIMEOUT_ABS) + timeouts_sched(T, to, timeout); + else + timeouts_sched(T, to, T->curtime + timeout); +} /* timeouts_add() */ + + +TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) { + timeout_t elapsed = curtime - T->curtime; + struct timeout_list todo; + int wheel; + + TOR_TAILQ_INIT(&todo); + + /* + * There's no avoiding looping over every wheel. It's best to keep + * WHEEL_NUM smallish. + */ + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + wheel_t pending; + + /* + * Calculate the slots expiring in this wheel + * + * If the elapsed time is greater than the maximum period of + * the wheel, mark every position as expiring. + * + * Otherwise, to determine the expired slots fill in all the + * bits between the last slot processed and the current + * slot, inclusive of the last slot. We'll bitwise-AND this + * with our pending set below. + * + * If a wheel rolls over, force a tick of the next higher + * wheel. + */ + if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) { + pending = (wheel_t)~WHEEL_C(0); + } else { + wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT)); + int oslot, nslot; + + /* + * TODO: It's likely that at least one of the + * following three bit fill operations is redundant + * or can be replaced with a simpler operation. + */ + oslot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT)); + pending = rotl(((UINT64_C(1) << _elapsed) - 1), oslot); + + nslot = WHEEL_MASK & (curtime >> (wheel * WHEEL_BIT)); + pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot), (int)_elapsed); + pending |= WHEEL_C(1) << nslot; + } + + while (pending & T->pending[wheel]) { + /* ctz input cannot be zero: loop condition. */ + int slot = ctz(pending & T->pending[wheel]); + TOR_TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe); + T->pending[wheel] &= ~(UINT64_C(1) << slot); + } + + if (!(0x1 & pending)) + break; /* break if we didn't wrap around end of wheel */ + + /* if we're continuing, the next wheel must tick at least once */ + elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT))); + } + + T->curtime = curtime; + + while (!TOR_TAILQ_EMPTY(&todo)) { + struct timeout *to = TOR_TAILQ_FIRST(&todo); + + TOR_TAILQ_REMOVE(&todo, to, tqe); + to->pending = NULL; + + timeouts_sched(T, to, to->expires); + } + + return; +} /* timeouts_update() */ + +TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *T) { + return T->curtime; +} /* timeouts_get_curtime() */ + +TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) { + timeouts_update(T, T->curtime + elapsed); +} /* timeouts_step() */ + + +TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *T) { + wheel_t pending = 0; + int wheel; + + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + pending |= T->pending[wheel]; + } + + return !!pending; +} /* timeouts_pending() */ + + +TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *T) { + return !TOR_TAILQ_EMPTY(&T->expired); +} /* timeouts_expired() */ + + +/* + * Calculate the interval before needing to process any timeouts pending on + * any wheel. + * + * (This is separated from the public API routine so we can evaluate our + * wheel invariant assertions irrespective of the expired queue.) + * + * This might return a timeout value sooner than any installed timeout if + * only higher-order wheels have timeouts pending. We can only know when to + * process a wheel, not precisely when a timeout is scheduled. Our timeout + * accuracy could be off by 2^(N*M)-1 units where N is the wheel number and + * M is WHEEL_BIT. Only timeouts which have fallen through to wheel 0 can be + * known exactly. + * + * We should never return a timeout larger than the lowest actual timeout. + */ +static timeout_t timeouts_int(struct timeouts *T) { + timeout_t timeout = ~TIMEOUT_C(0), _timeout; + timeout_t relmask; + int wheel, slot; + + relmask = 0; + + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + if (T->pending[wheel]) { + slot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT)); + + /* ctz input cannot be zero: T->pending[wheel] is + * nonzero, so rotr() is nonzero. */ + _timeout = (ctz(rotr(T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT); + /* +1 to higher order wheels as those timeouts are one rotation in the future (otherwise they'd be on a lower wheel or expired) */ + + _timeout -= relmask & T->curtime; + /* reduce by how much lower wheels have progressed */ + + timeout = MIN(_timeout, timeout); + } + + relmask <<= WHEEL_BIT; + relmask |= WHEEL_MASK; + } + + return timeout; +} /* timeouts_int() */ + + +/* + * Calculate the interval our caller can wait before needing to process + * events. + */ +TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) { + if (!TOR_TAILQ_EMPTY(&T->expired)) + return 0; + + return timeouts_int(T); +} /* timeouts_timeout() */ + + +TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) { + if (!TOR_TAILQ_EMPTY(&T->expired)) { + struct timeout *to = TOR_TAILQ_FIRST(&T->expired); + + TOR_TAILQ_REMOVE(&T->expired, to, tqe); + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + +#ifndef TIMEOUT_DISABLE_INTERVALS + if ((to->flags & TIMEOUT_INT) && to->interval > 0) + timeouts_readd(T, to); +#endif + + return to; + } else { + return 0; + } +} /* timeouts_get() */ + + +/* + * Use dumb looping to locate the earliest timeout pending on the wheel so + * our invariant assertions can check the result of our optimized code. + */ +static struct timeout *timeouts_min(struct timeouts *T) { + struct timeout *to, *min = NULL; + unsigned i, j; + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TOR_TAILQ_FOREACH(to, &T->wheel[i][j], tqe) { + if (!min || to->expires < min->expires) + min = to; + } + } + } + + return min; +} /* timeouts_min() */ + + +/* + * Check some basic algorithm invariants. If these invariants fail then + * something is definitely broken. + */ +#define report(...) do { \ + if ((fp)) \ + fprintf(fp, __VA_ARGS__); \ +} while (0) + +#define check(expr, ...) do { \ + if (!(expr)) { \ + report(__VA_ARGS__); \ + return 0; \ + } \ +} while (0) + +TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *T, FILE *fp) { + timeout_t timeout; + struct timeout *to; + + if ((to = timeouts_min(T))) { + check(to->expires > T->curtime, "missed timeout (expires:%" TIMEOUT_PRIu " <= curtime:%" TIMEOUT_PRIu ")\n", to->expires, T->curtime); + + timeout = timeouts_int(T); + check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime); + + timeout = timeouts_timeout(T); + check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime); + } else { + timeout = timeouts_timeout(T); + + if (!TOR_TAILQ_EMPTY(&T->expired)) + check(timeout == 0, "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, TIMEOUT_C(0)); + else + check(timeout == ~TIMEOUT_C(0), "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, ~TIMEOUT_C(0)); + } + + return 1; +} /* timeouts_check() */ + + +#define ENTER \ + do { \ + static const int pc0 = __LINE__; \ + switch (pc0 + it->pc) { \ + case __LINE__: (void)0 + +#define SAVE_AND_DO(do_statement) \ + do { \ + it->pc = __LINE__ - pc0; \ + do_statement; \ + case __LINE__: (void)0; \ + } while (0) + +#define YIELD(rv) \ + SAVE_AND_DO(return (rv)) + +#define LEAVE \ + SAVE_AND_DO(break); \ + } \ + } while (0) + +TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *T, struct timeouts_it *it) { + struct timeout *to; + + ENTER; + + if (it->flags & TIMEOUTS_EXPIRED) { + if (it->flags & TIMEOUTS_CLEAR) { + while ((to = timeouts_get(T))) { + YIELD(to); + } + } else { + TOR_TAILQ_FOREACH_SAFE(to, &T->expired, tqe, it->to) { + YIELD(to); + } + } + } + + if (it->flags & TIMEOUTS_PENDING) { + for (it->i = 0; it->i < countof(T->wheel); it->i++) { + for (it->j = 0; it->j < countof(T->wheel[it->i]); it->j++) { + TOR_TAILQ_FOREACH_SAFE(to, &T->wheel[it->i][it->j], tqe, it->to) { + YIELD(to); + } + } + } + } + + LEAVE; + + return NULL; +} /* timeouts_next */ + +#undef LEAVE +#undef YIELD +#undef SAVE_AND_DO +#undef ENTER + + +/* + * T I M E O U T R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) { + memset(to, 0, sizeof *to); + + to->flags = flags; + + return to; +} /* timeout_init() */ + + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS +TIMEOUT_PUBLIC bool timeout_pending(struct timeout *to) { + return to->pending && to->pending != &to->timeouts->expired; +} /* timeout_pending() */ + + +TIMEOUT_PUBLIC bool timeout_expired(struct timeout *to) { + return to->pending && to->pending == &to->timeouts->expired; +} /* timeout_expired() */ + + +TIMEOUT_PUBLIC void timeout_del(struct timeout *to) { + timeouts_del(to->timeouts, to); +} /* timeout_del() */ +#endif + + +/* + * V E R S I O N I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TIMEOUT_PUBLIC int timeout_version(void) { + return TIMEOUT_VERSION; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC const char *timeout_vendor(void) { + return TIMEOUT_VENDOR; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_rel(void) { + return TIMEOUT_V_REL; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_abi(void) { + return TIMEOUT_V_ABI; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_api(void) { + return TIMEOUT_V_API; +} /* timeout_version() */ + diff --git a/src/ext/timeouts/timeout.h b/src/ext/timeouts/timeout.h new file mode 100644 index 0000000000..b35874e153 --- /dev/null +++ b/src/ext/timeouts/timeout.h @@ -0,0 +1,256 @@ +/* ========================================================================== + * timeout.h - Tickless hierarchical timing wheel. + * -------------------------------------------------------------------------- + * Copyright (c) 2013, 2014 William Ahern + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * ========================================================================== + */ +#ifndef TIMEOUT_H +#define TIMEOUT_H + +#include <stdbool.h> /* bool */ +#include <stdio.h> /* FILE */ + +#include <inttypes.h> /* PRIu64 PRIx64 PRIX64 uint64_t */ + +#include "tor_queue.h" /* TAILQ(3) */ + + +/* + * V E R S I O N I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if !defined TIMEOUT_PUBLIC +#define TIMEOUT_PUBLIC +#endif + +#define TIMEOUT_VERSION TIMEOUT_V_REL +#define TIMEOUT_VENDOR "william@25thandClement.com" + +#define TIMEOUT_V_REL 0x20160226 +#define TIMEOUT_V_ABI 0x20160224 +#define TIMEOUT_V_API 0x20160226 + +TIMEOUT_PUBLIC int timeout_version(void); + +TIMEOUT_PUBLIC const char *timeout_vendor(void); + +TIMEOUT_PUBLIC int timeout_v_rel(void); + +TIMEOUT_PUBLIC int timeout_v_abi(void); + +TIMEOUT_PUBLIC int timeout_v_api(void); + + +/* + * I N T E G E R T Y P E I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#define TIMEOUT_C(n) UINT64_C(n) +#define TIMEOUT_PRIu PRIu64 +#define TIMEOUT_PRIx PRIx64 +#define TIMEOUT_PRIX PRIX64 + +#define TIMEOUT_mHZ TIMEOUT_C(1000) +#define TIMEOUT_uHZ TIMEOUT_C(1000000) +#define TIMEOUT_nHZ TIMEOUT_C(1000000000) + +typedef uint64_t timeout_t; + +#define timeout_error_t int /* for documentation purposes */ + + +/* + * C A L L B A C K I N T E R F A C E + * + * Callback function parameters unspecified to make embedding into existing + * applications easier. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#ifndef TIMEOUT_CB_OVERRIDE +struct timeout_cb { + void (*fn)(void); + void *arg; +}; /* struct timeout_cb */ +#endif + +/* + * T I M E O U T I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#ifndef TIMEOUT_DISABLE_INTERVALS +#define TIMEOUT_INT 0x01 /* interval (repeating) timeout */ +#endif +#define TIMEOUT_ABS 0x02 /* treat timeout values as absolute */ + +#define TIMEOUT_INITIALIZER(flags) { (flags) } + +#define timeout_setcb(to, fn, arg) do { \ + (to)->callback.fn = (fn); \ + (to)->callback.arg = (arg); \ +} while (0) + +struct timeout { + int flags; + + timeout_t expires; + /* absolute expiration time */ + + struct timeout_list *pending; + /* timeout list if pending on wheel or expiry queue */ + + TOR_TAILQ_ENTRY(timeout) tqe; + /* entry member for struct timeout_list lists */ + +#ifndef TIMEOUT_DISABLE_CALLBACKS + struct timeout_cb callback; + /* optional callback information */ +#endif + +#ifndef TIMEOUT_DISABLE_INTERVALS + timeout_t interval; + /* timeout interval if periodic */ +#endif + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS + struct timeouts *timeouts; + /* timeouts collection if member of */ +#endif +}; /* struct timeout */ + + +TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int); +/* initialize timeout structure (same as TIMEOUT_INITIALIZER) */ + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS +TIMEOUT_PUBLIC bool timeout_pending(struct timeout *); +/* true if on timing wheel, false otherwise */ + +TIMEOUT_PUBLIC bool timeout_expired(struct timeout *); +/* true if on expired queue, false otherwise */ + +TIMEOUT_PUBLIC void timeout_del(struct timeout *); +/* remove timeout from any timing wheel (okay if not member of any) */ +#endif + +/* + * T I M I N G W H E E L I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +struct timeouts; + +TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *); +/* open a new timing wheel, setting optional HZ (for float conversions) */ + +TIMEOUT_PUBLIC void timeouts_close(struct timeouts *); +/* destroy timing wheel */ + +TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *); +/* return HZ setting (for float conversions) */ + +TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t); +/* update timing wheel with current absolute time */ + +TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t); +/* step timing wheel by relative time */ + +TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *); +/* Return the current tick. */ + +TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *); +/* return interval to next required update */ + +TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t); +/* add timeout to timing wheel */ + +TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *); +/* remove timeout from any timing wheel or expired queue (okay if on neither) */ + +TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *); +/* return any expired timeout (caller should loop until NULL-return) */ + +TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *); +/* return true if any timeouts pending on timing wheel */ + +TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *); +/* return true if any timeouts on expired queue */ + +TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *, FILE *); +/* return true if invariants hold. describes failures to optional file handle. */ + +#define TIMEOUTS_PENDING 0x10 +#define TIMEOUTS_EXPIRED 0x20 +#define TIMEOUTS_ALL (TIMEOUTS_PENDING|TIMEOUTS_EXPIRED) +#define TIMEOUTS_CLEAR 0x40 + +#define TIMEOUTS_IT_INITIALIZER(flags) { (flags), 0, 0, 0, 0 } + +#define TIMEOUTS_IT_INIT(cur, _flags) do { \ + (cur)->flags = (_flags); \ + (cur)->pc = 0; \ +} while (0) + +struct timeouts_it { + int flags; + unsigned pc, i, j; + struct timeout *to; +}; /* struct timeouts_it */ + +TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *, struct timeouts_it *); +/* return next timeout in pending wheel or expired queue. caller can delete + * the returned timeout, but should not otherwise manipulate the timing + * wheel. in particular, caller SHOULD NOT delete any other timeout as that + * could invalidate cursor state and trigger a use-after-free. + */ + +#define TIMEOUTS_FOREACH(var, T, flags) \ + struct timeouts_it _it = TIMEOUTS_IT_INITIALIZER((flags)); \ + while (((var) = timeouts_next((T), &_it))) + + +/* + * B O N U S W H E E L I N T E R F A C E S + * + * I usually use floating point timeouts in all my code, but it's cleaner to + * separate it to keep the core algorithmic code simple. + * + * Using macros instead of static inline routines where <math.h> routines + * might be used to keep -lm linking optional. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#include <math.h> /* ceil(3) */ + +#define timeouts_f2i(T, f) \ + ((timeout_t)ceil((f) * timeouts_hz((T)))) /* prefer late expiration over early */ + +#define timeouts_i2f(T, i) \ + ((double)(i) / timeouts_hz((T))) + +#define timeouts_addf(T, to, timeout) \ + timeouts_add((T), (to), timeouts_f2i((T), (timeout))) + +#endif /* TIMEOUT_H */ diff --git a/src/or/buffers.c b/src/or/buffers.c index f93cc48f33..cdc71ab9db 100644 --- a/src/or/buffers.c +++ b/src/or/buffers.c @@ -107,7 +107,7 @@ chunk_repack(chunk_t *chunk) /** Keep track of total size of allocated chunks for consistency asserts */ static size_t total_bytes_allocated_in_chunks = 0; static void -chunk_free_unchecked(chunk_t *chunk) +buf_chunk_free_unchecked(chunk_t *chunk) { if (!chunk) return; @@ -228,7 +228,7 @@ buf_pullup(buf_t *buf, size_t bytes) dest->next = src->next; if (buf->tail == src) buf->tail = dest; - chunk_free_unchecked(src); + buf_chunk_free_unchecked(src); } else { memcpy(CHUNK_WRITE_PTR(dest), src->data, n); dest->datalen += n; @@ -274,7 +274,7 @@ buf_remove_from_front(buf_t *buf, size_t n) buf->head = victim->next; if (buf->tail == victim) buf->tail = NULL; - chunk_free_unchecked(victim); + buf_chunk_free_unchecked(victim); } } check(); @@ -314,7 +314,7 @@ buf_clear(buf_t *buf) buf->datalen = 0; for (chunk = buf->head; chunk; chunk = next) { next = chunk->next; - chunk_free_unchecked(chunk); + buf_chunk_free_unchecked(chunk); } buf->head = buf->tail = NULL; } diff --git a/src/or/channel.c b/src/or/channel.c index 5f69a0864b..f3939399b0 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -3510,7 +3510,7 @@ channel_dump_statistics, (channel_t *chan, int severity)) have_remote_addr = channel_get_addr_if_possible(chan, &remote_addr); if (have_remote_addr) { char *actual = tor_strdup(channel_get_actual_remote_descr(chan)); - remote_addr_str = tor_dup_addr(&remote_addr); + remote_addr_str = tor_addr_to_str_dup(&remote_addr); tor_log(severity, LD_GENERAL, " * Channel " U64_FORMAT " says its remote address" " is %s, and gives a canonical description of \"%s\" and an " diff --git a/src/or/channel.h b/src/or/channel.h index 129c0c2013..a8c337e107 100644 --- a/src/or/channel.h +++ b/src/or/channel.h @@ -18,7 +18,7 @@ typedef void (*channel_cell_handler_fn_ptr)(channel_t *, cell_t *); typedef void (*channel_var_cell_handler_fn_ptr)(channel_t *, var_cell_t *); struct cell_queue_entry_s; -TOR_SIMPLEQ_HEAD(chan_cell_queue, cell_queue_entry_s) incoming_queue; +TOR_SIMPLEQ_HEAD(chan_cell_queue, cell_queue_entry_s); typedef struct chan_cell_queue chan_cell_queue_t; /** diff --git a/src/or/channeltls.c b/src/or/channeltls.c index c65af5d040..2128b0924d 100644 --- a/src/or/channeltls.c +++ b/src/or/channeltls.c @@ -554,7 +554,7 @@ channel_tls_get_remote_descr_method(channel_t *chan, int flags) break; case GRD_FLAG_ORIGINAL: /* Actual address with port */ - addr_str = tor_dup_addr(&(tlschan->conn->real_addr)); + addr_str = tor_addr_to_str_dup(&(tlschan->conn->real_addr)); tor_snprintf(buf, MAX_DESCR_LEN + 1, "%s:%u", addr_str, conn->port); tor_free(addr_str); @@ -567,7 +567,7 @@ channel_tls_get_remote_descr_method(channel_t *chan, int flags) break; case GRD_FLAG_ORIGINAL|GRD_FLAG_ADDR_ONLY: /* Actual address, no port */ - addr_str = tor_dup_addr(&(tlschan->conn->real_addr)); + addr_str = tor_addr_to_str_dup(&(tlschan->conn->real_addr)); strlcpy(buf, addr_str, sizeof(buf)); tor_free(addr_str); answer = buf; diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index a5a933e6b0..e6fe3f0c37 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -47,10 +47,6 @@ #include "routerset.h" #include "crypto.h" -#ifndef MIN -#define MIN(a,b) ((a)<(b)?(a):(b)) -#endif - static channel_t * channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port, const char *id_digest); diff --git a/src/or/circuituse.c b/src/or/circuituse.c index a4b580104f..246f6c50c9 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -1067,7 +1067,7 @@ circuit_predict_and_launch_new(void) if (rep_hist_get_predicted_internal(now, &hidserv_needs_uptime, &hidserv_needs_capacity) && ((num_uptime_internal<2 && hidserv_needs_uptime) || - num_internal<2) + num_internal<3) && router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN) { if (hidserv_needs_uptime) flags |= CIRCLAUNCH_NEED_UPTIME; @@ -2145,10 +2145,11 @@ optimistic_data_enabled(void) { const or_options_t *options = get_options(); if (options->OptimisticData < 0) { - /* XXX023 consider having auto default to 1 rather than 0 before - * the 0.2.3 branch goes stable. See bug 3617. -RD */ + /* Note: this default was 0 before #18815 was merged. We can't take the + * parameter out of the consensus until versions before that are all + * obsolete. */ const int32_t enabled = - networkstatus_get_param(NULL, "UseOptimisticData", 0, 0, 1); + networkstatus_get_param(NULL, "UseOptimisticData", /*default*/ 1, 0, 1); return (int)enabled; } return options->OptimisticData; diff --git a/src/or/config.c b/src/or/config.c index 5d938d101a..2e14ba69dc 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -2796,7 +2796,8 @@ options_validate(or_options_t *old_options, or_options_t *options, } else { if (!is_legal_nickname(options->Nickname)) { tor_asprintf(msg, - "Nickname '%s' is wrong length or contains illegal characters.", + "Nickname '%s', nicknames must be between 1 and 19 characters " + "inclusive, and must contain only the characters [a-zA-Z0-9].", options->Nickname); return -1; } diff --git a/src/or/connection.c b/src/or/connection.c index 118e239176..1bd1a92e39 100644 --- a/src/or/connection.c +++ b/src/or/connection.c @@ -665,9 +665,7 @@ connection_free,(connection_t *conn)) return; tor_assert(!connection_is_on_closeable_list(conn)); tor_assert(!connection_in_array(conn)); - if (conn->linked_conn) { - log_err(LD_BUG, "Called with conn->linked_conn still set."); - tor_fragile_assert(); + if (BUG(conn->linked_conn)) { conn->linked_conn->linked_conn = NULL; if (! conn->linked_conn->marked_for_close && conn->linked_conn->reading_from_linked_conn) @@ -1564,7 +1562,7 @@ connection_handle_listener_read(connection_t *conn, int new_type) /* remember the remote address */ tor_addr_copy(&newconn->addr, &addr); newconn->port = port; - newconn->address = tor_dup_addr(&addr); + newconn->address = tor_addr_to_str_dup(&addr); if (new_type == CONN_TYPE_AP && conn->socket_family != AF_UNIX) { log_info(LD_NET, "New SOCKS connection opened from %s.", @@ -2538,7 +2536,7 @@ retry_listener_ports(smartlist_t *old_conns, real_port, listensockaddr, sizeof(struct sockaddr_storage)); - address = tor_dup_addr(&port->addr); + address = tor_addr_to_str_dup(&port->addr); } if (listensockaddr) { @@ -3644,7 +3642,7 @@ connection_read_to_buf(connection_t *conn, ssize_t *max_to_read, * take us over our read allotment, but really we shouldn't be * believing that SSL bytes are the same as TCP bytes anyway. */ int r2 = read_to_buf_tls(or_conn->tls, pending, conn->inbuf); - if (r2<0) { + if (BUG(r2<0)) { log_warn(LD_BUG, "apparently, reading pending bytes can fail."); return -1; } diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index 754e9762ea..e58d32e7a5 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -1691,7 +1691,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn, rend_service_authorization_t *client_auth = rend_client_lookup_service_authorization(socks->address); - const char *cookie = NULL; + const uint8_t *cookie = NULL; rend_auth_type_t auth_type = REND_NO_AUTH; if (client_auth) { log_info(LD_REND, "Using previously configured client authorization " @@ -1703,7 +1703,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn, /* Fill in the rend_data field so we can start doing a connection to * a hidden service. */ rend_data_t *rend_data = ENTRY_TO_EDGE_CONN(conn)->rend_data = - rend_data_client_create(socks->address, NULL, cookie, auth_type); + rend_data_client_create(socks->address, NULL, (char *) cookie, auth_type); if (rend_data == NULL) { return -1; } @@ -2433,7 +2433,7 @@ connection_ap_handshake_send_resolve(entry_connection_t *ap_conn) if (!base_conn->address) { /* This might be unnecessary. XXXX */ - base_conn->address = tor_dup_addr(&base_conn->addr); + base_conn->address = tor_addr_to_str_dup(&base_conn->addr); } base_conn->state = AP_CONN_STATE_RESOLVE_WAIT; log_info(LD_APP,"Address sent for resolve, ap socket "TOR_SOCKET_T_FORMAT diff --git a/src/or/connection_or.c b/src/or/connection_or.c index ea49bdba77..f8be763792 100644 --- a/src/or/connection_or.c +++ b/src/or/connection_or.c @@ -934,7 +934,7 @@ connection_or_init_conn_from_address(or_connection_t *conn, } conn->nickname = tor_strdup(node_get_nickname(r)); tor_free(conn->base_.address); - conn->base_.address = tor_dup_addr(&node_ap.addr); + conn->base_.address = tor_addr_to_str_dup(&node_ap.addr); } else { conn->nickname = tor_malloc(HEX_DIGEST_LEN+2); conn->nickname[0] = '$'; @@ -942,7 +942,7 @@ connection_or_init_conn_from_address(or_connection_t *conn, conn->identity_digest, DIGEST_LEN); tor_free(conn->base_.address); - conn->base_.address = tor_dup_addr(addr); + conn->base_.address = tor_addr_to_str_dup(addr); } /* @@ -1281,11 +1281,9 @@ connection_or_connect, (const tor_addr_t *_addr, uint16_t port, switch (connection_connect(TO_CONN(conn), conn->base_.address, &addr, port, &socket_error)) { case -1: - /* If the connection failed immediately, and we're using - * a proxy, our proxy is down. Don't blame the Tor server. */ - if (conn->base_.proxy_state == PROXY_INFANT) - entry_guard_register_connect_status(conn->identity_digest, - 0, 1, time(NULL)); + /* We failed to establish a connection probably because of a local + * error. No need to blame the guard in this case. Notify the networking + * system of this failure. */ connection_or_connect_failed(conn, errno_to_orconn_end_reason(socket_error), tor_socket_strerror(socket_error)); diff --git a/src/or/control.c b/src/or/control.c index e06d7d28a2..862c836e40 100644 --- a/src/or/control.c +++ b/src/or/control.c @@ -3788,14 +3788,18 @@ handle_control_add_onion(control_connection_t *conn, * the other arguments are malformed. */ smartlist_t *port_cfgs = smartlist_new(); + smartlist_t *auth_clients = NULL; + smartlist_t *auth_created_clients = NULL; int discard_pk = 0; int detach = 0; int max_streams = 0; int max_streams_close_circuit = 0; + rend_auth_type_t auth_type = REND_NO_AUTH; for (size_t i = 1; i < arg_len; i++) { static const char *port_prefix = "Port="; static const char *flags_prefix = "Flags="; static const char *max_s_prefix = "MaxStreams="; + static const char *auth_prefix = "ClientAuth="; const char *arg = smartlist_get(args, i); if (!strcasecmpstart(arg, port_prefix)) { @@ -3826,10 +3830,12 @@ handle_control_add_onion(control_connection_t *conn, * connection. * * 'MaxStreamsCloseCircuit' - Close the circuit if MaxStreams is * exceeded. + * * 'BasicAuth' - Client authorization using the 'basic' method. */ static const char *discard_flag = "DiscardPK"; static const char *detach_flag = "Detach"; static const char *max_s_close_flag = "MaxStreamsCloseCircuit"; + static const char *basicauth_flag = "BasicAuth"; smartlist_t *flags = smartlist_new(); int bad = 0; @@ -3848,6 +3854,8 @@ handle_control_add_onion(control_connection_t *conn, detach = 1; } else if (!strcasecmp(flag, max_s_close_flag)) { max_streams_close_circuit = 1; + } else if (!strcasecmp(flag, basicauth_flag)) { + auth_type = REND_BASIC_AUTH; } else { connection_printf_to_buf(conn, "512 Invalid 'Flags' argument: %s\r\n", @@ -3860,6 +3868,42 @@ handle_control_add_onion(control_connection_t *conn, smartlist_free(flags); if (bad) goto out; + } else if (!strcasecmpstart(arg, auth_prefix)) { + char *err_msg = NULL; + int created = 0; + rend_authorized_client_t *client = + add_onion_helper_clientauth(arg + strlen(auth_prefix), + &created, &err_msg); + if (!client) { + if (err_msg) { + connection_write_str_to_buf(err_msg, conn); + tor_free(err_msg); + } + goto out; + } + + if (auth_clients != NULL) { + int bad = 0; + SMARTLIST_FOREACH_BEGIN(auth_clients, rend_authorized_client_t *, ac) { + if (strcmp(ac->client_name, client->client_name) == 0) { + bad = 1; + break; + } + } SMARTLIST_FOREACH_END(ac); + if (bad) { + connection_printf_to_buf(conn, + "512 Duplicate name in ClientAuth\r\n"); + rend_authorized_client_free(client); + goto out; + } + } else { + auth_clients = smartlist_new(); + auth_created_clients = smartlist_new(); + } + smartlist_add(auth_clients, client); + if (created) { + smartlist_add(auth_created_clients, client); + } } else { connection_printf_to_buf(conn, "513 Invalid argument\r\n"); goto out; @@ -3868,6 +3912,18 @@ handle_control_add_onion(control_connection_t *conn, if (smartlist_len(port_cfgs) == 0) { connection_printf_to_buf(conn, "512 Missing 'Port' argument\r\n"); goto out; + } else if (auth_type == REND_NO_AUTH && auth_clients != NULL) { + connection_printf_to_buf(conn, "512 No auth type specified\r\n"); + goto out; + } else if (auth_type != REND_NO_AUTH && auth_clients == NULL) { + connection_printf_to_buf(conn, "512 No auth clients specified\r\n"); + goto out; + } else if ((auth_type == REND_BASIC_AUTH && + smartlist_len(auth_clients) > 512) || + (auth_type == REND_STEALTH_AUTH && + smartlist_len(auth_clients) > 16)) { + connection_printf_to_buf(conn, "512 Too many auth clients\r\n"); + goto out; } /* Parse the "keytype:keyblob" argument. */ @@ -3888,35 +3944,21 @@ handle_control_add_onion(control_connection_t *conn, } tor_assert(!err_msg); - /* Create the HS, using private key pk, and port config port_cfg. + /* Create the HS, using private key pk, client authentication auth_type, + * the list of auth_clients, and port config port_cfg. * rend_service_add_ephemeral() will take ownership of pk and port_cfg, * regardless of success/failure. */ char *service_id = NULL; int ret = rend_service_add_ephemeral(pk, port_cfgs, max_streams, max_streams_close_circuit, + auth_type, auth_clients, &service_id); port_cfgs = NULL; /* port_cfgs is now owned by the rendservice code. */ + auth_clients = NULL; /* so is auth_clients */ switch (ret) { case RSAE_OKAY: { - char *buf = NULL; - tor_assert(service_id); - if (key_new_alg) { - tor_assert(key_new_blob); - tor_asprintf(&buf, - "250-ServiceID=%s\r\n" - "250-PrivateKey=%s:%s\r\n" - "250 OK\r\n", - service_id, - key_new_alg, - key_new_blob); - } else { - tor_asprintf(&buf, - "250-ServiceID=%s\r\n" - "250 OK\r\n", - service_id); - } if (detach) { if (!detached_onion_services) detached_onion_services = smartlist_new(); @@ -3927,9 +3969,26 @@ handle_control_add_onion(control_connection_t *conn, smartlist_add(conn->ephemeral_onion_services, service_id); } - connection_write_str_to_buf(buf, conn); - memwipe(buf, 0, strlen(buf)); - tor_free(buf); + tor_assert(service_id); + connection_printf_to_buf(conn, "250-ServiceID=%s\r\n", service_id); + if (key_new_alg) { + tor_assert(key_new_blob); + connection_printf_to_buf(conn, "250-PrivateKey=%s:%s\r\n", + key_new_alg, key_new_blob); + } + if (auth_created_clients) { + SMARTLIST_FOREACH(auth_created_clients, rend_authorized_client_t *, ac, { + char *encoded = rend_auth_encode_cookie(ac->descriptor_cookie, + auth_type); + tor_assert(encoded); + connection_printf_to_buf(conn, "250-ClientAuth=%s:%s\r\n", + ac->client_name, encoded); + memwipe(encoded, 0, strlen(encoded)); + tor_free(encoded); + }); + } + + connection_printf_to_buf(conn, "250 OK\r\n"); break; } case RSAE_BADPRIVKEY: @@ -3941,6 +4000,9 @@ handle_control_add_onion(control_connection_t *conn, case RSAE_BADVIRTPORT: connection_printf_to_buf(conn, "512 Invalid VIRTPORT/TARGET\r\n"); break; + case RSAE_BADAUTH: + connection_printf_to_buf(conn, "512 Invalid client authorization\r\n"); + break; case RSAE_INTERNAL: /* FALLSTHROUGH */ default: connection_printf_to_buf(conn, "551 Failed to add Onion Service\r\n"); @@ -3957,6 +4019,16 @@ handle_control_add_onion(control_connection_t *conn, smartlist_free(port_cfgs); } + if (auth_clients) { + SMARTLIST_FOREACH(auth_clients, rend_authorized_client_t *, ac, + rend_authorized_client_free(ac)); + smartlist_free(auth_clients); + } + if (auth_created_clients) { + // Do not free entries; they are the same as auth_clients + smartlist_free(auth_created_clients); + } + SMARTLIST_FOREACH(args, char *, cp, { memwipe(cp, 0, strlen(cp)); tor_free(cp); @@ -4065,6 +4137,65 @@ add_onion_helper_keyarg(const char *arg, int discard_pk, return pk; } +/** Helper function to handle parsing a ClientAuth argument to the + * ADD_ONION command. Return a new rend_authorized_client_t, or NULL + * and an optional control protocol error message on failure. The + * caller is responsible for freeing the returned auth_client and err_msg. + * + * If 'created' is specified, it will be set to 1 when a new cookie has + * been generated. + */ +STATIC rend_authorized_client_t * +add_onion_helper_clientauth(const char *arg, int *created, char **err_msg) +{ + int ok = 0; + + tor_assert(arg); + tor_assert(created); + tor_assert(err_msg); + *err_msg = NULL; + + smartlist_t *auth_args = smartlist_new(); + rend_authorized_client_t *client = + tor_malloc_zero(sizeof(rend_authorized_client_t)); + smartlist_split_string(auth_args, arg, ":", 0, 0); + if (smartlist_len(auth_args) < 1 || smartlist_len(auth_args) > 2) { + *err_msg = tor_strdup("512 Invalid ClientAuth syntax\r\n"); + goto err; + } + client->client_name = tor_strdup(smartlist_get(auth_args, 0)); + if (smartlist_len(auth_args) == 2) { + char *decode_err_msg = NULL; + if (rend_auth_decode_cookie(smartlist_get(auth_args, 1), + client->descriptor_cookie, + NULL, &decode_err_msg) < 0) { + tor_assert(decode_err_msg); + tor_asprintf(err_msg, "512 %s\r\n", decode_err_msg); + tor_free(decode_err_msg); + goto err; + } + *created = 0; + } else { + crypto_rand((char *) client->descriptor_cookie, REND_DESC_COOKIE_LEN); + *created = 1; + } + + if (!rend_valid_client_name(client->client_name)) { + *err_msg = tor_strdup("512 Invalid name in ClientAuth\r\n"); + goto err; + } + + ok = 1; + err: + SMARTLIST_FOREACH(auth_args, char *, arg, tor_free(arg)); + smartlist_free(auth_args); + if (!ok) { + rend_authorized_client_free(client); + client = NULL; + } + return client; +} + /** Called when we get a DEL_ONION command; parse the body, and remove * the existing ephemeral Onion Service. */ static int diff --git a/src/or/control.h b/src/or/control.h index 008bfb1c3b..b3902e64bd 100644 --- a/src/or/control.h +++ b/src/or/control.h @@ -259,6 +259,8 @@ STATIC crypto_pk_t *add_onion_helper_keyarg(const char *arg, int discard_pk, const char **key_new_alg_out, char **key_new_blob_out, char **err_msg_out); +STATIC rend_authorized_client_t * +add_onion_helper_clientauth(const char *arg, int *created, char **err_msg_out); #endif #endif diff --git a/src/or/directory.c b/src/or/directory.c index 8dc018a662..a3ade8f164 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -1181,7 +1181,7 @@ directory_initiate_command_rend(const tor_addr_port_t *or_addr_port, /* set up conn so it's got all the data we need to remember */ tor_addr_copy(&conn->base_.addr, &addr); conn->base_.port = port; - conn->base_.address = tor_dup_addr(&addr); + conn->base_.address = tor_addr_to_str_dup(&addr); memcpy(conn->identity_digest, digest, DIGEST_LEN); conn->base_.purpose = dir_purpose; @@ -2854,18 +2854,84 @@ choose_compression_level(ssize_t n_bytes) } } +/** Information passed to handle a GET request. */ +typedef struct get_handler_args_t { + /** True if the client asked for compressed data. */ + int compressed; + /** If nonzero, the time included an if-modified-since header with this + * value. */ + time_t if_modified_since; + /** String containing the requested URL or resource. */ + const char *url; + /** String containing the HTTP headers */ + const char *headers; +} get_handler_args_t; + +/** Entry for handling an HTTP GET request. + * + * This entry matches a request if "string" is equal to the requested + * resource, or if "is_prefix" is true and "string" is a prefix of the + * requested resource. + * + * The 'handler' function is called to handle the request. It receives + * an arguments structure, and must return 0 on success or -1 if we should + * close the connection. + **/ +typedef struct url_table_ent_s { + const char *string; + int is_prefix; + int (*handler)(dir_connection_t *conn, const get_handler_args_t *args); +} url_table_ent_t; + +static int handle_get_frontpage(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_current_consensus(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_status_vote(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_microdesc(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_descriptor(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_keys(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_rendezvous2(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_bytes(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_robots(dir_connection_t *conn, + const get_handler_args_t *args); +static int handle_get_networkstatus_bridges(dir_connection_t *conn, + const get_handler_args_t *args); + +/** Table for handling GET requests. */ +static const url_table_ent_t url_table[] = { + { "/tor/", 0, handle_get_frontpage }, + { "/tor/status-vote/current/consensus", 1, handle_get_current_consensus }, + { "/tor/status-vote/current/", 1, handle_get_status_vote }, + { "/tor/status-vote/next/", 1, handle_get_status_vote }, + { "/tor/micro/d/", 1, handle_get_microdesc }, + { "/tor/server/", 1, handle_get_descriptor }, + { "/tor/extra/", 1, handle_get_descriptor }, + { "/tor/keys/", 1, handle_get_keys }, + { "/tor/rendezvous2/", 1, handle_get_rendezvous2 }, + { "/tor/bytes.txt", 0, handle_get_bytes }, + { "/tor/robots.txt", 0, handle_get_robots }, + { "/tor/networkstatus-bridges", 0, handle_get_networkstatus_bridges }, + { NULL, 0, NULL }, +}; + /** Helper function: called when a dirserver gets a complete HTTP GET * request. Look for a request for a directory or for a rendezvous * service descriptor. On finding one, write a response into - * conn-\>outbuf. If the request is unrecognized, send a 400. - * Always return 0. */ + * conn-\>outbuf. If the request is unrecognized, send a 404. + * Return 0 if we handled this successfully, or -1 if we need to close + * the connection. */ STATIC int directory_handle_command_get(dir_connection_t *conn, const char *headers, const char *req_body, size_t req_body_len) { - size_t dlen; char *url, *url_mem, *header; - const or_options_t *options = get_options(); time_t if_modified_since = 0; int compressed; size_t url_len; @@ -2905,10 +2971,46 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, url_len -= 2; } - if (!strcmp(url,"/tor/")) { + get_handler_args_t args; + args.url = url; + args.headers = headers; + args.if_modified_since = if_modified_since; + args.compressed = compressed; + + int i, result = -1; + for (i = 0; url_table[i].string; ++i) { + int match; + if (url_table[i].is_prefix) { + match = !strcmpstart(url, url_table[i].string); + } else { + match = !strcmp(url, url_table[i].string); + } + if (match) { + result = url_table[i].handler(conn, &args); + goto done; + } + } + + /* we didn't recognize the url */ + write_http_status_line(conn, 404, "Not found"); + result = 0; + + done: + tor_free(url_mem); + return result; +} + +/** Helper function for GET / or GET /tor/ + */ +static int +handle_get_frontpage(dir_connection_t *conn, const get_handler_args_t *args) +{ + const char *url = args->url; + { const char *frontpage = get_dirportfrontpage(); if (frontpage) { + size_t dlen; dlen = strlen(frontpage); /* Let's return a disclaimer page (users shouldn't use V1 anymore, and caches don't fetch '/', so this is safe). */ @@ -2919,12 +3021,24 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, write_http_response_header_impl(conn, dlen, "text/html", "identity", NULL, DIRPORTFRONTPAGE_CACHE_LIFETIME); connection_write_to_buf(frontpage, dlen, TO_CONN(conn)); - goto done; + } else { + write_http_status_line(conn, 404, "Not found"); } - /* if no disclaimer file, fall through and continue */ } + return 0; +} + +/** Helper function for GET /tor/status-vote/current/consensus + */ +static int +handle_get_current_consensus(dir_connection_t *conn, + const get_handler_args_t *args) +{ + const char *url = args->url; + const int compressed = args->compressed; + const time_t if_modified_since = args->if_modified_since; - if (!strcmpstart(url, "/tor/status-vote/current/consensus")) { + { /* v3 network status fetch. */ smartlist_t *dir_fps = smartlist_new(); const char *request_type = NULL; @@ -3001,7 +3115,7 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, goto done; } - dlen = dirserv_estimate_data_size(dir_fps, 0, compressed); + size_t dlen = dirserv_estimate_data_size(dir_fps, 0, compressed); if (global_write_bucket_low(TO_CONN(conn), dlen, 2)) { log_debug(LD_DIRSERV, "Client asked for network status lists, but we've been " @@ -3045,11 +3159,18 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, goto done; } - if (!strcmpstart(url,"/tor/status-vote/current/") || - !strcmpstart(url,"/tor/status-vote/next/")) { - /* XXXX If-modified-since is only implemented for the current - * consensus: that's probably fine, since it's the only vote document - * people fetch much. */ + done: + return 0; +} + +/** Helper function for GET /tor/status-vote/{current,next}/... + */ +static int +handle_get_status_vote(dir_connection_t *conn, const get_handler_args_t *args) +{ + const char *url = args->url; + const int compressed = args->compressed; + { int current; ssize_t body_len = 0; ssize_t estimated_len = 0; @@ -3145,8 +3266,18 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, smartlist_free(dir_items); goto done; } + done: + return 0; +} - if (!strcmpstart(url, "/tor/micro/d/")) { +/** Helper function for GET /tor/micro/d/... + */ +static int +handle_get_microdesc(dir_connection_t *conn, const get_handler_args_t *args) +{ + const char *url = args->url; + const int compressed = args->compressed; + { smartlist_t *fps = smartlist_new(); dir_split_resource_into_fingerprints(url+strlen("/tor/micro/d/"), @@ -3159,7 +3290,7 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, smartlist_free(fps); goto done; } - dlen = dirserv_estimate_microdesc_size(fps, compressed); + size_t dlen = dirserv_estimate_microdesc_size(fps, compressed); if (global_write_bucket_low(TO_CONN(conn), dlen, 2)) { log_info(LD_DIRSERV, "Client asked for server descriptors, but we've been " @@ -3182,9 +3313,22 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, goto done; } + done: + return 0; +} + +/** Helper function for GET /tor/{server,extra}/... + */ +static int +handle_get_descriptor(dir_connection_t *conn, const get_handler_args_t *args) +{ + const char *url = args->url; + const int compressed = args->compressed; + const or_options_t *options = get_options(); if (!strcmpstart(url,"/tor/server/") || (!options->BridgeAuthoritativeDir && !options->BridgeRelay && !strcmpstart(url,"/tor/extra/"))) { + size_t dlen; int res; const char *msg; const char *request_type = NULL; @@ -3251,8 +3395,19 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, } goto done; } + done: + return 0; +} - if (!strcmpstart(url,"/tor/keys/")) { +/** Helper function for GET /tor/keys/... + */ +static int +handle_get_keys(dir_connection_t *conn, const get_handler_args_t *args) +{ + const char *url = args->url; + const int compressed = args->compressed; + const time_t if_modified_since = args->if_modified_since; + { smartlist_t *certs = smartlist_new(); ssize_t len = -1; if (!strcmp(url, "/tor/keys/all")) { @@ -3337,9 +3492,17 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, smartlist_free(certs); goto done; } + done: + return 0; +} - if (connection_dir_is_encrypted(conn) && - !strcmpstart(url,"/tor/rendezvous2/")) { +/** Helper function for GET /tor/rendezvous2/ + */ +static int +handle_get_rendezvous2(dir_connection_t *conn, const get_handler_args_t *args) +{ + const char *url = args->url; + if (connection_dir_is_encrypted(conn)) { /* Handle v2 rendezvous descriptor fetch request. */ const char *descp; const char *query = url + strlen("/tor/rendezvous2/"); @@ -3362,16 +3525,30 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, write_http_status_line(conn, 400, "Bad request"); } goto done; + } else { + /* Not encrypted! */ + write_http_status_line(conn, 404, "Not found"); } + done: + return 0; +} + +/** Helper function for GET /tor/networkstatus-bridges + */ +static int +handle_get_networkstatus_bridges(dir_connection_t *conn, + const get_handler_args_t *args) +{ + const char *headers = args->headers; + const or_options_t *options = get_options(); if (options->BridgeAuthoritativeDir && options->BridgePassword_AuthDigest_ && - connection_dir_is_encrypted(conn) && - !strcmp(url,"/tor/networkstatus-bridges")) { + connection_dir_is_encrypted(conn)) { char *status; char digest[DIGEST256_LEN]; - header = http_get_header(headers, "Authorization: Basic "); + char *header = http_get_header(headers, "Authorization: Basic "); if (header) crypto_digest256(digest, header, strlen(header), DIGEST_SHA256); @@ -3387,75 +3564,43 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, /* all happy now. send an answer. */ status = networkstatus_getinfo_by_purpose("bridge", time(NULL)); - dlen = strlen(status); + size_t dlen = strlen(status); write_http_response_header(conn, dlen, 0, 0); connection_write_to_buf(status, dlen, TO_CONN(conn)); tor_free(status); goto done; } + done: + return 0; +} - if (!strcmpstart(url,"/tor/bytes.txt")) { +/** Helper function for GET /tor/bytes.txt + */ +static int +handle_get_bytes(dir_connection_t *conn, const get_handler_args_t *args) +{ + (void)args; + { char *bytes = directory_dump_request_log(); size_t len = strlen(bytes); write_http_response_header(conn, len, 0, 0); connection_write_to_buf(bytes, len, TO_CONN(conn)); tor_free(bytes); - goto done; } + return 0; +} - if (!strcmp(url,"/tor/robots.txt")) { /* /robots.txt will have been - rewritten to /tor/robots.txt */ - char robots[] = "User-agent: *\r\nDisallow: /\r\n"; +/** Helper function for GET robots.txt or /tor/robots.txt */ +static int +handle_get_robots(dir_connection_t *conn, const get_handler_args_t *args) +{ + (void)args; + { + const char robots[] = "User-agent: *\r\nDisallow: /\r\n"; size_t len = strlen(robots); write_http_response_header(conn, len, 0, ROBOTS_CACHE_LIFETIME); connection_write_to_buf(robots, len, TO_CONN(conn)); - goto done; } - -#if defined(EXPORTMALLINFO) && defined(HAVE_MALLOC_H) && defined(HAVE_MALLINFO) -#define ADD_MALLINFO_LINE(x) do { \ - smartlist_add_asprintf(lines, "%s %d\n", #x, mi.x); \ - }while(0); - - if (!strcmp(url,"/tor/mallinfo.txt") && - (tor_addr_eq_ipv4h(&conn->base_.addr, 0x7f000001ul))) { - char *result; - size_t len; - struct mallinfo mi; - smartlist_t *lines; - - memset(&mi, 0, sizeof(mi)); - mi = mallinfo(); - lines = smartlist_new(); - - ADD_MALLINFO_LINE(arena) - ADD_MALLINFO_LINE(ordblks) - ADD_MALLINFO_LINE(smblks) - ADD_MALLINFO_LINE(hblks) - ADD_MALLINFO_LINE(hblkhd) - ADD_MALLINFO_LINE(usmblks) - ADD_MALLINFO_LINE(fsmblks) - ADD_MALLINFO_LINE(uordblks) - ADD_MALLINFO_LINE(fordblks) - ADD_MALLINFO_LINE(keepcost) - - result = smartlist_join_strings(lines, "", 0, NULL); - SMARTLIST_FOREACH(lines, char *, cp, tor_free(cp)); - smartlist_free(lines); - - len = strlen(result); - write_http_response_header(conn, len, 0, 0); - connection_write_to_buf(result, len, TO_CONN(conn)); - tor_free(result); - goto done; - } -#endif - - /* we didn't recognize the url */ - write_http_status_line(conn, 404, "Not found"); - - done: - tor_free(url_mem); return 0; } @@ -3703,7 +3848,7 @@ connection_dir_would_close_consensus_conn_helper(void) * consensus, and we are still bootstrapping (that is, we have no usable * consensus), we don't want to close any until one starts downloading. */ if (!networkstatus_consensus_is_downloading_usable_flavor() - && networkstatus_consensus_is_boostrapping(time(NULL))) { + && networkstatus_consensus_is_bootstrapping(time(NULL))) { return 0; } @@ -3737,7 +3882,7 @@ connection_dir_avoid_extra_connection_for_purpose(unsigned int purpose) * bootstrapping (that is, we have no usable consensus), we can be sure that * any further connections would be excess. */ if (networkstatus_consensus_is_downloading_usable_flavor() - && networkstatus_consensus_is_boostrapping(time(NULL))) { + && networkstatus_consensus_is_bootstrapping(time(NULL))) { return 1; } @@ -3778,12 +3923,12 @@ connection_dir_close_consensus_conn_if_extra(dir_connection_t *conn) return 0; } - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( time(NULL)); /* We don't want to check other connections to see if they are downloading, * as this is prone to race-conditions. So leave it for - * connection_dir_consider_close_extra_consensus_conns() to clean up. + * connection_dir_close_extra_consensus_conns(() to clean up. * * But if conn has just started connecting, or we have a consensus already, * we can be sure it's not needed any more. */ @@ -3823,7 +3968,7 @@ connection_dir_close_extra_consensus_conns(void) return; } - int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( time(NULL)); const char *usable_resource = networkstatus_get_flavor_name( @@ -3932,7 +4077,7 @@ find_dl_schedule(download_status_t *dls, const or_options_t *options) const int dir_server = dir_server_mode(options); const int multi_d = networkstatus_consensus_can_use_multiple_directories( options); - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( time(NULL)); const int use_fallbacks = networkstatus_consensus_can_use_extra_fallbacks( options); diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 3e1f48062c..441e4b5377 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -349,7 +349,7 @@ dirserv_get_status_impl(const char *id_digest, const char *nickname, if (result & FP_REJECT) { if (msg) - *msg = "Fingerprint is marked rejected"; + *msg = "Fingerprint is marked rejected -- please contact us?"; return FP_REJECT; } else if (result & FP_INVALID) { if (msg) @@ -367,7 +367,7 @@ dirserv_get_status_impl(const char *id_digest, const char *nickname, log_fn(severity, LD_DIRSERV, "Rejecting '%s' because of address '%s'", nickname, fmt_addr32(addr)); if (msg) - *msg = "Authdir is rejecting routers in this range."; + *msg = "Suspicious relay address range -- please contact us?"; return FP_REJECT; } if (!authdir_policy_valid_address(addr, or_port)) { @@ -2200,7 +2200,7 @@ set_routerstatus_from_routerinfo(routerstatus_t *rs, rs->is_valid = node->is_valid; - if (node->is_fast && + if (node->is_fast && node->is_stable && ((options->AuthDirGuardBWGuarantee && routerbw_kb >= options->AuthDirGuardBWGuarantee/1000) || routerbw_kb >= MIN(guard_bandwidth_including_exits_kb, diff --git a/src/or/dnsserv.c b/src/or/dnsserv.c index 74f17ce78c..edca50f6f9 100644 --- a/src/or/dnsserv.c +++ b/src/or/dnsserv.c @@ -130,7 +130,7 @@ evdns_server_callback(struct evdns_server_request *req, void *data_) tor_addr_copy(&TO_CONN(conn)->addr, &tor_addr); TO_CONN(conn)->port = port; - TO_CONN(conn)->address = tor_dup_addr(&tor_addr); + TO_CONN(conn)->address = tor_addr_to_str_dup(&tor_addr); if (q->type == EVDNS_TYPE_A || q->type == EVDNS_TYPE_AAAA || q->type == EVDNS_QTYPE_ALL) { @@ -205,7 +205,7 @@ dnsserv_launch_request(const char *name, int reverse, tor_addr_copy(&TO_CONN(conn)->addr, &control_conn->base_.addr); #ifdef AF_UNIX /* - * The control connection can be AF_UNIX and if so tor_dup_addr will + * The control connection can be AF_UNIX and if so tor_addr_to_str_dup will * unhelpfully say "<unknown address type>"; say "(Tor_internal)" * instead. */ @@ -214,11 +214,11 @@ dnsserv_launch_request(const char *name, int reverse, TO_CONN(conn)->address = tor_strdup("(Tor_internal)"); } else { TO_CONN(conn)->port = control_conn->base_.port; - TO_CONN(conn)->address = tor_dup_addr(&control_conn->base_.addr); + TO_CONN(conn)->address = tor_addr_to_str_dup(&control_conn->base_.addr); } #else TO_CONN(conn)->port = control_conn->base_.port; - TO_CONN(conn)->address = tor_dup_addr(&control_conn->base_.addr); + TO_CONN(conn)->address = tor_addr_to_str_dup(&control_conn->base_.addr); #endif if (reverse) diff --git a/src/or/ext_orport.c b/src/or/ext_orport.c index aa1b3e26fe..8ba3c6afa3 100644 --- a/src/or/ext_orport.c +++ b/src/or/ext_orport.c @@ -461,8 +461,8 @@ connection_ext_or_handle_cmd_useraddr(connection_t *conn, return -1; { /* do some logging */ - char *old_address = tor_dup_addr(&conn->addr); - char *new_address = tor_dup_addr(&addr); + char *old_address = tor_addr_to_str_dup(&conn->addr); + char *new_address = tor_addr_to_str_dup(&addr); log_debug(LD_NET, "Received USERADDR." "We rewrite our address from '%s:%u' to '%s:%u'.", @@ -478,7 +478,7 @@ connection_ext_or_handle_cmd_useraddr(connection_t *conn, if (conn->address) { tor_free(conn->address); } - conn->address = tor_dup_addr(&addr); + conn->address = tor_addr_to_str_dup(&addr); return 0; } diff --git a/src/or/hibernate.c b/src/or/hibernate.c index 9408925d96..3666abbcf4 100644 --- a/src/or/hibernate.c +++ b/src/or/hibernate.c @@ -28,6 +28,7 @@ hibernating, phase 2: #include "config.h" #include "connection.h" #include "connection_edge.h" +#include "control.h" #include "hibernate.h" #include "main.h" #include "router.h" @@ -111,11 +112,34 @@ static int cfg_start_day = 0, cfg_start_min = 0; /** @} */ +static const char *hibernate_state_to_string(hibernate_state_t state); static void reset_accounting(time_t now); static int read_bandwidth_usage(void); static time_t start_of_accounting_period_after(time_t now); static time_t start_of_accounting_period_containing(time_t now); static void accounting_set_wakeup_time(void); +static void on_hibernate_state_change(hibernate_state_t prev_state); + +/** + * Return the human-readable name for the hibernation state <b>state</b> + */ +static const char * +hibernate_state_to_string(hibernate_state_t state) +{ + static char buf[64]; + switch (state) { + case HIBERNATE_STATE_EXITING: return "EXITING"; + case HIBERNATE_STATE_LOWBANDWIDTH: return "SOFT"; + case HIBERNATE_STATE_DORMANT: return "HARD"; + case HIBERNATE_STATE_INITIAL: + case HIBERNATE_STATE_LIVE: + return "AWAKE"; + default: + log_warn(LD_BUG, "unknown hibernate state %d", state); + tor_snprintf(buf, sizeof(buf), "unknown [%d]", state); + return buf; + } +} /* ************ * Functions for bandwidth accounting. @@ -935,6 +959,7 @@ consider_hibernation(time_t now) { int accounting_enabled = get_options()->AccountingMax != 0; char buf[ISO_TIME_LEN+1]; + hibernate_state_t prev_state = hibernate_state; /* If we're in 'exiting' mode, then we just shut down after the interval * elapses. */ @@ -990,6 +1015,10 @@ consider_hibernation(time_t now) hibernate_end_time_elapsed(now); } } + + /* Dispatch a controller event if the hibernation state changed. */ + if (hibernate_state != prev_state) + on_hibernate_state_change(prev_state); } /** Helper function: called when we get a GETINFO request for an @@ -1007,12 +1036,8 @@ getinfo_helper_accounting(control_connection_t *conn, if (!strcmp(question, "accounting/enabled")) { *answer = tor_strdup(accounting_is_enabled(get_options()) ? "1" : "0"); } else if (!strcmp(question, "accounting/hibernating")) { - if (hibernate_state == HIBERNATE_STATE_DORMANT) - *answer = tor_strdup("hard"); - else if (hibernate_state == HIBERNATE_STATE_LOWBANDWIDTH) - *answer = tor_strdup("soft"); - else - *answer = tor_strdup("awake"); + *answer = tor_strdup(hibernate_state_to_string(hibernate_state)); + tor_strlower(*answer); } else if (!strcmp(question, "accounting/bytes")) { tor_asprintf(answer, U64_FORMAT" "U64_FORMAT, U64_PRINTF_ARG(n_bytes_read_in_interval), @@ -1062,6 +1087,20 @@ getinfo_helper_accounting(control_connection_t *conn, return 0; } +/** + * Helper function: called when the hibernation state changes, and sends a + * SERVER_STATUS event to notify interested controllers of the accounting + * state change. + */ +static void +on_hibernate_state_change(hibernate_state_t prev_state) +{ + (void)prev_state; /* Should we do something with this? */ + control_event_server_status(LOG_NOTICE, + "HIBERNATION_STATUS STATUS=%s", + hibernate_state_to_string(hibernate_state)); +} + #ifdef TOR_UNIT_TESTS /** * Manually change the hibernation state. Private; used only by the unit diff --git a/src/or/main.c b/src/or/main.c index a2cf5b1101..fba9799a60 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -1643,8 +1643,8 @@ rotate_x509_certificate_callback(time_t now, const or_options_t *options) * TLS context. */ log_info(LD_GENERAL,"Rotating tls context."); if (router_initialize_tls_context() < 0) { - log_warn(LD_BUG, "Error reinitializing TLS context"); - tor_assert(0); + log_err(LD_BUG, "Error reinitializing TLS context"); + tor_assert_unreached(); } /* We also make sure to rotate the TLS connections themselves if they've @@ -1917,7 +1917,7 @@ fetch_networkstatus_callback(time_t now, const or_options_t *options) /* How often do we check whether we should download network status * documents? */ - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( now); const int prefer_mirrors = !directory_fetches_from_authorities( get_options()); @@ -2563,9 +2563,7 @@ run_main_loop_once(void) return -1; #endif } else { - if (ERRNO_IS_EINPROGRESS(e)) - log_warn(LD_BUG, - "libevent call returned EINPROGRESS? Please report."); + tor_assert_nonfatal_once(! ERRNO_IS_EINPROGRESS(e)); log_debug(LD_NET,"libevent call interrupted."); /* You can't trust the results of this poll(). Go back to the * top of the big for loop. */ diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index 185708a0c1..2975e7ebb4 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -819,7 +819,7 @@ update_consensus_networkstatus_downloads(time_t now) { int i; const or_options_t *options = get_options(); - const int we_are_bootstrapping = networkstatus_consensus_is_boostrapping( + const int we_are_bootstrapping = networkstatus_consensus_is_bootstrapping( now); const int use_multi_conn = networkstatus_consensus_can_use_multiple_directories(options); @@ -875,12 +875,13 @@ update_consensus_networkstatus_downloads(time_t now) resource, DIR_CONN_STATE_CONNECTING); - if (i == usable_consensus_flavor() - && connect_consens_conn_count < consens_conn_count) { + /* If not all connections are "connecting", then some are + * downloading. We want to have at most one downloading at a time. */ + if (connect_consens_conn_count < consens_conn_count) { continue; } - /* Make multiple connections for a bootstrap consensus download */ + /* Make multiple connections for a bootstrap consensus download. */ update_consensus_bootstrap_multiple_downloads(now, options, we_are_bootstrapping); } else { @@ -954,7 +955,7 @@ update_consensus_bootstrap_attempt_downloads( * connections. * Only call when bootstrapping, and when we want to make additional * connections. Only nodes that satisfy - * networkstatus_consensus_can_use_multiple_directories make additonal + * networkstatus_consensus_can_use_multiple_directories make additional * connections. */ static void @@ -969,7 +970,7 @@ update_consensus_bootstrap_multiple_downloads(time_t now, return; } - /* If we've managed to validate a usable consensus, don't make additonal + /* If we've managed to validate a usable consensus, don't make additional * connections. */ if (!we_are_bootstrapping) { return; @@ -1277,7 +1278,7 @@ networkstatus_get_reasonably_live_consensus(time_t now, int flavor) * only using the authorities and fallback directory mirrors to download the * consensus flavour we'll use. */ int -networkstatus_consensus_is_boostrapping(time_t now) +networkstatus_consensus_is_bootstrapping(time_t now) { /* If we don't have a consensus, we must still be bootstrapping */ return !networkstatus_get_reasonably_live_consensus( @@ -1327,7 +1328,7 @@ networkstatus_consensus_can_use_extra_fallbacks(const or_options_t *options) * return value of this function to see if a client could make multiple * bootstrap connections. Use * networkstatus_consensus_can_use_multiple_directories() - * and networkstatus_consensus_is_boostrapping(). */ + * and networkstatus_consensus_is_bootstrapping(). */ int networkstatus_consensus_has_excess_connections(void) { diff --git a/src/or/networkstatus.h b/src/or/networkstatus.h index 9bbb9a389e..f2f8af5c6b 100644 --- a/src/or/networkstatus.h +++ b/src/or/networkstatus.h @@ -70,7 +70,7 @@ MOCK_DECL(networkstatus_t *,networkstatus_get_latest_consensus_by_flavor, networkstatus_t *networkstatus_get_live_consensus(time_t now); networkstatus_t *networkstatus_get_reasonably_live_consensus(time_t now, int flavor); -int networkstatus_consensus_is_boostrapping(time_t now); +int networkstatus_consensus_is_bootstrapping(time_t now); int networkstatus_consensus_can_use_multiple_directories( const or_options_t *options); int networkstatus_consensus_can_use_extra_fallbacks( diff --git a/src/or/onion.c b/src/or/onion.c index d6ef3673dd..4bed7ae226 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -527,7 +527,7 @@ onion_skin_server_handshake(int type, * <b>rend_authenticator_out</b> to the "KH" field that can be used to * establish introduction points at this hop, and return 0. On failure, * return -1, and set *msg_out to an error message if this is worth - * complaining to the usre about. */ + * complaining to the user about. */ int onion_skin_client_handshake(int type, const onion_handshake_state_t *handshake_state, diff --git a/src/or/or.h b/src/or/or.h index 6694bb4ece..86664d470d 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -784,7 +784,7 @@ typedef enum rend_auth_type_t { /** Client-side configuration of authorization for a hidden service. */ typedef struct rend_service_authorization_t { - char descriptor_cookie[REND_DESC_COOKIE_LEN]; + uint8_t descriptor_cookie[REND_DESC_COOKIE_LEN]; char onion_address[REND_SERVICE_ADDRESS_LEN+1]; rend_auth_type_t auth_type; } rend_service_authorization_t; @@ -1294,21 +1294,26 @@ typedef struct connection_t { time_t timestamp_created; /**< When was this connection_t created? */ - /* XXXX_IP6 make this IPv6-capable */ int socket_family; /**< Address family of this connection's socket. Usually - * AF_INET, but it can also be AF_UNIX, or in the future - * AF_INET6 */ - tor_addr_t addr; /**< IP of the other side of the connection; used to - * identify routers, along with port. */ - uint16_t port; /**< If non-zero, port on the other end - * of the connection. */ + * AF_INET, but it can also be AF_UNIX, or AF_INET6 */ + tor_addr_t addr; /**< IP that socket "s" is directly connected to; + * may be the IP address for a proxy or pluggable transport, + * see "address" for the address of the final destination. + */ + uint16_t port; /**< If non-zero, port that socket "s" is directly connected + * to; may be the port for a proxy or pluggable transport, + * see "address" for the port at the final destination. */ uint16_t marked_for_close; /**< Should we close this conn on the next * iteration of the main loop? (If true, holds * the line number where this connection was * marked.) */ const char *marked_for_close_file; /**< For debugging: in which file were * we marked for close? */ - char *address; /**< FQDN (or IP) of the other end. + char *address; /**< FQDN (or IP) and port of the final destination for this + * connection; this is always the remote address, it is + * passed to a proxy or pluggable transport if one in use. + * See "addr" and "port" for the address that socket "s" is + * directly connected to. * strdup into this, because free_connection() frees it. */ /** Another connection that's connected to this one in lieu of a socket. */ struct connection_t *linked_conn; @@ -5034,7 +5039,7 @@ typedef enum { /** Hidden-service side configuration of client authorization. */ typedef struct rend_authorized_client_t { char *client_name; - char descriptor_cookie[REND_DESC_COOKIE_LEN]; + uint8_t descriptor_cookie[REND_DESC_COOKIE_LEN]; crypto_pk_t *client_key; } rend_authorized_client_t; diff --git a/src/or/policies.c b/src/or/policies.c index f9718b6a95..2703d7edef 100644 --- a/src/or/policies.c +++ b/src/or/policies.c @@ -103,7 +103,7 @@ policy_expand_private(smartlist_t **policy) if (tor_addr_parse_mask_ports(private_nets[i], 0, &newpolicy.addr, &newpolicy.maskbits, &port_min, &port_max)<0) { - tor_assert(0); + tor_assert_unreached(); } smartlist_add(tmp, addr_policy_get_canonical_entry(&newpolicy)); } diff --git a/src/or/rendclient.c b/src/or/rendclient.c index 609c45c71d..c119d86adf 100644 --- a/src/or/rendclient.c +++ b/src/or/rendclient.c @@ -1466,12 +1466,10 @@ rend_parse_service_authorization(const or_options_t *options, strmap_t *parsed = strmap_new(); smartlist_t *sl = smartlist_new(); rend_service_authorization_t *auth = NULL; - char descriptor_cookie_tmp[REND_DESC_COOKIE_LEN+2]; - char descriptor_cookie_base64ext[REND_DESC_COOKIE_LEN_BASE64+2+1]; + char *err_msg = NULL; for (line = options->HidServAuth; line; line = line->next) { char *onion_address, *descriptor_cookie; - int auth_type_val = 0; auth = NULL; SMARTLIST_FOREACH(sl, char *, c, tor_free(c);); smartlist_clear(sl); @@ -1500,31 +1498,13 @@ rend_parse_service_authorization(const or_options_t *options, } /* Parse descriptor cookie. */ descriptor_cookie = smartlist_get(sl, 1); - if (strlen(descriptor_cookie) != REND_DESC_COOKIE_LEN_BASE64) { - log_warn(LD_CONFIG, "Authorization cookie has wrong length: '%s'", - descriptor_cookie); + if (rend_auth_decode_cookie(descriptor_cookie, auth->descriptor_cookie, + &auth->auth_type, &err_msg) < 0) { + tor_assert(err_msg); + log_warn(LD_CONFIG, "%s", err_msg); + tor_free(err_msg); goto err; } - /* Add trailing zero bytes (AA) to make base64-decoding happy. */ - tor_snprintf(descriptor_cookie_base64ext, - REND_DESC_COOKIE_LEN_BASE64+2+1, - "%sAA", descriptor_cookie); - if (base64_decode(descriptor_cookie_tmp, sizeof(descriptor_cookie_tmp), - descriptor_cookie_base64ext, - strlen(descriptor_cookie_base64ext)) < 0) { - log_warn(LD_CONFIG, "Decoding authorization cookie failed: '%s'", - descriptor_cookie); - goto err; - } - auth_type_val = (((uint8_t)descriptor_cookie_tmp[16]) >> 4) + 1; - if (auth_type_val < 1 || auth_type_val > 2) { - log_warn(LD_CONFIG, "Authorization cookie has unknown authorization " - "type encoded."); - goto err; - } - auth->auth_type = auth_type_val == 1 ? REND_BASIC_AUTH : REND_STEALTH_AUTH; - memcpy(auth->descriptor_cookie, descriptor_cookie_tmp, - REND_DESC_COOKIE_LEN); if (strmap_get(parsed, auth->onion_address)) { log_warn(LD_CONFIG, "Duplicate authorization for the same hidden " "service."); @@ -1547,8 +1527,6 @@ rend_parse_service_authorization(const or_options_t *options, } else { strmap_free(parsed, rend_service_authorization_strmap_item_free); } - memwipe(descriptor_cookie_tmp, 0, sizeof(descriptor_cookie_tmp)); - memwipe(descriptor_cookie_base64ext, 0, sizeof(descriptor_cookie_base64ext)); return res; } diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c index 438fbc4d9a..56c49fee47 100644 --- a/src/or/rendcommon.c +++ b/src/or/rendcommon.c @@ -211,7 +211,7 @@ rend_encode_v2_intro_points(char **encoded, rend_service_descriptor_t *desc) goto done; } /* Assemble everything for this introduction point. */ - address = tor_dup_addr(&info->addr); + address = tor_addr_to_str_dup(&info->addr); res = tor_snprintf(unenc + unenc_written, unenc_len - unenc_written, "introduction-point %s\n" "ip-address %s\n" @@ -720,6 +720,22 @@ rend_valid_descriptor_id(const char *query) return 0; } +/** Return true iff <b>client_name</b> is a syntactically valid name + * for rendezvous client authentication. */ +int +rend_valid_client_name(const char *client_name) +{ + size_t len = strlen(client_name); + if (len < 1 || len > REND_CLIENTNAME_MAX_LEN) { + return 0; + } + if (strspn(client_name, REND_LEGAL_CLIENTNAME_CHARACTERS) != len) { + return 0; + } + + return 1; +} + /** Called when we get a rendezvous-related relay cell on circuit * <b>circ</b>. Dispatch on rendezvous relay command. */ void @@ -941,3 +957,114 @@ hid_serv_get_responsible_directories(smartlist_t *responsible_dirs, return smartlist_len(responsible_dirs) ? 0 : -1; } +/* Length of the 'extended' auth cookie used to encode auth type before + * base64 encoding. */ +#define REND_DESC_COOKIE_LEN_EXT (REND_DESC_COOKIE_LEN + 1) +/* Length of the zero-padded auth cookie when base64 encoded. These two + * padding bytes always (A=) are stripped off of the returned cookie. */ +#define REND_DESC_COOKIE_LEN_EXT_BASE64 (REND_DESC_COOKIE_LEN_BASE64 + 2) + +/** Encode a client authorization descriptor cookie. + * The result of this function is suitable for use in the HidServAuth + * option. The trailing padding characters are removed, and the + * auth type is encoded into the cookie. + * + * Returns a new base64-encoded cookie. This function cannot fail. + * The caller is responsible for freeing the returned value. + */ +char * +rend_auth_encode_cookie(const uint8_t *cookie_in, rend_auth_type_t auth_type) +{ + uint8_t extended_cookie[REND_DESC_COOKIE_LEN_EXT]; + char *cookie_out = tor_malloc_zero(REND_DESC_COOKIE_LEN_EXT_BASE64 + 1); + int re; + + tor_assert(cookie_in); + + memcpy(extended_cookie, cookie_in, REND_DESC_COOKIE_LEN); + extended_cookie[REND_DESC_COOKIE_LEN] = ((int)auth_type - 1) << 4; + re = base64_encode(cookie_out, REND_DESC_COOKIE_LEN_EXT_BASE64 + 1, + (const char *) extended_cookie, REND_DESC_COOKIE_LEN_EXT, + 0); + tor_assert(re == REND_DESC_COOKIE_LEN_EXT_BASE64); + + /* Remove the trailing 'A='. Auth type is encoded in the high bits + * of the last byte, so the last base64 character will always be zero + * (A). This is subtly different behavior from base64_encode_nopad. */ + cookie_out[REND_DESC_COOKIE_LEN_BASE64] = '\0'; + memwipe(extended_cookie, 0, sizeof(extended_cookie)); + return cookie_out; +} + +/** Decode a base64-encoded client authorization descriptor cookie. + * The descriptor_cookie can be truncated to REND_DESC_COOKIE_LEN_BASE64 + * characters (as given to clients), or may include the two padding + * characters (as stored by the service). + * + * The result is stored in REND_DESC_COOKIE_LEN bytes of cookie_out. + * The rend_auth_type_t decoded from the cookie is stored in the + * optional auth_type_out parameter. + * + * Return 0 on success, or -1 on error. The caller is responsible for + * freeing the returned err_msg. + */ +int +rend_auth_decode_cookie(const char *cookie_in, uint8_t *cookie_out, + rend_auth_type_t *auth_type_out, char **err_msg_out) +{ + uint8_t descriptor_cookie_decoded[REND_DESC_COOKIE_LEN_EXT + 1] = { 0 }; + char descriptor_cookie_base64ext[REND_DESC_COOKIE_LEN_EXT_BASE64 + 1]; + const char *descriptor_cookie = cookie_in; + char *err_msg = NULL; + int auth_type_val = 0; + int res = -1; + int decoded_len; + + size_t len = strlen(descriptor_cookie); + if (len == REND_DESC_COOKIE_LEN_BASE64) { + /* Add a trailing zero byte to make base64-decoding happy. */ + tor_snprintf(descriptor_cookie_base64ext, + sizeof(descriptor_cookie_base64ext), + "%sA=", descriptor_cookie); + descriptor_cookie = descriptor_cookie_base64ext; + } else if (len != REND_DESC_COOKIE_LEN_EXT_BASE64) { + tor_asprintf(&err_msg, "Authorization cookie has wrong length: %s", + escaped(cookie_in)); + goto err; + } + + decoded_len = base64_decode((char *) descriptor_cookie_decoded, + sizeof(descriptor_cookie_decoded), + descriptor_cookie, + REND_DESC_COOKIE_LEN_EXT_BASE64); + if (decoded_len != REND_DESC_COOKIE_LEN && + decoded_len != REND_DESC_COOKIE_LEN_EXT) { + tor_asprintf(&err_msg, "Authorization cookie has invalid characters: %s", + escaped(cookie_in)); + goto err; + } + + if (auth_type_out) { + auth_type_val = (descriptor_cookie_decoded[REND_DESC_COOKIE_LEN] >> 4) + 1; + if (auth_type_val < 1 || auth_type_val > 2) { + tor_asprintf(&err_msg, "Authorization cookie type is unknown: %s", + escaped(cookie_in)); + goto err; + } + *auth_type_out = auth_type_val == 1 ? REND_BASIC_AUTH : REND_STEALTH_AUTH; + } + + memcpy(cookie_out, descriptor_cookie_decoded, REND_DESC_COOKIE_LEN); + res = 0; + err: + if (err_msg_out) { + *err_msg_out = err_msg; + } else { + tor_free(err_msg); + } + memwipe(descriptor_cookie_decoded, 0, sizeof(descriptor_cookie_decoded)); + memwipe(descriptor_cookie_base64ext, 0, sizeof(descriptor_cookie_base64ext)); + return res; +} + + diff --git a/src/or/rendcommon.h b/src/or/rendcommon.h index d67552e405..88cf512f4a 100644 --- a/src/or/rendcommon.h +++ b/src/or/rendcommon.h @@ -45,6 +45,7 @@ void rend_intro_point_free(rend_intro_point_t *intro); int rend_valid_service_id(const char *query); int rend_valid_descriptor_id(const char *query); +int rend_valid_client_name(const char *client_name); int rend_encode_v2_descriptors(smartlist_t *descs_out, rend_service_descriptor_t *desc, time_t now, uint8_t period, rend_auth_type_t auth_type, @@ -68,5 +69,13 @@ rend_data_t *rend_data_service_create(const char *onion_address, const char *pk_digest, const uint8_t *cookie, rend_auth_type_t auth_type); + +char *rend_auth_encode_cookie(const uint8_t *cookie_in, + rend_auth_type_t auth_type); +int rend_auth_decode_cookie(const char *cookie_in, + uint8_t *cookie_out, + rend_auth_type_t *auth_type_out, + char **err_msg_out); + #endif diff --git a/src/or/rendmid.c b/src/or/rendmid.c index a33ad92966..ca0ad7b0d4 100644 --- a/src/or/rendmid.c +++ b/src/or/rendmid.c @@ -309,7 +309,7 @@ rend_mid_rendezvous(or_circuit_t *circ, const uint8_t *request, goto err; } - if (request_len != REND_COOKIE_LEN+DH_KEY_LEN+DIGEST_LEN) { + if (request_len < REND_COOKIE_LEN) { log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL, "Rejecting RENDEZVOUS1 cell with bad length (%d) on circuit %u.", (int)request_len, (unsigned)circ->p_circ_id); diff --git a/src/or/rendservice.c b/src/or/rendservice.c index 6f41f3b968..7426d8b35d 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -183,14 +183,15 @@ num_rend_services(void) } /** Helper: free storage held by a single service authorized client entry. */ -static void +void rend_authorized_client_free(rend_authorized_client_t *client) { if (!client) return; if (client->client_key) crypto_pk_free(client->client_key); - memwipe(client->client_name, 0, strlen(client->client_name)); + if (client->client_name) + memwipe(client->client_name, 0, strlen(client->client_name)); tor_free(client->client_name); memwipe(client->descriptor_cookie, 0, sizeof(client->descriptor_cookie)); tor_free(client); @@ -671,27 +672,17 @@ rend_config_services(const or_options_t *options, int validate_only) SMARTLIST_FOREACH_BEGIN(clients, const char *, client_name) { rend_authorized_client_t *client; - size_t len = strlen(client_name); - if (len < 1 || len > REND_CLIENTNAME_MAX_LEN) { + if (!rend_valid_client_name(client_name)) { log_warn(LD_CONFIG, "HiddenServiceAuthorizeClient contains an " - "illegal client name: '%s'. Length must be " - "between 1 and %d characters.", + "illegal client name: '%s'. Names must be " + "between 1 and %d characters and contain " + "only [A-Za-z0-9+_-].", client_name, REND_CLIENTNAME_MAX_LEN); SMARTLIST_FOREACH(clients, char *, cp, tor_free(cp)); smartlist_free(clients); rend_service_free(service); return -1; } - if (strspn(client_name, REND_LEGAL_CLIENTNAME_CHARACTERS) != len) { - log_warn(LD_CONFIG, "HiddenServiceAuthorizeClient contains an " - "illegal client name: '%s'. Valid " - "characters are [A-Za-z0-9+_-].", - client_name); - SMARTLIST_FOREACH(clients, char *, cp, tor_free(cp)); - smartlist_free(clients); - rend_service_free(service); - return -1; - } client = tor_malloc_zero(sizeof(rend_authorized_client_t)); client->client_name = tor_strdup(client_name); smartlist_add(service->clients, client); @@ -827,14 +818,17 @@ rend_config_services(const or_options_t *options, int validate_only) return 0; } -/** Add the ephemeral service <b>pk</b>/<b>ports</b> if possible, with +/** Add the ephemeral service <b>pk</b>/<b>ports</b> if possible, using + * client authorization <b>auth_type</b> and an optional list of + * rend_authorized_client_t in <b>auth_clients</b>, with * <b>max_streams_per_circuit</b> streams allowed per rendezvous circuit, * and circuit closure on max streams being exceeded set by * <b>max_streams_close_circuit</b>. * - * Regardless of sucess/failure, callers should not touch pk/ports after - * calling this routine, and may assume that correct cleanup has been done - * on failure. + * Ownership of pk, ports, and auth_clients is passed to this routine. + * Regardless of success/failure, callers should not touch these values + * after calling this routine, and may assume that correct cleanup has + * been done on failure. * * Return an appropriate rend_service_add_ephemeral_status_t. */ @@ -843,6 +837,8 @@ rend_service_add_ephemeral(crypto_pk_t *pk, smartlist_t *ports, int max_streams_per_circuit, int max_streams_close_circuit, + rend_auth_type_t auth_type, + smartlist_t *auth_clients, char **service_id_out) { *service_id_out = NULL; @@ -852,7 +848,8 @@ rend_service_add_ephemeral(crypto_pk_t *pk, rend_service_t *s = tor_malloc_zero(sizeof(rend_service_t)); s->directory = NULL; /* This indicates the service is ephemeral. */ s->private_key = pk; - s->auth_type = REND_NO_AUTH; + s->auth_type = auth_type; + s->clients = auth_clients; s->ports = ports; s->intro_period_started = time(NULL); s->n_intro_points_wanted = NUM_INTRO_POINTS_DEFAULT; @@ -868,6 +865,12 @@ rend_service_add_ephemeral(crypto_pk_t *pk, rend_service_free(s); return RSAE_BADVIRTPORT; } + if (s->auth_type != REND_NO_AUTH && + (!s->clients || smartlist_len(s->clients) == 0)) { + log_warn(LD_CONFIG, "At least one authorized client must be specified."); + rend_service_free(s); + return RSAE_BADAUTH; + } /* Enforcing pk/id uniqueness should be done by rend_service_load_keys(), but * it's not, see #14828. @@ -1156,7 +1159,6 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) strmap_t *parsed_clients = strmap_new(); FILE *cfile, *hfile; open_file_t *open_cfile = NULL, *open_hfile = NULL; - char extended_desc_cookie[REND_DESC_COOKIE_LEN+1]; char desc_cook_out[3*REND_DESC_COOKIE_LEN_BASE64+1]; char service_id[16+1]; char buf[1500]; @@ -1208,10 +1210,12 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) memcpy(client->descriptor_cookie, parsed->descriptor_cookie, REND_DESC_COOKIE_LEN); } else { - crypto_rand(client->descriptor_cookie, REND_DESC_COOKIE_LEN); + crypto_rand((char *) client->descriptor_cookie, REND_DESC_COOKIE_LEN); } + /* For compatibility with older tor clients, this does not + * truncate the padding characters, unlike rend_auth_encode_cookie. */ if (base64_encode(desc_cook_out, 3*REND_DESC_COOKIE_LEN_BASE64+1, - client->descriptor_cookie, + (char *) client->descriptor_cookie, REND_DESC_COOKIE_LEN, 0) < 0) { log_warn(LD_BUG, "Could not base64-encode descriptor cookie."); goto err; @@ -1272,6 +1276,8 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) log_warn(LD_BUG, "Could not write client entry."); goto err; } + } else { + strlcpy(service_id, s->service_id, sizeof(service_id)); } if (fputs(buf, cfile) < 0) { @@ -1280,27 +1286,18 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) goto err; } - /* Add line to hostname file. */ - if (s->auth_type == REND_BASIC_AUTH) { - /* Remove == signs (newline has been removed above). */ - desc_cook_out[strlen(desc_cook_out)-2] = '\0'; - tor_snprintf(buf, sizeof(buf),"%s.onion %s # client: %s\n", - s->service_id, desc_cook_out, client->client_name); - } else { - memcpy(extended_desc_cookie, client->descriptor_cookie, - REND_DESC_COOKIE_LEN); - extended_desc_cookie[REND_DESC_COOKIE_LEN] = - ((int)s->auth_type - 1) << 4; - if (base64_encode(desc_cook_out, 3*REND_DESC_COOKIE_LEN_BASE64+1, - extended_desc_cookie, - REND_DESC_COOKIE_LEN+1, 0) < 0) { - log_warn(LD_BUG, "Could not base64-encode descriptor cookie."); - goto err; - } - desc_cook_out[strlen(desc_cook_out)-2] = '\0'; /* Remove A=. */ - tor_snprintf(buf, sizeof(buf),"%s.onion %s # client: %s\n", - service_id, desc_cook_out, client->client_name); + /* Add line to hostname file. This is not the same encoding as in + * client_keys. */ + char *encoded_cookie = rend_auth_encode_cookie(client->descriptor_cookie, + s->auth_type); + if (!encoded_cookie) { + log_warn(LD_BUG, "Could not base64-encode descriptor cookie."); + goto err; } + tor_snprintf(buf, sizeof(buf), "%s.onion %s # client: %s\n", + service_id, encoded_cookie, client->client_name); + memwipe(encoded_cookie, 0, strlen(encoded_cookie)); + tor_free(encoded_cookie); if (fputs(buf, hfile)<0) { log_warn(LD_FS, "Could not append host entry to file: %s", @@ -1332,7 +1329,6 @@ rend_service_load_auth_keys(rend_service_t *s, const char *hfname) memwipe(buf, 0, sizeof(buf)); memwipe(desc_cook_out, 0, sizeof(desc_cook_out)); memwipe(service_id, 0, sizeof(service_id)); - memwipe(extended_desc_cookie, 0, sizeof(extended_desc_cookie)); return r; } diff --git a/src/or/rendservice.h b/src/or/rendservice.h index 101b37e18d..4966cb0302 100644 --- a/src/or/rendservice.h +++ b/src/or/rendservice.h @@ -106,8 +106,11 @@ rend_service_port_config_t *rend_service_parse_port_config(const char *string, char **err_msg_out); void rend_service_port_config_free(rend_service_port_config_t *p); +void rend_authorized_client_free(rend_authorized_client_t *client); + /** Return value from rend_service_add_ephemeral. */ typedef enum { + RSAE_BADAUTH = -5, /**< Invalid auth_type/auth_clients */ RSAE_BADVIRTPORT = -4, /**< Invalid VIRTPORT/TARGET(s) */ RSAE_ADDREXISTS = -3, /**< Onion address collision */ RSAE_BADPRIVKEY = -2, /**< Invalid public key */ @@ -118,6 +121,8 @@ rend_service_add_ephemeral_status_t rend_service_add_ephemeral(crypto_pk_t *pk, smartlist_t *ports, int max_streams_per_circuit, int max_streams_close_circuit, + rend_auth_type_t auth_type, + smartlist_t *auth_clients, char **service_id_out); int rend_service_del_ephemeral(const char *service_id); diff --git a/src/or/rephist.c b/src/or/rephist.c index fe0ca91c25..b94ad29650 100644 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@ -3214,7 +3214,7 @@ rep_hist_free_all(void) rep_hist_desc_stats_term(); total_descriptor_downloads = 0; - tor_assert(rephist_total_alloc == 0); - tor_assert(rephist_total_num == 0); + tor_assert_nonfatal(rephist_total_alloc == 0); + tor_assert_nonfatal_once(rephist_total_num == 0); } diff --git a/src/or/routerlist.c b/src/or/routerlist.c index d40d704a1d..2149192509 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -4295,7 +4295,7 @@ dir_server_new(int is_authority, return NULL; if (!hostname) - hostname_ = tor_dup_addr(addr); + hostname_ = tor_addr_to_str_dup(addr); else hostname_ = tor_strdup(hostname); diff --git a/src/or/routerparse.c b/src/or/routerparse.c index cec10c8f24..600d55294f 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -5371,6 +5371,7 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) directory_token_t *tok; const char *current_entry = NULL; memarea_t *area = NULL; + char *err_msg = NULL; if (!ckstr || strlen(ckstr) == 0) return -1; tokens = smartlist_new(); @@ -5380,8 +5381,6 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) current_entry = eat_whitespace(ckstr); while (!strcmpstart(current_entry, "client-name ")) { rend_authorized_client_t *parsed_entry; - size_t len; - char descriptor_cookie_tmp[REND_DESC_COOKIE_LEN+2]; /* Determine end of string. */ const char *eos = strstr(current_entry, "\nclient-name "); if (!eos) @@ -5410,12 +5409,10 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) tor_assert(tok == smartlist_get(tokens, 0)); tor_assert(tok->n_args == 1); - len = strlen(tok->args[0]); - if (len < 1 || len > 19 || - strspn(tok->args[0], REND_LEGAL_CLIENTNAME_CHARACTERS) != len) { + if (!rend_valid_client_name(tok->args[0])) { log_warn(LD_CONFIG, "Illegal client name: %s. (Length must be " - "between 1 and 19, and valid characters are " - "[A-Za-z0-9+-_].)", tok->args[0]); + "between 1 and %d, and valid characters are " + "[A-Za-z0-9+-_].)", tok->args[0], REND_CLIENTNAME_MAX_LEN); goto err; } /* Check if client name is duplicate. */ @@ -5437,23 +5434,13 @@ rend_parse_client_keys(strmap_t *parsed_clients, const char *ckstr) /* Parse descriptor cookie. */ tok = find_by_keyword(tokens, C_DESCRIPTOR_COOKIE); tor_assert(tok->n_args == 1); - if (strlen(tok->args[0]) != REND_DESC_COOKIE_LEN_BASE64 + 2) { - log_warn(LD_REND, "Descriptor cookie has illegal length: %s", - escaped(tok->args[0])); - goto err; - } - /* The size of descriptor_cookie_tmp needs to be REND_DESC_COOKIE_LEN+2, - * because a base64 encoding of length 24 does not fit into 16 bytes in all - * cases. */ - if (base64_decode(descriptor_cookie_tmp, sizeof(descriptor_cookie_tmp), - tok->args[0], strlen(tok->args[0])) - != REND_DESC_COOKIE_LEN) { - log_warn(LD_REND, "Descriptor cookie contains illegal characters: " - "%s", escaped(tok->args[0])); + if (rend_auth_decode_cookie(tok->args[0], parsed_entry->descriptor_cookie, + NULL, &err_msg) < 0) { + tor_assert(err_msg); + log_warn(LD_REND, "%s", err_msg); + tor_free(err_msg); goto err; } - memcpy(parsed_entry->descriptor_cookie, descriptor_cookie_tmp, - REND_DESC_COOKIE_LEN); } result = strmap_size(parsed_clients); goto done; diff --git a/src/test/include.am b/src/test/include.am index 7d80fdf152..d1e1cbd7f6 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -17,6 +17,7 @@ endif TESTS += src/test/test src/test/test-slow src/test/test-memwipe \ src/test/test_workqueue src/test/test_keygen.sh \ + src/test/test-timers \ $(TESTSCRIPTS) # These flavors are run using automake's test-driver and test-network.sh @@ -40,7 +41,8 @@ noinst_PROGRAMS+= \ src/test/test-memwipe \ src/test/test-child \ src/test/test_workqueue \ - src/test/test-switch-id + src/test/test-switch-id \ + src/test/test-timers endif src_test_AM_CPPFLAGS = -DSHARE_DATADIR="\"$(datadir)\"" \ @@ -86,6 +88,7 @@ src_test_test_SOURCES = \ src/test/test_guardfraction.c \ src/test/test_extorport.c \ src/test/test_hs.c \ + src/test/test_handles.c \ src/test/test_introduce.c \ src/test/test_keypin.c \ src/test/test_link_handshake.c \ @@ -97,6 +100,7 @@ src_test_test_SOURCES = \ src/test/test_policy.c \ src/test/test_procmon.c \ src/test/test_pt.c \ + src/test/test_pubsub.c \ src/test/test_relay.c \ src/test/test_relaycell.c \ src/test/test_rendcache.c \ @@ -127,6 +131,8 @@ src_test_test_slow_SOURCES = \ src_test_test_memwipe_SOURCES = \ src/test/test-memwipe.c +src_test_test_timers_SOURCES = \ + src/test/test-timers.c src_test_test_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) @@ -190,6 +196,16 @@ src_test_test_workqueue_LDADD = src/or/libtor-testing.a \ @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ @TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ +src_test_test_timers_CPPFLAGS = $(src_test_test_CPPFLAGS) +src_test_test_timers_CFLAGS = $(src_test_test_CFLAGS) +src_test_test_timers_LDADD = \ + src/common/libor-event-testing.a \ + src/common/libor-crypto-testing.a $(LIBKECCAK_TINY) $(LIBDONNA) \ + src/common/libor-testing.a \ + @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ \ + @TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ +src_test_test_timers_LDFLAGS = $(src_test_test_LDFLAGS) + noinst_HEADERS+= \ src/test/fakechans.h \ src/test/log_test_helpers.h \ diff --git a/src/test/test-memwipe.c b/src/test/test-memwipe.c index 5d4fcec664..5e89534db6 100644 --- a/src/test/test-memwipe.c +++ b/src/test/test-memwipe.c @@ -6,9 +6,6 @@ #include "crypto.h" #include "compat.h" -#undef MIN -#define MIN(a,b) ( ((a)<(b)) ? (a) : (b) ) - static unsigned fill_a_buffer_memset(void) __attribute__((noinline)); static unsigned fill_a_buffer_memwipe(void) __attribute__((noinline)); static unsigned fill_a_buffer_nothing(void) __attribute__((noinline)); diff --git a/src/test/test-timers.c b/src/test/test-timers.c new file mode 100644 index 0000000000..8f5ba7b78a --- /dev/null +++ b/src/test/test-timers.c @@ -0,0 +1,133 @@ +/* Copyright 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" + +#include <math.h> +#include <stdio.h> +#include <string.h> + +#ifdef HAVE_EVENT2_EVENT_H +#include <event2/event.h> +#else +#include <event.h> +#endif + +#include "compat.h" +#include "compat_libevent.h" +#include "crypto.h" +#include "timers.h" +#include "util.h" + +#define N_TIMERS 1000 +#define MAX_DURATION 30 +#define N_DISABLE 5 + +static struct timeval fire_at[N_TIMERS] = {{0,0}}; +static int is_disabled[N_TIMERS] = {0}; +static int fired[N_TIMERS] = {0}; +static struct timeval difference[N_TIMERS] = {{0,0}}; +static tor_timer_t *timers[N_TIMERS] = {NULL}; + +static int n_active_timers = 0; +static int n_fired = 0; + +static void +timer_cb(tor_timer_t *t, void *arg, const struct timeval *now) +{ + tor_timer_t **t_ptr = arg; + tor_assert(*t_ptr == t); + int idx = (int) (t_ptr - timers); + ++fired[idx]; + timersub(now, &fire_at[idx], &difference[idx]); + ++n_fired; + // printf("%d / %d\n",n_fired, N_TIMERS); + if (n_fired == n_active_timers) { + event_base_loopbreak(tor_libevent_get_base()); + } +} + +int +main(int argc, char **argv) +{ + (void)argc; + (void)argv; + tor_libevent_cfg cfg; + memset(&cfg, 0, sizeof(cfg)); + tor_libevent_initialize(&cfg); + timers_initialize(); + + int i; + int ret; + struct timeval now; + tor_gettimeofday(&now); + for (i = 0; i < N_TIMERS; ++i) { + struct timeval delay; + delay.tv_sec = crypto_rand_int_range(0,MAX_DURATION); + delay.tv_usec = crypto_rand_int_range(0,1000000); + timeradd(&now, &delay, &fire_at[i]); + timers[i] = timer_new(timer_cb, &timers[i]); + timer_schedule(timers[i], &delay); + ++n_active_timers; + } + + /* Disable some; we'll make sure they don't trigger. */ + for (i = 0; i < N_DISABLE; ++i) { + int idx = crypto_rand_int_range(0, N_TIMERS); + if (is_disabled[idx]) + continue; + is_disabled[idx] = 1; + timer_disable(timers[idx]); + --n_active_timers; + } + + event_base_loop(tor_libevent_get_base(), 0); + + int64_t total_difference = 0; + uint64_t total_square_difference = 0; + tor_assert(n_fired == n_active_timers); + for (i = 0; i < N_TIMERS; ++i) { + if (is_disabled[i]) { + tor_assert(fired[i] == 0); + continue; + } + tor_assert(fired[i] == 1); + int64_t diff = difference[i].tv_usec + difference[i].tv_sec * 1000000; + total_difference += diff; + total_square_difference += diff*diff; + } + const int64_t mean_diff = total_difference / n_active_timers; + printf("mean difference: "U64_FORMAT" usec\n", + U64_PRINTF_ARG(mean_diff)); + + const double mean_sq = ((double)total_square_difference)/ n_active_timers; + const double sq_mean = mean_diff * mean_diff; + const double stddev = sqrt(mean_sq - sq_mean); + printf("standard deviation: %lf usec\n", stddev); + +#define MAX_DIFF_USEC (500*1000) +#define MAX_STDDEV_USEC (500*1000) +#define ODD_DIFF_USEC (2000) +#define ODD_STDDEV_USEC (2000) + + if (mean_diff < 0 || mean_diff > MAX_DIFF_USEC || stddev > MAX_STDDEV_USEC) { + printf("Either your system is under ridiculous load, or the " + "timer backend is broken.\n"); + ret = 1; + } else if (mean_diff > ODD_DIFF_USEC || stddev > ODD_STDDEV_USEC) { + printf("Either your system is a bit slow or the " + "timer backend is odd.\n"); + ret = 0; + } else { + printf("Looks good enough.\n"); + ret = 0; + } + + timer_free(NULL); + + for (i = 0; i < N_TIMERS; ++i) { + timer_free(timers[i]); + } + timers_shutdown(); + return ret; +} diff --git a/src/test/test.c b/src/test/test.c index ed167a3e67..1595c8ee4f 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -1159,6 +1159,7 @@ extern struct testcase_t oom_tests[]; extern struct testcase_t options_tests[]; extern struct testcase_t policy_tests[]; extern struct testcase_t procmon_tests[]; +extern struct testcase_t pubsub_tests[]; extern struct testcase_t pt_tests[]; extern struct testcase_t relay_tests[]; extern struct testcase_t relaycell_tests[]; @@ -1177,6 +1178,7 @@ extern struct testcase_t util_tests[]; extern struct testcase_t util_format_tests[]; extern struct testcase_t util_process_tests[]; extern struct testcase_t dns_tests[]; +extern struct testcase_t handle_tests[]; struct testgroup_t testgroups[] = { { "", test_array }, @@ -1230,7 +1232,9 @@ struct testgroup_t testgroups[] = { { "util/format/", util_format_tests }, { "util/logging/", logging_tests }, { "util/process/", util_process_tests }, + { "util/pubsub/", pubsub_tests }, { "util/thread/", thread_tests }, + { "util/handle/", handle_tests }, { "dns/", dns_tests }, END_OF_GROUPS }; diff --git a/src/test/test.h b/src/test/test.h index e618ce1224..153b7cae00 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -73,7 +73,7 @@ {print_ = (I64_PRINTF_TYPE) value_;}, {}, TT_EXIT_TEST_FUNCTION) const char *get_fname(const char *name); -crypto_pk_t *pk_generate(int idx); +struct crypto_pk_t *pk_generate(int idx); #define US2_CONCAT_2__(a, b) a ## __ ## b #define US_CONCAT_2__(a, b) a ## _ ## b diff --git a/src/test/test_bt.sh b/src/test/test_bt.sh index 033acac955..83fa3ff24b 100755 --- a/src/test/test_bt.sh +++ b/src/test/test_bt.sh @@ -4,7 +4,7 @@ exitcode=0 "${builddir:-.}/src/test/test-bt-cl" backtraces || exit $? -"${builddir:-.}/src/test/test-bt-cl" assert | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" -"${builddir:-.}/src/test/test-bt-cl" crash | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" +"${builddir:-.}/src/test/test-bt-cl" assert 2>&1 | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" +"${builddir:-.}/src/test/test-bt-cl" crash 2>&1 | "${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/bt_test.py" || exitcode="$?" exit ${exitcode} diff --git a/src/test/test_connection.c b/src/test/test_connection.c index 15ae973f00..6f7aef879c 100644 --- a/src/test/test_connection.c +++ b/src/test/test_connection.c @@ -705,7 +705,7 @@ test_conn_download_status(void *arg) /* now try closing the one that isn't downloading: * these tests won't work unless tor thinks it is bootstrapping */ - tt_assert(networkstatus_consensus_is_boostrapping(time(NULL))); + tt_assert(networkstatus_consensus_is_bootstrapping(time(NULL))); tt_assert(connection_dir_count_by_purpose_and_resource( TEST_CONN_RSRC_PURPOSE, diff --git a/src/test/test_controller.c b/src/test/test_controller.c index 7f9db4312f..b276e06787 100644 --- a/src/test/test_controller.c +++ b/src/test/test_controller.c @@ -154,10 +154,61 @@ test_rend_service_parse_port_config(void *arg) tor_free(err_msg); } +static void +test_add_onion_helper_clientauth(void *arg) +{ + rend_authorized_client_t *client = NULL; + char *err_msg = NULL; + int created = 0; + + (void)arg; + + /* Test "ClientName" only. */ + client = add_onion_helper_clientauth("alice", &created, &err_msg); + tt_assert(client); + tt_assert(created); + tt_assert(!err_msg); + rend_authorized_client_free(client); + + /* Test "ClientName:Blob" */ + client = add_onion_helper_clientauth("alice:475hGBHPlq7Mc0cRZitK/B", + &created, &err_msg); + tt_assert(client); + tt_assert(!created); + tt_assert(!err_msg); + rend_authorized_client_free(client); + + /* Test invalid client names */ + client = add_onion_helper_clientauth("no*asterisks*allowed", &created, + &err_msg); + tt_assert(!client); + tt_assert(err_msg); + tor_free(err_msg); + + /* Test invalid auth cookie */ + client = add_onion_helper_clientauth("alice:12345", &created, &err_msg); + tt_assert(!client); + tt_assert(err_msg); + tor_free(err_msg); + + /* Test invalid syntax */ + client = add_onion_helper_clientauth(":475hGBHPlq7Mc0cRZitK/B", &created, + &err_msg); + tt_assert(!client); + tt_assert(err_msg); + tor_free(err_msg); + + done: + rend_authorized_client_free(client); + tor_free(err_msg); +} + struct testcase_t controller_tests[] = { { "add_onion_helper_keyarg", test_add_onion_helper_keyarg, 0, NULL, NULL }, { "rend_service_parse_port_config", test_rend_service_parse_port_config, 0, NULL, NULL }, + { "add_onion_helper_clientauth", test_add_onion_helper_clientauth, 0, NULL, + NULL }, END_OF_TESTCASES }; diff --git a/src/test/test_handles.c b/src/test/test_handles.c new file mode 100644 index 0000000000..8aaae13845 --- /dev/null +++ b/src/test/test_handles.c @@ -0,0 +1,95 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" +#include "test.h" + +#include "util.h" +#include "handles.h" + +typedef struct demo_t { + HANDLE_ENTRY(demo, demo_t); + int val; +} demo_t; + +HANDLE_DECL(demo, demo_t, static); +HANDLE_IMPL(demo, demo_t, static); + +static demo_t * +demo_new(int val) +{ + demo_t *d = tor_malloc_zero(sizeof(demo_t)); + d->val = val; + return d; +} + +static void +demo_free(demo_t *d) +{ + if (d == NULL) + return; + demo_handles_clear(d); + tor_free(d); +} + +static void +test_handle_basic(void *arg) +{ + (void) arg; + demo_t *d1 = NULL, *d2 = NULL; + demo_handle_t *wr1 = NULL, *wr2 = NULL, *wr3 = NULL, *wr4 = NULL; + + d1 = demo_new(9000); + d2 = demo_new(9009); + + wr1 = demo_handle_new(d1); + wr2 = demo_handle_new(d1); + wr3 = demo_handle_new(d1); + wr4 = demo_handle_new(d2); + + tt_assert(wr1); + tt_assert(wr2); + tt_assert(wr3); + tt_assert(wr4); + + tt_ptr_op(demo_handle_get(wr1), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr2), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr3), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_handle_free(wr1); + wr1 = NULL; + tt_ptr_op(demo_handle_get(wr2), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr3), OP_EQ, d1); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_free(d1); + d1 = NULL; + tt_ptr_op(demo_handle_get(wr2), OP_EQ, NULL); + tt_ptr_op(demo_handle_get(wr3), OP_EQ, NULL); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_handle_free(wr2); + wr2 = NULL; + tt_ptr_op(demo_handle_get(wr3), OP_EQ, NULL); + tt_ptr_op(demo_handle_get(wr4), OP_EQ, d2); + + demo_handle_free(wr3); + wr3 = NULL; + done: + demo_handle_free(wr1); + demo_handle_free(wr2); + demo_handle_free(wr3); + demo_handle_free(wr4); + demo_free(d1); + demo_free(d2); +} + +#define HANDLE_TEST(name, flags) \ + { #name, test_handle_ ##name, (flags), NULL, NULL } + +struct testcase_t handle_tests[] = { + HANDLE_TEST(basic, 0), + END_OF_TESTCASES +}; + diff --git a/src/test/test_hs.c b/src/test/test_hs.c index 49939a53cf..1daa1552e9 100644 --- a/src/test/test_hs.c +++ b/src/test/test_hs.c @@ -435,6 +435,67 @@ test_hs_rend_data(void *arg) rend_data_free(client_dup); } +/* Test encoding and decoding service authorization cookies */ +static void +test_hs_auth_cookies(void *arg) +{ +#define TEST_COOKIE_RAW ((const uint8_t *) "abcdefghijklmnop") +#define TEST_COOKIE_ENCODED "YWJjZGVmZ2hpamtsbW5vcA" +#define TEST_COOKIE_ENCODED_STEALTH "YWJjZGVmZ2hpamtsbW5vcB" +#define TEST_COOKIE_ENCODED_INVALID "YWJjZGVmZ2hpamtsbW5vcD" + + char *encoded_cookie; + uint8_t raw_cookie[REND_DESC_COOKIE_LEN]; + rend_auth_type_t auth_type; + char *err_msg; + int re; + + (void)arg; + + /* Test that encoding gives the expected result */ + encoded_cookie = rend_auth_encode_cookie(TEST_COOKIE_RAW, REND_BASIC_AUTH); + tt_str_op(encoded_cookie, OP_EQ, TEST_COOKIE_ENCODED); + tor_free(encoded_cookie); + + encoded_cookie = rend_auth_encode_cookie(TEST_COOKIE_RAW, REND_STEALTH_AUTH); + tt_str_op(encoded_cookie, OP_EQ, TEST_COOKIE_ENCODED_STEALTH); + tor_free(encoded_cookie); + + /* Decoding should give the original value */ + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED, raw_cookie, &auth_type, + &err_msg); + tt_assert(!re); + tt_assert(!err_msg); + tt_mem_op(raw_cookie, OP_EQ, TEST_COOKIE_RAW, REND_DESC_COOKIE_LEN); + tt_int_op(auth_type, OP_EQ, REND_BASIC_AUTH); + memset(raw_cookie, 0, sizeof(raw_cookie)); + + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED_STEALTH, raw_cookie, + &auth_type, &err_msg); + tt_assert(!re); + tt_assert(!err_msg); + tt_mem_op(raw_cookie, OP_EQ, TEST_COOKIE_RAW, REND_DESC_COOKIE_LEN); + tt_int_op(auth_type, OP_EQ, REND_STEALTH_AUTH); + memset(raw_cookie, 0, sizeof(raw_cookie)); + + /* Decoding with padding characters should also work */ + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED "==", raw_cookie, NULL, + &err_msg); + tt_assert(!re); + tt_assert(!err_msg); + tt_mem_op(raw_cookie, OP_EQ, TEST_COOKIE_RAW, REND_DESC_COOKIE_LEN); + + /* Decoding with an unknown type should fail */ + re = rend_auth_decode_cookie(TEST_COOKIE_ENCODED_INVALID, raw_cookie, + &auth_type, &err_msg); + tt_int_op(re, OP_LT, 0); + tt_assert(err_msg); + tor_free(err_msg); + + done: + return; +} + struct testcase_t hs_tests[] = { { "hs_rend_data", test_hs_rend_data, TT_FORK, NULL, NULL }, @@ -445,6 +506,8 @@ struct testcase_t hs_tests[] = { { "pick_bad_tor2web_rendezvous_node", test_pick_bad_tor2web_rendezvous_node, TT_FORK, NULL, NULL }, + { "hs_auth_cookies", test_hs_auth_cookies, TT_FORK, + NULL, NULL }, END_OF_TESTCASES }; diff --git a/src/test/test_options.c b/src/test/test_options.c index 4f24757a85..20e8dd563a 100644 --- a/src/test/test_options.c +++ b/src/test/test_options.c @@ -513,8 +513,9 @@ test_options_validate__nickname(void *ignored) ret = options_validate(tdata->old_opt, tdata->opt, tdata->def_opt, 0, &msg); tt_int_op(ret, OP_EQ, -1); tt_str_op(msg, OP_EQ, - "Nickname 'ThisNickNameIsABitTooLong' is wrong length or" - " contains illegal characters."); + "Nickname 'ThisNickNameIsABitTooLong', nicknames must be between " + "1 and 19 characters inclusive, and must contain only the " + "characters [a-zA-Z0-9]."); tor_free(msg); free_options_test_data(tdata); diff --git a/src/test/test_pubsub.c b/src/test/test_pubsub.c new file mode 100644 index 0000000000..547d6c6b32 --- /dev/null +++ b/src/test/test_pubsub.c @@ -0,0 +1,85 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file test_pubsub.c + * \brief Unit tests for publish-subscribe abstraction. + **/ + +#include "or.h" +#include "test.h" +#include "pubsub.h" + +DECLARE_PUBSUB_STRUCT_TYPES(foobar) +DECLARE_PUBSUB_TOPIC(foobar) +DECLARE_NOTIFY_PUBSUB_TOPIC(static, foobar) +IMPLEMENT_PUBSUB_TOPIC(static, foobar) + +struct foobar_event_data_t { + unsigned u; + const char *s; +}; + +struct foobar_subscriber_data_t { + const char *name; + long l; +}; + +static int +foobar_sub1(foobar_event_data_t *ev, foobar_subscriber_data_t *mine) +{ + ev->u += 10; + mine->l += 100; + return 0; +} + +static int +foobar_sub2(foobar_event_data_t *ev, foobar_subscriber_data_t *mine) +{ + ev->u += 5; + mine->l += 50; + return 0; +} + +static void +test_pubsub_basic(void *arg) +{ + (void)arg; + foobar_subscriber_data_t subdata1 = { "hi", 0 }; + foobar_subscriber_data_t subdata2 = { "wow", 0 }; + const foobar_subscriber_t *sub1; + const foobar_subscriber_t *sub2; + foobar_event_data_t ed = { 0, "x" }; + foobar_event_data_t ed2 = { 0, "y" }; + sub1 = foobar_subscribe(foobar_sub1, &subdata1, SUBSCRIBE_ATSTART, 100); + tt_assert(sub1); + + foobar_notify(&ed, 0); + tt_int_op(subdata1.l, OP_EQ, 100); + tt_int_op(subdata2.l, OP_EQ, 0); + tt_int_op(ed.u, OP_EQ, 10); + + sub2 = foobar_subscribe(foobar_sub2, &subdata2, 0, 5); + tt_assert(sub2); + + foobar_notify(&ed2, 0); + tt_int_op(subdata1.l, OP_EQ, 200); + tt_int_op(subdata2.l, OP_EQ, 50); + tt_int_op(ed2.u, OP_EQ, 15); + + foobar_unsubscribe(sub1); + + foobar_notify(&ed, 0); + tt_int_op(subdata1.l, OP_EQ, 200); + tt_int_op(subdata2.l, OP_EQ, 100); + tt_int_op(ed.u, OP_EQ, 15); + + done: + foobar_clear(); +} + +struct testcase_t pubsub_tests[] = { + { "pubsub_basic", test_pubsub_basic, TT_FORK, NULL, NULL }, + END_OF_TESTCASES +}; + diff --git a/src/win32/orconfig.h b/src/win32/orconfig.h index 67d023dd8d..9469245ba7 100644 --- a/src/win32/orconfig.h +++ b/src/win32/orconfig.h @@ -229,7 +229,7 @@ #define USING_TWOS_COMPLEMENT /* Version number of package */ -#define VERSION "0.2.8.2-alpha-dev" +#define VERSION "0.2.9.0-alpha-dev" |