May 2011 - Boost - lists.preview.boost.org

Delimiting protocol messages (was [asio] read_some() splits data)
by Marsh Ray 12 May '11

12 May '11

On 05/11/2011 09:36 AM, Andrew Holden wrote: > On Wednesday, May 11, 2011 9:57 AM, Slav wrote: >> Then messages of length not multiple of 128 (BUFFER_SIZE) >> will not be read - tested it, anyway, after >> last socket::read_some() (with readBytes> 0&& < >> BUFFER_SIZE) next socket::read_some() never ends. > > It would probably help to understand that TCP has no concept of a > "message". Anything you write to a socket is appended to a stream of > *bytes*. Alternatively, we could say that TCP, in fact, does have a well-defined concept of messages: they are all exactly one byte long. > Several subsystems on both the sending and receiving computers ... and sometimes boxes in the middle ... > will have the option of splitting and combining adjacent buffers with no > consideration to how big each individual write was. I've done a little protocol stuff with ASIO now and I must say it's a lot of fun and I can't go back to doing it any other way. > On further thought, I think I see the problem (and I apologize for the > bad recommendation in my last email). Your sender somehow needs to > communicate the message size or flag the end of the message. A partial > list of options includes: The pattern I encounter over and over again (often at multiple levels in a protocol) is: class protocol_layer_context { vector<uint8> buffer; void on_received_data(vector<uint8> & rx_bytes) { buffer.append(rx_bytes); // perhaps a virtual override. size_t msg_len = this->parse_len_from_start_of_buffer(); if (buffer.size() <= msg_len) { vector<uint8> msg_buf = consume_data_from_front_of_buffer(buffer, msg_len); // perhaps a virtual override this->process_complete_message(msg_buf); } // post another ASIO read request this->request_more_data(); } ... But there are some important issues with this naive pseudocode: 1. It can result in recopying the data a bunch of times for every protocol layer, killing performance. 2. It's susceptible to a denial-of-service (DoS). Bad guy can send trick you into allocating all your memory. 3. Sometimes the length of a message is stated at the beginning of the message, sometimes it isn't known until the end. 4. No processing happens on the message until it's completely read, but some protocols really need the receiving endpoint to process it incrementally. 5. Error handling 6. Optimal threading 7. Etc. We find bugs in exactly this logic all the darn time. Often the data being received is untrusted and possibly malicious. Real-world protocol implementations will commonly crash under fragmentation fuzzing, sometimes resulting in exploitable security holes. In a sense, this is the general refactoring problem of 'incrementalizing' a parsing function by moving all its state from stack variables into a longer-lived context object. We've seen it done successfully with coroutines, but that's not a commonly accepted solution because, frankly, the native C/C++ runtimes have not yet given coroutines the love (i.e., portability and performance guarantees) they really deserved. If someone figured out how to leverage generic techniques to handle just the unidirectional message delimiting problem in a bulletproof way I think it would make a really great boost library. - Marsh

1 0

Free BoostCon Registration
by Dave Abrahams 12 May '11

12 May '11

Unfortunately, two of our registrants had to cancel after the refund deadline. Fortunately, they have offered their registrations to anyone who might have not registered because of the cost. If you would like to claim these available registrations, please send email to our registrar, Marshall Clow (mclow AT gmail.com) Thanks, and see you in Aspen! -- Dave Abrahams BoostPro Computing http://www.boostpro.com

1 1

[spirit][qi] Dynamically combine Boost.Spirit.Qi rules at runtime
by Daniel F. 11 May '11

11 May '11

Hi, I recently tried to combine an arbitrary number of rules as alternatives in Boost.Spirit.Qi. Since rules are implemented as objects it seemed feasible to me. My motivation was to make certain parts of my grammar easily extensible. Unfortunately, I ran into some problems, so I wrote a simple program (see attachment for the complete code) demonstrating the unexpected behavior. Here's the key part: // "Dynamic" version - Does not compile! :( /* std::vector<rule_t> rules; rules.push_back(qi::char_('a')[qi::_r1 = px::val(0)]); rules.push_back(qi::char_('b')[qi::_r1 = px::val(1)]); rules.push_back(qi::char_('c')[qi::_r1 = px::val(2)]); std::vector<rule_t>::iterator i(rules.begin()), last(rules.end()); rule_t grammar; grammar = (*i)(qi::_r1); //[no_op] for(++i; i!=last; ++i) { grammar = grammar.copy() | (*i)(qi::_r1); //[no_op] } */ // "Dynamic" version - Kind of works! :-/ std::vector<rule_t> rules; rules.push_back(qi::char_('a')[qi::_r1 = px::val(0)]); rules.push_back(qi::char_('b')[qi::_r1 = px::val(1)]); rules.push_back(qi::char_('c')[qi::_r1 = px::val(2)]); std::vector<rule_t>::iterator i(rules.begin()), last(rules.end()); qi::rule<iterator_t, int()> temp; temp = (*i)(qi::_val); //[no_op] for(++i; i!=last; ++i) { temp = temp.copy() | (*i)(qi::_val); //[no_op] } rule_t grammar; grammar = temp[qi::_r1 = qi::_1]; Now, I suppose that the first version (commented out) doesn't compile, because I'm not passing the inherited attribute down to grammar.copy(). I would love to know if there's a better way of doing this than the workaround that is the second version. The second version actually compiles and it seems to do the right thing. However, once I attach a simple semantic action as indicated in the code using comments (see "[no_op]"), the behavior becomes really weird. Rather than printing 0,1,2 as before, the program prints 0,0,2. So I'm wondering, is what I'm trying to accomplish resulting in undefined behavior? Is this a bug? Or, quite possibly, am I just using something (e.g. semantic actions?) the wrong way? Thanks for reading, Daniel

