# # # 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++