2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
18 #define _XOPEN_SOURCE 600
22 #include <sys/types.h>
26 #include "kerncompat.h"
27 #include "extent_map.h"
30 u64 cache_max
= 1024 * 1024 * 32;
32 void extent_map_tree_init(struct extent_map_tree
*tree
)
34 cache_tree_init(&tree
->state
);
35 cache_tree_init(&tree
->cache
);
36 INIT_LIST_HEAD(&tree
->lru
);
40 static struct extent_state
*alloc_extent_state(void)
42 struct extent_state
*state
;
44 state
= malloc(sizeof(*state
));
53 static void free_extent_state(struct extent_state
*state
)
56 BUG_ON(state
->refs
< 0);
61 void extent_map_tree_cleanup(struct extent_map_tree
*tree
)
63 struct extent_state
*es
;
64 struct extent_buffer
*eb
;
65 struct cache_extent
*cache
;
67 while(!list_empty(&tree
->lru
)) {
68 eb
= list_entry(tree
->lru
.next
, struct extent_buffer
, lru
);
70 fprintf(stderr
, "extent buffer leak: "
71 "start %Lu len %u\n", eb
->start
, eb
->len
);
74 free_extent_buffer(eb
);
77 cache
= find_first_cache_extent(&tree
->state
, 0);
80 es
= container_of(cache
, struct extent_state
, cache_node
);
81 remove_cache_extent(&tree
->state
, &es
->cache_node
);
82 free_extent_state(es
);
86 static inline void update_extent_state(struct extent_state
*state
)
88 state
->cache_node
.start
= state
->start
;
89 state
->cache_node
.size
= state
->end
+ 1 - state
->start
;
93 * Utility function to look for merge candidates inside a given range.
94 * Any extents with matching state are merged together into a single
95 * extent in the tree. Extents with EXTENT_IO in their state field are
98 static int merge_state(struct extent_map_tree
*tree
,
99 struct extent_state
*state
)
101 struct extent_state
*other
;
102 struct cache_extent
*other_node
;
104 if (state
->state
& EXTENT_IOBITS
)
107 other_node
= prev_cache_extent(&state
->cache_node
);
109 other
= container_of(other_node
, struct extent_state
,
111 if (other
->end
== state
->start
- 1 &&
112 other
->state
== state
->state
) {
113 state
->start
= other
->start
;
114 update_extent_state(state
);
115 remove_cache_extent(&tree
->state
, &other
->cache_node
);
116 free_extent_state(other
);
119 other_node
= next_cache_extent(&state
->cache_node
);
121 other
= container_of(other_node
, struct extent_state
,
123 if (other
->start
== state
->end
+ 1 &&
124 other
->state
== state
->state
) {
125 other
->start
= state
->start
;
126 update_extent_state(other
);
127 remove_cache_extent(&tree
->state
, &state
->cache_node
);
128 free_extent_state(state
);
135 * insert an extent_state struct into the tree. 'bits' are set on the
136 * struct before it is inserted.
138 static int insert_state(struct extent_map_tree
*tree
,
139 struct extent_state
*state
, u64 start
, u64 end
,
145 state
->state
|= bits
;
146 state
->start
= start
;
148 update_extent_state(state
);
149 ret
= insert_existing_cache_extent(&tree
->state
, &state
->cache_node
);
151 merge_state(tree
, state
);
156 * split a given extent state struct in two, inserting the preallocated
157 * struct 'prealloc' as the newly created second half. 'split' indicates an
158 * offset inside 'orig' where it should be split.
160 static int split_state(struct extent_map_tree
*tree
, struct extent_state
*orig
,
161 struct extent_state
*prealloc
, u64 split
)
164 prealloc
->start
= orig
->start
;
165 prealloc
->end
= split
- 1;
166 prealloc
->state
= orig
->state
;
167 update_extent_state(prealloc
);
169 update_extent_state(orig
);
170 ret
= insert_existing_cache_extent(&tree
->state
,
171 &prealloc
->cache_node
);
177 * clear some bits on a range in the tree.
179 static int clear_state_bit(struct extent_map_tree
*tree
,
180 struct extent_state
*state
, int bits
)
182 int ret
= state
->state
& bits
;
184 state
->state
&= ~bits
;
185 if (state
->state
== 0) {
186 remove_cache_extent(&tree
->state
, &state
->cache_node
);
187 free_extent_state(state
);
189 merge_state(tree
, state
);
195 * set some bits on a range in the tree.
197 int clear_extent_bits(struct extent_map_tree
*tree
, u64 start
,
198 u64 end
, int bits
, gfp_t mask
)
200 struct extent_state
*state
;
201 struct extent_state
*prealloc
= NULL
;
202 struct cache_extent
*node
;
207 prealloc
= alloc_extent_state();
212 * this search will find the extents that end after
215 node
= find_first_cache_extent(&tree
->state
, start
);
218 state
= container_of(node
, struct extent_state
, cache_node
);
219 if (state
->start
> end
)
223 * | ---- desired range ---- |
225 * | ------------- state -------------- |
227 * We need to split the extent we found, and may flip
228 * bits on second half.
230 * If the extent we found extends past our range, we
231 * just split and search again. It'll get split again
232 * the next time though.
234 * If the extent we found is inside our range, we clear
235 * the desired bit on it.
237 if (state
->start
< start
) {
238 err
= split_state(tree
, state
, prealloc
, start
);
239 BUG_ON(err
== -EEXIST
);
243 if (state
->end
<= end
) {
244 start
= state
->end
+ 1;
245 set
|= clear_state_bit(tree
, state
, bits
);
247 start
= state
->start
;
252 * | ---- desired range ---- |
254 * We need to split the extent, and clear the bit
257 if (state
->start
<= end
&& state
->end
> end
) {
258 err
= split_state(tree
, state
, prealloc
, end
+ 1);
259 BUG_ON(err
== -EEXIST
);
261 set
|= clear_state_bit(tree
, prealloc
, bits
);
266 start
= state
->end
+ 1;
267 set
|= clear_state_bit(tree
, state
, bits
);
271 free_extent_state(prealloc
);
281 * set some bits on a range in the tree.
283 int set_extent_bits(struct extent_map_tree
*tree
, u64 start
,
284 u64 end
, int bits
, gfp_t mask
)
286 struct extent_state
*state
;
287 struct extent_state
*prealloc
= NULL
;
288 struct cache_extent
*node
;
294 prealloc
= alloc_extent_state();
299 * this search will find the extents that end after
302 node
= find_first_cache_extent(&tree
->state
, start
);
304 err
= insert_state(tree
, prealloc
, start
, end
, bits
);
305 BUG_ON(err
== -EEXIST
);
310 state
= container_of(node
, struct extent_state
, cache_node
);
311 last_start
= state
->start
;
312 last_end
= state
->end
;
315 * | ---- desired range ---- |
318 * Just lock what we found and keep going
320 if (state
->start
== start
&& state
->end
<= end
) {
321 set
= state
->state
& bits
;
322 state
->state
|= bits
;
323 start
= state
->end
+ 1;
324 merge_state(tree
, state
);
328 * | ---- desired range ---- |
331 * | ------------- state -------------- |
333 * We need to split the extent we found, and may flip bits on
336 * If the extent we found extends past our
337 * range, we just split and search again. It'll get split
338 * again the next time though.
340 * If the extent we found is inside our range, we set the
343 if (state
->start
< start
) {
344 set
= state
->state
& bits
;
345 err
= split_state(tree
, state
, prealloc
, start
);
346 BUG_ON(err
== -EEXIST
);
350 if (state
->end
<= end
) {
351 state
->state
|= bits
;
352 start
= state
->end
+ 1;
353 merge_state(tree
, state
);
355 start
= state
->start
;
360 * | ---- desired range ---- |
361 * | state | or | state |
363 * There's a hole, we need to insert something in it and
364 * ignore the extent we found.
366 if (state
->start
> start
) {
368 if (end
< last_start
)
371 this_end
= last_start
-1;
372 err
= insert_state(tree
, prealloc
, start
, this_end
,
374 BUG_ON(err
== -EEXIST
);
378 start
= this_end
+ 1;
382 * | ---- desired range ---- |
383 * | ---------- state ---------- |
384 * We need to split the extent, and set the bit
387 set
= state
->state
& bits
;
388 err
= split_state(tree
, state
, prealloc
, end
+ 1);
389 BUG_ON(err
== -EEXIST
);
391 state
->state
|= bits
;
392 merge_state(tree
, prealloc
);
396 free_extent_state(prealloc
);
404 int set_extent_dirty(struct extent_map_tree
*tree
, u64 start
, u64 end
,
407 return set_extent_bits(tree
, start
, end
, EXTENT_DIRTY
, mask
);
410 int clear_extent_dirty(struct extent_map_tree
*tree
, u64 start
, u64 end
,
413 return clear_extent_bits(tree
, start
, end
, EXTENT_DIRTY
, mask
);
416 int find_first_extent_bit(struct extent_map_tree
*tree
, u64 start
,
417 u64
*start_ret
, u64
*end_ret
, int bits
)
419 struct cache_extent
*node
;
420 struct extent_state
*state
;
424 * this search will find all the extents that end after
427 node
= find_first_cache_extent(&tree
->state
, start
);
432 state
= container_of(node
, struct extent_state
, cache_node
);
433 if (state
->end
>= start
&& (state
->state
& bits
)) {
434 *start_ret
= state
->start
;
435 *end_ret
= state
->end
;
439 node
= next_cache_extent(node
);
447 int test_range_bit(struct extent_map_tree
*tree
, u64 start
, u64 end
,
448 int bits
, int filled
)
450 struct extent_state
*state
= NULL
;
451 struct cache_extent
*node
;
454 node
= find_first_cache_extent(&tree
->state
, start
);
455 while (node
&& start
<= end
) {
456 state
= container_of(node
, struct extent_state
, cache_node
);
458 if (filled
&& state
->start
> start
) {
462 if (state
->start
> end
)
464 if (state
->state
& bits
) {
472 start
= state
->end
+ 1;
475 node
= next_cache_extent(node
);
485 int set_state_private(struct extent_map_tree
*tree
, u64 start
, u64
private)
487 struct cache_extent
*node
;
488 struct extent_state
*state
;
491 node
= find_first_cache_extent(&tree
->state
, start
);
496 state
= container_of(node
, struct extent_state
, cache_node
);
497 if (state
->start
!= start
) {
501 state
->private = private;
506 int get_state_private(struct extent_map_tree
*tree
, u64 start
, u64
*private)
508 struct cache_extent
*node
;
509 struct extent_state
*state
;
512 node
= find_first_cache_extent(&tree
->state
, start
);
517 state
= container_of(node
, struct extent_state
, cache_node
);
518 if (state
->start
!= start
) {
522 *private = state
->private;
527 static int free_some_buffers(struct extent_map_tree
*tree
)
530 struct extent_buffer
*eb
;
531 struct list_head
*node
, *next
;
533 if (tree
->cache_size
< cache_max
)
535 list_for_each_safe(node
, next
, &tree
->lru
) {
536 eb
= list_entry(node
, struct extent_buffer
, lru
);
538 free_extent_buffer(eb
);
539 if (tree
->cache_size
< cache_max
)
548 static struct extent_buffer
*__alloc_extent_buffer(struct extent_map_tree
*tree
,
549 u64 bytenr
, u32 blocksize
)
551 struct extent_buffer
*eb
;
554 eb
= malloc(sizeof(struct extent_buffer
) + blocksize
);
564 eb
->dev_bytenr
= (u64
)-1;
565 eb
->cache_node
.start
= bytenr
;
566 eb
->cache_node
.size
= blocksize
;
568 free_some_buffers(tree
);
569 ret
= insert_existing_cache_extent(&tree
->cache
, &eb
->cache_node
);
574 list_add_tail(&eb
->lru
, &tree
->lru
);
575 tree
->cache_size
+= blocksize
;
579 void free_extent_buffer(struct extent_buffer
*eb
)
585 BUG_ON(eb
->refs
< 0);
587 struct extent_map_tree
*tree
= eb
->tree
;
588 BUG_ON(eb
->flags
& EXTENT_DIRTY
);
589 list_del_init(&eb
->lru
);
590 remove_cache_extent(&tree
->cache
, &eb
->cache_node
);
591 BUG_ON(tree
->cache_size
< eb
->len
);
592 tree
->cache_size
-= eb
->len
;
597 struct extent_buffer
*find_extent_buffer(struct extent_map_tree
*tree
,
598 u64 bytenr
, u32 blocksize
)
600 struct extent_buffer
*eb
= NULL
;
601 struct cache_extent
*cache
;
603 cache
= find_cache_extent(&tree
->cache
, bytenr
, blocksize
);
604 if (cache
&& cache
->start
== bytenr
&& cache
->size
== blocksize
) {
605 eb
= container_of(cache
, struct extent_buffer
, cache_node
);
606 list_move_tail(&eb
->lru
, &tree
->lru
);
612 struct extent_buffer
*find_first_extent_buffer(struct extent_map_tree
*tree
,
615 struct extent_buffer
*eb
= NULL
;
616 struct cache_extent
*cache
;
618 cache
= find_first_cache_extent(&tree
->cache
, start
);
620 eb
= container_of(cache
, struct extent_buffer
, cache_node
);
621 list_move_tail(&eb
->lru
, &tree
->lru
);
627 struct extent_buffer
*alloc_extent_buffer(struct extent_map_tree
*tree
,
628 u64 bytenr
, u32 blocksize
)
630 struct extent_buffer
*eb
;
631 struct cache_extent
*cache
;
633 cache
= find_cache_extent(&tree
->cache
, bytenr
, blocksize
);
634 if (cache
&& cache
->start
== bytenr
&& cache
->size
== blocksize
) {
635 eb
= container_of(cache
, struct extent_buffer
, cache_node
);
636 list_move_tail(&eb
->lru
, &tree
->lru
);
640 eb
= container_of(cache
, struct extent_buffer
,
642 BUG_ON(eb
->refs
!= 1);
643 free_extent_buffer(eb
);
645 eb
= __alloc_extent_buffer(tree
, bytenr
, blocksize
);
650 int read_extent_from_disk(struct extent_buffer
*eb
)
653 ret
= pread(eb
->fd
, eb
->data
, eb
->len
, eb
->dev_bytenr
);
656 if (ret
!= eb
->len
) {
665 int write_extent_to_disk(struct extent_buffer
*eb
)
668 ret
= pwrite(eb
->fd
, eb
->data
, eb
->len
, eb
->dev_bytenr
);
671 if (ret
!= eb
->len
) {
680 int set_extent_buffer_uptodate(struct extent_buffer
*eb
)
682 eb
->flags
|= EXTENT_UPTODATE
;
686 int extent_buffer_uptodate(struct extent_buffer
*eb
)
688 if (eb
->flags
& EXTENT_UPTODATE
)
693 int set_extent_buffer_dirty(struct extent_buffer
*eb
)
695 struct extent_map_tree
*tree
= eb
->tree
;
696 if (!(eb
->flags
& EXTENT_DIRTY
)) {
697 eb
->flags
|= EXTENT_DIRTY
;
698 set_extent_dirty(tree
, eb
->start
, eb
->start
+ eb
->len
- 1, 0);
699 extent_buffer_get(eb
);
704 int clear_extent_buffer_dirty(struct extent_buffer
*eb
)
706 struct extent_map_tree
*tree
= eb
->tree
;
707 if (eb
->flags
& EXTENT_DIRTY
) {
708 eb
->flags
&= ~EXTENT_DIRTY
;
709 clear_extent_dirty(tree
, eb
->start
, eb
->start
+ eb
->len
- 1, 0);
710 free_extent_buffer(eb
);
715 int memcmp_extent_buffer(struct extent_buffer
*eb
, const void *ptrv
,
716 unsigned long start
, unsigned long len
)
718 return memcmp(eb
->data
+ start
, ptrv
, len
);
721 void read_extent_buffer(struct extent_buffer
*eb
, void *dst
,
722 unsigned long start
, unsigned long len
)
724 memcpy(dst
, eb
->data
+ start
, len
);
727 void write_extent_buffer(struct extent_buffer
*eb
, const void *src
,
728 unsigned long start
, unsigned long len
)
730 memcpy(eb
->data
+ start
, src
, len
);
733 void copy_extent_buffer(struct extent_buffer
*dst
, struct extent_buffer
*src
,
734 unsigned long dst_offset
, unsigned long src_offset
,
737 memcpy(dst
->data
+ dst_offset
, src
->data
+ src_offset
, len
);
740 void memcpy_extent_buffer(struct extent_buffer
*dst
, unsigned long dst_offset
,
741 unsigned long src_offset
, unsigned long len
)
743 memcpy(dst
->data
+ dst_offset
, dst
->data
+ src_offset
, len
);
746 void memmove_extent_buffer(struct extent_buffer
*dst
, unsigned long dst_offset
,
747 unsigned long src_offset
, unsigned long len
)
749 memmove(dst
->data
+ dst_offset
, dst
->data
+ src_offset
, len
);
752 void memset_extent_buffer(struct extent_buffer
*eb
, char c
,
753 unsigned long start
, unsigned long len
)
755 memset(eb
->data
+ start
, c
, len
);