+struct shared_extent {
+ struct rb_node rb;
+ u64 start; /* Start of interval */
+ u64 last; /* Last location _in_ interval */
+ u64 __subtree_last;
+};
+
+/*
+ * extent_tree_* functions are defined in the massive interval tree
+ * macro below. This serves to illustrate the api in human-readable
+ * terms.
+ */
+static void
+extent_tree_insert(struct shared_extent *node, struct rb_root *root);
+
+static void
+extent_tree_remove(struct shared_extent *node, struct rb_root *root);
+
+static struct shared_extent *
+extent_tree_iter_first(struct rb_root *root,
+ u64 start, u64 last);
+
+static struct shared_extent *
+extent_tree_iter_next(struct shared_extent *node,
+ u64 start, u64 last);
+
+#define START(node) ((node)->start)
+#define LAST(node) ((node)->last)
+
+INTERVAL_TREE_DEFINE(struct shared_extent, rb,
+ u64, __subtree_last,
+ START, LAST, static, extent_tree)
+
+static int add_shared_extent(u64 start, u64 len, struct rb_root *root)
+{
+ struct shared_extent *sh;
+
+ BUG_ON(len == 0);
+
+ sh = calloc(1, sizeof(*sh));
+ if (!sh)
+ return -ENOMEM;
+
+ sh->start = start;
+ sh->last = (start + len - 1);
+
+ extent_tree_insert(sh, root);
+
+ return 0;
+}
+
+static void cleanup_shared_extents(struct rb_root *root)
+{
+ struct shared_extent *s;
+ struct shared_extent *tmp;
+
+ if (!root)
+ return;
+
+ s = extent_tree_iter_first(root, 0, -1ULL);
+ while (s) {
+ tmp = extent_tree_iter_next(s, 0, -1ULL);
+ extent_tree_remove(s, root);
+
+ free(s);
+ s = tmp;
+ }
+}
+
+#define dprintf(...)
+
+/*
+ * Find all extents which overlap 'n', calculate the space
+ * covered by them and remove those nodes from the tree.
+ */
+static u64 count_unique_bytes(struct rb_root *root, struct shared_extent *n)
+{
+ struct shared_extent *tmp;
+ u64 wstart = n->start;
+ u64 wlast = n->last;
+
+ dprintf("Count overlaps:");
+
+ do {
+ /*
+ * Expand our search window based on the lastest
+ * overlapping extent. Doing this will allow us to
+ * find all possible overlaps
+ */
+ if (wstart > n->start)
+ wstart = n->start;
+ if (wlast < n->last)
+ wlast = n->last;
+
+ dprintf(" (%llu, %llu)", n->start, n->last);
+
+ tmp = n;
+ n = extent_tree_iter_next(n, wstart, wlast);
+
+ extent_tree_remove(tmp, root);
+ free(tmp);
+ } while (n);
+
+ dprintf("; wstart: %llu wlast: %llu total: %llu\n", wstart,
+ wlast, wlast - wstart + 1);
+
+ return wlast - wstart + 1;
+}
+
+/*
+ * What we want to do here is get a count of shared bytes within the
+ * set of extents we have collected. Specifically, we don't want to
+ * count any byte more than once, so just adding them up doesn't
+ * work.
+ *
+ * For each set of overlapping extents we find the lowest start and
+ * highest end. From there we have the actual number of bytes which is
+ * shared across all of the extents in our set. A sum of each sets
+ * extent length is returned.
+ */
+static void count_shared_bytes(struct rb_root *root, u64 *ret_cnt)
+{
+ u64 count = 0;
+ struct shared_extent *s = extent_tree_iter_first(root,
+ 0, -1ULL);
+
+ if (!s)
+ goto out;
+
+ while (s) {
+ /*
+ * Find all extents which overlap 's', calculate the space
+ * covered by them and remove those nodes from the tree.
+ */
+ count += count_unique_bytes(root, s);
+
+ /*
+ * Since count_unique_bytes will be emptying the tree,
+ * we can grab the first node here
+ */
+ s = extent_tree_iter_first(root, 0, -1ULL);
+ }
+
+ BUG_ON(!RB_EMPTY_ROOT(root));
+out:
+ *ret_cnt = count;
+}
+