free-space-cache.c 18.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * Copyright (C) 2008 Red Hat.  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.
 */

#include <linux/sched.h>
#include "ctree.h"
21
22
23
24
25
26
27
28
29
#include "free-space-cache.h"
#include "transaction.h"

struct btrfs_free_space {
	struct rb_node bytes_index;
	struct rb_node offset_index;
	u64 offset;
	u64 bytes;
};
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

static int tree_insert_offset(struct rb_root *root, u64 offset,
			      struct rb_node *node)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct btrfs_free_space *info;

	while (*p) {
		parent = *p;
		info = rb_entry(parent, struct btrfs_free_space, offset_index);

		if (offset < info->offset)
			p = &(*p)->rb_left;
		else if (offset > info->offset)
			p = &(*p)->rb_right;
		else
			return -EEXIST;
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);

	return 0;
}

static int tree_insert_bytes(struct rb_root *root, u64 bytes,
			     struct rb_node *node)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct btrfs_free_space *info;

	while (*p) {
		parent = *p;
		info = rb_entry(parent, struct btrfs_free_space, bytes_index);

		if (bytes < info->bytes)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);

	return 0;
}

/*
Josef Bacik's avatar
Josef Bacik committed
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 * searches the tree for the given offset.
 *
 * fuzzy == 1: this is used for allocations where we are given a hint of where
 * to look for free space.  Because the hint may not be completely on an offset
 * mark, or the hint may no longer point to free space we need to fudge our
 * results a bit.  So we look for free space starting at or after offset with at
 * least bytes size.  We prefer to find as close to the given offset as we can.
 * Also if the offset is within a free space range, then we will return the free
 * space that contains the given offset, which means we can return a free space
 * chunk with an offset before the provided offset.
 *
 * fuzzy == 0: this is just a normal tree search.  Give us the free space that
 * starts at the given offset which is at least bytes size, and if its not there
 * return NULL.
94
95
96
 */
static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
						   u64 offset, u64 bytes,
Josef Bacik's avatar
Josef Bacik committed
97
						   int fuzzy)
98
99
100
101
102
103
104
105
{
	struct rb_node *n = root->rb_node;
	struct btrfs_free_space *entry, *ret = NULL;

	while (n) {
		entry = rb_entry(n, struct btrfs_free_space, offset_index);

		if (offset < entry->offset) {
Josef Bacik's avatar
Josef Bacik committed
106
			if (fuzzy &&
107
108
109
110
111
			    (!ret || entry->offset < ret->offset) &&
			    (bytes <= entry->bytes))
				ret = entry;
			n = n->rb_left;
		} else if (offset > entry->offset) {
Josef Bacik's avatar
Josef Bacik committed
112
113
			if (fuzzy &&
			    (entry->offset + entry->bytes - 1) >= offset &&
114
			    bytes <= entry->bytes) {
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
				ret = entry;
				break;
			}
			n = n->rb_right;
		} else {
			if (bytes > entry->bytes) {
				n = n->rb_right;
				continue;
			}
			ret = entry;
			break;
		}
	}

	return ret;
}

/*
 * return a chunk at least bytes size, as close to offset that we can get.
 */
static struct btrfs_free_space *tree_search_bytes(struct rb_root *root,
						  u64 offset, u64 bytes)
{
	struct rb_node *n = root->rb_node;
	struct btrfs_free_space *entry, *ret = NULL;

	while (n) {
		entry = rb_entry(n, struct btrfs_free_space, bytes_index);

		if (bytes < entry->bytes) {
			/*
			 * We prefer to get a hole size as close to the size we
			 * are asking for so we don't take small slivers out of
			 * huge holes, but we also want to get as close to the
			 * offset as possible so we don't have a whole lot of
			 * fragmentation.
			 */
			if (offset <= entry->offset) {
				if (!ret)
					ret = entry;
				else if (entry->bytes < ret->bytes)
					ret = entry;
				else if (entry->offset < ret->offset)
					ret = entry;
			}
			n = n->rb_left;
		} else if (bytes > entry->bytes) {
			n = n->rb_right;
		} else {
			/*
			 * Ok we may have multiple chunks of the wanted size,
			 * so we don't want to take the first one we find, we
			 * want to take the one closest to our given offset, so
			 * keep searching just in case theres a better match.
			 */
			n = n->rb_right;
			if (offset > entry->offset)
				continue;
			else if (!ret || entry->offset < ret->offset)
				ret = entry;
		}
	}

	return ret;
}

