This file is indexed.

/usr/share/doc/gcc-4.7-base/libitm.html is in gcc-4.7-doc 4.7.3-12ubuntu1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 2011 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with no
Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
A copy of the license is included in the section entitled "GNU
Free Documentation License". -->
<!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU libitm</title>

<meta name="description" content="GNU libitm">
<meta name="keywords" content="GNU libitm">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="#Top" rel="start" title="Top">
<link href="#Index" rel="index" title="Index">
<link href="#SEC_Contents" rel="contents" title="Table of Contents">
<link href="dir.html#Top" rel="up" title="(dir)">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<h1 class="settitle" align="center">GNU libitm</h1>







<a name="SEC_Overview"></a>
<h2 class="shortcontents-heading">Short Table of Contents</h2>

<div class="shortcontents">
<ul class="no-bullet">
<li><a name="stoc-Enabling-libitm-1" href="#toc-Enabling-libitm-1">1 Enabling libitm</a></li>
<li><a name="stoc-C_002fC_002b_002b-Language-Constructs-for-TM-1" href="#toc-C_002fC_002b_002b-Language-Constructs-for-TM-1">2 C/C++ Language Constructs for TM</a></li>
<li><a name="stoc-The-libitm-ABI-1" href="#toc-The-libitm-ABI-1">3 The libitm ABI</a></li>
<li><a name="stoc-Internals-1" href="#toc-Internals-1">4 Internals</a></li>
<li><a name="stoc-GNU-Free-Documentation-License-1" href="#toc-GNU-Free-Documentation-License-1">GNU Free Documentation License</a></li>
<li><a name="stoc-Index-1" href="#toc-Index-1">Index</a></li>
</ul>
</div>

<a name="SEC_Contents"></a>
<h2 class="contents-heading">Table of Contents</h2>

<div class="contents">

<ul class="no-bullet">
  <li><a name="toc-Enabling-libitm-1" href="#Enabling-libitm">1 Enabling libitm</a></li>
  <li><a name="toc-C_002fC_002b_002b-Language-Constructs-for-TM-1" href="#C_002fC_002b_002b-Language-Constructs-for-TM">2 C/C++ Language Constructs for TM</a></li>
  <li><a name="toc-The-libitm-ABI-1" href="#The-libitm-ABI">3 The libitm ABI</a>
  <ul class="no-bullet">
    <li><a name="toc-_005bNo-changes_005d-Objectives" href="#g_t_005bNo-changes_005d-Objectives">3.1 [No changes] Objectives</a></li>
    <li><a name="toc-_005bNo-changes_005d-Non_002dobjectives" href="#g_t_005bNo-changes_005d-Non_002dobjectives">3.2 [No changes] Non-objectives</a></li>
    <li><a name="toc-Library-design-principles" href="#Library-design-principles">3.3 Library design principles</a>
    <ul class="no-bullet">
      <li><a name="toc-_005bNo-changes_005d-Calling-conventions" href="#g_t_005bNo-changes_005d-Calling-conventions">3.3.1 [No changes] Calling conventions</a></li>
      <li><a name="toc-_005bNo-changes_005d-TM-library-algorithms" href="#g_t_005bNo-changes_005d-TM-library-algorithms">3.3.2 [No changes] TM library algorithms</a></li>
      <li><a name="toc-_005bNo-changes_005d-Optimized-load-and-store-routines" href="#g_t_005bNo-changes_005d-Optimized-load-and-store-routines">3.3.3 [No changes] Optimized load and store routines</a></li>
      <li><a name="toc-_005bNo-changes_005d-Aligned-load-and-store-routines" href="#g_t_005bNo-changes_005d-Aligned-load-and-store-routines">3.3.4 [No changes] Aligned load and store routines</a></li>
      <li><a name="toc-Data-logging-functions" href="#Data-logging-functions">3.3.5 Data logging functions</a></li>
      <li><a name="toc-_005bNo-changes_005d-Scatter_002fgather-calls" href="#g_t_005bNo-changes_005d-Scatter_002fgather-calls">3.3.6 [No changes] Scatter/gather calls</a></li>
      <li><a name="toc-_005bNo-changes_005d-Serial-and-irrevocable-mode" href="#g_t_005bNo-changes_005d-Serial-and-irrevocable-mode">3.3.7 [No changes] Serial and irrevocable mode</a></li>
      <li><a name="toc-_005bNo-changes_005d-Transaction-descriptor" href="#g_t_005bNo-changes_005d-Transaction-descriptor">3.3.8 [No changes] Transaction descriptor</a></li>
      <li><a name="toc-Store-allocation" href="#Store-allocation">3.3.9 Store allocation</a></li>
      <li><a name="toc-_005bNo-changes_005d-Naming-conventions" href="#g_t_005bNo-changes_005d-Naming-conventions">3.3.10 [No changes] Naming conventions</a></li>
      <li><a name="toc-Function-pointer-encryption" href="#Function-pointer-encryption">3.3.11 Function pointer encryption</a></li>
    </ul></li>
    <li><a name="toc-Types-and-macros-list" href="#Types-and-macros-list">3.4 Types and macros list</a></li>
    <li><a name="toc-Function-list" href="#Function-list">3.5 Function list</a>
    <ul class="no-bullet">
      <li><a name="toc-Initialization-and-finalization-functions" href="#Initialization-and-finalization-functions">3.5.1 Initialization and finalization functions</a></li>
      <li><a name="toc-_005bNo-changes_005d-Version-checking" href="#g_t_005bNo-changes_005d-Version-checking">3.5.2 [No changes] Version checking</a></li>
      <li><a name="toc-_005bNo-changes_005d-Error-reporting" href="#g_t_005bNo-changes_005d-Error-reporting">3.5.3 [No changes] Error reporting</a></li>
      <li><a name="toc-_005bNo-changes_005d-inTransaction-call" href="#g_t_005bNo-changes_005d-inTransaction-call">3.5.4 [No changes] inTransaction call</a></li>
      <li><a name="toc-State-manipulation-functions" href="#State-manipulation-functions">3.5.5 State manipulation functions</a></li>
      <li><a name="toc-_005bNo-changes_005d-Source-locations" href="#g_t_005bNo-changes_005d-Source-locations">3.5.6 [No changes] Source locations</a></li>
      <li><a name="toc-Starting-a-transaction" href="#Starting-a-transaction">3.5.7 Starting a transaction</a>
      <ul class="no-bullet">
        <li><a name="toc-Transaction-code-properties" href="#Transaction-code-properties">3.5.7.1 Transaction code properties</a></li>
        <li><a name="toc-_005bNo-changes_005d-Windows-exception-state" href="#g_t_005bNo-changes_005d-Windows-exception-state">3.5.7.2 [No changes] Windows exception state</a></li>
        <li><a name="toc-_005bNo-changes_005d-Other-machine-state" href="#g_t_005bNo-changes_005d-Other-machine-state">3.5.7.3 [No changes] Other machine state</a></li>
        <li><a name="toc-_005bNo-changes_005d-Results-from-beginTransaction" href="#g_t_005bNo-changes_005d-Results-from-beginTransaction">3.5.7.4 [No changes] Results from beginTransaction</a></li>
      </ul></li>
      <li><a name="toc-Aborting-a-transaction" href="#Aborting-a-transaction">3.5.8 Aborting a transaction</a></li>
      <li><a name="toc-Committing-a-transaction" href="#Committing-a-transaction">3.5.9 Committing a transaction</a></li>
      <li><a name="toc-Exception-handling-support" href="#Exception-handling-support">3.5.10 Exception handling support</a></li>
      <li><a name="toc-_005bNo-changes_005d-Transition-to-serial_002d_002dirrevocable-mode" href="#g_t_005bNo-changes_005d-Transition-to-serial_002d_002dirrevocable-mode">3.5.11 [No changes] Transition to serial&ndash;irrevocable mode</a></li>
      <li><a name="toc-_005bNo-changes_005d-Data-transfer-functions" href="#g_t_005bNo-changes_005d-Data-transfer-functions">3.5.12 [No changes] Data transfer functions</a></li>
      <li><a name="toc-_005bNo-changes_005d-Transactional-memory-copies" href="#g_t_005bNo-changes_005d-Transactional-memory-copies">3.5.13 [No changes] Transactional memory copies</a></li>
      <li><a name="toc-Transactional-versions-of-memmove" href="#Transactional-versions-of-memmove">3.5.14 Transactional versions of memmove</a></li>
      <li><a name="toc-_005bNo-changes_005d-Transactional-versions-of-memset" href="#g_t_005bNo-changes_005d-Transactional-versions-of-memset">3.5.15 [No changes] Transactional versions of memset</a></li>
      <li><a name="toc-_005bNo-changes_005d-Logging-functions" href="#g_t_005bNo-changes_005d-Logging-functions">3.5.16 [No changes] Logging functions</a></li>
      <li><a name="toc-User_002dregistered-commit-and-undo-actions" href="#User_002dregistered-commit-and-undo-actions">3.5.17 User-registered commit and undo actions</a></li>
      <li><a name="toc-_005bNew_005d-Transactional-indirect-calls" href="#g_t_005bNew_005d-Transactional-indirect-calls">3.5.18 [New] Transactional indirect calls</a></li>
      <li><a name="toc-_005bNew_005d-Transactional-dynamic-memory-management" href="#g_t_005bNew_005d-Transactional-dynamic-memory-management">3.5.19 [New] Transactional dynamic memory management</a></li>
    </ul></li>
    <li><a name="toc-_005bNo-changes_005d-Future-Enhancements-to-the-ABI" href="#g_t_005bNo-changes_005d-Future-Enhancements-to-the-ABI">3.6 [No changes] Future Enhancements to the ABI</a></li>
    <li><a name="toc-Sample-code" href="#Sample-code">3.7 Sample code</a></li>
    <li><a name="toc-_005bNew_005d-Memory-model" href="#g_t_005bNew_005d-Memory-model">3.8 [New] Memory model</a></li>
  </ul></li>
  <li><a name="toc-Internals-1" href="#Internals">4 Internals</a>
  <ul class="no-bullet">
    <li><a name="toc-TM-methods-and-method-groups" href="#TM-methods-and-method-groups">4.1 TM methods and method groups</a>
    <ul class="no-bullet">
      <li><a name="toc-TM-method-life-cycle" href="#TM-method-life-cycle">4.1.1 TM method life cycle</a></li>
      <li><a name="toc-Selecting-the-default-method" href="#Selecting-the-default-method">4.1.2 Selecting the default method</a></li>
    </ul></li>
    <li><a name="toc-Nesting_003a-flat-vs_002e-closed" href="#Nesting_003a-flat-vs_002e-closed">4.2 Nesting: flat vs. closed</a></li>
    <li><a name="toc-Locking-conventions" href="#Locking-conventions">4.3 Locking conventions</a>
    <ul class="no-bullet">
      <li><a name="toc-State_002dto_002dlock-mapping" href="#State_002dto_002dlock-mapping">4.3.1 State-to-lock mapping</a></li>
      <li><a name="toc-Lock-acquisition-order" href="#Lock-acquisition-order">4.3.2 Lock acquisition order</a></li>
      <li><a name="toc-Serial-lock-implementation" href="#Serial-lock-implementation">4.3.3 Serial lock implementation</a></li>
      <li><a name="toc-Reentrancy" href="#Reentrancy">4.3.4 Reentrancy</a></li>
      <li><a name="toc-Privatization-safety" href="#Privatization-safety">4.3.5 Privatization safety</a></li>
      <li><a name="toc-Progress-guarantees" href="#Progress-guarantees">4.3.6 Progress guarantees</a></li>
    </ul></li>
  </ul></li>
  <li><a name="toc-GNU-Free-Documentation-License-1" href="#GNU-Free-Documentation-License">GNU Free Documentation License</a>
  <ul class="no-bullet">
    <li><a name="toc-ADDENDUM_003a-How-to-use-this-License-for-your-documents" href="#ADDENDUM_003a-How-to-use-this-License-for-your-documents">ADDENDUM: How to use this License for your documents</a></li>
  </ul></li>
  <li><a name="toc-Index-1" href="#Index">Index</a></li>
