summaryrefslogtreecommitdiff
path: root/src/btree/bt_slvg.c
blob: 0e064d306b6fc6ba861cfdc55074a779bd46dec9 (plain)
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
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
/*-
 * Copyright (c) 2014-2016 MongoDB, Inc.
 * Copyright (c) 2008-2014 WiredTiger, Inc.
 *	All rights reserved.
 *
 * See the file LICENSE for redistribution information.
 */

#include "wt_internal.h"

struct __wt_stuff;	  typedef struct __wt_stuff WT_STUFF;
struct __wt_track;	  typedef struct __wt_track WT_TRACK;
struct __wt_track_shared; typedef struct __wt_track_shared WT_TRACK_SHARED;

/*
 * There's a bunch of stuff we pass around during salvage, group it together
 * to make the code prettier.
 */
struct __wt_stuff {
	WT_SESSION_IMPL *session;		/* Salvage session */

	WT_TRACK **pages;			/* Pages */
	uint32_t   pages_next;			/* Next empty slot */
	size_t     pages_allocated;		/* Bytes allocated */

	WT_TRACK **ovfl;			/* Overflow pages */
	uint32_t   ovfl_next;			/* Next empty slot */
	size_t     ovfl_allocated;		/* Bytes allocated */

	WT_REF	   root_ref;			/* Created root page */

	uint8_t    page_type;			/* Page type */

	/* If need to free blocks backing merged page ranges. */
	bool	   merge_free;

	WT_ITEM	  *tmp1;			/* Verbose print buffer */
	WT_ITEM	  *tmp2;			/* Verbose print buffer */

	uint64_t fcnt;				/* Progress counter */
};

/*
 * WT_TRACK_SHARED --
 *	Information shared between pages being merged.
 */
struct __wt_track_shared {
	uint32_t ref;				/* Reference count */

	/*
	 * Physical information about the file block.
	 */
	WT_ADDR  addr;				/* Page address */
	uint32_t size;				/* Page size */
	uint64_t gen;				/* Page generation */

	/*
	 * Pages that reference overflow pages contain a list of the overflow
	 * pages they reference.  We start out with a list of addresses, and
	 * convert to overflow array slots during the reconciliation of page
	 * references to overflow records.
	 */
	WT_ADDR  *ovfl_addr;			/* Overflow pages by address */
	uint32_t *ovfl_slot;			/* Overflow pages by slot */
	uint32_t  ovfl_cnt;			/* Overflow reference count */
};

/*
 * WT_TRACK --
 *	Structure to track chunks, one per chunk; we start out with a chunk per
 * page (either leaf or overflow), but when we find overlapping key ranges, we
 * split the leaf page chunks up, one chunk for each unique key range.
 */
struct __wt_track {
#define	trk_addr	shared->addr.addr
#define	trk_addr_size	shared->addr.size
#define	trk_gen		shared->gen
#define	trk_ovfl_addr	shared->ovfl_addr
#define	trk_ovfl_cnt	shared->ovfl_cnt
#define	trk_ovfl_slot	shared->ovfl_slot
#define	trk_size	shared->size
	WT_TRACK_SHARED *shared;		/* Shared information */

	WT_STUFF  *ss;				/* Enclosing stuff */

	union {
		struct {
#undef	row_start
#define	row_start	u.row._row_start
			WT_ITEM   _row_start;	/* Row-store start range */
#undef	row_stop
#define	row_stop	u.row._row_stop
			WT_ITEM   _row_stop;	/* Row-store stop range */
		} row;

		struct {
#undef	col_start
#define	col_start	u.col._col_start
			uint64_t _col_start;	/* Col-store start range */
#undef	col_stop
#define	col_stop	u.col._col_stop
			uint64_t _col_stop;	/* Col-store stop range */
#undef	col_missing
#define	col_missing	u.col._col_missing
			uint64_t _col_missing;	/* Col-store missing range */
		} col;
	} u;

#define	WT_TRACK_CHECK_START	0x01		/* Row: initial key updated */
#define	WT_TRACK_CHECK_STOP	0x02		/* Row: last key updated */
#define	WT_TRACK_MERGE		0x04		/* Page requires merging */
#define	WT_TRACK_OVFL_REFD	0x08		/* Overflow page referenced */
	u_int flags;
};

