results-tree.c 7.56 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
/*
 * results-tree.c
 *
 * Copyright (C) 2013 SUSE.  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 version 2 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.
Mark Fasheh's avatar
Mark Fasheh committed
14 15
 *
 * Authors: Mark Fasheh <mfasheh@suse.de>
16 17
 */

18 19 20 21 22 23 24 25 26 27 28 29
#include <stdlib.h>
#include <errno.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>

#include "kernel.h"
#include "rbtree.h"
#include "list.h"

#include "csum.h"	/* for digest_len variable and DIGEST_LEN_MAX */

30
#include "filerec.h"
31 32
#include "results-tree.h"

33
#include "debug.h"
34
#include "memstats.h"
35

36 37
declare_alloc_tracking(dupe_extents);
declare_alloc_tracking(extent);
38

39
static struct extent *alloc_extent(struct filerec *file, uint64_t loff)
40
{
41
	struct extent *e = calloc_extent(1);
42 43

	if (e) {
44 45
		INIT_LIST_HEAD(&e->e_list);
		INIT_LIST_HEAD(&e->e_file_extents);
46
		rb_init_node(&e->e_node);
47
		e->e_file = file;
48 49 50 51 52
		e->e_loff = loff;
	}
	return e;
}

53 54 55 56 57 58 59 60 61 62 63 64 65 66
static int extents_rb_cmp(struct extent *e1, struct extent *e2)
{
	if (e1->e_file > e2->e_file)
		return -1;
	if (e1->e_file < e2->e_file)
		return 1;
	if (e1->e_loff > e2->e_loff)
		return -1;
	if (e1->e_loff < e2->e_loff)
		return 1;
	return 0;
}

static int insert_extent_rb(struct dupe_extents *dext, struct extent *e)
67
{
68
	int res;
69
	struct extent *tmp;
70 71 72 73 74
	struct rb_node **p = &dext->de_extents_root.rb_node;
	struct rb_node *parent = NULL;

	while (*p) {
		parent = *p;
75

76 77 78 79 80 81 82
		tmp = rb_entry(parent, struct extent, e_node);
		res = extents_rb_cmp(tmp, e);
		if (res < 0) {
			p = &(*p)->rb_left;
		} else if (res > 0) {
			p = &(*p)->rb_right;
		} else {
83
			return 1;
84
		}
85 86
	}

87 88 89 90
	rb_link_node(&e->e_node, parent, p);
	rb_insert_color(&e->e_node, &dext->de_extents_root);
	return 0;
}
91

92 93 94 95 96 97 98 99 100
static int insert_extent_list(struct dupe_extents *dext, struct extent *e)
{
	/* We keep this tree free of duplicates  */
	if (insert_extent_rb(dext, e) == 0) {
		e->e_parent = dext;
		dext->de_num_dupes++;
		list_add_tail(&e->e_list, &dext->de_extents);
		return 0;
	}
101

102
	return 1;
103 104 105
}

static void insert_dupe_extents(struct results_tree *res,
106
				struct dupe_extents *dext)
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
{
	struct rb_node **p = &res->root.rb_node;
	struct rb_node *parent = NULL;
	struct dupe_extents *tmp;
	int cmp; 

	while (*p) {
		parent = *p;

		tmp = rb_entry(parent, struct dupe_extents, de_node);
		if (dext->de_len < tmp->de_len)
			p = &(*p)->rb_left;
		else if (dext->de_len > tmp->de_len)
			p = &(*p)->rb_right;
		else {
			cmp = memcmp(dext->de_hash, tmp->de_hash, digest_len);
			if (cmp < 0)
				p = &(*p)->rb_left;
			else if (cmp > 0)
				p = &(*p)->rb_right;
			else
128
				abort_lineno(); /* We should never find a duplicate */
129 130 131 132 133 134 135 136
		}
	}

	res->num_dupes++;
	rb_link_node(&dext->de_node, parent, p);
	rb_insert_color(&dext->de_node, &res->root);
}

137 138
static struct dupe_extents *find_dupe_extents(struct results_tree *res,
				      unsigned char *digest, uint64_t len)
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
{
	struct rb_node *n = res->root.rb_node;
	struct dupe_extents *dext;
	int cmp;

	while (n) {
		dext = rb_entry(n, struct dupe_extents, de_node);

		/* Compare by length first, then use digest to drill
		 * down to a match */
		if (len < dext->de_len)
			n = n->rb_left;
		else if (len > dext->de_len)
			n = n->rb_right;
		else {
			cmp = memcmp(digest, dext->de_hash, digest_len);
			if (cmp < 0)
				n = n->rb_left;
			else if (cmp > 0)
				n = n->rb_right;
			else
				return dext;
		}

	}
	return NULL;
}

static void insert_extent_list_free(struct dupe_extents *dext,
				    struct extent **e)
{
	if (insert_extent_list(dext, *e)) {
171
		free_extent(*e);
172 173 174 175
		*e = NULL;
	}
}

