• Using RAII to clean up temporary values from a stack

    For the last couple of days, I have been playing around with the Lua C API and have been writing a thin wrapper library for C++. The main purpose of this auxiliary library is to ensure that global interpreter resources such as the global state or the execution stack are kept consistent in the presence of exceptions — and, in particular, that none of these are leaked due to programming mistakes when handling error codes.To illustrate this point, let's forget about Lua and consider a simpler case. Suppose we lost the ability to pass arguments and return values from functions in C++ and all we have is a stack that we pass around. With this in mind, we could implement a multiply function as follows:void multiply(std::stack& context) { const int arg1 = context.top(); context.pop(); const int arg2 = context.top(); context.pop(); context.push(arg1 * arg2);}And we could call our function as this:std::stack context;context.push(5);context.push(6);multiply(context);const int result = s.top();s.pop();In fact, my friends, this is more-or-less what your C/C++ compiler is internally doing when converting code to assembly language. The way the stack is organized to perform calls is known as the calling conventions of an ABI (language/platform combination).Anyway, back to our point. One important property of such a stack-based system is that any function that deals with the stack must leave it in a consistent state: if the function pushes temporary values (read: local variables) into the stack, such temporary values must be gone upon return no matter how the function terminates. Otherwise, the caller will not find the stack as it expects, which will surely cause trouble at a later stage. The above example works just fine because our function is extremely simple and does not put anything on the stack.But things get messier when our functions can fail halfway through, and, in particular, if such failures are signaled by exceptions. In these cases, the function will abort abruptly and the function must take care to clean up any values that may still be left on the stack. Let's consider another example:void magic(std::stack& context) { const int arg1 = context.top(); context.pop(); const int arg2 = context.top(); context.pop(); context.push(arg1 * arg2); context.push(arg1 / arg2); try { ... do something with the two values on top ... context.push(arg1 - arg2); try { ... do something with the three values on top ... } catch (...) { context.pop(); // arg1 - arg2 throw; } context.pop(); } catch (...) { context.pop(); // arg1 / arg2 context.pop(); // arg1 * arg2 throw; } context.pop(); context.pop();}The above is a completely fictitious and useless function, but serves to illustrate the point. magic() starts by pushing two values on the stack and then performs some computation that reads these two values. It later pushes an additional value and does some more computations on the three temporary values that are on the top of the stack.The "problem" is that the computation code can throw an exception. If it does, we must sanitize the stack to remove the two or three values we have already pushed. Otherwise, the caller will receive the exception, it will assume nothing has happened, and will leak values on the stack (bad thing). To prevent this, we have added a couple of try/catch clauses to capture these possible exceptions and to clean up the already-pushed values before exiting the function. Unfortunately, this gets old very quickly: having to add try/catch statements surrounding every call is boring, ugly, and hard to read (remember that, potentially, any statement can throw an exception). You can see this in the example above with the two nested try/catch blocks.To mitigate this situation, we can apply a RAII-like technique to make popping elements on errors completely transparent and automated. If we can make it transparent, writing the code is easier and reading it is trivial; if we can make it automated, we can be certain that our error paths (rarely tested!) correctly clean up any global state. In C++, destructors are deterministically executed whenever a variable goes out of scope, so we can use this to our advantage to clean up temporary values. Let's consider this class:class temp_stack { std::stack& _stack; int _pop_count;public: temp_stack(std::stack& stack_) : _stack(stack_), _pop_count(0) {} ~temp_stack(void) { while (_pop_count-- > 0) _stack.pop(); } void push(int i) { _stack.push(i); _pop_count++; }};With this, we can rewrite our function as:void magic(std::stack& context) { const int arg1 = context.top(); context.pop(); const int arg2 = context.top(); context.pop(); temp_stack temp(context); temp_stack.push(arg1 * arg2); temp_stack.push(arg1 / arg2); ... do something with the two values on top ... temp_stack.push(arg1 - arg2); ... do something with the three values on top ... // Yes, we can return now. No need to do manual pop()s!}Simple, huh? Our temp_stack function keeps track of how many elements have been pushed on the stack. Whenever the function terminates, be it due to reaching the end of the body or due to an exception thrown anywhere, the temp_stack destructor will remove all elements previously registered from the stack. This ensures that the function leaves the global state (the stack) as it was on entry — modulo the function parameters consumed as part of the calling conventions.So how does all this play together with Lua? Well, Lua maintains a stack to communicate parameters and return values between C and Lua. Such stack can be managed in a similar way with a RAII class, which makes it very easy to write native functions that deal with the stack and clean it up correctly in all cases. I would like to show you some non-fictitious code right now, but it's not ready yet ;-) But when it is, it will be part of Kyua. Stay tuned!And, to conclude: to make C++ code robust, wrap objects that need manual clean up (pointers, file descriptors, etc.) with small wrapper classes that perform such clean up on destruction. These classes are typically fully inlined and contain a single member field, so they do not impose any performance penalty. But, on the contrary, your code can avoid the need of many try/catch blocks, which are tricky to get right and hard to validate. (Unfortunately, this technique cannot be applied in, e.g. Java or Python, because the execution of the class destructors is completely non-deterministic and not guaranteed to happen whatsoever!) [Continue reading]

  • Dependency injection: simple class constructors

    Following my previous post on dependency injection (DI for short), I wanted to show you today another example of code in which DI helps in making the code clearer and easier to validate. In this case, the person to blame for the original piece of code being criticized is me.The atffile module in ATF provides a class to represent the contents of Atffiles. An Atffile is, basically, a file containing a list of test programs to run and a list of properties associated to these test programs. Let's consider the original implementation of this module:class atffile { strings_vector _test_programs; strings_vector _properties;public: atffile(const path& file) { std::ifstream input(file.c_str()); _test_programs = ... parse list from input ...; _properties = ... parse list from input ...; } ... getters and other read-only methods ...};According to the object-oriented programming (OOP) principles we are taught over and over again, this seems like a reasonable design. An atffile object is entirely self-contained: if the constructor finishes successfully, we know that the new object matches exactly the representation of an Atffile on disk. The other methods in the class provide read-only access to the internal attributes, which ensures that the in-memory representation remains consistent.However, this design couples the initialization of an object with external dependencies, and that is bad for two main reasons: first, because it makes testing (very) difficult; and, second, because it makes an apparently simple action (constructing an object) a potentially expensive task (reading from an external resource).To illustrate the first point, let's consider a helper free-function that deals with an atffile object:std::stringget_property(const atffile& file, const std::string& name, const std::string& defvalue){ const strings_vector& props = file.properties(); const strings_vector::const_iterator iter = props.find(name); if (iter == props.end()) return defvalue; else return *iter;}Now, how do we write unit-tests for this function? Note that, to execute this function, we need to pass in an atffile object. And to instantiate an atffile, we need to be able to read a Atffile from disk because the only constructor for the atffile class has this dependency on an external subsystem. So, summarizing, to test this innocent function, we need to create a file on disk with valid contents, we need to instantiate an atffile object pointing to this file, and only then we can pass it to the get_property function. At this point, our unit test smells like an integration test, and it actually is for no real reason. This will cause our test suite to be more fragile (the test for this auxiliary function depends on the parsing of a file) and slow.How can we improve the situation? Easy: decoupling the dependencies on external systems from the object initialization. Take a look at this rewritten atffile class:class atffile { strings_vector _test_programs; strings_vector _properties;public: atffile(const strings_vector& test_programs_, const strings_vector& properties_) : _test_programs(test_programs_), _properties(properties_) { assert(!_test_programs.empty()); } static atffile parse(const path& file) { std::ifstream input(file.c_str()); strings_vector test_programs_ = ... parse list from input ...; strings_vector properties_ = ... parse list from input ...; return atffile(test_programs_, properties_); } ... getters and other read-only methods ...};Note that this new design does not necessarily violate OOP principles: yes, we can now construct an object with fake values in it by passing them to the constructor, but that does not mean that such values can be inconsistent once the object is created. In this particular example, I have added an assertion in the constructor to reenforce a check performed by parse (that an atffile must list at least one test program).With this new design in mind, it is now trivial to test the get_property function shown above: constructing an auxiliary atffile object is easy, because we can inject values into the object to later pass it to get_property: no need to create a temporary file that has to be valid and later parsed by the atffile code. Our test now follows the true sense of a unit test, which is much faster, less fragile and "to-the-point". We can later write integration tests if we so desire. Additionally, we can also write tests for atffile member functions, and we can very easily reproduce corner cases for them by, for example, injecting bad data. The only place where we need to create temporary Atffiles is when we need to test the parse class method.So, to conclude: make your class constructors as simple as possible and, in particular, do not make your class constructors depend on external systems. If you find yourself opening resources or constructing other objects from within your constructor, you are doing it wrong (with very few exceptions).I have been using the above principle for the last ~2 years and the results are neat: I am much, much more confident on my code because I write lots of more accurate test cases and I can focalize dependencies on external resources on a small subset of functions. (Yes, Kyua uses this design pattern intensively!) [Continue reading]

  • Dependency injection and testing: an example

    A coworker just sent me some Python code for review and, among such code, there was the addition of a function similar to:def PathWithCurrentDate(prefix, now=None): """Extend a path with a year/month/day subdirectory layout. Args: prefix: string, The path to extend with the date subcomponents. now: datetime.date, The date to use for the path; if None, use the current date. Returns: string, The new computed path with the date appended. """ path = os.path.join(prefix, '%Y', '%m', '%d') if now: return now.strftime(path) else: return datetime.datetime.now().strftime(path)The purpose of this function, as the docstring says, is to simplify the construction of a path that lays out files on disk depending on a given date.This function works just fine... but it has a serious design problem (in my opinion) that you only see when you try to write unit tests for such function (guess what, the code to review did not include any unit tests for this). If I ask you to write tests for PathWithCurrentDate, how would you do that? You would need to consider these cases (at the very very least):Passing now=None correctly fetches the current date. To write such a test, we must stub out the call to datetime.datetime.now() so that our test is deterministic. This is easy to do with helper libraries but does not count as trivial to me.Could datetime.datetime.now() raise an exception? If so, test that the exception is correctly propagated to match the function contract.Passing an actual date to now works. We know this is a different code path that does not call datetime.datetime.now(), but still we must stub it out to ensure that the test is not going through that past in case the current date actually matches the date hardcoded in the test as an argument to now.My point is: why is such a trivial function so complex to validate? Why such a trivial function needs to depend on external state? Things become more obvious if we take a look at a caller of this function:def BackupTree(source, destination): path = PathWithCurrentDate(destination) CreateArchive(source, os.path.join(path, 'archive.tar.gz'))Now, question again: how do we test this? Our tests would look like:def testOk(self): # Why do we even have to do this? ... create stub for datetime.datetime.now() to return a fake date ... CreateArchive('/foo', '/backups/prefix') ... validate that the archive was generated in the fake date directory ...Having to stub out the call to datetime.datetime.now() before calling CreateArchive is a really, really weird thing at first glance. To be able to write this test, you must have deep insight of how the auxiliary functions called within the function work to know what dependencies on external state they have. Lots of black magic involved.All this said, the above may not seem like a big issue because, well, a call to datetime.datetime.now() is cheap. But imagine that the call being performed deep inside the dependency tree was more expensive and dealt with some external state that is hard to mock out.The trick to make this simpler and clearer is to apply a form of Dependency injection (or, rather, "value injection"). We want the PathWithCurrentDate function to be a simple data manipulation routine that has no dependencies on external state (i.e. make it purely functional). The easiest way to do so is to remove the now=None code path and pass the date in right from the most external caller (aka, the main() program). For example (skipping docstrings for brevity):def PathWithCurrentDate(prefix, now): path = os.path.join(prefix, '%Y', '%m', '%d') return now.strftime(path)def BackupTree(source, destination, backup_date): path = PathWithCurrentDate(destination, backup_date) CreateArchive(source, os.path.join(path, 'archive.tar.gz'))With this approach, the dependency on datetime.datetime.now() (aka, a dependency on global state) completely vanishes from the code. The code paths to validate are less, and they are much simpler to test. There is no need to stub out a function call seemingly unused by BackupTree.Another advantage of this approach can be seen if we were to have multiple functions accessing the same path. In this case, we would need to ensure that all calls receive the exact same date... what if the program kept running past 12AM and the "now" value changed? It is trivial to reason about this feature if the code does not have hidden queries to "now" (aka global state) within the code... but it becomes tricky to ensure our code is right if we can't easily audit where the "now" value is queried from!The "drawback", as some will think, is that the caller of any of these functions must do more work on its own to provide the correct arguments to the called functions. "And if I always want the backup to be created on the current directory, why can't the backup function decide on itself?", they may argue. But, to me, the former is definitely not a drawback and the latter... is troublesome as explained in this post.Another "drawback", as some others would say, is that testing is not a goal. Indeed it is not: testing is only a means to "correct" code, but it is also true that having testable code often improves (internal) APIs and overall design.To conclude: the above is an over-simplistic case study and my explanations will surely not convince anyone to stop doing black evil "clever" magic from within functions (and, worse, from within constructors). You will only realize that the above makes any sense when you start unit-testing your code. Start today! :-) [Continue reading]

  • Kyua: Design of the configuration system

    Over a week ago, I mostly finished the implementation of the runtime engine for test cases of Kyua and, along the way, realized that it is imperative to write a configuration system right now before the configuration code becomes messier than it already is.To that end, I spent the last week working on a design document for the configuration system. Summarizing, the document describes what the requirements for the configuration files of Kyua are, what the possible alternatives to implement them are, and advocates the use of Lua — a tiny embedded programming language — to bring these configuration files to life.It is your chance to get involved in the early stages of the development of Kyua! :-) Take a look at the email to kyua-discuss asking for comments and feel free to join the mailing list ;-) [Continue reading]

  • Sticky bit trivia

    Did you ever wonder where the "sticky" part of the "sticky bit" name comes from? I actually didn't, but I just came across the Sticky bit page on Wikipedia through a tweet from @AaronToponce and discovered why.If you have used any "recent" (the quotes are important) Unix-like system, you probably know what the sticky bit is used for: to restrict the deletion of files in a directory to, basically, the owner of such files. The sticky bit is used on /tmp (among other directories) so that anyone can create temporary files in it but only those that created the temporary files can delete them.But that's not all that is to know.The original purpose of the sticky bit was to mark frequently-used executable files so that the operating system kept their text segment on swap space. This speeded up subsequent executions of such programs because the system would not need to access the file system to load the binary: it could just use the image already kept in the swap space. This behavior became obsolete with the advent of memory-mapped executables.Now it's clear why the sticky bit has the name it has, isn't it? But still, that's not all that is to know.SunOS 4 introduced a new behavior for the sticky bit on regular, non-executable files: reads and writes to such files would bypass the buffer cache, thus basically telling the system to perform raw I/O on those files. This was particularly useful on swap files when NFS was involved.With the above, I have just tried to summarize you the information that is in NetBSD's chmod(2) and sticky(7) manual pages; they contain much more detailed information. (And yep, that's right: contrary to what the Wikipedia article says, NetBSD does not support this behavior any more.) Hope you found this insightful if you did not know this little piece of history! [Continue reading]

  • Getting the hang of Twitter searches

    I have had a Twitter account (@jmmv) for several years already but I have never leveraged its power. Why? Well... basically because I have never known how.The Twitterville book by Shel Israel (@shelisrael), which I have been reading lately, has opened my mind quite a bit. Twitter is not so much about posting status updates, but more about sharing content and starting/joining conversations with other people. Today I like to think of Twitter as a world-wide chat-room.Twitterville mentions many times that the key in Twitter usage is to search for content. But finding content among all the junk that floats in Twitter is hard. I had seen that it is possible to actually do searches in the Twitter web page, but that is not really usable. Yes, you can search once for something you are interested in... but you know what, you can do the same in any search engine and get more relevant results.To me, what has made a difference is to switch to a client that does actually support live searches (TweetDeck in my case). With such a client, all you have to do is create a search for any given topic you may be remotely interested in and status updates will just pop up in your client as soon as someone posts about that particular topic. Easy, huh? See, it's like joining your favorite #topic chat-room.With this in mind, you can, for example, create a search such as "#netbsd OR #freebsd OR #openbsd" to get real-time tweets about these BSD operating systems. It is a fact that you will see loads of junk (disable popup notifications recommended), but you will catch some interesting content. And the best of it, you can reply to that content. This is particularly useful because you can (try to) fix misconceptions that people have before they spread out too much.That said, the value you see in Twitter and how you use it, is fully up to you. Different people will find different use cases, all of them interesting on their own.And to conclude, I have to confess that while the above may seem obvious to many, it is something that has escaped my mind until last week. [Continue reading]

  • Introducing Kyua

    Wow. I have just realized that I have not blogged at all about the project that has kept me busy for the past two months! Not good, not good. "What is this project?", I hear. Well, this project is Kyua.A bit of background first: the Automated Testing Framework, or ATF for short, is a project that I started during the Summer of Code of 2007. The major goal of ATF was, and still is, to provide a testing framework for the NetBSD operating system. The ATF framework is composed of a set of libraries to aid in the implementation of test cases in C, C++ and shell, and a set of tools to ease the execution of such test cases (atf-run) and to generate reports of the execution (atf-report).At that point in time, I would say that the original design of ATF was nice. It made test programs intelligent enough to execute their test cases in a sandboxed environment. Such test programs could be executed on their own (without atf-run) and they exposed the same behavior as when they were run within the runtime monitor, atf-run. On paper this was nice, but in practice it has become a hassle. Additionally, some of these design decisions mean that particular features (in particular, parallel execution of tests) cannot be implemented at all. At the end of 2009 and beginning of 2010, I did some major refactorings to the code to make the test programs dumber and to move much of the common logic into atf-run, which helped a lot in fixing the major shortcomings encountered by the users... but the result is that, today, we have a huge mess.Additionally, while ATF is composed of different modules conceptually separate from each other, there is some hard implementation couplings among them that impose severe restrictions during development. Tangentially, during the past 2 years of working at Google (and coding mainly in Python), I have been learning new neat programming techniques to make code more testable... and these are not followed at all by ATF. In fact, while the test suite of ATF seems very extensive, it definitely is not: there are many corner cases that are not tested and for which implementing tests would be very hard (which means that nasty bugs have easily sneaked in into releases).Lastly, a very important point that affects directly the success of the project. Outsiders that want to contribute to ATF have a huge entry barrier: the source repository is managed by Monotone, the bug tracker is provided by Gnats (a truly user-unfriendly system), and the mailing lists are offered by majordomo. None of these tools is "standard" by today's common practices, and some of them are tied to NetBSD's hosting which puts some outsiders off.For all the reasons above and as this year has been moving along, I have gotten fed up with the ATF code base. (OK, things are not that bad... but in my mind they do ;-) And here is where Kyua comes into the game.Kyua is a project to address all the shortcomings listed above. First of all, the project uses off-the-shelf development tools that should make it much, much easier for external people to contribute. Secondly, the project intends to be much more modular, providing a clear separation between the different components and providing code that is easily testable. Lastly, Kyua intends to remain compatible with ATF so that there are no major disruptions for users. You can (and should) think of Kyua as ATF 2.0, not as a vastly different framework.As of today, Kyua implements a runtime engine that is on par, feature-wise, to the one provided by atf-run. It is able to run test cases implemented with the ATF libraries and it is able to test itself. It currently contains 355 test cases that run in less than 20 seconds. (Compare that to the 536 test cases of ATF, which take over a minute to run, and Kyua is still really far from catching up with all the functionality of ATF.) Next actions involve implementing reports generation and configuration files.Anyway. For more details on the project, I recommend you to read the original posting to atf-devel or the project's main page and wiki. And of course, you can also download the preliminary source code to take a look!Enjoy :-) [Continue reading]