SummerOfCodeProposal Billynux

This page is related to Summer of Code 2010

See the list of Summer of Code 2010 Ideas

This is a Summer of Code 2010 student page

Project: SoC Ideas Network Stack Rewrite

Description

Billynux - Rewrite Wesnoth network stack using boost::asio

email : billybiset@gmail.com irc : billynux gna.org : billynux

The project consists of developing a network framework in the form of an API and subsequently an implementation that can be distributed as a library for the development of client/server applications. This library will be used to implement Wesnoth's network stack.

IRC

billynux

SoC Application

Rewriting Battle for Wesnoth network stack using boost::asio.

Changelog

Revision 0 : April 9 - Initial Wiki page for application deadline.

Revision 1 : April 13 - Added two sections:

• Additional Technical Information : Information about documentation procedures and tools of the different sub-projects.
• Technical Considerations Regarding boost::asio : Technical aspects relevant to implementing the network code using boost::asio.

Revision 2 : April 15 - Updated the timeline with milestones and added three sections:

• This Changelog.
• Current Network Dynamics : Explaining how data is sent using the current network module and how will this change with the new implementation.
• Compatibility Issues : Explaining why backwards compatibility won't be a problem.

Questionnaire

1.1) Write a small introduction to yourself.

My name is Guillermo Biset and I'm 25 years old. I live in Argentina and I work part time as a university teacher at UNRC. I've been coding since I was 11. Lately I finished my thesis (written in english) using C++, boost::asio and other libs (see http://fud.googlecode.com). I'm highly motivated and will be dedicating full time to the project (at least 6hrs a day).

1.2) State your preferred email address.

billybiset@gmail.com

1.3) If you have chosen a nick for IRC and Wesnoth forums, what is it?

IRC and Wesnoth forums: billynux

1.4) Why do you want to participate in summer of code?

I use exclusively free software and would love to contribute to such a project, I just finished my Licenciatura thesis and I'm currently seeking open source projects to get involved in (besides the thesis).

1.5) What are you studying, subject, level and school?

I'm taking a post-graduate course in Category Theory here in the National University of Rio Cuarto while teaching first year students basic programming and Pascal.

1.6) What country are you from, at what time are you most likely to be able to join IRC?

I'm from Argentina (GMT -3). I don't have particular time restrictions besides my 6 hours/week dedicated to teaching (mon. 18-20, wed. 16-20, local time).

1.7) Do you have other commitments for the summer period ? Do you plan to take any vacations ? If yes, when.

No, it will be winter here and I'm currently seeking a full-time or 6hrs/day project.

2) Experience

2.1) What programs/software have you worked on before?

• I wrote a C-- compiler using Lex/Yacc at school, I loved the project and managed to output both 64/32 bit assembly with many optimizations and developed an automatic bash testing scheme that would translate the C-- code to C and compile that version with gcc and then compare the results of both binaries.
• I was in charge of performing a translation of Visual Basic code used to analyze the frequency in a phone call to C++ code using sipXtapi with asterisk.
• I wrote a simple particle dynamics engine using Ruby as a thought experiment. It turned out to be an introductory physics tutor called Phygaro. Originally it supported round particles in a 2d environment colliding with other particles or static polygons, users could draw the environment in a Gtk/cairo application and the run a simulation and plot results in gnuplot. I then rewrote the whole thing dropping my engine and using ODE. The design was very naive and I want to rewrite the whole thing using C++, ODE and a better design. See user "billynux94" on YouTube for some example videos.
• I developed a framework for work distribution that enables a user to write distributed applications without knowledge of parallel programming (aimed at scientist not familiar with advanced programming) called FuD. I worked on it throughout 2009 and now at least 15 people are involved in continuing the project. It uses a simple boost::asio communication layer to have prototyping capabilities. The site contains plenty documentation including UML diagrams, a ~100 pages long english thesis, paper and presentations (LaTeX).
• Also as part of my thesis I developed a protein-backbone clustering application using FuD that uses an algorithm similar to k-means and an optimal rotation+alignment algorithm to compare the 3d structures using RMSD. Code can be seen in it's repository.
• I contribute to MiLi, a minimalistic header-only C++ library collection. I developed an object serialization library there that can be used as a stream.

