?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Print the root generation in btrfs-debug-tree
[btrfs-progs-unstable/devel.git] / extent_io.c
blob8f0a8763c161ad4881c9f8c8cfb494b41aa6e76b
1
2 /*
3 * Copyright (C) 2007 Oracle. All rights reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public
7 * License v2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public
15 * License along with this program; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 021110-1307, USA.
18 */
19 #define _XOPEN_SOURCE 600
20 #define __USE_XOPEN2K
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <sys/types.h>
24 #include <sys/stat.h>
25 #include <fcntl.h>
26 #include <unistd.h>
27 #include "kerncompat.h"
28 #include "extent_io.h"
29 #include "list.h"
30
31 u64 cache_max = 1024 * 1024 * 32;
32
33 void extent_io_tree_init(struct extent_io_tree *tree)
34 {
35 cache_tree_init(&tree->state);
36 cache_tree_init(&tree->cache);
37 INIT_LIST_HEAD(&tree->lru);
38 tree->cache_size = 0;
39 }
40
41 static struct extent_state *alloc_extent_state(void)
42 {
43 struct extent_state *state;
44
45 state = malloc(sizeof(*state));
46 if (!state)
47 return NULL;
48 state->refs = 1;
49 state->state = 0;
50 state->private = 0;
51 return state;
52 }
53
54 static void free_extent_state(struct extent_state *state)
55 {
56 state->refs--;
57 BUG_ON(state->refs < 0);
58 if (state->refs == 0)
59 free(state);
60 }
61
62 void extent_io_tree_cleanup(struct extent_io_tree *tree)
63 {
64 struct extent_state *es;
65 struct extent_buffer *eb;
66 struct cache_extent *cache;
67
68 while(!list_empty(&tree->lru)) {
69 eb = list_entry(tree->lru.next, struct extent_buffer, lru);
70 if (eb->refs != 1) {
71 fprintf(stderr, "extent buffer leak: "
72 "start %llu len %u\n",
73 (unsigned long long)eb->start, eb->len);
74 eb->refs = 1;
75 }
76 free_extent_buffer(eb);
77 }
78 while (1) {
79 cache = find_first_cache_extent(&tree->state, 0);
80 if (!cache)
81 break;
82 es = container_of(cache, struct extent_state, cache_node);
83 remove_cache_extent(&tree->state, &es->cache_node);
84 free_extent_state(es);
85 }
86 }
87
88 static inline void update_extent_state(struct extent_state *state)
89 {
90 state->cache_node.start = state->start;
91 state->cache_node.size = state->end + 1 - state->start;
92 }
93
94 /*
95 * Utility function to look for merge candidates inside a given range.
96 * Any extents with matching state are merged together into a single
97 * extent in the tree. Extents with EXTENT_IO in their state field are
98 * not merged
99 */
100 static int merge_state(struct extent_io_tree *tree,
101 struct extent_state *state)
102 {
103 struct extent_state *other;
104 struct cache_extent *other_node;
105
106 if (state->state & EXTENT_IOBITS)
107 return 0;
108
109 other_node = prev_cache_extent(&state->cache_node);
110 if (other_node) {
111 other = container_of(other_node, struct extent_state,
112 cache_node);
113 if (other->end == state->start - 1 &&
114 other->state == state->state) {
115 state->start = other->start;
116 update_extent_state(state);
117 remove_cache_extent(&tree->state, &other->cache_node);
118 free_extent_state(other);
119 }
120 }
121 other_node = next_cache_extent(&state->cache_node);
122 if (other_node) {
123 other = container_of(other_node, struct extent_state,
124 cache_node);
125 if (other->start == state->end + 1 &&
126 other->state == state->state) {
127 other->start = state->start;
128 update_extent_state(other);
129 remove_cache_extent(&tree->state, &state->cache_node);
130 free_extent_state(state);
131 }
132 }
133 return 0;
134 }
135
136 /*
137 * insert an extent_state struct into the tree. 'bits' are set on the
138 * struct before it is inserted.
139 */
140 static int insert_state(struct extent_io_tree *tree,
141 struct extent_state *state, u64 start, u64 end,
142 int bits)
143 {
144 int ret;
145
146 BUG_ON(end < start);
147 state->state |= bits;
148 state->start = start;
149 state->end = end;
150 update_extent_state(state);
151 ret = insert_existing_cache_extent(&tree->state, &state->cache_node);
152 BUG_ON(ret);
153 merge_state(tree, state);
154 return 0;
155 }
156
157 /*
158 * split a given extent state struct in two, inserting the preallocated
159 * struct 'prealloc' as the newly created second half. 'split' indicates an
160 * offset inside 'orig' where it should be split.
161 */
162 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
163 struct extent_state *prealloc, u64 split)
164 {
165 int ret;
166 prealloc->start = orig->start;
167 prealloc->end = split - 1;
168 prealloc->state = orig->state;
169 update_extent_state(prealloc);
170 orig->start = split;
171 update_extent_state(orig);
172 ret = insert_existing_cache_extent(&tree->state,
173 &prealloc->cache_node);
174 BUG_ON(ret);
175 return 0;
176 }
177
178 /*
179 * clear some bits on a range in the tree.
180 */
181 static int clear_state_bit(struct extent_io_tree *tree,
182 struct extent_state *state, int bits)
183 {
184 int ret = state->state & bits;
185
186 state->state &= ~bits;
187 if (state->state == 0) {
188 remove_cache_extent(&tree->state, &state->cache_node);
189 free_extent_state(state);
190 } else {
191 merge_state(tree, state);
192 }
193 return ret;
194 }
195
196 /*
197 * set some bits on a range in the tree.
198 */
199 int clear_extent_bits(struct extent_io_tree *tree, u64 start,
200 u64 end, int bits, gfp_t mask)
201 {
202 struct extent_state *state;
203 struct extent_state *prealloc = NULL;
204 struct cache_extent *node;
205 u64 last_end;
206 int err;
207 int set = 0;
208
209 again:
210 prealloc = alloc_extent_state();
211 if (!prealloc)
212 return -ENOMEM;
213
214 /*
215 * this search will find the extents that end after
216 * our range starts
217 */
218 node = find_first_cache_extent(&tree->state, start);
219 if (!node)
220 goto out;
221 state = container_of(node, struct extent_state, cache_node);
222 if (state->start > end)
223 goto out;
224 last_end = state->end;
225
226 /*
227 * | ---- desired range ---- |
228 * | state | or
229 * | ------------- state -------------- |
230 *
231 * We need to split the extent we found, and may flip
232 * bits on second half.
233 *
234 * If the extent we found extends past our range, we
235 * just split and search again. It'll get split again
236 * the next time though.
237 *
238 * If the extent we found is inside our range, we clear
239 * the desired bit on it.
240 */
241 if (state->start < start) {
242 err = split_state(tree, state, prealloc, start);
243 BUG_ON(err == -EEXIST);
244 prealloc = NULL;
245 if (err)
246 goto out;
247 if (state->end <= end) {
248 set |= clear_state_bit(tree, state, bits);
249 if (last_end == (u64)-1)
250 goto out;
251 start = last_end + 1;
252 } else {
253 start = state->start;
254 }
255 goto search_again;
256 }
257 /*
258 * | ---- desired range ---- |
259 * | state |
260 * We need to split the extent, and clear the bit
261 * on the first half
262 */
263 if (state->start <= end && state->end > end) {
264 err = split_state(tree, state, prealloc, end + 1);
265 BUG_ON(err == -EEXIST);
266
267 set |= clear_state_bit(tree, prealloc, bits);
268 prealloc = NULL;
269 goto out;
270 }
271
272 start = state->end + 1;
273 set |= clear_state_bit(tree, state, bits);
274 if (last_end == (u64)-1)
275 goto out;
276 start = last_end + 1;
277 goto search_again;
278 out:
279 if (prealloc)
280 free_extent_state(prealloc);
281 return set;
282
283 search_again:
284 if (start > end)
285 goto out;
286 goto again;
287 }
288
289 /*
290 * set some bits on a range in the tree.
291 */
292 int set_extent_bits(struct extent_io_tree *tree, u64 start,
293 u64 end, int bits, gfp_t mask)
294 {
295 struct extent_state *state;
296 struct extent_state *prealloc = NULL;
297 struct cache_extent *node;
298 int err = 0;
299 u64 last_start;
300 u64 last_end;
301 again:
302 prealloc = alloc_extent_state();
303 if (!prealloc)
304 return -ENOMEM;
305
306 /*
307 * this search will find the extents that end after
308 * our range starts
309 */
310 node = find_first_cache_extent(&tree->state, start);
311 if (!node) {
312 err = insert_state(tree, prealloc, start, end, bits);
313 BUG_ON(err == -EEXIST);
314 prealloc = NULL;
315 goto out;
316 }
317
318 state = container_of(node, struct extent_state, cache_node);
319 last_start = state->start;
320 last_end = state->end;
321
322 /*
323 * | ---- desired range ---- |
324 * | state |
325 *
326 * Just lock what we found and keep going
327 */
328 if (state->start == start && state->end <= end) {
329 state->state |= bits;
330 merge_state(tree, state);
331 if (last_end == (u64)-1)
332 goto out;
333 start = last_end + 1;
334 goto search_again;
335 }
336 /*
337 * | ---- desired range ---- |
338 * | state |
339 * or
340 * | ------------- state -------------- |
341 *
342 * We need to split the extent we found, and may flip bits on
343 * second half.
344 *
345 * If the extent we found extends past our
346 * range, we just split and search again. It'll get split
347 * again the next time though.
348 *
349 * If the extent we found is inside our range, we set the
350 * desired bit on it.
351 */
352 if (state->start < start) {
353 err = split_state(tree, state, prealloc, start);
354 BUG_ON(err == -EEXIST);
355 prealloc = NULL;
356 if (err)
357 goto out;
358 if (state->end <= end) {
359 state->state |= bits;
360 start = state->end + 1;
361 merge_state(tree, state);
362 if (last_end == (u64)-1)
363 goto out;
364 start = last_end + 1;
365 } else {
366 start = state->start;
367 }
368 goto search_again;
369 }
370 /*
371 * | ---- desired range ---- |
372 * | state | or | state |
373 *
374 * There's a hole, we need to insert something in it and
375 * ignore the extent we found.
376 */
377 if (state->start > start) {
378 u64 this_end;
379 if (end < last_start)
380 this_end = end;
381 else
382 this_end = last_start -1;
383 err = insert_state(tree, prealloc, start, this_end,
384 bits);
385 BUG_ON(err == -EEXIST);
386 prealloc = NULL;
387 if (err)
388 goto out;
389 start = this_end + 1;
390 goto search_again;
391 }
392 /*
393 * | ---- desired range ---- |
394 * | ---------- state ---------- |
395 * We need to split the extent, and set the bit
396 * on the first half
397 */
398 err = split_state(tree, state, prealloc, end + 1);
399 BUG_ON(err == -EEXIST);
400
401 state->state |= bits;
402 merge_state(tree, prealloc);
403 prealloc = NULL;
404 out:
405 if (prealloc)
406 free_extent_state(prealloc);
407 return err;
408 search_again:
409 if (start > end)
410 goto out;
411 goto again;
412 }
413
414 int set_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
415 gfp_t mask)
416 {
417 return set_extent_bits(tree, start, end, EXTENT_DIRTY, mask);
418 }
419
420 int clear_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
421 gfp_t mask)
422 {
423 return clear_extent_bits(tree, start, end, EXTENT_DIRTY, mask);
424 }
425
426 int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
427 u64 *start_ret, u64 *end_ret, int bits)
428 {
429 struct cache_extent *node;
430 struct extent_state *state;
431 int ret = 1;
432
433 /*
434 * this search will find all the extents that end after
435 * our range starts.
436 */
437 node = find_first_cache_extent(&tree->state, start);
438 if (!node)
439 goto out;
440
441 while(1) {
442 state = container_of(node, struct extent_state, cache_node);
443 if (state->end >= start && (state->state & bits)) {
444 *start_ret = state->start;
445 *end_ret = state->end;
446 ret = 0;
447 break;
448 }
449 node = next_cache_extent(node);
450 if (!node)
451 break;
452 }
453 out:
454 return ret;
455 }
456
457 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
458 int bits, int filled)
459 {
460 struct extent_state *state = NULL;
461 struct cache_extent *node;
462 int bitset = 0;
463
464 node = find_first_cache_extent(&tree->state, start);
465 while (node && start <= end) {
466 state = container_of(node, struct extent_state, cache_node);
467
468 if (filled && state->start > start) {
469 bitset = 0;
470 break;
471 }
472 if (state->start > end)
473 break;
474 if (state->state & bits) {
475 bitset = 1;
476 if (!filled)
477 break;
478 } else if (filled) {
479 bitset = 0;
480 break;
481 }
482 start = state->end + 1;
483 if (start > end)
484 break;
485 node = next_cache_extent(node);
486 if (!node) {
487 if (filled)
488 bitset = 0;
489 break;
490 }
491 }
492 return bitset;
493 }
494
495 int set_state_private(struct extent_io_tree *tree, u64 start, u64 private)
496 {
497 struct cache_extent *node;
498 struct extent_state *state;
499 int ret = 0;
500
501 node = find_first_cache_extent(&tree->state, start);
502 if (!node) {
503 ret = -ENOENT;
504 goto out;
505 }
506 state = container_of(node, struct extent_state, cache_node);
507 if (state->start != start) {
508 ret = -ENOENT;
509 goto out;
510 }
511 state->private = private;
512 out:
513 return ret;
514 }
515
516 int get_state_private(struct extent_io_tree *tree, u64 start, u64 *private)
517 {
518 struct cache_extent *node;
519 struct extent_state *state;
520 int ret = 0;
521
522 node = find_first_cache_extent(&tree->state, start);
523 if (!node) {
524 ret = -ENOENT;
525 goto out;
526 }
527 state = container_of(node, struct extent_state, cache_node);
528 if (state->start != start) {
529 ret = -ENOENT;
530 goto out;
531 }
532 *private = state->private;
533 out:
534 return ret;
535 }
536
537 static int free_some_buffers(struct extent_io_tree *tree)
538 {
539 u32 nrscan = 0;
540 struct extent_buffer *eb;
541 struct list_head *node, *next;
542
543 if (tree->cache_size < cache_max)
544 return 0;
545 list_for_each_safe(node, next, &tree->lru) {
546 eb = list_entry(node, struct extent_buffer, lru);
547 if (eb->refs == 1) {
548 free_extent_buffer(eb);
549 if (tree->cache_size < cache_max)
550 break;
551 } else {
552 list_move_tail(&eb->lru, &tree->lru);
553 }
554 if (nrscan++ > 64)
555 break;
556 }
557 return 0;
558 }
559
560 static struct extent_buffer *__alloc_extent_buffer(struct extent_io_tree *tree,
561 u64 bytenr, u32 blocksize)
562 {
563 struct extent_buffer *eb;
564 int ret;
565
566 eb = malloc(sizeof(struct extent_buffer) + blocksize);
567 if (!eb) {
568 BUG();
569 return NULL;
570 }
571 memset(eb, 0, sizeof(struct extent_buffer) + blocksize);
572
573 eb->start = bytenr;
574 eb->len = blocksize;
575 eb->refs = 2;
576 eb->flags = 0;
577 eb->tree = tree;
578 eb->fd = -1;
579 eb->dev_bytenr = (u64)-1;
580 eb->cache_node.start = bytenr;
581 eb->cache_node.size = blocksize;
582
583 free_some_buffers(tree);
584 ret = insert_existing_cache_extent(&tree->cache, &eb->cache_node);
585 if (ret) {
586 free(eb);
587 return NULL;
588 }
589 list_add_tail(&eb->lru, &tree->lru);
590 tree->cache_size += blocksize;
591 return eb;
592 }
593
594 void free_extent_buffer(struct extent_buffer *eb)
595 {
596 if (!eb)
597 return;
598
599 eb->refs--;
600 BUG_ON(eb->refs < 0);
601 if (eb->refs == 0) {
602 struct extent_io_tree *tree = eb->tree;
603 BUG_ON(eb->flags & EXTENT_DIRTY);
604 list_del_init(&eb->lru);
605 remove_cache_extent(&tree->cache, &eb->cache_node);
606 BUG_ON(tree->cache_size < eb->len);
607 tree->cache_size -= eb->len;
608 free(eb);
609 }
610 }
611
612 struct extent_buffer *find_extent_buffer(struct extent_io_tree *tree,
613 u64 bytenr, u32 blocksize)
614 {
615 struct extent_buffer *eb = NULL;
616 struct cache_extent *cache;
617
618 cache = find_cache_extent(&tree->cache, bytenr, blocksize);
619 if (cache && cache->start == bytenr && cache->size == blocksize) {
620 eb = container_of(cache, struct extent_buffer, cache_node);
621 list_move_tail(&eb->lru, &tree->lru);
622 eb->refs++;
623 }
624 return eb;
625 }
626
627 struct extent_buffer *find_first_extent_buffer(struct extent_io_tree *tree,
628 u64 start)
629 {
630 struct extent_buffer *eb = NULL;
631 struct cache_extent *cache;
632
633 cache = find_first_cache_extent(&tree->cache, start);
634 if (cache) {
635 eb = container_of(cache, struct extent_buffer, cache_node);
636 list_move_tail(&eb->lru, &tree->lru);
637 eb->refs++;
638 }
639 return eb;
640 }
641
642 struct extent_buffer *alloc_extent_buffer(struct extent_io_tree *tree,
643 u64 bytenr, u32 blocksize)
644 {
645 struct extent_buffer *eb;
646 struct cache_extent *cache;
647
648 cache = find_cache_extent(&tree->cache, bytenr, blocksize);
649 if (cache && cache->start == bytenr && cache->size == blocksize) {
650 eb = container_of(cache, struct extent_buffer, cache_node);
651 list_move_tail(&eb->lru, &tree->lru);
652 eb->refs++;
653 } else {
654 if (cache) {
655 eb = container_of(cache, struct extent_buffer,
656 cache_node);
657 BUG_ON(eb->refs != 1);
658 free_extent_buffer(eb);
659 }
660 eb = __alloc_extent_buffer(tree, bytenr, blocksize);
661 }
662 return eb;
663 }
664
665 int read_extent_from_disk(struct extent_buffer *eb)
666 {
667 int ret;
668 ret = pread(eb->fd, eb->data, eb->len, eb->dev_bytenr);
669 if (ret < 0)
670 goto out;
671 if (ret != eb->len) {
672 ret = -EIO;
673 goto out;
674 }
675 ret = 0;
676 out:
677 return ret;
678 }
679
680 int write_extent_to_disk(struct extent_buffer *eb)
681 {
682 int ret;
683 ret = pwrite(eb->fd, eb->data, eb->len, eb->dev_bytenr);
684 if (ret < 0)
685 goto out;
686 if (ret != eb->len) {
687 ret = -EIO;
688 goto out;
689 }
690 ret = 0;
691 out:
692 return ret;
693 }
694
695 int set_extent_buffer_uptodate(struct extent_buffer *eb)
696 {
697 eb->flags |= EXTENT_UPTODATE;
698 return 0;
699 }
700
701 int clear_extent_buffer_uptodate(struct extent_io_tree *tree,
702 struct extent_buffer *eb)
703 {
704 eb->flags &= ~EXTENT_UPTODATE;
705 return 0;
706 }
707
708 int extent_buffer_uptodate(struct extent_buffer *eb)
709 {
710 if (eb->flags & EXTENT_UPTODATE)
711 return 1;
712 return 0;
713 }
714
715 int set_extent_buffer_dirty(struct extent_buffer *eb)
716 {
717 struct extent_io_tree *tree = eb->tree;
718 if (!(eb->flags & EXTENT_DIRTY)) {
719 eb->flags |= EXTENT_DIRTY;
720 set_extent_dirty(tree, eb->start, eb->start + eb->len - 1, 0);
721 extent_buffer_get(eb);
722 }
723 return 0;
724 }
725
726 int clear_extent_buffer_dirty(struct extent_buffer *eb)
727 {
728 struct extent_io_tree *tree = eb->tree;
729 if (eb->flags & EXTENT_DIRTY) {
730 eb->flags &= ~EXTENT_DIRTY;
731 clear_extent_dirty(tree, eb->start, eb->start + eb->len - 1, 0);
732 free_extent_buffer(eb);
733 }
734 return 0;
735 }
736
737 int memcmp_extent_buffer(struct extent_buffer *eb, const void *ptrv,
738 unsigned long start, unsigned long len)
739 {
740 return memcmp(eb->data + start, ptrv, len);
741 }
742
743 void read_extent_buffer(struct extent_buffer *eb, void *dst,
744 unsigned long start, unsigned long len)
745 {
746 memcpy(dst, eb->data + start, len);
747 }
748
749 void write_extent_buffer(struct extent_buffer *eb, const void *src,
750 unsigned long start, unsigned long len)
751 {
752 memcpy(eb->data + start, src, len);
753 }
754
755 void copy_extent_buffer(struct extent_buffer *dst, struct extent_buffer *src,
756 unsigned long dst_offset, unsigned long src_offset,
757 unsigned long len)
758 {
759 memcpy(dst->data + dst_offset, src->data + src_offset, len);
760 }
761
762 void memcpy_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
763 unsigned long src_offset, unsigned long len)
764 {
765 memcpy(dst->data + dst_offset, dst->data + src_offset, len);
766 }
767
768 void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
769 unsigned long src_offset, unsigned long len)
770 {
771 memmove(dst->data + dst_offset, dst->data + src_offset, len);
772 }
773
774 void memset_extent_buffer(struct extent_buffer *eb, char c,
775 unsigned long start, unsigned long len)
776 {
777 memset(eb->data + start, c, len);
778 }
(deprecated) Btrfs progs developments and patch integration