Print-friendly Version

The command-line utility lock_lint analyzes the use of mutex and multiple readers/single writer locks, and reports on inconsistent use of these locking techniques that may lead to data races and deadlocks in multi-threaded applications.

LockLint Overview

In the multithreading model, a process consists of one or more threads of control that share a common address space and most other process resources. Threads must acquire and release locks associated with the data they share. If they fail to do so, a data race could result, causing the program to produce different results when rerun with the same input.

Data races are easy to introduce. Simply accessing a variable without first acquiring the appropriate lock can cause a data race. But data race situations are generally very difficult to find. Symptoms generally manifest themselves only if two threads access the improperly protected data at nearly the same time; hence a data race may easily run correctly without showing any signs of a problem. It is extremely difficult to exhaustively test all concurrent states of even a simple multithreaded program, so conventional testing and debugging are not always an adequate defense against data races.

Most processes share several resources. Operations within the application may require access to more than one of those resources. This means that the operation needs to grab a lock for each of the resources before performing the operation. If different operations use a common set of resources, but the order in which they acquire the locks is inconsistent, there is a potential for deadlock. The simplest case of deadlock occurs when two threads hold locks for different resources and each thread tries to acquire the lock for the resource held by the other thread.

When analyzing locks and how they are used, LockLint (the command is lock_lint) detects a common cause of data races: failure to hold the appropriate lock while accessing a variable.

The following tables list the routines of the Solaris OS and POSIX libthread APIs recognized by LockLint.

TABLE 1 Mutex (Mutual Exclusion) Locks

TABLE 2 Reader -Writer Locks

TABLE 3 Condition Variables

Additionally, LockLint recognizes the structure types shown in Table 4 .

TABLE 4 Lock Structures

LockLint reports several kinds of basic information about the modules it analyzes, including:

• Locking side effects of functions. Unknown side effects can lead to data races or deadlocks.

• Accesses to variables that are not consistently protected by at least one lock, and accesses that violate assertions about which locks protect them. This information can point to a potential data race.

• Cycles and inconsistent lock-order acquisitions. This information can point to potential deadlocks.

• Variables that were protected by a given lock. This can assist in judging the appropriateness of the chosen granularity, that is, which variables are protected by which locks.

LockLint provides subcommands for specifying assertions about the application. During the analysis phase, LockLint reports any violation of the assertions.

Note - Add assertions liberally, and use the analysis phase to refine assertions and to make sure that new code does not violate the established locking conventions of the program.

Collecting Information for LockLint

The compiler gathers the information used by LockLint. More specifically, you specify a command-line option, -Zll, to the C compiler to generate a .ll file for each .c source code file. The .ll file contains information about the flow of control in each function and about each access to a variable or operation on a mutex or readers-writer lock.

Note - No .o file is produced when you compile with the -Zll flag.

LockLint User Interface

There are two ways for you to interact with LockLint: source code annotations and the command-line interface.

• Source code annotations are assertions and NOTEs that you place in your source code to pass information to LockLint. LockLint can verify certain assertions about the states of locks at specific points in your code, and annotations can be used to verify that locking behavior is correct or avoid unnecessary error warnings.

• Alternatively, you can use LockLint subcommands to load the relevant .ll files and make assertions. This interface to LockLint consists of a lock_lint command and a set of subcommands that you specify on the lock_lint command line.

The important features of the lock_lint subcommands are:

• You can exercise a few additional controls that have no corresponding annotations.

• You can make a number of useful queries about the functions, variables, function pointers, and locks in your program.

LockLint subcommands help you analyze your code and discover which variables are not consistently protected by locks. You may make assertions about which variables are supposed to be protected by a lock and which locks are supposed to be held whenever a function is called. Running the analysis with such assertions in place will show you where the assertions are violated.

Most programmers report that they find source code annotations preferable to command-line subcommands. However, there is not always a one-to-one correspondence between the two.

How to Use LockLint

Using LockLint consists of three steps:

1. Setting up the environment for using LockLint

2. Compiling the source code to be analyzed, producing the LockLint database files (.ll files)

3. Using the lock_lint command to run a LockLint session

These steps are described in the rest of this section.

Figure 1 shows the flow control of tasks involved in using LockLint:

FIGURE 1 LockLint Control Flow

Use LockLint to refine the set of assertions you maintain for the implementation of your system. A rich set of assertions enables LockLint to validate existing and new source code as you work.

Managing LockLint's Environment

The LockLint interface consists of the lock_lint command, which is executed in a shell, and the lock_lint subcommands. By default, LockLint uses the shell given by the environment variable $SHELL. Alternatively, LockLint can execute any shell by specifying the shell to use on the lock_lint start command. This example starts a LockLint session in the Korn shell:

% lock_lint start /bin/ksh

LockLint creates an environment variable called LL_CONTEXT, which is visible in the child shell. If you are using a shell that provides for initialization, you can arrange to have the lock_lint command source a .ll_init file in your home directory, and then execute a .ll_init file in the current directory if it exists. If you use csh, you can do this by inserting the following code into your .cshrc file:

if ($?LL_CONTEXT) then
        if ( -x $(HOME)/.ll_init ) source $(HOME)/.ll_init
endif

It is better not to have your .cshrc source the file in your current working directory, since others may want to run LockLint on those same files, and they may not use the same shell you do. Since you are the only one who is going to use your $(HOME)/.ll_init, you should source that one, so that you can change the prompt and define aliases for use during your LockLint session. The following version of ~/.ll_init does this for csh:

# Cause analyze subcommand to save state before analysis.
alias analyze "lock_lint save before analyze;\
        lock_lint analyze"
# Change prompt to show we are in lock_lint.
set prompt="lock_lint~$prompt"

