~ubuntu-branches/ubuntu/karmic/valgrind/karmic

C++ languagues. For a draft memory model, see also document <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html" target="_top">

195

WG21/N2338</a>.

196

</p>

197

<p>

198

For more information about POSIX threads, see also the Single UNIX

199

Specification version 3, also known as

200

201

IEEE Std 1003.1</a>.

202

</p>

203

</div>

204

205

206

<a name="drd-manual.mt-problems"></a>8.1.3.�Multithreaded Programming Problems</h3></div></div></div>

207

<p>

208

Depending on which multithreading paradigm is being used in a program,

209

one or more of the following problems can occur:

210

</p>

211

212

<li><p>

213

Data races. One or more threads access the same memory

214

location without sufficient locking.

215

</p></li>

216

<li><p>

217

Lock contention. One thread blocks the progress of one or more other

218

threads by holding a lock too long.

219

</p></li>

220

<li><p>

221

Improper use of the POSIX threads API. The most popular POSIX

222

threads implementation, NPTL, is optimized for speed. The NPTL

223

will not complain on certain errors, e.g. when a mutex is locked

224

in one thread and unlocked in another thread.

225

</p></li>

226

<li><p>

227

Deadlock. A deadlock occurs when two or more threads wait for

228

each other indefinitely.

229

</p></li>

230

<li><p>

231

False sharing. If threads that run on different processor cores

232

access different variables located in the same cache line

233

frequently, this will slow down the involved threads a lot due

234

to frequent exchange of cache lines.

235

</p></li>

236

</ul></div>

237

<p>

238

</p>

239

<p>

240

Although the likelihood of the occurrence of data races can be reduced

241

through a disciplined programming style, a tool for automatic

242

detection of data races is a necessity when developing multithreaded

243

software. DRD can detect these, as well as lock contention and

244

improper use of the POSIX threads API.

245

</p>

246

</div>

247

248

249

<a name="drd-manual.data-race-detection"></a>8.1.4.�Data Race Detection</h3></div></div></div>

250

<p>

251

Synchronization operations impose an order on interthread memory

252

accesses. This order is also known as the happens-before relationship.

253

</p>

254

<p>

255

A multithreaded program is data-race free if all interthread memory

256

accesses are ordered by synchronization operations.

257

</p>

258

<p>

259

A well known way to ensure that a multithreaded program is data-race

260

free is to ensure that a locking discipline is followed. It is e.g.

261

possible to associate a mutex with each shared data item, and to hold

262

a lock on the associated mutex while the shared data is accessed.

263

</p>

264

<p>

265

All programs that follow a locking discipline are data-race free, but

266

not all data-race free programs follow a locking discipline. There

267

exist multithreaded programs where access to shared data is arbitrated

268

via condition variables, semaphores or barriers. As an example, a

269

certain class of HPC applications consists of a sequence of

270

computation steps separated in time by barriers, and where these

271

barriers are the only means of synchronization.

272

</p>

273

<p>

274

There exist two different algorithms for verifying the correctness of

275

multithreaded programs at runtime. The so-called Eraser algorithm

276

verifies whether all shared memory accesses follow a consistent

277

locking strategy. And the happens-before data race detectors verify

278

directly whether all interthread memory accesses are ordered by

279

synchronization operations. While the happens-before data race

280

detection algorithm is more complex to implement, and while it is more

281

sensitive to OS scheduling, it is a general approach that works for

282

all classes of multithreaded programs. Furthermore, the happens-before

283

data race detection algorithm does not report any false positives.

284

</p>

285

<p>

286

DRD is based on the happens-before algorithm.

287

</p>

288

</div>

289

</div>

290

291

292

<a name="drd-manual.using-drd"></a>8.2.�Using DRD</h2></div></div></div>

293

294

295

<a name="drd-manual.options"></a>8.2.1.�Command Line Options</h3></div></div></div>

296

<p>The following command-line options are available for controlling the

297

behavior of the DRD tool itself:</p>

298

299

300

301

<code class="option">--check-stack-var=<yes|no> [default: no]</code>

302

</span></dt>

303

<dd><p>

304

Controls whether <code class="constant">DRD</code> reports data races

305

for stack variables. This is disabled by default in order to

306

accelerate data race detection. Most programs do not share

307

stack variables over threads.

308

</p></dd>

309

310

<code class="option">--exclusive-threshold=<n> [default: off]</code>

311

</span></dt>

312

<dd><p>

313

Print an error message if any mutex or writer lock has been

314

held longer than the specified time (in milliseconds). This

315

option enables detecting lock contention.

316

</p></dd>

317

318

319

--report-signal-unlocked=<yes|no> [default: yes]

320

</code>

321

</span></dt>

322

<dd><p>

323

Whether to report calls to

324

<code class="function">pthread_cond_signal()</code> and

325

<code class="function">pthread_cond_broadcast()</code> where the mutex

326

associated with the signal through

327

<code class="function">pthread_cond_wait()</code> or

328