2.2) Have you developed software in a team environment before? (As opposed to hacking on something on your own)

Yes, right now the work on FuD involves about 15 people and I'm actually running the project. Without svn it couldn't be possible. The project with sipXtapi and asterisk involved many people (> 20).

2.3) Have you participated to the Google Summer of Code before? As a mentor or a student? In what project? Were you successful? If not, why?

No.

2.4) Are you already involved with any open source development projects? If yes, please describe the project and the scope of your involvement.

Yes, I'm a collaborator at FuDePAN a Non-Profit organization researching in bioinformatics that only releases free software. There I developed FuD, a library for MiLi and the clusterer. I run the FuD and clusterer projects and contribute to MiLi under the advice of Daniel Gutson, FuDePAN's director.

2.5) Gaming experience - Are you a gamer?

Yes, I play Urban Terror (a FPS) actively and I represent Argentina in the national team, although we haven't participated in international tournaments. I played many strategy-based games such as C&C Red Alert as a kid.

2.5.1) What type of gamer are you?

Tough question, what types are there? I play occasionally and prefer tournament engagements to random playing.

2.5.2) What type of games?

Right now only FPS games. I'm taking my first steps in Wesnoth though.

2.5.3) What type of opponents do you prefer?

Human.

2.5.4) Are you more interested in story or gameplay?

Gameplay.

2.5.5) Have you played Wesnoth? If so, tell us roughly for how long and whether you lean towards single player or multiplayer.

I have just started playing Wesnoth and gone through the tutorial and basic campaigns. I really prefer multiplayer for any game.

2.6) If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for GSoC. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.

Nothing yet.

3) Communication skills

3.1) Though most of our developers are not native English speakers, English is the project's working language. Describe your fluency level in written English.

Excellent, I lived for almost a year in Montreal and New Orleans and have little accent or grammar problems. I wrote my thesis and a couple of papers in English and have no problem at all communicating in English either in writing, in person or over the phone.

3.2) What spoken languages are you fluent in?

Spanish, English. I'm mildly fluent in French but have only basic knowledge.

3.3) Are you good at interacting with other players? Our developer community is friendly, but the player community can be a bit rough.

I believe so, I participate in the Urban Terror Argentina forums. I have no trouble listening to valid but ill-spoken criticism. I judge opinions on their content and not how they are expressed but I always try to express myself seriously, professionally and openly honest.

3.4) Do you give constructive advice?

I would like to think so. I help first year university students take their first steps in programming and continuously remark the properties of quality code. Looking favorably at the results makes me think my advice was, to some extent, constructive.

3.5) Do you receive advice well?

Yes, again, I like to listen to the contents of the advice rather than how it is expressed. And I never believe that my stance can't be proven wrong.

3.6) Are you good at sorting useful criticisms from useless ones?

Yes, by trying to understand what is being critiqued. Technical aspects should allow me to discern its usefulness.

3.7) How autonomous are you when developing ? Would you rather discuss intensively changes and not start coding until you know what you want to do or would you rather code a proof of concept to "see how it turn out", taking the risk of having it thrown away if it doesn't match what the project want

There is a bit of a balance to it, neither extreme is good. You need to produce functioning code but you need a previous understanding of the current dynamics of a project. There must be a constant balance of the two activities, albeit depending on the current position, i.e. at first there is a lot of communication involved and as one learns its way around the code and the requirements, more independent work is carried out.

4) Project

4.1) Did you select a project from our list? If that is the case, what project did you select? What do you want to especially concentrate on?

Yes, the network stack rewrite using boost::asio. It is important to have a good initial design, after that: KISS. The rewritten code should look much more simpler than the original, this is due mostly to boost::asio's great functionality through a clean interface.

4.2) If you have invented your own project, please describe the project and the scope.

N/A.

4.3) Why did you choose this project?

