Tutorial

This tutorial will guide the reader through applying SharC to a couple of sample programs. First, we'll look at a simple program that uses a pipeline model for parallelism..

Simple Pipeline

Open up this file in your favorite editor, and follow along. This file can be used as a sample input.

First, let's take a look at how this program works. The main() function creates a list of stage structures. Then, it spawns a number of threads, passing the stage structures as arguments. Next, it allocates buffers and passes them to the readstage until it indicates that it is done reading from the file with the readstage->last flag. Finally, main() waits for the other threads to finish.

The next important function to look at is thr_func(). This is the function that the threads will be running, albeit with different stage structures as arguments. Until receiving the last chunk of data, threads wait until their stage is passed some data. Then, they copy the data pointer into a local variable and null-out the field in the stage structure. This allows the thread to call do_work() without holding a lock, and indicates to the previous stage that the data pointer is available for storing a new value. If the value returned by do_work() is less than the expected size, then the current chunk is assumed to be the final one. After applying do_work() to the data, the thread passes the pointer to the next stage structure in the list, and signals the thread for that stage that it has done so.

Compiling with SharC

SharC is part of the Ivy compiler, which has three parts: Deputy, Heapsafe, and SharC. For this example, we'll disable Deputy by passing the --nodeputy flag. With the exception of this flag, Ivy is invoked like gcc. To compile our example:

$ ivycc --nodeputy -g -o pipeline_test_orig pipeline_test_orig.c

The example should compile with a few warning that we'll return to later.

Runtime Errors

After running the program, however, we note that there are many sharing violations recorded in sharc.log. In particular, SharC has inferred that the fields of the stage structures must be in the SDYNAMIC mode, but it is clear that these fields are read and written by different threads. Therefore, at runtime we see errors like this:

SHARC: read conflict(0x30e7fdac):
        who(1) readstage->data @ pipeline_test_work.c:163
        last(2) Write

This error message indicates that some thread is trying to read the data field of readstage after another field has written it. If there isn't any synchronization, then this is a data race. However, if we go look at like 163(and the other lines where a data field of a stage structure is accessed), then we see that this field is always protected by the mutex in the same stage structure. The same is also true about the size, and last fields, as well.

Preliminaries

Before adding annotations, we'll add a bit of code at the top of the file so that we can still compile with gcc if we want:

#define SHARC_ON

#ifdef SHARC_ON
#include <sharc/sharc.h>
#else
#define SPRIVATE
#define SREADONLY
#define SLOCKED(x)
#define SDYNAMIC
#define SRACY
#define SCAST(x) (x)
#define SINIT(x) (x)
#endif