</ul>
</div>



<a name="Top"></a>
<div class="header">
<p>
Next: <a href="#Enabling-libitm" accesskey="n" rel="next">Enabling libitm</a>, Up: <a href="dir.html#Top" accesskey="u" rel="up">(dir)</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="Introduction"></a>
<h1 class="top">Introduction</h1>
<a name="index-Introduction"></a>

<p>This manual documents the usage and internals of libitm, the GNU Transactional
Memory Library. It provides transaction support for accesses to a process&rsquo;
memory, enabling easy-to-use synchronization of accesses to shared memory by
several threads.
</p>

<table class="menu" border="0" cellspacing="0">
<tr><td align="left" valign="top">&bull; <a href="#Enabling-libitm" accesskey="1">Enabling libitm</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">How to enable libitm for your applications.
</td></tr>
<tr><td align="left" valign="top">&bull; <a href="#C_002fC_002b_002b-Language-Constructs-for-TM" accesskey="2">C/C++ Language Constructs for TM</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
                               Notes on the language-level interface supported
                               by gcc.
</td></tr>
<tr><td align="left" valign="top">&bull; <a href="#The-libitm-ABI" accesskey="3">The libitm ABI</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">Notes on the external ABI provided by libitm.
</td></tr>
<tr><td align="left" valign="top">&bull; <a href="#Internals" accesskey="4">Internals</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">Notes on libitm&rsquo;s internal synchronization.
</td></tr>
<tr><td align="left" valign="top">&bull; <a href="#GNU-Free-Documentation-License" accesskey="5">GNU Free Documentation License</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
                               How you can copy and share this manual.
</td></tr>
<tr><td align="left" valign="top">&bull; <a href="#Index" accesskey="6">Index</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">Index of this documentation.
</td></tr>
</table>



<hr>
<a name="Enabling-libitm"></a>
<div class="header">
<p>
Next: <a href="#C_002fC_002b_002b-Language-Constructs-for-TM" accesskey="n" rel="next">C/C++ Language Constructs for TM</a>, Previous: <a href="#Top" accesskey="p" rel="prev">Top</a>, Up: <a href="#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="Enabling-libitm-1"></a>
<h2 class="chapter">1 Enabling libitm</h2>

<p>To activate support for TM in C/C++, the compile-time flag <samp>-fgnu-tm</samp>
must be specified. This enables TM language-level constructs such as
transaction statements (e.g., <code>__transaction_atomic</code>, see <a href="#C_002fC_002b_002b-Language-Constructs-for-TM">C/C++ Language Constructs for TM</a> for details).
</p>

<hr>
<a name="C_002fC_002b_002b-Language-Constructs-for-TM"></a>
<div class="header">
<p>
Next: <a href="#The-libitm-ABI" accesskey="n" rel="next">The libitm ABI</a>, Previous: <a href="#Enabling-libitm" accesskey="p" rel="prev">Enabling libitm</a>, Up: <a href="#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="C_002fC_002b_002b-Language-Constructs-for-TM-1"></a>
<h2 class="chapter">2 C/C++ Language Constructs for TM</h2>

<p>Transactions are supported in C++ and C in the form of transaction statements,
transaction expressions, and function transactions. In the following example,
both <code>a</code> and <code>b</code> will be read and the difference will be written to
<code>c</code>, all atomically and isolated from other transactions:
</p>
<div class="example">
<pre class="example">__transaction_atomic { c = a - b; }
</pre></div>

<p>Therefore, another thread can use the following code to concurrently update
<code>b</code> without ever causing <code>c</code> to hold a negative value (and without
having to use other synchronization constructs such as locks or C++11
atomics):
</p>
<div class="example">
<pre class="example">__transaction_atomic { if (a &gt; b) b++; }
</pre></div>

<p>GCC follows the <a href="https://sites.google.com/site/tmforcplusplus/">Draft
Specification of Transactional Language Constructs for C++ (v1.1)</a> in its
implementation of transactions.
</p>
<p>The precise semantics of transactions are defined in terms of the C++11/C11
memory model (see the specification). Roughly, transactions provide
synchronization guarantees that are similar to what would be guaranteed when
using a single global lock as a guard for all transactions. Note that like
other synchronization constructs in C/C++, transactions rely on a
data-race-free program (e.g., a nontransactional write that is concurrent
with a transactional read to the same memory location is a data race).
</p>

<hr>
<a name="The-libitm-ABI"></a>
<div class="header">
<p>
Next: <a href="#Internals" accesskey="n" rel="next">Internals</a>, Previous: <a href="#C_002fC_002b_002b-Language-Constructs-for-TM" accesskey="p" rel="prev">C/C++ Language Constructs for TM</a>, Up: <a href="#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="The-libitm-ABI-1"></a>
<h2 class="chapter">3 The libitm ABI</h2>

<p>The ABI provided by libitm is basically equal to the Linux variant of Intel&rsquo;s
current TM ABI specification document (Revision 1.1, May 6 2009) but with the
differences listed in this chapter. It would be good if these changes would
eventually be merged into a future version of this specification. To ease
look-up, the following subsections mirror the structure of this specification.
</p>
<a name="g_t_005bNo-changes_005d-Objectives"></a>
<h3 class="section">3.1 [No changes] Objectives</h3>
<a name="g_t_005bNo-changes_005d-Non_002dobjectives"></a>
<h3 class="section">3.2 [No changes] Non-objectives</h3>

<a name="Library-design-principles"></a>
<h3 class="section">3.3 Library design principles</h3>
<a name="g_t_005bNo-changes_005d-Calling-conventions"></a>
<h4 class="subsection">3.3.1 [No changes] Calling conventions</h4>
<a name="g_t_005bNo-changes_005d-TM-library-algorithms"></a>
<h4 class="subsection">3.3.2 [No changes] TM library algorithms</h4>
<a name="g_t_005bNo-changes_005d-Optimized-load-and-store-routines"></a>
<h4 class="subsection">3.3.3 [No changes] Optimized load and store routines</h4>
<a name="g_t_005bNo-changes_005d-Aligned-load-and-store-routines"></a>
<h4 class="subsection">3.3.4 [No changes] Aligned load and store routines</h4>

