CERT C: Rule CON35-C

Avoid deadlock by locking in a predefined order

Description

This checker is deactivated in a default Polyspace^® as You Code analysis. See Checkers Deactivated in Polyspace as You Code Analysis (Polyspace Access).

Rule Definition

Avoid deadlock by locking in a predefined order.¹

Polyspace Implementation

The rule checker checks for Deadlock.

Extend Checker

For the rule checker to detect issues, your code must use one of the concurrency primitives recognized by Polyspace for thread creation and shared variable protection. Otherwise, you must explicitly specify tasks, interrupts, critical sections, and other multitasking options in your project configuration. See Multitasking.

You can also extend this checker to detect synchronization issues by mapping your multithreading functions to their known POSIX^® equivalents. See Extend Concurrency Defect Checkers to Unsupported Multithreading Environments.

Examples

Deadlock

Issue

Deadlock occurs when multiple tasks are stuck in their critical sections (CS) because:

• Each CS waits for another CS to end.

• The critical sections (CS) form a closed cycle. For example:

  • CS #1 waits for CS #2 to end, and CS #2 waits for CS #1 to end.

  • CS #1 waits for CS #2 to end, CS #2 waits for CS #3 to end and CS #3 waits for CS #1 to end.

Polyspace expects critical sections of code to follow a specific format. A critical section lies between a call to a lock function and a call to an unlock function. When a task my_task calls a lock function my_lock, other tasks calling my_lock must wait until my_task calls the corresponding unlock function. Both lock and unlock functions must have the form void func(void).

To find this defect, you must specify the multitasking options before analysis. To specify these options, on the Configuration pane, select Multitasking.

Risk

Each task waits for a critical section in another task to end and is unable to proceed. The program can freeze indefinitely.

Fix

The fix depends on the root cause of the defect. You can try to break the cyclic order between the tasks in one of these ways:

• Write down all critical sections involved in the deadlock in a certain sequence. Whenever you call the lock functions of the critical sections within a task, respect the order in that sequence. See an example below.

• If one of the critical sections involved in a deadlock occurs in an interrupt, try to disable all interrupts during critical sections in all tasks. See Disabling all interrupts (-routine-disable-interrupts -routine-enable-interrupts).

Reviewing this defect is an opportunity to check if all operations in your critical section are really meant to be executed as an atomic block. It is a good practice to keep critical sections at a bare minimum.

If you do not want to fix the issue, add comments to your result or code to avoid another review. See:

• Address Results in Polyspace User Interface Through Bug Fixes or Justifications if you review results in the Polyspace user interface.

• Address Results in Polyspace Access Through Bug Fixes or Justifications (Polyspace Access) if you review results in a web browser.

• Annotate Code and Hide Known or Acceptable Results if you review results in an IDE.

Example - Deadlock with Two Tasks

void task1(void);
void task2(void);

int var;
void perform_task_cycle(void) {
 var++;
}

void begin_critical_section_1(void);
void end_critical_section_1(void);

void begin_critical_section_2(void);
void end_critical_section_2(void);

void task1() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2(); //Noncompliant
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

void task2() {
 while(1) {
    begin_critical_section_2();
    begin_critical_section_1();
    perform_task_cycle();
    end_critical_section_1();
    end_critical_section_2();
 } 
}

In this example, to emulate multitasking behavior, you must specify the following options:

Option	Specification
Configure multitasking manually
Entry points	task1 task2
Critical section details	Starting routine	Ending routine
	begin_critical_section_1	end_critical_section_1
	begin_critical_section_2	end_critical_section_2

A Deadlock occurs because the instructions can execute in the following sequence:

1. task1 calls begin_critical_section_1.

2. task2 calls begin_critical_section_2.

3. task1 reaches the instruction begin_critical_section_2();. Since task2 has already called begin_critical_section_2, task1 waits for task2 to call end_critical_section_2.

4. task2 reaches the instruction begin_critical_section_1();. Since task1 has already called begin_critical_section_1, task2 waits for task1 to call end_critical_section_1.

Correction-Follow Same Locking Sequence in Both Tasks

One possible correction is to follow the same sequence of calls to lock and unlock functions in both task1 and task2.

void task1(void);
void task2(void);
void perform_task_cycle(void);

void begin_critical_section_1(void);
void end_critical_section_1(void);

void begin_critical_section_2(void);
void end_critical_section_2(void);

void task1() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

void task2() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

Example - Deadlock with More Than Two Tasks

int var;
void performTaskCycle() {
 var++;
}

void lock1(void);
void lock2(void);
void lock3(void);


void unlock1(void);
void unlock2(void);
void unlock3(void);

void task1() {
 while(1) {
    lock1();
    lock2(); //Noncompliant
    performTaskCycle();
    unlock2();
    unlock1();
 } 
}

void task2() {
 while(1) {
    lock2();
    lock3();
    performTaskCycle();
    unlock3();
    unlock2();
 } 
}

void task3() {
 while(1) {
    lock3();
    lock1();
    performTaskCycle();
    unlock1();
    unlock3();
 } 
}

In this example, to emulate multitasking behavior, you must specify the following options:

Option	Specification
Configure multitasking manually
Entry points	task1 task2 task3
Critical section details	Starting routine	Ending routine
	lock1	unlock1
	lock2	unlock2
	lock3	unlock3

A Deadlock occurs because the instructions can execute in the following sequence:

1. task1 calls lock1.

2. task2 calls lock2.

3. task3 calls lock3.

4. task1 reaches the instruction lock2();. Since task2 has already called lock2, task1 waits for call to unlock2.

5. task2 reaches the instruction lock3();. Since task3 has already called lock3, task2 waits for call to unlock3.

6. task3 reaches the instruction lock1();. Since task1 has already called lock1, task3 waits for call to unlock1.

Correction — Break Cyclic Order

To break the cyclic order between critical sections, note every lock function in your code in a certain sequence, for example:

1. lock1

2. lock2

3. lock3

If you use more than one lock function in a task, use them in the order in which they appear in the sequence. For example, you can use lock1 followed by lock2 but not lock2 followed by lock1.

int var;
void performTaskCycle() {
 var++;
}

void lock1(void);
void lock2(void);
void lock3(void);

void unlock1(void);
void unlock2(void);
void unlock3(void);

void task1() {
 while(1) {
    lock1();
    lock2();
    performTaskCycle();
    unlock2();
    unlock1();
 } 
}

void task2() {
 while(1) {
    lock2();
    lock3();
    performTaskCycle();
    unlock3();
    unlock2();
 } 
}

void task3() {
 while(1) {
    lock1();
    lock3();
    performTaskCycle();
    unlock3();
    unlock1();
 } 
}

Check Information

Group: Rule 14. Concurrency (CON)

Version History

Introduced in R2019a