static int  __slvg_cleanup(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_col_build_internal(WT_SESSION_IMPL *, uint32_t, WT_STUFF *);
static int  __slvg_col_build_leaf(WT_SESSION_IMPL *, WT_TRACK *, WT_REF *);
static int  __slvg_col_ovfl(
		WT_SESSION_IMPL *, WT_TRACK *, WT_PAGE *, uint64_t, uint64_t);
static int  __slvg_col_range(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_col_range_missing(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_col_range_overlap(
		WT_SESSION_IMPL *, uint32_t, uint32_t, WT_STUFF *);
static void __slvg_col_trk_update_start(uint32_t, WT_STUFF *);
static int  __slvg_merge_block_free(WT_SESSION_IMPL *, WT_STUFF *);
static int WT_CDECL __slvg_ovfl_compare(const void *, const void *);
static int  __slvg_ovfl_discard(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_ovfl_reconcile(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_ovfl_ref(WT_SESSION_IMPL *, WT_TRACK *, bool);
static int  __slvg_ovfl_ref_all(WT_SESSION_IMPL *, WT_TRACK *);
static int  __slvg_read(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_row_build_internal(WT_SESSION_IMPL *, uint32_t, WT_STUFF *);
static int  __slvg_row_build_leaf(
		WT_SESSION_IMPL *, WT_TRACK *, WT_REF *, WT_STUFF *);
static int  __slvg_row_ovfl(
		WT_SESSION_IMPL *, WT_TRACK *, WT_PAGE *, uint32_t, uint32_t);
static int  __slvg_row_range(WT_SESSION_IMPL *, WT_STUFF *);
static int  __slvg_row_range_overlap(
		WT_SESSION_IMPL *, uint32_t, uint32_t, WT_STUFF *);
static int  __slvg_row_trk_update_start(
		WT_SESSION_IMPL *, WT_ITEM *, uint32_t, WT_STUFF *);
static int  WT_CDECL __slvg_trk_compare_addr(const void *, const void *);
static int  WT_CDECL __slvg_trk_compare_gen(const void *, const void *);
static int  WT_CDECL __slvg_trk_compare_key(const void *, const void *);
static int  __slvg_trk_free(WT_SESSION_IMPL *, WT_TRACK **, bool);
static void __slvg_trk_free_addr(WT_SESSION_IMPL *, WT_TRACK *);
static int  __slvg_trk_init(WT_SESSION_IMPL *, uint8_t *,
		size_t, uint32_t, uint64_t, WT_STUFF *, WT_TRACK **);
static int  __slvg_trk_leaf(WT_SESSION_IMPL *,
		const WT_PAGE_HEADER *, uint8_t *, size_t, WT_STUFF *);
static int  __slvg_trk_leaf_ovfl(
		WT_SESSION_IMPL *, const WT_PAGE_HEADER *, WT_TRACK *);
static int  __slvg_trk_ovfl(WT_SESSION_IMPL *,
		const WT_PAGE_HEADER *, uint8_t *, size_t, WT_STUFF *);

/*
 * __wt_bt_salvage --
 *	Salvage a Btree.
 */
int
__wt_bt_salvage(WT_SESSION_IMPL *session, WT_CKPT *ckptbase, const char *cfg[])
{
	WT_BM *bm;
	WT_BTREE *btree;
	WT_DECL_RET;
	WT_STUFF *ss, stuff;
	uint32_t i, leaf_cnt;

	WT_UNUSED(cfg);

	btree = S2BT(session);
	bm = btree->bm;

	WT_CLEAR(stuff);
	ss = &stuff;
	ss->session = session;
	ss->page_type = WT_PAGE_INVALID;

	/* Allocate temporary buffers. */
	WT_ERR(__wt_scr_alloc(session, 0, &ss->tmp1));
	WT_ERR(__wt_scr_alloc(session, 0, &ss->tmp2));

	/*
	 * Step 1:
	 * Inform the underlying block manager that we're salvaging the file.
	 */
	WT_ERR(bm->salvage_start(bm, session));

	/*
	 * Step 2:
	 * Read the file and build in-memory structures that reference any leaf
	 * or overflow page.  Any pages other than leaf or overflow pages are
	 * added to the free list.
	 *
	 * Turn off read checksum and verification error messages while we're
	 * reading the file, we expect to see corrupted blocks.
	 */
	F_SET(session, WT_SESSION_QUIET_CORRUPT_FILE);
	ret = __slvg_read(session, ss);
	F_CLR(session, WT_SESSION_QUIET_CORRUPT_FILE);
	WT_ERR(ret);

	/*
	 * Step 3:
	 * Discard any page referencing a non-existent overflow page.  We do
	 * this before checking overlapping key ranges on the grounds that a
	 * bad key range we can use is better than a terrific key range that
	 * references pages we don't have. On the other hand, we subsequently
	 * discard key ranges where there are better overlapping ranges, and
	 * it would be better if we let the availability of an overflow value
	 * inform our choices as to the key ranges we select, ideally on a
	 * per-key basis.
	 *
	 * A complicating problem is found in variable-length column-store
	 * objects, where we potentially split key ranges within RLE units.
	 * For example, if there's a page with rows 15-20 and we later find
	 * row 17 with a larger LSN, the range splits into 3 chunks, 15-16,
	 * 17, and 18-20.  If rows 15-20 were originally a single value (an
	 * RLE of 6), and that record is an overflow record, we end up with
	 * two chunks, both of which want to reference the same overflow value.
	 *
	 * Instead of the approach just described, we're first discarding any
	 * pages referencing non-existent overflow pages, then we're reviewing
	 * our key ranges and discarding any that overlap.  We're doing it that
	 * way for a few reasons: absent corruption, missing overflow items are
	 * strong arguments the page was replaced (on the other hand, some kind
	 * of file corruption is probably why we're here); it's a significant
	 * amount of additional complexity to simultaneously juggle overlapping
	 * ranges and missing overflow items; finally, real-world applications
	 * usually don't have a lot of overflow items, as WiredTiger supports
	 * very large page sizes, overflow items shouldn't be common.
	 *
	 * Step 4:
	 * Add unreferenced overflow page blocks to the free list so they are
	 * reused immediately.
	 */
	WT_ERR(__slvg_ovfl_reconcile(session, ss));
	WT_ERR(__slvg_ovfl_discard(session, ss));

	/*
	 * Step 5:
	 * Walk the list of pages looking for overlapping ranges to resolve.
	 * If we find a range that needs to be resolved, set a global flag
	 * and a per WT_TRACK flag on the pages requiring modification.
	 *
	 * This requires sorting the page list by key, and secondarily by LSN.
	 *
	 * !!!
	 * It's vanishingly unlikely and probably impossible for fixed-length
	 * column-store files to have overlapping key ranges.  It's possible
	 * for an entire key range to go missing (if a page is corrupted and
	 * lost), but because pages can't split, it shouldn't be possible to
	 * find pages where the key ranges overlap.  That said, we check for
	 * it and clean up after it in reconciliation because it doesn't cost
	 * much and future column-store formats or operations might allow for
	 * fixed-length format ranges to overlap during salvage, and I don't
	 * want to have to retrofit the code later.
	 */
	qsort(ss->pages,
	    (size_t)ss->pages_next, sizeof(WT_TRACK *), __slvg_trk_compare_key);
	if (ss->page_type == WT_PAGE_ROW_LEAF)
		WT_ERR(__slvg_row_range(session, ss));
	else
		WT_ERR(__slvg_col_range(session, ss));

	/*
	 * Step 6:
	 * We may have lost key ranges in column-store databases, that is, some
	 * part of the record number space is gone; look for missing ranges.
	 */
	switch (ss->page_type) {
	case WT_PAGE_COL_FIX:
	case WT_PAGE_COL_VAR:
		WT_ERR(__slvg_col_range_missing(session, ss));
		break;
	case WT_PAGE_ROW_LEAF:
		break;
	}

	/*
	 * Step 7:
	 * Build an internal page that references all of the leaf pages,
	 * and write it, as well as any merged pages, to the file.
	 *
	 * Count how many leaf pages we have (we could track this during the
	 * array shuffling/splitting, but that's a lot harder).
	 */
	for (leaf_cnt = i = 0; i < ss->pages_next; ++i)
		if (ss->pages[i] != NULL)
			++leaf_cnt;
	if (leaf_cnt != 0)
		switch (ss->page_type) {
		case WT_PAGE_COL_FIX:
		case WT_PAGE_COL_VAR:
			WT_WITH_PAGE_INDEX(session,
			    ret = __slvg_col_build_internal(
			    session, leaf_cnt, ss));
			WT_ERR(ret);
			break;
		case WT_PAGE_ROW_LEAF:
			WT_WITH_PAGE_INDEX(session,
			    ret = __slvg_row_build_internal(
			    session, leaf_cnt, ss));
			WT_ERR(ret);
			break;
		}

	/*
	 * Step 8:
	 * If we had to merge key ranges, we have to do a final pass through
	 * the leaf page array and discard file pages used during key merges.
	 * We can't do it earlier: if we free'd the leaf pages we're merging as
	 * we merged them, the write of subsequent leaf pages or the internal
	 * page might allocate those free'd file blocks, and if the salvage run
	 * subsequently fails, we'd have overwritten pages used to construct the
	 * final key range.  In other words, if the salvage run fails, we don't
	 * want to overwrite data the next salvage run might need.
	 */
	if (ss->merge_free)
		WT_ERR(__slvg_merge_block_free(session, ss));

	/*
	 * Step 9:
	 * Evict the newly created root page, creating a checkpoint.
	 */
	if (ss->root_ref.page != NULL) {
		btree->ckpt = ckptbase;
		ret = __wt_evict(session, &ss->root_ref, true);
		ss->root_ref.page = NULL;
		btree->ckpt = NULL;
	}

	/*
	 * Step 10:
	 * Inform the underlying block manager that we're done.
	 */
err:	WT_TRET(bm->salvage_end(bm, session));

	/* Discard any root page we created. */
	if (ss->root_ref.page != NULL)
		__wt_ref_out(session, &ss->root_ref);

	/* Discard the leaf and overflow page memory. */
	WT_TRET(__slvg_cleanup(session, ss));

	/* Discard temporary buffers. */
	__wt_scr_free(session, &ss->tmp1);
	__wt_scr_free(session, &ss->tmp2);

	return (ret);
}

/*
 * __slvg_read --
 *	Read the file and build a table of the pages we can use.
 */
static int
__slvg_read(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_BM *bm;
	WT_DECL_ITEM(as);
	WT_DECL_ITEM(buf);
	WT_DECL_RET;
	const WT_PAGE_HEADER *dsk;
	size_t addr_size;
	uint8_t addr[WT_BTREE_MAX_ADDR_COOKIE];
	bool eof, valid;

	bm = S2BT(session)->bm;
	WT_ERR(__wt_scr_alloc(session, 0, &as));
	WT_ERR(__wt_scr_alloc(session, 0, &buf));

	for (;;) {
		/* Get the next block address from the block manager. */
		WT_ERR(bm->salvage_next(bm, session, addr, &addr_size, &eof));
		if (eof)
			break;

		/* Report progress occasionally. */
#define	WT_SALVAGE_PROGRESS_INTERVAL	100
		if (++ss->fcnt % WT_SALVAGE_PROGRESS_INTERVAL == 0)
			WT_ERR(__wt_progress(session, NULL, ss->fcnt));

		/*
		 * Read (and potentially decompress) the block; the underlying
		 * block manager might return only good blocks if checksums are
		 * configured, or both good and bad blocks if we're relying on
		 * compression.
		 *
		 * Report the block's status to the block manager.
		 */
		if ((ret = __wt_bt_read(session, buf, addr, addr_size)) == 0)
			valid = true;
		else {
			valid = false;
			if (ret == WT_ERROR)
				ret = 0;
			WT_ERR(ret);
		}
		WT_ERR(bm->salvage_valid(bm, session, addr, addr_size, valid));
		if (!valid)
			continue;

		/* Create a printable version of the address. */
		WT_ERR(bm->addr_string(bm, session, as, addr, addr_size));

		/*
		 * Make sure it's an expected page type for the file.
		 *
		 * We only care about leaf and overflow pages from here on out;
		 * discard all of the others.  We put them on the free list now,
		 * because we might as well overwrite them, we want the file to
		 * grow as little as possible, or shrink, and future salvage
		 * calls don't need them either.
		 */
		dsk = buf->data;
		switch (dsk->type) {
		case WT_PAGE_BLOCK_MANAGER:
		case WT_PAGE_COL_INT:
		case WT_PAGE_ROW_INT:
			WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s page ignored %s",
			    __wt_page_type_string(dsk->type),
			    (const char *)as->data));
			WT_ERR(bm->free(bm, session, addr, addr_size));
			continue;
		}

		/*
		 * Verify the page.  It's unlikely a page could have a valid
		 * checksum and still be broken, but paranoia is healthy in
		 * salvage.  Regardless, verify does return failure because
		 * it detects failures we'd expect to see in a corrupted file,
		 * like overflow references past the end of the file or
		 * overflow references to non-existent pages, might as well
		 * discard these pages now.
		 */
		if (__wt_verify_dsk(session, as->data, buf) != 0) {
			WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s page failed verify %s",
			    __wt_page_type_string(dsk->type),
			    (const char *)as->data));
			WT_ERR(bm->free(bm, session, addr, addr_size));
			continue;
		}

		WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
		    "tracking %s page, generation %" PRIu64 " %s",
		    __wt_page_type_string(dsk->type), dsk->write_gen,
		    (const char *)as->data));

		switch (dsk->type) {
		case WT_PAGE_COL_FIX:
		case WT_PAGE_COL_VAR:
		case WT_PAGE_ROW_LEAF:
			if (ss->page_type == WT_PAGE_INVALID)
				ss->page_type = dsk->type;
			if (ss->page_type != dsk->type)
				WT_ERR_MSG(session, WT_ERROR,
				    "file contains multiple file formats (both "
				    "%s and %s), and cannot be salvaged",
				    __wt_page_type_string(ss->page_type),
				    __wt_page_type_string(dsk->type));

			WT_ERR(__slvg_trk_leaf(
			    session, dsk, addr, addr_size, ss));
			break;
		case WT_PAGE_OVFL:
			WT_ERR(__slvg_trk_ovfl(
			    session, dsk, addr, addr_size, ss));
			break;
		}
	}

err:	__wt_scr_free(session, &as);
	__wt_scr_free(session, &buf);

	return (ret);
}

/*
 * __slvg_trk_init --
 *	Initialize tracking information for a page.
 */
static int
__slvg_trk_init(WT_SESSION_IMPL *session,
    uint8_t *addr, size_t addr_size,
    uint32_t size, uint64_t gen, WT_STUFF *ss, WT_TRACK **retp)
{
	WT_DECL_RET;
	WT_TRACK *trk;

	WT_RET(__wt_calloc_one(session, &trk));
	WT_ERR(__wt_calloc_one(session, &trk->shared));
	trk->shared->ref = 1;

	trk->ss = ss;
	WT_ERR(__wt_strndup(session, addr, addr_size, &trk->trk_addr));
	trk->trk_addr_size = (uint8_t)addr_size;
	trk->trk_size = size;
	trk->trk_gen = gen;

	*retp = trk;
	return (0);

err:	__wt_free(session, trk->trk_addr);
	__wt_free(session, trk->shared);
	__wt_free(session, trk);
	return (ret);
}

/*
 * __slvg_trk_leaf --
 *	Track a leaf page.
 */
static int
__slvg_trk_leaf(WT_SESSION_IMPL *session,
    const WT_PAGE_HEADER *dsk, uint8_t *addr, size_t addr_size, WT_STUFF *ss)
{
	WT_BTREE *btree;
	WT_CELL *cell;
	WT_CELL_UNPACK *unpack, _unpack;
	WT_DECL_RET;
	WT_PAGE *page;
	WT_TRACK *trk;
	uint64_t stop_recno;
	uint32_t i;

	btree = S2BT(session);
	unpack = &_unpack;
	page = NULL;
	trk = NULL;

	/* Re-allocate the array of pages, as necessary. */
	WT_RET(__wt_realloc_def(
	    session, &ss->pages_allocated, ss->pages_next + 1, &ss->pages));

	/* Allocate a WT_TRACK entry for this new page and fill it in. */
	WT_RET(__slvg_trk_init(
	    session, addr, addr_size, dsk->mem_size, dsk->write_gen, ss, &trk));

	switch (dsk->type) {
	case WT_PAGE_COL_FIX:
		/*
		 * Column-store fixed-sized format: start and stop keys can be
		 * taken from the block's header, and doesn't contain overflow
		 * items.
		 */
		trk->col_start = dsk->recno;
		trk->col_stop = dsk->recno + (dsk->u.entries - 1);

		WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
		    "%s records %" PRIu64 "-%" PRIu64,
		    __wt_addr_string(
		    session, trk->trk_addr, trk->trk_addr_size, ss->tmp1),
		    trk->col_start, trk->col_stop));
		break;
	case WT_PAGE_COL_VAR:
		/*
		 * Column-store variable-length format: the start key can be
		 * taken from the block's header, stop key requires walking
		 * the page.
		 */
		stop_recno = dsk->recno;
		WT_CELL_FOREACH(btree, dsk, cell, unpack, i) {
			__wt_cell_unpack(cell, unpack);
			stop_recno += __wt_cell_rle(unpack);
		}

		trk->col_start = dsk->recno;
		trk->col_stop = stop_recno - 1;

		WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
		    "%s records %" PRIu64 "-%" PRIu64,
		    __wt_addr_string(
		    session, trk->trk_addr, trk->trk_addr_size, ss->tmp1),
		    trk->col_start, trk->col_stop));

		/* Column-store pages can contain overflow items. */
		WT_ERR(__slvg_trk_leaf_ovfl(session, dsk, trk));
		break;
	case WT_PAGE_ROW_LEAF:
		/*
		 * Row-store format: copy the first and last keys on the page.
		 * Keys are prefix-compressed, the simplest and slowest thing
		 * to do is instantiate the in-memory page, then instantiate
		 * and copy the full keys, then free the page. We do this on
		 * every leaf page, and if you need to speed up the salvage,
		 * it's probably a great place to start.
		 */
		WT_ERR(__wt_page_inmem(session, NULL, dsk, 0, 0, &page));
		WT_ERR(__wt_row_leaf_key_copy(session,
		    page, &page->pg_row_d[0], &trk->row_start));
		WT_ERR(__wt_row_leaf_key_copy(session, page,
		    &page->pg_row_d[page->pg_row_entries - 1], &trk->row_stop));

		WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
		    "%s start key %s",
		    __wt_addr_string(session,
		    trk->trk_addr, trk->trk_addr_size, ss->tmp1),
		    __wt_buf_set_printable(session,
		    trk->row_start.data, trk->row_start.size, ss->tmp2)));
		WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
		    "%s stop key %s",
		    __wt_addr_string(session,
		    trk->trk_addr, trk->trk_addr_size, ss->tmp1),
		    __wt_buf_set_printable(session,
		    trk->row_stop.data, trk->row_stop.size, ss->tmp2)));

		/* Row-store pages can contain overflow items. */
		WT_ERR(__slvg_trk_leaf_ovfl(session, dsk, trk));
		break;
	}
	ss->pages[ss->pages_next++] = trk;

	if (0) {
err:		__wt_free(session, trk);
	}
	if (page != NULL)
		__wt_page_out(session, &page);
	return (ret);
}