I believe it to be an interesting project and one in which I have good knowledge of the necessary tools needed to implement it. I love gaming and I expect to someday have a career as a free software developer.

As with any free software endeavor, I learn a lot. As of now, new insights on free build systems (cmake) prove to be very valuable knowledge for me to apply on my other free software projects. This, I believe, is the main reason I chose this project.

4.4) Include an estimated timeline for your work on the project. Don't forget to mention special things like "I booked holidays between A and B" and "I got an exam at ABC and won't be doing much then".

There are 12 weeks to the project:

Week 1 - Designing the API, documenting. Most of this will be done before the start of the project.

Milestone 1 : By this point, there will be a fixed API to work upon, a document explaining its purpose, philosophy, main types and main methods and Doxygen generated documentation (e.g. LaTeX document, html page and so on) for it.

Weeks 2 and 3 - API implementation.

• Week 2 - Implementing the API using boost::asio.
• Week 3 - Documenting, writing very simple applications that use the API linked with this library. Start on client code.

Milestone 2 : After week 3, there should be a running implementation of the API with Doxygen documentation for it and a couple of example applications that use it.

Weeks 4 and 5 - Implementing the client side network code.

• Week 4 - Porting existing client code to use the library. Add Proxy support for basic and digest proxies.
• Week 5 - Testing code alongside the Wesnoth servers.

Week 6 - Documenting client changes.

Milestone 3 : By week 6, the client network module will be rewritten to use the new library, there will be basic and digest support for client connections. Optionally(but unlikely) there will be support for NTLM proxies.

Client code wrap-up.

Weeks 7 through 9 - Implementing the server side network code.

• Porting existing server code to use the library.

Week 10 - Testing implementation against both existing client implementations.

Milestone 4 : By end of week 10, there will be server implementations using the developed library with boost::asio. Code will be tested and documented with Doxygen.

Week 11 - Documenting changes. Finish testing/debugging.

By now, an API would have been defined alongside documentation explaining the semantics of each method. Also, there will be an implementation for it and some simple test applications.

Wesnoth will use this implementation throughout its network module.

Milestone 5 : Clients and servers implemented with boost::asio should be interchangeable, all should be good. There should be little or no issues and bugs regarding the new code.

Week 12 - GSoC end, final wrap-up.

4.5) Include as much technical detail about your implementation as you can

See answers to the questions below.

4.6) What do you expect to gain from this project?

Experience and knowledge.

4.7) What would make you stay in the Wesnoth community after the conclusion of SOC?

Many things would, mainly good feedback from the developers and gamers.

5) Practical considerations

5.1) Are you familiar with any of the following tools or languages?

   * Subversion (used for all commits)

Yes. I use it daily.

   * C++ (language used for all the normal source code)

Yes, absolutely.

   * STL, Boost, Sdl (C++ libraries used by Wesnoth)

Yes, I only have a basic concept of SDL however.

   * Python (optional, mainly used for tools)

I coded some python as a kid, but haven't done so in a while.

   * build environments (eg cmake/autotools/scons)

Yes, I have trained in them but haven't applied that to my projects yet. I'm learning cmake (and enjoying it).

   * WML (the wesnoth specific scenario language)

No.

   * Lua (used in combination with WML to create scenarios) 

No.

5.2) Which tools do you normally use for development? Why do you use them?

Any linux environment with a powerful editor (I use Kate) and a good drop-down console such as yakuake (I now use Guake).

Many tools from unix environments are priceless for many reasons (such as sed).

A good debugger is essential in spotting out errors in the code, I use gdb extensively for its versatility and valgrind for memory debugging.

5.3) What programming languages are you fluent in?

Fluent in C++, C, LaTeX, Pascal, Ruby, Eiffel and Haskell.

Some experience in Java, Alloy, ProMeLa.

5.5) Would you mind talking with your mentor on telephone / internet phone? We would like to have a backup way for communications for the case that somehow emails and IRC do fail. If you are willing to do so, please do list a phone number (including international code) so that we are able to contact you. You should probably *only* add this number in the application for you submit to google since the info in the wiki is available in public. We will *not* make any use of your number unless some case of "there is no way to contact you" does arise!