<a name="Data-logging-functions"></a>
<h4 class="subsection">3.3.5 Data logging functions</h4>

<p>The memory locations accessed with transactional loads and stores and the
memory locations whose values are logged must not overlap. This required
separation only extends to the scope of the execution of one transaction
including all the executions of all nested transactions.
</p>
<p>The compiler must be consistent (within the scope of a single transaction)
about which memory locations are shared and which are not shared with other
threads (i.e., data must be accessed either transactionally or
nontransactionally). Otherwise, non-write-through TM algorithms would not work.
</p>
<a name="g_t_005bNo-changes_005d-Scatter_002fgather-calls"></a>
<h4 class="subsection">3.3.6 [No changes] Scatter/gather calls</h4>
<a name="g_t_005bNo-changes_005d-Serial-and-irrevocable-mode"></a>
<h4 class="subsection">3.3.7 [No changes] Serial and irrevocable mode</h4>
<a name="g_t_005bNo-changes_005d-Transaction-descriptor"></a>
<h4 class="subsection">3.3.8 [No changes] Transaction descriptor</h4>
<a name="Store-allocation"></a>
<h4 class="subsection">3.3.9 Store allocation</h4>

<p>There is no <code>getTransaction</code> function. 
</p>
<a name="g_t_005bNo-changes_005d-Naming-conventions"></a>
<h4 class="subsection">3.3.10 [No changes] Naming conventions</h4>

<a name="Function-pointer-encryption"></a>
<h4 class="subsection">3.3.11 Function pointer encryption</h4>

<p>Currently, this is not implemented.
</p>

<a name="Types-and-macros-list"></a>
<h3 class="section">3.4 Types and macros list</h3>

<p><code>_ITM_codeProperties</code> has changed, see <a href="#txn_002dcode_002dproperties">Starting a
transaction</a>.
<code>_ITM_srcLocation</code> is not used. 
</p>

<a name="Function-list"></a>
<h3 class="section">3.5 Function list</h3>

<a name="Initialization-and-finalization-functions"></a>
<h4 class="subsection">3.5.1 Initialization and finalization functions</h4>
<p>These functions are not part of the ABI.
</p>
<a name="g_t_005bNo-changes_005d-Version-checking"></a>
<h4 class="subsection">3.5.2 [No changes] Version checking</h4>
<a name="g_t_005bNo-changes_005d-Error-reporting"></a>
<h4 class="subsection">3.5.3 [No changes] Error reporting</h4>
<a name="g_t_005bNo-changes_005d-inTransaction-call"></a>
<h4 class="subsection">3.5.4 [No changes] inTransaction call</h4>

<a name="State-manipulation-functions"></a>
<h4 class="subsection">3.5.5 State manipulation functions</h4>
<p>There is no <code>getTransaction</code> function. Transaction identifiers for
nested transactions will be ordered but not necessarily sequential (i.e., for
a nested transaction&rsquo;s identifier <var>IN</var> and its enclosing transaction&rsquo;s
identifier <var>IE</var>, it is guaranteed that <em>IN &gt;= IE</em>).
</p>
<a name="g_t_005bNo-changes_005d-Source-locations"></a>
<h4 class="subsection">3.5.6 [No changes] Source locations</h4>

<a name="Starting-a-transaction"></a>
<h4 class="subsection">3.5.7 Starting a transaction</h4>

<a name="Transaction-code-properties"></a>
<h4 class="subsubsection">3.5.7.1 Transaction code properties</h4>

<a name="txn_002dcode_002dproperties"></a><p>The bit <code>hasNoXMMUpdate</code> is instead called <code>hasNoVectorUpdate</code>.
Iff it is set, vector register save/restore is not necessary for any target
machine.
</p>
<p>The <code>hasNoFloatUpdate</code> bit (<code>0x0010</code>) is new. Iff it is set, floating
point register save/restore is not necessary for any target machine.
</p>
<p><code>undoLogCode</code> is not supported and a fatal runtime error will be raised
if this bit is set. It is not properly defined in the ABI why barriers
other than undo logging are not present; Are they not necessary (e.g., a
transaction operating purely on thread-local data) or have they been omitted by
the compiler because it thinks that some kind of global synchronization
(e.g., serial mode) might perform better? The specification suggests that the
latter might be the case, but the former seems to be more useful.
</p>
<p>The <code>readOnly</code> bit (<code>0x4000</code>) is new. <strong>TODO</strong> Lexical or dynamic
scope?
</p>
<p><code>hasNoRetry</code> is not supported. If this bit is not set, but
<code>hasNoAbort</code> is set, the library can assume that transaction
rollback will not be requested.
</p>
<p>It would be useful if the absence of externally-triggered rollbacks would be
reported for the dynamic scope as well, not just for the lexical scope
(<code>hasNoAbort</code>). Without this, a library cannot exploit this together
with flat nesting.
</p>
<p><code>exceptionBlock</code> is not supported because exception blocks are not used.
</p>
<a name="g_t_005bNo-changes_005d-Windows-exception-state"></a>
<h4 class="subsubsection">3.5.7.2 [No changes] Windows exception state</h4>
<a name="g_t_005bNo-changes_005d-Other-machine-state"></a>
<h4 class="subsubsection">3.5.7.3 [No changes] Other machine state</h4>

<a name="g_t_005bNo-changes_005d-Results-from-beginTransaction"></a>
<h4 class="subsubsection">3.5.7.4 [No changes] Results from beginTransaction</h4>

<a name="Aborting-a-transaction"></a>
<h4 class="subsection">3.5.8 Aborting a transaction</h4>

<p><code>_ITM_rollbackTransaction</code> is not supported. <code>_ITM_abortTransaction</code>
is supported but the abort reasons <code>exceptionBlockAbort</code>,
<code>TMConflict</code>, and <code>userRetry</code> are not supported. There are no
exception blocks in general, so the related cases also do not have to be
considered. To encode <code>__transaction_cancel [[outer]]</code>, compilers must
set the new <code>outerAbort</code> bit (<code>0x10</code>) additionally to the
<code>userAbort</code> bit in the abort reason.
</p>
<a name="Committing-a-transaction"></a>
<h4 class="subsection">3.5.9 Committing a transaction</h4>

<p>The exception handling (EH) scheme is different. The Intel ABI requires the
<code>_ITM_tryCommitTransaction</code> function that will return even when the
commit failed and will have to be matched with calls to either
<code>_ITM_abortTransaction</code> or <code>_ITM_commitTransaction</code>. In contrast,
gcc relies on transactional wrappers for the functions of the Exception
Handling ABI and on one additional commit function (shown below). This allows
the TM to keep track of EH internally and thus it does not have to embed the
cleanup of EH state into the existing EH code in the program.
<code>_ITM_tryCommitTransaction</code> is not supported.
<code>_ITM_commitTransactionToId</code> is also not supported because the
propagation of thrown exceptions will not bypass commits of nested
transactions.
</p>
<div class="example">
<pre class="example">void _ITM_commitTransactionEH(void *exc_ptr) ITM_REGPARM;
void *_ITM_cxa_allocate_exception (size_t);
void _ITM_cxa_throw (void *obj, void *tinfo, void *dest);
void *_ITM_cxa_begin_catch (void *exc_ptr);
void _ITM_cxa_end_catch (void);
</pre></div>

<p><code>_ITM_commitTransactionEH</code> must be called to commit a transaction if an
exception could be in flight at this position in the code. <code>exc_ptr</code> is
the current exception or zero if there is no current exception.
The <code>_ITM_cxa...</code> functions are transactional wrappers for the respective
<code>__cxa...</code> functions and must be called instead of these in transactional
code.
</p>
<p>To support this EH scheme, libstdc++ needs to provide one additional function
(<code>_cxa_tm_cleanup</code>), which is used by the TM to clean up the exception
handling state while rolling back a transaction:
</p>
<div class="example">
<pre class="example">void __cxa_tm_cleanup (void *unthrown_obj, void *cleanup_exc,
                       unsigned int caught_count);
</pre></div>

<p><code>unthrown_obj</code> is non-null if the program called
<code>__cxa_allocate_exception</code> for this exception but did not yet called
<code>__cxa_throw</code> for it. <code>cleanup_exc</code> is non-null if the program is
currently processing a cleanup along an exception path but has not caught this
exception yet. <code>caught_count</code> is the nesting depth of
<code>__cxa_begin_catch</code> within the transaction (which can be counted by the TM
using <code>_ITM_cxa_begin_catch</code> and <code>_ITM_cxa_end_catch</code>);
<code>__cxa_tm_cleanup</code> then performs rollback by essentially performing
<code>__cxa_end_catch</code> that many times.
</p>