<code class="function">pthread_cond_timed_wait()</code>is not locked at

329

the time the signal is sent. Sending a signal without holding

330

a lock on the associated mutex is a common programming error

331

which can cause subtle race conditions and unpredictable

332

behavior. There exist some uncommon synchronization patterns

333

however where it is safe to send a signal without holding a

334

lock on the associated mutex.

335

</p></dd>

336

337

<code class="option">--segment-merging=<yes|no> [default: yes]</code>

338

</span></dt>

339

<dd><p>

340

Controls segment merging. Segment merging is an algorithm to

341

limit memory usage of the data race detection

342

algorithm. Disabling segment merging may improve the accuracy

343

of the so-called 'other segments' displayed in race reports

344

but can also trigger an out of memory error.

345

</p></dd>

346

347

<code class="option">--shared-threshold=<n> [default: off]</code>

348

</span></dt>

349

<dd><p>

350

Print an error message if a reader lock has been held longer

351

than the specified time (in milliseconds). This option enables

352

detection of lock contention.

353

</p></dd>

354

355

<code class="option">--show-confl-seg=<yes|no> [default: yes]</code>

356

</span></dt>

357

<dd><p>

358

Show conflicting segments in race reports. Since this

359

information can help to find the cause of a data race, this

360

option is enabled by default. Disabling this option makes the

361

output of DRD more compact.

362

</p></dd>

363

364

<code class="option">--show-stack-usage=<yes|no> [default: no]</code>

365

</span></dt>

366

<dd><p>

367

Print stack usage at thread exit time. When a program creates

368

a large number of threads it becomes important to limit the

369

amount of virtual memory allocated for thread stacks. This

370

option makes it possible to observe how much stack memory has

371

been used by each thread of the the client program. Note: the

372

DRD tool allocates some temporary data on the client thread

373

stack itself. The space necessary for this temporary data must

374

be allocated by the client program, but is not included in the

375

reported stack usage.

376

</p></dd>

377

378

<code class="option">--var-info=<yes|no> [default: no]</code>

379

</span></dt>

380

<dd><p>

381

Display the names of global, static and stack variables when a

382

data race is reported. While this information can be very

383

helpful, it is not loaded into memory by default. This is

384

because for big programs reading in all debug information at

385

once may cause an out of memory error.

386

</p></dd>

387

</dl>

388

</div>

389

<p>

390

The following options are available for monitoring the behavior of the

391

client program:

392

</p>

393

394

395

396

<code class="option">--trace-addr=<address> [default: none]</code>

397

</span></dt>

398

<dd><p>

399

Trace all load and store activity for the specified

400

address. This option may be specified more than once.

401

</p></dd>

402

403

<code class="option">--trace-barrier=<yes|no> [default: no]</code>

404

</span></dt>

405

<dd><p>

406

Trace all barrier activity.

407

</p></dd>

408

409

<code class="option">--trace-cond=<yes|no> [default: no]</code>

410

</span></dt>

411

<dd><p>

412

Trace all condition variable activity.

413

</p></dd>

414

415

<code class="option">--trace-fork-join=<yes|no> [default: no]</code>

416

</span></dt>

417

<dd><p>

418

Trace all thread creation and all thread termination events.

419

</p></dd>

420

421

<code class="option">--trace-mutex=<yes|no> [default: no]</code>

422

</span></dt>

423

<dd><p>

424

Trace all mutex activity.

425

</p></dd>

426

427

<code class="option">--trace-rwlock=<yes|no> [default: no]</code>

428

</span></dt>

429

<dd><p>

430

Trace all reader-writer lock activity.

431

</p></dd>

432

433

<code class="option">--trace-semaphore=<yes|no> [default: no]</code>

434

</span></dt>

435

<dd><p>

436

Trace all semaphore activity.

437

</p></dd>

438

</dl>

439

</div>

440

</div>

441

442

443

<a name="drd-manual.data-races"></a>8.2.2.�Detected Errors: Data Races</h3></div></div></div>

444

<p>

445

DRD prints a message every time it detects a data race. Please keep

446

the following in mind when interpreting DRD's output:

447

</p>

448

449

<li><p>

450

Every thread is assigned two <span class="emphasis"><em>thread ID's</em></span>:

451

one thread ID is assigned by the Valgrind core and one thread ID

452

is assigned by DRD. Both thread ID's start at one. Valgrind

453

thread ID's are reused when one thread finishes and another

454

thread is created. DRD does not reuse thread ID's. Thread ID's

455

are displayed e.g. as follows: 2/3, where the first number is

456

Valgrind's thread ID and the second number is the thread ID

457

assigned by DRD.

458

</p></li>

459

<li><p>

460

The term <span class="emphasis"><em>segment</em></span> refers to a consecutive

461

sequence of load, store and synchronization operations, all

462

issued by the same thread. A segment always starts and ends at a

463

synchronization operation. Data race analysis is performed

464

between segments instead of between individual load and store

465

operations because of performance reasons.

466

</p></li>

467