No, no problems here. Please contact me by email and we can set up a call procedure via skype or phone.

6) Answers

6.1) what proxies (authentication types) we can support, if we code a network stack using boost::asio, and how hard it'll be ?

I think Wesnoth should initially support basic and digest proxies (see RFC2617).

NTLM is a closed protocol and I propose to postpone an implementation until it is found a necessity. However, an implementation can be achieved.

Proxies can be used for tunneling purposes, to achieve this one must implement the CONNECT method described in RFC2616(p. 56). This can be done via the following steps:

1. Connect to Proxy Server first.
2. Issue CONNECT Host:Port HTTP/1.1<CR><LF>.
3. Issue <CR><LF>.
4. Wait for a line of response. If it contains HTTP/1.X 200, the connection is successful.
5. Read further lines of response until you receive an empty line.
6. Now, you are connected to the outside world through a proxy. Do any data exchange you want.

To accomplish this one would simply extend current asio socket functionality where the connect() method goes through the aforementioned steps.

6.2)what general architecture for the client you're going to use ?

There isn't much architecture needed for a client. A Client uses a socket class implemented with proxy capacity, it may hold as many sockets as it wishes, establishing many connections to the server.

6.3)what general architecture for the server you're going to use ?

Well, the server doesn't require a complex design either. Patters such as Proactor[0] and Leaders/Followers[0][1] are a good way to go when implementing Multi-threaded I/O Demultiplexing and Dispatching.

Particularly boost::asio is implemented using the Proactor Pattern (see boost's online doc).

However, a Server application using the designed library shouldn't really be complicated. It should just use the provided methods and register its own handlers to events. All event demultiplexing and threading is carried out in the API implementation and not the in the code that uses it. A server would just use client proxies (server side representatives of connected clients) using a Proxy Pattern (see Wikipedia's article).

All design decisions aim to achieve high cohesion while keeping coupling low and upholding the Open/Closed principle[2]. To accomplish these design goals, many Object Oriented principles are taken into account, notably ISP, SRP, LSP and DIP.

Anti-Patterns should also be taken under consideration to avoid common design mistakes such as the God-Object.

Timeout capability can also be configured in a manner described in boost's documentation as well.

[0] : D. Schmidt et al, Pattern Oriented Software Architecture, Volume 2. Wiley, 2000.

[1] : D. Schmidt et al, Leaders/Followers.

[2] : B. Meyer, Object Oriented Software Construction, Second Edition. Prentice-Hall, 2000.

6.4)how you'd allow the wesnoth client to multiplex connections to wesnoth server ?

There are many ways to accomplish this, none of them complicated. Which way to go is determined by the intended usage.

• If you just want to have clients holding many different connections to the server, then one could add a class extending from a basic client that would just spawn several connections on different sockets (parameterizing the amount).
• A different alternative is to directly spawn many clients from an application, but I don't see how this could be useful.

Again, how this is done depends on the use-cases.

I have a prototype running using boost::asio with clients supporting multiple connections to the server, you can check out the code here.

6.5)how you'd make it possible to use wesnoth network client with a different c++ backend?

I initially thought this meant using different network stacks for a single client, like having clients concurrently running with different backends all connected to one server.

I gather from conversations at #wesnoth-dev that what is sought after is reusability of the stack implementation for other applications. Basically I consider this to be among the design requirements of the API and I don't see many problems for it.

A KISS-designed API using Wesnoth as a study case will get the job done.

6.6)what problems and potential pitfalls do you see in the task?

Many things can spoil software development. Design is a crucial task. The code-base that needs to be refactored is large enough, so an initial stage involving familiarization with the code is also imperative (I'm already doing this and I'm not planning on stopping to wait for acceptance into GSoC), this involves a lot of input from the current developer community.

Also, a lot of testing must be carried out. However, testing code while playing doesn't sound so bad :)

Additional Technical Information

Documentation