<a name="Exception-handling-support"></a>
<h4 class="subsection">3.5.10 Exception handling support</h4>

<p>Currently, there is no support for functionality like
<code>__transaction_cancel throw</code> as described in the C++ TM specification.
Supporting this should be possible with the EH scheme explained previously
because via the transactional wrappers for the EH ABI, the TM is able to
observe and intercept EH.
</p>

<a name="g_t_005bNo-changes_005d-Transition-to-serial_002d_002dirrevocable-mode"></a>
<h4 class="subsection">3.5.11 [No changes] Transition to serial&ndash;irrevocable mode</h4>
<a name="g_t_005bNo-changes_005d-Data-transfer-functions"></a>
<h4 class="subsection">3.5.12 [No changes] Data transfer functions</h4>
<a name="g_t_005bNo-changes_005d-Transactional-memory-copies"></a>
<h4 class="subsection">3.5.13 [No changes] Transactional memory copies</h4>

<a name="Transactional-versions-of-memmove"></a>
<h4 class="subsection">3.5.14 Transactional versions of memmove</h4>

<p>If either the source or destination memory region is to be accessed
nontransactionally, then source and destination regions must not be
overlapping. The respective <code>_ITM_memmove</code> functions are still
available but a fatal runtime error will be raised if such regions do overlap.
To support this functionality, the ABI would have to specify how the
intersection of the regions has to be accessed (i.e., transactionally or
nontransactionally).
</p>
<a name="g_t_005bNo-changes_005d-Transactional-versions-of-memset"></a>
<h4 class="subsection">3.5.15 [No changes] Transactional versions of memset</h4>
<a name="g_t_005bNo-changes_005d-Logging-functions"></a>
<h4 class="subsection">3.5.16 [No changes] Logging functions</h4>

<a name="User_002dregistered-commit-and-undo-actions"></a>
<h4 class="subsection">3.5.17 User-registered commit and undo actions</h4>

<p>Commit actions will get executed in the same order in which the respective
calls to <code>_ITM_addUserCommitAction</code> happened. Only
<code>_ITM_noTransactionId</code> is allowed as value for the
<code>resumingTransactionId</code> argument. Commit actions get executed after
privatization safety has been ensured.
</p>
<p>Undo actions will get executed in reverse order compared to the order in which
the respective calls to <code>_ITM_addUserUndoAction</code> happened. The ordering of
undo actions w.r.t. the roll-back of other actions (e.g., data transfers or
memory allocations) is undefined.
</p>
<p><code>_ITM_getThreadnum</code> is not supported currently because its only purpose
is to provide a thread ID that matches some assumed performance tuning output,
but this output is not part of the ABI nor further defined by it.
</p>
<p><code>_ITM_dropReferences</code> is not supported currently because its semantics and
the intention behind it is not entirely clear. The
specification suggests that this function is necessary because of certain
orderings of data transfer undos and the releasing of memory regions (i.e.,
privatization). However, this ordering is never defined, nor is the ordering of
dropping references w.r.t. other events.
</p>
<a name="g_t_005bNew_005d-Transactional-indirect-calls"></a>
<h4 class="subsection">3.5.18 [New] Transactional indirect calls</h4>

<p>Indirect calls (i.e., calls through a function pointer) within transactions
should execute the transactional clone of the original function (i.e., a clone
of the original that has been fully instrumented to use the TM runtime), if
such a clone is available. The runtime provides two functions to
register/deregister clone tables:
</p>
<div class="example">
<pre class="example">struct clone_entry
{
  void *orig, *clone;
};

void _ITM_registerTMCloneTable (clone_entry *table, size_t entries);
void _ITM_deregisterTMCloneTable (clone_entry *table);
</pre></div>

<p>Registered tables must be writable by the TM runtime, and must be live
throughout the life-time of the TM runtime.
</p>
<p><strong>TODO</strong> The intention was always to drop the registration functions
entirely, and create a new ELF Phdr describing the linker-sorted table.  Much
like what currently happens for <code>PT_GNU_EH_FRAME</code>.
This work kept getting bogged down in how to represent the <var>N</var> different
code generation variants.  We clearly needed at least two&mdash;SW and HW
transactional clones&mdash;but there was always a suggestion of more variants for
different TM assumptions/invariants.
</p>
<p>The compiler can then use two TM runtime functions to perform indirect calls in
transactions:
</p><div class="example">
<pre class="example">void *_ITM_getTMCloneOrIrrevocable (void *function) ITM_REGPARM;
void *_ITM_getTMCloneSafe (void *function) ITM_REGPARM;
</pre></div>

<p>If there is a registered clone for supplied function, both will return a
pointer to the clone. If not, the first runtime function will attempt to switch
to serial&ndash;irrevocable mode and return the original pointer, whereas the second
will raise a fatal runtime error.
</p>
<a name="g_t_005bNew_005d-Transactional-dynamic-memory-management"></a>
<h4 class="subsection">3.5.19 [New] Transactional dynamic memory management</h4>

<div class="example">
<pre class="example">void *_ITM_malloc (size_t)
       __attribute__((__malloc__)) ITM_PURE;
void *_ITM_calloc (size_t, size_t)
       __attribute__((__malloc__)) ITM_PURE;
void _ITM_free (void *) ITM_PURE;
</pre></div>

<p>These functions are essentially transactional wrappers for <code>malloc</code>,
<code>calloc</code>, and <code>free</code>. Within transactions, the compiler should
replace calls to the original functions with calls to the wrapper functions.
</p>

<a name="g_t_005bNo-changes_005d-Future-Enhancements-to-the-ABI"></a>
<h3 class="section">3.6 [No changes] Future Enhancements to the ABI</h3>

<a name="Sample-code"></a>
<h3 class="section">3.7 Sample code</h3>

<p>The code examples might not be correct w.r.t. the current version of the ABI,
especially everything related to exception handling.
</p>

<a name="g_t_005bNew_005d-Memory-model"></a>
<h3 class="section">3.8 [New] Memory model</h3>

<p>The ABI should define a memory model and the ordering that is guaranteed for
data transfers and commit/undo actions, or at least refer to another memory
model that needs to be preserved. Without that, the compiler cannot ensure the
memory model specified on the level of the programming language (e.g., by the
C++ TM specification).
</p>
<p>For example, if a transactional load is ordered before another load/store, then
the TM runtime must also ensure this ordering when accessing shared state. If
not, this might break the kind of publication safety used in the C++ TM
specification. Likewise, the TM runtime must ensure privatization safety.
</p>



<hr>
<a name="Internals"></a>
<div class="header">
<p>
Next: <a href="#GNU-Free-Documentation-License" accesskey="n" rel="next">GNU Free Documentation License</a>, Previous: <a href="#The-libitm-ABI" accesskey="p" rel="prev">The libitm ABI</a>, Up: <a href="#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="Internals-1"></a>
<h2 class="chapter">4 Internals</h2>

<a name="TM-methods-and-method-groups"></a>
<h3 class="section">4.1 TM methods and method groups</h3>

<p>libitm supports several ways of synchronizing transactions with each other.
These TM methods (or TM algorithms) are implemented in the form of
subclasses of <code>abi_dispatch</code>, which provide methods for
transactional loads and stores as well as callbacks for rollback and commit.
All methods that are compatible with each other (i.e., that let concurrently
running transactions still synchronize correctly even if different methods
are used) belong to the same TM method group. Pointers to TM methods can be
obtained using the factory methods prefixed with <code>dispatch_</code> in
<samp>libitm_i.h</samp>. There are two special methods, <code>dispatch_serial</code> and
<code>dispatch_serialirr</code>, that are compatible with all methods because they
run transactions completely in serial mode.
</p>
<a name="TM-method-life-cycle"></a>
<h4 class="subsection">4.1.1 TM method life cycle</h4>

<p>The state of TM methods does not change after construction, but they do alter
the state of transactions that use this method. However, because
per-transaction data gets used by several methods, <code>gtm_thread</code> is
responsible for setting an initial state that is useful for all methods.
After that, methods are responsible for resetting/clearing this state on each
rollback or commit (of outermost transactions), so that the transaction
executed next is not affected by the previous transaction.
</p>
<p>There is also global state associated with each method group, which is
initialized and shut down (<code>method_group::init()</code> and <code>fini()</code>)
when switching between method groups (see <samp>retry.cc</samp>).
</p>
<a name="Selecting-the-default-method"></a>
<h4 class="subsection">4.1.2 Selecting the default method</h4>

<p>The default method that libitm uses for freshly started transactions (but
not necessarily for restarted transactions) can be set via an environment
variable (<code>ITM_DEFAULT_METHOD</code>), whose value should be equal to the name
of one of the factory methods returning abi_dispatch subclasses but without
the &quot;dispatch_&quot; prefix (e.g., &quot;serialirr&quot; instead of
<code>GTM::dispatch_serialirr()</code>).
</p>
<p>Note that this environment variable is only a hint for libitm and might not
be supported in the future.
</p>

