This is an automated email from the ASF dual-hosted git repository. bneradt pushed a commit to branch dev-1-0-13 in repository https://gitbox.apache.org/repos/asf/trafficserver-libswoc.git
commit a132724cbadd0f3fea1936f5e9a1c672d99de57a Author: Alan M. Carroll <[email protected]> AuthorDate: Wed Feb 26 06:48:51 2020 -0600 Fix blend bug, update blend documentation. --- doc/code/IPSpace.en.rst | 184 ++++++++++++++++++++++++++++++++++-- swoc++/include/swoc/DiscreteRange.h | 2 +- swoc++/include/swoc/swoc_ip.h | 3 +- unit_tests/ex_ipspace_properties.cc | 95 ++++++++++++++----- 4 files changed, 250 insertions(+), 34 deletions(-) diff --git a/doc/code/IPSpace.en.rst b/doc/code/IPSpace.en.rst index ecfe09e..3f78f2f 100644 --- a/doc/code/IPSpace.en.rst +++ b/doc/code/IPSpace.en.rst @@ -17,8 +17,6 @@ Synopsis Usage ***** -:libswoc:`Reference documentation <swoc::IPEndpoint>`. - This library is for storing and manipulating IP addresses as data. It has no support for actual network operations. @@ -168,17 +166,185 @@ Examples Blending Bitsets ================ -As an example of blending, consider a mapping of IP addresses to a bit set, each representing some -independent property of the address (e.g., production, externally accessible, secure, etc.). It -might be the case that each of these was in a separate data source. In that case one approach -would be to blend each data source into the IPSpace, combining the bits in the blending functor. -The declarations could be +.. sidebar:: Code + + Some details are omitted for brevity and because they aren't directly relevant. The full + implementation, which is run as a unit test to verify its correctness, + `is available here <https://github.com/SolidWallOfCode/libswoc/blob/1.0.13/unit_tests/ex_ipspace_properties.cc>`__. + You can compile and step through the code to see how it works in more detail, or experiment + with changing some of the example data. + +As an example of blending, consider a mapping of IP addresses to a bit set, each bit representing +some independent property of the address (e.g., production, externally accessible, secure, etc.). It +might be the case that each of these was in a separate data source. In that case one approach would +be to blend each data source into the IPSpace, combining the bits in the blending functor. If +`std::bitset <http://www.cplusplus.com/reference/bitset/bitset/>`__ is used to hold the bits, the +declarations could be done as .. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc :start-after: "IPSpace bitset blending" :lines: 1-4 :emphasize-lines: 2,4 +To do the blending, a blending functor is needed. + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // Bitset blend functor + :lines: 1-4 + +This always returns :code:`true` because blending any bits never yields a zero result. A lambda is +provided to do the marking of the example data for convience. This takes a list of example data +items defined as a range and a list of bits to set. + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // Example data type. + :lines: 1 + +The marking logic is + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // Example marking functor. + :lines: 1-7 + +Let's try it out. For the first pass this data will be used. + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // test ranges 1 + :lines: 2-8 + +After using this, the space contents are :: + + 7 ranges + 100.0.0.0-100.0.0.255 : 10000000000000000000000000000000 + 100.0.1.0-100.0.1.255 : 01000000000000000000000000000000 + 100.0.2.0-100.0.2.255 : 00100000000000000000000000000000 + 100.0.3.0-100.0.3.255 : 00010000000000000000000000000000 + 100.0.4.0-100.0.4.255 : 00001000000000000000000000000000 + 100.0.5.0-100.0.5.255 : 00000100000000000000000000000000 + 100.0.6.0-100.0.6.255 : 00000010000000000000000000000000 + +Those are non-overlapping intervals and therefore are not really blended. Suppose the following +ranges are also blended - note these overlap the first two ranges from the previous ranges. + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // test ranges 2 + :lines: 2-4 + +This yields :: + + 9 ranges + 100.0.0.0-100.0.0.255 : 10000000000000000000000000000001 + 100.0.1.0-100.0.1.255 : 01000000000000000000000000000010 + 100.0.2.0-100.0.2.127 : 00100000000000000000000000000000 + 100.0.2.128-100.0.2.255 : 00100000000000000000000000000100 + 100.0.3.0-100.0.3.127 : 00010000000000000000000000000100 + 100.0.3.128-100.0.3.255 : 00010000000000000000000000000000 + 100.0.4.0-100.0.4.255 : 00001000000000000000000000000000 + 100.0.5.0-100.0.5.255 : 00000100000000000000000000000000 + 100.0.6.0-100.0.6.255 : 00000010000000000000000000000000 + +The additional bits are now present on the other side of the bit set. Note there are now more ranges +because the last range overlapped two of the previously existing ranges. Those are split because of +the now differing payloads for the new ranges. + +What happens if this range and data is blended into the space? + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // test ranges 3 + :lines: 2 + +The result is :: + + 6 ranges + 100.0.0.0-100.0.0.255 : 10000000000000000000000000000001 + 100.0.1.0-100.0.1.255 : 01000000000000000000000000000010 + 100.0.2.0-100.0.3.255 : 00110000000000000000000000000100 + 100.0.4.0-100.0.4.255 : 00111000000000000000000000000100 + 100.0.5.0-100.0.5.255 : 00000100000000000000000000000000 + 100.0.6.0-100.0.6.255 : 00000010000000000000000000000000 + +Note the ".2" and ".3" ranges have collapsed in to a single range with the bits 2,3,29 set. The +".4" range remains separate because it also has bit 4 set, which is distinct. + +Blending allows selective erasing. Let's erase bits 2,3,29 in all ranges. First a blending functor +is needed to erase bits instead of settting them. + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // reset blend functor + :lines: 1-5 + +Note this returns :code:`false` if the result of clearing the bits is an empty bitset. Just to be +thorough, let's clear those bits for all IPv4 addresses. + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // erase bits + :lines: 1 + +The result is :: + + 5 ranges + 100.0.0.0-100.0.0.255 : 10000000000000000000000000000001 + 100.0.1.0-100.0.1.255 : 01000000000000000000000000000010 + 100.0.4.0-100.0.4.255 : 00001000000000000000000000000000 + 100.0.5.0-100.0.5.255 : 00000100000000000000000000000000 + 100.0.6.0-100.0.6.255 : 00000010000000000000000000000000 + +The ".2" and ".3" ranges have disappeared, as this bit clearing cleared all the bits in those +ranges. The ".4" range remains back to its original state, the extra bits having been cleared. The +other ranges are unchanged because this operation did not change their payloads. No new ranges have +been added because the result of unsetting bits where no bits are set is also the empty bit set. +This means the blender returns :code:`false` and this prevents the range from being created. + +As a final note, although the data used here was network based, that is in no way required. +This line of code being executed + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // ragged boundaries + :lines: 1 + +yields the result :: + + 7 ranges + 100.0.0.0-100.0.0.255 : 10000000000000000000000000000001 + 100.0.1.0-100.0.1.255 : 01000000000000000000000000000010 + 100.0.2.19-100.0.3.255 : 00000000000000001010100000000000 + 100.0.4.0-100.0.4.255 : 00001000000000001010100000000000 + 100.0.5.0-100.0.5.117 : 00000100000000001010100000000000 + 100.0.5.118-100.0.5.255 : 00000100000000000000000000000000 + 100.0.6.0-100.0.6.255 : 00000010000000000000000000000000 + +Although the examples up to now have used :code:`PAYLOAD` as the argument type to the +:code:`blend` method, this is not required in general. The type of the second argument +to :code:`blend` is determined by the second argumen to the functor, so that data other +than strictly :code:`PAYLOAD` can be blended into the space. For instance the blending +functor might directly take a list of bit indices - + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // bit list blend functor + :lines: 1-5 + +In this case the call to :code:`blend` must also take a list of bit indices, not a :code:`PAYLOAD` +(e.g. a :code:`std::bitset<32>`). + +.. literalinclude:: ../../unit_tests/ex_ipspace_properties.cc + :start-after: // bit list blend functor + :lines: 7-8 + +That call to :code:`blend` will blend bits 10 and 11 into all IPv4 addresses except the first and +last, yielding :: + + 10 ranges + 0.0.0.1-99.255.255.255 : 00000000001100000000000000000000 + 100.0.0.0-100.0.0.255 : 10000000001100000000000000000001 + 100.0.1.0-100.0.1.255 : 01000000001100000000000000000010 + 100.0.2.0-100.0.2.18 : 00000000001100000000000000000000 + 100.0.2.19-100.0.3.255 : 00000000001100001010100000000000 + 100.0.4.0-100.0.4.255 : 00001000001100001010100000000000 + 100.0.5.0-100.0.5.117 : 00000100001100001010100000000000 + 100.0.5.118-100.0.5.255 : 00000100001100000000000000000000 + 100.0.6.0-100.0.6.255 : 00000010001100000000000000000000 + 100.0.7.0-255.255.255.254 : 00000000001100000000000000000000 + History ******* @@ -187,3 +353,7 @@ on IP addresses classes developed by Network Geographics for the Infosecter prod Apach Traffic Server was a much simplified version of the original work and this is a reversion to that richer and more complete set of classes and draws much of its structure from the Network Geographics work directly. + +I want to thank `Uthira Mohan <https://www.linkedin.com/in/uthiramohan>`__ for being my intial +tester and feature requestor - in particular the design of blending is a result of her feature +demands. diff --git a/swoc++/include/swoc/DiscreteRange.h b/swoc++/include/swoc/DiscreteRange.h index f961449..2886a4b 100644 --- a/swoc++/include/swoc/DiscreteRange.h +++ b/swoc++/include/swoc/DiscreteRange.h @@ -1306,7 +1306,7 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const&range, U c if (pred && pred->payload() == plain_color) { pred->assign_max(n_min_minus_1); } else { - this->insert_before(n, _fa.make(range.min(), n_min_minus_1, plain_color)); + this->insert_before(n, _fa.make(remaining.min(), n_min_minus_1, plain_color)); } } } diff --git a/swoc++/include/swoc/swoc_ip.h b/swoc++/include/swoc/swoc_ip.h index 9070ebd..0ee3f9b 100644 --- a/swoc++/include/swoc/swoc_ip.h +++ b/swoc++/include/swoc/swoc_ip.h @@ -773,7 +773,8 @@ public: * * Every address in @a range is assigned a payload. If the address does not already have a color, * it is assigned the default constructed @c PAYLOAD blended with @a color. If the address has a - * color of A it is updated by invoking @a blender on the existing payload and @a color. + * @c PAYLOAD @a p, @a p is updated by invoking <tt>blender(p, color)</tt>, with the expectation + * that @a p will be updated in place. */ template < typename F , typename U = PAYLOAD > self_type & blend(IPRange const& range, U const& color, F && blender); diff --git a/unit_tests/ex_ipspace_properties.cc b/unit_tests/ex_ipspace_properties.cc index 8ee8e9c..e0f0e8e 100644 --- a/unit_tests/ex_ipspace_properties.cc +++ b/unit_tests/ex_ipspace_properties.cc @@ -50,58 +50,103 @@ TEST_CASE("IPSpace bitset blending", "[libswoc][ipspace][bitset][blending]") { using PAYLOAD = std::bitset<32>; // Declare the IPSpace. using Space = swoc::IPSpace<PAYLOAD>; + // Example data type. + using Data = std::tuple<TextView, std::initializer_list<unsigned>>; // Dump the ranges to stdout. auto dump = [](Space&space) -> void { if (Verbose_p) { std::cout << W().print("{} ranges\n", space.count()); for (auto &&[r, payload] : space) { - std::cout << W().print("{:12}-{:12} : {}\n", r.min(), r.max(), payload); + std::cout << W().print("{:25} : {}\n", r, payload); } } }; - // Blend functor which computes a union of the bitsets. + // Convert a list of bit indices into a bitset. + auto make_bits = [](std::initializer_list<unsigned> idx) -> PAYLOAD { + PAYLOAD bits; + for (auto bit : idx) { + bits[bit] = true; + } + return bits; + }; + + // Bitset blend functor which computes a union of the bitsets. auto blender = [](PAYLOAD& lhs, PAYLOAD const& rhs) -> bool { lhs |= rhs; - return lhs != 0; + return true; }; - // test ranges. - std::array<std::tuple<TextView, std::initializer_list<unsigned>>, 9> ranges = { - { - { "100.0.0.0-100.0.0.255", { 0 } } - , { "100.0.1.0-100.0.1.255", { 1 } } - , { "100.0.2.0-100.0.2.255", { 2 } } - , { "100.0.3.0-100.0.3.255", { 3 } } - , { "100.0.4.0-100.0.4.255", { 4 } } - , { "100.0.5.0-100.0.5.255", { 5 } } - , { "100.0.6.0-100.0.6.255", { 6 } } - , { "100.0.0.0-100.0.0.255", { 31 } } - , { "100.0.1.0-100.0.1.255", { 30 } } - }}; + // Example marking functor. + auto marker = [&](Space & space, swoc::MemSpan<Data> ranges) -> void { + // For each test range, compute the bitset from the list of bit indices. + for (auto &&[text, bit_list] : ranges) { + space.blend(IPRange{text}, make_bits(bit_list), blender); + } + }; // The IPSpace instance. Space space; - // For each test range, compute the bitset from the list of bit indices. - for (auto &&[text, bit_list] : ranges) { - PAYLOAD bits; // zero bitset. - for (auto bit : bit_list) { - bits[bit] = true; - } - space.blend(IPRange{text}, bits, blender); - } + // test ranges 1 + std::array<Data, 7> ranges_1 = {{ + { "100.0.0.0-100.0.0.255", { 0 } } + , { "100.0.1.0-100.0.1.255", { 1 } } + , { "100.0.2.0-100.0.2.255", { 2 } } + , { "100.0.3.0-100.0.3.255", { 3 } } + , { "100.0.4.0-100.0.4.255", { 4 } } + , { "100.0.5.0-100.0.5.255", { 5 } } + , { "100.0.6.0-100.0.6.255", { 6 } } + }}; + + marker(space, MemSpan<Data>{ranges_1.data(), ranges_1.size()}); + dump(space); + + // test ranges 2 + std::array<Data, 3> ranges_2 = {{ + { "100.0.0.0-100.0.0.255", { 31 } } + , { "100.0.1.0-100.0.1.255", { 30 } } + , { "100.0.2.128-100.0.3.127", { 29 }} + }}; + marker(space, MemSpan<Data>{ranges_2.data(), ranges_2.size()}); dump(space); + // test ranges 3 + std::array<Data, 1> ranges_3 = {{ + { "100.0.2.0-100.0.4.255", { 2, 3, 29 }} + }}; + + marker(space, MemSpan<Data>{ranges_3.data(), ranges_3.size()}); + dump(space); + + // reset blend functor auto resetter = [](PAYLOAD& lhs, PAYLOAD const& rhs) -> bool { auto mask = rhs; lhs &= mask.flip(); return lhs != 0; }; - space.blend(IPRange{"100.0.2.128-100.0.3.127"}, PAYLOAD{"1111"}, resetter); + + // erase bits + space.blend(IPRange{"0.0.0.0-255.255.255.255"}, make_bits({2,3,29}), resetter); + dump(space); + + // ragged boundaries + space.blend(IPRange{"100.0.2.19-100.0.5.117"}, make_bits({16,18,20}), blender); dump(space); + + // bit list blend functor which computes a union of the bitsets. + auto bit_blender = [](PAYLOAD& lhs, std::initializer_list<unsigned> const& rhs) -> bool { + for ( auto idx : rhs ) + lhs[idx] = true; + return true; + }; + + std::initializer_list<unsigned> bit_list = { 10,11 }; + space.blend(IPRange{"0.0.0.1-255.255.255.254"}, bit_list, bit_blender); + dump(space); + } // ---
