Import wiredtiger: fc383862a729667bdd4011c363601c180f848d65 from branch mongodb-3.8

ref: 357efdd4ce..fc383862a7
for: 3.7.2

WT-3074       Automate a test to stress eviction walk with many active trees
WT-3799       Test/format with timestamps enabled pin cache full
WT-3835       cursor remove tries to return a key that doesn't exist
WT-3846       Refine operation tracking visualization tool
WT-3853       LSM version 1 metadata incompatibility
WT-3860       Fix a list of lint issues
WT-3862       Remove invalid diagnostic assertion during reconciliation

12 files changed, 327 insertions, 246 deletions

diff --git a/src/third_party/wiredtiger/bench/wtperf/runners/evict-fairness.wtperf b/src/third_party/wiredtiger/bench/wtperf/runners/evict-fairness.wtperf
new file mode 100644
index 00000000000..94f55f6bea9
--- /dev/null
+++ b/src/third_party/wiredtiger/bench/wtperf/runners/evict-fairness.wtperf
@@ -0,0 +1,20 @@
+# This configuration is used to test the eviction fairness of visiting all tables.
+# Create a set of tables with uneven distribution of data
+conn_config="cache_size=1G,eviction=(threads_max=8),file_manager=(close_idle_time=100000),checkpoint=(wait=20,log_size=2GB),session_max=1000"
+table_config="type=file"
+table_count=200
+icount=0
+random_range=1000000000
+pareto=0
+range_partition=true
+report_interval=5
+
+run_ops=1000000
+populate_threads=0
+icount=0
+threads=((count=60,inserts=1))
+
+# Warn if a latency over 1 second is seen
+max_latency=1000
+sample_interval=5
+sample_rate=1
diff --git a/src/third_party/wiredtiger/dist/s_clang-tidy b/src/third_party/wiredtiger/dist/s_clang-tidy
index 209d6f7d5d5..89d3fa4112a 100644
--- a/src/third_party/wiredtiger/dist/s_clang-tidy
+++ b/src/third_party/wiredtiger/dist/s_clang-tidy
@@ -32,18 +32,14 @@ sh autogen.sh > /dev/null || exit 1
 
 # We need a custom wiredtiger_config.h, clang-tidy doesn't know where to
 # find the x86intrin.h include file.
-echo '!!!!'
-echo 'Modifying wiredtiger_config.h'
-echo '!!!!'
 cp wiredtiger_config.h $t
 sed '/HAVE_X86INTRIN_H/d' < $t > wiredtiger_config.h
 
-# XXX
-# clang-tidy doesn't like verify_build at the moment.
-echo '!!!!'
-echo 'Modifying src/include/verify_build.h'
-echo '!!!!'
-echo '#define WT_STATIC_ASSERT(a)' > src/include/verify_build.h
+# We need a custom verify_build.h, clang-tidy doesn't like the magic.
+f=src/include/verify_build.h
+rm -f $f.save
+cp $f $f.save
+echo '#define WT_STATIC_ASSERT(a)' > $f
 
 def="-D_GNU_SOURCE"
 inc="-I. -Isrc/include"
@@ -81,4 +77,9 @@ sed -e '/ warnings generated/d' \
     -e '/Suppressed.*warnings/d' \
     -e '/Use -header-filter/d' < $t
 
+# Restore verify_build.h.
+f=src/include/verify_build.h
+rm -f $f
+mv $f.save $f
+
 exit 0
