Add debug-tree -e to print all allocated extents, and show-blocks to graph them

2 files changed, 423 insertions, 16 deletions

diff --git a/debug-tree.c b/debug-tree.c
index 368b8fb3..7a2d0d06 100644
--- a/debug-tree.c
+++ b/debug-tree.c
@@ -18,6 +18,7 @@
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <unistd.h>
 #include <uuid/uuid.h>
 #include "kerncompat.h"
 #include "radix-tree.h"
@@ -26,7 +27,79 @@
 #include "print-tree.h"
 #include "transaction.h"
 
-int main(int ac, char **av) {
+static int print_usage(void)
+{
+	fprintf(stderr, "usage: debug-tree [ -e ] device\n");
+	exit(1);
+}
+
+static void print_extent_leaf(struct btrfs_root *root, struct extent_buffer *l)
+{
+	int i;
+	struct btrfs_item *item;
+	struct btrfs_extent_ref *ref;
+	struct btrfs_key key;
+	static u64 last = 0;
+	static u64 last_len = 0;
+	u32 nr = btrfs_header_nritems(l);
+	u32 type;
+
+	for (i = 0 ; i < nr ; i++) {
+		item = btrfs_item_nr(l, i);
+		btrfs_item_key_to_cpu(l, &key, i);
+		type = btrfs_key_type(&key);
+		switch (type) {
+		case BTRFS_EXTENT_ITEM_KEY:
+			last_len = key.offset;
+			last = key.objectid;
+			break;
+		case BTRFS_EXTENT_REF_KEY:
+			ref = btrfs_item_ptr(l, i, struct btrfs_extent_ref);
+			printf("%llu %llu extent back ref root %llu gen %llu "
+			       "owner %llu offset %llu\n",
+			       (unsigned long long)last,
+			       (unsigned long long)last_len,
+			       (unsigned long long)btrfs_ref_root(l, ref),
+			       (unsigned long long)btrfs_ref_generation(l, ref),
+			       (unsigned long long)btrfs_ref_objectid(l, ref),
+			       (unsigned long long)btrfs_ref_offset(l, ref));
+			break;
+		};
+		fflush(stdout);
+	}
+}
+
+static void print_extents(struct btrfs_root *root, struct extent_buffer *eb)
+{
+	int i;
+	u32 nr;
+	u32 size;
+
+	if (!eb)
+		return;
+	if (btrfs_is_leaf(eb)) {
+		print_extent_leaf(root, eb);
+		return;
+	}
+	size = btrfs_level_size(root, btrfs_header_level(eb) - 1);
+	nr = btrfs_header_nritems(eb);
+	for (i = 0; i < nr; i++) {
+		struct extent_buffer *next = read_tree_block(root,
+					     btrfs_node_blockptr(eb, i),
+					     size);
+		if (btrfs_is_leaf(next) &&
+		    btrfs_header_level(eb) != 1)
+			BUG();
+		if (btrfs_header_level(next) !=
+			btrfs_header_level(eb) - 1)
+			BUG();
+		print_extents(root, next);
+		free_extent_buffer(next);
+	}
+}
+
+int main(int ac, char **av)
+{
 	struct btrfs_root *root;
 	struct btrfs_path path;
 	struct btrfs_key key;
@@ -36,20 +109,37 @@ int main(int ac, char **av) {
 	char uuidbuf[37];
 	int ret;
 	int slot;
+	int extent_only = 0;
 
-	if (ac != 2) {
-		fprintf(stderr, "usage: %s device\n", av[0]);
-		exit(1);
-	}
 	radix_tree_init();
-	root = open_ctree(av[1], 0);
+
+	while(1) {
+		int c;
+		c = getopt(ac, av, "e");
+		if (c < 0)
+			break;
+		switch(c) {
+			case 'e':
+				extent_only = 1;
+				break;
+			default:
+				print_usage();
+		}
+	}
+	ac = ac - optind;
+	if (ac != 1)
+		print_usage();
+
+	root = open_ctree(av[optind], 0);
 	if (!root) {
-		fprintf(stderr, "unable to open %s\n", av[1]);
+		fprintf(stderr, "unable to open %s\n", av[optind]);
 		exit(1);
 	}
-	printf("root tree\n");
-	btrfs_print_tree(root->fs_info->tree_root,
-			 root->fs_info->tree_root->node);
+	if (!extent_only) {
+		printf("root tree\n");
+		btrfs_print_tree(root->fs_info->tree_root,
+				 root->fs_info->tree_root->node);
+	}
 	btrfs_init_path(&path);
 	key.offset = 0;
 	key.objectid = 0;
@@ -71,6 +161,8 @@ int main(int ac, char **av) {
 		if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
 			unsigned long offset;
 			struct extent_buffer *buf;
+			int skip = extent_only;
+
 			offset = btrfs_item_ptr_offset(leaf, slot);
 			read_extent_buffer(leaf, &ri, offset, sizeof(ri));
 			buf = read_tree_block(root->fs_info->tree_root,
@@ -81,18 +173,27 @@ int main(int ac, char **av) {
 				printf("root ");
 				break;
 			case BTRFS_EXTENT_TREE_OBJECTID:
-				printf("extent tree ");
+				skip = 0;
+				if (!extent_only)
+					printf("extent tree ");
 				break;
 			}
-			printf("tree %llu %u %llu\n",
-			       (unsigned long long)found_key.objectid,
-			       found_key.type,
-			       (unsigned long long)found_key.offset);
-			btrfs_print_tree(root, buf);
+			if (!skip && !extent_only) {
+				printf("tree %llu %u %llu\n",
+				       (unsigned long long)found_key.objectid,
+				       found_key.type,
+				       (unsigned long long)found_key.offset);
+				btrfs_print_tree(root, buf);
+			} else if (extent_only && !skip) {
+				print_extents(root, buf);
+			}
 		}
 		path.slots[0]++;
 	}
 	btrfs_release_path(root, &path);
+	if (extent_only)
+		return 0;
+
 	printf("total bytes %llu\n",
 	       (unsigned long long)btrfs_super_total_bytes(&root->fs_info->super_copy));
 	printf("bytes used %llu\n",
diff --git a/show-blocks b/show-blocks
new file mode 100755
index 00000000..8db4c0b1
--- /dev/null
+++ b/show-blocks
@@ -0,0 +1,306 @@
+#!/usr/bin/env python
+#
+# Copyright (C) 2007 Oracle.  All rights reserved.
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public
+# License v2 as published by the Free Software Foundation.
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public
+# License along with this program; if not, write to the
+# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 021110-1307, USA.
+#
+import sys, os, signal, time, commands, tempfile
+from optparse import OptionParser
+from matplotlib import rcParams
+from matplotlib.font_manager import fontManager, FontProperties
+import numpy
+
+rcParams['numerix'] = 'numpy'
+rcParams['backend'] = 'Agg'
+rcParams['interactive'] = 'False'
+from pylab import *
+
+class AnnoteFinder:
+  """
+  callback for matplotlib to display an annotation when points are clicked on.  The
+  point which is closest to the click and within xtol and ytol is identified.
+    
+  Register this function like this:
+    
+  scatter(xdata, ydata)
+  af = AnnoteFinder(xdata, ydata, annotes)
+  connect('button_press_event', af)
+  """
+
+  def __init__(self, axis=None):
+    if axis is None:
+      self.axis = gca()
+    else:
+      self.axis= axis
+    self.drawnAnnotations = {}
+    self.links = []
+    
+  def clear(self):
+    for k in self.drawnAnnotations.keys():
+        self.drawnAnnotations[k].set_visible(False)
+
+  def __call__(self, event):
+    if event.inaxes:
+      if event.button != 1:
+        self.clear()
+        draw()
+        return
+      clickX = event.xdata
+      clickY = event.ydata
+      if (self.axis is None) or (self.axis==event.inaxes):
+        self.drawAnnote(event.inaxes, clickX, clickY)
+    
+  def drawAnnote(self, axis, x, y):
+    """
+    Draw the annotation on the plot
+    """
+    if self.drawnAnnotations.has_key((x,y)):
+      markers = self.drawnAnnotations[(x,y)]
+      markers.set_visible(not markers.get_visible())
+      draw()
+    else:
+      t = axis.text(x,y, "(%3.2f, %3.2f)"%(x,y), bbox=dict(facecolor='red',
+                    alpha=0.8))
+      self.drawnAnnotations[(x,y)] = t
+      draw()
+
+def loaddata(fh,delimiter=None, converters=None):
+
+    def iter(fh, delimiter, converters):
+        global total_data
+        global total_metadata
+        for i,line in enumerate(fh):
+            line = line.split(' ')
+            start = float(line[0])
+            len = float(line[1])
+            owner = float(line[10])
+            if owner <= 255:
+                total_metadata += int(len)
+            else:
+                total_data += int(len)
+            if start < zoommin or (zoommax != 0 and start > zoommax):
+                continue
+            yield start
+            yield len
+            yield owner
+    X = numpy.fromiter(iter(fh, delimiter, converters), dtype=float)
+    return X
+
+def run_debug_tree(device):
+    p = os.popen('debug-tree -e ' + device)
+    data = loaddata(p)
+    return data
+
+def shapeit(X):
+    lines = len(X) / 3
+    X.shape = (lines, 3)
+
+def line_picker(line, mouseevent):
+    if mouseevent.xdata is None: return False, dict()
+    print "%d %d\n", mouseevent.xdata, mouseevent.ydata
+    return False, dict()
+
+def xycalc(byte):
+    byte = byte / bytes_per_cell
+    yval = floor(byte / num_cells)
+    xval = byte % num_cells
+    return (xval, yval + 1)
+
+def plotone(a, xvals, yvals, owner):
+    global data_lines
+    global meta_lines
+
+    if owner:
+        if options.meta_only:
+            return
+        color = "blue"
+        label = "Data"
+    else:
+        if options.data_only:
+            return
+        color = "green"
+        label = "Metadata"
+
+    lines = a.plot(xvals, yvals, 's', color=color, mfc=color, mec=color,
+           markersize=.23, label=label)
+    if owner and not data_lines:
+        data_lines = lines
+    elif not owner and not meta_lines:
+        meta_lines = lines
+
+
+def parse_zoom():
+    def parse_num(s):
+        mult = 1
+        c = s.lower()[-1]
+        if c == 't':
+            mult = 1024 * 1024 * 1024 * 1024
+        elif c == 'g':
+            mult = 1024 * 1024 * 1024
+        elif c == 'm':
+            mult = 1024 * 1024
+        elif c == 'k':
+            mult = 1024
+        else:
+            c = None
+        if c:
+            num = int(s[:-1]) * mult
+        else:
+            num = int(s)
+        return num
+        
+    if not options.zoom:
+        return (0, 0)
+
+    vals = options.zoom.split(':')
+    if len(vals) != 2:
+        sys.stderr.write("warning: unable to parse zoom %s\n" % options.zoom)
+        return (0, 0)
+    zoommin = parse_num(vals[0])
+    zoommax = parse_num(vals[1])
+    return (zoommin, zoommax)
+
+usage = "usage: %prog [options]"
+parser = OptionParser(usage=usage)
+parser.add_option("-d", "--device", help="Btrfs device", default="")
+parser.add_option("-i", "--input-file", help="debug-tree data", default="")
+parser.add_option("-o", "--output", help="Output file", default="blocks.png")
+parser.add_option("-z", "--zoom", help="Zoom", default=None)
+parser.add_option("", "--data-only", help="Only print data blocks",
+                  default=False, action="store_true")
+parser.add_option("", "--meta-only", help="Only print metadata blocks",
+                  default=False, action="store_true")
+
+(options,args) = parser.parse_args()
+
+if not options.device and not options.input_file:
+    parser.print_help()
+    sys.exit(1)
+
+zoommin, zoommax = parse_zoom()
+total_data = 0
+total_metadata = 0
+data_lines = []
+meta_lines = []
+
+if options.device:
+    data = run_debug_tree(options.device)
+elif options.input_file:
+    data = loaddata(file(options.input_file))
+shapeit(data)
+
+# try to drop out the least common data points by creating
+# a historgram of the sectors seen.
+sectors = data[:,0]
+sizes = data[:,1]
+datalen = len(data)
+sectormax = numpy.max(sectors)
+sectormin = 0
+num_cells = 800
+total_cells = num_cells * num_cells
+byte_range = sectormax - sectormin
+bytes_per_cell = byte_range / total_cells
+
+f = figure(figsize=(8,6))
+
+# Throughput goes at the botoom
+a = subplot(1, 1, 1)
+datai = 0
+xvals = []
+yvals = []
+last = 0
+while datai < datalen:
+    row = data[datai]
+    datai += 1
+    byte = row[0]
+    size = row[1]
+    owner = row[2]
+
+    if owner <= 255:
+        owner = 0
+    else:
+        owner = 1
+
+    if len(xvals) and owner != last:
+        plotone(a, xvals, yvals, last)
+        xvals = []
+        yvals = []
+    cell = 0
+    while cell < size:
+        xy = xycalc(byte)
+        byte += bytes_per_cell
+        cell += bytes_per_cell
+        if xy:
+            xvals.append(xy[0])
+            yvals.append(xy[1])
+    last = owner
+
+if xvals:
+    plotone(a, xvals, yvals, last)
+
+# make sure the final second goes on the x axes
+ticks = []
+a.set_xticks(ticks)
+ticks = a.get_yticks()
+
+first_tick = ticks[1] * bytes_per_cell * num_cells
+if first_tick > 1024 * 1024 * 1024 * 1024:
+    scale = 1024 * 1024 * 1024 * 1024;
+    scalestr = "TB"
+elif first_tick > 1024 * 1024 * 1024:
+    scale = 1024 * 1024 * 1024;
+    scalestr = "GB"
+elif first_tick > 1024 * 1024:
+    scale = 1024 * 1024;
+    scalestr = "MB"
+elif first_tick > 1024:
+    scale = 1024;
+    scalestr = "KB"
+else:
+    scalestr = "Bytes"
+    scale = 1
+
+ylabels = [ str(int((x * bytes_per_cell * num_cells) / scale)) for x in ticks ]
+a.set_yticklabels(ylabels)
+a.set_ylabel('Disk offset (%s)' % scalestr)
+a.set_xlim(0, num_cells)
+a.set_title('Blocks')
+
+lines = []
+labels = []
+if data_lines:
+    lines += data_lines
+    labels += ["Data"]
+if meta_lines:
+    lines += meta_lines
+    labels += ["Metadata"]
+
+a.legend(lines, labels, loc=(.9, 1.02), shadow=True, pad=0.5, numpoints=1,
+              handletextsep = 0.005,
+              labelsep = 0.01,
+              markerscale=10,
+              prop=FontProperties(size='x-small') )
+
+if total_data == 0:
+    percent_meta = 100
+else:
+    percent_meta = (float(total_metadata) / float(total_data)) * 100
+
+print "Total metadata bytes %d data %d ratio %.3f" % (total_metadata,
+                                                    total_data, percent_meta)
+print "saving graph to %s" % options.output
+savefig(options.output, orientation='landscape')
+show()
+