<li><p>

468

There are always at least two memory accesses involved in a data

469

race. Memory accesses involved in a data race are called

470

<span class="emphasis"><em>conflicting memory accesses</em></span>. DRD prints a

471

report for each memory access that conflicts with a past memory

472

access.

473

</p></li>

474

</ul></div>

475

<p>

476

</p>

477

<p>

478

Below you can find an example of a message printed by DRD when it

479

detects a data race:

480

</p>

481

482

$ valgrind --tool=drd --var-info=yes drd/tests/rwlock_race

483

...

484

==9466== Thread 3:

485

==9466== Conflicting load by thread 3/3 at 0x006020b8 size 4

486

==9466== at 0x400B6C: thread_func (rwlock_race.c:29)

487

==9466== by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)

488

==9466== by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)

489

==9466== by 0x53250CC: clone (in /lib64/libc-2.8.so)

490

==9466== Location 0x6020b8 is 0 bytes inside local var "s_racy"

491

==9466== declared at rwlock_race.c:18, in frame #0 of thread 3

492

==9466== Other segment start (thread 2/2)

493

==9466== at 0x4C2847D: pthread_rwlock_rdlock* (drd_pthread_intercepts.c:813)

494

==9466== by 0x400B6B: thread_func (rwlock_race.c:28)

495

==9466== by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)

496

==9466== by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)

497

==9466== by 0x53250CC: clone (in /lib64/libc-2.8.so)

498

==9466== Other segment end (thread 2/2)

499

==9466== at 0x4C28B54: pthread_rwlock_unlock* (drd_pthread_intercepts.c:912)

500

==9466== by 0x400B84: thread_func (rwlock_race.c:30)

501

==9466== by 0x4C291DF: vg_thread_wrapper (drd_pthread_intercepts.c:186)

502

==9466== by 0x4E3403F: start_thread (in /lib64/libpthread-2.8.so)

503

==9466== by 0x53250CC: clone (in /lib64/libc-2.8.so)

504

...

505

</pre>

506

<p>

507

The above report has the following meaning:

508

</p>

509

510

<li><p>

511

The number in the column on the left is the process ID of the

512

process being analyzed by DRD.

513

</p></li>

514

<li><p>

515

The first line ("Thread 3") tells you Valgrind's thread ID for

516

the thread in which context the data race was detected.

517

</p></li>

518

<li><p>

519

The next line tells which kind of operation was performed (load

520

or store) and by which thread. Both Valgrind's and DRD's thread

521

ID's are displayed. On the same line the start address and the

522

number of bytes involved in the conflicting access are also

523

displayed.

524

</p></li>

525

<li><p>

526

Next, the call stack of the conflicting access is displayed. If

527

your program has been compiled with debug information (-g), this

528

call stack will include file names and line numbers. The two

529

bottommost frames in this call stack (<code class="function">clone</code>

530

and <code class="function">start_thread</code>) show how the NPTL starts

531

a thread. The third frame

532

(<code class="function">vg_thread_wrapper</code>) is added by DRD. The

533

fourth frame (<code class="function">thread_func</code>) is the first

534

interesting line because it shows the thread entry point, that

535

is the function that has been passed as the third argument to

536

<code class="function">pthread_create()</code>.

537

</p></li>

538

<li><p>

539

Next, the allocation context for the conflicting address is

540

displayed. For dynamically allocated data the allocation call

541

stack is shown. For static variables and stack variables the

542

allocation context is only shown when the option

543

<code class="computeroutput">--var-info=yes</code> has been

544

specified. Otherwise DRD will print <code class="computeroutput">Allocation

545

context: unknown</code>.

546

</p></li>

547

<li>

548

<p>

549

A conflicting access involves at least two memory accesses. For

550

one of these accesses an exact call stack is displayed, and for

551

the other accesses an approximate call stack is displayed,

552

namely the start and the end of the segments of the other

553

accesses. This information can be interpreted as follows:

554

</p>

555

556

<li><p>

557

Start at the bottom of both call stacks, and count the

558

number stack frames with identical function name, file

559

name and line number. In the above example the three

560

bottommost frames are identical

561

(<code class="function">clone</code>,

562

<code class="function">start_thread</code> and

563

<code class="function">vg_thread_wrapper</code>).

564

</p></li>

565

<li><p>

566

The next higher stack frame in both call stacks now tells

567

you between in which source code region the other memory

568

access happened. The above output tells that the other

569

memory access involved in the data race happened between

570

source code lines 28 and 30 in file

571

<code class="computeroutput">rwlock_race.c</code>.

572

</p></li>

573

</ol></div>

574

<p>

575

</p>

576

</li>

577

</ul></div>

578

<p>

579

</p>

580

</div>

581

582

583

<a name="drd-manual.lock-contention"></a>8.2.3.�Detected Errors: Lock Contention</h3></div></div></div>

584

<p>

585

Threads must be able to make progress without being blocked for too

586

long by other threads. Sometimes a thread has to wait until a mutex or

587

