Archive for May, 2005

MT tools taxonomy

Wednesday, May 25th, 2005

There has been some discussion where I work about what kinds of tools are good for supporting multi-threaded programming. There are lots of different kinds of tools and features that can help. My natural tendency is to try to create categories and taxonomies when I get a bunch if different-but-related ideas. So here is my attempt to give an overview of how a development tools chain can support threads from beginning to end.


MT Tools Taxonomy

For the sake of contemplation, you can divide software development tools into two categories. Some tools are used to create your program, and other tools operate on your program after it’s been created.

The primary tools in the first category are compilers and linkers. Also included are pre-processors (auto-parallelisers, etc.), static checkers (lint), etc. These tools don’t get to see the program in action. They don’t depend on the dataset or runtime environment of the program. They must assume that all possible code paths through the code are important and relevant. These are “compile-time” tools.

The primary tools in the second category are debuggers and performance tools. Also included are dynamic checkers (for synchronization, memory allocation, code coverage (like tcov), etc.). These tools observe the program in action. But they are only as good as the dataset you feed into your running application. (If your program is interactive, then the dataset is the pre-canned or user-performed set of actions that exercise your program when it runs under the tool.) These tools have the advantage and disadvantage that they can focus on frequently executed paths, and ignore code paths that are not executed in practice. These are “runtime” tools.

Because of the recent popularity of multi-core chips, tools to help create and maintain threaded applications are more important than ever. There are three aspects to this, decomposition (how to break your task into multiple threads) and implementing proper synchronization. There are few tools to help programmers effectively decompose their application into threads. Most people focus on trying to get the synchronization right, and most threading tools are created to help this kind of task.

Compile-time tools

Compile-time tools focus on correct code generation, and they can help the user implement correct synchronization in a variety of ways. Directives can be inserted by the user to help them explain to the tool chain how they intend the synchronization to work. Such directives can be implemented as pragmas or language extensions.

Assertion-style directives can be used by the compiler or an external tool to verify synchronization operations. For example, (assuming a structure type named ST) the user could declare that “lock ST.lk protects variable ST.data”. As with lint, the user will probably need ways to suppress specific warnings. Such suppression directives serve as red flags when it comes time to debug problems. This style of directive is better implemented a pragma instead of a language extension. It will be assumed that the presence or absence of these directives doesn’t affect program correctness.

Implementation-style directives can support higher level synchronization operations in the compiler. For example, “always protect variable ST.data with lock ST.lk”. The compiler would make sure to generate lock and unlock primitives to protect all accesses to the structure member named data. This kind of directive would be better implemented as a language extension, because it’s primary purpose is to drastically affect program correctness.

An example of what I mean by Implementation-style directives is the “synchronized” keyword in Java. This keyword supports a rich set of synchronization styles in Java.

Another example of Implementation-style directives is the OpenMP system. The primary purpose of the OpenMP directives is to specify the way work is broken down into chunks, which makes it different than the other tools I’m talking about here (which focus on synchronization implementation and checking).

Implementation-style directives will allow the compiler to optimize your code more effectively. Memory operations that don’t need to be synchronized can be moved outside of critical regions, and critical regions can be merged, split, and moved around much more effectively when the compiler knows exactly what semantics need to be preserved.

The barrier to entry will be high for using implementation-style directives because it causes your code to be non-portable until standards (either official or de facto) are created for such directives. It’s possible that you could omit these directives on a system that didn’t support them and create a properly functioning sequential program, but your code would have to be designed and implemented to operate correctly in both modes. Doing this is straightforward but non-trivial. It doesn’t come for free.

Other implementation-style directives can support a wide variety of high level synchronization mechanisms: Critical sections (a block of code protected by an automatically allocated global lock), synchronized structures and classes whose members are automatically protected by a per-object lock, synchronized classes in C++.

The more information the compile-time tools have, the faster and more correct the resulting program will be. If the tools support a wide variety of assertion-style and implementation-style directives, then the error checking they do will be more likely to find useful problems, and optimizations that they do will be better and more correct.

Runtime-tools

Runtime tools focus on analyzing, controlling and inspecting the behavior of a running program. They are less helpful during the creation phase of development, and more helpful in the debugging and tuning phases. Some runtime tools implement a harness that executes checking code along side the running program, and some tools collect event traces at runtime and do the analysis later. Runtime tools depend on significant support from the compilers. Source line information, type information, and compile-time instrumentation (for data collection) are widely used by runtime tools.

Runtime checking tools can help repair and improve threaded programs with a variety of thread-specific features. They can check for data races in threaded programs (either at runtime, or post hoc) by analyzing the memory accesses and lock operations performed by a test run of the program.

Performance tools can detect which locks are the most frequently accessed, which locks are most likely to cause a thread to block, which locks result in the longest total wait times. By doing this the tool can help you improve the performance of your synchronization. They can detect violations of any assertion-style directives that the user has put into the code.

Debugging tools can show details of running threads, which ones are blocked on which synchronization objects and which locks are held by a particular thread. Debuggers can allow you to suspend or resume individual threads in order to provoke certain conditions in your program.


As I said, which of these tools we might extend or develop is still being discussed around my part of Sun. If you have feedback on which areas need more attention, or what you think we should do, let me know.

pseudonyms

Monday, May 23rd, 2005

A trust network is the only thing that is safe against marketing.