There are three parts to document in the project: the API for building simple server/client applications, the boost::asio implementation of said API and the new code introduced in Wesnoth to use this implementation. They should be documented as follows:

API documentation

An API has to initially define the following:

• Syntax: The API's syntax. What are the methods published and what are their parameters and return types.
• Description: Detailed description of the API. What is the purpose of the API, how should one go about building an application for that purpose (i.e. using the API).
• Parameters (input, output): Details of all the input and output parameters along with description of values that can be passed and examples.
• Return Value(s): Details of the values returned by API after execution of those introduced methods. How should they be regarded and examples of returned values for particular scenarios.

This documentation will be in a technical document written in LaTeX. An example of LaTeX's many features can be seen in my thesis' .tex file.

Additionally, the API is to be developed in a C++ header file, which should be heavily documented using Doxygen and will be considered a single-file project (i.e. this header file will include Doxygen's main page documentation and so on.) Optionally, and disregarding compactness for the sake of organization, it could be implemented in many header files, although I expect that one should suffice.

This header file should then be distributed with any implementation of the API and upon installation be copied to the corresponding include directory.

The API template may also include all/any of the following:

• Synopsis: One line description of the API.
• Calling Sequence: The order in which an API must be called.
• Usage Scenario: Expected scenarios where the API can be used.
• Examples: Most of the programmers makes best use of this place and are expert in copying the examples provided illustrating the use of APIs.
• Related APIs: Information on the APIs that could be related to the API being documented.
• Classes/Objects/Methods lists: Names of classes/objects/methods associated with the API.
• Data types: Any special data type declared only for the specific API.
• Header Files: Any header files associated with the API.
• Exceptions/Error Messages: Any exceptions or errors that a user may encounter while using the API.
• Notes/Warnings: Special notes or warnings while using the API.
• Associations or dependencies: If the API is dependent on a separate API.

It goes without saying that any implementation of the API must implement all published methods/types which will later be compiled as a loadable library (either static or dynamic and for the target Operating System).

The API's implementation documentation

Documentation of this implementation will be that of a standard Doxygen project with many sources. I plan to use Wesnoth's coding standards both in the overall C++ implementation along with the style used throughout Doxygen.

The Wesnoth's network code documentation

According to the aforementioned standards in current Wesnoth code.

Technical considerations regarding boost::asio

Client Types

It is noted that there are three types of users of the network code:

1. Clients: Basic operation.
2. Game Server: Usually sending many smalls packets, mostly duplicated content.
3. Campaign Server: Sends very large packets (see next section).

It is important to remark the fact that the asynchronous methods for sending/receiving/connection in boost::asio are non-blocking (i.e. don't block execution of the next sentence for any considerable time, or it behaves as a O(1) operation.)

This will also be a requirement of the API methods, meaning that the implementer of the API will have to ensure these properties with regards to these methods.

What this means is that there is no reason to think that a large packet to be sent will be blocking a thread. The boost::asio implementation creates an object which attempts to send the data in the background and then calls the handler upon successful completion (or error, carrying an error code.) What is blocked is the thread that ran the run() method of the asio::io_service object.

There is good documentation available to explain this at boost's page. There is a possibility of having many threads calling the run() method, the io_service object will then call any of these.

The calls to the handlers can also be sequential using strands. There is even a tutorial about it.

Buffers

It is important that buffers used to send data are kept alive while data is being sent. The boost::asio buffer function will create references to some region in memory, but it is the caller's responsibility to ensure that the region will not be made invalid while the sending is taking place.

So, sending a single packet to many clients may involve reading many times from a single region in memory, the completion handler may then deallocate the memory if all clients have received the packet. The same holds for large packets, invalidating the buffer during sending will result in obscure behavior.

Data Considerations

There is no particular restrictions on the type of data that can be sent. The important part is separating application information from packet information. It will be up to the receiver of a message to understand what the message (buffer read) means.

This is done encapsulating messages in an OSI manner. A trivial implementation is prefixing the message size as a network layer message. Making sent data to look something like [size,message-of-said-size].

For example, sending a 1MB compressed WML document may form the following package:

   [(1MB + size-of-enumerated + size-of-doc), WML-COMPRESSED_enum, 1MB, 1MB-WML-DOC_compressed]

So, the network layer will see that it is a (1MB + size-of-enumerated + size-of-doc) message and read its contents calling the application handler, the application (Wesnoth) will see that it is a 1MB compressed WML document and use it accordingly.

For this purpose, I implemented a serialization library called BinaryStreams for the MiLi library collection (mentioned above). It provides stream support handling information of any type of object in a similar way that the standard input/output library does. There is also an example of its usage.

I have been asked if we should include this library into Wesnoth. It is neither necessary nor unlikely to do so. It has been properly tested and uses uint32_t from <stdint.h> (instead of size_t) to avoid multi-platform issues. However, it is not necessary to use it.

Any compression/decompression of data can be taken care both at the application level or the network level. Neither one will know if the other compressed its data, i.e. the application doesn't need to know if the sender will pack the data for sending and the sender won't know anything about the data it is to send. Both approaches should be considered.

Current Network Dynamics

In this section I give a brief explanation of the current dynamics of the network module while properly sending information to a connected component. Many details are omitted, but this overview should help understand its general current operation.

The steps are the following:

1. A call to send_to_one or send_to_many is made in player_network to send a simple_wml::document(a WML document.)
   • If a send_to_one, a socket is passed as a parameter.
   • If a send_to_many, a vector of network::connection elements is passed.
2. For each network::connection, or the single socket object, a call to send_raw_data is made in the network module.
3. If the connection parameter in send_raw_data is 0, it will call itself recursively with all the sockets in the network::connection vector sockets, declared in network.cpp:182.
4. If the connection parameter is not 0, it will call network_worker_pool::queue_raw_data with the corresponding connection socket and add the sent information for statistical purposes via add_bandwidth_out.
   • Note 1 : I recommend not using "if (! num )" for numerical variables replacing it by "if (num != 0) ".
   • Note 2 : There is a simple violation of the Single Responsibility Principle here, while manually adding 4 (as in bytes) to the bandwidth statistics module, meaning the header size. There really should be a constant determining the size of a header file in a single place.
5. In the network_worker module, queue_raw_data will create the corresponding buffer (adding the header via make_network_buffer which in turn uses SDLNet_Write32) and enqueue it via queue_buffer.
   • Note : I plan to use a similar approach than that taken of mili::binstreams to mimick SDLNet_Write32.
6. queue_buffer will find the corresponding shard to a particular socket, lock its mutex and queue the buffer, notifying a pool of condition variables if the socket is READY or ERRORED.
7. Eventually, the thread running the process_queue method in the network_worker module will make its way to a send_buffer operation, which uses SDLNet_TCP_Send to send the actual data.

How this will change

With a new boost::asio implementation of the network module this whole procedure will be much simpler. For instance:

• There is no need to implement buffer queues.
• There is no need to manually implement a thread method polling the buffers or using condition variables such as process_queue. The current implementation of boost's io_service does this automatically. The important part is deciding on which thread the run method will be called.
• Apparently the currents statistics module considers data as sent when the buffer is sent to the queue. This is not appropriate as the actual sending will take place later, we could count this information in the handler of the async_send method, thus improving the statistical analysis.

Many of these features can be seen functioning in my prototype.

Compatibility Issues

It is a requirement of the implementation that there is backwards compatibility between both implementations of the network module. Luckily, this isn't a big issue, SDLNet_Write32 just copies a uint32_t unsigned integer (defined in <stdint.h>) to a char buffer, this can be done with a C++ line as follows:

_s.append(reinterpret_cast<char*>(&x), sizeof(T));

To read the value:

_s.copy(reinterpret_cast<char*>(&x), sizeof(x),_pos);

The rest of the package is a WML document, which is actually sent compressed as a regular char buffer. Basically this means that the current code for arranging packets for sending and then reading them doesn't need to be modified.

Overall, I see no issues in having backwards compatibility.