4 7

[convert] no-throw and fallback feature
by Vicente BOTET 11 May '11

11 May '11

Hi, I was thinking on the fallback feature a little bit more and I've the impression that we can get it for free. If we accept that we need a no-throw function such as try_convert_to that returns an optional Target we can have the fallback using the optional::get_value_or function auto r = try_convert_to(*int*)(s); int i = r.get_value_or(fallback); or just int i = try_convert_to(*int*)(s).get_value_or(fallback); or int i = get_value_or(try_convert_to(*int*)(s), fallback); I don't know if it is worth adding a function that does all in one int i = convert_to_or(*int*)(s, fallback); Best, Vicente

5 25

[autoindex] Review
by Edward Diener 11 May '11

11 May '11

This is my review of autoindex. - What is your evaluation of the design? Very clean and easy to understand. - What is your evaluation of the implementation? Did not look at the internals. - What is your evaluation of the documentation? Generally good. Here is a list of mostly grammatical errors: 1) Overview: "the HTML indexes look a lot less good" -> "the HTML indexes look a lot worse" Step 1: Build the AutoIndex tool: "Finally note that tools/auto_index/auto-index.jam gets copied into the same directory as the rest of the Boost.Build tools." -> I am not sure if this means that building AutoIndex does this automatically or the end-user must do it but the sentence grammar suggests the former, which does not happen for me. If the end-user should do it, the line should read "Finally note that tools/auto_index/auto-index.jam should be copied into the same directory as the rest of the Boost.Build tools." 2) Step 2: Configure Boost.Build jamfile to use AutoIndex "Always send the output to a log file. It will contain of lot of stuff, but is invaluable to check if all has gone right, and else diagnose what has gone wrong. -> ..."and also diagnose what has gone wrong." ..."or else diagnose what has gone wrong." 3) Available Indexing Options: For Document Type 'library', Available Index Types says 'See Chapter'. I am guessing this means it is the same as Document Type 'chapter' but it should be made clearer in the remark. 4) Step 7: Iterate - to refine your index: "You can restrict which sections are indexed for a particular term. So assuming that the docbook document has the usual hierarchical names for section ID's hierarchical names for section IDs(as Quickbook generates, for example), you can easily place a constraint on which sections are examined for a particular term. " ' -> remove the second repeated "hierarchical names for section IDs". "This would avoid an index entry every time ° kelvin is found, something the user is unlikely to find helpful. " -> "This would avoid an index entry every time 'Kelvin' is found, something the user is unlikely to find helpful. " 5) Script File (.idx) Reference: "Blank lines consisting of only whitespace are ignored, so are lines that start with a #. (But, of course, you can't append # comments onto the end of a line!). " -> I am guessing this should be: "...(But, of course, you can append # comments onto the end of a line!)." "recurse An optional boolean value - either "true" or "false" - that indicates whether to recurse into subdirectories. This defaults to "false" -> Needs a period at the end. "type The type to which items found using this rule will assigned, index terms created from the source file and then found in the XML, will have the type attribute set to this value, and may then appear in a specialized index with the same type attribute " -> Needs a period at the end. The only other issue in the documentation is that while there is very good documentation about what type of XML container wraps an internally generated index, I am not sure what this actually means to a Quickbook author. No doubt somewhere there is probably a discussion in Docbook of what these XML containers mean and do but, aside from experimentation, the user of AutoIndex is not likely to understand what it means to put the Index in a specific XML container and how this affects the final layout of the documentation. Perhaps some further explanation of what this actually means for an AutoIndex user, especially for a Quickbook document, would be appropriate. - What is your evaluation of the potential usefulness of AutoIndex? Immense. Searching through documentation of even mildly complex libraries which have little or no index is very frustrating. - Did you try to use it? With what compiler? Did you have any problems? I have used it for the documentation of my VMD and TTI libraries with both gcc and vc++ under Windows. Any problems were of my own making and the author of AutoIndex answered my questions when I was stuck. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? A pretty deep study, although I have not tried to add anything to the index file other than 'scan' statements. - Are you knowledgeable about the problem domain? Yes. I vote for the library to be accepted into Boost. Edward Diener