/*
 * __slvg_trk_ovfl --
 *	Track an overflow page.
 */
static int
__slvg_trk_ovfl(WT_SESSION_IMPL *session,
    const WT_PAGE_HEADER *dsk, uint8_t *addr, size_t addr_size, WT_STUFF *ss)
{
	WT_TRACK *trk;

	/*
	 * Reallocate the overflow page array as necessary, then save the
	 * page's location information.
	 */
	WT_RET(__wt_realloc_def(
	    session, &ss->ovfl_allocated, ss->ovfl_next + 1, &ss->ovfl));

	WT_RET(__slvg_trk_init(
	    session, addr, addr_size, dsk->mem_size, dsk->write_gen, ss, &trk));
	ss->ovfl[ss->ovfl_next++] = trk;

	return (0);
}

/*
 * __slvg_trk_leaf_ovfl --
 *	Search a leaf page for overflow items.
 */
static int
__slvg_trk_leaf_ovfl(
    WT_SESSION_IMPL *session, const WT_PAGE_HEADER *dsk, WT_TRACK *trk)
{
	WT_BTREE *btree;
	WT_CELL *cell;
	WT_CELL_UNPACK *unpack, _unpack;
	uint32_t i, ovfl_cnt;

	btree = S2BT(session);
	unpack = &_unpack;

	/*
	 * Two passes: count the overflow items, then copy them into an
	 * allocated array.
	 */
	ovfl_cnt = 0;
	WT_CELL_FOREACH(btree, dsk, cell, unpack, i) {
		__wt_cell_unpack(cell, unpack);
		if (unpack->ovfl)
			++ovfl_cnt;
	}
	if (ovfl_cnt == 0)
		return (0);

	/* Allocate room for the array of overflow addresses and fill it in. */
	WT_RET(__wt_calloc_def(session, ovfl_cnt, &trk->trk_ovfl_addr));
	trk->trk_ovfl_cnt = ovfl_cnt;

	ovfl_cnt = 0;
	WT_CELL_FOREACH(btree, dsk, cell, unpack, i) {
		__wt_cell_unpack(cell, unpack);
		if (unpack->ovfl) {
			WT_RET(__wt_strndup(session, unpack->data,
			    unpack->size, &trk->trk_ovfl_addr[ovfl_cnt].addr));
			trk->trk_ovfl_addr[ovfl_cnt].size =
			    (uint8_t)unpack->size;

			WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s overflow reference %s",
			    __wt_addr_string(session,
			    trk->trk_addr, trk->trk_addr_size, trk->ss->tmp1),
			    __wt_addr_string(session,
			    unpack->data, unpack->size, trk->ss->tmp2)));

			if (++ovfl_cnt == trk->trk_ovfl_cnt)
				break;
		}
	}

	return (0);
}

/*
 * __slvg_col_range --
 *	Figure out the leaf pages we need and free the leaf pages we don't.
 *
 * When pages split, the key range is split across multiple pages.  If not all
 * of the old versions of the page are overwritten, or not all of the new pages
 * are written, or some of the pages are corrupted, salvage will read different
 * pages with overlapping key ranges, at different LSNs.
 *
 * We salvage all of the key ranges we find, at the latest LSN value: this means
 * we may resurrect pages of deleted items, as page deletion doesn't write leaf
 * pages and salvage will read and instantiate the contents of an old version of
 * the deleted page.
 *
 * The leaf page array is sorted in key order, and secondarily on LSN: what this
 * means is that for each new key range, the first page we find is the best page
 * for that key. The process is to walk forward from each page until we reach a
 * page with a starting key after the current page's stopping key.
 *
 * For each of page, check to see if they overlap the current page's key range.
 * If they do, resolve the overlap.  Because WiredTiger rarely splits pages,
 * overlap resolution usually means discarding a page because the key ranges
 * are the same, and one of the pages is simply an old version of the other.
 *
 * However, it's possible more complex resolution is necessary.  For example,
 * here's an improbably complex list of page ranges and LSNs:
 *
 *	Page	Range	LSN
 *	 30	 A-G	 3
 *	 31	 C-D	 4
 *	 32	 B-C	 5
 *	 33	 C-F	 6
 *	 34	 C-D	 7
 *	 35	 F-M	 8
 *	 36	 H-O	 9
 *
 * We walk forward from each page reviewing all other pages in the array that
 * overlap the range.  For each overlap, the current or the overlapping
 * page is updated so the page with the most recent information for any range
 * "owns" that range.  Here's an example for page 30.
 *
 * Review page 31: because page 31 has the range C-D and a higher LSN than page
 * 30, page 30 would "split" into two ranges, A-C and E-G, conceding the C-D
 * range to page 31.  The new track element would be inserted into array with
 * the following result:
 *
 *	Page	Range	LSN
 *	 30	 A-C	 3		<< Changed WT_TRACK element
 *	 31	 C-D	 4
 *	 32	 B-C	 5
 *	 33	 C-F	 6
 *	 34	 C-D	 7
 *	 30	 E-G	 3		<< New WT_TRACK element
 *	 35	 F-M	 8
 *	 36	 H-O	 9
 *
 * Continue the review of the first element, using its new values.
 *
 * Review page 32: because page 31 has the range B-C and a higher LSN than page
 * 30, page 30's A-C range would be truncated, conceding the B-C range to page
 * 32.
 *	 30	 A-B	 3
 *		 E-G	 3
 *	 31	 C-D	 4
 *	 32	 B-C	 5
 *	 33	 C-F	 6
 *	 34	 C-D	 7
 *
 * Review page 33: because page 33 has a starting key (C) past page 30's ending
 * key (B), we stop evaluating page 30's A-B range, as there can be no further
 * overlaps.
 *
 * This process is repeated for each page in the array.
 *
 * When page 33 is processed, we'd discover that page 33's C-F range overlaps
 * page 30's E-G range, and page 30's E-G range would be updated, conceding the
 * E-F range to page 33.
 *
 * This is not computationally expensive because we don't walk far forward in
 * the leaf array because it's sorted by starting key, and because WiredTiger
 * splits are rare, the chance of finding the kind of range overlap requiring
 * re-sorting the array is small.
 */
static int
__slvg_col_range(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_TRACK *jtrk;
	uint32_t i, j;

	/*
	 * DO NOT MODIFY THIS CODE WITHOUT REVIEWING THE CORRESPONDING ROW- OR
	 * COLUMN-STORE CODE: THEY ARE IDENTICAL OTHER THAN THE PAGES THAT ARE
	 * BEING HANDLED.
	 *
	 * Walk the page array looking for overlapping key ranges, adjusting
	 * the ranges based on the LSN until there are no overlaps.
	 *
	 * DO NOT USE POINTERS INTO THE ARRAY: THE ARRAY IS RE-SORTED IN PLACE
	 * AS ENTRIES ARE SPLIT, SO ARRAY REFERENCES MUST ALWAYS BE ARRAY BASE
	 * PLUS OFFSET.
	 */
	for (i = 0; i < ss->pages_next; ++i) {
		if (ss->pages[i] == NULL)
			continue;

		/* Check for pages that overlap our page. */
		for (j = i + 1; j < ss->pages_next; ++j) {
			if (ss->pages[j] == NULL)
				continue;
			/*
			 * We're done if this page starts after our stop, no
			 * subsequent pages can overlap our page.
			 */
			if (ss->pages[j]->col_start >
			    ss->pages[i]->col_stop)
				break;

			/* There's an overlap, fix it up. */
			jtrk = ss->pages[j];
			WT_RET(__slvg_col_range_overlap(session, i, j, ss));

			/*
			 * If the overlap resolution changed the entry's start
			 * key, the entry might have moved and the page array
			 * re-sorted, and pages[j] would reference a different
			 * page.  We don't move forward if that happened, we
			 * re-process the slot again (by decrementing j before
			 * the loop's increment).
			 */
			if (ss->pages[j] != NULL && jtrk != ss->pages[j])
				--j;
		}
	}
	return (0);
}

/*
 * __slvg_col_range_overlap --
 *	Two column-store key ranges overlap, deal with it.
 */