After adding annotations, if we want to go back to using gcc, we can just undefine SHARC_ON. (If there's no need to go back, just #include <sharc/sharc.h>.)

SLOCKED Annotation

We can now annotate the stage structure definition as follows:

struct stage {
    struct stage *next;
    pthread_cond_t *cv;
    pthread_cond_t *mut;
    char *SLOCKED(mut) data;
    unsigned int SLOCKED(mut) size;
    int func;
    int SLOCKED(mut) last;
};

However, now when we compile, we get an error like this:

Error: The lock S->mut is not SREADONLY for SLOCKED object S->data at pipeline_test_work.c:50

This is because the type of the data field depends on some other object, in this case the mut field of the same stage structure. If the mut field were to change while the type of the data field depends on it, then type safety would be lost. Therefore, SharC requires that objects that a type somewhere depends on must be SREADONLY. So, the stage structure becomes:

struct stage {
    ...
    pthread_mutex_t * SREADONLY mut;
    ...
};

This annotation leads to another compile-time error:

Error: Write to SREADONLY lval new->mut at pipeline_test_work.c:130 in #line 130 "pipeline_test_work.c"

At line 130, the SREADONLY field in a stage structure is being written. After inspecting the code, we can see that this write is for initialization, and that it is taking place while the program is still single-threaded. Therefore, we can tell SharC that we're just initializing the field with the SINIT() call, but first let's modify the code so that the return of malloc() goes into a temporary variable first. The code in make_stage() becomes:

struct stage *make_stage(...) {
    ...
    pthread_mutex_t *tmut = malloc(sizeof(pthread_mutex_t));
    new->mut = SINIT(tmut);
    ...
}

Sharing Casts

Now when we try to compile, we get a couple more compile-time errors:

Error: Sharing cast needed for assignment: #line 53 "pipeline_test_work.c"
data = S->data; at pipeline_test_work.c:53
        Got: char SLOCKED(mut)   * SLOCKED(mut)  
        Expected: char SPRIVATE   * SPRIVATE  

Error: Sharing cast needed for assignment: #line 70
(S->next)->data = data; at pipeline_test_work.c:70
        Got: char SPRIVATE   * SPRIVATE  
        Expected: char SLOCKED(mut)   * SLOCKED(mut)

In thr_func() we're copying a pointer into and out of a local pointer that SharC determines to be SPRIVATE, and it's being copied to/from a field in the stage structure that is qualified as SLOCKED. This results in the type error above. We could try to copy the SLOCKED qualifier over to the local variable, like we did with SRACY above, but this would be incorrect. Notice that the local variable is accessed without the mutex being held when it is passed to the do_work() function. Therefore, we will accept SharC's suggestion to include sharing casts at these locations. So, line 53 becomes:

data = SCAST(S->data);

And line 70 becomes:

S->next->data = SCAST(data);

Warnings

At this point, the example should compile and run without errors. But we might still need to worry about those warnings. First, there is a series of warnings like this:

Warning: global inFile must be annotated SDYNAMIC. Touched by thread.

These warnings occur because SharC determines that these variables can be touched by multiple threads, but we haven't made an explicit annotation. SharC adds these annotations automatically, so we can ignore the warning since our current example consists of only a single file. If our program consisted of multiple files, then the variables and functions mentioned in the warnings would need to be given the correct annotation in the appropriate header file. Alternately, SharC can generate all of the correct SDYNAMIC annotations and save them in a file off to the side. This works as follows:

SDYNAMIC Inference

ivycc can be invoked in such a way that it performs whole program analysis over all of the source files in a program. This feature would typically be used in conjunction with make, or any other build script. That is, most programs can be built with ivycc by saying something like:

$ make CC=ivycc

Ivy performs whole program analysis by forking a process off to the side that receives CIL globals through a named pipe. When this process receives the SIGTERM signal, or when a few minutes have passed since the last global was received, the off-to-the-side process applies its analysis to the assembled globals.

To invoke SharC's SDYNAMIC inference on a program built with make, we would issue the following command:

$ make CC="ivycc --global-analysis=sharing --build-root=/home/you/build-dir"

Then, after the build is finished, we can wait a couple minutes or send SIGTERM like this:

$ killall ivy.asm.exe

Compile-time errors during this process may leave the global analysis in an inconsistent state. To start over fresh, kill the ivy process as above, do a make clean, and remove a directory that ivycc uses for some metadata:

rm -rf /home/you/build-dir/.ppataches

Library Calls

During the SDYNAMIC inference, SharC will also complain if functions without definitions(i.e. external functions, or library calls) are passed SDYNAMIC arguments. The warning will look something like this:

External function foo is passed a dynamic argument at file.c:100 : arg1

There are a couple of ways to deal with this. First, if the function reads and writes the arguments, but doesn't store any aliases, then we can simply summarize the read/write behavior of the function. Some examples of this can be found in ivy/sharC-include/sharc_libc/sharc_libc_patch.h. Here is what the signature for memcpy looks like:

void *memcpy(void *SWRITES(n) dest, void *SREADS(n) src, void n);

These summaries can also refer to the length of C strings:

int chmod(char *SREADS(strlen(path)+1) path, void mode);

However, if the read/write behavior isn't easy to summarize, or if the library will store aliases to the pointers it is passed, then the library must also be analyzed and processed with SharC.

Sharing Cast warnings

In our example, we see a warning that looks like this:

Warning: Failed to prove that S->data is dead after Sharing Cast at pipeline_test_work.c:53

Since a sharing cast nulls-out a pointer, SharC will generate a warning if it can't prove that a pointer won't be used again. In this case, SharC doesn't know that there aren't aliases to the data field of S, and so fails to prove that S->data won't be used while it's nulled-out. However, since data is a local variable, and its address isn't taken, SharC sees that it is no longer used after the other sharing cast, and so does not generate a warning.