<a name="Nesting_003a-flat-vs_002e-closed"></a>
<h3 class="section">4.2 Nesting: flat vs. closed</h3>

<p>We support two different kinds of nesting of transactions. In the case of
<em>flat nesting</em>, the nesting structure is flattened and all nested
transactions are subsumed by the enclosing transaction. In contrast,
with <em>closed nesting</em>, nested transactions that have not yet committed
can be rolled back separately from the enclosing transactions; when they
commit, they are subsumed by the enclosing transaction, and their effects
will be finally committed when the outermost transaction commits.
<em>Open nesting</em> (where nested transactions can commit independently of the
enclosing transactions) are not supported.
</p>
<p>Flat nesting is the default nesting mode, but closed nesting is supported and
used when transactions contain user-controlled aborts
(<code>__transaction_cancel</code> statements). We assume that user-controlled
aborts are rare in typical code and used mostly in exceptional situations.
Thus, it makes more sense to use flat nesting by default to avoid the
performance overhead of the additional checkpoints required for closed
nesting. User-controlled aborts will correctly abort the innermost enclosing
transaction, whereas the whole (i.e., outermost) transaction will be restarted
otherwise (e.g., when a transaction encounters data conflicts during
optimistic execution).
</p>

<a name="Locking-conventions"></a>
<h3 class="section">4.3 Locking conventions</h3>

<p>This section documents the locking scheme and rules for all uses of locking
in libitm. We have to support serial(-irrevocable) mode, which is implemented
using a global lock as explained next (called the <em>serial lock</em>). To
simplify the overall design, we use the same lock as catch-all locking
mechanism for other infrequent tasks such as (de)registering clone tables or
threads. Besides the serial lock, there are <em>per-method-group locks</em> that
are managed by specific method groups (i.e., groups of similar TM concurrency
control algorithms), and lock-like constructs for quiescence-based operations
such as ensuring privatization safety.
</p>
<p>Thus, the actions that participate in the libitm-internal locking are either
<em>active transactions</em> that do not run in serial mode, <em>serial
transactions</em> (which (are about to) run in serial mode), and management tasks
that do not execute within a transaction but have acquired the serial mode
like a serial transaction would do (e.g., to be able to register threads with
libitm). Transactions become active as soon as they have successfully used the
serial lock to announce this globally (see <a href="#serial_002dlock_002dimpl">Serial lock
implementation</a>). Likewise, transactions become serial transactions as soon as
they have acquired the exclusive rights provided by the serial lock (i.e.,
serial mode, which also means that there are no other concurrent active or
serial transactions). Note that active transactions can become serial
transactions when they enter serial mode during the runtime of the
transaction.
</p>
<a name="State_002dto_002dlock-mapping"></a>
<h4 class="subsection">4.3.1 State-to-lock mapping</h4>

<p>Application data is protected by the serial lock if there is a serial
transaction and no concurrently running active transaction (i.e., non-serial).
Otherwise, application data is protected by the currently selected method
group, which might use per-method-group locks or other mechanisms. Also note
that application data that is about to be privatized might not be allowed to be
accessed by nontransactional code until privatization safety has been ensured;
the details of this are handled by the current method group.
</p>
<p>libitm-internal state is either protected by the serial lock or accessed
through custom concurrent code. The latter applies to the public/shared part
of a transaction object and most typical method-group-specific state.
</p>
<p>The former category (protected by the serial lock) includes:
</p><ul>
<li> The list of active threads that have used transactions.
</li><li> The tables that map functions to their transactional clones.
</li><li> The current selection of which method group to use.
</li><li> Some method-group-specific data, or invariants of this data. For example,
resetting a method group to its initial state is handled by switching to the
same method group, so the serial lock protects such resetting as well.
</li></ul>
<p>In general, such state is immutable whenever there exists an active
(non-serial) transaction. If there is no active transaction, a serial
transaction (or a thread that is not currently executing a transaction but has
acquired the serial lock) is allowed to modify this state (but must of course
be careful to not surprise the current method group&rsquo;s implementation with such
modifications).
</p>
<a name="Lock-acquisition-order"></a>
<h4 class="subsection">4.3.2 Lock acquisition order</h4>

<p>To prevent deadlocks, locks acquisition must happen in a globally agreed-upon
order. Note that this applies to other forms of blocking too, but does not
necessarily apply to lock acquisitions that do not block (e.g., trylock()
calls that do not get retried forever). Note that serial transactions are
never return back to active transactions until the transaction has committed.
Likewise, active transactions stay active until they have committed.
Per-method-group locks are typically also not released before commit.
</p>
<p>Lock acquisition / blocking rules:
</p><ul>
<li> Transactions must become active or serial before they are allowed to
use method-group-specific locks or blocking (i.e., the serial lock must be
acquired before those other locks, either in serial or nonserial mode).