static void unlink_free_space(struct btrfs_block_group_cache *block_group,
			      struct btrfs_free_space *info)
{
	rb_erase(&info->offset_index, &block_group->free_space_offset);
	rb_erase(&info->bytes_index, &block_group->free_space_bytes);
}

static int link_free_space(struct btrfs_block_group_cache *block_group,
			   struct btrfs_free_space *info)
{
	int ret = 0;


194
	BUG_ON(!info->bytes);
195
196
197
198
199
200
201
202
203
204
205
206
207
	ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
				 &info->offset_index);
	if (ret)
		return ret;

	ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
				&info->bytes_index);
	if (ret)
		return ret;

	return ret;
}

208
209
int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
			 u64 offset, u64 bytes)
210
211
212
213
214
215
{
	struct btrfs_free_space *right_info;
	struct btrfs_free_space *left_info;
	struct btrfs_free_space *info = NULL;
	int ret = 0;

216
217
218
219
220
221
222
223
224
	info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
	if (!info)
		return -ENOMEM;

	info->offset = offset;
	info->bytes = bytes;

	spin_lock(&block_group->tree_lock);

225
226
227
228
229
230
	/*
	 * first we want to see if there is free space adjacent to the range we
	 * are adding, if there is remove that struct and add a new one to
	 * cover the entire range
	 */
	right_info = tree_search_offset(&block_group->free_space_offset,
Josef Bacik's avatar
Josef Bacik committed
231
					offset+bytes, 0, 0);
232
233
234
	left_info = tree_search_offset(&block_group->free_space_offset,
				       offset-1, 0, 1);

Josef Bacik's avatar
Josef Bacik committed
235
	if (right_info) {
236
		unlink_free_space(block_group, right_info);
237
238
		info->bytes += right_info->bytes;
		kfree(right_info);
239
240
	}

Josef Bacik's avatar
Josef Bacik committed
241
	if (left_info && left_info->offset + left_info->bytes == offset) {
242
		unlink_free_space(block_group, left_info);
243
244
245
		info->offset = left_info->offset;
		info->bytes += left_info->bytes;
		kfree(left_info);
246
247
248
249
250
	}

	ret = link_free_space(block_group, info);
	if (ret)
		kfree(info);
251
252
253

	spin_unlock(&block_group->tree_lock);

254
255
	if (ret) {
		printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
Stoyan Gaydarov's avatar
Stoyan Gaydarov committed
256
		BUG_ON(ret == -EEXIST);
257
258
259
260
261
	}

	return ret;
}

262
263
int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
			    u64 offset, u64 bytes)