When executing subcommands, remember that you can use pipes, redirection, backward quotes (`), and so on to accomplish your aims. For example, the following command asserts that lock foo protects all global variables (the formal name for a global variable begins with a colon):

% lock_lint assert foo protects `lock_lint vars | grep ^:`

In general, the subcommands are set up for easy use with filters such as grep and sed. This is particularly true for vars and funcs, which put out a single line of information for each variable or function. Each line contains the attributes (defined and derived) for that variable or function. The following example shows which members of struct bar are supposed to be protected by member lock:

% lock_lint vars -a `lock_lint members bar` | grep =bar::lock

Since you are using a shell interface, a log of user commands can be obtained by using the shell's history function (the history level may need to be made large in the .ll_init file).

Temporary Files

LockLint puts temporary files in /var/tmp unless $TMPDIR is set.

Makefile Rules

To modify your makefile to produce .ll files, first use the rule for creating a .o from a .c to write a rule to create a .ll from a .c. For example, from:

# Rule for making .o from .c in ../src.
%.o: ../src/%.c
        $(COMPILE.c) -o $@ $<

you might write:

# Rule for making .ll from .c in ../src.
%.ll: ../src/%.c
        cc $(CFLAGS) $(CPPFLAGS) $(FOO) $<

In the above example, the -Zll flag would have to be specified in the make macros for compiler options (CFLAGS and CPPFLAGS).

If you use a suffix rule, you will need to define .ll as a suffix. For that reason some prefer to use % rules.

If the appropriate .o files are contained in a make variable FOO_OBJS, you can create FOO_LLS with the line:

FOO_LLS = ${FOO_OBJS:%.o=%.ll}

or, if they are in a subdirectory ll:

FOO_LLS = ${FOO_OBJS:%.o=ll/%.ll}

If you want to keep the .ll files in subdirectory ll/, you can have the makefile automatically create this file with the label:

.INIT:
        @if [ ! -d ll ]; then mkdir ll; fi

Compiling Code

For LockLint to analyze your source code, you must first compile it using the -Zll option of the Sun Studio C compiler. The compiler then produces the LockLint database files (.ll files), one for each .c file compiled. Later you load the .ll files into LockLint with the load subcommand.

LockLint sometimes needs a simpler view of the code to return meaningful results during analysis. To allow you to provide this simpler view, the -Zll option automatically defines the preprocessor symbol __lock_lint; further discussions of the likely uses of __lock_lint can be found in .

LockLint Subcommands

subcommands that can be specified with the lock_lint command:

lock_lint [subcommand]

In this example subcommand is one of a set of subcommands used to direct the analysis of the source code for data races and deadlocks. More information about subcommands can be found in the summary at the end of this article, or in the lock_lint(1) man page.

Starting and Exiting LockLint

The first subcommand of any LockLint session must be start, which starts a subshell of your choice with the appropriate LockLint context. Since a LockLint session is started within a subshell, you exit by exiting that subshell. For example, to exit LockLint when using the C shell, use the command exit.

Setting the Tool State

LockLint's state consists of the set of databases loaded and the specified assertions. Iteratively modifying that state and rerunning the analysis can provide optimal information on potential data races and deadlocks. Since the analysis can be done only once for any particular state, the save, restore, and refresh subcommands are provided as a means to reestablish a state, modify that state, and retry the analysis.

Checking an Application

1. Annotate your source code and compile it to create .ll files.

2. Load the .ll files using the load subcommand.

3. Make assertions about locks protecting functions and variables using the assert subcommand.

4. Make assertions about the order in which locks should be acquired in order to avoid deadlocks, using the assert order subcommand.
   
   Note - These specifications may also be conveyed using source code annotations.

5. Check that LockLint has the right idea about which functions are roots.
   
   If the funcs -o subcommand does not show a root function as root, use the declare root subcommand to fix it. If funcs -o shows a non-root function as root, it's likely that the function should be listed as a function target using the declare ... targets subcommand.

6. Describe any hierarchical lock relationships (if you have any--they are rare) using the assert rwlock subcommand.
   
   Note - These specifications may also be conveyed using source code annotations.

7. Tell LockLint to ignore any functions or variables you want to exclude from the analysis using the ignore subcommand.
   
   Be conservative in your use of the ignore command. Make sure you should not be using one of the source code annotations instead (for example, NO_COMPETING_THREADS_NOW).

8. Run the analysis using the analyze subcommand.

9. Investigate the errors.
   
   This may involve modifying the source using #ifdef __lock_lint (see ) or adding source code annotations to accomplish steps 3, 4, 6, and 7.
   
   Restore LockLint to the state it was in before the analysis and rerun the analysis as necessary.
   
   Note - It is best to handle the errors in order. Otherwise, problems with locks not being held on entry to a function, or locks being released while not held, can cause lots of misleading messages about variables not being properly protected.

10. Run the analysis using the analyze -v subcommand and repeat the above step.

11. When the errors from the analyze subcommand are gone, check for variables that are not properly protected by any lock.
    
    Use the command: lock_lint vars -h | fgrep \*
    
    Rerun the analysis using appropriate assertions to find out where the variables are being accessed without holding the proper locks.
    
    Remember that you cannot run analyze twice for a given state, so it will probably help to save the state of LockLint using the save subcommand before running analyze. Then restore that state using refresh or restore before adding more assertions. You may want to set up an alias for analyze that automatically does a save before analyzing.

Program Knowledge Management

LockLint acquires its information on the sources to be analyzed with a set of databases produced by the C compiler. The LockLint database for each source file is stored in a separate file. To analyze a set of source files, use the load subcommand to load their associated database files.

The files subcommand can be used to display a list of the source files represented by the loaded database files. Once a file is loaded, LockLint knows about all the functions, global data, and external functions referenced in the associated source files.

Function Management

As part of the analysis phase, LockLint builds a call graph for all the loaded sources. Information about the functions defined is available via the funcssubcommand. It is extremely important for a meaningful analysis that LockLint have the correct call graph for the code to be analyzed.

All functions that are not called by any of the loaded files are called root functions. You may want to treat certain functions as root functions even though they are called within the loaded modules. For example, the function is an entry point for a library that is also called from within the library. Do this by using the declare root subcommand.

LockLint knows about all the references to function pointers and most of the assignments made to them. Information about the function pointers in the currently loaded files is available through the funcptrs subcommand. Information about the calls made via function pointers is available via the pointer calls subcommand. If there are function pointer assignments that LockLint could not discover, they may be specified with the declare ... targets subcommand.

By default, LockLint tries to examine all possible execution paths. If the code uses function pointers, it's possible that many of the execution paths are not actually followed in normal operation of the code. This can result in the reporting of deadlocks that do not really occur. To prevent this, use the disallow and reallow subcommands to inform LockLint of execution paths that never occur. To print out existing constraints, use the reallows and disallows subcommands.

Variable Management

LockLint database also contains information about all global variables accessed in the source code. Information about these variables is available via the vars subcommands.

One of LockLint's jobs is to determine if variable accesses are consistently protected. If you are unconcerned about accesses to a particular variable, you can remove it from consideration by using the ignore subcommand.

You may also consider using one of the following source code annotations, as appropriate.

SCHEME_PROTECTS_DATA

READ_ONLY_DATA

DATA_READABLE_WITHOUT_LOCK

NOW_INVISIBLE_TO_OTHER_THREADS

NOW_VISIBLE_TO_OTHER_THREADS

Lock Management

Source code annotations are an efficient way to refine the assertions you make about the locks in your code. There are three types of assertions: protection, order, and side effects.

Protection assertions state what is protected by a given lock. For example, the following source code annotations can be used to assert how data is protected.

MUTEX_PROTECTS_DATA

RWLOCK_PROTECTS_DATA

SCHEME_PROTECTS_DATA

DATA_READABLE_WITHOUT_LOCK

RWLOCK_COVERS_LOCK

A variation of the assert subcommand is used to assert that a given lock protects some piece of data or a function. Another variation, assert ... covers, asserts that a given lock protects another lock; this is used for hierarchical locking schemes.

Order assertions specify the order in which the given locks must be acquired. The source code annotation LOCK_ORDER or the assert order subcommand can be used to specify lock ordering.

Side effect assertions state that a function has the side effect of releasing or acquiring a given lock. Use the following source code annotations:

MUTEX_ACQUIRED_AS_SIDE_EFFECT

READ_LOCK_ACQUIRED_AS_SIDE_EFFECT

WRITE_LOCK_ACQUIRED_AS_SIDE_EFFECT

LOCK_RELEASED_AS_SIDE_EFFECT

LOCK_UPGRADED_AS_SIDE_EFFECT

LOCK_DOWNGRADED_AS_SIDE_EFFECT

NO_COMPETING_THREADS_AS_SIDE_EFFECT

COMPETING_THREADS_AS_SIDE_EFFECT

You can also use the assert side effect subcommand to specify side effects. In some cases you may want to make side effect assertions about an external function and the lock is not visible from the loaded module. For example, it is static to the module of the external function. In such a case, you can "create" a lock by using a form of the declare subcommand.

Analysis of Lock Usage

LockLint's primary role is to report on lock usage inconsistencies that may lead to data races and deadlocks. The analysis of lock usage occurs when you use the analyze subcommand. The result is a report on the following problems:

• Functions that produce side effects on locks or violate assertions made about side effects on locks. For example, a function that changes the state of a mutex lock from locked to unlocked. The most common unintentional side effect occurs when a function acquires a lock on entry, and then fails to release it at some return point. That path through the function is said to acquire the lock as a side effect. This type of problem may lead to both data races and deadlocks.

• Functions that have inconsistent side effects on locks (that is, different paths through the function) yield different side effects. This may be a limitation of LockLint and a common cause of errors. LockLint cannot handle such functions. It always reports them as errors and does not correctly interpret them. For example, one of the returns from a function may forget to unlock a lock acquired in the function.

• Violations of assertions about which locks should be held upon entry to a function. This problem may lead to a data race.

• Violations of assertions that a lock should be held when a variable is accessed. This problem may lead to a data race.

• Violations of assertions that specify the order in which locks are to be acquired. This problem may lead to a deadlock.

• Failure to use the same, or asserted, mutex lock for all waits on a particular condition variable.

• Miscellaneous problems related to analysis of the source code in relation to assertions and locks.

Post-analysis Queries

After analysis, you can use LockLint subcommands for:

• Finding additional locking inconsistencies.

• Forming appropriate declare, assert, and ignore subcommands. These can be specified after you've restored LockLint's state, prior to rerunning the analysis.

One such subcommand is order, which you can use to make inquiries about the order in which locks have been acquired. This information is particularly useful in understanding lock ordering problems and making assertions about those orders so that LockLint can more accurately diagnose potential deadlocks.

Another such subcommand is vars. The vars subcommand reports which locks are consistently held when a variable is read or written (if any). This information can be useful in determining the protection conventions in code where the original conventions were never documented, or the documentation has become outdated.

Limitations of LockLint

There are limitations to LockLint's analysis. At the root of many of its difficulties is the fact that LockLint doesn't know the values of the program's variables.

LockLint solves some of these problems by ignoring the likely cause or making simplifying assumptions. You can avoid some other problems by using conditionally compiled code in the application. Towards this end, the compiler always defines the preprocessor macro __lock_lint when you compile with the -Zll option. You can use this macro to make your code less ambiguous.

LockLint has trouble deducing:

• Which functions your function pointers point to. There are some assignments LockLint cannot deduce. The declare subcommand can be used to add new possible assignments to the function pointer.
  
  When LockLint sees a call through a function pointer, it tests that call path for every possible value of that function pointer. If you know or suspect that some calling sequences are never executed, use the disallow and reallow subcommands to specify which sequences are executed.

• Whether or not you locked a lock in code like this:

  if (x) pthread_mutex_lock(&lock1);

  
  In this case, two execution paths are created, one holding the lock, and one not holding the lock, which will probably cause the generation of a side effect message at the unlock call. You may be able to work around this problem by using the __lock_lint macro to force LockLint to treat a lock as unconditionally taken. For example:

  #ifdef __lock_lint pthread_mutex_lock(&lock1); #else if (x) pthread_mutex_lock(&lock1); #endif

  LockLint has no problem analyzing code like this:

  if (x) { pthread_mutex_lock(&lock1); foo(); pthread_mutex_unlock(&lock1); }

  In this case, there is only one execution path, along which the lock is acquired and released, causing no side effects.

• Whether or not a lock was acquired in code like this:

  rc = pthread_mutex_trylock(&lock1); if (rc) ...

• Which lock is being locked in code like this:

  pthread_mutex_t* lockp; pthread_mutex_lock(lockp);

  
  In such cases, the lock call is ignored.

• Which variables and locks are being used in code where elements of a structure are used (see Lock Inversions):

struct foo* p; pthread_mutex_lock(p->lock); p->bar = 0;

• Which element of an array is being accessed. This is treated analogously to the previous case; the index is ignored.

• Anything about longjmps.

• When you would exit a loop or break out of a recursion (so it just stops proceeding down a path as soon as it finds itself looping or after one recursion).

Some other LockLint difficulties:

• LockLint only analyzes the use of mutex locks and readers-writer locks. LockLint performs limited consistency checks of mutex locks as used with condition variables. However, semaphores and condition variables are not recognized as locks by LockLint. Even with this analysis, there are limits to what LockLint can make sense of.

• There are situations where LockLint thinks two different variables are the same variable, or that a single variable is two different variables. (See Lock Inversions .)

• It is possible to share automatic variables between threads (via pointers), but LockLint assumes that automatics are unshared, and generally ignores them (the only situation in which they are of interest to LockLint is when they are function pointers).

• LockLint complains about any functions that are not consistent in their side effects on locks. #ifdef's and assertions must be used to give LockLint a simpler view of functions that may or may not have such a side effect.

During analysis, LockLint may produce messages about a lock operation called rw_upgrade. Such a call does not really exist, but LockLint rewrites code like

if (rw_tryupgrade(&lock1)) {    ...     }

as

if () { rw_tryupgrade(&lock1);  ...     }

such that, wherever rw_tryupgrade() occurs, LockLint always assumes it succeeds.

One of the errors LockLint flags is an attempt to acquire a lock that is already held. However, if the lock is unnamed (for example, foo::lock), this error is suppressed, since the name refers not to a single lock but to a set of locks. However, if the unnamed lock always refers to the same lock, use the declare one subcommand so that LockLint can report this type of potential deadlock.

If you have constructed your own locks out of these locks (for example, recursive mutexes are sometimes built from ordinary mutexes), LockLint will not know about them. Generally you can use #ifdef to make it appear to LockLint as though an ordinary mutex is being manipulated. For recursive locks, use an unnamed lock for this deception, since errors won't be generated when it is recursively locked. For example:

void get_lock() {
        #ifdef __lock_lint 
                        struct bogus *p;
                        pthread_mutex_lock(p->lock);
        #else
                        <the real recursive locking code>
        #endif
}

Source Code Annotations

An annotation is some piece of text inserted into your source code. You use annotations to tell LockLint things about your program that it cannot deduce for itself, either to keep it from excessively flagging problems or to have LockLint test for certain conditions. Annotations also serve to document code, in much the same way that comments do. There are two types of source code annotations: assertions and NOTEs.

Annotations are similar to some of the LockLint subcommands described in the command-line summary. In general, it's preferable to use source code annotations over these subcommands, as explained next.

Reasons to Use Source Code Annotations

There are several reasons to use source code annotations. In many cases, such annotations are preferable to using a script of LockLint subcommands.

• Annotations, being mixed in with the code that they describe, are generally better maintained than a script of LockLint subcommands.

• With annotations, you can make assertions about lock state at any point within a function--wherever you put the assertion is where the check occurs. With subcommands, the finest granularity you can achieve is to check an assertion on entry to a function.

• Functions mentioned in subcommands can change. If someone changes the name of a function from func1 to func2, a subcommand mentioning func1 fails (or worse, might work but do the wrong thing, if a different function is given the name func1).

• Some annotations, such as NOTE(NO_COMPETING_THREADS_NOW), have no subcommand equivalents.

• Annotations provide a good way to document your program. In fact, even if you are not using LockLint often, annotations are worthwhile just for this purpose. For example, a header file declaring a variable can document what lock or convention protects the variable, or a function that acquires a lock and deliberately returns without releasing it can have that behavior clearly declared in an annotation.

The Annotations Scheme

LockLint shares the source code annotations scheme with several other tools. When you install the Sun Studio C Compiler, you automatically install the file SUNW_SPRO-cc-ssbd, which contains the names of all the annotations that LockLint understands. The file is located in installation_directory/SUNWspro/prod/lib/note.

You can specify a location other than the default by setting the environment variable NOTEPATH, as in

setenv NOTEPATH other_location:$NOTEPATH

The default value for NOTEPATH is installation_directory/SUNWSPRO/prod/lib/note:/usr/lib/note

To use source code annotations, include the file note.h in your source or header files:

#include <note.h>

Using LockLint NOTEs

Many of the note-style annotations accept names--of locks or variables--as arguments. Names are specified using the syntax shown in .

TABLE 5 Specifying Names With LockLint NOTEs

In C, structure tags and types are kept in separate namespaces, making it possible to have two different structs by the same name as far as LockLint is concerned. When LockLint sees foo::bar, it first looks for a struct with tag foo; if it does not find one, it looks for a type foo and checks that it represents a struct.

However, the proper operation of LockLint requires that a given variable or lock be known by exactly one name. Therefore type will be used only when no tag is provided for the struct, and even then only when the struct is defined as part of a typedef.

For example, Foo would serve as the type name in this example:

typedef struct { int a, b; } Foo;

These restrictions ensure that there is only one name by which the struct is known.

Name arguments do not accept general expressions. It is not valid, for example, to write:

NOTE(MUTEX_PROTECTS_DATA(p->lock, p->a p->b))

However, some of the annotations do accept expressions (rather than names); they are clearly marked.

In many cases an annotation accepts a list of names as an argument. Members of a list should be separated by white space. To simplify the specification of lists, a generator mechanism similar to that of many shells is understood by all annotations taking such lists. The notation for this is:

Prefix{A B ...}Suffix

where Prefix, Suffix, A, B, ... are nothing at all, or any text containing no white space. The above notation is equivalent to:

PrefixASuffix PrefixBSuffix ...

For example, the notation:

struct_tag::{a b c d}

is equivalent to the far more cumbersome text:

struct_tag::a struct_tag::b struct_tag::c struct_tag::d

This construct may be nested, as in:

foo::{a b.{c d} e}

which is equivalent to:

foo::a

foo::b.c

foo::b.d

foo::ae

Where an annotation refers to a lock or another variable, a declaration or definition for that lock or variable should already have been seen.

If a name for data represents a structure, it refers to all non-lock (mutex or readers-writer) members of the structure. If one of those members is itself a structure, then all of its non-lock members are implied, and so on. However, LockLint understands the abstraction of a condition variable and therefore does not break it down into its constituent members.

NOTE and _NOTE

The NOTE interface enables you to insert information for LockLint into your source code without affecting the compiled object code. The basic syntax of a note-style annotation is either:

NOTE(NoteInfo)

or:

_NOTE(NoteInfo)

The preferred use is NOTE rather than _NOTE. Header files that are to be used in multiple, unrelated projects, should use _NOTE to avoid conflicts. If NOTE has already been used, and you do not want to change, you should define some other macro (such as ANNOTATION) using _NOTE. For example, you might define an include file (say, annotation.h) that contains the following:

#define ANNOTATION _NOTE
#include <sys/note.h>

The NoteInfo that gets passed to the NOTE interface must syntactically fit one of the following:

NoteName

NoteName(Args)

NoteName is simply an identifier indicating the type of annotation. Args can be anything, so long as it can be tokenized properly and any parenthesis tokens are matched (so that the closing parenthesis can be found). Each distinct NoteName will have its own requirements regarding arguments.

This text uses NOTE to mean both NOTE and _NOTE, unless explicitly stated otherwise.

Where NOTE May Be Used

NOTE may be invoked only at certain well-defined places in source code:

• At the top level; that is, outside of all function definitions, type and struct definitions, variable declarations, and other constructs. For example:

struct foo { int a, b; mutex_t lock; }; NOTE(MUTEX_PROTECTS_DATA(foo::lock, foo)) bar() {...}

• At the top level within a block, among declarations or statements. Here too, the annotation must be outside of all type and struct definitions, variable declarations, and other constructs. For example:

foo() { ...; NOTE(...) ...; ...; }

• At the top level within a struct or union definition, among the declarations. For example:

struct foo { int a; NOTE(...) int b; };

Where NOTE May Not Be Used

NOTE() may be used only in the locations described above. For example, the following are invalid:

a = b NOTE(...) + 1;

typedef NOTE(...) struct foo Foo;

for (i=0; NOTE(...) i<10; i++) ...

A note-style annotation is not a statement; NOTE() may not be used inside an if/else/for/while body unless braces are used to make a block. For example, the following causes a syntax error:

if (x) NOTE(...)

How Data Is Protected

The following annotations are allowed both outside and inside a function definition. Remember that any name mentioned in an annotation must already have been declared.

NOTE(MUTEX_PROTECTS_DATA(Mutex, DataNameList))

NOTE(RWLOCK_PROTECTS_DATA(Rwlock, DataNameList))

NOTE(SCHEME_PROTECTS_DATA("description", DataNameList))

The first two annotations tell LockLint that the lock should be held whenever the specified data is accessed.

The third annotation, SCHEME_PROTECTS_DATA, describes how data are protected if it does not have a mutex or readers-writer lock. The description supplied for the scheme is simply text and is not semantically significant; LockLint responds by ignoring the specified data altogether. You may make description anything you like.

Some examples help show how these annotations are used. The first example is very simple, showing a lock that protects two variables:

mutex_t lock1;
int a,b;
NOTE(MUTEX_PROTECTS_DATA(lock1, a b))

In the next example, a number of different possibilities are shown. Some members of struct foo are protected by a static lock, while others are protected by the lock on foo. Another member of foo is protected by some convention regarding its use.

mutex_t lock1;
struct foo {
        mutex_t lock;
        int mbr1, mbr2;
        struct {
                int mbr1, mbr2;
                char* mbr3;
        } inner;
        int mbr4;
};
NOTE(MUTEX_PROTECTS_DATA(lock1, foo::{mbr1 inner.mbr1}))
NOTE(MUTEX_PROTECTS_DATA(foo::lock, foo::{mbr2 inner.mbr2}))
NOTE(SCHEME_PROTECTS_DATA("convention XYZ", inner.mbr3))

A datum can only be protected in one way. If multiple annotations about protection (not only these three but also READ_ONLY_DATA) are used for a single datum, later annotations silently override earlier annotations. This allows for easy description of a structure in which all but one or two members are protected in the same way. For example, most of the members of struct BAR below are protected by the lock on struct foo, but one is protected by a global lock.

mutex_t lock1;
typedef struct {
        int mbr1, mbr2, mbr3, mbr4;
} BAR;
NOTE(MUTEX_PROTECTS_DATA(foo::lock, BAR))
NOTE(MUTEX_PROTECTS_DATA(lock1, BAR::mbr3))

Read-Only Variables

NOTE(READ_ONLY_DATA(DataNameList))

This annotation is allowed both outside and inside a function definition. It tells LockLint how data should be protected. In this case, it tells LockLint that the data should only be read, and not written.

Note - No error is signaled if read-only data is written while it is considered invisible. Data is considered invisible when other threads cannot access it; for example, if other threads do not know about it.

This annotation is often used with data that is initialized and never changed thereafter. If the initialization is done at runtime before the data is visible to other threads, use annotations to let LockLint know that the data is invisible during that time.

LockLint knows that const data is read-only.

Allowing Unprotected Reads

NOTE(DATA_READABLE_WITHOUT_LOCK(DataNameList))

This annotation is allowed both outside and inside a function definition. It informs LockLint that the specified data may be read without holding the protecting locks. This is useful with an atomically readable datum that stands alone (as opposed to a set of data whose values are used together), since it is valid to peek at the unprotected data if you do not intend to modify it.

Hierarchical Lock Relationships

NOTE(RWLOCK_COVERS_LOCKS(RwlockName, LockNameList))

This annotation is allowed both outside and inside a function definition. It tells LockLint that a hierarchical relationship exists between a readers-writer lock and a set of other locks. Under these rules, holding the cover lock for write access affords a thread access to all data protected by the covered locks. Also, a thread must hold the cover lock for read access whenever holding any of the covered locks.

Using a readers-writer lock to cover another lock in this way is simply a convention; there is no special lock type. However, if LockLint is not told about this coverage relationship, it assumes that the locks are being used according to the usual conventions and generates error messages.

The following example specifies that member lock of unnamed foo structures covers member lock of unnamed bar and zot structures:

NOTE(RWLOCK_COVERS_LOCKS(foo::lock, {bar zot}::lock))

Functions With Locking Side Effects

NOTE(MUTEX_ACQUIRED_AS_SIDE_EFFECT(MutexExpr))

NOTE(READ_LOCK_ACQUIRED_AS_SIDE_EFFECT(RwlockExpr))

NOTE(WRITE_LOCK_ACQUIRED_AS_SIDE_EFFECT(RwlockExpr))

NOTE(LOCK_RELEASED_AS_SIDE_EFFECT(LockExpr))

NOTE(LOCK_UPGRADED_AS_SIDE_EFFECT(RwlockExpr))

NOTE(LOCK_DOWNGRADED_AS_SIDE_EFFECT(RwlockExpr))

NOTE(NO_COMPETING_THREADS_AS_SIDE_EFFECT)

NOTE(COMPETING_THREADS_AS_SIDE_EFFECT)

These annotations are allowed only inside a function definition. Each tells LockLint that the function has the specified side effect on the specified lock--that is, that the function deliberately leaves the lock in a different state on exit than it was in when the function was entered. In the case of the last two of these annotations, the side effect is not about a lock but rather about the state of concurrency.

When stating that a readers-writer lock is acquired as a side effect, you must specify whether the lock was acquired for read or write access.

A lock is said to be upgraded if it changes from being acquired for read-only access to being acquired for read/write access. Downgraded means a transformation in the opposite direction.

LockLint analyzes each function for its side effects on locks (and concurrency). Ordinarily, LockLint expects that a function will have no such effects; if the code has such effects intentionally, you must inform LockLint of that intent using annotations. If it finds that a function has different side effects from those expressed in the annotations, an error message results.

The annotations described in this section refer generally to the function's characteristics and not to a particular point in the code. Thus, these annotations are probably best written at the top of the function. There is, for example, no difference (other than readability) between this:

foo() {
        NOTE(MUTEX_ACQUIRED_AS_SIDE_EFFECT(lock_foo))
        ...
        if (x && y) {
                ...
        }
}

and this:

foo() {
        ...
        if (x && y) {
        NOTE(MUTEX_ACQUIRED_AS_SIDE_EFFECT(lock_foo))
                ...
        }
}

If a function has such a side effect, the effect should be the same on every path through the function. LockLint complains about and refuses to analyze paths through the function that have side effects other than those specified.

Single-Threaded Code

NOTE(COMPETING_THREADS_NOW)

NOTE(NO_COMPETING_THREADS_NOW)

These two annotations are allowed only inside a function definition. The first annotation tells LockLint that after this point in the code, other threads exist that might try to access the same data that this thread will access. The second function specifies that this is no longer the case; either no other threads are running or whatever threads are running will not be accessing data that this thread will access. While there are no competing threads, LockLint does not complain if the code accesses data without holding the locks that ordinarily protect that data.

These annotations are useful in functions that initialize data without holding locks before starting up any additional threads. Such functions may access data without holding locks, after waiting for all other threads to exit. So one might see something like this:

main() {
        <initialize data structures>
        NOTE(COMPETING_THREADS_NOW)
        <create several threads>
        <wait for all of those threads to exit>
        NOTE(NO_COMPETING_THREADS_NOW)
        <look at data structures and print results>
}

Note - If a NOTE is present in main(), LockLint assumes that when main() starts, no other threads are running. If main() does not include a NOTE, LockLint does not assume that no other threads are running.

LockLint does not issue a warning if, during analysis, it encounters a COMPETING_THREADS_NOW annotation when it already thinks competing threads are present. The condition simply nests. No warning is issued because the annotation may mean different things in each use (that is the notion of which threads compete may differ from one piece of code to the next). On the other hand, a NO_COMPETING_THREADS_NOW annotation that does not match a prior COMPETING_THREADS_NOW (explicit or implicit) causes a warning.

Unreachable Code

NOTE(NOT_REACHED)

This annotation is allowed only inside a function definition. It tells LockLint that a particular point in the code cannot be reached, and therefore LockLint should ignore the condition of locks held at that point. This annotation need not be used after every call to exit(), for example, as the lint annotation /* NOTREACHED */ is used. Simply use it in definitions for exit() and the like (primarily in LockLint libraries), and LockLint will determine that code following calls to such functions is not reached. This annotation should seldom appear outside LockLint libraries. An example of its use (in a LockLint library) would be:

exit(int code) { NOTE(NOT_REACHED) }

Lock Order

NOTE(LOCK_ORDER(LockNameList))

This annotation, which is allowed either outside or inside a function definition, specifies the order in which locks should be acquired. It is similar to the assert order and order subcommands. See the command summary at the end of this article.

To avoid deadlocks, LockLint assumes that whenever multiple locks must be held at once they are always acquired in a well-known order. If LockLint has been informed of such ordering using this annotation, an informative message is produced whenever the order is violated.

This annotation may be used multiple times, and the semantics will be combined appropriately. For example, given the annotations

NOTE(LOCK_ORDER(a b c))

NOTE(LOCK_ORDER(b d))

LockLint will deduce the ordering:

NOTE(LOCK_ORDER(a d))

It is not possible to deduce anything about the order of c with respect to d in this example.

If a cycle exists in the ordering, an appropriate error message will be generated.

Variables Invisible to Other Threads

NOTE(NOW_INVISIBLE_TO_OTHER_THREADS(DataExpr, ...))

NOTE(NOW_VISIBLE_TO_OTHER_THREADS(DataExpr, ...))

These annotations, which are allowed only within a function definition, tell LockLint whether or not the variables represented by the specified expressions are visible to other threads; that is, whether or not other threads could access the variables.

Another common use of these annotations is to inform LockLint that variables it would ordinarily assume are visible are in fact not visible, because no other thread has a pointer to them. This frequently occurs when allocating data off the heap--you can safely initialize the structure without holding a lock, since no other thread can yet see the structure.

Foo* p = (Foo*) malloc(sizeof(*p));
NOTE(NOW_INVISIBLE_TO_OTHER_THREADS(*p))
p->a = bar;
p->b = zot;
NOTE(NOW_VISIBLE_TO_OTHER_THREADS(*p))
add_entry(&global_foo_list, p);

Calling a function never has the side effect of making variables visible or invisible. Upon return from the function, all changes in visibility caused by the function are reversed.

Assuming Variables Are Protected

NOTE(ASSUMING_PROTECTED(DataExpr, ...))

This annotation, which is allowed only within a function definition, tells LockLint that this function assumes that the variables represented by the specified expressions are protected in one of the following ways:

• The appropriate lock is held for each variable

• The variables are invisible to other threads

• There are no competing threads when the call is made

LockLint issues an error if none of these conditions is true.

f(Foo* p, Bar* q) {
        NOTE(ASSUMING_PROTECTED(*p, *q))
        p->a++;
        ...
}

Assertions Recognized by LockLint

LockLint recognizes some assertions as relevant to the state of threads and locks. (For more information, see the assert man page.)

Assertions may be made only within a function definition, where a statement is allowed.

Note - ASSERT() is used in kernel and driver code, whereas assert() is used in user (application) code. For simplicity's sake, this document uses assert() to refer to either one, unless explicitly stated otherwise.

Making Sure All Locks Are Released

assert(NO_LOCKS_HELD);

LockLint recognizes this assertion to mean that, when this point in the code is reached, no locks should be held by the thread executing this test. Violations are reported during analysis. A routine that blocks might want to use such an assertion to ensure that no locks are held when a thread blocks or exits.

The assertion also clearly serves as a reminder to someone modifying the code that any locks acquired must be released at that point.

It is really only necessary to use this assertion in leaf-level functions that block. If a function blocks only inasmuch as it calls another function that blocks, the caller need not contain this assertion as long as the callee does. Therefore this assertion probably sees its heaviest use in versions of libraries (for example, libc) written specifically for LockLint (like lint libraries).

The file synch.h defines NO_LOCKS_HELD as 1 if it has not already been otherwise defined, causing the assertion to succeed; that is, the assertion is effectively ignored at runtime. You can override this default runtime meaning by defining NO_LOCKS_HELD before you include either note.h or synch.h (which may be included in either order). For example, if a body of code uses only two locks called a and b, the following definition would probably suffice:

#define NO_LOCKS_HELD (!MUTEX_HELD(&a) && !MUTEX_HELD(&b))
#include <note.h>
#include <synch.h>

Doing so does not affect LockLint's testing of the assertion; that is, LockLint still complains if any locks are held (not just a or b).

Making Sure No Other Threads Are Running

assert(NO_COMPETING_THREADS);

LockLint recognizes this assertion to mean that, when this point in the code is reached, no other threads should be competing with the one running this code. Violations (based on information provided by certain NOTE-style assertions) are reported during analysis. Any function that accesses variables without holding their protecting locks (operating under the assumption that no other relevant threads are out there touching the same data), should be so marked.

By default, this assertion is ignored at runtime--that is, it always succeeds. No generic runtime meaning for NO_COMPETING_THREADS is possible, since the notion of which threads compete involves knowledge of the application. For example, a driver might make such an assertion to say that no other threads are running in this driver for the same device. Because no generic meaning is possible, synch.h defines NO_COMPETING_THREADS as 1 if it has not already been otherwise defined.

However, you can override the default meaning for NO_COMPETING_THREADS by defining it before including either note.h or synch.h (which may be included in either order). For example, if the program keeps a count of the number of running threads in a variable called num_threads, the following definition might suffice:

#define NO_COMPETING_THREADS (num_threads == 1)
#include <note.h>
#include <synch.h>

Doing so does not affect LockLint's testing of the assertion.

Asserting Lock State

assert(MUTEX_HELD(lock_expr) && ...);

This assertion is widely used within the kernel. It performs runtime checking if assertions are enabled. The same capability exists in user code.

This code does roughly the same thing during LockLint analysis as it does when the code is actually run with assertions enabled; that is, it reports an error if the executing thread does not hold the lock as described.

Note - The thread library performs a weaker test, only checking that some thread holds the lock. LockLint performs the stronger test.

LockLint recognizes the use of MUTEX_HELD(), RW_READ_HELD(), RW_WRITE_HELD(), and RW_LOCK_HELD() macros, and negations thereof. Such macro calls may be combined using the && operators. For example, the following assertion causes LockLint to check that a mutex is not held and that a readers-writer lock is write-held:

assert(p && !MUTEX_HELD(&p->mtx) && RW_WRITE_HELD(&p->rwlock));

LockLint also recognizes expressions like:

MUTEX_HELD(&foo) == 0

LockLint Command Reference

Subcommand Summary

TABLE A-1 contains a summary of LockLint subcommands.

TABLE A-1 LockLint Subcommands

Many LockLint subcommands require you to specify names of locks, variables, pointers, and functions. In C, it is possible for names to be ambiguous. See LockLint Naming Conventions for details on specifying names to LockLint subcommands.

TABLE A-2 lists the exit status values of LockLint subcommands.

TABLE A-2 Exit Status Values of LockLint Subcommands

LockLint Naming Conventions

Many LockLint subcommands require you to specify names of locks, variables, pointers, and functions. In C, it is possible for names to be ambiguous; for example, there may be several variables named foo, one of them extern and others static.

The C language does not provide a way of referring to ambiguously named variables that are hidden by the scoping rules. In LockLint, however, a way of referring to such variables is needed. Therefore, every symbol in the code being analyzed is given a formal name, a name that LockLint uses when referring to the symbol. Table A-3 lists some examples of formal names for a function.

TABLE A-3 Sample Formal Function Names

Table A-4 lists the formal names for a variable, depending on its use as a lock, a pointer, or an actual variable.

TABLE A-4 Sample Formal Variable Names

In addition, any of these may be followed by an arbitrary number of .mbr specifications to denote members of a structure.

Table A-5 contains some examples of the LockLint naming scheme.

TABLE A-5 LockLint Naming Scheme Examples

While LockLint refers to symbols in this way, you are not required to. You may use as little of the name as is required to unambiguously identify it. For example, you could refer to zot.c:foo/bar as foo/bar as long as there is only one function foo defining a variable bar. You can even refer to it simply as bar as long as there is no other variable by that name.

C allows the programmer to declare a structure without assigning it a tag. When you use a pointer to such a structure, LockLint must make up a tag by which to refer to the structure. It generates a tag of the format filename@line_number. For example, if you declare a structure without a tag at line 42 of file foo.c, and then refer to member bar of an instance of that structure using a pointer, as in:

typedef struct { ... } foo;
foo *p;
func1() { p->bar = 0; }

LockLint sees that as a reference to foo.c@42::bar.

Because members of a union share the same memory location, LockLint treats all members of a union as the same variable. This is accomplished by using a member name of % regardless of which member is accessed. Since bit fields typically involve sharing of memory between variables, they are handled similarly: % is used in place of the bit field member name.

When you list locks and variables, you are only seeing those locks and variables that are actually used within the code represented by the .ll files. No information is available from LockLint on locks, variables, pointers, and functions that are declared but not used. Likewise, no information is available for accesses through pointers to simple types, such as this one:

int *ip = &i;
*ip = 0;

When simple names (for example, foo) are used, there is the possibility of conflict with keywords in the subcommand language. Such conflicts can be resolved by surrounding the word with double quotes, but remember that you are typing commands to a shell, and shells typically consume the outermost layer of quotes. Therefore you have to escape the quotes, as in this example:

% lock_lint ignore foo in func \"func\"

If two files with the same base name are included in an analysis, and these two files contain static variables by the same name, confusion can result. LockLint thinks the two variables are the same.

If you duplicate the definition for a struct with no tag, LockLint does not recognize the definitions as the same struct. The problem is that LockLint makes up a tag based on the file and line number where the struct is defined (such as x.c@24), and that tag differs for the two copies of the definition.

If a function contains multiple automatic variables of the same name, LockLint cannot tell them apart. Because LockLint ignores automatic variables except when they are used as function pointers, this does not come up often. In the following code, for example, LockLint uses the name :foo/fp for both function pointers:

int foo(void (*fp)()) {
  (*fp)();
  {
      void (*fp)() = get_func();
      (*fp)();
      ...

LockLint Subcommands

Some of these are equivalent to subcommands such as assert. Source code annotations are often preferable to subcommands, because they

• Have finer granularity

• Are easy to maintain

• Serve as comments on the code in question

analyze [-hv]

Analyzes the loaded files for lock inconsistencies that may lead to data races and deadlocks. This subcommand may produce a great deal of output, so you may want to redirect the output to a file. This subcommand can be run only once for each saved state.

-h (history) produces detailed information for each phase of the analysis. No additional errors are issued.

-v (verbose) generates additional messages during analysis:

• Writable variable read while no locks held!

• Variable written while no locks held!

• No lock consistently held while accessing variable!

Output from the analyze subcommand can be particularly abundant if:

• The code has not been analyzed before

• The assert read only subcommand was not used to identify read-only variables

• No assertions were made about the protection of writable variables

The output messages are likely to reflect situations that are not real problems; therefore, it is often helpful to first analyze the code without the -v option, to show only the messages that are likely to represent real problems.

LockLint analyze Phases

Each problem encountered during analysis is reported on one or more lines, the first of which begins with an asterisk. Where possible, LockLint provides a complete traceback of the calls taken to arrive at the point of the problem. The analysis goes through the following phases:

1. Checking for functions with variable side effects on locks
   
   If a disallow sequence specifies that a function with locking side effects should not be analyzed, LockLint produces incorrect results. If such disallow sequences are found, they are reported and analysis does not proceed.

2. Preparing locks to hold order info
   
   LockLint processes the asserted lock order information available to it. If LockLint detects a cycle in the asserted lock order, the cycle is reported as an error.

3. Checking for function pointers with no targets
   
   LockLint cannot always deduce assignments to function pointers. During this phase, LockLint reports any function pointer for which it does not think there is at least one target, whether deduced from the source or declared a func.ptr target.

4. Removing accesses to ignored variables
   
   To improve performance, LockLint removes references to ignored variables at this point. (This affects the output of the vars subcommands.)

5. Preparing functions for analysis
   
   During this phase, LockLint determines what side effects each function has on locks. (A side effect is a change in a lock's state that is not reversed before returning.) An error results if:

   • The side effects do not match what LockLint expects

   • The side effects are different depending upon the path taken through the function

   • A function with such side effects is recursive

   LockLint expects that a function will have no side effects on locks, except where side effects have been added using the assert side effect subcommand.

6. Preparing to recognize calling sequences to allow/disallow subcommands that were issued, if any. No errors or warnings are reported.
   
   Here, LockLint is processing the various allow/disallow subcommands that were issued, if any. No errors or warnings are reported.

7. Checking locking side effects in function pointer targets
   
   Calls through function pointers may target several functions. All functions that are targets of a particular function pointer must have the same side effects on locks (if any). If a function pointer has targets that differ in their side effects, analysis does not proceed.

8. Checking for consistent use of locks with condition variables

   Here LockLint checks that all waits on a particular condition variable use the same mutex. Also, if you assert that particular lock to protect that condition variable, LockLint makes sure you use that lock when waiting on the condition variable.

9. Determining locks consistently held when each function is entered

   During this phase, LockLint reports violations of assertions that locks should be held upon entry to a function (see assert subcommand). Errors such as locking a mutex lock that is already held, or releasing a lock that is not held, are also reported. Locking an anonymous lock, such as foo::lock, more than once is not considered an error, unless the declare one command has been used to indicate otherwise.

10. Determining locks consistently held when each variable is accessed
    
    During this phase, LockLint reports violations of assertions that a lock should be held when a variable is accessed (see the assert subcommand). Also, any writes to read-only variables are reported.
    
    Occasionally you may get messages that certain functions were never called. This can occur if a set of functions (none of which are root functions) call each other. If none of the functions is called from outside the set, LockLint reports that the functions were never called at all. The declare root subcommand can be used to fix this situation for a subsequent analysis.
    
    Using the disallow subcommand to disallow all sequences that reach a function will also cause a message that the function is never called.

Once the analysis is done, you can find still more potential problems in the output of the vars and order subcommands.

assert has the following syntax:

assert side effect	mutex	acquired in	func ...
assert side effect	rwlock [read]	acquired in	func ...
assert side effect	lock	released in	func ...
assert side effect	rwlock	upgraded in	func ...
assert side effect	rwlock	downgraded in	func ...
assert mutex|rwlock	protects		var ...
assert mutex	protects		func ...
assert rwlock	protects	[reads in]	func ...
assert order			lock lock ...
assert read only			var ...
assert rwlock	covers		lock ...

These subcommands tell LockLint how the programmer expects locks and variables to be accessed and modified in the application being checked. During analysis any violations of such assertions are reported.


Note - If a variable is asserted more than once, only the last assert takes effect.

assert side effect

side effect is a change made by a function in the state of a lock, a change that is not reversed before the function returns. If a function contains locking side effects and no assertion is made about the side effects, or the side effects differ from those that are asserted, a warning is issued during the analysis. The analysis then continues as if the unexpected side effect never occurred.


Note - There is another kind of side effect called an inversion. See the locks or funcs subcommands for more details.

Warnings are also issued if the side effects produced by a function could differ from call to call (for example, conditional side effects). The keywords acquired in, released in, upgraded in, and downgraded in describe the type of locking side effect being asserted about the function. The keywords correspond to the side effects available via the threads library interfaces and the DDI and DKI Kernel Functions (see mutex(3T), rwlock(3T), mutex(9F) and rwlock(9F)).

The side effect assertion for rwlocks takes an optional argument read; if read is present, the side effect is that the function acquires read-level access for that lock. If read is not present, the side effect specifies that the function acquires write-level access for that lock.

assert mutex|rwlock protects

Asserting that a mutex lock protects a variable causes an error whenever the variable is accessed without holding the mutex lock. Asserting that a readers-writer lock protects a variable causes an error whenever the variable is read without holding the lock for read access or written without holding the lock for write access. Subsequent assertions as to which lock protects a variable override any previous assertions; that is, only the last lock asserted to protect a variable is used during analysis.

assert mutex protects

Asserting that a mutex lock protects a function causes an error whenever the function is called without holding the lock. For root functions, the analysis is performed as if the root function were called with this assertion being true.

assert rwlock protects

Asserting that a readers-writer lock protects a function causes an error whenever the function is called without holding the lock for write access. Asserting that a readers-writer lock protects reads in a function causes an error whenever the function is called without holding the lock for read access. For root functions, the analysis is performed as if the root function were called with this assertion being true.


Note - To avoid flooding the output with too many violations of a single assert... protects subcommand, a maximum of 20 violations of any given assertion is shown. This limit does not apply to the assert order subcommand.

assert order

Informs LockLint of the order in which locks should be acquired. That is, LockLint assumes that the program avoids deadlocks by adhering to a well-known lock order. Using this subcommand, you can make LockLint aware of the intended order so that violations of the order can be printed during analysis.

assert read only

States that the given set of variables should never be written by the application; LockLint reports any writes to the variables. Unless a variable is read-only, reading the variable while no locks are held will elicit an error since LockLint assumes that the variable could be written by another thread at the same time.

assert rwlock covers

Informs LockLint of the existence of a hierarchical locking relationship. A readers-writer lock may be used in conjunction with other locks (mutex or readers-writer) in the following way to increase performance in certain situations:

• , must be held while any of a set of other covered locks is held. That is, it is illegal (under these conventions) to hold a covered lock while not also holding the cover, with at least read access.

• While holding the cover for write access, you can access any variable protected by one of the covered locks without holding the covered lock. This works because it is impossible for another thread to hold the covered lock (since it would also have to be holding the cover). The time saved by not locking the covered locks can increase performance if there is not excessive contention over the cover.

Using assert rwlock covers prevents LockLint from issuing error messages when a thread accesses variables while holding the cover for write access but not the covered lock. It also enables checks to ensure that a covered lock is never held when its cover is not.

declare has the following syntax:

declare	mutex	mutex . . .
declare	rwlocks	rwlock ...
declare	func_ptr	targets	func ...
declare	nonreturning	func ...
declare	one	tag ...
declare	readable	var ...
declare	root	func ...

These subcommands tell LockLint things that it cannot deduce from the source presented to it.

declare mutex mutex
declare rwlocks rwlock

These subcommands (along with declare root, below) are typically used when analyzing libraries without a supporting harness. The subcommands declare mutex and declare rwlocks create mutex and reader-writer locks of the given names. These symbols can be used in subsequent assert subcommands.

declare func_ptr targets func

Adds the specified functions to the list of functions that could be called through the specified function pointer.

LockLint manages to gather a good deal of information about function pointer targets on its own by watching initialization and assignments. For example, for the code

struct foo { int (*fp)(); } foo1 = { bar };

LockLint does the equivalent of the command

% lock_lint declare foo::fp targets bar

% lock_lint declare foo1.fp targets bar

declare nonreturning func

Tells LockLint that the specified functions do not return. LockLint will not give errors about lock state after calls to such functions.

declare one tag

Tells LockLint that only one unnamed instance exists of each structure whose tag is specified. This knowledge makes it possible for LockLint to give an error if a lock in that structure is acquired multiple times without being released. Without this knowledge, LockLint does not complain about multiple acquisitions of anonymous locks (for example, foo::lock), since two different instances of the structure could be involved.

declare readable var

Tells LockLint that the specified variables may be safely read without holding any lock, thus suppressing the errors that would ordinarily occur for such unprotected reads.

declare root func

Tells LockLint to analyze the given functions as a root function; by default, if a function is called from any other function, LockLint does not attempt to analyze that function as the root of a calling sequence.

A root function is a starting point for the analysis; functions that are not called from within the loaded files are naturally roots. This includes, for example, functions that are never called directly but are the initial starting point of a thread (for example, the target function of a thread_create call). However, a function that is called from within the loaded files might also be called from outside the loaded files, in which case you should use this subcommand to tell LockLint to use the function as a starting point in the analysis.

disallow has the following syntax:

disallow func ...

Tells LockLint that the specified calling sequence should not be analyzed. For example, to prevent LockLint from analyzing any calling sequence in which f() calls g() calls h(), use the subcommand

% lock_lint disallow f g h

Function pointers can make a program appear to follow many calling sequences that do not in practice occur. Bogus locking problems, particularly deadlocks, can appear in such sequences. disallow prevents LockLint from following such sequences.

disallows has the following syntax:

disallows

Lists the calling sequences that are disallowed by the disallow subcommand.

There is no exit subcommand for LockLint. To exit LockLint, use the exit command for the shell you are using.

files has the following syntax:

files

Lists the .ll versions of the source code files loaded with the load subcommand.

funcptrs has the following syntax:

funcptrs [-botu] func_ptr ... funcptrs [-blotuz]

Lists information about the function pointers used in the loaded files. One line is produced for each function pointer.

TABLE A-6 funcptrs Options

Option	Definition
-b	(bound) This option lists only function pointers to which function targets have been bound, that is it suppresses the display of function pointers for which there are no bound targets.
-l	(long) Equivalent to -ot.
-o	(other) This presents the following information about each function pointer:
	Calls=#	Indicates the number of places in the loaded files this function pointer is used to call a function.
	=nonreturning	Indicates that a call through this function pointer never returns (none of the functions targeted ever return).
-t	(targets) This option lists the functions currently bound as targets to each function pointer listed, as follows: targets={ func ... }
-u	(unbound) This lists only those function pointers to which no function targets are bound. That is, suppresses the display of function pointers for which there are bound targets.
-z	(zero) This lists function pointers for which there are no calls. Without this option information is given only on function pointers through which calls are made.

You can combine various options to funcptrs:

• This example lists information about the specified function pointers. By default, this variant of the subcommand gives all the details about the function pointers, as if -ot had been specified.

  funcptrs [-botu] func_ptr ...

• This example lists information about all function pointers through which calls are made. If -z is used, even function pointers through which no calls are made are listed.

  funcptrs [-blotuz]

has the following syntax:

funcs [-adehou]			func ...
funcs [-adehilou]	[directly]
funcs [-adehlou]	[directly]	called by	func ...
funcs [-adehlou]	[directly]	calling	func ...
funcs [-adehlou]	[directly]	reading	var ....
funcs [-adehlou]	[directly]	writing	var ...
funcs [-adehlou]	[directly]	accessing	var ...
funcs [-adehlou]	[directly]	affecting	lock ...
funcs [-adehlou]	[directly]	inverting	lock ...

funcs lists information about the functions defined and called in the loaded files. Exactly one line is printed for each function.

TABLE A-7 funcs Options

Option	Definition
-a	(asserts) This option shows information about which locks are supposed to be held on entry to each function, as set by the assert subcommand. When such assertions have been made, they show as: asserts={ lock ... } read_asserts={ lock ... } An asterisk appears before the name of any lock that was not consistently held upon entry (after analysis).
-e	(effects) This option shows information about the side effects each function has on locks (for example, "acquires mutex lock foo"). If a function has such side effects, they are shown as: side_effects={ effect [, effect] ... } Using this option prior to analysis shows side effects asserted by an assert side effect subcommand. After analysis, information on side effects discovered during the analysis is also shown.
-d	(defined) This option shows only those functions that are defined in the loaded files. That is, that it suppresses the display of undefined functions.
-h	(held) This option shows information about which locks were consistently held when the function was called (after analysis). Locks consistently held for read (or write) on entry show as: held={ lock ... }+{ lock ... } read_held={ lock ... }+{ lock ... } The first list in each set is the list of locks consistently held when the function was called; the second is a list of inconsistently held locks--locks that were sometimes held when the function was called, but not every time.
-i	(ignored) This option lists ignored functions.
-l	(long) Equivalent to -aeoh.
-o	(other) This option causes LockLint to present, where applicable, the following information about each function
	=ignored	Indicates that LockLint has been told to ignore the function using the ignore subcommand.
	=nonreturning	Indicates that a call through this function never returns (none of the functions targeted ever return).
	=rooted	Indicates that the function was made a root using the declare root subcommand.
	=root	Indicates that the function is naturally a root (is not called by any function).
	=recursive	Indicates that the function makes a call to itself.
	=unanalyzed	Indicates that the function was never called during analysis (and is therefore unanalyzed). This differs from =root in that this can happen when foo calls bar and bar calls foo, and no other function calls either foo or bar, and neither have been rooted (see =rooted). So, because foo and bar are not roots, and they can never be reached from any root function, they have not been analyzed.
	calls=#	Indicates the number of places in the source code, as represented by the loaded files, where this function is called. These calls may not actually be analyzed; for example, a disallow subcommand may prevent a call from ever really taking place.
-u	(undefined) This option shows only those functions that are undefined in the loaded files.

funcs [-adehou] func ...

Lists information about individual functions. By default, this variant of the subcommand gives all the details about the functions, as if -aeho had been specified.

funcs [-adehilou]

Lists information about all functions that are not ignored. If -i is used, even ignored functions are listed.

funcs [-adehlou] [directly] called by func ...

Lists only those functions that may be called as a result of calling the specified functions. If directly is used, only those functions called by the specified functions are listed. If directly is not used, any functions those functions called are also listed, and so on.

funcs [-adehlou] [directly] calling func ...

Lists only those functions that, when called, may result in one or more of the specified functions being called. See notes below on directly.

funcs [-adehlou] [directly] reading var ...

Lists only those functions that, when called, may result in one or more of the specified variables being read. See notes below on directly.

funcs [-adehlou] [directly] writing var ...

Lists only those functions that, when called, may result in one or more of the specified variables being written. See notes below on directly.

funcs [-adehlou] [directly] accessing var ...

Lists only those functions that, when called, may result in one or more of the specified variables being accessed (read or written). See notes below on directly.

funcs [-adehlou] [directly] affecting lock ...

Lists only those functions that, when called, may result in one or more of the specified locks being affected (acquired, released, upgraded, or downgraded). See notes below on directly.

funcs [-adehlou] [directly] inverting lock ...

Lists only those functions that invert one or more of the specified locks. If directly is used, only those functions that themselves invert one or more of the locks (actually release them) are listed. If directly is not used, any function that is called with a lock already held, and then calls another function that inverts the lock, is also listed, and so on.

For example, in the following code, f3() directly inverts lock m, and f2() indirectly inverts it:

f1() { pthread_mutex_unlock(&m); f2(); pthread_mutex_lock(&m); } f2() { f3(); } f3() { pthread_mutex_unlock(&m); pthread_mutex_lock(&m); }

About directly

Except where stated otherwise, variants that allow the keyword directly only list the functions that themselves fit the description. If directly is not used, all the functions that call those functions are listed, and any functions that call those functions, and so on.

has the following syntax:

help [keyword]

Without a keyword, help displays the subcommand set.

With a keyword, help gives helpful information relating to the specified keyword. The keyword may be the first word of any LockLint subcommand. There are also a few other keywords for which help is available:

condvars locking example makefile ifdef names inversions overview limitations shell

If environment variable PAGER is set, that program is used as the pager for help. If PAGER is not set, more is used.

has the following syntax:

ignore func|var ... [ in func ... ]

Tells LockLint to exclude certain functions and variables from the analysis. This exclusion may be limited to specific functions using the in func ... clause; otherwise the exclusion applies to all functions.

The commands

% lock_lint funcs -io | grep =ignored % lock_lint vars -io | grep =ignored

show which functions and variables are ignored.

has the following syntax:

load file ...

Loads the specified .ll files. The extension may be omitted, but if an extension is specified, it must be .ll. Absolute and relative paths are allowed. You are talking to a shell, so the following are perfectly legal (depending upon your shell's capabilities):

% lock_lint load *.ll % lock_lint load ../foo/abcdef{1,2} % lock_lint load `find . -name \*.ll -print`

The text for load is changed extensively. To set the new text, type:

% lock_lint help load

has the following syntax:

locks [-co] lock ... locks [-col] locks [-col] [directly] affected by func ... locks [-col] [directly] inverted by func ...

Lists information about the locks of the loaded files. Only those variables that are actually used in lock manipulation routines are shown; locks that are simply declared but never manipulated are not shown.

TABLE A-8 locks Options

Option	Definition
-c	(cover) This option shows information about lock hierarchies. Such relationships are described using the assert rwlock covers subcommand. (When locks are arranged in such a hierarchy, the covering lock must be held, at least for read access, whenever any of the covered locks is held. While holding the covering lock for write access, it is unnecessary to acquire any of the covered locks.) If a lock covers other locks, those locks show as covered={ lock ... } If a lock is covered by another lock, the covering lock shows as cover=lock
-l	(long) Equivalent to -co.
-o	(other) Causes the type of the lock to be shown as (type) where type is mutex, rwlock, or ambiguous type [used as a mutex in some places and as a rwlock (readers-writer) in other places].

locks [-co] lock ...

Lists information about individual locks. By default, this variant of the subcommand gives all the details about the locks, as if -co had been specified.

locks [-col]

Lists information about all locks.

locks [-col] [directly] affected by func ...

Lists only those locks that may be affected (acquired, released, upgraded, or downgraded) as a result of calling the specified functions. If the keyword directly is used, only functions that use the threads library routines directly to affect a lock (acquire, release, upgrade, or downgrade) are listed. If the keyword directly is not used, any function that calls a function that affects a lock will be listed, and any function calling that function are listed, and so on.

locks [-col] [directly] inverted by func ...

Lists only those locks that may be inverted by calling one of the specified functions.

If the keyword directly is used, only those locks that are directly inverted by the specified functions (that is, the functions that actually release and reacquire locks using a threads library routine) are listed. If the keyword directly is not used, a lock that is held by one of the specified functions and inverted by some function called from it (and so on) is also listed. For example, in the following code f1 directly inverts m1, and indirectly inverts m2.

f1() { pthread_mutex_unlock(&m1); f2(); pthread_mutex_lock(&m1); } f2() { f3(); } f3() { pthread_mutex_unlock(&m2); pthread_mutex_lock(&m2); }

has the following syntax:

members struct_tag

Lists the members of the struct with the specified tag, one per line. For structures that were not assigned a tag, the notation file@line is used (for example, x.c@29), where the file and line number are the source location of the struct declaration.

members is particularly useful to use as input to other LockLint subcommands. For example, when trying to assert that a lock protects all the members of a struct, the following command suffices:

% lock_lint assert foo::lock protects `lock_lint members foo`

---

Note - The members subcommand does not list any fields of the struct that are defined to be of type mutex_t, rwlock_t, krwlock_t, or kmutex_t.

---

has the following syntax:

order [lock [lock]] order summary

The order subcommand lists information about the order in which locks are acquired by the code being analyzed. It may be run only after the analyze subcommand.

order [lock [lock]]

Shows the details about lock pairs. For example, the command

% lock_lint order foo bar

shows whether an attempt was made to acquire lock bar while holding lock foo. The output looks something like the following:

:foo :bar seen (first never write-held), valid

First the output tells whether such an attempt actually occurred (seen or unseen). If the attempt occurred, but never with one or both of the locks write-held, a parenthetical message to that effect appears, as shown. In this case, foo was never write-held while acquiring bar.

If an assertion was made about the lock order, the output shows whether the specified order is valid or invalid according to the assertion. If there was no assertion about the order of foo and bar, or if both orders were asserted (presumably because the user wanted to see all places where one of the locks was held while acquiring the other), the output indicates neither valid nor invalid.

order summary

Shows in a concise format the order in which locks are acquired. For example, the subcommand might show

:f :e :d :g :a :f :c :g :a

In this example, there are two orders because there is not enough information to allow locks e and d to be ordered with respect to lock c.

Some cycles are shown, while others are not. For example,

:a :b :c :b

is shown, but

:a :b :c :a

(where no other lock is ever held while trying to acquire one of these) is not. Deadlock information from the analysis is still reported.

has the following syntax:

pointer calls

Lists calls made through function pointers in the loaded files. Each call is shown as:

function [location of call] calls through funcptr func_ptr

For example,

foo.c:func1 [foo.c,84] calls through funcptr bar::read

means that at line 84 of foo.c, in func1 of foo.c, the function pointer bar::read (member read of a pointer to struct of type bar) is used to call a function.

has the following syntax:

reallow func ...

Allows you to make exceptions to disallow subcommands. For example, to prevent LockLint from analyzing any calling sequence in which f() calls g() calls h(), except when f() is called by e() which was called by d(), use the commands

% lock_lint disallow f g h % lock_lint reallow d e f g h

In some cases you may want to state that a function should only be called from a particular function, as in this example:

% lock_lint disallow f % lock_lint reallow e f

---

Note - A reallow subcommand only suppresses the effect of a disallow subcommand if the sequences end the same. For example, after the following commands, the sequence d e f g h would still be disallowed:

---

% lock_lint disallow e f g h % lock_lint reallow d e f g

has the following syntax:

reallows

Lists the calling sequences that are reallowed, as specified using the reallow subcommand.

has the following syntax:

refresh

Pops the saved state stack, restoring LockLint to the state of the top of the saved-state stack, prints the description, if any, associated with that state, and saves the state again. Equivalent to restore followed by save.

has the following syntax:

restore

Pops the saved state stack, restoring LockLint to the state of the top of the saved-state stack, and prints the description, if any, associated with that state.

The saved state stack is a LIFO (Last-In-First-Out) stack. Once a saved state is restored (popped) from the stack, that state is no longer on the saved-state stack. If the state needs to be saved and restored repeatedly, simply save the state again immediately after restoring it, or use the refresh subcommand.

has the following syntax:

save description

Saves the current state of the tool on a stack. The user-specified description is attached to the state. Saved states form a LIFO (Last-In-First-Out) stack, so that the last state saved is the first one restored.

This subcommand is commonly used to save the state of the tool before running the analyze subcommand, which can be run only once on a given state. For example, you can do the following:

%: lock_lint load *.ll %: lock_lint save Before Analysis %: lock_lint analyze <output from analyze> %: lock_lint vars -h | grep \* <apparent members of struct foo are not consistently protected> %: lock_lint refresh Before Analysis %: lock_lint assert lock1 protects `lock_lint members foo` %: lock_lint analyze <output now contains info about where the assertion is violated>

has the following syntax:

saves

Lists the descriptions of the states saved on the saved stack via the save subcommand. The descriptions are shown from top to bottom, with the first description being the most recently saved state that has not been restored, and the last description being the oldest state saved that has not been restored.

has the following syntax:

start [cmd]

which contains the path to the temporary directory of files used to maintain a LockLint session.

cmd specifies a command and its path and options. By default, if cmd is not specified, the value of $SHELL is used.

---

Note - To exit a LockLint session use the exit command of the shell you are using.

---

Start Examples

The following examples show variations of the start subcommand.

  Using the default

% lock_lint start

LockLint's context is established and LL_CONTEXT is set. Then the program identified by $SHELL is executed. Normally, this is your default shell. LockLint subcommands can now be entered. Upon exiting the shell, the LockLint context is removed.

Using a pre-written script

% lock_lint start foo

The LockLint context is established and LL_CONTEXT is set. Then, the command /bin/csh -c foo is executed. This results in executing the C shell command file foo, which contains LockLint commands. Upon completing the execution of the commands in foo by /bin/csh, the LockLint context is removed.

If you use a shell script to start LockLint, insert #! in the first line of the script to define the name of the interpreter that processes that script. For example, to specify the C-shell the first line of the script is:

#! /bin/csh

Starting up with a specific shell

In this case, the user starts LockLint with the Korn shell:

% lock_lint start /bin/ksh

After establishing the LockLint context and setting LL_CONTEXT, the command /bin/ksh is executed. This results in the user interacting with an interactive Korn shell. Upon exiting the Korn shell, the LockLint context is removed.

has the following syntax:

sym name ...

Lists the fully qualified names of various things the specified names could refer to within the loaded files. For example, foo might refer both to variable x.c:func1/foo and to function y.c:foo, depending on context.

has the following syntax:

unassert vars var ...

Undoes any assertion about locks protecting the specified variables. There is no way to remove an assertion about a lock protecting a function.

has the following syntax:

vars [-aho] var ... vars [-ahilo] vars [-ahlo] protected by lock vars [-ahlo] [directly] read by func ... vars [-ahlo] [directly] written by func ... vars [-ahlo] [directly] accessed by func ...

Lists information about the variables of the loaded files. Only those variables that are actually used are shown; variables that are simply declared in the program but never accessed are not shown.

TABLE A-9 vars Options

Option	Definition
-a	(assert) Shows information about which lock is supposed to protect each variable, as specified by the assert mutex|rwlock protects subcommand. The information is shown as follows assert=lock If the assertion is violated, then after analysis this will be preceded by an asterisk, such as *assert=<lock>.
-h	(held) Shows information about which locks were consistently held when the variable was accessed. This information is shown after the analyze subcommand has been run. If the variable was never accessed, this information is not shown. When it is shown, it looks like this: held={ <lock> ... } If no locks were consistently held and the variable was written, this is preceded by an asterisk, such as *held={ }. Unlike funcs, the vars subcommand lists a lock as protecting a variable even if the lock was not actually held, but was simply covered by another lock.
-i	(ignored) causes even ignored variables to be listed.
-l	(long) Equivalent to -aho.
-o	(other) Where applicable, shows information about each variable
	=cond_var	Indicates that this variable is used as a condition variable.
	=ignored	Indicates that LockLint has been told to ignore the variable explicitly via an ignore subcommand.
	=read-only	Means that LockLint has been told (by assert read only) that the variable is read-only, and will complain if it is written. If it is written, then after analysis this will be followed by an asterisk, such as =read-only* for example.
	=readable	Indicates that LockLint has been told by a declare readable subcommand that the variable may be safely read without holding a lock.
	=unwritten	May appear after analysis, meaning that while the variable was not declared read-only, it was never written.

vars [-aho] var ...

Lists information about individual variables. By default, this variant of the subcommand gives all the details about the variables, as if -aho had been specified.

vars [-ahilo]

Lists information about all variables that are not ignored. If -i is used, even ignored variables are listed.

vars [-ahlo] protected by lock

Lists only those variables that are protected by the specified lock. This subcommand may be run only after the analyze subcommand has been run.

vars [-ahlo] [directly] read by func ...

Lists only those variables that may be read as a result of calling the specified functions. See notes below on directly.

vars [-ahlo] [directly] written by func ...

Lists only those variables that may be written as a result of calling the specified functions. See notes below on directly.

vars [-ahlo] [directly] accessed by func ...

Lists only those variables that may be accessed (read or written) as a result of calling the specified functions.

About directly

Those variants that list the variables accessed by a list of functions can be told to list only those variables that are directly accessed by the specified functions. Otherwise the variables accessed by those functions, the functions they call, the functions those functions call, and so on, are listed.

Lock Inversions

A function is said to invert a lock if the lock is already held when the function is called, and the function releases the lock, such as:

foo() {
 pthread_mutex_unlock(&mtx);
 ...
 pthread_mutex_lock(&mtx);
}

Lock inversions are a potential source of insidious race conditions, since observations made under the protection of a lock may be invalidated by the inversion. In the following example, if foo() inverts mtx, then upon its return zort_list may be NULL (another thread may have emptied the list while the lock was dropped):

ZORT* zort_list;
 /* VARIABLES PROTECTED BY mtx: zort_list */
void f() {
 pthread_mutex_lock(&mtx);
 if (zort_list == NULL) {/* trying to be careful here */
 pthread_mutex_unlock(&mtx);
 return;
 }
 foo();
 zort_list->count++; /* but zort_list may be NULL here!! */
 pthread_mutex_unlock(&mtx);
}

Lock inversions may be found using the commands:

% lock_lint funcs [directly] inverting lock ...
% lock_lint locks [directly] inverted by func ...

An interesting question to ask is "Which functions acquire locks that then get inverted by calls they make?" That is, which functions are in danger of having stale data? The following (Bourne shell) code can answer this question:

$ LOCKS=`lock_lint locks`
$ lock_lint funcs calling `lock_lint funcs inverting $LOCKS`

The following gives similar output, separated by lock:

for lock in `lock_lint locks` do echo "functions endangered by inversions of lock $lock" lock_lint funcs calling `lock_lint funcs inverting $lock` done