diff --git a/src/third_party/wiredtiger/import.data b/src/third_party/wiredtiger/import.data
index dc3e684a19f..a67a400e735 100644
--- a/src/third_party/wiredtiger/import.data
+++ b/src/third_party/wiredtiger/import.data
@@ -1,5 +1,5 @@
 {
-    "commit": "357efdd4ce279efc71ff618c59fe1b903ef80bb2", 
+    "commit": "fc383862a729667bdd4011c363601c180f848d65", 
     "github": "wiredtiger/wiredtiger.git", 
     "vendor": "wiredtiger", 
     "branch": "mongodb-3.8"
diff --git a/src/third_party/wiredtiger/src/btree/bt_cursor.c b/src/third_party/wiredtiger/src/btree/bt_cursor.c
index 6e90447f18d..8c7170e6180 100644
--- a/src/third_party/wiredtiger/src/btree/bt_cursor.c
+++ b/src/third_party/wiredtiger/src/btree/bt_cursor.c
@@ -1067,13 +1067,6 @@ err:	if (ret == WT_RESTART) {
 		goto retry;
 	}
 
-	/*
-	 * If the cursor is configured to overwrite and the record is not found,
-	 * that is exactly what we want, return success.
-	 */
-	if (F_ISSET(cursor, WT_CURSTD_OVERWRITE) && ret == WT_NOTFOUND)
-		ret = 0;
-
 done:	if (ret == 0) {
 		F_CLR(cursor, WT_CURSTD_VALUE_SET);
 		switch (positioned) {
@@ -1104,6 +1097,19 @@ done:	if (ret == 0) {
 	if (ret != 0) {
 		WT_TRET(__cursor_reset(cbt));
 		__cursor_state_restore(cursor, &state);
+
+		/*
+		 * If the cursor is configured to overwrite and the record isn't
+		 * found, that is exactly what we want, return success. Note we
+		 * set clear the return value after everything else, the clause
+		 * above dealing with the cursor position is only correct if we
+		 * were successful. If search failed after positioned is set to
+		 * SEARCH_POSITION, we cannot return a key. The only action to
+		 * take is to set the cursor to its original key, which we just
+		 * did.
+		 */
+		if (F_ISSET(cursor, WT_CURSTD_OVERWRITE) && ret == WT_NOTFOUND)
+			ret = 0;
 	}
 
 	return (ret);
diff --git a/src/third_party/wiredtiger/src/evict/evict_page.c b/src/third_party/wiredtiger/src/evict/evict_page.c
index 0ff314f3484..6d904a2004b 100644
--- a/src/third_party/wiredtiger/src/evict/evict_page.c
+++ b/src/third_party/wiredtiger/src/evict/evict_page.c
@@ -306,16 +306,14 @@ __evict_page_dirty_update(WT_SESSION_IMPL *session, WT_REF *ref, bool closing)
 	switch (mod->rec_result) {
 	case WT_PM_REC_EMPTY:				/* Page is empty */
 		/*
-		 * Update the parent to reference a deleted page.  The fact that
-		 * reconciliation left the page "empty" means there's no older
-		 * transaction in the system that might need to see an earlier
-		 * version of the page.  For that reason, we clear the address
-		 * of the page, if we're forced to "read" into that namespace,
-		 * we'll instantiate a new page instead of trying to read from
-		 * the backing store.
+		 * Update the parent to reference a deleted page. Reconciliation
+		 * left the page "empty", so there's no older transaction in the
+		 * system that might need to see an earlier version of the page.
+		 * There's no backing address, if we're forced to "read" into
+		 * that namespace, we instantiate a new page instead of trying
+		 * to read from the backing store.
 		 */
 		__wt_ref_out(session, ref);
-		ref->addr = NULL;
 		WT_WITH_PAGE_INDEX(session,
 		    ret = __evict_delete_ref(session, ref, closing));
 		WT_RET_BUSY_OK(ret);
@@ -354,9 +352,7 @@ __evict_page_dirty_update(WT_SESSION_IMPL *session, WT_REF *ref, bool closing)
 		 * Publish: a barrier to ensure the structure fields are set
 		 * before the state change makes the page available to readers.
 		 */
-		if (mod->mod_replace.addr == NULL)
-			ref->addr = NULL;
-		else {
+		if (mod->mod_replace.addr != NULL) {
 			WT_RET(__wt_calloc_one(session, &addr));
 			*addr = mod->mod_replace;
 			mod->mod_replace.addr = NULL;
diff --git a/src/third_party/wiredtiger/src/lsm/lsm_meta.c b/src/third_party/wiredtiger/src/lsm/lsm_meta.c
index 88daca989a6..de12f19380b 100644
--- a/src/third_party/wiredtiger/src/lsm/lsm_meta.c
+++ b/src/third_party/wiredtiger/src/lsm/lsm_meta.c
@@ -201,9 +201,12 @@ __lsm_meta_read_v1(
 		    cv.str, cv.len, &lsm_tree->collator_name));
 	}
 
-	WT_ERR(__wt_config_getones(
-	    session, lsmconf, "lsm.merge_custom.start_generation", &cv));
-	lsm_tree->custom_generation = (uint32_t)cv.val;
+	/* lsm.merge_custom does not appear in all V1 LSM metadata. */
+	lsm_tree->custom_generation = 0;
+	if ((ret = __wt_config_getones(
+	    session, lsmconf, "lsm.merge_custom.start_generation", &cv)) == 0)
+		lsm_tree->custom_generation = (uint32_t)cv.val;
+	WT_ERR_NOTFOUND_OK(ret);
 	if (lsm_tree->custom_generation != 0) {
 		WT_ERR(__wt_config_getones(
 		    session, lsmconf, "lsm.merge_custom.prefix", &cv));
diff --git a/src/third_party/wiredtiger/src/reconcile/rec_write.c b/src/third_party/wiredtiger/src/reconcile/rec_write.c
index 3ad6bdf41ea..d9b415a76cd 100644
--- a/src/third_party/wiredtiger/src/reconcile/rec_write.c
+++ b/src/third_party/wiredtiger/src/reconcile/rec_write.c
@@ -1347,7 +1347,6 @@ __rec_txn_read(WT_SESSION_IMPL *session, WT_RECONCILE *r,
 		    (F_ISSET(r, WT_REC_VISIBLE_ALL) ?
 		    WT_TXNID_LE(r->last_running, txnid) :
 		    !__txn_visible_id(session, txnid))) {
-			WT_ASSERT(session, upd->type != WT_UPDATE_BIRTHMARK);
 			uncommitted = r->update_uncommitted = true;
 			continue;
 		}
diff --git a/src/third_party/wiredtiger/src/utilities/util_main.c b/src/third_party/wiredtiger/src/utilities/util_main.c
index fb9fb433892..2d08c4c5274 100644
--- a/src/third_party/wiredtiger/src/utilities/util_main.c
+++ b/src/third_party/wiredtiger/src/utilities/util_main.c
@@ -41,7 +41,7 @@ usage(void)
 	    "\t" "compact\t  compact an object\n"
 	    "\t" "copyright copyright information\n"
 	    "\t" "create\t  create an object\n"
-	    "\t" "downgrade\t  downgrade an database\n"
+	    "\t" "downgrade downgrade a database\n"
 	    "\t" "drop\t  drop an object\n"
 	    "\t" "dump\t  dump an object\n"
 	    "\t" "list\t  list database objects\n"
diff --git a/src/third_party/wiredtiger/test/format/util.c b/src/third_party/wiredtiger/test/format/util.c
index b8343fee1d6..aa31521c3b7 100644
--- a/src/third_party/wiredtiger/test/format/util.c
+++ b/src/third_party/wiredtiger/test/format/util.c
@@ -621,6 +621,15 @@ timestamp(void *arg)
 		}
 
 		/*
+		 * Don't try to update until we've committed some transactions
+		 * with timestamps.
+		 */
+		if (oldest_timestamp == 0) {
+			__wt_sleep(1, 0);
+			continue;
+		}
+
+		/*
 		 * If less than 100 transactions out of date, wait up to 15
 		 * seconds before updating.
 		 */
diff --git a/src/third_party/wiredtiger/tools/optrack/arrow-left.png b/src/third_party/wiredtiger/tools/optrack/arrow-left.png
deleted file mode 100644
index 315983e3118..00000000000
--- a/src/third_party/wiredtiger/tools/optrack/arrow-left.png
+++ /dev/null
diff --git a/src/third_party/wiredtiger/tools/optrack/arrow-right.png b/src/third_party/wiredtiger/tools/optrack/arrow-right.png
deleted file mode 100644
index e874d0f55fc..00000000000
--- a/src/third_party/wiredtiger/tools/optrack/arrow-right.png
+++ /dev/null
diff --git a/src/third_party/wiredtiger/tools/optrack/find-latency-spikes.py b/src/third_party/wiredtiger/tools/optrack/find-latency-spikes.py
index 5bb557ce21b..ac80b78bc5d 100755
--- a/src/third_party/wiredtiger/tools/optrack/find-latency-spikes.py
+++ b/src/third_party/wiredtiger/tools/optrack/find-latency-spikes.py
@@ -1,9 +1,36 @@
 #!/usr/bin/env python
+#
+# Public Domain 2014-2018 MongoDB, Inc.
+# Public Domain 2008-2014 WiredTiger, Inc.
+#
+# This is free and unencumbered software released into the public domain.
+#
+# Anyone is free to copy, modify, publish, use, compile, sell, or
+# distribute this software, either in source code form or as a compiled
+# binary, for any purpose, commercial or non-commercial, and by any
+# means.
+#
+# In jurisdictions that recognize copyright laws, the author or authors
+# of this software dedicate any and all copyright interest in the
+# software to the public domain. We make this dedication for the benefit
+# of the public at large and to the detriment of our heirs and
+# successors. We intend this dedication to be an overt act of
+# relinquishment in perpetuity of all present and future rights to this
+# software under copyright law.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+# OTHER DEALINGS IN THE SOFTWARE.
+#!/usr/bin/env python
 
 import argparse
 from bokeh.layouts import column
 from bokeh.models import ColumnDataSource, CustomJS, HoverTool, FixedTicker
-from bokeh.models import Legend, LegendItem
+from bokeh.models import  LabelSet, Legend, LegendItem
 from bokeh.models import NumeralTickFormatter, OpenURL, Range1d, TapTool
 from bokeh.models.annotations import Label
 from bokeh.plotting import figure, output_file, reset_output, save, show
@@ -15,10 +42,6 @@ import pandas as pd
 import sys
 import traceback
 
-# Names of the image files we use
-arrowLeftImg = "arrow-left.png";
-arrowRightImg = "arrow-right.png";
-
 # A directory where we store cross-file plots for each bucket of the outlier
 # histogram.
 #
@@ -30,16 +53,16 @@ colorList = [];
 # Codes for various colors for printing of informational and error messages.
 #
 class color:
-   PURPLE = '\033[95m'
-   CYAN = '\033[96m'
-   DARKCYAN = '\033[36m'
-   BLUE = '\033[94m'
-   GREEN = '\033[92m'
-   YELLOW = '\033[93m'
-   RED = '\033[91m'
-   BOLD = '\033[1m'
-   UNDERLINE = '\033[4m'
-   END = '\033[0m'
+    PURPLE = '\033[95m'
+    CYAN = '\033[96m'
+    DARKCYAN = '\033[36m'
+    BLUE = '\033[94m'
+    GREEN = '\033[92m'
+    YELLOW = '\033[93m'
+    RED = '\033[91m'
+    BOLD = '\033[1m'
+    UNDERLINE = '\033[4m'
+    END = '\033[0m'
 
 # A function name mapped to its corresponding color.
 #
@@ -80,7 +103,6 @@ pixelsPerWidthUnit = 5;
 #
 STDEV_MULT = 2;
 
-
 def initColorList():
 
     global colorList;
@@ -109,7 +131,6 @@ def getColorForFunction(function):
 
     return funcToColor[function];
 
-
 #
 # An intervalEnd is a tuple of three items.
 # item #0 is the timestamp,
@@ -151,9 +172,6 @@ def getIntervalData(intervalBeginningsStack, intervalEnd, logfile):
         else:
             matchFound = True;
 
-    # This value determines how deep we are in the callstack
-    # stackDepth = len(intervalBeginningsStack);
-
     return intervalBegin[0], intervalEnd[0], intervalEnd[2], errorOccurred;
 
 def plotOutlierHistogram(dataframe, maxOutliers, func, durationThreshold,
@@ -179,7 +197,8 @@ def plotOutlierHistogram(dataframe, maxOutliers, func, durationThreshold,
                                        * pixelsPerHeightUnit + \
                                        pixelsForTitle)),
                x_axis_label = "Execution timeline (CPU cycles)",
-               y_axis_label = "Number of outliers", tools = TOOLS);
+               y_axis_label = "Number of outliers",
+               tools = TOOLS, toolbar_location="above");
 
     y_ticker_max = p.plot_height / pixelsPerHeightUnit;
     y_ticker_step = max(1, (maxOutliers + 1)/y_ticker_max);
@@ -316,12 +335,6 @@ def createCallstackSeries(data, logfilename):
             beginIntervals.append(intervalBegin);
             endIntervals.append(intervalEnd);
             functionNames.append(function);
-            #stackDepths.append(stackDepth);
-            #stackDepthsNext.append(stackDepth + 1);
-
-            #print("Begin: " + str(intervalBegin)),
-            #print(" Func: " + function),
-            #print(" Stack depth: " + str(stackDepth));
 
         else:
             print("Invalid event in this line:");
@@ -352,27 +365,110 @@ def createCallstackSeries(data, logfilename):
 
     return dataframe;
 
-def addLegend(p, legendItems, numLegends):
-
-    legend = Legend(items=legendItems, orientation = "horizontal");
-    p.add_layout(legend, place='above');
-    legendItems[:] = [];  # Empty the list.
-
-    return (numLegends + 1);
-
 # For each function we only show the legend once. In this dictionary we
 # keep track of colors already used.
 #
 colorAlreadyUsedInLegend = {};
 
+def createLegendFigure(legendDict):
+
+    global pixelsForTitle;
+    global plotWidth;
+
+    FUNCS_PER_ROW = 5;
+    HSPACE_BETWEEN_FUNCS = 10;
+    VSPACE_BETWEEN_FUNCS = 1;
+
+    funcs = [];
+    colors = [];
+    x_coords = [];
+    y_coords = [];
+    pixelsForLegendItem = 20;
+
+    # Get a sorted list of functions and their
+    # corresponding colors.
+    #
+    for func in sorted(legendDict.keys()):
+        funcs.append(func);
+        colors.append(legendDict[func]);
+
+    # Figure out the coordinates of functions on the plot
+    #
+    for i in range(len(funcs)):
+
+        x_coord = i % (FUNCS_PER_ROW) + 1;
+        x_coord += i % (FUNCS_PER_ROW) *  HSPACE_BETWEEN_FUNCS;
+        x_coords.append(x_coord);
+
+        y_coord = (i/FUNCS_PER_ROW) + 1;
+        y_coord += (i/FUNCS_PER_ROW) *  VSPACE_BETWEEN_FUNCS;
+        y_coords.append(y_coord);
+
+    data = {};
+    data['func'] = funcs;
+    data['color'] = colors;
+    data['left'] = x_coords;
+    data['bottom'] = y_coords;
+
+    df = pd.DataFrame(data=data);
+
+    max_ycoord = df['bottom'].max();
+    df['bottom'] = (max_ycoord + 1) - df['bottom'];
+
+    df['right'] = df['left'] + 1;
+    df['top'] = df['bottom'] + 1;
+
+    cds = ColumnDataSource(df);
+
+    p = figure(title="TRACKED FUNCTIONS",
+               plot_width=plotWidth,
+               plot_height = max((max_ycoord + 2) * pixelsForLegendItem, 90),
+               tools = [], toolbar_location="above",
+               x_range = (0, (FUNCS_PER_ROW + 1)* HSPACE_BETWEEN_FUNCS),
+               y_range = (0, max_ycoord + 2),
+               x_axis_label = "",
+               y_axis_label = "");
+
+    p.title.align = "center";
+    p.title.text_font_style = "normal";
+
+    p.xaxis.axis_line_color = "lightgrey";
+    p.xaxis.major_tick_line_color = None;
+    p.xaxis.minor_tick_line_color = None;
+    p.xaxis.major_label_text_font_size = '0pt';
+
+    p.yaxis.axis_line_color = "lightgrey";
+    p.yaxis.major_tick_line_color = None;
+    p.yaxis.minor_tick_line_color = None;
+    p.yaxis.major_label_text_font_size = '0pt';
+
+    p.xgrid.grid_line_color = None;
+    p.ygrid.grid_line_color = None;
+
+    p.outline_line_width = 1
+    p.outline_line_alpha = 1
+    p.outline_line_color = "lightgrey"
+
+    p.quad(left = 'left', right = 'right', bottom = 'bottom',
+           top = 'top', color = 'color', line_color = "lightgrey",
+           line_width = 0.5, source=cds);
+
+    labels = LabelSet(x='right', y='bottom', text='func', level='glyph',
+                      text_font_size = "10pt",
+                      x_offset=3, y_offset=0, source=cds, render_mode='canvas');
+    p.add_layout(labels);
+
+    return p;
+
 def generateBucketChartForFile(figureName, dataframe, y_max, x_min, x_max):
 
     global colorAlreadyUsedInLegend;
     global funcToColor;
+    global plotWidth;
 
-    MAX_ITEMS_PER_LEGEND = 5;
+    MAX_ITEMS_PER_LEGEND = 10;
     numLegends = 0;
-    legendItems = [];
+    legendItems = {};
     pixelsPerStackLevel = 30;
     pixelsPerLegend = 60;
     pixelsForTitle = 30;
@@ -387,13 +483,12 @@ def generateBucketChartForFile(figureName, dataframe, y_max, x_min, x_max):
 
     TOOLS = [hover];
 
-    p = figure(title=figureName, plot_width=1200,
+    p = figure(title=figureName, plot_width=plotWidth,
                x_range = (x_min, x_max),
                y_range = (0, y_max+1),
                x_axis_label = "Time (CPU cycles)",
                y_axis_label = "Stack depth",
-               tools = TOOLS
-    );
+               tools = TOOLS, toolbar_location="above");
 
     # No minor ticks or labels on the y-axis
     p.yaxis.major_tick_line_color = None;
@@ -402,7 +497,8 @@ def generateBucketChartForFile(figureName, dataframe, y_max, x_min, x_max):
     p.yaxis.ticker = FixedTicker(ticks = range(0, y_max+1));
     p.ygrid.ticker = FixedTicker(ticks = range(0, y_max+1));
 
-    p.xaxis.formatter = NumeralTickFormatter(format="0,")
+    p.xaxis.formatter = NumeralTickFormatter(format="0,");
+    p.title.text_font_style = "bold";
 
     p.quad(left = 'start', right = 'end', bottom = 'stackdepth',
            top = 'stackdepthNext', color = 'color', line_color = "lightgrey",
@@ -427,28 +523,13 @@ def generateBucketChartForFile(figureName, dataframe, y_max, x_min, x_max):
         else:
             colorAlreadyUsedInLegend[fColor] = True;
 
-        r = p.quad(left=0, right=1, bottom=0, top=1, color=fColor);
-
-        lItem = LegendItem(label = func,
-                           renderers = [r]);
-        legendItems.append(lItem);
-
-        # Cap the number of items in a legend, so it can
-        # fit horizontally.
-        if (len(legendItems) == MAX_ITEMS_PER_LEGEND):
-            numLegends = addLegend(p, legendItems, numLegends);
-
-    # Add whatever legend items did not get added
-    if (len(legendItems) > 0):
-        numLegends = addLegend(p, legendItems, numLegends);
+        legendItems[func] = fColor;
 
     # Plot height is the function of the maximum call stack and the number of
     # legends
-    p.plot_height =  (numLegends * pixelsPerLegend) \
-                     + max((y_max+1) * pixelsPerStackLevel, 100) \
-                     + pixelsForTitle;
+    p.plot_height =  max((y_max+1) * pixelsPerStackLevel, 100) + pixelsForTitle;
 
-    return p;
+    return p, legendItems;
 
 def generateEmptyDataset():
 
@@ -463,26 +544,6 @@ def generateEmptyDataset():
 
     return pd.DataFrame(data=dict);
 
-# When we have no data for a trace interva we generate an empty file
-# for that interval.
-#
-def createNoDataFile(filename):
-
-    try:
-        f = open(filename, "w");
-    except:
-        print(color.RED + color.BOLD),
-        exc_type, exc_value, exc_traceback = sys.exc_info()
-        traceback.print_exception(exc_type, exc_value, exc_traceback);
-        print("Could not open file " + filename + " for writing.");
-        print(color.END);
-        return;
-
-    f.write("<body>\n");
-    f.write("<p style=\"text-align:center;\">");
-    f.write("No data was generated for this trace interval.</p>\n");
-    f.write("</body>\n");
-    f.close()
 #
 # Here we generate plots that span all the input files. Each plot shows
 # the timelines for all files, stacked vertically. The timeline shows
@@ -493,26 +554,33 @@ def createNoDataFile(filename):
 # across the timelines for all files. We call it a bucket, because it
 # corresponds to a bucket in the outlier histogram.
 #
-def generateCrossFilePlotsForBucket(i, lowerBound, upperBound):
+def generateCrossFilePlotsForBucket(i, lowerBound, upperBound, navigatorDF):
 
     global bucketDir;
     global colorAlreadyUsedInLegend;
 
+    aggregateLegendDict = {};
     figuresForAllFiles = [];
     fileName = bucketDir + "/bucket-" + str(i) + ".html";
 
     reset_output();
 
+    intervalTitle = "Interval #" + str(i) + ". {:,}".format(lowerBound) + \
+                    " to " + "{:,}".format(upperBound) + \
+                    " CPU cycles.";
+
+    # Generate a navigator chart, which shows where we are in the
+    # trace and allows moving around the trace.
+    #
+    navigatorFigure = generateNavigatorFigure(navigatorDF, i, intervalTitle);
+    figuresForAllFiles.append(navigatorFigure);
+
     # The following dictionary keeps track of legends. We need
     # a legend for each new HTML file. So we reset the dictionary
     # before generating a new file.
     #
     colorAlreadyUsedInLegend = {};
 
-    intervalTitle = "Interval " + "{:,}".format(lowerBound) + \
-                    " to " + "{:,}".format(upperBound) + \
-                    " CPU cycles";
-
     # Select from the dataframe for this file the records whose 'start'
     # and 'end' timestamps fall within the lower and upper bound.
     #
@@ -560,159 +628,154 @@ def generateCrossFilePlotsForBucket(i, lowerBound, upperBound):
         bucketDF.loc[mask, 'start'] = lowerBound;
 
         largestStackDepth = bucketDF['stackdepthNext'].max();
-        figureTitle = fname + ": " + intervalTitle;
-
-        figure = generateBucketChartForFile(figureTitle, bucketDF,
-                                            largestStackDepth,
-                                            lowerBound, upperBound);
+        figureTitle = fname;
 
+        figure, legendDict = generateBucketChartForFile(figureTitle, bucketDF,
+                                                        largestStackDepth,
+                                                        lowerBound, upperBound);
+        aggregateLegendDict.update(legendDict);
         figuresForAllFiles.append(figure);
 
-    if (len(figuresForAllFiles) > 0):
-        savedFileName = save(column(figuresForAllFiles),
-                             filename = fileName, title=intervalTitle,
-                             resources=CDN);
-    else:
-        createNoDataFile(fileName);
+    # Create the legend for this file and insert it after the navigator figure
+    if (len(aggregateLegendDict) > 0):
+        legendFigure = createLegendFigure(aggregateLegendDict);
+        figuresForAllFiles.insert(1, legendFigure);
+
+    save(column(figuresForAllFiles), filename = fileName,
+         title=intervalTitle, resources=CDN);
 
     return fileName;
 
-# Generate plots of time series slices across all files for each bucket
-# in the outlier histogram. Save each cross-file slice to an HTML file.
+# Generate a plot that shows a view of the entire timeline in a form of
+# intervals. By clicking on an interval we can navigate to that interval.
 #
-def generateTSSlicesForBuckets():
+def generateNavigatorFigure(dataframe, i, title):
 
-    global firstTimeStamp;
-    global lastTimeStamp;
+    global pixelsForTitle;
+    global pixelsPerHeightUnit;
     global plotWidth;
-    global pixelsPerWidthUnit;
 
-    bucketFilenames = [];
+    # Generate the colors, such that the current interval is shown in a
+    # different color than the rest.
+    #
+    numIntervals = dataframe['intervalnumber'].size;
+    color = ["white" for x in range(numIntervals)];
+    color[i] = "salmon";
+    dataframe['color'] = color;
 
-    numBuckets = plotWidth / pixelsPerWidthUnit;
-    timeUnitsPerBucket = (lastTimeStamp - firstTimeStamp) / numBuckets;
+    cds = ColumnDataSource(dataframe);
 
-    for i in range(numBuckets):
-        lowerBound = i * timeUnitsPerBucket;
-        upperBound = (i+1) * timeUnitsPerBucket;
+    title = title + " CLICK TO NAVIGATE";
 
-        fileName = generateCrossFilePlotsForBucket(i, lowerBound,
-                                                       upperBound);
+    hover = HoverTool(tooltips = [
+        ("interval #", "@intervalnumber"),
+        ("interval start", "@intervalbegin{0,0}"),
+        ("interval end", "@intervalend{0,0}")]);
 
-        percentComplete = float(i) / float(numBuckets) * 100;
-        print(color.BLUE + color.BOLD + " Generating timeline charts... "),
-        sys.stdout.write("%d%% complete  \r" % (percentComplete) );
-        sys.stdout.flush();
-        bucketFilenames.append(fileName);
+    TOOLS = [hover, "tap"];
 
-    print(color.END);
+    p = figure(title = title, plot_width = plotWidth,
+               x_range = (0, numIntervals),
+               plot_height =  2 * pixelsPerHeightUnit + pixelsForTitle,
+               x_axis_label = "",
+               y_axis_label = "", tools = TOOLS,
+               toolbar_location="above");
 
-    return bucketFilenames;
+    # No minor ticks or labels on the y-axis
+    p.yaxis.major_tick_line_color = None;
+    p.yaxis.minor_tick_line_color = None;
+    p.yaxis.major_label_text_font_size = '0pt';
+    p.yaxis.ticker = FixedTicker(ticks = range(0, 1));
+    p.ygrid.ticker = FixedTicker(ticks = range(0, 1));
 
-# Here we are making a line that will be inserted into an HTML file for
-# a given bucket (execution slice). This line will have links to the
-# previous slice and to the next slice, so we can navigate between slices
-# by clicking those links.
-#
-def makeLineWithLinks(previous, next):
+    p.xaxis.formatter = NumeralTickFormatter(format="0,");
 
-    global arrowLeftImg;
-    global arrowRightImg;
+    p.title.align = "center";
+    p.title.text_font_style = "normal";
 
-    previousLink = "";
-    nextLink = "";
+    p.quad(left = 'intervalnumber', right = 'intervalnumbernext',
+           bottom = 0, top = 2, color = 'color', source = cds,
+           nonselection_fill_color='color',
+           nonselection_fill_alpha = 1.0,
+           line_color = "aliceblue",
+           selection_fill_color = "white",
+           selection_line_color="lightgrey"
+    );
 
-    # Strip the directory component out of the file name.
-    #
-    if previous is not None:
-        words = previous.split("/");
-        previousStripped = words[len(words)-1];
-        previousLink =  "<a href=\"" + previousStripped + "\">" + \
-                        "<img src=\"" + arrowLeftImg + \
-                        "\" height=\"30\" style=\"float:left\"></a><p>&nbsp;";
+    url = "@bucketfiles";
+    taptool = p.select(type=TapTool);
+    taptool.callback = OpenURL(url=url);
 
+    return p;
 
-    if next is not None:
-        words = next.split("/");
-        nextStripped = words[len(words)-1];
-        nextLink = "<a href=\"" + nextStripped + "\">" + \
-                   "<img src=\"" + arrowRightImg + \
-                   "\" height=\"30\" style=\"float:right\"></a><p>&nbsp;";
 
-    line = previousLink + " " + nextLink + "\n";
-    return line;
+# Create a dataframe describing all time intervals, which will later be used
+# to generate a plot allowing us to navigate along the execution by clicking
+# on different intervals.
+#
+def createIntervalNavigatorDF(numBuckets, timeUnitsPerBucket):
 
+    global bucketDir;
 
-# Into the current file insert links to the previous one and to the next one.
-# The rewritten file is saved under a new file name.
-#
-def linkFiles(current, previous, next):
+    bucketFiles = [];
+    bucketID = [];
+    intervalBegin = [];
+    intervalEnd = [];
 
-    curFile = None;
-    newFile = None;
-    newFileName = current + ".new";
+    for i in range(numBuckets):
 
-    try:
-        curFile = open(current, "r");
-    except:
-        print(color.RED + color.BOLD),
-        exc_type, exc_value, exc_traceback = sys.exc_info()
-        traceback.print_exception(exc_type, exc_value, exc_traceback);
-        print("Could not open file " + current + " for reading.");
-        print(color.END);
-        return None;
+        lBound = i * timeUnitsPerBucket;
+        uBound = (i+1) * timeUnitsPerBucket;
+        fileName = "bucket-" + str(i) + ".html";
 
-    try:
-        newFile = open(newFileName, "w");
-    except:
-        print(color.RED + color.BOLD),
-        exc_type, exc_value, exc_traceback = sys.exc_info()
-        traceback.print_exception(exc_type, exc_value, exc_traceback);
-        print("Could not open file " + newFileName + " for writing.");
-        print(color.END);
-        return None;
+        bucketID.append(i);
+        intervalBegin.append(lBound);
+        intervalEnd.append(uBound);
+        bucketFiles.append(fileName);
 
-    curFileLines = curFile.readlines();
+    data = {};
+    data['bucketfiles'] = bucketFiles;
+    data['intervalbegin'] =  intervalBegin;
+    data['intervalend'] =  intervalEnd;
+    data['intervalnumber'] = bucketID;
 
-    for i in range(len(curFileLines)):
-        line = curFileLines[i];
+    dataframe = pd.DataFrame(data=data);
+    dataframe['intervalnumbernext'] = dataframe['intervalnumber'] + 1;
+    return dataframe;
 
-        insertedLine = makeLineWithLinks(previous, next);
+# Generate plots of time series slices across all files for each bucket
+# in the outlier histogram. Save each cross-file slice to an HTML file.
+#
+def generateTSSlicesForBuckets():
 
-        if "<body>" in line:
-            curFileLines.insert(i+1, insertedLine);
-        elif "</body>" in line:
-            curFileLines.insert(i, insertedLine);
+    global firstTimeStamp;
+    global lastTimeStamp;
+    global plotWidth;
+    global pixelsPerWidthUnit;
 
-    for line in curFileLines:
-        newFile.write(line);
+    bucketFilenames = [];
 
-    curFile.close();
-    newFile.close();
+    numBuckets = plotWidth / pixelsPerWidthUnit;
+    timeUnitsPerBucket = (lastTimeStamp - firstTimeStamp) / numBuckets;
 
-    os.rename(newFileName, current);
+    navigatorDF = createIntervalNavigatorDF(numBuckets, timeUnitsPerBucket);
 
-# We have a list of bucket files. Each one is an HTML file showing a slice of
-# the execution. To be able to easily navigate between consecutive execution
-# slices we insert links into each slice-file that take us to the previous
-# slice and to the next slice.
-#
-def interlinkFiles(fnameList):
+    for i in range(numBuckets):
+        lowerBound = i * timeUnitsPerBucket;
+        upperBound = (i+1) * timeUnitsPerBucket;
 
-    for i in range(len(fnameList)):
-        current = fnameList[i];
+        fileName = generateCrossFilePlotsForBucket(i, lowerBound, upperBound,
+                                                   navigatorDF);
 
-        if i > 0:
-            previous = fnameList[i-1];
-        else:
-            previous = None;
+        percentComplete = float(i) / float(numBuckets) * 100;
+        print(color.BLUE + color.BOLD + " Generating timeline charts... "),
+        sys.stdout.write("%d%% complete  \r" % (percentComplete) );
+        sys.stdout.flush();
+        bucketFilenames.append(fileName);
 
-        if (i < len(fnameList)-1):
-            next = fnameList[i+1];
-        else:
-            next = None;
+    print(color.END);
 
-        linkFiles(current, previous, next);
+    return bucketFilenames;
 
 def processFile(fname):
 
@@ -1011,13 +1074,6 @@ def main():
     if not os.path.exists(bucketDir):
         os.makedirs(bucketDir);
 
-    # Copy the image files that we will need later into bucketDir
-    scriptLocation = os.path.dirname(os.path.realpath(__file__));
-    os.system("cp " + scriptLocation + "/" + arrowLeftImg + " " + bucketDir +
-              "/" + arrowLeftImg);
-    os.system("cp " + scriptLocation + "/" + arrowRightImg + " " + bucketDir +
-              "/" + arrowRightImg);
-
     # Parallelize this later, so we are working on files in parallel.
     for fname in args.files:
         processFile(fname);
@@ -1030,12 +1086,6 @@ def main():
     #
     fileNameList = generateTSSlicesForBuckets();
 
-    # Rewrite the files, so that they have links to one another. This way
-    # you can navigate from one slice to the next by clicking the link inside
-    # the file.
-    #
-    interlinkFiles(fileNameList);
-
     totalFuncs = len(perFuncDF.keys());
     i = 0;
     # Generate a histogram of outlier durations
@@ -1058,6 +1108,3 @@ def main():
 
 if __name__ == '__main__':
     main()
-
-
-