static int
__slvg_col_range_overlap(
    WT_SESSION_IMPL *session, uint32_t a_slot, uint32_t b_slot, WT_STUFF *ss)
{
	WT_DECL_RET;
	WT_TRACK *a_trk, *b_trk, *new;
	uint32_t i;

	/*
	 * DO NOT MODIFY THIS CODE WITHOUT REVIEWING THE CORRESPONDING ROW- OR
	 * COLUMN-STORE CODE: THEY ARE IDENTICAL OTHER THAN THE PAGES THAT ARE
	 * BEING HANDLED.
	 */
	a_trk = ss->pages[a_slot];
	b_trk = ss->pages[b_slot];

	WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
	    "%s and %s range overlap",
	    __wt_addr_string(
	    session, a_trk->trk_addr, a_trk->trk_addr_size, ss->tmp1),
	    __wt_addr_string(
	    session, b_trk->trk_addr, b_trk->trk_addr_size, ss->tmp2)));

	/*
	 * The key ranges of two WT_TRACK pages in the array overlap -- choose
	 * the ranges we're going to take from each.
	 *
	 * We can think of the overlap possibilities as 11 different cases:
	 *
	 *		AAAAAAAAAAAAAAAAAA
	 * #1		BBBBBBBBBBBBBBBBBB		pages are the same
	 * #2	BBBBBBBBBBBBB				overlaps the beginning
	 * #3			BBBBBBBBBBBBBBBB	overlaps the end
	 * #4		BBBBB				B is a prefix of A
	 * #5			BBBBBB			B is middle of A
	 * #6			BBBBBBBBBB		B is a suffix of A
	 *
	 * and:
	 *
	 *		BBBBBBBBBBBBBBBBBB
	 * #7	AAAAAAAAAAAAA				same as #3
	 * #8			AAAAAAAAAAAAAAAA	same as #2
	 * #9		AAAAA				A is a prefix of B
	 * #10			AAAAAA			A is middle of B
	 * #11			AAAAAAAAAA		A is a suffix of B
	 *
	 * Note the leaf page array was sorted by key and a_trk appears earlier
	 * in the array than b_trk, so cases #2/8, #10 and #11 are impossible.
	 *
	 * Finally, there's one additional complicating factor -- final ranges
	 * are assigned based on the page's LSN.
	 */
						/* Case #2/8, #10, #11 */
	if (a_trk->col_start > b_trk->col_start)
		WT_PANIC_RET(
		    session, EINVAL, "unexpected merge array sort order");

	if (a_trk->col_start == b_trk->col_start) {	/* Case #1, #4 and #9 */
		/*
		 * The secondary sort of the leaf page array was the page's LSN,
		 * in high-to-low order, which means a_trk has a higher LSN, and
		 * is more desirable, than b_trk.  In cases #1 and #4 and #9,
		 * where the start of the range is the same for the two pages,
		 * this simplifies things, it guarantees a_trk has a higher LSN
		 * than b_trk.
		 */
		if (a_trk->col_stop >= b_trk->col_stop)
			/*
			 * Case #1, #4: a_trk is a superset of b_trk, and a_trk
			 * is more desirable -- discard b_trk.
			 */
			goto delete_b;

		/*
		 * Case #9: b_trk is a superset of a_trk, but a_trk is more
		 * desirable: keep both but delete a_trk's key range from
		 * b_trk.
		 */
		b_trk->col_start = a_trk->col_stop + 1;
		__slvg_col_trk_update_start(b_slot, ss);
		F_SET(b_trk, WT_TRACK_MERGE);
		goto merge;
	}

	if (a_trk->col_stop == b_trk->col_stop) {	/* Case #6 */
		if (a_trk->trk_gen > b_trk->trk_gen)
			/*
			 * Case #6: a_trk is a superset of b_trk and a_trk is
			 * more desirable -- discard b_trk.
			 */
			goto delete_b;

		/*
		 * Case #6: a_trk is a superset of b_trk, but b_trk is more
		 * desirable: keep both but delete b_trk's key range from a_trk.
		 */
		a_trk->col_stop = b_trk->col_start - 1;
		F_SET(a_trk, WT_TRACK_MERGE);
		goto merge;
	}

	if  (a_trk->col_stop < b_trk->col_stop) {	/* Case #3/7 */
		if (a_trk->trk_gen > b_trk->trk_gen) {
			/*
			 * Case #3/7: a_trk is more desirable, delete a_trk's
			 * key range from b_trk;
			 */
			b_trk->col_start = a_trk->col_stop + 1;
			__slvg_col_trk_update_start(b_slot, ss);
			F_SET(b_trk, WT_TRACK_MERGE);
		} else {
			/*
			 * Case #3/7: b_trk is more desirable, delete b_trk's
			 * key range from a_trk;
			 */
			a_trk->col_stop = b_trk->col_start - 1;
			F_SET(a_trk, WT_TRACK_MERGE);
		}
		goto merge;
	}

	/*
	 * Case #5: a_trk is a superset of b_trk and a_trk is more desirable --
	 * discard b_trk.
	 */
	if (a_trk->trk_gen > b_trk->trk_gen) {
delete_b:	/*
		 * After page and overflow reconciliation, one (and only one)
		 * page can reference an overflow record.  But, if we split a
		 * page into multiple chunks, any of the chunks might own any
		 * of the backing overflow records, so overflow records won't
		 * normally be discarded until after the merge phase completes.
		 * (The merge phase is where the final pages are written, and
		 * we figure out which overflow records are actually used.)
		 * If freeing a chunk and there are no other references to the
		 * underlying shared information, the overflow records must be
		 * useless, discard them to keep the final file size small.
		 */
		if (b_trk->shared->ref == 1)
			for (i = 0; i < b_trk->trk_ovfl_cnt; ++i)
				WT_RET(__slvg_trk_free(session,
				    &ss->ovfl[b_trk->trk_ovfl_slot[i]], true));
		return (__slvg_trk_free(session, &ss->pages[b_slot], true));
	}

	/*
	 * Case #5: b_trk is more desirable and is a middle chunk of a_trk.
	 * Split a_trk into two parts, the key range before b_trk and the
	 * key range after b_trk.
	 *
	 * Allocate a new WT_TRACK object, and extend the array of pages as
	 * necessary.
	 */
	WT_RET(__wt_calloc_one(session, &new));
	if ((ret = __wt_realloc_def(session,
	    &ss->pages_allocated, ss->pages_next + 1, &ss->pages)) != 0) {
		__wt_free(session, new);
		return (ret);
	}

	/*
	 * First, set up the track share (we do this after the allocation to
	 * ensure the shared reference count is never incorrect).
	 */
	new->shared = a_trk->shared;
	new->ss = a_trk->ss;
	++new->shared->ref;

	/*
	 * Second, insert the new element into the array after the existing
	 * element (that's probably wrong, but we'll fix it up in a second).
	 */
	memmove(ss->pages + a_slot + 1, ss->pages + a_slot,
	    (ss->pages_next - a_slot) * sizeof(*ss->pages));
	ss->pages[a_slot + 1] = new;
	++ss->pages_next;

	/*
	 * Third, set its start key to be the first key after the stop key of
	 * the middle chunk (that's b_trk), and its stop key to be the stop key
	 * of the original chunk, and call __slvg_col_trk_update_start.  That
	 * function will re-sort the WT_TRACK array as necessary to move our
	 * new entry into the right sorted location.
	 */
	new->col_start = b_trk->col_stop + 1;
	new->col_stop = a_trk->col_stop;
	__slvg_col_trk_update_start(a_slot + 1, ss);

	/*
	 * Fourth, set the original WT_TRACK information to reference only
	 * the initial key space in the page, that is, everything up to the
	 * starting key of the middle chunk (that's b_trk).
	 */
	a_trk->col_stop = b_trk->col_start - 1;

	F_SET(new, WT_TRACK_MERGE);
	F_SET(a_trk, WT_TRACK_MERGE);

merge:	WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
	    "%s and %s require merge",
	    __wt_addr_string(
	    session, a_trk->trk_addr, a_trk->trk_addr_size, ss->tmp1),
	    __wt_addr_string(
	    session, b_trk->trk_addr, b_trk->trk_addr_size, ss->tmp2)));
	return (0);
}

/*
 * __slvg_col_trk_update_start --
 *	Update a column-store page's start key after an overlap.
 */
static void
__slvg_col_trk_update_start(uint32_t slot, WT_STUFF *ss)
{
	WT_TRACK *trk;
	uint32_t i;

	trk = ss->pages[slot];

	/*
	 * If we deleted an initial piece of the WT_TRACK name space, it may no
	 * longer be in the right location.
	 *
	 * For example, imagine page #1 has the key range 30-50, it split, and
	 * we wrote page #2 with key range 30-40, and page #3 key range with
	 * 40-50, where pages #2 and #3 have larger LSNs than page #1.  When the
	 * key ranges were sorted, page #2 came first, then page #1 (because of
	 * their earlier start keys than page #3), and page #2 came before page
	 * #1 because of its LSN.  When we resolve the overlap between page #2
	 * and page #1, we truncate the initial key range of page #1, and it now
	 * sorts after page #3, because it has the same starting key of 40, and
	 * a lower LSN.
	 *
	 * We have already updated b_trk's start key; what we may have to do is
	 * re-sort some number of elements in the list.
	 */
	for (i = slot + 1; i < ss->pages_next; ++i) {
		if (ss->pages[i] == NULL)
			continue;
		if (ss->pages[i]->col_start > trk->col_stop)
			break;
	}
	i -= slot;
	if (i > 1)
		qsort(ss->pages + slot, (size_t)i,
		    sizeof(WT_TRACK *), __slvg_trk_compare_key);
}

/*
 * __slvg_col_range_missing --
 *	Detect missing ranges from column-store files.
 */
static int
__slvg_col_range_missing(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_TRACK *trk;
	uint64_t r;
	uint32_t i;

	for (i = 0, r = 0; i < ss->pages_next; ++i) {
		if ((trk = ss->pages[i]) == NULL)
			continue;
		if (trk->col_start != r + 1) {
			WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s column-store missing range from %"
			    PRIu64 " to %" PRIu64 " inclusive",
			    __wt_addr_string(session,
			    trk->trk_addr, trk->trk_addr_size, ss->tmp1),
			    r + 1, trk->col_start - 1));

			/*
			 * We need to instantiate deleted items for the missing
			 * record range.
			 */
			trk->col_missing = r + 1;
			F_SET(trk, WT_TRACK_MERGE);
		}
		r = trk->col_stop;
	}
	return (0);
}

/*
 * __slvg_modify_init --
 *	Initialize a salvage page's modification information.
 */
static int
__slvg_modify_init(WT_SESSION_IMPL *session, WT_PAGE *page)
{
	WT_RET(__wt_page_modify_init(session, page));
	__wt_page_modify_set(session, page);

	return (0);
}

/*
 * __slvg_col_build_internal --
 *	Build a column-store in-memory page that references all of the leaf
 *	pages we've found.
 */
static int
__slvg_col_build_internal(
    WT_SESSION_IMPL *session, uint32_t leaf_cnt, WT_STUFF *ss)
{
	WT_ADDR *addr;
	WT_DECL_RET;
	WT_PAGE *page;
	WT_PAGE_INDEX *pindex;
	WT_REF *ref, **refp;
	WT_TRACK *trk;
	uint32_t i;

	addr = NULL;

	/* Allocate a column-store root (internal) page and fill it in. */
	WT_RET(__wt_page_alloc(
	    session, WT_PAGE_COL_INT, 1, leaf_cnt, true, &page));
	WT_ERR(__slvg_modify_init(session, page));

	pindex = WT_INTL_INDEX_GET_SAFE(page);
	for (refp = pindex->index, i = 0; i < ss->pages_next; ++i) {
		if ((trk = ss->pages[i]) == NULL)
			continue;

		ref = *refp++;
		ref->home = page;
		ref->page = NULL;

		WT_ERR(__wt_calloc_one(session, &addr));
		WT_ERR(__wt_strndup(
		    session, trk->trk_addr, trk->trk_addr_size, &addr->addr));
		addr->size = trk->trk_addr_size;
		addr->type =
		    trk->trk_ovfl_cnt == 0 ? WT_ADDR_LEAF_NO : WT_ADDR_LEAF;
		ref->addr = addr;
		addr = NULL;

		ref->key.recno = trk->col_start;
		ref->state = WT_REF_DISK;

		/*
		 * If the page's key range is unmodified from when we read it
		 * (in other words, we didn't merge part of this page with
		 * another page), we can use the page without change, and the
		 * only thing we need to do is mark all overflow records the
		 * page references as in-use.
		 *
		 * If we did merge with another page, we have to build a page
		 * reflecting the updated key range.  Note, that requires an
		 * additional pass to free the merge page's backing blocks.
		 */
		if (F_ISSET(trk, WT_TRACK_MERGE)) {
			ss->merge_free = true;

			WT_ERR(__slvg_col_build_leaf(session, trk, ref));
		} else
			WT_ERR(__slvg_ovfl_ref_all(session, trk));
		++ref;
	}

	__wt_root_ref_init(&ss->root_ref, page, true);

	if (0) {
err:		__wt_free(session, addr);
		__wt_page_out(session, &page);
	}
	return (ret);
}

/*
 * __slvg_col_build_leaf --
 *	Build a column-store leaf page for a merged page.
 */