176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
static struct dupe_extents *dupe_extents_new(struct results_tree *res,
					     unsigned char *digest,
					     uint64_t len)
{
	struct dupe_extents *dext;

	dext = calloc_dupe_extents(1);
	if (!dext)
		return NULL;

	memcpy(dext->de_hash, digest, digest_len);
	dext->de_len = len;
	INIT_LIST_HEAD(&dext->de_extents);
	dext->de_extents_root = RB_ROOT;

	rb_init_node(&dext->de_node);

	insert_dupe_extents(res, dext);

	dext->de_score = len;

	return dext;
}

200
int insert_result(struct results_tree *res, unsigned char *digest,
201 202
		  struct filerec *recs[2], uint64_t startoff[2],
		  uint64_t endoff[2])
203
{
204 205
	struct extent *e0 = alloc_extent(recs[0], startoff[0]);
	struct extent *e1 = alloc_extent(recs[1], startoff[1]);
206 207
	struct dupe_extents *dext;
	uint64_t len = endoff[0] - startoff[0];
208
	int add_score = 1;
209 210 211 212 213 214

	if (!e0 || !e1)
		return ENOMEM;

	dext = find_dupe_extents(res, digest, len);
	if (!dext) {
215
		dext = dupe_extents_new(res, digest, len);
216 217
		if (!dext)
			return ENOMEM;
218
		add_score = 0;
219 220
	}

221
	abort_on(dext->de_len != len);
222 223 224 225

	insert_extent_list_free(dext, &e0);
	insert_extent_list_free(dext, &e1);

226 227 228
	if (e0) {
		if (add_score)
			dext->de_score += len;
229
		list_add_tail(&e0->e_file_extents, &recs[0]->extent_list);
230 231 232 233
	}
	if (e1) {
		if (add_score)
			dext->de_score += len;
234
		list_add_tail(&e1->e_file_extents, &recs[1]->extent_list);
235
	}
236 237 238 239 240 241 242 243 244 245 246 247

	return 0;
}

static uint64_t extent_len(struct extent *extent)
{
	return extent->e_parent->de_len;
}

static void remove_extent(struct results_tree *res, struct extent *extent)
{
	struct dupe_extents *p = extent->e_parent;
248
	struct rb_node *n;
249 250 251 252 253 254 255

again:
	p->de_score -= p->de_len;
	p->de_num_dupes--;

	list_del_init(&extent->e_list);
	list_del_init(&extent->e_file_extents);
256
	rb_erase(&extent->e_node, &p->de_extents_root);
257
	free_extent(extent);
258 259 260 261

	if (p->de_num_dupes == 1) {
		/* It doesn't make sense to have one extent in a dup
		 * list. */
262
		abort_on(RB_EMPTY_ROOT(&p->de_extents_root));/* logic error */
263

264 265
		n = rb_first(&p->de_extents_root);
		extent = rb_entry(n, struct extent, e_node);
266 267 268 269 270
		goto again;
	}

	if (p->de_num_dupes == 0) {
		rb_erase(&p->de_node, &res->root);
271
		free_dupe_extents(p);
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
		res->num_dupes--;
	}
}

static int compare_extent(struct results_tree *res,
			  struct extent *extent,
			  struct list_head *head)
{
	struct extent *pos = extent;
	uint64_t pos_end, extent_end;
	struct list_head *next = extent->e_file_extents.next;

	list_for_each_entry_continue(pos, head, e_file_extents) {
		/* This is a logic error - we shouldn't loop back on
		 * ourselves. */
287 288
		abort_on(pos == extent);

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
//		if (pos->e_loff == extent->e_loff
//		    && extent_len(pos) == extent_len(extent))
//			continue; /* Same extent? Skip. */

		pos_end = pos->e_loff + extent_len(pos) - 1;
		extent_end = extent->e_loff + extent_len(extent) - 1;

		if (pos_end < extent->e_loff ||
		    pos->e_loff > extent_end)
			continue; /* Extents don't overlap */

		if (extent->e_parent->de_score <= pos->e_parent->de_score) {
			/* remove extent */
			remove_extent(res, extent);
		} else {
			/* remove pos */
			if (pos == list_entry(next, struct extent,
					      e_file_extents))
				next = pos->e_file_extents.next;
			remove_extent(res, pos);
		}
		return 1;
	}

	return 0;
}

316
void remove_overlapping_extents(struct results_tree *res, struct filerec *file)
317 318 319 320
{
	struct extent *orig;
	struct list_head *next;

321
	if (list_empty(&file->extent_list))
322 323 324
		return;

restart:
325 326
	next = file->extent_list.next;
	while (next != &file->extent_list) {
327 328 329 330 331 332 333
		orig = list_entry(next, struct extent, e_file_extents);

		/*
		 * Re-start the search if we wound up deleting items -
		 * compare_extent could have deleted up to two items,
		 * either of which could be our loop cursor.
		 */
334
		if (compare_extent(res, orig, &file->extent_list))
335 336 337 338 339 340 341 342 343 344 345
			goto restart;

		next = next->next;
	}
}

void init_results_tree(struct results_tree *res)
{
	res->root = RB_ROOT;
	res->num_dupes = 0;
}