reader-writer lock is unlocked by another thread. This is called

588

<span class="emphasis"><em>lock contention</em></span>.

589

</p>

590

<p>

591

Lock contention causes delays. Such delays should be as short as

592

possible. The two command line options

593

<code class="literal">--exclusive-threshold=<n></code> and

594

<code class="literal">--shared-threshold=<n></code> make it possible to

595

detect excessive lock contention by making DRD report any lock that

596

has been held longer than the specified threshold. An example:

597

</p>

598

599

$ valgrind --tool=drd --exclusive-threshold=10 drd/tests/hold_lock -i 500

600

...

601

==10668== Acquired at:

602

==10668== at 0x4C267C8: pthread_mutex_lock (drd_pthread_intercepts.c:395)

603

==10668== by 0x400D92: main (hold_lock.c:51)

604

==10668== Lock on mutex 0x7fefffd50 was held during 503 ms (threshold: 10 ms).

605

==10668== at 0x4C26ADA: pthread_mutex_unlock (drd_pthread_intercepts.c:441)

606

==10668== by 0x400DB5: main (hold_lock.c:55)

607

...

608

</pre>

609

<p>

610

The <code class="literal">hold_lock</code> test program holds a lock as long as

611

specified by the <code class="literal">-i</code> (interval) argument. The DRD

612

output reports that the lock acquired at line 51 in source file

613

<code class="literal">hold_lock.c</code> and released at line 55 was held during

614

503 ms, while a threshold of 10 ms was specified to DRD.

615

</p>

616

</div>

617

618

619

<a name="drd-manual.api-checks"></a>8.2.4.�Detected Errors: Misuse of the POSIX threads API</h3></div></div></div>

620

<p>

621

DRD is able to detect and report the following misuses of the POSIX

622

threads API:

623

</p>

624

625

<li><p>

626

Passing the address of one type of synchronization object

627

(e.g. a mutex) to a POSIX API call that expects a pointer to

628

another type of synchronization object (e.g. a condition

629

variable).

630

</p></li>

631

<li><p>

632

Attempts to unlock a mutex that has not been locked.

633

</p></li>

634

<li><p>

635

Attempts to unlock a mutex that was locked by another thread.

636

</p></li>

637

<li><p>

638

Attempts to lock a mutex of type

639

<code class="literal">PTHREAD_MUTEX_NORMAL</code> or a spinlock

640

recursively.

641

</p></li>

642

<li><p>

643

Destruction or deallocation of a locked mutex.

644

</p></li>

645

<li><p>

646

Sending a signal to a condition variable while no lock is held

647

on the mutex associated with the signal.

648

</p></li>

649

<li><p>

650

Calling <code class="function">pthread_cond_wait()</code> on a mutex

651

that is not locked, that is locked by another thread or that

652

has been locked recursively.

653

</p></li>

654

<li><p>

655

Associating two different mutexes with a condition variable

656

through <code class="function">pthread_cond_wait()</code>.

657

</p></li>

658

<li><p>

659

Destruction or deallocation of a condition variable that is

660

being waited upon.

661

</p></li>

662

<li><p>

663

Destruction or deallocation of a locked reader-writer lock.

664

</p></li>

665

<li><p>

666

Attempts to unlock a reader-writer lock that was not locked by

667

the calling thread.

668

</p></li>

669

<li><p>

670

Attempts to recursively lock a reader-writer lock exclusively.

671

</p></li>

672

<li><p>

673

Reinitialization of a mutex, condition variable, reader-writer

674

lock, semaphore or barrier.

675

</p></li>

676

<li><p>

677

Destruction or deallocation of a semaphore or barrier that is

678

being waited upon.

679

</p></li>

680

<li><p>

681

Exiting a thread without first unlocking the spinlocks,

682

mutexes or reader-writer locks that were locked by that

683

thread.

684

</p></li>

685

</ul></div>

686

<p>

687

</p>

688

</div>

689

690

691

<a name="drd-manual.clientreqs"></a>8.2.5.�Client Requests</h3></div></div></div>

692

<p>

693

Just as for other Valgrind tools it is possible to let a client

694

program interact with the DRD tool.

695

</p>

696

<p>

697

The interface between client programs and the DRD tool is defined in

698

the header file <code class="literal"><valgrind/drd.h></code>. The

699

available client requests are:

700

</p>

701

702

<li><p>

703

<code class="varname">VG_USERREQ__DRD_GET_VALGRIND_THREAD_ID</code>.

704

Query the thread ID that was assigned by the Valgrind core to

705

the thread executing this client request. Valgrind's thread ID's

706

start at one and are recycled in case a thread stops.

707

</p></li>

708

<li><p>

709

<code class="varname">VG_USERREQ__DRD_GET_DRD_THREAD_ID</code>.

710

Query the thread ID that was assigned by DRD to

711

the thread executing this client request. DRD's thread ID's

712

start at one and are never recycled.

713

</p></li>

714

<li><p>

715