static int
__slvg_col_build_leaf(WT_SESSION_IMPL *session, WT_TRACK *trk, WT_REF *ref)
{
	WT_COL *save_col_var;
	WT_DECL_RET;
	WT_PAGE *page;
	WT_SALVAGE_COOKIE *cookie, _cookie;
	uint64_t skip, take;
	uint32_t *entriesp, save_entries;

	cookie = &_cookie;
	WT_CLEAR(*cookie);

	/* Get the original page, including the full in-memory setup. */
	WT_RET(__wt_page_in(session, ref, 0));
	page = ref->page;

	entriesp = page->type == WT_PAGE_COL_VAR ?
	    &page->pg_var_entries : &page->pg_fix_entries;

	save_col_var = page->pg_var_d;
	save_entries = *entriesp;

	/*
	 * Calculate the number of K/V entries we are going to skip, and
	 * the total number of K/V entries we'll take from this page.
	 */
	cookie->skip = skip = trk->col_start - page->pg_var_recno;
	cookie->take = take = (trk->col_stop - trk->col_start) + 1;

	WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
	    "%s merge discarding first %" PRIu64 " records, "
	    "then taking %" PRIu64 " records",
	    __wt_addr_string(
	    session, trk->trk_addr, trk->trk_addr_size, trk->ss->tmp1),
	    skip, take));

	/* Set the referenced flag on overflow pages we're using. */
	if (page->type == WT_PAGE_COL_VAR && trk->trk_ovfl_cnt != 0)
		WT_ERR(__slvg_col_ovfl(session, trk, page, skip, take));

	/*
	 * If we're missing some part of the range, the real start range is in
	 * trk->col_missing, else, it's in trk->col_start.  Update the parent's
	 * reference as well as the page itself.
	 */
	if (trk->col_missing == 0)
		page->pg_var_recno = trk->col_start;
	else {
		page->pg_var_recno = trk->col_missing;
		cookie->missing = trk->col_start - trk->col_missing;

		WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
		    "%s merge inserting %" PRIu64 " missing records",
		    __wt_addr_string(
		    session, trk->trk_addr, trk->trk_addr_size, trk->ss->tmp1),
		    cookie->missing));
	}
	ref->key.recno = page->pg_var_recno;

	/*
	 * We can't discard the original blocks associated with this page now.
	 * (The problem is we don't want to overwrite any original information
	 * until the salvage run succeeds -- if we free the blocks now, the next
	 * merge page we write might allocate those blocks and overwrite them,
	 * and should the salvage run eventually fail, the original information
	 * would have been lost.)  Clear the reference addr so eviction doesn't
	 * free the underlying blocks.
	 */
	__wt_ref_addr_free(session, ref);

	/* Write the new version of the leaf page to disk. */
	WT_ERR(__slvg_modify_init(session, page));
	WT_ERR(__wt_reconcile(session, ref, cookie, WT_VISIBILITY_ERR));

	/* Reset the page. */
	page->pg_var_d = save_col_var;
	*entriesp = save_entries;

	ret = __wt_page_release(session, ref, 0);
	if (ret == 0)
		ret = __wt_evict(session, ref, true);

	if (0) {
err:		WT_TRET(__wt_page_release(session, ref, 0));
	}

	return (ret);
}

/*
 * __slvg_col_ovfl_single --
 *	Find a single overflow record in the merge page's list, and mark it as
 * referenced.
 */
static int
__slvg_col_ovfl_single(
    WT_SESSION_IMPL *session, WT_TRACK *trk, WT_CELL_UNPACK *unpack)
{
	WT_TRACK *ovfl;
	uint32_t i;

	/*
	 * Search the list of overflow records for this page -- we should find
	 * exactly one match, and we mark it as referenced.
	 */
	for (i = 0; i < trk->trk_ovfl_cnt; ++i) {
		ovfl = trk->ss->ovfl[trk->trk_ovfl_slot[i]];
		if (unpack->size == ovfl->trk_addr_size &&
		    memcmp(unpack->data, ovfl->trk_addr, unpack->size) == 0)
			return (__slvg_ovfl_ref(session, ovfl, false));
	}

	WT_PANIC_RET(session,
	    EINVAL, "overflow record at column-store page merge not found");
}

/*
 * __slvg_col_ovfl --
 *	Mark overflow items referenced by the merged page.
 */
static int
__slvg_col_ovfl(WT_SESSION_IMPL *session,
    WT_TRACK *trk, WT_PAGE *page, uint64_t skip, uint64_t take)
{
	WT_CELL_UNPACK unpack;
	WT_CELL *cell;
	WT_COL *cip;
	WT_DECL_RET;
	uint64_t recno, start, stop;
	uint32_t i;

	/*
	 * Merging a variable-length column-store page, and we took some number
	 * of records, figure out which (if any) overflow records we used.
	 */
	recno = page->pg_var_recno;
	start = recno + skip;
	stop = (recno + skip + take) - 1;

	WT_COL_FOREACH(page, cip, i) {
		cell = WT_COL_PTR(page, cip);
		__wt_cell_unpack(cell, &unpack);
		recno += __wt_cell_rle(&unpack);

		/*
		 * I keep getting this calculation wrong, so here's the logic.
		 * Start is the first record we want, stop is the last record
		 * we want. The record number has already been incremented one
		 * past the maximum record number for this page entry, that is,
		 * it's set to the first record number for the next page entry.
		 * The test of start should be greater-than (not greater-than-
		 * or-equal), because of that increment, if the record number
		 * equals start, we want the next record, not this one.  The
		 * test against stop is greater-than, not greater-than-or-equal
		 * because stop is the last record wanted, if the record number
		 * equals stop, we want the next record.
		 */
		if (recno > start && unpack.type == WT_CELL_VALUE_OVFL) {
			ret = __slvg_col_ovfl_single(session, trk, &unpack);

			/*
			 * When handling overlapping ranges on variable-length
			 * column-store leaf pages, we split ranges without
			 * considering if we were splitting RLE units.  (See
			 * note at the beginning of this file for explanation
			 * of the overall process.) If the RLE unit was on-page,
			 * we can simply write it again. If the RLE unit was an
			 * overflow value that's already been used by another
			 * row (from some other page created by a range split),
			 * there's not much to do, this row can't reference an
			 * overflow record we don't have: delete the row.
			 */
			if (ret == EBUSY) {
				__wt_cell_type_reset(session,
				    cell, WT_CELL_VALUE_OVFL, WT_CELL_DEL);
				ret = 0;
			}
			WT_RET(ret);
		}
		if (recno > stop)
			break;
	}
	return (0);
}

/*
 * __slvg_row_range --
 *	Figure out the leaf pages we need and discard everything else.  At the
 * same time, tag the overflow pages they reference.
 */
static int
__slvg_row_range(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_TRACK *jtrk;
	WT_BTREE *btree;
	uint32_t i, j;
	int cmp;

	btree = S2BT(session);

	/*
	 * DO NOT MODIFY THIS CODE WITHOUT REVIEWING THE CORRESPONDING ROW- OR
	 * COLUMN-STORE CODE: THEY ARE IDENTICAL OTHER THAN THE PAGES THAT ARE
	 * BEING HANDLED.
	 *
	 * Walk the page array looking for overlapping key ranges, adjusting
	 * the ranges based on the LSN until there are no overlaps.
	 *
	 * DO NOT USE POINTERS INTO THE ARRAY: THE ARRAY IS RE-SORTED IN PLACE
	 * AS ENTRIES ARE SPLIT, SO ARRAY REFERENCES MUST ALWAYS BE ARRAY BASE
	 * PLUS OFFSET.
	 */
	for (i = 0; i < ss->pages_next; ++i) {
		if (ss->pages[i] == NULL)
			continue;

		/* Check for pages that overlap our page. */
		for (j = i + 1; j < ss->pages_next; ++j) {
			if (ss->pages[j] == NULL)
				continue;
			/*
			 * We're done if this page starts after our stop, no
			 * subsequent pages can overlap our page.
			 */
			WT_RET(__wt_compare(session, btree->collator,
			    &ss->pages[j]->row_start, &ss->pages[i]->row_stop,
			    &cmp));
			if (cmp > 0)
				break;

			/* There's an overlap, fix it up. */
			jtrk = ss->pages[j];
			WT_RET(__slvg_row_range_overlap(session, i, j, ss));

			/*
			 * If the overlap resolution changed the entry's start
			 * key, the entry might have moved and the page array
			 * re-sorted, and pages[j] would reference a different
			 * page.  We don't move forward if that happened, we
			 * re-process the slot again (by decrementing j before
			 * the loop's increment).
			 */
			if (ss->pages[j] != NULL && jtrk != ss->pages[j])
				--j;
		}
	}
	return (0);
}

/*
 * __slvg_row_range_overlap --
 *	Two row-store key ranges overlap, deal with it.
 */
static int
__slvg_row_range_overlap(
    WT_SESSION_IMPL *session, uint32_t a_slot, uint32_t b_slot, WT_STUFF *ss)
{
	WT_BTREE *btree;
	WT_DECL_RET;
	WT_TRACK *a_trk, *b_trk, *new;
	uint32_t i;
	int start_cmp, stop_cmp;

	/*
	 * DO NOT MODIFY THIS CODE WITHOUT REVIEWING THE CORRESPONDING ROW- OR
	 * COLUMN-STORE CODE: THEY ARE IDENTICAL OTHER THAN THE PAGES THAT ARE
	 * BEING HANDLED.
	 */
	btree = S2BT(session);

	a_trk = ss->pages[a_slot];
	b_trk = ss->pages[b_slot];

	WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
	    "%s and %s range overlap",
	    __wt_addr_string(
	    session, a_trk->trk_addr, a_trk->trk_addr_size, ss->tmp1),
	    __wt_addr_string(
	    session, b_trk->trk_addr, b_trk->trk_addr_size, ss->tmp2)));

	/*
	 * The key ranges of two WT_TRACK pages in the array overlap -- choose
	 * the ranges we're going to take from each.
	 *
	 * We can think of the overlap possibilities as 11 different cases:
	 *
	 *		AAAAAAAAAAAAAAAAAA
	 * #1		BBBBBBBBBBBBBBBBBB		pages are the same
	 * #2	BBBBBBBBBBBBB				overlaps the beginning
	 * #3			BBBBBBBBBBBBBBBB	overlaps the end
	 * #4		BBBBB				B is a prefix of A
	 * #5			BBBBBB			B is middle of A
	 * #6			BBBBBBBBBB		B is a suffix of A
	 *
	 * and:
	 *
	 *		BBBBBBBBBBBBBBBBBB
	 * #7	AAAAAAAAAAAAA				same as #3
	 * #8			AAAAAAAAAAAAAAAA	same as #2
	 * #9		AAAAA				A is a prefix of B
	 * #10			AAAAAA			A is middle of B
	 * #11			AAAAAAAAAA		A is a suffix of B
	 *
	 * Note the leaf page array was sorted by key and a_trk appears earlier
	 * in the array than b_trk, so cases #2/8, #10 and #11 are impossible.
	 *
	 * Finally, there's one additional complicating factor -- final ranges
	 * are assigned based on the page's LSN.
	 */