264
265
266
267
{
	struct btrfs_free_space *info;
	int ret = 0;

268
269
	spin_lock(&block_group->tree_lock);

270
271
272
273
	info = tree_search_offset(&block_group->free_space_offset, offset, 0,
				  1);
	if (info && info->offset == offset) {
		if (info->bytes < bytes) {
274
275
276
277
278
			printk(KERN_ERR "Found free space at %llu, size %llu,"
			       "trying to use %llu\n",
			       (unsigned long long)info->offset,
			       (unsigned long long)info->bytes,
			       (unsigned long long)bytes);
279
280
			WARN_ON(1);
			ret = -EINVAL;
281
			spin_unlock(&block_group->tree_lock);
282
283
284
285
286
287
			goto out;
		}
		unlink_free_space(block_group, info);

		if (info->bytes == bytes) {
			kfree(info);
288
			spin_unlock(&block_group->tree_lock);
289
290
291
292
293
294
295
			goto out;
		}

		info->offset += bytes;
		info->bytes -= bytes;

		ret = link_free_space(block_group, info);
296
		spin_unlock(&block_group->tree_lock);
297
		BUG_ON(ret);
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
	} else if (info && info->offset < offset &&
		   info->offset + info->bytes >= offset + bytes) {
		u64 old_start = info->offset;
		/*
		 * we're freeing space in the middle of the info,
		 * this can happen during tree log replay
		 *
		 * first unlink the old info and then
		 * insert it again after the hole we're creating
		 */
		unlink_free_space(block_group, info);
		if (offset + bytes < info->offset + info->bytes) {
			u64 old_end = info->offset + info->bytes;

			info->offset = offset + bytes;
			info->bytes = old_end - info->offset;
			ret = link_free_space(block_group, info);
			BUG_ON(ret);
		} else {
			/* the hole we're creating ends at the end
			 * of the info struct, just free the info
			 */
			kfree(info);
		}
322
		spin_unlock(&block_group->tree_lock);
323
324
325
		/* step two, insert a new info struct to cover anything
		 * before the hole
		 */
326
327
		ret = btrfs_add_free_space(block_group, old_start,
					   offset - old_start);
328
		BUG_ON(ret);
329
	} else {
330
		spin_unlock(&block_group->tree_lock);
Josef Bacik's avatar
Josef Bacik committed
331
332
333
334
		if (!info) {
			printk(KERN_ERR "couldn't find space %llu to free\n",
			       (unsigned long long)offset);
			printk(KERN_ERR "cached is %d, offset %llu bytes %llu\n",
335
336
337
			       block_group->cached,
			       (unsigned long long)block_group->key.objectid,
			       (unsigned long long)block_group->key.offset);
Josef Bacik's avatar
Josef Bacik committed
338
339
340
341
			btrfs_dump_free_space(block_group, bytes);
		} else if (info) {
			printk(KERN_ERR "hmm, found offset=%llu bytes=%llu, "
			       "but wanted offset=%llu bytes=%llu\n",
342
343
344
345
			       (unsigned long long)info->offset,
			       (unsigned long long)info->bytes,
			       (unsigned long long)offset,
			       (unsigned long long)bytes);
Josef Bacik's avatar
Josef Bacik committed
346
		}
347
348
349
		WARN_ON(1);
	}
out:
350
351
352
	return ret;
}

353
354
355
356
357
358
359
360
361
362
363
void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
			   u64 bytes)
{
	struct btrfs_free_space *info;
	struct rb_node *n;
	int count = 0;

	for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
		info = rb_entry(n, struct btrfs_free_space, offset_index);
		if (info->bytes >= bytes)
			count++;
364
365
366
		printk(KERN_ERR "entry offset %llu, bytes %llu\n",
		       (unsigned long long)info->offset,
		       (unsigned long long)info->bytes);
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
	}
	printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
	       "\n", count);
}

u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
{
	struct btrfs_free_space *info;
	struct rb_node *n;
	u64 ret = 0;

	for (n = rb_first(&block_group->free_space_offset); n;
	     n = rb_next(n)) {
		info = rb_entry(n, struct btrfs_free_space, offset_index);
		ret += info->bytes;
	}

	return ret;
}

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
/*
 * for a given cluster, put all of its extents back into the free
 * space cache.  If the block group passed doesn't match the block group
 * pointed to by the cluster, someone else raced in and freed the
 * cluster already.  In that case, we just return without changing anything
 */
static int
__btrfs_return_cluster_to_free_space(
			     struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster)
{
	struct btrfs_free_space *entry;
	struct rb_node *node;

	spin_lock(&cluster->lock);
	if (cluster->block_group != block_group)
		goto out;

	cluster->window_start = 0;
	node = rb_first(&cluster->root);
	while(node) {
		entry = rb_entry(node, struct btrfs_free_space, offset_index);
		node = rb_next(&entry->offset_index);
		rb_erase(&entry->offset_index, &cluster->root);
		link_free_space(block_group, entry);
	}
	list_del_init(&cluster->block_group_list);

	btrfs_put_block_group(cluster->block_group);
	cluster->block_group = NULL;
	cluster->root.rb_node = NULL;
out:
	spin_unlock(&cluster->lock);
	return 0;
}