<code class="varname">VG_USERREQ__DRD_START_SUPPRESSION</code>. Some

716

applications contain intentional races. There exist

717

e.g. applications where the same value is assigned to a shared

718

variable from two different threads. It may be more convenient

719

to suppress such races than to solve these. This client request

720

allows to suppress such races. See also the macro

721

<code class="literal">DRD_IGNORE_VAR(x)</code> defined in

722

<code class="literal"><valgrind/drd.h></code>.

723

</p></li>

724

<li><p>

725

<code class="varname">VG_USERREQ__DRD_FINISH_SUPPRESSION</code>. Tell DRD

726

to no longer ignore data races in the address range that was

727

suppressed via

728

<code class="varname">VG_USERREQ__DRD_START_SUPPRESSION</code>.

729

</p></li>

730

<li><p>

731

<code class="varname">VG_USERREQ__DRD_START_TRACE_ADDR</code>. Trace all

732

load and store activity on the specified address range. When DRD

733

reports a data race on a specified variable, and it's not

734

immediately clear which source code statements triggered the

735

conflicting accesses, it can be helpful to trace all activity on

736

the offending memory location. See also the macro

737

<code class="literal">DRD_TRACE_VAR(x)</code> defined in

738

<code class="literal"><valgrind/drd.h></code>.

739

</p></li>

740

<li><p>

741

<code class="varname">VG_USERREQ__DRD_STOP_TRACE_ADDR</code>. Do no longer

742

trace load and store activity for the specified address range.

743

</p></li>

744

</ul></div>

745

<p>

746

</p>

747

<p>

748

Note: if you compiled Valgrind yourself, the header file

749

<code class="literal"><valgrind/drd.h></code> will have been installed in

750

the directory <code class="literal">/usr/include</code> by the command

751

<code class="literal">make install</code>. If you obtained Valgrind by

752

installing it as a package however, you will probably have to install

753

another package with a name like <code class="literal">valgrind-devel</code>

754

before Valgrind's header files are present.

755

</p>

756

</div>

757

758

759

<a name="drd-manual.gnome"></a>8.2.6.�Debugging GNOME Programs</h3></div></div></div>

760

<p>

761

GNOME applications use the threading primitives provided by the

762

<code class="computeroutput">glib</code> and

763

<code class="computeroutput">gthread</code> libraries. These libraries

764

are built on top of POSIX threads, and hence are directly supported by

765

DRD. Please keep in mind that you have to call

766

<code class="function">g_thread_init()</code> before creating any threads, or

767

DRD will report several data races on glib functions. See also the

768

<a href="http://library.gnome.org/devel/glib/stable/glib-Threads.html" target="_top">GLib

769

Reference Manual</a> for more information about

770

<code class="function">g_thread_init()</code>.

771

</p>

772

<p>

773

One of the many facilities provided by the <code class="literal">glib</code>

774

library is a block allocator, called <code class="literal">g_slice</code>. You

775

have to disable this block allocator when using DRD by adding the

776

following to the shell environment variables:

777

<code class="literal">G_SLICE=always-malloc</code>. See also the <a href="http://library.gnome.org/devel/glib/stable/glib-Memory-Slices.html" target="_top">GLib

778

Reference Manual</a> for more information.

779

</p>

780

</div>

781

782

783

<a name="drd-manual.qt"></a>8.2.7.�Debugging Qt Programs</h3></div></div></div>

784

<p>

785

The Qt library is the GUI library used by the KDE project. Currently

786

there are two versions of the Qt library in use: Qt3 by KDE 3 and Qt4

787

by KDE 4. If possible, use Qt4 instead of Qt3. Qt3 is no longer

788

supported, and there are known problems with multithreading support in

789

Qt3. As an example, using QString objects in more than one thread will

790

