Saturday, February 24, 2007

Zarro Boogs Found

At the start of this week I tried to integrate several patches submitted to Jira. Unfortunately, there were two impediments to this.

The first problem was simply because XML output has now been configured to provide datatypes and language types to any literal that defines them. This makes a lot of sense to me, and I was happy to integrate it. Unfortunately all the scripted tests are looking for exact textual matches on the output, so many of them are suddenly failing. This is trivial but time consuming to fix. As I write this, I'm running tests over my latest attempt to squash all these bugs. I hope I finally got them all.

The other problem seemed to be easier, but was far more insidious.

I was getting an iTQL error that I didn't understand. The stack trace in the log did not take me far enough, so I added in some more logging. The next time through the tests, the section I was analyzing passed, but something else failed.

This went on for a whole night. Every time I thought I was getting closer, the failing code would move. This generally indicates threaded code with a race, but I couldn't imagine where. I finally tracked one instance of the bug down to a transaction exception, which was the point where I decided I needed to talk to Andrae.

String Pool

In the meantime, Andrae had decided to take on the hard task of the fixing a problem that had been reported with the string pool. I had so much on my plate that I wanted to avoid it, though I knew it was a significant issue, and would compromise confidence in the project.

Since I needed Andrae's help I offered some description on the structure of the string pool. However, I quickly realized how lazy I was being, so I decided to look for myself.

Andrae had managed to narrow down the problem to a very specific behavior. This made it much easier for me to think through exactly what was happening, and how the system had to get there.

The problem was due to an entry in the AVLTree, with no corresponding entry in the IntFile. To understand this, I need to explain some of the basics of the string pool.

String Pool

The string pool gets its name from the fact that it used to store strings in it. The strings were either URIs or string literals for RDF. However, it didn't take long before we needed to store other data types as well, starting with doubles, and eventually moving on to the entire set of XSD datatypes. By this point, we had a lot of code using the name "String Pool", and we were all used to referring to it by that name, so we kept calling it that, despite the fact that it holds much more than strings.

The purpose of the string pool is to map these data objects to a unique number representing a node in the RDF graph, which we call a graph node, or gNode. We also need to map from a gNode back to the data, so we know what that node is supposed to be representing.

The string pool is based on two main structures, with each structure providing one of the two mappings we need.