423
424
425
426
void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
{
	struct btrfs_free_space *info;
	struct rb_node *node;
427
428
	struct btrfs_free_cluster *cluster;
	struct btrfs_free_cluster *safe;
429

430
	spin_lock(&block_group->tree_lock);
431
432
433
434
435
436
437
438

	list_for_each_entry_safe(cluster, safe, &block_group->cluster_list,
				 block_group_list) {

		WARN_ON(cluster->block_group != block_group);
		__btrfs_return_cluster_to_free_space(block_group, cluster);
	}

439
440
441
442
443
	while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
		info = rb_entry(node, struct btrfs_free_space, bytes_index);
		unlink_free_space(block_group, info);
		kfree(info);
		if (need_resched()) {
444
			spin_unlock(&block_group->tree_lock);
445
			cond_resched();
446
			spin_lock(&block_group->tree_lock);
447
448
		}
	}
449
	spin_unlock(&block_group->tree_lock);
450
451
}

452
453
u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
			       u64 offset, u64 bytes, u64 empty_size)
454
{
455
456
	struct btrfs_free_space *entry = NULL;
	u64 ret = 0;
457

458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
	spin_lock(&block_group->tree_lock);
	entry = tree_search_offset(&block_group->free_space_offset, offset,
				   bytes + empty_size, 1);
	if (!entry)
		entry = tree_search_bytes(&block_group->free_space_bytes,
					  offset, bytes + empty_size);
	if (entry) {
		unlink_free_space(block_group, entry);
		ret = entry->offset;
		entry->offset += bytes;
		entry->bytes -= bytes;

		if (!entry->bytes)
			kfree(entry);
		else
			link_free_space(block_group, entry);
	}
	spin_unlock(&block_group->tree_lock);
476
477
478

	return ret;
}
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

/*
 * given a cluster, put all of its extents back into the free space
 * cache.  If a block group is passed, this function will only free
 * a cluster that belongs to the passed block group.
 *
 * Otherwise, it'll get a reference on the block group pointed to by the
 * cluster and remove the cluster from it.
 */
int btrfs_return_cluster_to_free_space(
			       struct btrfs_block_group_cache *block_group,
			       struct btrfs_free_cluster *cluster)
{
	int ret;

	/* first, get a safe pointer to the block group */
	spin_lock(&cluster->lock);
	if (!block_group) {
		block_group = cluster->block_group;
		if (!block_group) {
			spin_unlock(&cluster->lock);
			return 0;
		}
	} else if (cluster->block_group != block_group) {
		/* someone else has already freed it don't redo their work */
		spin_unlock(&cluster->lock);
		return 0;
	}
	atomic_inc(&block_group->count);
	spin_unlock(&cluster->lock);

	/* now return any extents the cluster had on it */
	spin_lock(&block_group->tree_lock);
	ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
	spin_unlock(&block_group->tree_lock);

	/* finally drop our ref */
	btrfs_put_block_group(block_group);
	return ret;
}

/*
 * given a cluster, try to allocate 'bytes' from it, returns 0
 * if it couldn't find anything suitably large, or a logical disk offset
 * if things worked out
 */
u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster, u64 bytes,
			     u64 min_start)
{
	struct btrfs_free_space *entry = NULL;
	struct rb_node *node;
	u64 ret = 0;

	spin_lock(&cluster->lock);
	if (bytes > cluster->max_size)
		goto out;

	if (cluster->block_group != block_group)
		goto out;

	node = rb_first(&cluster->root);
	if (!node)
		goto out;

	entry = rb_entry(node, struct btrfs_free_space, offset_index);

	while(1) {
		if (entry->bytes < bytes || entry->offset < min_start) {
			struct rb_node *node;

			node = rb_next(&entry->offset_index);
			if (!node)
				break;
			entry = rb_entry(node, struct btrfs_free_space,
					 offset_index);
			continue;
		}
		ret = entry->offset;

		entry->offset += bytes;
		entry->bytes -= bytes;

		if (entry->bytes == 0) {
			rb_erase(&entry->offset_index, &cluster->root);
			kfree(entry);
		}
		break;
	}
out:
	spin_unlock(&cluster->lock);
	return ret;
}