Any individual person who becomes popular enough as an expert on a particular topic, will normally be commercialized into a product which can be sold. At that point you have to start looking at where they get their “corporate donations” from in order to interpret what they say.

How do I tell if an music album is good? I can find a forum, and look for what people have written about it. How do I know if the people writing about it know what they’re talking about? Well I can try to guess based on how they write, and what they say.

But maybe they know a lot about blues and jazz, and for some reason they decide to review a rock album? I’ve been playing around with Orkut recently. You can hook up with people and places you know, and reveal information about your self in a controlled way to people whom you name as “friends”.

When I read a message someone wrote about an album, I want to be able to go find out about them. Do they like music? How *much* do they like music. What kind of music do they like? How old are they? Are there interests like mine? Do they like other music that I like?

On the other hand, maybe the person who posted the review was just a scammer with a temporary account trying to boost sales? It would be nice to have a way to know if that’s true.

I am hopeful that in the next 10 years the idea of federated identity (aka “single-sign-on”) will become popular. Remember the book Ender’s Game? In that fictional story (science fiction) two people who were very well known and very influential in world politics were completely anonymous. Well not anonymous really, that’s the whole point. They were pseudonymous. They were well known personalities but nobody happened to know who they were in real life. The kind of protection this can give to free speech is mind boggling.

Any loony can post his or her ideas anonymously. If they reveal facts that can be checked by others, then they might spark a debate that can turn into something real. But free speech doesn’t really work unless you have free discussion. And to do that, you have to trust someone with your identity (whether it’s a re-mailer or a website).

If we had ubiquitous PKI (public key infrastructure), you wouldn’t have to trust anyone. You create a public/private key pair, register it with a made-up name, and you can carry on conversations for years, and let people get to know you without needing to reveal your true identity. If the website you’re using gets shut down (as they often do), you can use your same identity on another web site, just by signing your messages with the same key.

The only compelling reason to sell federated identity to Joe Six-pack is by telling him he doesn’t have to remember 100 passwords anymore. But I have higher hopes. Once the software becomes standardized I expect there to be trustable “repositories” for pseudonymous identities. This will be a step in the right direction.

–chris

Pretty printing C++ types with dbx

Tuesday, May 17th, 2005

Since Lawrence doesn’t work at Sun any more, I’ll swipe a blog entry of his to make sure it stays available.

A tip from Lawrence Crowl:

One of the problems with debugging C++ programs is that they have many user-defined types. The debugger typically does not know anything about those types, and so cannot provide any high-level printing of those types. Instead, the debugger prints the types’ representations.

For example, consider a simple C++ standard string.

    #include <string>
    #include <iostream>

    int main() {
        std::string variable( "Hello!" );
        std::cout << variable << std::endl;
    }

In dbx, the result of printing variable is:

    (dbx) print variable
    variable = {
        __data_   = {
            __data_ = 0x41260 "Hello!"
        }
        npos      = 0
        __nullref = 0
    }

Not nice.

The Sun dbx debugger provides a helpful facility for up-leveling the printout. This facility is called pretty printing.

We can help dbx by defining a pretty printing call-back function. In essence, we write a function that converts from our high-level type into a char*. Dbx will look for pretty printing functions with the name db_pretty_print and a first parameter that is a pointer to the high-level type. In our example, the function is:

    char* db_pretty_print( std::string* var_addr, int, char* ) {
        return const_cast< char* >( var_addr->data() );
    }

(The second and third parameters are not needed in this example.)

Now, with the -p flag on the dbx print command line, dbx calls the pretty-printing function and uses the result for its output.

    (dbx) print -p variable
    variable = Hello!

You can make pretty printing the default by executing

    dbxenv output_pretty_print on

either in the debugger or in your ~/.dbxrc. Once pretty printing is the default, you can print the type’s representation with the +p flag.

    (dbx) print +p variable
    variable = {
        __data_   = {
            __data_ = 0x41260 "Hello!"
        }
        npos      = 0
        __nullref = 0
    }

For more information, type “help prettyprint” within dbx.

See more source in dbx

Thursday, May 12th, 2005

Okay, so you use dbx from the command line. When dbx stops at a breakpoint, it tells you the source line where you stopped. Well that’s nice. But it’s usually not enough context to know where you really are. You’d like to see more of the source. You can use the ‘list’ command to show you the source from that line down, but how can you see the source above and below that line at the same time? Easy. Write a little script. I got this script from someone else in my group, so I can’t take credit for it, but now I use it all the time. Put this script in your .dbxrc file, and away you go:

li() {
   list $[$vlineno-5], $[$vlineno-1]
   kprint -n ">"
   list $vlineno
   list $[$vlineno], $[$vlineno+5]
}

Here’s what it looks like in use:

stopped in main at line 64 in file "Cdlib.c"
   64     if (argc == 1)
(dbx) li
   59     FILE *cd_file;
   60     cd_title *cd_p, *prev_cd_p, *cd_p_2;
   61     char cd_info_path[PATH_MAX], *lp;
   62     int tr;
   63
>   64     if (argc == 1)
   65       sprintf (cd_info_path, "%s/.workmandb", ...
   66     else
   67       strcpy (cd_info_path, argv[1]);
   68
   69     cd_file = fopen (cd_info_path, "r");
   70     if (cd_file == NULL) {

Getting the current line to line up with the others (because of the arrow) even when the first character might be a tab, is left as an exercise for the reader. 🙂 more later. I’ll be on vacation for a week.