#define	A_TRK_START	(&a_trk->row_start)
#define	A_TRK_STOP	(&a_trk->row_stop)
#define	B_TRK_START	(&b_trk->row_start)
#define	B_TRK_STOP	(&b_trk->row_stop)
#define	SLOT_START(i)	(&ss->pages[i]->row_start)
#define	__slvg_key_copy(session, dst, src)				\
	__wt_buf_set(session, dst, (src)->data, (src)->size)

	WT_RET(__wt_compare(
	    session, btree->collator, A_TRK_START, B_TRK_START, &start_cmp));
	WT_RET(__wt_compare(
	    session, btree->collator, A_TRK_STOP, B_TRK_STOP, &stop_cmp));

	if (start_cmp > 0)			/* Case #2/8, #10, #11 */
		WT_PANIC_RET(
		    session, EINVAL, "unexpected merge array sort order");

	if (start_cmp == 0) {				/* Case #1, #4, #9 */
		/*
		 * The secondary sort of the leaf page array was the page's LSN,
		 * in high-to-low order, which means a_trk has a higher LSN, and
		 * is more desirable, than b_trk.  In cases #1 and #4 and #9,
		 * where the start of the range is the same for the two pages,
		 * this simplifies things, it guarantees a_trk has a higher LSN
		 * than b_trk.
		 */
		if (stop_cmp >= 0)
			/*
			 * Case #1, #4: a_trk is a superset of b_trk, and a_trk
			 * is more desirable -- discard b_trk.
			 */
			goto delete_b;

		/*
		 * Case #9: b_trk is a superset of a_trk, but a_trk is more
		 * desirable: keep both but delete a_trk's key range from
		 * b_trk.
		 */
		WT_RET(__slvg_row_trk_update_start(
		    session, A_TRK_STOP, b_slot, ss));
		F_SET(b_trk, WT_TRACK_CHECK_START | WT_TRACK_MERGE);
		goto merge;
	}

	if (stop_cmp == 0) {				/* Case #6 */
		if (a_trk->trk_gen > b_trk->trk_gen)
			/*
			 * Case #6: a_trk is a superset of b_trk and a_trk is
			 * more desirable -- discard b_trk.
			 */
			goto delete_b;

		/*
		 * Case #6: a_trk is a superset of b_trk, but b_trk is more
		 * desirable: keep both but delete b_trk's key range from a_trk.
		 */
		WT_RET(__slvg_key_copy(session, A_TRK_STOP, B_TRK_START));
		F_SET(a_trk, WT_TRACK_CHECK_STOP | WT_TRACK_MERGE);
		goto merge;
	}

	if (stop_cmp < 0) {				/* Case #3/7 */
		if (a_trk->trk_gen > b_trk->trk_gen) {
			/*
			 * Case #3/7: a_trk is more desirable, delete a_trk's
			 * key range from b_trk;
			 */
			WT_RET(__slvg_row_trk_update_start(
			    session, A_TRK_STOP, b_slot, ss));
			F_SET(b_trk, WT_TRACK_CHECK_START | WT_TRACK_MERGE);
		} else {
			/*
			 * Case #3/7: b_trk is more desirable, delete b_trk's
			 * key range from a_trk;
			 */
			WT_RET(__slvg_key_copy(
			    session, A_TRK_STOP, B_TRK_START));
			F_SET(a_trk, WT_TRACK_CHECK_STOP | WT_TRACK_MERGE);
		}
		goto merge;
	}

	/*
	 * Case #5: a_trk is a superset of b_trk and a_trk is more desirable --
	 * discard b_trk.
	 */
	if (a_trk->trk_gen > b_trk->trk_gen) {
delete_b:	/*
		 * After page and overflow reconciliation, one (and only one)
		 * page can reference an overflow record.  But, if we split a
		 * page into multiple chunks, any of the chunks might own any
		 * of the backing overflow records, so overflow records won't
		 * normally be discarded until after the merge phase completes.
		 * (The merge phase is where the final pages are written, and
		 * we figure out which overflow records are actually used.)
		 * If freeing a chunk and there are no other references to the
		 * underlying shared information, the overflow records must be
		 * useless, discard them to keep the final file size small.
		 */
		if (b_trk->shared->ref == 1)
			for (i = 0; i < b_trk->trk_ovfl_cnt; ++i)
				WT_RET(__slvg_trk_free(session,
				    &ss->ovfl[b_trk->trk_ovfl_slot[i]], true));
		return (__slvg_trk_free(session, &ss->pages[b_slot], true));
	}

	/*
	 * Case #5: b_trk is more desirable and is a middle chunk of a_trk.
	 * Split a_trk into two parts, the key range before b_trk and the
	 * key range after b_trk.
	 *
	 * Allocate a new WT_TRACK object, and extend the array of pages as
	 * necessary.
	 */
	WT_RET(__wt_calloc_one(session, &new));
	if ((ret = __wt_realloc_def(session,
	    &ss->pages_allocated, ss->pages_next + 1, &ss->pages)) != 0) {
		__wt_free(session, new);
		return (ret);
	}

	/*
	 * First, set up the track share (we do this after the allocation to
	 * ensure the shared reference count is never incorrect).
	 */
	new->shared = a_trk->shared;
	new->ss = a_trk->ss;
	++new->shared->ref;

	/*
	 * Second, insert the new element into the array after the existing
	 * element (that's probably wrong, but we'll fix it up in a second).
	 */
	memmove(ss->pages + a_slot + 1, ss->pages + a_slot,
	    (ss->pages_next - a_slot) * sizeof(*ss->pages));
	ss->pages[a_slot + 1] = new;
	++ss->pages_next;

	/*
	 * Third, set its its stop key to be the stop key of the original chunk,
	 * and call __slvg_row_trk_update_start. That function will both set
	 * the start key to be the first key after the stop key of the middle
	 * chunk (that's b_trk), and re-sort the WT_TRACK array as necessary to
	 * move our new entry into the right sorted location.
	 */
	WT_RET(__slvg_key_copy(session, &new->row_stop, A_TRK_STOP));
	WT_RET(
	    __slvg_row_trk_update_start(session, B_TRK_STOP, a_slot + 1, ss));

	/*
	 * Fourth, set the original WT_TRACK information to reference only
	 * the initial key space in the page, that is, everything up to the
	 * starting key of the middle chunk (that's b_trk).
	 */
	WT_RET(__slvg_key_copy(session, A_TRK_STOP, B_TRK_START));
	F_SET(new, WT_TRACK_CHECK_START);
	F_SET(a_trk, WT_TRACK_CHECK_STOP);

	F_SET(new, WT_TRACK_MERGE);
	F_SET(a_trk, WT_TRACK_MERGE);

merge:	WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
	    "%s and %s require merge",
	    __wt_addr_string(
	    session, a_trk->trk_addr, a_trk->trk_addr_size, ss->tmp1),
	    __wt_addr_string(
	    session, b_trk->trk_addr, b_trk->trk_addr_size, ss->tmp2)));
	return (0);
}

/*
 * __slvg_row_trk_update_start --
 *	Update a row-store page's start key after an overlap.
 */
static int
__slvg_row_trk_update_start(
    WT_SESSION_IMPL *session, WT_ITEM *stop, uint32_t slot, WT_STUFF *ss)
{
	WT_BTREE *btree;
	WT_DECL_ITEM(dsk);
	WT_DECL_ITEM(key);
	WT_DECL_RET;
	WT_PAGE *page;
	WT_ROW *rip;
	WT_TRACK *trk;
	uint32_t i;
	int cmp;
	bool found;

	btree = S2BT(session);
	page = NULL;
	found = false;

	trk = ss->pages[slot];

	/*
	 * If we deleted an initial piece of the WT_TRACK name space, it may no
	 * longer be in the right location.
	 *
	 * For example, imagine page #1 has the key range 30-50, it split, and
	 * we wrote page #2 with key range 30-40, and page #3 key range with
	 * 40-50, where pages #2 and #3 have larger LSNs than page #1.  When the
	 * key ranges were sorted, page #2 came first, then page #1 (because of
	 * their earlier start keys than page #3), and page #2 came before page
	 * #1 because of its LSN.  When we resolve the overlap between page #2
	 * and page #1, we truncate the initial key range of page #1, and it now
	 * sorts after page #3, because it has the same starting key of 40, and
	 * a lower LSN.
	 *
	 * First, update the WT_TRACK start key based on the specified stop key.
	 *
	 * Read and instantiate the WT_TRACK page (we don't have to verify the
	 * page, nor do we have to be quiet on error, we've already read this
	 * page successfully).
	 */
	WT_RET(__wt_scr_alloc(session, trk->trk_size, &dsk));
	WT_ERR(__wt_bt_read(session, dsk, trk->trk_addr, trk->trk_addr_size));
	WT_ERR(__wt_page_inmem(session, NULL, dsk->mem, 0, 0, &page));

	/*
	 * Walk the page, looking for a key sorting greater than the specified
	 * stop key -- that's our new start key.
	 */
	WT_ERR(__wt_scr_alloc(session, 0, &key));
	WT_ROW_FOREACH(page, rip, i) {
		WT_ERR(__wt_row_leaf_key(session, page, rip, key, false));
		WT_ERR(__wt_compare(session, btree->collator, key, stop, &cmp));
		if (cmp > 0) {
			found = true;
			break;
		}
	}

	/*
	 * We know that at least one key on the page sorts after the specified
	 * stop key, otherwise the page would have entirely overlapped and we
	 * would have discarded it, we wouldn't be here.  Therefore, this test
	 * is safe.  (But, it never hurts to check.)
	 */
	WT_ERR_TEST(!found, WT_ERROR);
	WT_ERR(__slvg_key_copy(session, &trk->row_start, key));

	/*
	 * We may need to re-sort some number of elements in the list.  Walk
	 * forward in the list until reaching an entry which cannot overlap
	 * the adjusted entry.  If it's more than a single slot, re-sort the
	 * entries.
	 */
	for (i = slot + 1; i < ss->pages_next; ++i) {
		if (ss->pages[i] == NULL)
			continue;
		WT_ERR(__wt_compare(session,
		    btree->collator, SLOT_START(i), &trk->row_stop, &cmp));
		if (cmp > 0)
			break;
	}
	i -= slot;
	if (i > 1)
		qsort(ss->pages + slot, (size_t)i,
		    sizeof(WT_TRACK *), __slvg_trk_compare_key);

err:	if (page != NULL)
		__wt_page_out(session, &page);
	__wt_scr_free(session, &dsk);
	__wt_scr_free(session, &key);

	return (ret);
}

/*
 * __slvg_row_build_internal --
 *	Build a row-store in-memory page that references all of the leaf
 *	pages we've found.
 */