trigger race reports (this has been confirmed by Trolltech -- see also

791

Trolltech task <a href="http://trolltech.com/developer/task-tracker/index_html" target="_top">#206152</a>).

792

</p>

793

<p>

794

Qt4 applications are supported by DRD, but only if the

795

<code class="literal">libqt4-debuginfo</code> package has been installed. Some

796

of the synchronization and threading primitives in Qt4 bypass the

797

POSIX threads library, and DRD can only intercept these if symbol

798

information for the Qt4 library is available. DRD won't tell you if it

799

has not been able to load the Qt4 debug information, but a huge number

800

of data races will be reported on data protected via

801

<code class="literal">QMutex</code> objects.

802

</p>

803

</div>

804

805

806

<a name="drd-manual.boost.thread"></a>8.2.8.�Debugging Boost.Thread Programs</h3></div></div></div>

807

<p>

808

The Boost.Thread library is the threading library included with the

809

cross-platform Boost Libraries. This threading library is an early

810

implementation of the upcoming C++0x threading library.

811

</p>

812

<p>

813

Applications that use the Boost.Thread library should run fine under DRD.

814

</p>

815

<p>

816

More information about Boost.Thread can be found here:

817

</p>

818

819

<li><p>

820

Anthony Williams, <a href="http://www.boost.org/doc/libs/1_37_0/doc/html/thread.html" target="_top">Boost.Thread</a>

821

Library Documentation, Boost website, 2007.

822

</p></li>

823

<li><p>

824

Anthony Williams, <a href="http://www.ddj.com/cpp/211600441" target="_top">What's New in Boost

825

Threads?</a>, Recent changes to the Boost Thread library,

826

Dr. Dobbs Magazine, October 2008.

827

</p></li>

828

</ul></div>

829

<p>

830

</p>

831

</div>

832

833

834

<a name="drd-manual.openmp"></a>8.2.9.�Debugging OpenMP Programs</h3></div></div></div>

835

<p>

836

OpenMP stands for <span class="emphasis"><em>Open Multi-Processing</em></span>. The

837

OpenMP standard consists of a set of compiler directives for C, C++

838

and Fortran programs that allows a compiler to transform a sequential

839

program into a parallel program. OpenMP is well suited for HPC

840

applications and allows to work at a higher level compared to direct

841

use of the POSIX threads API. While OpenMP ensures that the POSIX API

842

is used correctly, OpenMP programs can still contain data races. So it

843

makes sense to verify OpenMP programs with a thread checking tool.

844

</p>

845

<p>

846

DRD supports OpenMP shared-memory programs generated by gcc. The gcc

847

compiler supports OpenMP since version 4.2.0. Gcc's runtime support

848

for OpenMP programs is provided by a library called

849

<code class="literal">libgomp</code>. The synchronization primites implemented

850

in this library use Linux' futex system call directly, unless the

851

library has been configured with the

852

<code class="literal">--disable-linux-futex</code> flag. DRD only supports

853

libgomp libraries that have been configured with this flag and in

854

which symbol information is present. For most Linux distributions this

855

means that you will have to recompile gcc. See also the script

856

<code class="literal">drd/scripts/download-and-build-gcc</code> in the

857

Valgrind source tree for an example of how to compile gcc. You will

858

also have to make sure that the newly compiled

859

<code class="literal">libgomp.so</code> library is loaded when OpenMP programs

860

are started. This is possible by adding a line similar to the

861

following to your shell startup script:

862

</p>

863

864

export LD_LIBRARY_PATH=~/gcc-4.3.2/lib64:~/gcc-4.3.2/lib:

865

</pre>

866

<p>

867

As an example, the test OpenMP test program

868

<code class="literal">drd/tests/omp_matinv</code> triggers a data race

869

when the option -r has been specified on the command line. The data

870

race is triggered by the following code:

871

</p>

872

873

#pragma omp parallel for private(j)

874

for (j = 0; j < rows; j++)

875

{

876

if (i != j)

877

{

878

const elem_t factor = a[j * cols + i];

879

for (k = 0; k < cols; k++)

880

{

881

a[j * cols + k] -= a[i * cols + k] * factor;

882

}

883

}

884

}

885

</pre>

886

<p>

887

The above code is racy because the variable <code class="literal">k</code> has

888

not been declared private. DRD will print the following error message

889

for the above code:

890

</p>

891

892

$ valgrind --check-stack-var=yes --var-info=yes --tool=drd drd/tests/omp_matinv 3 -t 2 -r

893

...

894

Conflicting store by thread 1/1 at 0x7fefffbc4 size 4

895

at 0x4014A0: gj.omp_fn.0 (omp_matinv.c:203)

896

by 0x401211: gj (omp_matinv.c:159)

897

by 0x40166A: invert_matrix (omp_matinv.c:238)

898

by 0x4019B4: main (omp_matinv.c:316)

899

Allocation context: unknown.

900

...

901

</pre>

902

<p>

903

In the above output the function name <code class="function">gj.omp_fn.0</code>

904

has been generated by gcc from the function name

905

<code class="function">gj</code>. Unfortunately the variable name

906

<code class="literal">k</code> is not shown as the allocation context -- it is

907

not clear to me whether this is caused by Valgrind or whether this is

908

caused by gcc. The most usable information in the above output is the

909

source file name and the line number where the data race has been detected

910

(<code class="literal">omp_matinv.c:203</code>).

911

</p>

912

<p>

913

Note: DRD reports errors on the <code class="literal">libgomp</code> library

914

included with gcc 4.2.0 up to and including 4.3.2. This might indicate

915

a race condition in the POSIX version of <code class="literal">libgomp</code>.

916

</p>

917

<p>

918

For more information about OpenMP, see also

919

<a href="http://openmp.org/" target="_top">openmp.org</a>.

920

</p>

921

</div>

922

923

924

<a name="drd-manual.cust-mem-alloc"></a>8.2.10.�DRD and Custom Memory Allocators</h3></div></div></div>

925

<p>

926

DRD tracks all memory allocation events that happen via either the

927

standard memory allocation and deallocation functions

928

(<code class="function">malloc</code>, <code class="function">free</code>,

929

<code class="function">new</code> and <code class="function">delete</code>) or via entry

930

and exit of stack frames. DRD uses memory allocation and deallocation

931

information for two purposes:

932

</p>

933

934

<li><p>

935

To know where the scope ends of POSIX objects that have not been

936

destroyed explicitly. It is e.g. not required by the POSIX

937

threads standard to call

938

<code class="function">pthread_mutex_destroy()</code> before freeing the

939

memory in which a mutex object resides.

940

</p></li>

941

<li><p>

942

To know where the scope of variables ends. If e.g. heap memory

943

has been used by one thread, that thread frees that memory, and

944

another thread allocates and starts using that memory, no data

945

races must be reported for that memory.

946

</p></li>

947

</ul></div>

948

<p>

949

</p>

950

<p>

951

It is essential for correct operation of DRD that the tool knows about

952

memory allocation and deallocation events. DRD does not yet support

953

custom memory allocators, so you will have to make sure that any

954

program which runs under DRD uses the standard memory allocation

955

functions. As an example, the GNU libstdc++ library can be configured

956

to use standard memory allocation functions instead of memory pools by

957

setting the environment variable

958

<code class="literal">GLIBCXX_FORCE_NEW</code>. For more information, see also

959

the <a href="http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt04ch11.html" target="_top">libstdc++

960

manual</a>.

961

</p>

962

</div>

963

964

965

<a name="drd-manual.drd-versus-memcheck"></a>8.2.11.�DRD Versus Memcheck</h3></div></div></div>

966

<p>

967

It is essential for correct operation of DRD that there are no memory

968

errors such as dangling pointers in the client program. Which means that

969

it is a good idea to make sure that your program is memcheck-clean

970

before you analyze it with DRD. It is possible however that some of

971

the memcheck reports are caused by data races. In this case it makes

972

sense to run DRD before memcheck.

973

</p>

974

<p>

975

So which tool should be run first ? In case both DRD and memcheck

976

complain about a program, a possible approach is to run both tools

977

alternatingly and to fix as many errors as possible after each run of

978

each tool until none of the two tools prints any more error messages.

979

</p>

980

</div>

981

982

983

<a name="drd-manual.resource-requirements"></a>8.2.12.�Resource Requirements</h3></div></div></div>

984

<p>

985

The requirements of DRD with regard to heap and stack memory and the

986

effect on the execution time of client programs are as follows:

987

</p>

988

989

<li><p>

990

When running a program under DRD with default DRD options,

991

between 1.1 and 3.6 times more memory will be needed compared to

992

a native run of the client program. More memory will be needed

993

if loading debug information has been enabled

994

(<code class="literal">--var-info=yes</code>).

995

</p></li>

996

<li><p>

997

DRD allocates some of its temporary data structures on the stack

998

of the client program threads. This amount of data is limited to

999

1 - 2 KB. Make sure that thread stacks are sufficiently large.

1000

</p></li>

1001

<li><p>

1002

Most applications will run between 20 and 50 times slower under

1003

DRD than a native single-threaded run. Applications such as

1004

Firefox which perform very much mutex lock / unlock operations

1005

however will run too slow to be usable under DRD. This issue

1006

will be addressed in a future DRD version.

1007

</p></li>

1008

</ul></div>

1009

<p>

1010

</p>

1011

</div>

1012

1013

1014

<a name="drd-manual.effective-use"></a>8.2.13.�Hints and Tips for Effective Use of DRD</h3></div></div></div>

1015

<p>

1016

The following information may be helpful when using DRD:

1017

</p>

1018

1019

<li><p>

1020

Make sure that debug information is present in the executable

1021

being analysed, such that DRD can print function name and line

1022

number information in stack traces. Most compilers can be told

1023

to include debug information via compiler option

1024

<code class="option">-g</code>.

1025

</p></li>

1026

<li><p>

1027

Compile with flag <code class="option">-O1</code> instead of

1028

<code class="option">-O0</code>. This will reduce the amount of generated

1029

code, may reduce the amount of debug info and will speed up

1030

DRD's processing of the client program. For more information,

1031

see also <a href="manual-core.html#manual-core.started">Getting started</a>.

1032

</p></li>

1033

<li><p>

1034

If DRD reports any errors on libraries that are part of your

1035

Linux distribution like e.g. <code class="literal">libc.so</code> or

1036

<code class="literal">libstdc++.so</code>, installing the debug packages

1037

for these libraries will make the output of DRD a lot more

1038

detailed.

1039

</p></li>

1040

<li>

1041

<p>

1042

When using C++, do not send output from more than one thread to

1043

<code class="literal">std::cout</code>. Doing so would not only

1044

generate multiple data race reports, it could also result in

1045

output from several threads getting mixed up. Either use

1046

<code class="function">printf()</code> or do the following:

1047

</p>

1048

1049

<li><p>Derive a class from <code class="literal">std::ostreambuf</code>

1050

and let that class send output line by line to

1051

<code class="literal">stdout</code>. This will avoid that individual

1052

lines of text produced by different threads get mixed

1053

up.</p></li>

1054

<li><p>Create one instance of <code class="literal">std::ostream</code>

1055

for each thread. This makes stream formatting settings

1056

thread-local. Pass a per-thread instance of the class

1057

derived from <code class="literal">std::ostreambuf</code> to the

1058

constructor of each instance. </p></li>

1059

<li><p>Let each thread send its output to its own instance of

1060

<code class="literal">std::ostream</code> instead of

1061

1062

</ol></div>

1063

<p>

1064

</p>

1065

</li>

1066

</ul></div>

1067

<p>

1068

</p>

1069

</div>

1070

</div>

1071

1072

1073

<a name="drd-manual.Pthreads"></a>8.3.�Using the POSIX Threads API Effectively</h2></div></div></div>

1074

1075

1076

<a name="drd-manual.mutex-types"></a>8.3.1.�Mutex types</h3></div></div></div>

1077

<p>

1078

The Single UNIX Specification version two defines the following four

1079

mutex types (see also the documentation of <a href="http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_mutexattr_settype.html" target="_top"><code class="function">pthread_mutexattr_settype()</code></a>):

1080

</p>

1081

1082

<li><p>

1083

<span class="emphasis"><em>normal</em></span>, which means that no error checking

1084

is performed, and that the mutex is non-recursive.

1085

</p></li>

1086

<li><p>

1087

<span class="emphasis"><em>error checking</em></span>, which means that the mutex

1088

is non-recursive and that error checking is performed.

1089

</p></li>

1090

<li><p>

1091

<span class="emphasis"><em>recursive</em></span>, which means that a mutex may be

1092

locked recursively.

1093

</p></li>

1094

<li><p>

1095

<span class="emphasis"><em>default</em></span>, which means that error checking

1096

behavior is undefined, and that the behavior for recursive

1097

locking is also undefined. Or: portable code must neither

1098

trigger error conditions through the Pthreads API nor attempt to

1099

lock a mutex of default type recursively.

1100

</p></li>

1101

</ul></div>

1102

<p>

1103

</p>

1104

<p>

1105

In complex applications it is not always clear from beforehand which

1106

mutex will be locked recursively and which mutex will not be locked

1107

recursively. Attempts lock a non-recursive mutex recursively will

1108

result in race conditions that are very hard to find without a thread

1109

checking tool. So either use the error checking mutex type and

1110

consistently check the return value of Pthread API mutex calls, or use

1111

the recursive mutex type.

1112

</p>

1113

</div>

1114

1115

1116

<a name="drd-manual.condvar"></a>8.3.2.�Condition variables</h3></div></div></div>

1117

<p>

1118

A condition variable allows one thread to wake up one or more other

1119

threads. Condition variables are often used to notify one or more

1120

threads about state changes of shared data. Unfortunately it is very

1121

easy to introduce race conditions by using condition variables as the

1122

only means of state information propagation. A better approach is to

1123

let threads poll for changes of a state variable that is protected by

1124

a mutex, and to use condition variables only as a thread wakeup

1125

mechanism. See also the source file

1126

<code class="computeroutput">drd/tests/monitor_example.cpp</code> for an

1127

example of how to implement this concept in C++. The monitor concept

1128

used in this example is a well known and very useful concept -- see

1129

also Wikipedia for more information about the <a href="http://en.wikipedia.org/wiki/Monitor_(synchronization)" target="_top">monitor</a>

1130

concept.

1131

</p>

1132

</div>

1133

1134

1135

<a name="drd-manual.pctw"></a>8.3.3.�pthread_cond_timedwait() and timeouts</h3></div></div></div>

1136

<p>

1137

Historically the function

1138

<code class="function">pthread_cond_timedwait()</code> only allowed the

1139

specification of an absolute timeout, that is a timeout independent of

1140

the time when this function was called. However, almost every call to

1141

this function expresses a relative timeout. This typically happens by

1142

passing the sum of

1143

<code class="computeroutput">clock_gettime(CLOCK_REALTIME)</code> and a

1144

relative timeout as the third argument. This approach is incorrect

1145

since forward or backward clock adjustments by e.g. ntpd will affect

1146

the timeout. A more reliable approach is as follows:

1147

</p>

1148

1149

<li><p>

1150

When initializing a condition variable through

1151

pthread_cond_init(), specify that the timeout of

1152

pthread_cond_timedwait() will use the clock

1153

<code class="literal">CLOCK_MONOTONIC</code> instead of

1154

<code class="literal">CLOCK_REALTIME</code>. You can do this via

1155

<code class="computeroutput">pthread_condattr_setclock(...,

1156

CLOCK_MONOTONIC)</code>.

1157

</p></li>

1158

<li><p>

1159

When calling <code class="function">pthread_cond_timedwait()</code>, pass

1160

the sum of

1161

<code class="computeroutput">clock_gettime(CLOCK_MONOTONIC)</code>

1162

and a relative timeout as the third argument.

1163

</p></li>

1164

</ul></div>

1165

<p>

1166