2 1

inquiry about proposing a new Boost library for a tree template container class
by Erik Erlandson 11 May '11

11 May '11

Hello, I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration. The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki Regards, Erik Erlandson

7 27

[type_factory] new utility/class proposal
by Vlad Lazarenko 11 May '11

11 May '11

Dear Boost developers, How many times in your experience you needed to associate a type with some identifier known at run-time only? It’s like having an associative container with numeric key and type as a value. Not object, but type. This is a concept similar to object factory pattern but with no objects, only their types. I call it a type factory. There might be a solution for this in Boost already but I haven’t seen it. Please forgive me if I am just being blind. Just to give you a little taste of what I mean – imagine that you have a stream of bytes where objects of different types and sizes are stored (serialized), and one byte identifying a type is preceding every such serialized object, and you need to parse it. One approach is to have a switch statement, for example, where all type identifiers are cased, and parse data depending on a type. But then, as list of types grows and/or shrinks, maintenance of this switch becomes unpleasant. And if this logic is in some base library, where user specifies list of types, it becomes even worse. There might be another way, I thought, and came up with sort of hybrid between compile-time types and run-time identifiers – a type factory. I am wondering if anyone else will find it useful. Perhaps we can have it as part of boost utility classes. Here is a very simple example of usage: https://github.com/Yocto/type_factory/blob/master/test/simple_example.cpp It gets a number from “argc”, and then, depending on its value, invokes “speak” method of either “cow”, “dog” or “alligator” classes. More functionality is covered in unit test. Basically, the type factory, given a list of types as “MPL vector“ is enumerating them from 0 to N. Later, for any given instantiation of “create” method, it generates a dispatch table for invoking of one of template methods (with no arguments) on a supplied “visitor” class. The source code of the class is here - https://github.com/Yocto/type_factory/blob/master/include/yocto/type_factor…. There are a lot of details, but the main class exposed to the user-land API is “type_factory”. Please let me know if you are interested in such a concept. Thank you, Vlad

2 1

Review manager needed for TTI library
by Edward Diener 10 May '11

10 May '11

I am looking for a review manager for my TTI library in the review queue. The TTI library, which is an abbreviation for the 'Type Traits Introspection' library, allows a programmer to introspect at compile time the inner elements of a C++ type. The introspection process depends on specifying the name of the inner element by different macros for different types of elements, and then using a generated metafunction to determine whether that element exists within the enclosing type. The inner elements which can be introspected are type, class template, member data, member function, static member data, and static member function. The TTI library is based on the type_traits_ext portion of the Concept Traits Library, with improvements and additions, and also reproduces functionality ( without changing existing code ), for the purposes of completeness, from Boost.MPL regarding introspection of types and templates. The purpose of the library is to provide a consistent set of interfaces for doing compile-time introspection of a type, which other template metaprogrammers can use in their code. Since I have acted as a review manager for another library, and have expressed my willingness to do so for some other libraries, I would appreciate it if someone, who understands Boost MPL well and the compile-time introspection problems my library solves, would be a review manager for my own library.

3 6

Re: [boost] [trolling] Alexander's crusade (was: [provocative] Whom did the SFC pay to list boostdevelopers as a whole in "Current Member Projects"?)
by Matt Chambers 10 May '11

10 May '11

> ... pointless quoted legal jargon... What's your point? -Matt

10 17

[container_bptree] first version of submitted library
by Vadim Stadnik 09 May '11

09 May '11

Hi all, The first version of submitted library container_bptree http://www.boostpro.com/vault/index.php?action=downloadfile&filename=contai… offers a number of STL variants of containers based on B+ trees. These powerful data structures enable the implementation of various useful extensions of STL containers and iterators. One of the most interesting improvements is the efficient algorithm accumulate(), which has computational cost *O(log N)* in the worst case. This algorithm can increase performance of solutions in numerous application areas, including traveling salesman problem. Please read the documentation and try the included test code. The current implementation has been developed for Visual Studio compilers (2008 and 2010). Portability of this library has not yet been tested. I would really appreciate if someone could compile and run the test code using other compilers and let me know if there are any technical issues. Any suggestions concerning improvements of the current version of this library will be carefully analyzed and implemented if possible. The potential of B+ trees has not yet been used to its full capacity. There are a number of options for further extensions of this library. The community interest and feedback will have an effect on the priority of the development of new features and efficient algorithms in future versions of this library. Thank you, Vadim Stadnik

2 2