static int
__slvg_row_build_internal(
    WT_SESSION_IMPL *session, uint32_t leaf_cnt, WT_STUFF *ss)
{
	WT_ADDR *addr;
	WT_DECL_RET;
	WT_PAGE *page;
	WT_PAGE_INDEX *pindex;
	WT_REF *ref, **refp;
	WT_TRACK *trk;
	uint32_t i;

	addr = NULL;

	/* Allocate a row-store root (internal) page and fill it in. */
	WT_RET(__wt_page_alloc(
	    session, WT_PAGE_ROW_INT, WT_RECNO_OOB, leaf_cnt, true, &page));
	WT_ERR(__slvg_modify_init(session, page));

	pindex = WT_INTL_INDEX_GET_SAFE(page);
	for (refp = pindex->index, i = 0; i < ss->pages_next; ++i) {
		if ((trk = ss->pages[i]) == NULL)
			continue;

		ref = *refp++;
		ref->home = page;
		ref->page = NULL;

		WT_ERR(__wt_calloc_one(session, &addr));
		WT_ERR(__wt_strndup(
		    session, trk->trk_addr, trk->trk_addr_size, &addr->addr));
		addr->size = trk->trk_addr_size;
		addr->type =
		    trk->trk_ovfl_cnt == 0 ? WT_ADDR_LEAF_NO : WT_ADDR_LEAF;
		ref->addr = addr;
		addr = NULL;

		__wt_ref_key_clear(ref);
		ref->state = WT_REF_DISK;

		/*
		 * If the page's key range is unmodified from when we read it
		 * (in other words, we didn't merge part of this page with
		 * another page), we can use the page without change, and the
		 * only thing we need to do is mark all overflow records the
		 * page references as in-use.
		 *
		 * If we did merge with another page, we have to build a page
		 * reflecting the updated key range.  Note, that requires an
		 * additional pass to free the merge page's backing blocks.
		 */
		if (F_ISSET(trk, WT_TRACK_MERGE)) {
			ss->merge_free = true;

			WT_ERR(__slvg_row_build_leaf(session, trk, ref, ss));
		} else {
			WT_ERR(__wt_row_ikey_incr(session, page, 0,
			    trk->row_start.data, trk->row_start.size, ref));

			WT_ERR(__slvg_ovfl_ref_all(session, trk));
		}
		++ref;
	}

	__wt_root_ref_init(&ss->root_ref, page, false);

	if (0) {
err:		__wt_free(session, addr);
		__wt_page_out(session, &page);
	}
	return (ret);
}

/*
 * __slvg_row_build_leaf --
 *	Build a row-store leaf page for a merged page.
 */
static int
__slvg_row_build_leaf(
    WT_SESSION_IMPL *session, WT_TRACK *trk, WT_REF *ref, WT_STUFF *ss)
{
	WT_BTREE *btree;
	WT_DECL_ITEM(key);
	WT_DECL_RET;
	WT_PAGE *page;
	WT_ROW *rip;
	WT_SALVAGE_COOKIE *cookie, _cookie;
	uint32_t i, skip_start, skip_stop;
	int cmp;

	btree = S2BT(session);
	page = NULL;

	cookie = &_cookie;
	WT_CLEAR(*cookie);

	/* Allocate temporary space in which to instantiate the keys. */
	WT_RET(__wt_scr_alloc(session, 0, &key));

	/* Get the original page, including the full in-memory setup. */
	WT_ERR(__wt_page_in(session, ref, 0));
	page = ref->page;

	/*
	 * Figure out how many page keys we want to take and how many we want
	 * to skip.
	 *
	 * If checking the starting range key, the key we're searching for will
	 * be equal to the starting range key.  This is because we figured out
	 * the true merged-page start key as part of discarding initial keys
	 * from the page (see the __slvg_row_range_overlap function, and its
	 * calls to __slvg_row_trk_update_start for more information).
	 *
	 * If checking the stopping range key, we want the keys on the page that
	 * are less-than the stopping range key.  This is because we copied a
	 * key from another page to define this page's stop range: that page is
	 * the page that owns the "equal to" range space.
	 */
	skip_start = skip_stop = 0;
	if (F_ISSET(trk, WT_TRACK_CHECK_START))
		WT_ROW_FOREACH(page, rip, i) {
			WT_ERR(
			    __wt_row_leaf_key(session, page, rip, key, false));

			/*
			 * >= is correct: see the comment above.
			 */
			WT_ERR(__wt_compare(session,
			    btree->collator, key, &trk->row_start, &cmp));
			if (cmp >= 0)
				break;
			WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s merge discarding leading key %.*s",
			    __wt_addr_string(session,
			    trk->trk_addr, trk->trk_addr_size, ss->tmp1),
			    __wt_buf_set_printable(
			    session, key->data, key->size, ss->tmp2)));
			++skip_start;
		}
	if (F_ISSET(trk, WT_TRACK_CHECK_STOP))
		WT_ROW_FOREACH_REVERSE(page, rip, i) {
			WT_ERR(
			    __wt_row_leaf_key(session, page, rip, key, false));

			/*
			 * < is correct: see the comment above.
			 */
			WT_ERR(__wt_compare(session,
			    btree->collator, key, &trk->row_stop, &cmp));
			if (cmp < 0)
				break;
			WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s merge discarding trailing key %.*s",
			    __wt_addr_string(session,
			    trk->trk_addr, trk->trk_addr_size, ss->tmp1),
			    __wt_buf_set_printable(
			    session, key->data, key->size, ss->tmp2)));
			++skip_stop;
		}

	/* We should have selected some entries, but not the entire page. */
	WT_ASSERT(session,
	    skip_start + skip_stop > 0 &&
	    skip_start + skip_stop < page->pg_row_entries);

	/*
	 * Take a copy of this page's first key to define the start of
	 * its range.  The key may require processing, otherwise, it's
	 * a copy from the page.
	 */
	rip = page->pg_row_d + skip_start;
	WT_ERR(__wt_row_leaf_key(session, page, rip, key, false));
	WT_ERR(__wt_row_ikey_incr(
	    session, ref->home, 0, key->data, key->size, ref));

	/* Set the referenced flag on overflow pages we're using. */
	if (trk->trk_ovfl_cnt != 0)
		WT_ERR(__slvg_row_ovfl(session,
		    trk, page, skip_start, page->pg_row_entries - skip_stop));

	/*
	 * Change the page to reflect the correct record count: there is no
	 * need to copy anything on the page itself, the entries value limits
	 * the number of page items.
	 */
	page->pg_row_entries -= skip_stop;
	cookie->skip = skip_start;

	/*
	 * We can't discard the original blocks associated with this page now.
	 * (The problem is we don't want to overwrite any original information
	 * until the salvage run succeeds -- if we free the blocks now, the next
	 * merge page we write might allocate those blocks and overwrite them,
	 * and should the salvage run eventually fail, the original information
	 * would have been lost.)  Clear the reference addr so eviction doesn't
	 * free the underlying blocks.
	 */
	__wt_ref_addr_free(session, ref);

	/* Write the new version of the leaf page to disk. */
	WT_ERR(__slvg_modify_init(session, page));
	WT_ERR(__wt_reconcile(session, ref, cookie, WT_VISIBILITY_ERR));

	/* Reset the page. */
	page->pg_row_entries += skip_stop;

	/*
	 * Discard our hazard pointer and evict the page, updating the
	 * parent's reference.
	 */
	ret = __wt_page_release(session, ref, 0);
	if (ret == 0)
		ret = __wt_evict(session, ref, true);

	if (0) {
err:		WT_TRET(__wt_page_release(session, ref, 0));
	}
	__wt_scr_free(session, &key);

	return (ret);
}

/*
 * __slvg_row_ovfl_single --
 *	Find a single overflow record in the merge page's list, and mark it as
 * referenced.
 */
static int
__slvg_row_ovfl_single(WT_SESSION_IMPL *session, WT_TRACK *trk, WT_CELL *cell)
{
	WT_CELL_UNPACK unpack;
	WT_TRACK *ovfl;
	uint32_t i;

	/* Unpack the cell, and check if it's an overflow record. */
	__wt_cell_unpack(cell, &unpack);
	if (unpack.type != WT_CELL_KEY_OVFL &&
	    unpack.type != WT_CELL_VALUE_OVFL)
		return (0);

	/*
	 * Search the list of overflow records for this page -- we should find
	 * exactly one match, and we mark it as referenced.
	 */
	for (i = 0; i < trk->trk_ovfl_cnt; ++i) {
		ovfl = trk->ss->ovfl[trk->trk_ovfl_slot[i]];
		if (unpack.size == ovfl->trk_addr_size &&
		    memcmp(unpack.data, ovfl->trk_addr, unpack.size) == 0)
			return (__slvg_ovfl_ref(session, ovfl, true));
	}

	WT_PANIC_RET(session,
	    EINVAL, "overflow record at row-store page merge not found");
}

/*
 * __slvg_row_ovfl --
 *	Mark overflow items referenced by the merged page.
 */
static int
__slvg_row_ovfl(WT_SESSION_IMPL *session,
    WT_TRACK *trk, WT_PAGE *page, uint32_t start, uint32_t stop)
{
	WT_CELL *cell;
	WT_ROW *rip;
	void *copy;

	/*
	 * We're merging a row-store page, and we took some number of records,
	 * figure out which (if any) overflow records we used.
	 */
	for (rip = page->pg_row_d + start; start < stop; ++start, ++rip) {
		copy = WT_ROW_KEY_COPY(rip);
		(void)__wt_row_leaf_key_info(
		    page, copy, NULL, &cell, NULL, NULL);
		if (cell != NULL)
			WT_RET(__slvg_row_ovfl_single(session, trk, cell));
		cell = __wt_row_leaf_value_cell(page, rip, NULL);
		if (cell != NULL)
			WT_RET(__slvg_row_ovfl_single(session, trk, cell));
	}
	return (0);
}

/*
 * __slvg_trk_compare_addr --
 *	Compare two WT_TRACK array entries by address cookie.
 */
static int WT_CDECL
__slvg_trk_compare_addr(const void *a, const void *b)
{
	WT_DECL_RET;
	WT_TRACK *a_trk, *b_trk;
	size_t len;

	a_trk = *(WT_TRACK **)a;
	b_trk = *(WT_TRACK **)b;

	/*
	 * We don't care about the order because these are opaque cookies --
	 * we're just sorting them so we can binary search instead of linear
	 * search.
	 */
	len = WT_MIN(a_trk->trk_addr_size, b_trk->trk_addr_size);
	ret = memcmp(a_trk->trk_addr, b_trk->trk_addr, len);
	if (ret == 0)
		ret = a_trk->trk_addr_size > b_trk->trk_addr_size ? -1 : 1;
	return (ret);
}

/*
 * __slvg_ovfl_compare --
 *	Bsearch comparison routine for the overflow array.
 */
static int WT_CDECL
__slvg_ovfl_compare(const void *a, const void *b)
{
	WT_ADDR *addr;
	WT_DECL_RET;
	WT_TRACK *trk;
	size_t len;

	addr = (WT_ADDR *)a;
	trk = *(WT_TRACK **)b;

	len = WT_MIN(trk->trk_addr_size, addr->size);
	ret = memcmp(addr->addr, trk->trk_addr, len);
	if (ret == 0 && addr->size != trk->trk_addr_size)
		ret = addr->size < trk->trk_addr_size ? -1 : 1;
	return (ret);
}

/*
 * __slvg_ovfl_reconcile --
 *	Review relationships between leaf pages and the overflow pages, delete
 * leaf pages until there's a one-to-one relationship between leaf and overflow
 * pages.
 */
