Move address_set to src/or

This is temporary, until src/or is split.

Putting this in containers would be another logical alternative,
except that addresses depend on containers, and we don't like
cycles.

4 files changed, 105 insertions, 1 deletions

diff --git a/src/or/address_set.c b/src/or/address_set.c
new file mode 100644
index 0000000000..927a5597c0
--- /dev/null
+++ b/src/or/address_set.c
@@ -0,0 +1,71 @@
+/* Copyright (c) 2018-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file address_set.c
+ * \brief Implementation for a set of addresses.
+ *
+ * This module was first written on a semi-emergency basis to improve the
+ * robustness of the anti-DoS module.  As such, it's written in a pretty
+ * conservative way, and should be susceptible to improvement later on.
+ **/
+
+#include "orconfig.h"
+#include "or/address_set.h"
+#include "lib/net/address.h"
+#include "lib/container/bloomfilt.h"
+#include "lib/crypt_ops/crypto_rand.h"
+#include "siphash.h"
+
+/* Wrap our hash function to have the signature that the bloom filter
+ * needs. */
+static uint64_t
+bloomfilt_addr_hash(const struct sipkey *key,
+                    const void *item)
+{
+  return tor_addr_keyed_hash(key, item);
+}
+
+/**
+ * Allocate and return an address_set, suitable for holding up to
+ * <b>max_address_guess</b> distinct values.
+ */
+address_set_t *
+address_set_new(int max_addresses_guess)
+{
+  uint8_t k[BLOOMFILT_KEY_LEN];
+  crypto_rand((void*)k, sizeof(k));
+  return bloomfilt_new(max_addresses_guess, bloomfilt_addr_hash, k);
+}
+
+/**
+ * Add <b>addr</b> to <b>set</b>.
+ *
+ * All future queries for <b>addr</b> in set will return true. Removing
+ * items is not possible.
+ */
+void
+address_set_add(address_set_t *set, const struct tor_addr_t *addr)
+{
+  bloomfilt_add(set, addr);
+}
+
+/** As address_set_add(), but take an ipv4 address in host order. */
+void
+address_set_add_ipv4h(address_set_t *set, uint32_t addr)
+{
+  tor_addr_t a;
+  tor_addr_from_ipv4h(&a, addr);
+  address_set_add(set, &a);
+}
+
+/**
+ * Return true if <b>addr</b> is a member of <b>set</b>.  (And probably,
+ * return false if <b>addr</b> is not a member of set.)
+ */
+int
+address_set_probably_contains(const address_set_t *set,
+                              const struct tor_addr_t *addr)
+{
+  return bloomfilt_probably_contains(set, addr);
+}
diff --git a/src/or/address_set.h b/src/or/address_set.h
new file mode 100644
index 0000000000..2efa1cb03b
--- /dev/null
+++ b/src/or/address_set.h
@@ -0,0 +1,31 @@
+/* Copyright (c) 2018-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file address_set.h
+ * \brief Types to handle sets of addresses.
+ **/
+
+#ifndef TOR_ADDRESS_SET_H
+#define TOR_ADDRESS_SET_H
+
+#include "orconfig.h"
+#include "lib/cc/torint.h"
+#include "lib/container/bloomfilt.h"
+
+/**
+ * An address_set_t represents a set of tor_addr_t values. The implementation
+ * is probabilistic: false negatives cannot occur but false positives are
+ * possible.
+ */
+typedef struct bloomfilt_t address_set_t;
+struct tor_addr_t;
+
+address_set_t *address_set_new(int max_addresses_guess);
+#define address_set_free(set) bloomfilt_free(set)
+void address_set_add(address_set_t *set, const struct tor_addr_t *addr);
+void address_set_add_ipv4h(address_set_t *set, uint32_t addr);
+int address_set_probably_contains(const address_set_t *set,
+                                  const struct tor_addr_t *addr);
+
+#endif
diff --git a/src/or/include.am b/src/or/include.am
index 9b5f7c1f60..ad7ee69bf5 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -19,6 +19,7 @@ EXTRA_DIST+= src/or/ntmain.c src/or/Makefile.nmake
 
 LIBTOR_APP_A_SOURCES = \
 	src/or/addressmap.c				\
+	src/or/address_set.c				\
 	src/or/bridges.c				\
 	src/or/channel.c				\
 	src/or/channelpadding.c				\
@@ -180,6 +181,7 @@ endif
 
 ORHEADERS = \
 	src/or/addressmap.h				\
+	src/or/address_set.h				\
 	src/or/addr_policy_st.h				\
 	src/or/authority_cert_st.h			\
 	src/or/auth_dirs.inc				\
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index bc04ab9526..51fd0015df 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -42,7 +42,7 @@
 
 #include "or/or.h"
 #include "lib/net/address.h"
-#include "common/address_set.h"
+#include "or/address_set.h"
 #include "or/bridges.h"
 #include "or/config.h"
 #include "or/control.h"