</li><li> Any number of threads that do not currently run active transactions can
block while trying to get the serial lock in exclusive mode. Note that active
transactions must not block when trying to upgrade to serial mode unless there
is no other transaction that is trying that (the latter is ensured by the
serial lock implementation.

</li><li> Method groups must prevent deadlocks on their locks. In particular, they
must also be prepared for another active transaction that has acquired
method-group-specific locks but is blocked during an attempt to upgrade to
being a serial transaction. See below for details.

</li><li> Serial transactions can acquire method-group-specific locks because there
will be no other active nor serial transaction.

</li></ul>

<p>There is no single rule for per-method-group blocking because this depends on
when a TM method might acquire locks. If no active transaction can upgrade to
being a serial transaction after it has acquired per-method-group locks (e.g.,
when those locks are only acquired during an attempt to commit), then the TM
method does not need to consider a potential deadlock due to serial mode.
</p>
<p>If there can be upgrades to serial mode after the acquisition of
per-method-group locks, then TM methods need to avoid those deadlocks:
</p><ul>
<li> When upgrading to a serial transaction, after acquiring exclusive rights
to the serial lock but before waiting for concurrent active transactions to
finish (see <a href="#serial_002dlock_002dimpl">Serial lock implementation</a> for details),
we have to wake up all active transactions waiting on the upgrader&rsquo;s
per-method-group locks.
</li><li> Active transactions blocking on per-method-group locks need to check the
serial lock and abort if there is a pending serial transaction.
</li><li> Lost wake-ups have to be prevented (e.g., by changing a bit in each
per-method-group lock before doing the wake-up, and only blocking on this lock
using a futex if this bit is not group).
</li></ul>

<p><strong>TODO</strong>: Can reuse serial lock for gl-*? And if we can, does it make
sense to introduce further complexity in the serial lock? For gl-*, we can
really only avoid an abort if we do -wb and -vbv.
</p>

<a name="Serial-lock-implementation"></a>
<h4 class="subsection">4.3.3 Serial lock implementation</h4>
<a name="serial_002dlock_002dimpl"></a>
<p>The serial lock implementation is optimized towards assuming that serial
transactions are infrequent and not the common case. However, the performance
of entering serial mode can matter because when only few transactions are run
concurrently or if there are few threads, then it can be efficient to run
transactions serially.
</p>
<p>The serial lock is similar to a multi-reader-single-writer lock in that there
can be several active transactions but only one serial transaction. However,
we do want to avoid contention (in the lock implementation) between active
transactions, so we split up the reader side of the lock into per-transaction
flags that are true iff the transaction is active. The exclusive writer side
remains a shared single flag, which is acquired using a CAS, for example.
On the fast-path, the serial lock then works similar to Dekker&rsquo;s algorithm but
with several reader flags that a serial transaction would have to check.
A serial transaction thus requires a list of all threads with potentially
active transactions; we can use the serial lock itself to protect this list
(i.e., only threads that have acquired the serial lock can modify this list).
</p>
<p>We want starvation-freedom for the serial lock to allow for using it to ensure
progress for potentially starved transactions (see <a href="#progress_002dguarantees">Progress Guarantees</a> for details). However, this is currently not enforced by
the implementation of the serial lock.
</p>
<p>Here is pseudo-code for the read/write fast paths of acquiring the serial
lock (read-to-write upgrade is similar to write_lock:
</p><div class="example">
<pre class="example">// read_lock:
tx-&gt;shared_state |= active;
__sync_synchronize(); // or STLD membar, or C++0x seq-cst fence
while (!serial_lock.exclusive)
  if (spinning_for_too_long) goto slowpath;

// write_lock:
if (CAS(&amp;serial_lock.exclusive, 0, this) != 0)
  goto slowpath; // writer-writer contention
// need a membar here, but CAS already has full membar semantics
bool need_blocking = false;
for (t: all txns)
  {
    for (;t-&gt;shared_state &amp; active;)
      if (spinning_for_too_long) { need_blocking = true; break; }
  }
if (need_blocking) goto slowpath;
</pre></div>

<p>Releasing a lock in this spin-lock version then just consists of resetting
<code>tx-&gt;shared_state</code> to inactive or clearing <code>serial_lock.exclusive</code>.
</p>
<p>However, we can&rsquo;t rely on a pure spinlock because we need to get the OS
involved at some time (e.g., when there are more threads than CPUs to run on).
Therefore, the real implementation falls back to a blocking slow path, either
based on pthread mutexes or Linux futexes.
</p>

<a name="Reentrancy"></a>
<h4 class="subsection">4.3.4 Reentrancy</h4>

<p>libitm has to consider the following cases of reentrancy:
</p><ul>
<li> Transaction calls unsafe code that starts a new transaction: The outer
transaction will become a serial transaction before executing unsafe code.
Therefore, nesting within serial transactions must work, even if the nested
transaction is called from within uninstrumented code.

</li><li> Transaction calls either a transactional wrapper or safe code, which in
turn starts a new transaction: It is not yet defined in the specification
whether this is allowed. Thus, it is undefined whether libitm supports this.

</li><li> Code that starts new transactions might be called from within any part
of libitm: This kind of reentrancy would likely be rather complex and can
probably be avoided. Therefore, it is not supported.

</li></ul>

<a name="Privatization-safety"></a>
<h4 class="subsection">4.3.5 Privatization safety</h4>

<p>Privatization safety is ensured by libitm using a quiescence-based approach.
Basically, a privatizing transaction waits until all concurrent active
transactions will either have finished (are not active anymore) or operate on
a sufficiently recent snapshot to not access the privatized data anymore. This
happens after the privatizing transaction has stopped being an active
transaction, so waiting for quiescence does not contribute to deadlocks.
</p>
<p>In method groups that need to ensure publication safety explicitly, active
transactions maintain a flag or timestamp in the public/shared part of the
transaction descriptor. Before blocking, privatizers need to let the other
transactions know that they should wake up the privatizer.
</p>
<p><strong>TODO</strong> Ho to implement the waiters? Should those flags be
per-transaction or at a central place? We want to avoid one wake/wait call
per active transactions, so we might want to use either a tree or combining
to reduce the syscall overhead, or rather spin for a long amount of time
instead of doing blocking. Also, it would be good if only the last transaction
that the privatizer waits for would do the wake-up.
</p>
<a name="Progress-guarantees"></a>
<h4 class="subsection">4.3.6 Progress guarantees</h4>
<a name="progress_002dguarantees"></a>
<p>Transactions that do not make progress when using the current TM method will
eventually try to execute in serial mode. Thus, the serial lock&rsquo;s progress
guarantees determine the progress guarantees of the whole TM. Obviously, we at
least need deadlock-freedom for the serial lock, but it would also be good to
provide starvation-freedom (informally, all threads will finish executing a
transaction eventually iff they get enough cycles).
</p>
<p>However, the scheduling of transactions (e.g., thread scheduling by the OS)
also affects the handling of progress guarantees by the TM. First, the TM
can only guarantee deadlock-freedom if threads do not get stopped. Likewise,
low-priority threads can starve if they do not get scheduled when other
high-priority threads get those cycles instead.
</p>
<p>If all threads get scheduled eventually, correct lock implementations will
provide deadlock-freedom, but might not provide starvation-freedom. We can
either enforce the latter in the TM&rsquo;s lock implementation, or assume that
the scheduling is sufficiently random to yield a probabilistic guarantee that
no thread will starve (because eventually, a transaction will encounter a
scheduling that will allow it to run). This can indeed work well in practice
but is not necessarily guaranteed to work (e.g., simple spin locks can be
pretty efficient).
</p>
<p>Because enforcing stronger progress guarantees in the TM has a higher runtime
overhead, we focus on deadlock-freedom right now and assume that the threads
will get scheduled eventually by the OS (but don&rsquo;t consider threads with
different priorities). We should support starvation-freedom for serial
transactions in the future. Everything beyond that is highly related to proper
contention management across all of the TM (including with TM method to
choose), and is future work.
</p>
<p><strong>TODO</strong> Handling thread priorities: We want to avoid priority inversion
but it&rsquo;s unclear how often that actually matters in practice. Workloads that
have threads with different priorities will likely also require lower latency
or higher throughput for high-priority threads. Therefore, it probably makes
not that much sense (except for eventual progress guarantees) to use
priority inheritance until the TM has priority-aware contention management.
</p>


<hr>
<a name="GNU-Free-Documentation-License"></a>
<div class="header">
<p>
Next: <a href="#Index" accesskey="n" rel="next">Index</a>, Previous: <a href="#Internals" accesskey="p" rel="prev">Internals</a>, Up: <a href="#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="GNU-Free-Documentation-License-1"></a>
<h2 class="unnumbered">GNU Free Documentation License</h2>

<a name="index-FDL_002c-GNU-Free-Documentation-License"></a>
<div align="center">Version 1.3, 3 November 2008
</div>
<div class="display">
<pre class="display">Copyright &copy; 2000, 2001, 2002, 2007, 2008 Free Software Foundation, Inc.
<a href="http://fsf.org/">http://fsf.org/</a>

Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.
</pre></div>

<ol>
<li> PREAMBLE

<p>The purpose of this License is to make a manual, textbook, or other
functional and useful document <em>free</em> in the sense of freedom: to
assure everyone the effective freedom to copy and redistribute it,
with or without modifying it, either commercially or noncommercially.
Secondarily, this License preserves for the author and publisher a way
to get credit for their work, while not being considered responsible
for modifications made by others.
</p>
<p>This License is a kind of &ldquo;copyleft&rdquo;, which means that derivative
works of the document must themselves be free in the same sense.  It
complements the GNU General Public License, which is a copyleft
license designed for free software.
</p>
<p>We have designed this License in order to use it for manuals for free
software, because free software needs free documentation: a free
program should come with manuals providing the same freedoms that the
software does.  But this License is not limited to software manuals;
it can be used for any textual work, regardless of subject matter or
whether it is published as a printed book.  We recommend this License
principally for works whose purpose is instruction or reference.
</p>
</li><li> APPLICABILITY AND DEFINITIONS

<p>This License applies to any manual or other work, in any medium, that
contains a notice placed by the copyright holder saying it can be
distributed under the terms of this License.  Such a notice grants a
world-wide, royalty-free license, unlimited in duration, to use that
work under the conditions stated herein.  The &ldquo;Document&rdquo;, below,
refers to any such manual or work.  Any member of the public is a
licensee, and is addressed as &ldquo;you&rdquo;.  You accept the license if you
copy, modify or distribute the work in a way requiring permission
under copyright law.
</p>
<p>A &ldquo;Modified Version&rdquo; of the Document means any work containing the
Document or a portion of it, either copied verbatim, or with
modifications and/or translated into another language.
</p>
<p>A &ldquo;Secondary Section&rdquo; is a named appendix or a front-matter section
of the Document that deals exclusively with the relationship of the
publishers or authors of the Document to the Document&rsquo;s overall
subject (or to related matters) and contains nothing that could fall
directly within that overall subject.  (Thus, if the Document is in
part a textbook of mathematics, a Secondary Section may not explain
any mathematics.)  The relationship could be a matter of historical
connection with the subject or with related matters, or of legal,
commercial, philosophical, ethical or political position regarding
them.
</p>
<p>The &ldquo;Invariant Sections&rdquo; are certain Secondary Sections whose titles
are designated, as being those of Invariant Sections, in the notice
that says that the Document is released under this License.  If a
section does not fit the above definition of Secondary then it is not
allowed to be designated as Invariant.  The Document may contain zero
Invariant Sections.  If the Document does not identify any Invariant
Sections then there are none.
</p>
<p>The &ldquo;Cover Texts&rdquo; are certain short passages of text that are listed,
as Front-Cover Texts or Back-Cover Texts, in the notice that says that
the Document is released under this License.  A Front-Cover Text may
be at most 5 words, and a Back-Cover Text may be at most 25 words.
</p>
<p>A &ldquo;Transparent&rdquo; copy of the Document means a machine-readable copy,
represented in a format whose specification is available to the
general public, that is suitable for revising the document
straightforwardly with generic text editors or (for images composed of
pixels) generic paint programs or (for drawings) some widely available
drawing editor, and that is suitable for input to text formatters or
for automatic translation to a variety of formats suitable for input
to text formatters.  A copy made in an otherwise Transparent file
format whose markup, or absence of markup, has been arranged to thwart
or discourage subsequent modification by readers is not Transparent.
An image format is not Transparent if used for any substantial amount
of text.  A copy that is not &ldquo;Transparent&rdquo; is called &ldquo;Opaque&rdquo;.
</p>
<p>Examples of suitable formats for Transparent copies include plain
<small>ASCII</small> without markup, Texinfo input format, LaTeX input
format, <acronym>SGML</acronym> or <acronym>XML</acronym> using a publicly available
<acronym>DTD</acronym>, and standard-conforming simple <acronym>HTML</acronym>,
PostScript or <acronym>PDF</acronym> designed for human modification.  Examples
of transparent image formats include <acronym>PNG</acronym>, <acronym>XCF</acronym> and
<acronym>JPG</acronym>.  Opaque formats include proprietary formats that can be
read and edited only by proprietary word processors, <acronym>SGML</acronym> or
<acronym>XML</acronym> for which the <acronym>DTD</acronym> and/or processing tools are
not generally available, and the machine-generated <acronym>HTML</acronym>,
PostScript or <acronym>PDF</acronym> produced by some word processors for
output purposes only.
</p>
<p>The &ldquo;Title Page&rdquo; means, for a printed book, the title page itself,
plus such following pages as are needed to hold, legibly, the material
this License requires to appear in the title page.  For works in
formats which do not have any title page as such, &ldquo;Title Page&rdquo; means
the text near the most prominent appearance of the work&rsquo;s title,
preceding the beginning of the body of the text.
</p>
<p>The &ldquo;publisher&rdquo; means any person or entity that distributes copies
of the Document to the public.
</p>
<p>A section &ldquo;Entitled XYZ&rdquo; means a named subunit of the Document whose
title either is precisely XYZ or contains XYZ in parentheses following
text that translates XYZ in another language.  (Here XYZ stands for a
specific section name mentioned below, such as &ldquo;Acknowledgements&rdquo;,
&ldquo;Dedications&rdquo;, &ldquo;Endorsements&rdquo;, or &ldquo;History&rdquo;.)  To &ldquo;Preserve the Title&rdquo;
of such a section when you modify the Document means that it remains a
section &ldquo;Entitled XYZ&rdquo; according to this definition.
</p>
<p>The Document may include Warranty Disclaimers next to the notice which
states that this License applies to the Document.  These Warranty
Disclaimers are considered to be included by reference in this
License, but only as regards disclaiming warranties: any other
implication that these Warranty Disclaimers may have is void and has
no effect on the meaning of this License.
</p>
</li><li> VERBATIM COPYING

<p>You may copy and distribute the Document in any medium, either
commercially or noncommercially, provided that this License, the
copyright notices, and the license notice saying this License applies
to the Document are reproduced in all copies, and that you add no other
conditions whatsoever to those of this License.  You may not use
technical measures to obstruct or control the reading or further
copying of the copies you make or distribute.  However, you may accept
compensation in exchange for copies.  If you distribute a large enough
number of copies you must also follow the conditions in section 3.
</p>
<p>You may also lend copies, under the same conditions stated above, and
you may publicly display copies.
</p>
</li><li> COPYING IN QUANTITY

<p>If you publish printed copies (or copies in media that commonly have
printed covers) of the Document, numbering more than 100, and the
Document&rsquo;s license notice requires Cover Texts, you must enclose the
copies in covers that carry, clearly and legibly, all these Cover
Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on
the back cover.  Both covers must also clearly and legibly identify
you as the publisher of these copies.  The front cover must present
the full title with all words of the title equally prominent and
visible.  You may add other material on the covers in addition.
Copying with changes limited to the covers, as long as they preserve
the title of the Document and satisfy these conditions, can be treated
as verbatim copying in other respects.
</p>
<p>If the required texts for either cover are too voluminous to fit
legibly, you should put the first ones listed (as many as fit
reasonably) on the actual cover, and continue the rest onto adjacent
pages.
</p>
<p>If you publish or distribute Opaque copies of the Document numbering
more than 100, you must either include a machine-readable Transparent
copy along with each Opaque copy, or state in or with each Opaque copy
a computer-network location from which the general network-using
public has access to download using public-standard network protocols
a complete Transparent copy of the Document, free of added material.
If you use the latter option, you must take reasonably prudent steps,
when you begin distribution of Opaque copies in quantity, to ensure
that this Transparent copy will remain thus accessible at the stated
location until at least one year after the last time you distribute an
Opaque copy (directly or through your agents or retailers) of that
edition to the public.
</p>
<p>It is requested, but not required, that you contact the authors of the
Document well before redistributing any large number of copies, to give
them a chance to provide you with an updated version of the Document.
</p>
</li><li> MODIFICATIONS

<p>You may copy and distribute a Modified Version of the Document under
the conditions of sections 2 and 3 above, provided that you release
the Modified Version under precisely this License, with the Modified
Version filling the role of the Document, thus licensing distribution
and modification of the Modified Version to whoever possesses a copy
of it.  In addition, you must do these things in the Modified Version:
</p>
<ol>
<li> Use in the Title Page (and on the covers, if any) a title distinct
from that of the Document, and from those of previous versions
(which should, if there were any, be listed in the History section
of the Document).  You may use the same title as a previous version
if the original publisher of that version gives permission.

</li><li> List on the Title Page, as authors, one or more persons or entities
responsible for authorship of the modifications in the Modified
Version, together with at least five of the principal authors of the
Document (all of its principal authors, if it has fewer than five),
unless they release you from this requirement.

</li><li> State on the Title page the name of the publisher of the
Modified Version, as the publisher.

</li><li> Preserve all the copyright notices of the Document.

</li><li> Add an appropriate copyright notice for your modifications
adjacent to the other copyright notices.

</li><li> Include, immediately after the copyright notices, a license notice
giving the public permission to use the Modified Version under the
terms of this License, in the form shown in the Addendum below.

</li><li> Preserve in that license notice the full lists of Invariant Sections
and required Cover Texts given in the Document&rsquo;s license notice.

</li><li> Include an unaltered copy of this License.

</li><li> Preserve the section Entitled &ldquo;History&rdquo;, Preserve its Title, and add
to it an item stating at least the title, year, new authors, and
publisher of the Modified Version as given on the Title Page.  If
there is no section Entitled &ldquo;History&rdquo; in the Document, create one
stating the title, year, authors, and publisher of the Document as
given on its Title Page, then add an item describing the Modified
Version as stated in the previous sentence.

</li><li> Preserve the network location, if any, given in the Document for
public access to a Transparent copy of the Document, and likewise
the network locations given in the Document for previous versions
it was based on.  These may be placed in the &ldquo;History&rdquo; section.
You may omit a network location for a work that was published at
least four years before the Document itself, or if the original
publisher of the version it refers to gives permission.

</li><li> For any section Entitled &ldquo;Acknowledgements&rdquo; or &ldquo;Dedications&rdquo;, Preserve
the Title of the section, and preserve in the section all the
substance and tone of each of the contributor acknowledgements and/or
dedications given therein.

</li><li> Preserve all the Invariant Sections of the Document,
unaltered in their text and in their titles.  Section numbers
or the equivalent are not considered part of the section titles.

</li><li> Delete any section Entitled &ldquo;Endorsements&rdquo;.  Such a section
may not be included in the Modified Version.

</li><li> Do not retitle any existing section to be Entitled &ldquo;Endorsements&rdquo; or
to conflict in title with any Invariant Section.

</li><li> Preserve any Warranty Disclaimers.
</li></ol>

<p>If the Modified Version includes new front-matter sections or
appendices that qualify as Secondary Sections and contain no material
copied from the Document, you may at your option designate some or all
of these sections as invariant.  To do this, add their titles to the
list of Invariant Sections in the Modified Version&rsquo;s license notice.
These titles must be distinct from any other section titles.
</p>
<p>You may add a section Entitled &ldquo;Endorsements&rdquo;, provided it contains
nothing but endorsements of your Modified Version by various
parties&mdash;for example, statements of peer review or that the text has
been approved by an organization as the authoritative definition of a
standard.
</p>
<p>You may add a passage of up to five words as a Front-Cover Text, and a
passage of up to 25 words as a Back-Cover Text, to the end of the list
of Cover Texts in the Modified Version.  Only one passage of
Front-Cover Text and one of Back-Cover Text may be added by (or
through arrangements made by) any one entity.  If the Document already
includes a cover text for the same cover, previously added by you or
by arrangement made by the same entity you are acting on behalf of,
you may not add another; but you may replace the old one, on explicit
permission from the previous publisher that added the old one.
</p>
<p>The author(s) and publisher(s) of the Document do not by this License
give permission to use their names for publicity for or to assert or
imply endorsement of any Modified Version.
</p>
</li><li> COMBINING DOCUMENTS

<p>You may combine the Document with other documents released under this
License, under the terms defined in section 4 above for modified
versions, provided that you include in the combination all of the
Invariant Sections of all of the original documents, unmodified, and
list them all as Invariant Sections of your combined work in its
license notice, and that you preserve all their Warranty Disclaimers.
</p>
<p>The combined work need only contain one copy of this License, and
multiple identical Invariant Sections may be replaced with a single
copy.  If there are multiple Invariant Sections with the same name but
different contents, make the title of each such section unique by
adding at the end of it, in parentheses, the name of the original
author or publisher of that section if known, or else a unique number.
Make the same adjustment to the section titles in the list of
Invariant Sections in the license notice of the combined work.
</p>
<p>In the combination, you must combine any sections Entitled &ldquo;History&rdquo;
in the various original documents, forming one section Entitled
&ldquo;History&rdquo;; likewise combine any sections Entitled &ldquo;Acknowledgements&rdquo;,
and any sections Entitled &ldquo;Dedications&rdquo;.  You must delete all
sections Entitled &ldquo;Endorsements.&rdquo;
</p>
</li><li> COLLECTIONS OF DOCUMENTS

<p>You may make a collection consisting of the Document and other documents
released under this License, and replace the individual copies of this
License in the various documents with a single copy that is included in
the collection, provided that you follow the rules of this License for
verbatim copying of each of the documents in all other respects.
</p>
<p>You may extract a single document from such a collection, and distribute
it individually under this License, provided you insert a copy of this
License into the extracted document, and follow this License in all
other respects regarding verbatim copying of that document.
</p>
</li><li> AGGREGATION WITH INDEPENDENT WORKS

<p>A compilation of the Document or its derivatives with other separate
and independent documents or works, in or on a volume of a storage or
distribution medium, is called an &ldquo;aggregate&rdquo; if the copyright
resulting from the compilation is not used to limit the legal rights
of the compilation&rsquo;s users beyond what the individual works permit.
When the Document is included in an aggregate, this License does not
apply to the other works in the aggregate which are not themselves
derivative works of the Document.
</p>
<p>If the Cover Text requirement of section 3 is applicable to these
copies of the Document, then if the Document is less than one half of
the entire aggregate, the Document&rsquo;s Cover Texts may be placed on
covers that bracket the Document within the aggregate, or the
electronic equivalent of covers if the Document is in electronic form.
Otherwise they must appear on printed covers that bracket the whole
aggregate.
</p>
</li><li> TRANSLATION

<p>Translation is considered a kind of modification, so you may
distribute translations of the Document under the terms of section 4.
Replacing Invariant Sections with translations requires special
permission from their copyright holders, but you may include
translations of some or all Invariant Sections in addition to the
original versions of these Invariant Sections.  You may include a
translation of this License, and all the license notices in the
Document, and any Warranty Disclaimers, provided that you also include
the original English version of this License and the original versions
of those notices and disclaimers.  In case of a disagreement between
the translation and the original version of this License or a notice
or disclaimer, the original version will prevail.
</p>
<p>If a section in the Document is Entitled &ldquo;Acknowledgements&rdquo;,
&ldquo;Dedications&rdquo;, or &ldquo;History&rdquo;, the requirement (section 4) to Preserve
its Title (section 1) will typically require changing the actual
title.
</p>
</li><li> TERMINATION

<p>You may not copy, modify, sublicense, or distribute the Document
except as expressly provided under this License.  Any attempt
otherwise to copy, modify, sublicense, or distribute it is void, and
will automatically terminate your rights under this License.
</p>
<p>However, if you cease all violation of this License, then your license
from a particular copyright holder is reinstated (a) provisionally,
unless and until the copyright holder explicitly and finally
terminates your license, and (b) permanently, if the copyright holder
fails to notify you of the violation by some reasonable means prior to
60 days after the cessation.
</p>
<p>Moreover, your license from a particular copyright holder is
reinstated permanently if the copyright holder notifies you of the
violation by some reasonable means, this is the first time you have
received notice of violation of this License (for any work) from that
copyright holder, and you cure the violation prior to 30 days after
your receipt of the notice.
</p>
<p>Termination of your rights under this section does not terminate the
licenses of parties who have received copies or rights from you under
this License.  If your rights have been terminated and not permanently
reinstated, receipt of a copy of some or all of the same material does
not give you any rights to use it.
</p>
</li><li> FUTURE REVISIONS OF THIS LICENSE

<p>The Free Software Foundation may publish new, revised versions
of the GNU Free Documentation License from time to time.  Such new
versions will be similar in spirit to the present version, but may
differ in detail to address new problems or concerns.  See
<a href="http://www.gnu.org/copyleft/">http://www.gnu.org/copyleft/</a>.
</p>
<p>Each version of the License is given a distinguishing version number.
If the Document specifies that a particular numbered version of this
License &ldquo;or any later version&rdquo; applies to it, you have the option of
following the terms and conditions either of that specified version or
of any later version that has been published (not as a draft) by the
Free Software Foundation.  If the Document does not specify a version
number of this License, you may choose any version ever published (not
as a draft) by the Free Software Foundation.  If the Document
specifies that a proxy can decide which future versions of this
License can be used, that proxy&rsquo;s public statement of acceptance of a
version permanently authorizes you to choose that version for the
Document.
</p>
</li><li> RELICENSING

<p>&ldquo;Massive Multiauthor Collaboration Site&rdquo; (or &ldquo;MMC Site&rdquo;) means any
World Wide Web server that publishes copyrightable works and also
provides prominent facilities for anybody to edit those works.  A
public wiki that anybody can edit is an example of such a server.  A
&ldquo;Massive Multiauthor Collaboration&rdquo; (or &ldquo;MMC&rdquo;) contained in the
site means any set of copyrightable works thus published on the MMC
site.
</p>
<p>&ldquo;CC-BY-SA&rdquo; means the Creative Commons Attribution-Share Alike 3.0
license published by Creative Commons Corporation, a not-for-profit
corporation with a principal place of business in San Francisco,
California, as well as future copyleft versions of that license
published by that same organization.
</p>
<p>&ldquo;Incorporate&rdquo; means to publish or republish a Document, in whole or
in part, as part of another Document.
</p>
<p>An MMC is &ldquo;eligible for relicensing&rdquo; if it is licensed under this
License, and if all works that were first published under this License
somewhere other than this MMC, and subsequently incorporated in whole
or in part into the MMC, (1) had no cover texts or invariant sections,
and (2) were thus incorporated prior to November 1, 2008.
</p>
<p>The operator of an MMC Site may republish an MMC contained in the site
under CC-BY-SA on the same site at any time before August 1, 2009,
provided the MMC is eligible for relicensing.
</p>
</li></ol>

<a name="ADDENDUM_003a-How-to-use-this-License-for-your-documents"></a>
<h3 class="unnumberedsec">ADDENDUM: How to use this License for your documents</h3>

<p>To use this License in a document you have written, include a copy of
the License in the document and put the following copyright and
license notices just after the title page:
</p>
<div class="smallexample">
<pre class="smallexample">  Copyright (C)  <var>year</var>  <var>your name</var>.
  Permission is granted to copy, distribute and/or modify this document
  under the terms of the GNU Free Documentation License, Version 1.3
  or any later version published by the Free Software Foundation;
  with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
  Texts.  A copy of the license is included in the section entitled ``GNU
  Free Documentation License''.
</pre></div>

<p>If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts,
replace the &ldquo;with...Texts.&rdquo; line with this:
</p>
<div class="smallexample">
<pre class="smallexample">    with the Invariant Sections being <var>list their titles</var>, with
    the Front-Cover Texts being <var>list</var>, and with the Back-Cover Texts
    being <var>list</var>.
</pre></div>

<p>If you have Invariant Sections without Cover Texts, or some other
combination of the three, merge those two alternatives to suit the
situation.
</p>
<p>If your document contains nontrivial examples of program code, we
recommend releasing these examples in parallel under your choice of
free software license, such as the GNU General Public License,
to permit their use in free software.
</p>



<hr>
<a name="Index"></a>
<div class="header">
<p>
Previous: <a href="#GNU-Free-Documentation-License" accesskey="p" rel="prev">GNU Free Documentation License</a>, Up: <a href="#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="#Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="Index-1"></a>
<h2 class="unnumbered">Index</h2>

<table><tr><th valign="top">Jump to: &nbsp; </th><td><a class="summary-letter" href="#Index_cp_letter-F"><b>F</b></a>
 &nbsp; 
<a class="summary-letter" href="#Index_cp_letter-I"><b>I</b></a>
 &nbsp; 
</td></tr></table>
<table class="index-cp" border="0">
<tr><td></td><th align="left">Index Entry</th><td>&nbsp;</td><th align="left"> Section</th></tr>
<tr><td colspan="4"> <hr></td></tr>
<tr><th><a name="Index_cp_letter-F">F</a></th><td></td><td></td></tr>
<tr><td></td><td valign="top"><a href="#index-FDL_002c-GNU-Free-Documentation-License">FDL, GNU Free Documentation License</a>:</td><td>&nbsp;</td><td valign="top"><a href="#GNU-Free-Documentation-License">GNU Free Documentation License</a></td></tr>
<tr><td colspan="4"> <hr></td></tr>
<tr><th><a name="Index_cp_letter-I">I</a></th><td></td><td></td></tr>
<tr><td></td><td valign="top"><a href="#index-Introduction">Introduction</a>:</td><td>&nbsp;</td><td valign="top"><a href="#Top">Top</a></td></tr>
<tr><td colspan="4"> <hr></td></tr>
</table>
<table><tr><th valign="top">Jump to: &nbsp; </th><td><a class="summary-letter" href="#Index_cp_letter-F"><b>F</b></a>
 &nbsp; 
<a class="summary-letter" href="#Index_cp_letter-I"><b>I</b></a>
 &nbsp; 
</td></tr></table>

<hr>



</body>
</html>