static int
__slvg_ovfl_reconcile(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_ADDR *addr;
	WT_DECL_RET;
	WT_TRACK **searchp, *trk;
	uint32_t i, j, *slot;

	slot = NULL;

	/*
	 * If an overflow page is referenced more than once, discard leaf pages
	 * with the lowest LSNs until overflow pages are only referenced once.
	 *
	 * This requires sorting the page list by LSN, and the overflow array

	 * by address cookie.
	 */
	qsort(ss->pages,
	    (size_t)ss->pages_next, sizeof(WT_TRACK *), __slvg_trk_compare_gen);
	qsort(ss->ovfl,
	    (size_t)ss->ovfl_next, sizeof(WT_TRACK *), __slvg_trk_compare_addr);

	/*
	 * Walk the list of pages and discard any pages referencing non-existent
	 * overflow pages or referencing overflow pages also referenced by pages
	 * with higher LSNs.  Our caller sorted the page list by LSN, high to
	 * low, so we don't have to do explicit testing of the page LSNs, the
	 * first page to reference an overflow page is the best page to own it.
	 */
	for (i = 0; i < ss->pages_next; ++i) {
		if ((trk = ss->pages[i]) == NULL || trk->trk_ovfl_cnt == 0)
			continue;

		WT_ERR(__wt_calloc_def(session, trk->trk_ovfl_cnt, &slot));
		for (j = 0; j < trk->trk_ovfl_cnt; ++j) {
			addr = &trk->trk_ovfl_addr[j];
			searchp = bsearch(addr, ss->ovfl, ss->ovfl_next,
			    sizeof(WT_TRACK *), __slvg_ovfl_compare);

			/*
			 * If the overflow page doesn't exist or if another page
			 * has already claimed it, this leaf page isn't usable.
			 */
			if (searchp != NULL &&
			    !F_ISSET(*searchp, WT_TRACK_OVFL_REFD)) {
				/*
				 * Convert each block address into a slot in the
				 * list of overflow pages as we go.
				 */
				slot[j] = (uint32_t)(searchp - ss->ovfl);
				F_SET(*searchp, WT_TRACK_OVFL_REFD);
				continue;
			}

			WT_ERR(__wt_verbose(session, WT_VERB_SALVAGE,
			    "%s references unavailable overflow page %s",
			    __wt_addr_string(session,
			    trk->trk_addr, trk->trk_addr_size, ss->tmp1),
			    __wt_addr_string(session,
			    addr->addr, addr->size, ss->tmp2)));

			/*
			 * Clear the "referenced" flag for any overflow pages
			 * already claimed by this leaf page some other page
			 * might claim them.
			 */
			while (j > 0)
				F_CLR(ss->ovfl[slot[--j]], WT_TRACK_OVFL_REFD);
			trk = NULL;
			WT_ERR(__slvg_trk_free(session, &ss->pages[i], true));
			break;
		}

		/*
		 * We now have a reference to the overflow WT_TRACK, and so no
		 * longer need the page's address array, discard it.  Note, we
		 * potentially freed the WT_TRACK in the loop above, check it's
		 * still valid.
		 */
		if (trk == NULL)
			__wt_free(session, slot);
		else {
			__slvg_trk_free_addr(session, trk);

			trk->trk_ovfl_slot = slot;
			slot = NULL;
		}
	}
	return (0);

err:	__wt_free(session, slot);
	return (ret);
}

/*
 * __slvg_trk_compare_key --
 *	Compare two WT_TRACK array entries by key, and secondarily, by LSN.
 */
static int WT_CDECL
__slvg_trk_compare_key(const void *a, const void *b)
{
	WT_SESSION_IMPL *session;
	WT_TRACK *a_trk, *b_trk;
	uint64_t a_gen, a_recno, b_gen, b_recno;
	int cmp;

	a_trk = *(WT_TRACK **)a;
	b_trk = *(WT_TRACK **)b;

	if (a_trk == NULL)
		return (b_trk == NULL ? 0 : 1);
	if (b_trk == NULL)
		return (-1);

	switch (a_trk->ss->page_type) {
	case WT_PAGE_COL_FIX:
	case WT_PAGE_COL_VAR:
		a_recno = a_trk->col_start;
		b_recno = b_trk->col_start;
		if (a_recno == b_recno)
			break;
		if (a_recno > b_recno)
			return (1);
		if (a_recno < b_recno)
			return (-1);
		break;
	case WT_PAGE_ROW_LEAF:
		/*
		 * XXX
		 * __wt_compare can potentially fail, and we're ignoring that
		 * error because this routine is called as an underlying qsort
		 * routine.
		 */
		session = a_trk->ss->session;
		(void)__wt_compare(session, S2BT(session)->collator,
		    &a_trk->row_start, &b_trk->row_start, &cmp);
		if (cmp != 0)
			return (cmp);
		break;
	}

	/*
	 * If the primary keys compare equally, differentiate based on LSN.
	 * Sort from highest LSN to lowest, that is, the earlier pages in
	 * the array are more desirable.
	 */
	a_gen = a_trk->trk_gen;
	b_gen = b_trk->trk_gen;
	return (a_gen > b_gen ? -1 : (a_gen < b_gen ? 1 : 0));
}

/*
 * __slvg_trk_compare_gen --
 *	Compare two WT_TRACK array entries by LSN.
 */
static int WT_CDECL
__slvg_trk_compare_gen(const void *a, const void *b)
{
	WT_TRACK *a_trk, *b_trk;
	uint64_t a_gen, b_gen;

	a_trk = *(WT_TRACK **)a;
	b_trk = *(WT_TRACK **)b;

	/*
	 * Sort from highest LSN to lowest, that is, the earlier pages in the
	 * array are more desirable.
	 */
	a_gen = a_trk->trk_gen;
	b_gen = b_trk->trk_gen;
	return (a_gen > b_gen ? -1 : (a_gen < b_gen ? 1 : 0));
}

/*
 * __slvg_merge_block_free --
 *	Clean up backing file and overflow blocks after the merge phase.
 */
static int
__slvg_merge_block_free(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_TRACK *trk;
	uint32_t i;

	/* Free any underlying file blocks for merged pages. */
	for (i = 0; i < ss->pages_next; ++i) {
		if ((trk = ss->pages[i]) == NULL)
			continue;
		if (F_ISSET(trk, WT_TRACK_MERGE))
			WT_RET(__slvg_trk_free(session, &ss->pages[i], true));
	}

	/* Free any unused overflow records. */
	return (__slvg_ovfl_discard(session, ss));
}

/*
 * __slvg_ovfl_ref --
 *	Reference an overflow page, checking for multiple references.
 */
static int
__slvg_ovfl_ref(WT_SESSION_IMPL *session, WT_TRACK *trk, bool multi_panic)
{
	if (F_ISSET(trk, WT_TRACK_OVFL_REFD)) {
		if (!multi_panic)
			return (EBUSY);
		WT_PANIC_RET(session, EINVAL,
		    "overflow record unexpectedly referenced multiple times "
		    "during leaf page merge");
	}

	F_SET(trk, WT_TRACK_OVFL_REFD);
	return (0);
}

/*
 * __slvg_ovfl_ref_all --
 *	Reference all of the page's overflow pages.
 */
static int
__slvg_ovfl_ref_all(WT_SESSION_IMPL *session, WT_TRACK *trk)
{
	uint32_t i;

	for (i = 0; i < trk->trk_ovfl_cnt; ++i)
		WT_RET(__slvg_ovfl_ref(
		    session, trk->ss->ovfl[trk->trk_ovfl_slot[i]], 1));

	return (0);
}

/*
 * __slvg_ovfl_discard --
 *	Discard unused overflow pages.
 */
static int
__slvg_ovfl_discard(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	WT_TRACK *trk;
	uint32_t i;

	/*
	 * Walk the overflow page array: if an overflow page isn't referenced,
	 * add its file blocks to the free list.
	 *
	 * Clear the reference flag (it's reused to figure out if the overflow
	 * record is referenced, but never used, by merged pages).
	 */
	for (i = 0; i < ss->ovfl_next; ++i) {
		if ((trk = ss->ovfl[i]) == NULL)
			continue;

		if (F_ISSET(trk, WT_TRACK_OVFL_REFD)) {
			F_CLR(trk, WT_TRACK_OVFL_REFD);
			continue;
		}
		WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
		    "%s unused overflow page",
		    __wt_addr_string(
		    session, trk->trk_addr, trk->trk_addr_size, ss->tmp1)));
		WT_RET(__slvg_trk_free(session, &ss->ovfl[i], true));
	}

	return (0);
}

/*
 * __slvg_cleanup --
 *	Discard memory allocated to the page and overflow arrays.
 */
static int
__slvg_cleanup(WT_SESSION_IMPL *session, WT_STUFF *ss)
{
	uint32_t i;

	/* Discard the leaf page array. */
	for (i = 0; i < ss->pages_next; ++i)
		if (ss->pages[i] != NULL)
			WT_RET(__slvg_trk_free(session, &ss->pages[i], false));
	__wt_free(session, ss->pages);

	/* Discard the ovfl page array. */
	for (i = 0; i < ss->ovfl_next; ++i)
		if (ss->ovfl[i] != NULL)
			WT_RET(__slvg_trk_free(session, &ss->ovfl[i], false));
	__wt_free(session, ss->ovfl);

	return (0);
}

/*
 * __slvg_trk_free_addr --
 *	Discard address information.
 */
static void
__slvg_trk_free_addr(WT_SESSION_IMPL *session, WT_TRACK *trk)
{
	uint32_t i;

	if (trk->trk_ovfl_addr != NULL) {
		for (i = 0; i < trk->trk_ovfl_cnt; ++i)
			__wt_free(session, trk->trk_ovfl_addr[i].addr);
		__wt_free(session, trk->trk_ovfl_addr);
	}
}

/*
 * __slvg_trk_free_block --
 *	Discard underlying blocks.
 */
static int
__slvg_trk_free_block(WT_SESSION_IMPL *session, WT_TRACK *trk)
{
	WT_BM *bm;

	bm = S2BT(session)->bm;

	/*
	 * If freeing underlying file blocks or overflow pages, this is a page
	 * we were tracking but eventually decided not to use.
	 */
	WT_RET(__wt_verbose(session, WT_VERB_SALVAGE,
	    "%s blocks discarded: discard freed file bytes %" PRIu32,
	    __wt_addr_string(session,
	    trk->trk_addr, trk->trk_addr_size, trk->ss->tmp1), trk->trk_size));

	return (bm->free(bm, session, trk->trk_addr, trk->trk_addr_size));
}

/*
 * __slvg_trk_free --
 *	Discard a WT_TRACK structure and (optionally) its underlying blocks.
 */
static int
__slvg_trk_free(
    WT_SESSION_IMPL *session, WT_TRACK **trkp, bool free_on_last_ref)
{
	WT_TRACK *trk;

	trk = *trkp;
	*trkp = NULL;

	/*
	 * If we're the last user of shared information, clean up.
	 */
	WT_ASSERT(session, trk->shared->ref > 0);
	if (--trk->shared->ref == 0) {
		/*
		 * If the free-on-last-ref flag is set, this chunk isn't going
		 * to use the backing physical blocks.  As we're the last user
		 * of those blocks, nobody is going to use them and they can be
		 * discarded.
		 */
		if (free_on_last_ref)
			WT_RET(__slvg_trk_free_block(session, trk));

		__wt_free(session, trk->trk_addr);

		__slvg_trk_free_addr(session, trk);

		__wt_free(session, trk->trk_ovfl_slot);

		__wt_free(session, trk->shared);
	}

	if (trk->ss->page_type == WT_PAGE_ROW_LEAF) {
		__wt_buf_free(session, &trk->row_start);
		__wt_buf_free(session, &trk->row_stop);
	}

	__wt_free(session, trk);

	return (0);
}