#
#
# add_file "randomizer.cc"
# content [d52b91acd41a39d4fd88904da51e9f651ad133fe]
#
# add_file "randomizer.hh"
# content [a28dd5739fcc4a23680f460fa428e42654e21e77]
#
# patch "ChangeLog"
# from [57cd41bd38f7418a78c0d2ad32fda45b9a90bca6]
# to [5796d8bcc7842862177f0d4f8bfb1b5a6fd172fe]
#
# patch "Makefile.am"
# from [f8f60ee0c94da567d51a59fdadabf61979f3ea27]
# to [65caebb5283ccc3ce17a96a8d2ff89a2efb5af6c]
#
# patch "charset.cc"
# from [81d5e2619337eb076e1511b9980a2dc3fa3b1e68]
# to [f7b71f28c5f99965532a3fcac9580df7026d829c]
#
# patch "netxx_pipe.cc"
# from [8b395427a639ef059cba75dc723b8399adf02055]
# to [8e75c59d30d1922022dce7a3edf464f8942c2a81]
#
# patch "randomfile.hh"
# from [c5f159f6c5b9878ac7a12d37def6d696cf4b2a9c]
# to [c3603046d013d2d2c16edbb21969cdcb72fc1c7e]
#
# patch "refiner.cc"
# from [63eb28ab5c190ed59bc5dfd84a0cf7e42e0bb456]
# to [dcb840fc67b92a9bbba3982c715ef11132f666a3]
#
# patch "refiner.hh"
# from [3c9e3b79c74a9a4552c36ae3dd07642cda777207]
# to [c95dc3897a862cf1c032d5b05ca0ba9a60b764c3]
#
# patch "roster.cc"
# from [76aa75696d056c98a890b0b0bb6c1164363a919e]
# to [d4c7f97919e49a5191439bf9bac604b734b7774f]
#
# patch "unit_tests.cc"
# from [a69aa50b93e2be1ff1531f685a137d750bcffddd]
# to [0681ea82bcb92ab13dba3cff4e8de17e2363e58a]
#
# patch "unit_tests.hh"
# from [a17ee7dc506a7bbfc4afc903e9d66ed108bfa1a0]
# to [f725a5a24793b324839108e7dd18bebaf9cb9955]
#
============================================================
--- randomizer.cc d52b91acd41a39d4fd88904da51e9f651ad133fe
+++ randomizer.cc d52b91acd41a39d4fd88904da51e9f651ad133fe
@@ -0,0 +1,56 @@
+// Copyright (C) 2006 Graydon Hoare
+//
+// This program is made available under the GNU GPL version 2.0 or
+// greater. See the accompanying file COPYING for details.
+//
+// This program is distributed WITHOUT ANY WARRANTY; without even the
+// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+// PURPOSE.
+
+#include "randomizer.hh"
+#include
+
+namespace randomizer
+{
+ static boost::mt19937 *rng = NULL;
+
+ boost::mt19937 &get_rng()
+ {
+ if (!rng)
+ rng = new boost::mt19937;
+ return *rng;
+ }
+
+ bool flip(size_t n)
+ {
+ return bernoulli(1.0 / static_cast(n));
+ }
+
+ void seed(size_t n)
+ {
+ if (rng)
+ delete rng;
+ rng = new boost::mt19937(n);
+ }
+
+ size_t uniform(size_t n)
+ {
+ return boost::random_number_generator(get_rng())(n);
+ }
+
+ bool bernoulli(double p)
+ {
+ typedef boost::mt19937& rng_t;
+ typedef boost::bernoulli_distribution dist_t;
+ return boost::variate_generator(get_rng(), dist_t(p))();
+ }
+
+}
+
+// Local Variables:
+// mode: C++
+// fill-column: 76
+// c-file-style: "gnu"
+// indent-tabs-mode: nil
+// End:
+// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
============================================================
--- randomizer.hh a28dd5739fcc4a23680f460fa428e42654e21e77
+++ randomizer.hh a28dd5739fcc4a23680f460fa428e42654e21e77
@@ -0,0 +1,33 @@
+#ifndef __RANDOMIZER_HH__
+#define __RANDOMIZER_HH__
+
+// Copyright (C) 2006 Graydon Hoare
+//
+// This program is made available under the GNU GPL version 2.0 or
+// greater. See the accompanying file COPYING for details.
+//
+// This program is distributed WITHOUT ANY WARRANTY; without even the
+// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+// PURPOSE.
+
+// This is just a set of utility methods built on top of boost::random.
+//
+// Our purpose is to create a global randomization utility for unit
+// tests. Nothing fancy.
+
+#include
+
+namespace randomizer
+{
+ void seed(size_t n);
+
+ // uniform process in [0,n]
+ size_t uniform(size_t n);
+
+ // boolean process with prob(true) = p, prob(false) = 1-p.
+ bool bernoulli(double p);
+
+ bool flip(size_t n = 2);
+};
+
+#endif
============================================================
--- ChangeLog 57cd41bd38f7418a78c0d2ad32fda45b9a90bca6
+++ ChangeLog 5796d8bcc7842862177f0d4f8bfb1b5a6fd172fe
@@ -1,3 +1,14 @@
+2006-07-04 Graydon Hoare
+
+ * randomizer.{cc,hh}: New helpers for prngs.
+ * Makefile.am (MOST_SOURCES): Add them.
+ * charset.cc: Fix some missing initializers in unit tests.
+ * randomfile.hh: Use randomizer, not rand().
+ * roster.cc: Likewise.
+ * refiner.{cc,hh}: Add random unit tester,
+ and fix serious protocol-wedging bug.
+ * unit_tests.{cc,hh}: Register refiner tests.
+
2006-06-17 Graydon Hoare
* Makefile.am: Permit building 'tester' with static boost.
============================================================
--- Makefile.am f8f60ee0c94da567d51a59fdadabf61979f3ea27
+++ Makefile.am 65caebb5283ccc3ce17a96a8d2ff89a2efb5af6c
@@ -66,7 +66,8 @@
\
cleanup.hh unit_tests.hh \
cycle_detector.hh randomfile.hh adler32.hh \
- netio.hh smap.hh gettext.h \
+ randomizer.cc randomizer.hh \
+ netio.hh smap.hh gettext.h \
package_revision.c package_revision.h \
package_full_revision.c package_full_revision.h options.hh \
i18n.h parallel_iter.hh safe_map.hh pch.hh
============================================================
--- charset.cc 81d5e2619337eb076e1511b9980a2dc3fa3b1e68
+++ charset.cc f7b71f28c5f99965532a3fcac9580df7026d829c
@@ -458,36 +458,36 @@
0x0644, 0x064A, 0x0647, 0x0645, 0x0627, 0x0628, 0x062A, 0x0643,
0x0644, 0x0645, 0x0648, 0x0634, 0x0639, 0x0631, 0x0628, 0x064A,
0x061F},
- IDNA_ACE_PREFIX "egbpdaj6bu4bxfgehfvwxn", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "egbpdaj6bu4bxfgehfvwxn", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Chinese (simplified)", 9,
{
0x4ED6, 0x4EEC, 0x4E3A, 0x4EC0, 0x4E48, 0x4E0D, 0x8BF4, 0x4E2D, 0x6587},
- IDNA_ACE_PREFIX "ihqwcrb4cv8a8dqg056pqjye", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "ihqwcrb4cv8a8dqg056pqjye", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Chinese (traditional)", 9,
{
0x4ED6, 0x5011, 0x7232, 0x4EC0, 0x9EBD, 0x4E0D, 0x8AAA, 0x4E2D, 0x6587},
- IDNA_ACE_PREFIX "ihqwctvzc91f659drss3x8bo0yb", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "ihqwctvzc91f659drss3x8bo0yb", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Czech", 22,
{
0x0050, 0x0072, 0x006F, 0x010D, 0x0070, 0x0072, 0x006F, 0x0073,
0x0074, 0x011B, 0x006E, 0x0065, 0x006D, 0x006C, 0x0075, 0x0076,
0x00ED, 0x010D, 0x0065, 0x0073, 0x006B, 0x0079},
- IDNA_ACE_PREFIX "Proprostnemluvesky-uyb24dma41a", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "Proprostnemluvesky-uyb24dma41a", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Hebrew", 22,
{
0x05DC, 0x05DE, 0x05D4, 0x05D4, 0x05DD, 0x05E4, 0x05E9, 0x05D5,
0x05D8, 0x05DC, 0x05D0, 0x05DE, 0x05D3, 0x05D1, 0x05E8, 0x05D9,
0x05DD, 0x05E2, 0x05D1, 0x05E8, 0x05D9, 0x05EA},
- IDNA_ACE_PREFIX "4dbcagdahymbxekheh6e0a7fei0b", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "4dbcagdahymbxekheh6e0a7fei0b", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Hindi (Devanagari)", 30,
{
@@ -496,7 +496,7 @@
0x0928, 0x0939, 0x0940, 0x0902, 0x092C, 0x094B, 0x0932, 0x0938,
0x0915, 0x0924, 0x0947, 0x0939, 0x0948, 0x0902},
IDNA_ACE_PREFIX "i1baa7eci9glrd9b2ae1bj0hfcgg6iyaf8o0a1dig0cd", 0, 0,
- IDNA_SUCCESS},
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese (kanji and hiragana)", 18,
{
@@ -504,7 +504,7 @@
0x3092, 0x8A71, 0x3057, 0x3066, 0x304F, 0x308C, 0x306A, 0x3044,
0x306E, 0x304B},
IDNA_ACE_PREFIX "n8jok5ay5dzabd5bym9f0cm5685rrjetr6pdxa", 0, 0,
- IDNA_SUCCESS},
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Russian (Cyrillic)", 28,
{
@@ -523,7 +523,7 @@
0x0065, 0x0068, 0x0061, 0x0062, 0x006C, 0x0061, 0x0072, 0x0065,
0x006E, 0x0045, 0x0073, 0x0070, 0x0061, 0x00F1, 0x006F, 0x006C},
IDNA_ACE_PREFIX "PorqunopuedensimplementehablarenEspaol-fmd56a", 0, 0,
- IDNA_SUCCESS},
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Vietnamese", 31,
{
@@ -532,13 +532,13 @@
0x0063, 0x0068, 0x1EC9, 0x006E, 0x00F3, 0x0069, 0x0074, 0x0069,
0x1EBF, 0x006E, 0x0067, 0x0056, 0x0069, 0x1EC7, 0x0074},
IDNA_ACE_PREFIX "TisaohkhngthchnitingVit-kjcr8268qyxafd2f1b9g", 0, 0,
- IDNA_SUCCESS},
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese", 8,
{
0x0033, 0x5E74, 0x0042, 0x7D44, 0x91D1, 0x516B, 0x5148, 0x751F},
- IDNA_ACE_PREFIX "3B-ww4c5e180e575a65lsy2b", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "3B-ww4c5e180e575a65lsy2b", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese", 24,
{
@@ -546,7 +546,7 @@
0x0074, 0x0068, 0x002D, 0x0053, 0x0055, 0x0050, 0x0045, 0x0052,
0x002D, 0x004D, 0x004F, 0x004E, 0x004B, 0x0045, 0x0059, 0x0053},
IDNA_ACE_PREFIX "-with-SUPER-MONKEYS-pc58ag80a8qai00g7n9n", 0, 0,
- IDNA_SUCCESS},
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese", 25,
{
@@ -555,20 +555,20 @@
0x0079, 0x002D, 0x305D, 0x308C, 0x305E, 0x308C, 0x306E, 0x5834,
0x6240},
IDNA_ACE_PREFIX "Hello-Another-Way--fc4qua05auwb3674vfr0b", 0, 0,
- IDNA_SUCCESS},
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese", 8,
{
0x3072, 0x3068, 0x3064, 0x5C4B, 0x6839, 0x306E, 0x4E0B, 0x0032},
- IDNA_ACE_PREFIX "2-u9tlzr9756bt3uc0v", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "2-u9tlzr9756bt3uc0v", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese", 13,
{
0x004D, 0x0061, 0x006A, 0x0069, 0x3067, 0x004B, 0x006F, 0x0069,
0x3059, 0x308B, 0x0035, 0x79D2, 0x524D},
- IDNA_ACE_PREFIX "MajiKoi5-783gue6qz075azm5e", 0, 0, IDNA_SUCCESS,
- IDNA_SUCCESS},
+ IDNA_ACE_PREFIX "MajiKoi5-783gue6qz075azm5e", 0, 0,
+ IDNA_SUCCESS, IDNA_SUCCESS},
{
"Japanese", 9,
{
============================================================
--- netxx_pipe.cc 8b395427a639ef059cba75dc723b8399adf02055
+++ netxx_pipe.cc 8e75c59d30d1922022dce7a3edf464f8942c2a81
@@ -59,6 +59,11 @@
overlap.hEvent = CreateEvent(0, TRUE, TRUE, 0);
bytes_available = 0;
I(overlap.hEvent != 0);
+#else
+ int flags = fcntl(readfd, F_GETFL, 0);
+ I(fcntl(readfd, F_SETFL, flags | O_NONBLOCK) != -1);
+ flags = fcntl(writefd, F_GETFL, 0);
+ I(fcntl(writefd, F_SETFL, flags | O_NONBLOCK) != -1);
#endif
}
============================================================
--- randomfile.hh c5f159f6c5b9878ac7a12d37def6d696cf4b2a9c
+++ randomfile.hh c3603046d013d2d2c16edbb21969cdcb72fc1c7e
@@ -12,38 +12,28 @@
#include
#include
-#include
#include
+#include "randomizer.hh"
+
struct file_randomizer
{
-
std::vector lines;
std::string prefix;
- void seed(int seed = 0xf00feed)
- {
- srand (seed);
- }
-
size_t random_index(bool last_line_ok = true)
{
if (last_line_ok)
- return static_cast(rand() % lines.size());
+ return static_cast(randomizer::uniform(lines.size()));
else
{
if (lines.size() == 0)
return 0;
else
- return static_cast(rand() % (lines.size() - 1));
+ return static_cast(randomizer::uniform(lines.size() - 1));
}
}
- bool random_bool()
- {
- return (rand() % 2 == 0);
- }
-
void set_prefix(std::string const & p)
{
prefix = p;
@@ -108,12 +98,12 @@
{
file_randomizer fr;
- fr.seed(seed);
+ randomizer::seed(seed);
// maybe prepend something to one side or the other
- if (fr.random_bool())
+ if (randomizer::flip())
{
fr.prepend_sequential_lines();
- if (fr.random_bool())
+ if (randomizer::flip())
fr.append_to(left);
else
fr.append_to(right);
@@ -124,14 +114,14 @@
for (int h = 0; h < n_hunks; ++h)
{
file_randomizer hr;
- hr.seed(seed + h);
+ randomizer::seed(seed + h);
hr.set_prefix(std::string("hunk ") + boost::lexical_cast(h) + " -- ");
hr.initial_sequential_lines(10);
hr.append_to(ancestor);
- if (hr.random_bool())
+ if (randomizer::flip())
{
// doing an insert
- if (hr.random_bool())
+ if (randomizer::flip())
{
// inserting in left
hr.append_to(right);
@@ -150,7 +140,7 @@
else
{
// doing a delete
- if (hr.random_bool())
+ if (randomizer::flip())
{
// deleting in left
hr.append_to(right);
@@ -169,10 +159,10 @@
}
// maybe append something to one side or the other
- if (fr.random_bool())
+ if (randomizer::flip())
{
fr.append_sequential_lines();
- if (fr.random_bool())
+ if (randomizer::flip())
fr.append_to(left);
else
fr.append_to(right);
============================================================
--- refiner.cc 63eb28ab5c190ed59bc5dfd84a0cf7e42e0bb456
+++ refiner.cc dcb840fc67b92a9bbba3982c715ef11132f666a3
@@ -26,6 +26,8 @@
using std::set_difference;
using std::string;
+using boost::dynamic_bitset;
+
// Our goal is to learn the complete set of items to send. To do this
// we exchange two types of refinement commands: queries and responses.
//
@@ -102,7 +104,8 @@
string typestr;
netcmd_item_type_to_string(type, typestr);
- L(FL("determined %d %s items to send") % items_to_send.size() % typestr);
+ // L(FL("%s determined %d %s items to send")
+ // % voicestr() % items_to_send.size() % typestr);
calculated_items_to_send = true;
}
@@ -114,11 +117,34 @@
our_node.extended_raw_prefix(slot, subprefix);
merkle_ptr our_subtree;
load_merkle_node(our_node.level + 1, subprefix, our_subtree);
+ // L(FL("%s queueing subquery on level %d\n") % voicestr() % (our_node.level + 1));
cb.queue_refine_cmd(refinement_query, *our_subtree);
++queries_in_flight;
}
void
+refiner::send_synthetic_subquery(merkle_node const & our_node, size_t slot)
+{
+ id val;
+ size_t subslot;
+ dynamic_bitset subprefix;
+
+ our_node.get_raw_slot(slot, val);
+ pick_slot_and_prefix_for_value(val, our_node.level + 1, subslot, subprefix);
+
+ merkle_node synth_node;
+ synth_node.pref = subprefix;
+ synth_node.level = our_node.level + 1;
+ synth_node.type = our_node.type;
+ synth_node.set_raw_slot(subslot, val);
+ synth_node.set_slot_state(subslot, our_node.get_slot_state(slot));
+
+ // L(FL("%s queueing synthetic subquery on level %d\n") % voicestr() % (our_node.level + 1));
+ cb.queue_refine_cmd(refinement_query, synth_node);
+ ++queries_in_flight;
+}
+
+void
refiner::note_subtree_shared_with_peer(merkle_node const & our_node, size_t slot)
{
prefix pref;
@@ -148,6 +174,7 @@
peer_items.insert(slotval);
// Write a debug message
+ /*
{
hexenc hslotval;
their_node.get_hex_slot(slot, hslotval);
@@ -158,9 +185,10 @@
string typestr;
netcmd_item_type_to_string(their_node.type, typestr);
- L(FL("peer has %s '%s' at slot %d (in node '%s', level %d)")
- % typestr % hslotval % slot % hpref % their_node.level);
+ L(FL("%s's peer has %s '%s' at slot %d (in node '%s', level %d)")
+ % voicestr() % typestr % hslotval % slot % hpref % their_node.level);
}
+ */
}
@@ -169,14 +197,15 @@
{
merkle_ptr root;
load_merkle_node(0, prefix(""), root);
+ // L(FL("%s queueing initial node\n") % voicestr());
cb.queue_refine_cmd(refinement_query, *root);
++queries_in_flight;
sent_initial_query = true;
string typestr;
netcmd_item_type_to_string(type, typestr);
- L(FL("Beginning %s refinement.") % typestr);
+ L(FL("Beginning %s refinement on %s.") % typestr % voicestr());
}
-
+
void
refiner::process_done_command(size_t n_items)
{
@@ -186,12 +215,32 @@
calculate_items_to_send();
items_to_receive = n_items;
- L(FL("finished %s refinement: %d to send, %d to receive")
- % typestr % items_to_send.size() % items_to_receive);
+ L(FL("%s finished %s refinement: %d to send, %d to receive")
+ % voicestr() % typestr % items_to_send.size() % items_to_receive);
- if (voice == server_voice)
- cb.queue_done_cmd(type, items_to_send.size());
+ /*
+ if (local_items.size() < 25)
+ {
+ // Debugging aid.
+ L(FL("+++ %d items in %s") % local_items.size() % voicestr());
+ for (set::const_iterator i = local_items.begin();
+ i != local_items.end(); ++i)
+ {
+ hexenc hid;
+ encode_hexenc(*i, hid);
+ L(FL("%s item %s") % voicestr() % hid);
+ }
+ L(FL("--- items in %s") % voicestr());
+ }
+ */
+ if (voice == server_voice)
+ {
+ // L(FL("server responding to [done %s %d] with [done %s %d]")
+ // % typestr % n_items % typestr % items_to_send.size());
+ cb.queue_done_cmd(type, items_to_send.size());
+ }
+
done = true;
}
@@ -209,8 +258,9 @@
netcmd_item_type_to_string(their_node.type, typestr);
size_t lev = static_cast(their_node.level);
- L(FL("received refinement %s netcmd on %s node '%s', level %d")
- % (ty == refinement_query ? "query" : "response") % typestr % hpref % lev);
+ // L(FL("%s received refinement %s netcmd on %s node '%s', level %d") %
+ // voicestr() % (ty == refinement_query ? "query" : "response") %
+ // typestr % hpref % lev);
merkle_ptr our_node;
@@ -229,12 +279,27 @@
{
// Note any leaves they have.
if (their_node.get_slot_state(slot) == leaf_state)
+ note_item_in_peer(their_node, slot);
+
+ if (ty == refinement_query)
{
- note_item_in_peer(their_node, slot);
- // If we have their leaf somewhere in our subtree,
- // we need to tell them.
- if (our_node->get_slot_state(slot) == subtree_state)
+ // This block handles the interesting asymmetric cases of subtree
+ // vs. leaf.
+ //
+ // Note that in general we're not allowed to send a new query
+ // packet when we're looking at a response. This wrinkle is both
+ // why this block appears to do slightly more work than necessary,
+ // and why it's predicated on "ty == refinement_query". More detail
+ // in the cases below.
+
+ if (their_node.get_slot_state(slot) == leaf_state
+ && our_node->get_slot_state(slot) == subtree_state)
{
+ // If they have a leaf and we have a subtree, we need to look
+ // in our subtree to find if their leaf is present, and send
+ // them a "query" that will inform them, in passing, of the
+ // presence of our node.
+
id their_slotval;
their_node.get_raw_slot(slot, their_slotval);
size_t snum;
@@ -243,13 +308,46 @@
{
cb.queue_refine_cmd(refinement_query, *mp);
++queries_in_flight;
- }
+ }
+
}
+
+ else if (their_node.get_slot_state(slot) == subtree_state
+ && our_node->get_slot_state(slot) == leaf_state)
+ {
+ // If they have a subtree and we have a leaf, we need to
+ // arrange for a subquery to explore the subtree looking for
+ // the leaf in *their* subtree. The tricky part is that we
+ // cannot have this subquery triggered by our response
+ // packet. We need to initiate a new (redundant) query here to
+ // prompt our peer to explore the subtree.
+ //
+ // This is purely for the sake of balancing the bracketing of
+ // queries and responses: if they were to reply to our
+ // response packet, our query-in-flight counter would have
+ // temporarily dropped to zero and we'd have initiated
+ // streaming send mode.
+ //
+ // Yes, the need to invert the sense of queries in this case
+ // represents a misdesign in this generation of the netsync
+ // protocol. It still contains much less hair than it used to,
+ // so I'm willing to accept it.
+
+ send_synthetic_subquery(*our_node, slot);
+ }
+
+ // Finally: if they had an empty slot in either case, there's no
+ // subtree exploration to perform; the response packet will inform
+ // the peer of everything relevant know about this node: namely
+ // that they're going to receive a complete subtree, we know
+ // what's in it, and we'll tell them how many nodes to expect in
+ // the aggregate count of the 'done' commane.
+
}
// Compare any subtrees, if we both have subtrees.
- if (our_node->get_slot_state(slot) == subtree_state
- && their_node.get_slot_state(slot) == subtree_state)
+ if (their_node.get_slot_state(slot) == subtree_state
+ && our_node->get_slot_state(slot) == subtree_state)
{
id our_slotval, their_slotval;
their_node.get_raw_slot(slot, their_slotval);
@@ -264,11 +362,6 @@
else if (ty == refinement_query)
send_subquery(*our_node, slot);
}
-
- // Note: if they had a leaf (or empty) where I had a subtree, I
- // will have noted the leaf and will not send it. They will not
- // have any of the *other* parts of my subtree, so it's ok if I
- // eventually wind up sending the subtree-minus-their-leaf.
}
if (ty == refinement_response)
@@ -280,7 +373,10 @@
// Possibly this signals the end of refinement.
if (voice == client_voice && queries_in_flight == 0)
{
+ string typestr;
+ netcmd_item_type_to_string(their_node.type, typestr);
calculate_items_to_send();
+ // L(FL("client sending [done %s %d]") % typestr % items_to_send.size());
cb.queue_done_cmd(type, items_to_send.size());
}
}
@@ -288,13 +384,363 @@
{
// Always reply to every query with the current node.
I(ty == refinement_query);
+ // L(FL("%s queueing response to query on %d\n") % voicestr() % our_node->level);
cb.queue_refine_cmd(refinement_response, *our_node);
}
}
+#ifdef BUILD_UNIT_TESTS
+#include "randomizer.hh"
+#include "unit_tests.hh"
+#include
+#include
+using std::deque;
+using boost::shared_ptr;
+using randomizer::flip;
+using randomizer::uniform;
+using randomizer::bernoulli;
+struct
+refiner_pair
+{
+ // This structure acts as a mock netsync session. It's only purpose is to
+ // construct two refiners that are connected to one another, and route
+ // refinement calls back and forth between them.
+
+ struct
+ refiner_pair_callbacks : refiner_callbacks
+ {
+ refiner_pair & p;
+ bool is_client;
+ refiner_pair_callbacks(refiner_pair & p, bool is_client)
+ : p(p), is_client(is_client)
+ {}
+
+ virtual void queue_refine_cmd(refinement_type ty,
+ merkle_node const & our_node)
+ {
+ p.events.push_back(shared_ptr(new msg(is_client, ty, our_node)));
+ }
+
+ virtual void queue_done_cmd(netcmd_item_type ty,
+ size_t n_items)
+ {
+ p.events.push_back(shared_ptr(new msg(is_client, n_items)));
+ }
+ virtual ~refiner_pair_callbacks() {}
+ };
+
+ refiner_pair_callbacks client_cb;
+ refiner_pair_callbacks server_cb;
+ refiner client;
+ refiner server;
+
+ struct msg
+ {
+ msg(bool is_client, refinement_type ty, merkle_node const & node)
+ : op(refine),
+ ty(ty),
+ send_to_client(!is_client),
+ node(node)
+ {}
+
+ msg(bool is_client, size_t items)
+ : op(done),
+ send_to_client(!is_client),
+ n_items(items)
+ {}
+
+ enum { refine, done } op;
+ refinement_type ty;
+ bool send_to_client;
+ size_t n_items;
+ merkle_node node;
+ };
+
+ deque > events;
+ size_t n_msgs;
+
+ void crank()
+ {
+
+ shared_ptr m = events.front();
+ events.pop_front();
+ ++n_msgs;
+
+ switch (m->op)
+ {
+
+ case msg::refine:
+ if (m->send_to_client)
+ client.process_refinement_command(m->ty, m->node);
+ else
+ server.process_refinement_command(m->ty, m->node);
+ break;
+
+ case msg::done:
+ if (m->send_to_client)
+ client.process_done_command(m->n_items);
+ else
+ server.process_done_command(m->n_items);
+ break;
+ }
+ }
+
+ refiner_pair(set const & client_items,
+ set const & server_items) :
+ client_cb(*this, true),
+ server_cb(*this, false),
+ // The item type here really doesn't matter.
+ client(file_item, client_voice, client_cb),
+ server(file_item, server_voice, server_cb),
+ n_msgs(0)
+ {
+ for (set::const_iterator i = client_items.begin();
+ i != client_items.end(); ++i)
+ client.note_local_item(*i);
+
+ for (set::const_iterator i = server_items.begin();
+ i != server_items.end(); ++i)
+ server.note_local_item(*i);
+
+ client.reindex_local_items();
+ server.reindex_local_items();
+ client.begin_refinement();
+
+ while (! events.empty())
+ crank();
+
+ // Refinement should have completed by here.
+ BOOST_CHECK(client.done);
+ BOOST_CHECK(server.done);
+
+ check_set_differences("client", client);
+ check_set_differences("server", server);
+ check_no_redundant_sends("client->server",
+ client.items_to_send,
+ server.get_local_items());
+ check_no_redundant_sends("server->client",
+ server.items_to_send,
+ client.get_local_items());
+ BOOST_CHECK(client.items_to_send.size() == server.items_to_receive);
+ BOOST_CHECK(server.items_to_send.size() == client.items_to_receive);
+ L(FL("stats: %d total, %d cs, %d sc, %d msgs")
+ % (server.items_to_send.size() + client.get_local_items().size())
+ % client.items_to_send.size()
+ % server.items_to_send.size()
+ % n_msgs);
+ }
+
+ void print_if_unequal(char const * context,
+ char const * name1,
+ set const & set1,
+ char const * name2,
+ set const & set2)
+ {
+ if (set1 != set2)
+ {
+ L(FL("WARNING: Unequal sets in %s!") % context);
+ for (set::const_iterator i = set1.begin(); i != set1.end(); ++i)
+ {
+ hexenc hid;
+ encode_hexenc(*i, hid);
+ L(FL("%s: %s") % name1 % hid);
+ }
+
+ for (set::const_iterator i = set2.begin(); i != set2.end(); ++i)
+ {
+ hexenc hid;
+ encode_hexenc(*i, hid);
+ L(FL("%s: %s") % name2 % hid);
+ }
+ L(FL("end of unequal sets"));
+ }
+ }
+
+ void check_no_redundant_sends(char const * context,
+ set const & src,
+ set const & dst)
+ {
+ for (set::const_iterator i = src.begin(); i != src.end(); ++i)
+ {
+ set::const_iterator j = dst.find(*i);
+ if (j != dst.end())
+ {
+ hexenc hid;
+ encode_hexenc(*i, hid);
+ L(FL("WARNING: %s transmission will send redundant item %s")
+ % context % hid);
+ }
+ BOOST_CHECK(j == dst.end());
+ }
+ }
+
+ void check_set_differences(char const * context, refiner const & r)
+ {
+ set tmp;
+ set_difference(r.get_local_items().begin(), r.get_local_items().end(),
+ r.get_peer_items().begin(), r.get_peer_items().end(),
+ inserter(tmp, tmp.begin()));
+ print_if_unequal(context,
+ "diff(local,peer)", tmp,
+ "items_to_send", r.items_to_send);
+
+ BOOST_CHECK(tmp == r.items_to_send);
+ }
+};
+
+
+void
+check_combinations_of_sets(set const & s0,
+ set const & a,
+ set const & b)
+{
+ // Having composed our two input sets s0 and s1, we now construct the 2
+ // auxilary union-combinations of them -- {} and {s0 U s1} -- giving 4
+ // basic input sets. We then run 9 "interesting" pairwise combinations
+ // of these input sets.
+
+ set e, u, v;
+ set_union(s0.begin(), s0.end(), a.begin(), a.end(), inserter(u, u.begin()));
+ set_union(s0.begin(), s0.end(), b.begin(), b.end(), inserter(v, v.begin()));
+
+ { refiner_pair x(e, u); } // a large initial transfer
+ { refiner_pair x(u, e); } // a large initial transfer
+
+ { refiner_pair x(s0, u); } // a mostly-shared superset/subset
+ { refiner_pair x(u, s0); } // a mostly-shared superset/subset
+
+ { refiner_pair x(a, u); } // a mostly-unshared superset/subset
+ { refiner_pair x(u, a); } // a mostly-unshared superset/subset
+
+ { refiner_pair x(u, v); } // things to send in both directions
+ { refiner_pair x(v, u); } // things to send in both directions
+
+ { refiner_pair x(u, u); } // a large no-op
+}
+
+
+void
+build_random_set(set & s, size_t sz, bool clumpy)
+{
+ while (s.size() < sz)
+ {
+ string str(constants::merkle_hash_length_in_bytes, ' ');
+ for (size_t i = 0; i < constants::merkle_hash_length_in_bytes; ++i)
+ str[i] = static_cast(uniform(0xff));
+ s.insert(id(str));
+ if (clumpy && flip())
+ {
+ size_t clumpsz = uniform(7) + 1;
+ size_t pos = flip() ? str.size() - 1 : uniform(str.size());
+ for (size_t i = 0; s.size() < sz && i < clumpsz; ++i)
+ {
+ char c = str[pos];
+ if (c == static_cast(0xff))
+ break;
+ ++c;
+ str[pos] = c;
+ s.insert(id(str));
+ }
+ }
+ }
+}
+
+size_t
+perturbed(size_t n)
+{
+ // we sometimes perturb sizes to deviate a bit from natural word-multiple sizes
+ if (flip())
+ return n + uniform(5);
+ return n;
+}
+
+size_t
+modulated_size(size_t base_set_size, size_t i)
+{
+ if (i < 3)
+ return i+1;
+ else
+ return static_cast((static_cast(i - 2) / 5.0)
+ * static_cast(base_set_size));
+}
+
+
+void
+check_with_count(size_t base_set_size)
+{
+ if (base_set_size == 0)
+ return;
+
+ L(FL("running refinement check with base set size %d") % base_set_size);
+
+ // Our goal here is to construct a base set of a given size, and two
+ // secondary sets which will be combined with the base set in various
+ // ways.
+ //
+ // The secondary sets will be built at the following sizes:
+ //
+ // 1 element
+ // 2 elements
+ // 3 elements
+ // 0.2 * size of base set
+ // 0.4 * size of base set
+ // 0.8 * size of base set
+ //
+ // The base set is constructed in both clumpy and non-clumpy forms,
+ // making 6 * 6 * 2 = 72 variations.
+ //
+ // Since each group of sets creates 9 sync scenarios, each "size" creates
+ // 648 sync scenarios.
+
+ for (size_t c = 0; c < 2; ++c)
+ {
+ set s0;
+ build_random_set(s0, perturbed(base_set_size), c == 0);
+
+ for (size_t a = 0; a < 6; ++a)
+ {
+ set sa;
+ build_random_set(sa, modulated_size(perturbed(base_set_size), a), false);
+
+ for (size_t b = 0; b < 6; ++b)
+ {
+ set sb;
+ build_random_set(sb, modulated_size(perturbed(base_set_size), b), false);
+ check_combinations_of_sets(s0, sa, sb);
+ }
+ }
+ }
+}
+
+void
+check_various_counts()
+{
+ {
+ // Once with zero-zero, for good measure.
+ set s0;
+ refiner_pair x(s0, s0);
+ }
+
+ // We run 3 primary counts, giving 1944 tests. Note that there is some
+ // perturbation within the test, so we're not likely to feel side effects
+ // of landing on such pleasant round numbers.
+
+ check_with_count(1);
+ check_with_count(128);
+ check_with_count(1024);
+}
+
+void
+add_refiner_tests(test_suite * suite)
+{
+ suite->add(BOOST_TEST_CASE(&check_various_counts));
+}
+
+#endif
+
// Local Variables:
// mode: C++
// fill-column: 76
============================================================
--- refiner.hh 3c9e3b79c74a9a4552c36ae3dd07642cda777207
+++ refiner.hh c95dc3897a862cf1c032d5b05ca0ba9a60b764c3
@@ -68,11 +68,16 @@
size_t slot);
void note_subtree_shared_with_peer(merkle_node const & our_node, size_t slot);
void send_subquery(merkle_node const & our_node, size_t slot);
+ void send_synthetic_subquery(merkle_node const & our_node, size_t slot);
void note_item_in_peer(merkle_node const & their_node, size_t slot);
void load_merkle_node(size_t level, prefix const & pref,
merkle_ptr & node);
bool merkle_node_exists(size_t level, prefix const & pref);
void calculate_items_to_send();
+ std::string voicestr()
+ {
+ return voice == server_voice ? "server" : "client";
+ }
public:
@@ -87,6 +92,8 @@
return local_items.find(ident) != local_items.end();
}
+ std::set const & get_local_items() const { return local_items; }
+ std::set const & get_peer_items() const { return peer_items; }
// These are populated as the 'done' packets arrive.
bool done;
============================================================
--- roster.cc 76aa75696d056c98a890b0b0bb6c1164363a919e
+++ roster.cc d4c7f97919e49a5191439bf9bac604b734b7774f
@@ -2625,18 +2625,20 @@
#include "unit_tests.hh"
#include "sanity.hh"
#include "constants.hh"
+#include "randomizer.hh"
#include
#include
#include
using std::logic_error;
-using std::rand;
using std::search;
-using std::srand;
using boost::shared_ptr;
+using randomizer::uniform;
+using randomizer::flip;
+
static void
make_fake_marking_for(roster_t const & r, marking_map & mm)
{
@@ -2809,7 +2811,7 @@
typename M::const_iterator
random_element(M const & m)
{
- size_t i = rand() % m.size();
+ size_t i = randomizer::uniform(m.size());
typename M::const_iterator j = m.begin();
while (i > 0)
{
@@ -2820,11 +2822,6 @@
return j;
}
-bool flip(unsigned n = 2)
-{
- return (rand() % n) == 0;
-}
-
string new_word()
{
static string wordchars = "abcdefghijlkmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
@@ -2832,7 +2829,7 @@
string tmp;
do
{
- tmp += wordchars[rand() % wordchars.size()];
+ tmp += wordchars[uniform(wordchars.size())];
}
while (tmp.size() < 10 && !flip(10));
return tmp + lexical_cast(tick++);
@@ -2844,7 +2841,7 @@
string tmp;
tmp.reserve(constants::idlen);
for (unsigned i = 0; i < constants::idlen; ++i)
- tmp += tab[rand() % tab.size()];
+ tmp += tab[uniform(tab.size())];
return file_id(tmp);
}
@@ -2892,11 +2889,6 @@
change_automaton
{
- change_automaton()
- {
- srand(0x12345678);
- }
-
void perform_random_action(roster_t & r, node_id_source & nis)
{
cset c;
@@ -2916,7 +2908,7 @@
r.get_name(n->self, pth);
// L(FL("considering acting on '%s'") % file_path(pth));
- switch (rand() % 7)
+ switch (uniform(7))
{
default:
case 0:
@@ -4659,7 +4651,7 @@
roster_t & right_ros,
set & right_new_nodes)
{
- size_t n_nodes = 10 + (rand() % 30);
+ size_t n_nodes = 10 + (uniform(30));
editable_roster_base left_er(left_ros, nis);
editable_roster_base right_er(right_ros, nis);
============================================================
--- unit_tests.cc a69aa50b93e2be1ff1531f685a137d750bcffddd
+++ unit_tests.cc 0681ea82bcb92ab13dba3cff4e8de17e2363e58a
@@ -94,6 +94,7 @@
if (t.empty() || t.find("pipe") != t.end())
add_pipe_tests(suite);
+
if (t.empty() || t.find("string_queue") != t.end())
add_string_queue_tests(suite);
@@ -112,6 +113,9 @@
if (t.empty() || t.find("uri") != t.end())
add_uri_tests(suite);
+ if (t.empty() || t.find("refiner") != t.end())
+ add_refiner_tests(suite);
+
// all done, add our clean-shutdown-indicator
suite->add(BOOST_TEST_CASE(&clean_shutdown_dummy_test));
============================================================
--- unit_tests.hh a17ee7dc506a7bbfc4afc903e9d66ed108bfa1a0
+++ unit_tests.hh f725a5a24793b324839108e7dd18bebaf9cb9955
@@ -46,6 +46,7 @@
void add_roster_merge_tests(test_suite * suite);
void add_restrictions_tests(test_suite * suite);
void add_uri_tests(test_suite * suite);
+void add_refiner_tests(test_suite * suite);
// Local Variables:
// mode: C++