The first is an AVLTree, which is used to sort all entries (of all data types). This is used to look up data (strings, URIs, numbers, dates, etc) to map it back to a gNode (a "long"). It is also used to find ranges of data, such as all URIs beginning with the rdf domain, or all dates in a range. This tree is phased, in that it contains multiple root nodes, with each root corresponding to a phase. Only tree nodes uniquely belonging to the latest phase can be written to. Older phases are for reading data only, and each phase is associated with Answers obtained when that phase was the most recent. (This is why Answers must be closed - we can't mark nodes from an old phase as free until the Answer no longer needs them).

The other structure is called an IntFile. This is an array integers, which we use to hold an array of string pool entries. These entries each contain exactly the same information as the nodes in the AVLTree (laid out in the same way). The entries are indexed in the array by gNode value. Each entry is 72 bytes, so a gNode ID of 100 would correspond to data starting at byte 7200.

Importantly, this array is not phased. Once a gNode gets allocated in a phase, it represents the same data in all phases. The gNode can only be reused after the data has been deleted, AND all phases that have ever referred to that gNode have been closed.

So we have a tree which maps from data to gNode (the "localization" operation), and the array which maps from gNode to data (the "globalization" operation).

Out of Synch

Back to the problem: we have an entry in the tree that is not in the array. Now the methods that put data in the string pool put that information into both structures at the same time. The structure of this information is identical for both structures (the array doesn't have to store the gNode, since the location of the entry gives this). For a gNode to come up as a "blank node" means that the entry in the array is full of zeros, meaning it hasn't been written to.

The problem is trying to work out how the same data can be written into two files, and only show up in one of them.

Data written in a phase tree is really irrelevant until it is committed. Committing means writing the location of the new root to a separate file (called the metaroot file). So if we see data in the tree, then the tree MUST have been correctly committed to disk. The operation of committing means "forcing" all data to disk in a consistent way. We do this by forcing the tree to disk (if this fails partway through, then the old tree data is still valid), and only once this is finished can we save this new root to the metaroot file (making this new root valid in future). If you look at the prepare() method, then you'll see this data being forced to disk, and only then is the metaroot file updated and forced to disk.

So how can this AVL tree get ahead of the array in the IntFile? This could only happen if the IntFile were not forced to disk when the tree was forced to disk. This would mean that while the data was "written" to the array, it would not have arrived on the disk yet, even though it was committed to the tree. This would be bad, as nothing should be "committed" until it is completely consistent on disk.

So the solution was to find if there was any code path where the tree were forced to disk and the array were not. Looking in the string pool, it turns out that the tree is only forced to disk in one place, and the array is never forced to disk! So this must be the source of the problem.

Write behind at the OS level is generally a safe operation, even when a process is killed. However, it is possible to call write() and have things die before the data makes it to disk. (The libc libraries can do write-behind, the OS could die in some way, power gets pulled, etc). So the lack of synchronization is unlikely, but possible. This is why we've never seen it before now.

The solution is simply to ensure that the IntFile is completely written, before any data relying on that file is consistent enough to be committed. This means we just need the single line before updating the metaroot file:


I believe the bug could be reproduced by inserting a large number of unique literals into the store (sufficient to overflow the caches and force the JVM to buffer IO); followed by a commit(); and then kill -9'ing Mulgara immediately the commit returns.

Andrae's suggestion here is an attempt to fill the write-behind buffers, committing the data in an inconsistent state (since there is necessary data in the write-behind buffer), and then killing the write operation before these buffers can reach the disk.

Since we're trying to prevent the IO operations from operating correctly at the libc/OS level, it's not a problem that is suitable for running in JUnit!

So we're confident we've found the problem, but consistently reproducing it is not
trivial. This makes it similarly difficult to properly test that it's fixed.

I'm the one who understood the string pool structure enough to look for this and find it, but I wouldn't have even been looking in the right place had Andrae not taken me there. This story got played out in a similar way again the following day.

Transaction Exceptions

The String Pool bug was a vital one to find and fix, but it was extremely rare, and really hadn't affected us before this first bug report. It is a testament to how rare the bug is that this was our first report of it in the nearly 6 years that it has existed! However, I still had my transaction bug to find, and I was getting this one all the time.

I had managed to create a test case that was guaranteed to fail for me. My code performed a simple query (a duplicate of one that usually failed in our tests), and then iterated through the Answer, printing the results. However, before iterating, I did exactly what ItqlInterpreterBean does, and checked isUnconstrained() first (in which case the return value should be true).

This almost always failed, but I soon discovered that if I did the query (successfully) in the iTQL shell, then it would sometimes let my test code run correctly. My first approach was to see the difference between my code and the iTQL shell, and I finally realized that the shell would always call beforeFirst() on an Answer before check isUnconstrained(). Doing this in my sample code also fixed the problem. But why?

The exception I was getting was always a MulgaraTransactionException. The problem was happening when the transaction manager detected that an operation was being performed by a different thread to the one that had just registered itself for performing the operation. But I didn't know why this was happening.

While discussing what was happening, I started to gain an appreciation for what was happening inside the transaction manager. Andrae and I (mostly Andrae) even managed to spot some minor problems, which we could clean up. If nothing else, it was helping understand this new part of the system.

Transactions are the area Andrae just spent a couple of months working on, so I asked him to look at it. This was when I discovered that Andrae wasn't seeing these problems at all! I'd already established that a thread race was going on, and it seemed that my Core Duo (unfortunately, it's a 32 bit Core 1, and not the 64 bit Core 2) was demonstrating sufficient difference to a single cored machine to demonstrate the bug. So I gave Andrae an account on my machine, and went to bed.

RMI Threads

The next morning Andrae had some news for me. The transaction was being thrown correctly. For some reason an AnswerPage object was accessing an Answer using a different thread to the one that was asking for isUnconstrained() on the same Answer.

I was confused, as I thought that these two read-only operations would be perfectly safe operating in separate threads. Andrae explained that the semantics of an RMI connection like this required that only one thread be accessing the object at a time. Once he told me this, I immediately understood why, but it had never occurred to me before then.

The purpose of an Answer page is to package a page of Answer data, compress it, and send it over RMI to the client, all completely transparently to the client. This saves the client from making an expensive RMI call every time it needs the next row of an Answer. This is only ever performed on large result sets. The problem was that this would result in a pause for the client every time it ran out of the current page, and it needed to wait for the next one. The solution was to get the next AnswerPage in the background. In other words, they were supposed to operate in a separate thread. I have a blog entry on when I wrote this, back in 2004.

In general operation, using an Answer never resulted in two threads trying to access the server at once. The initial call to beforeFirst() would set the paging thread off, and pretty much all other calls would access local data. The only exceptions (like getRowCount()) were never going to be called while in the process of iterating over the Answer. So while I had not been aware of this issue with multi-threading over RMI when I wrote the code, the operation of the class would not have caused a problem anyway.

This all changed a few months after Answer paging was written, when isUnconstrained() was introduced. This indicates a "match" or true value for a query, even when there are no variable values to be returned. So before iterating over a result set, a client should always check for the value of isUnconstrained(). Unfortunately, the first thing a large Answer does after construction is to build start the paging thread. If isUnconstrained() is called immediately after construction of the Answer, then this will conflict on the server.

There are a few things to note here. A small Answer set will never be paged, so this bug will not manifest for Answers of less than 100 lines (or whatever mulgara.rmi.marshallsizelimit is set to by the user). Also, the form of a query will indicate if isUnconstrained() needs to be called, and only short, non-paged Answers will need this method called. Usually, the only method that will ever be called while paging Answers in the background is the next() method. However, ever since isUnconstrained() was introduced, generic code for handling and printing Answers, such as what is found in ItqlInterpreterBean, will always need to call isUnconstrained() no matter the size of the answer set. In fact, this must be the cause of the "Concurrent access exception" errors that have been reported, and I never understood.

Andrae's new transaction code was written specifically to prevent inappropriate access like this. So by throwing this exception it is doing its job perfectly. It's a godo thing he wrote it, or else this bug would have been around for a lot longer!

Once Andrae explained to me that we now had a situation where two threads could try to speak to the server at once, I realized I had to prevent both threads from operating on the server at the same time. The background thread is only ever started synchronously, in response to a call to the constructor, beforeFirst() or next(), and it ends asynchronously. On the other hand, the other methods which use RMI are all started and finished synchronously with respect to the rest of the client system. The way to handle this then is for any potentially conflicting methods to wait until a page returns.

Fortunately, the mechanism for this page return is already in place. The method is called waitForPrefetchThread(). This is the ideal method to use here, since it manages timeouts, throwing an exception if the server takes too long. All we had to do was put this method into the start of every method which makes an RMI call. It only took a few minutes to add the code, and then for the first time in a long time, every test passed!

Like the first one, this bug has been around for a while. It would also have taken much longer to be found if it were just Andrae or just myself working on it. It's a good thing we're both on it at the moment. I'll have to try to make more time available when we can both be online at once.

I hope Andrae is feeling good about these bug fixes, because I sure am!

Friday, February 23, 2007

Dreaming in Code

Time has been too short for me to comment on a couple of articles I've saw last week, so I'll just write something brief.

The first story was Software is Hard, which is an interview with Scott Rosenberg, the author off Dreaming in Code. Some of this story seems so familiar, and yet some of it seems unaware of modern software production techniques. Not that I can blame anyone for this. No technique works in all situations, and few are taught in schools or universities around the world. The most effective become a "fad" for a while, as those whose projects are most suited to them discover these techniques, but the resulting hype sets unrealistic expectations for people with less compatible project requirements.

Of course, the techniques I'm referring to are the various types of Agile programming, such as XP (the one that suffered the most from hype), Scrumm, and my own company's COSM. It is not a part of my duties to work directly with COSM, but I've still spent some time with it, and I agree that it is impressive, for the project planning as much as for the techniques of integrating business component with code components. But Agile is not the only useful technique out there.

Having defended these techniques, I will also say that they are not a panacea. Most people who use them don't really use them. They pick up on some ideas, but for reasons of practicality of preference, they decline to implement the entire paradigm. Another problem is that programmers are often at fault. It's one thing to have a great plan, but it is completely different to follow it. The type of plan you have is also going to suit different programmers differently. Highly skilled and creative programmers may be better with agile techniques, while those who pass a postgraduate course in programming will often be better suited to more structured environments like the waterfall model. (Note: I've never heard of, let alone seen, the waterfall model actually working).

It is this last part about asking talented (or any) coders to conform to management techniques that aligns most with what Scott has to say on the topic. One point of note is that he points out how good programmers enjoy re-inventing the wheel as it may often be faster than learning the intricacies of how "someone else" did it. The problem with this being that the resulting code is not tested as well, and has not been iteratively improved by running in the real world.

While this comment is true, I think Scott is looking at the problem from a traditional "commercial" viewpoint. Many programmers today, especially those in agile environments, will choose to use an open source project which implements some important functionality. The "challenge" that programmers enjoy is then sated by the integration of the many tools and libraries typical of most projects. Have a look at the library directory in Mulgara for a common example. There are 75 separate Jar files in there, all of which are from external projects.

In summary, he's sort of right, but he's also missed the ability of agile programming to work in some places. He has also seemed to have missed open source software, both as a project paradigm, and as a resource that modern programmers are absolutely ready to use.

By the way, I liked the title of the book. In my early days of programming I had several dreams in C: not about C, they were actually in C. The plot was a set of actions which was represented by functions, with people, places and events being structs. I've heard the experience is common.

A Stratified Profession

A different tone was set by Prof. Neil McBride in his article The Death of Computing. He sets a very cynical tone criticizing those still adhering to computationally pure programming techniques, and advocating the pragmatic approach. In particular, Neil talks about an inter-disciplinary approach for computers.

I like the idea of the interdisciplinary approach. After all, computers were always tools which we use to do jobs. They don't exist for their own benefit (though this has almost changed now with the advent of the internet). When I was younger, I noticed that all the successful approaches to computing relied on mixing skills with computers with expertise in engineering, finances, medicine, and so on. This made sense to me then, and it makes more sense now. This is particularly evident in the field of computational biology, where unbelievably complex systems (like genomes) are finally starting to be managed.

I also agree that in the past universities considered the computational purity above all else, and that rigidly sticking to this path is ignoring the pragmatism that the commercial world today wants. However, there seemed to be no acknowledgment of the continued need for the purists as well.

The idea seems to be that where once there were purists, today we need only pragmatists. I disagree with this. I think we need the purists as much as we ever did, but now there are also roles for the pragmatists. Whereas the profession was once restricted to the academic mindset, today we have a stratification, with different people needed at all levels.

We really do need people who don't understand a lot of the underlying system but who are prepared to be the resources needed for large financial institutions to build their enterprise systems. We need the talented developers who can take an idea, and in a few months turn it into a prototype that can set a new standard on the internet. We also need the theoreticians who analyze logic and modeling systems for completeness, or create new mathematical techniques for representing and transforming data.

I agree with the need to take a pragmatic approach. However, it can be taken too far, as is evident in many learning institutions today. Favoring pragmatism over everything else is throwing the baby out with the bathwater.

Tuesday, February 20, 2007


Interface design appears to fall into two categories.

The first category is where a set of functionality is to be provided, or is available in some way, and the interfaces are then built to provide access to all of this functionality. These designs are typically obtuse, and force a developer to jump through obscure hoops for their own internal gratification. 90% of interfaces fall into this category.

The second category is where the designer thinks about the task to be performed, and then thinks about how the code they would want to write in order to accomplish this task. Subsequent implementation may force some extra requirements into the design, but it is almost always possible to write implementations that largely fit the initial design.

Of course, the first category is built from the bottom up, and the second is top down. Sometimes it is necessary to use the bottom up approach, particularly when providing access to a pre-existing system, but the results are almost never pretty. Unfortunately, given the difficulty of many interfaces available today bottom up design seems to be the norm for designing interfaces. I want to name names here, but with the exception of Microsoft (MFC, or COM+ anyone?) it hardly seems fair to many of those hard working developers out there. (Actually, MFC doesn't seem to be a bottom up design. It's just full of weird inconsistencies where 6 similar-but-slightly different tasks rely on 6 completely unrelated mechanisms).

As an aside, when I say "interface", I'm not referring to Java interface definitions. I'm referring to the more general concept. These can be defined as Java interfaces, C++ headers, IDL files, XML descriptions, IUnknown querying, and more.


Many interfaces I've seen for interacting with RDFS and OWL have had bottom up interfaces, often because they are trying to provide all of the functionality available in these languages. However, the result is usually very messy, and difficult to work with. For many of these interfaces, you really need to know OWL in order to use the interface.

However, the task that most developers what to achieve is often much simpler than anything that would require a complete knowledge of OWL. Typically, a developer will want to define two things: A model, and instance data.
  • The model will generally involve a taxonomy of classes, each with their own specific fields. It will describe properties on those fields, such as data types, lists, which ones are key fields, which ones are optional, and so on. It will also describe relationships between the classes, and possibly restrictions on those relationships.
  • The instance data will simply be a set of objects which each have a type defined in the model.
To be sure, all OWL interfaces out there allow all of this, but I personally haven't found them easy to use.

It should also be noted that OWL isn't the only way to do this. UML has done all of this for a long time now. This should be no surprise, as almost all features from each language (OWL and UML) can be mapped into a representation in the other. The exceptions are rarely employed and can be worked around (one of these exceptions is n-m associations in UML). However, UML is typically used statically at design time, and not dynamically at runtime. This makes sense, since UML is a closed world model, and a runtime system would need to allow temporarily incomplete systems while instance data was being built. OWL has a natural advantage in this regard.

RDFS/OWL Interfaces

When I needed a modeling interface, I made a conscious decision to avoid all of the OWL constructs, and only pick what I needed. I reasoned that the underlying language already would support any new required constructs, and trust that it would be possible to make sensible additions to the interface if any new requirements came along. My justification here is in my experience with interface changes usually being trivial, but modifying an underlying construct is often difficult or impossible.

Once I made that choice, my next step was to work out just what I wanted to do. The list was short, being comprised of the class definition, and object instantiation described above.

So what is the easiest way to describe each of these things? To me, a class definition is the name of the class, along with any inheritances it may have. It also contains a collection of fields. So a class definition should be a constructor which accepts a name, a list of other class definitions (or their names if I wanted to get into referencing classes before their definitions), and a list of fields. Fields would also require a name, a datatype (object or simple type), and some flags to indicate if they represented required data, a key field, and if they represented a list.

So was this approach useful? Well other than being verbose (having to describe all the fields, and then construct the class definition), it seems easy to use, and has been quite successful in the code we've used it in.

A more interesting question has been object instantiation.

I decided to take a leaf out of Perl here, where objects are just a hashmap, keyed on field name. This works quite well, and described a cheap way for me to get objects up and running. Wrapping the hashmap in a class that is given a copy of the class definition allows the data to be checked for consistency and completeness, and in some cases inferencing can be performed.

My only regret with this approach has been that it is verbose in a similar way to defining classes. The hashmap has to be created and fully populated, with each field taking its own verbose call for insertion. While easy, it isn't the way I would like to create these objects. Using the objects is similarly verbose, with all access going through get and put methods.

Thinking about it, the most obvious thing that I want to do here, is to simply create the object with an inbuilt language constructor. In the case of Java, this means a call to new, with appropriate parameters. This is what UML would have provided, but UML would have been compiled into Java source code before compilation. What I'm looking for here is dynamic creation of the class.

Bytecode Libraries

This is where my interest in bytecode libraries like ASM and BCEL comes in. Using these libraries it is possible to turn a class definition into a Java class, that can be instantiated with a custom class loader.

Make the custom class loader the current class loader, and you could theoretically use the new keyword. However, you'd have to cheat by doing a bait-and-switch, where you let the compiler build against one instance of a class, but have the class loader provide your class instead. OK, so this is an serviceable hack, but it's fun to know it's possible. Accessing fields isn't so easy though, and reflection is the only effective way.

A bigger problem is evolving class definitions over time. I've dynamically built classes in the past, but never tried to update a class after it has already been loaded once. I suppose the simplest way would be for each modification to get a new version ID that becomes a hidden part of the name, but that could lead to problems.

A better language to do this in is Ruby. Ruby already lets you define classes at runtime. More importantly, it lets you update them at runtime as well. I'm still a Ruby beginner, and I know nothing about the VM, so most of my ideas are just that, but it seems like a good idea.

I haven't had the chance to work on any of this modeling code for some months now, but I'm hoping I'll get the chance again soon. Depending on what seems most "natural" at the time, I may get to do some interesting things yet.

I should point out that most of my API is based on RDFS, with just a little OWL (InverseFunctionalProperty, Transitive, cardinality). While this sounds very restrictive, these few constructs provide a great deal of functionality. I'm looking forward to applying a few more.

Thursday, February 15, 2007

Vista DRM

Windows Vista puts a lot of work into preventing what it considers to be "unauthorized" access to copyrighted material. In an attempt to plug every leak (an impossible task) the DRM system pervades every aspect of the OS, from the kernel upwards.

One disturbing aspect is the constant scanning of the system to determine if there are any fluctuations in voltage, unexpected register content, etc. Over time this totals to significant energy consumption. Also consider that the CPU requirements are significantly higher than would otherwise be expected, meaning that power consumption gets even higher.

We often don't pay attention to how much power extra CPU cycles burn in a PC, but it becomes painfully obvious when traveling with a notebook computer. I once had a PC which made it clear whenever I scrolled text in a web browser, as the fan in the power supply would go up in pitch with the extra load from the CPU. So the power difference of CPU use can be significant, despite it being hidden in amongst the hair dryer and air conditioning in your electricity bill.

If 90% of the new computers in the world (Microsoft's approximate market share) are going to be running Vista, then what will be the extra power consumption? This is a worldwide expansion in energy consumption for the sake of the MPAA.