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