/*
 * here we try to find a cluster of blocks in a block group.  The goal
 * is to find at least bytes free and up to empty_size + bytes free.
 * We might not find them all in one contiguous area.
 *
 * returns zero and sets up cluster if things worked out, otherwise
 * it returns -enospc
 */
int btrfs_find_space_cluster(struct btrfs_trans_handle *trans,
			     struct btrfs_block_group_cache *block_group,
			     struct btrfs_free_cluster *cluster,
			     u64 offset, u64 bytes, u64 empty_size)
{
	struct btrfs_free_space *entry = NULL;
	struct rb_node *node;
	struct btrfs_free_space *next;
	struct btrfs_free_space *last;
	u64 min_bytes;
	u64 window_start;
	u64 window_free;
	u64 max_extent = 0;
	int total_retries = 0;
	int ret;

	/* for metadata, allow allocates with more holes */
	if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
		/*
		 * we want to do larger allocations when we are
		 * flushing out the delayed refs, it helps prevent
		 * making more work as we go along.
		 */
		if (trans->transaction->delayed_refs.flushing)
			min_bytes = max(bytes, (bytes + empty_size) >> 1);
		else
			min_bytes = max(bytes, (bytes + empty_size) >> 4);
	} else
		min_bytes = max(bytes, (bytes + empty_size) >> 2);

	spin_lock(&block_group->tree_lock);
	spin_lock(&cluster->lock);

	/* someone already found a cluster, hooray */
	if (cluster->block_group) {
		ret = 0;
		goto out;
	}
again:
	min_bytes = min(min_bytes, bytes + empty_size);
	entry = tree_search_bytes(&block_group->free_space_bytes,
				  offset, min_bytes);
	if (!entry) {
		ret = -ENOSPC;
		goto out;
	}
	window_start = entry->offset;
	window_free = entry->bytes;
	last = entry;
	max_extent = entry->bytes;

	while(1) {
		/* out window is just right, lets fill it */
		if (window_free >= bytes + empty_size)
			break;

		node = rb_next(&last->offset_index);
		if (!node) {
			ret = -ENOSPC;
			goto out;
		}
		next = rb_entry(node, struct btrfs_free_space, offset_index);

		/*
		 * we haven't filled the empty size and the window is
		 * very large.  reset and try again
		 */
		if (next->offset - window_start > (bytes + empty_size) * 2) {
			entry = next;
			window_start = entry->offset;
			window_free = entry->bytes;
			last = entry;
			max_extent = 0;
			total_retries++;
655
			if (total_retries % 64 == 0) {
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
				if (min_bytes >= (bytes + empty_size)) {
					ret = -ENOSPC;
					goto out;
				}
				/*
				 * grow our allocation a bit, we're not having
				 * much luck
				 */
				min_bytes *= 2;
				goto again;
			}
		} else {
			last = next;
			window_free += next->bytes;
			if (entry->bytes > max_extent)
				max_extent = entry->bytes;
		}
	}

	cluster->window_start = entry->offset;

	/*
	 * now we've found our entries, pull them out of the free space
	 * cache and put them into the cluster rbtree
	 *
	 * The cluster includes an rbtree, but only uses the offset index
	 * of each free space cache entry.
	 */
	while(1) {
		node = rb_next(&entry->offset_index);
		unlink_free_space(block_group, entry);
		ret = tree_insert_offset(&cluster->root, entry->offset,
					 &entry->offset_index);
		BUG_ON(ret);

		if (!node || entry == last)
			break;

		entry = rb_entry(node, struct btrfs_free_space, offset_index);
	}
	ret = 0;
	cluster->max_size = max_extent;
	atomic_inc(&block_group->count);
	list_add_tail(&cluster->block_group_list, &block_group->cluster_list);
	cluster->block_group = block_group;
out:
	spin_unlock(&cluster->lock);
	spin_unlock(&block_group->tree_lock);

	return ret;
}

/*
 * simple code to zero out a cluster
 */
void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
{
	spin_lock_init(&cluster->lock);
	spin_lock_init(&cluster->refill_lock);
	cluster->root.rb_node = NULL;
	cluster->max_size = 0;
	INIT_LIST_HEAD(&cluster->block_group_list);
	cluster->block_group = NULL;
}