]>
Commit | Line | Data |
---|---|---|
c1359d91 LC |
1 | /* |
2 | * blkmap64_rb.c --- Simple rb-tree implementation for bitmaps | |
3 | * | |
4 | * (C)2010 Red Hat, Inc., Lukas Czerner <lczerner@redhat.com> | |
5 | * | |
6 | * %Begin-Header% | |
7 | * This file may be redistributed under the terms of the GNU Public | |
8 | * License. | |
9 | * %End-Header% | |
10 | */ | |
11 | ||
f47f3195 | 12 | #include "config.h" |
c1359d91 LC |
13 | #include <stdio.h> |
14 | #include <string.h> | |
15 | #if HAVE_UNISTD_H | |
16 | #include <unistd.h> | |
17 | #endif | |
18 | #include <fcntl.h> | |
19 | #include <time.h> | |
20 | #if HAVE_SYS_STAT_H | |
21 | #include <sys/stat.h> | |
22 | #endif | |
23 | #if HAVE_SYS_TYPES_H | |
24 | #include <sys/types.h> | |
25 | #endif | |
f47f3195 AS |
26 | #if HAVE_LINUX_TYPES_H |
27 | #include <linux/types.h> | |
28 | #endif | |
c1359d91 LC |
29 | |
30 | #include "ext2_fs.h" | |
31 | #include "ext2fsP.h" | |
32 | #include "bmap64.h" | |
33 | #include "rbtree.h" | |
34 | ||
35 | #include <limits.h> | |
36 | ||
37 | struct bmap_rb_extent { | |
38 | struct rb_node node; | |
39 | __u64 start; | |
918eeb32 | 40 | __u64 count; |
c1359d91 LC |
41 | }; |
42 | ||
43 | struct ext2fs_rb_private { | |
44 | struct rb_root root; | |
0bcba36f TT |
45 | struct bmap_rb_extent *wcursor; |
46 | struct bmap_rb_extent *rcursor; | |
fb129bba | 47 | struct bmap_rb_extent *rcursor_next; |
1625bf42 | 48 | #ifdef ENABLE_BMAP_STATS_OPS |
9288e3be LC |
49 | __u64 mark_hit; |
50 | __u64 test_hit; | |
51 | #endif | |
c1359d91 LC |
52 | }; |
53 | ||
e48bf256 TT |
54 | inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node) |
55 | { | |
56 | /* | |
57 | * This depends on the fact the struct rb_node is at the | |
58 | * beginning of the bmap_rb_extent structure. We use this | |
59 | * instead of the ext2fs_rb_entry macro because it causes gcc | |
60 | * -Wall to generate a huge amount of noise. | |
61 | */ | |
62 | return (struct bmap_rb_extent *) node; | |
63 | } | |
64 | ||
c1359d91 LC |
65 | static int rb_insert_extent(__u64 start, __u64 count, |
66 | struct ext2fs_rb_private *); | |
67 | static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64); | |
68 | ||
69 | /* #define DEBUG_RB */ | |
70 | ||
71 | #ifdef DEBUG_RB | |
72 | static void print_tree(struct rb_root *root) | |
73 | { | |
74 | struct rb_node *node = NULL; | |
75 | struct bmap_rb_extent *ext; | |
76 | ||
8b5273d5 | 77 | fprintf(stderr, "\t\t\t=================================\n"); |
c1359d91 LC |
78 | node = ext2fs_rb_first(root); |
79 | for (node = ext2fs_rb_first(root); node != NULL; | |
80 | node = ext2fs_rb_next(node)) { | |
e48bf256 | 81 | ext = node_to_extent(node); |
8b5273d5 | 82 | fprintf(stderr, "\t\t\t--> (%llu -> %llu)\n", |
33b9a60c TT |
83 | (unsigned long long) ext->start, |
84 | (unsigned long long) ext->start + ext->count); | |
c1359d91 | 85 | } |
8b5273d5 | 86 | fprintf(stderr, "\t\t\t=================================\n"); |
c1359d91 LC |
87 | } |
88 | ||
1d6fd6d0 | 89 | static void check_tree(struct rb_root *root, const char *msg) |
c1359d91 | 90 | { |
8b90ab2b | 91 | struct rb_node *node; |
c1359d91 LC |
92 | struct bmap_rb_extent *ext, *old = NULL; |
93 | ||
94 | for (node = ext2fs_rb_first(root); node; | |
95 | node = ext2fs_rb_next(node)) { | |
e48bf256 | 96 | ext = node_to_extent(node); |
4d46e6c7 | 97 | if (ext->count == 0) { |
8b5273d5 TT |
98 | fprintf(stderr, "Tree Error: count is zero\n"); |
99 | fprintf(stderr, "extent: %llu -> %llu (%llu)\n", | |
33b9a60c TT |
100 | (unsigned long long) ext->start, |
101 | (unsigned long long) ext->start + ext->count, | |
102 | (unsigned long long) ext->count); | |
c1359d91 LC |
103 | goto err_out; |
104 | } | |
4d46e6c7 | 105 | if (ext->start + ext->count < ext->start) { |
8b5273d5 TT |
106 | fprintf(stderr, |
107 | "Tree Error: start or count is crazy\n"); | |
108 | fprintf(stderr, "extent: %llu -> %llu (%llu)\n", | |
33b9a60c TT |
109 | (unsigned long long) ext->start, |
110 | (unsigned long long) ext->start + ext->count, | |
111 | (unsigned long long) ext->count); | |
c1359d91 LC |
112 | goto err_out; |
113 | } | |
114 | ||
115 | if (old) { | |
116 | if (old->start > ext->start) { | |
8b5273d5 TT |
117 | fprintf(stderr, "Tree Error: start is crazy\n"); |
118 | fprintf(stderr, "extent: %llu -> %llu (%llu)\n", | |
33b9a60c TT |
119 | (unsigned long long) old->start, |
120 | (unsigned long long) old->start + old->count, | |
121 | (unsigned long long) old->count); | |
8b5273d5 TT |
122 | fprintf(stderr, |
123 | "extent next: %llu -> %llu (%llu)\n", | |
33b9a60c TT |
124 | (unsigned long long) ext->start, |
125 | (unsigned long long) ext->start + ext->count, | |
126 | (unsigned long long) ext->count); | |
c1359d91 LC |
127 | goto err_out; |
128 | } | |
129 | if ((old->start + old->count) >= ext->start) { | |
8b5273d5 TT |
130 | fprintf(stderr, |
131 | "Tree Error: extent is crazy\n"); | |
132 | fprintf(stderr, "extent: %llu -> %llu (%llu)\n", | |
33b9a60c TT |
133 | (unsigned long long) old->start, |
134 | (unsigned long long) old->start + old->count, | |
135 | (unsigned long long) old->count); | |
8b5273d5 TT |
136 | fprintf(stderr, |
137 | "extent next: %llu -> %llu (%llu)\n", | |
33b9a60c TT |
138 | (unsigned long long) ext->start, |
139 | (unsigned long long) ext->start + ext->count, | |
140 | (unsigned long long) ext->count); | |
c1359d91 LC |
141 | goto err_out; |
142 | } | |
143 | } | |
144 | old = ext; | |
145 | } | |
1d6fd6d0 | 146 | return; |
c1359d91 LC |
147 | |
148 | err_out: | |
8b5273d5 | 149 | fprintf(stderr, "%s\n", msg); |
c1359d91 LC |
150 | print_tree(root); |
151 | exit(1); | |
152 | } | |
153 | #else | |
1d6fd6d0 | 154 | #define check_tree(root, msg) do {} while (0) |
d954fa40 | 155 | #define print_tree(root) do {} while (0) |
c1359d91 LC |
156 | #endif |
157 | ||
158 | static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start, | |
159 | __u64 count) | |
160 | { | |
161 | struct bmap_rb_extent *new_ext; | |
162 | int retval; | |
163 | ||
164 | retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent), | |
165 | &new_ext); | |
1b6de47f TT |
166 | if (retval) |
167 | abort(); | |
c1359d91 LC |
168 | |
169 | new_ext->start = start; | |
170 | new_ext->count = count; | |
171 | *ext = new_ext; | |
172 | } | |
173 | ||
174 | inline | |
175 | static void rb_free_extent(struct ext2fs_rb_private *bp, | |
176 | struct bmap_rb_extent *ext) | |
177 | { | |
0bcba36f TT |
178 | if (bp->wcursor == ext) |
179 | bp->wcursor = NULL; | |
180 | if (bp->rcursor == ext) | |
181 | bp->rcursor = NULL; | |
fb129bba TT |
182 | if (bp->rcursor_next == ext) |
183 | bp->rcursor_next = NULL; | |
c1359d91 LC |
184 | ext2fs_free_mem(&ext); |
185 | } | |
186 | ||
83d9ffcc | 187 | static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap_64 bitmap) |
c1359d91 LC |
188 | { |
189 | struct ext2fs_rb_private *bp; | |
190 | errcode_t retval; | |
191 | ||
192 | retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp); | |
193 | if (retval) | |
194 | return retval; | |
195 | ||
196 | bp->root = RB_ROOT; | |
0bcba36f | 197 | bp->rcursor = NULL; |
fb129bba | 198 | bp->rcursor_next = NULL; |
0bcba36f | 199 | bp->wcursor = NULL; |
c1359d91 | 200 | |
1625bf42 | 201 | #ifdef ENABLE_BMAP_STATS_OPS |
9288e3be LC |
202 | bp->test_hit = 0; |
203 | bp->mark_hit = 0; | |
204 | #endif | |
205 | ||
c1359d91 LC |
206 | bitmap->private = (void *) bp; |
207 | return 0; | |
208 | } | |
209 | ||
210 | static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), | |
83d9ffcc | 211 | ext2fs_generic_bitmap_64 bitmap) |
c1359d91 LC |
212 | { |
213 | errcode_t retval; | |
214 | ||
215 | retval = rb_alloc_private_data (bitmap); | |
216 | if (retval) | |
217 | return retval; | |
218 | ||
219 | return 0; | |
220 | } | |
221 | ||
222 | static void rb_free_tree(struct rb_root *root) | |
223 | { | |
224 | struct bmap_rb_extent *ext; | |
225 | struct rb_node *node, *next; | |
226 | ||
227 | for (node = ext2fs_rb_first(root); node; node = next) { | |
228 | next = ext2fs_rb_next(node); | |
e48bf256 | 229 | ext = node_to_extent(node); |
c1359d91 LC |
230 | ext2fs_rb_erase(node, root); |
231 | ext2fs_free_mem(&ext); | |
232 | } | |
233 | } | |
234 | ||
83d9ffcc | 235 | static void rb_free_bmap(ext2fs_generic_bitmap_64 bitmap) |
c1359d91 LC |
236 | { |
237 | struct ext2fs_rb_private *bp; | |
238 | ||
239 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
240 | ||
241 | rb_free_tree(&bp->root); | |
c1359d91 LC |
242 | ext2fs_free_mem(&bp); |
243 | bp = 0; | |
244 | } | |
245 | ||
83d9ffcc TT |
246 | static errcode_t rb_copy_bmap(ext2fs_generic_bitmap_64 src, |
247 | ext2fs_generic_bitmap_64 dest) | |
c1359d91 LC |
248 | { |
249 | struct ext2fs_rb_private *src_bp, *dest_bp; | |
250 | struct bmap_rb_extent *src_ext, *dest_ext; | |
251 | struct rb_node *dest_node, *src_node, *dest_last, **n; | |
252 | errcode_t retval = 0; | |
253 | ||
254 | retval = rb_alloc_private_data (dest); | |
255 | if (retval) | |
256 | return retval; | |
257 | ||
258 | src_bp = (struct ext2fs_rb_private *) src->private; | |
259 | dest_bp = (struct ext2fs_rb_private *) dest->private; | |
0bcba36f TT |
260 | src_bp->rcursor = NULL; |
261 | dest_bp->rcursor = NULL; | |
c1359d91 LC |
262 | |
263 | src_node = ext2fs_rb_first(&src_bp->root); | |
264 | while (src_node) { | |
e48bf256 | 265 | src_ext = node_to_extent(src_node); |
c1359d91 LC |
266 | retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent), |
267 | &dest_ext); | |
268 | if (retval) | |
269 | break; | |
270 | ||
271 | memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent)); | |
272 | ||
273 | dest_node = &dest_ext->node; | |
274 | n = &dest_bp->root.rb_node; | |
275 | ||
276 | dest_last = NULL; | |
277 | if (*n) { | |
278 | dest_last = ext2fs_rb_last(&dest_bp->root); | |
279 | n = &(dest_last)->rb_right; | |
280 | } | |
281 | ||
282 | ext2fs_rb_link_node(dest_node, dest_last, n); | |
283 | ext2fs_rb_insert_color(dest_node, &dest_bp->root); | |
284 | ||
285 | src_node = ext2fs_rb_next(src_node); | |
286 | } | |
287 | ||
288 | return retval; | |
289 | } | |
290 | ||
291 | static void rb_truncate(__u64 new_max, struct rb_root *root) | |
292 | { | |
293 | struct bmap_rb_extent *ext; | |
294 | struct rb_node *node; | |
295 | ||
296 | node = ext2fs_rb_last(root); | |
297 | while (node) { | |
e48bf256 | 298 | ext = node_to_extent(node); |
c1359d91 LC |
299 | |
300 | if ((ext->start + ext->count - 1) <= new_max) | |
301 | break; | |
302 | else if (ext->start > new_max) { | |
303 | ext2fs_rb_erase(node, root); | |
304 | ext2fs_free_mem(&ext); | |
305 | node = ext2fs_rb_last(root); | |
306 | continue; | |
307 | } else | |
308 | ext->count = new_max - ext->start + 1; | |
309 | } | |
310 | } | |
311 | ||
83d9ffcc | 312 | static errcode_t rb_resize_bmap(ext2fs_generic_bitmap_64 bmap, |
c1359d91 LC |
313 | __u64 new_end, __u64 new_real_end) |
314 | { | |
315 | struct ext2fs_rb_private *bp; | |
316 | ||
c1359d91 | 317 | bp = (struct ext2fs_rb_private *) bmap->private; |
0bcba36f TT |
318 | bp->rcursor = NULL; |
319 | bp->wcursor = NULL; | |
c1359d91 | 320 | |
2dbf34e5 TT |
321 | rb_truncate(((new_end < bmap->end) ? new_end : bmap->end) - bmap->start, |
322 | &bp->root); | |
c1359d91 LC |
323 | |
324 | bmap->end = new_end; | |
325 | bmap->real_end = new_real_end; | |
2dbf34e5 TT |
326 | |
327 | if (bmap->end < bmap->real_end) | |
328 | rb_insert_extent(bmap->end + 1 - bmap->start, | |
329 | bmap->real_end - bmap->end, bp); | |
c1359d91 LC |
330 | return 0; |
331 | ||
332 | } | |
333 | ||
334 | inline static int | |
335 | rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) | |
336 | { | |
fb129bba | 337 | struct bmap_rb_extent *rcursor, *next_ext = NULL; |
547a59a8 | 338 | struct rb_node *parent = NULL, *next; |
c1359d91 LC |
339 | struct rb_node **n = &bp->root.rb_node; |
340 | struct bmap_rb_extent *ext; | |
c1359d91 | 341 | |
0bcba36f | 342 | rcursor = bp->rcursor; |
c1359d91 LC |
343 | if (!rcursor) |
344 | goto search_tree; | |
345 | ||
9288e3be | 346 | if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) { |
1625bf42 | 347 | #ifdef ENABLE_BMAP_STATS_OPS |
9288e3be LC |
348 | bp->test_hit++; |
349 | #endif | |
c1359d91 | 350 | return 1; |
9288e3be | 351 | } |
c1359d91 | 352 | |
fb129bba TT |
353 | next_ext = bp->rcursor_next; |
354 | if (!next_ext) { | |
355 | next = ext2fs_rb_next(&rcursor->node); | |
356 | if (next) | |
e48bf256 | 357 | next_ext = node_to_extent(next); |
fb129bba TT |
358 | bp->rcursor_next = next_ext; |
359 | } | |
360 | if (next_ext) { | |
547a59a8 TT |
361 | if ((bit >= rcursor->start + rcursor->count) && |
362 | (bit < next_ext->start)) { | |
363 | #ifdef BMAP_STATS_OPS | |
364 | bp->test_hit++; | |
365 | #endif | |
366 | return 0; | |
367 | } | |
368 | } | |
fb129bba TT |
369 | bp->rcursor = NULL; |
370 | bp->rcursor_next = NULL; | |
547a59a8 | 371 | |
0bcba36f | 372 | rcursor = bp->wcursor; |
c1359d91 LC |
373 | if (!rcursor) |
374 | goto search_tree; | |
375 | ||
376 | if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) | |
377 | return 1; | |
378 | ||
379 | search_tree: | |
380 | ||
381 | while (*n) { | |
382 | parent = *n; | |
e48bf256 | 383 | ext = node_to_extent(parent); |
c1359d91 LC |
384 | if (bit < ext->start) |
385 | n = &(*n)->rb_left; | |
386 | else if (bit >= (ext->start + ext->count)) | |
387 | n = &(*n)->rb_right; | |
388 | else { | |
0bcba36f | 389 | bp->rcursor = ext; |
fb129bba | 390 | bp->rcursor_next = NULL; |
c1359d91 LC |
391 | return 1; |
392 | } | |
393 | } | |
394 | return 0; | |
395 | } | |
396 | ||
397 | static int rb_insert_extent(__u64 start, __u64 count, | |
398 | struct ext2fs_rb_private *bp) | |
399 | { | |
400 | struct rb_root *root = &bp->root; | |
401 | struct rb_node *parent = NULL, **n = &root->rb_node; | |
402 | struct rb_node *new_node, *node, *next; | |
403 | struct bmap_rb_extent *new_ext; | |
404 | struct bmap_rb_extent *ext; | |
405 | int retval = 0; | |
406 | ||
8b5273d5 TT |
407 | if (count == 0) |
408 | return 0; | |
409 | ||
fb129bba | 410 | bp->rcursor_next = NULL; |
0bcba36f | 411 | ext = bp->wcursor; |
c1359d91 LC |
412 | if (ext) { |
413 | if (start >= ext->start && | |
9288e3be | 414 | start <= (ext->start + ext->count)) { |
1625bf42 | 415 | #ifdef ENABLE_BMAP_STATS_OPS |
9288e3be LC |
416 | bp->mark_hit++; |
417 | #endif | |
c1359d91 | 418 | goto got_extent; |
9288e3be | 419 | } |
c1359d91 LC |
420 | } |
421 | ||
422 | while (*n) { | |
423 | parent = *n; | |
e48bf256 | 424 | ext = node_to_extent(parent); |
c1359d91 LC |
425 | |
426 | if (start < ext->start) { | |
427 | n = &(*n)->rb_left; | |
428 | } else if (start > (ext->start + ext->count)) { | |
429 | n = &(*n)->rb_right; | |
430 | } else { | |
431 | got_extent: | |
432 | if ((start + count) <= (ext->start + ext->count)) | |
433 | return 1; | |
434 | ||
435 | if ((ext->start + ext->count) == start) | |
436 | retval = 0; | |
437 | else | |
438 | retval = 1; | |
439 | ||
440 | count += (start - ext->start); | |
441 | start = ext->start; | |
442 | new_ext = ext; | |
443 | new_node = &ext->node; | |
444 | ||
445 | goto skip_insert; | |
446 | } | |
447 | } | |
448 | ||
449 | rb_get_new_extent(&new_ext, start, count); | |
450 | ||
451 | new_node = &new_ext->node; | |
452 | ext2fs_rb_link_node(new_node, parent, n); | |
453 | ext2fs_rb_insert_color(new_node, root); | |
0bcba36f | 454 | bp->wcursor = new_ext; |
c1359d91 LC |
455 | |
456 | node = ext2fs_rb_prev(new_node); | |
457 | if (node) { | |
e48bf256 | 458 | ext = node_to_extent(node); |
c1359d91 LC |
459 | if ((ext->start + ext->count) == start) { |
460 | start = ext->start; | |
461 | count += ext->count; | |
462 | ext2fs_rb_erase(node, root); | |
463 | rb_free_extent(bp, ext); | |
464 | } | |
465 | } | |
466 | ||
467 | skip_insert: | |
468 | /* See if we can merge extent to the right */ | |
469 | for (node = ext2fs_rb_next(new_node); node != NULL; node = next) { | |
470 | next = ext2fs_rb_next(node); | |
e48bf256 | 471 | ext = node_to_extent(node); |
c1359d91 LC |
472 | |
473 | if ((ext->start + ext->count) <= start) | |
474 | continue; | |
475 | ||
476 | /* No more merging */ | |
477 | if ((start + count) < ext->start) | |
478 | break; | |
479 | ||
480 | /* ext is embedded in new_ext interval */ | |
481 | if ((start + count) >= (ext->start + ext->count)) { | |
482 | ext2fs_rb_erase(node, root); | |
483 | rb_free_extent(bp, ext); | |
484 | continue; | |
485 | } else { | |
486 | /* merge ext with new_ext */ | |
487 | count += ((ext->start + ext->count) - | |
488 | (start + count)); | |
489 | ext2fs_rb_erase(node, root); | |
490 | rb_free_extent(bp, ext); | |
491 | break; | |
492 | } | |
493 | } | |
494 | ||
495 | new_ext->start = start; | |
496 | new_ext->count = count; | |
497 | ||
498 | return retval; | |
499 | } | |
500 | ||
501 | static int rb_remove_extent(__u64 start, __u64 count, | |
502 | struct ext2fs_rb_private *bp) | |
503 | { | |
504 | struct rb_root *root = &bp->root; | |
505 | struct rb_node *parent = NULL, **n = &root->rb_node; | |
506 | struct rb_node *node; | |
507 | struct bmap_rb_extent *ext; | |
508 | __u64 new_start, new_count; | |
509 | int retval = 0; | |
510 | ||
539d3ae3 | 511 | if (ext2fs_rb_empty_root(root)) |
c1359d91 LC |
512 | return 0; |
513 | ||
514 | while (*n) { | |
515 | parent = *n; | |
e48bf256 | 516 | ext = node_to_extent(parent); |
c1359d91 LC |
517 | if (start < ext->start) { |
518 | n = &(*n)->rb_left; | |
519 | continue; | |
520 | } else if (start >= (ext->start + ext->count)) { | |
521 | n = &(*n)->rb_right; | |
522 | continue; | |
523 | } | |
524 | ||
525 | if ((start > ext->start) && | |
526 | (start + count) < (ext->start + ext->count)) { | |
527 | /* We have to split extent into two */ | |
528 | new_start = start + count; | |
529 | new_count = (ext->start + ext->count) - new_start; | |
530 | ||
531 | ext->count = start - ext->start; | |
532 | ||
533 | rb_insert_extent(new_start, new_count, bp); | |
534 | return 1; | |
535 | } | |
536 | ||
537 | if ((start + count) >= (ext->start + ext->count)) { | |
538 | ext->count = start - ext->start; | |
539 | retval = 1; | |
540 | } | |
541 | ||
542 | if (0 == ext->count) { | |
543 | parent = ext2fs_rb_next(&ext->node); | |
544 | ext2fs_rb_erase(&ext->node, root); | |
545 | rb_free_extent(bp, ext); | |
546 | break; | |
547 | } | |
548 | ||
549 | if (start == ext->start) { | |
550 | ext->start += count; | |
551 | ext->count -= count; | |
552 | return 1; | |
553 | } | |
554 | } | |
555 | ||
556 | /* See if we should delete or truncate extent on the right */ | |
557 | for (; parent != NULL; parent = node) { | |
558 | node = ext2fs_rb_next(parent); | |
e48bf256 | 559 | ext = node_to_extent(parent); |
c1359d91 LC |
560 | if ((ext->start + ext->count) <= start) |
561 | continue; | |
562 | ||
563 | /* No more extents to be removed/truncated */ | |
564 | if ((start + count) < ext->start) | |
565 | break; | |
566 | ||
567 | /* The entire extent is within the region to be removed */ | |
568 | if ((start + count) >= (ext->start + ext->count)) { | |
569 | ext2fs_rb_erase(parent, root); | |
570 | rb_free_extent(bp, ext); | |
571 | retval = 1; | |
572 | continue; | |
573 | } else { | |
055866d8 | 574 | /* modify the last extent in region to be removed */ |
c1359d91 LC |
575 | ext->count -= ((start + count) - ext->start); |
576 | ext->start = start + count; | |
577 | retval = 1; | |
578 | break; | |
579 | } | |
580 | } | |
581 | ||
582 | return retval; | |
583 | } | |
584 | ||
83d9ffcc | 585 | static int rb_mark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) |
c1359d91 LC |
586 | { |
587 | struct ext2fs_rb_private *bp; | |
d954fa40 | 588 | int retval; |
c1359d91 LC |
589 | |
590 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
591 | arg -= bitmap->start; | |
592 | ||
d954fa40 TT |
593 | retval = rb_insert_extent(arg, 1, bp); |
594 | check_tree(&bp->root, __func__); | |
595 | return retval; | |
c1359d91 LC |
596 | } |
597 | ||
83d9ffcc | 598 | static int rb_unmark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) |
c1359d91 LC |
599 | { |
600 | struct ext2fs_rb_private *bp; | |
601 | int retval; | |
602 | ||
603 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
604 | arg -= bitmap->start; | |
605 | ||
606 | retval = rb_remove_extent(arg, 1, bp); | |
607 | check_tree(&bp->root, __func__); | |
608 | ||
609 | return retval; | |
610 | } | |
611 | ||
612 | inline | |
83d9ffcc | 613 | static int rb_test_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) |
c1359d91 LC |
614 | { |
615 | struct ext2fs_rb_private *bp; | |
616 | ||
617 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
618 | arg -= bitmap->start; | |
619 | ||
620 | return rb_test_bit(bp, arg); | |
621 | } | |
622 | ||
83d9ffcc | 623 | static void rb_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, |
c1359d91 LC |
624 | unsigned int num) |
625 | { | |
626 | struct ext2fs_rb_private *bp; | |
c1359d91 LC |
627 | |
628 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
629 | arg -= bitmap->start; | |
630 | ||
631 | rb_insert_extent(arg, num, bp); | |
d954fa40 | 632 | check_tree(&bp->root, __func__); |
c1359d91 LC |
633 | } |
634 | ||
83d9ffcc | 635 | static void rb_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, |
c1359d91 LC |
636 | unsigned int num) |
637 | { | |
638 | struct ext2fs_rb_private *bp; | |
c1359d91 LC |
639 | |
640 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
641 | arg -= bitmap->start; | |
642 | ||
643 | rb_remove_extent(arg, num, bp); | |
644 | check_tree(&bp->root, __func__); | |
645 | } | |
646 | ||
83d9ffcc | 647 | static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap, |
c1359d91 LC |
648 | __u64 start, unsigned int len) |
649 | { | |
650 | struct rb_node *parent = NULL, **n; | |
651 | struct rb_node *node, *next; | |
652 | struct ext2fs_rb_private *bp; | |
653 | struct bmap_rb_extent *ext; | |
654 | int retval = 1; | |
655 | ||
656 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
657 | n = &bp->root.rb_node; | |
658 | start -= bitmap->start; | |
659 | ||
539d3ae3 | 660 | if (len == 0 || ext2fs_rb_empty_root(&bp->root)) |
c1359d91 LC |
661 | return 1; |
662 | ||
663 | /* | |
664 | * If we find nothing, we should examine whole extent, but | |
665 | * when we find match, the extent is not clean, thus be return | |
666 | * false. | |
667 | */ | |
668 | while (*n) { | |
669 | parent = *n; | |
e48bf256 | 670 | ext = node_to_extent(parent); |
c1359d91 LC |
671 | if (start < ext->start) { |
672 | n = &(*n)->rb_left; | |
673 | } else if (start >= (ext->start + ext->count)) { | |
674 | n = &(*n)->rb_right; | |
675 | } else { | |
676 | /* | |
677 | * We found extent int the tree -> extent is not | |
678 | * clean | |
679 | */ | |
680 | return 0; | |
681 | } | |
682 | } | |
683 | ||
684 | node = parent; | |
685 | while (node) { | |
686 | next = ext2fs_rb_next(node); | |
e48bf256 | 687 | ext = node_to_extent(node); |
c1359d91 LC |
688 | node = next; |
689 | ||
690 | if ((ext->start + ext->count) <= start) | |
691 | continue; | |
692 | ||
693 | /* No more merging */ | |
694 | if ((start + len) <= ext->start) | |
695 | break; | |
696 | ||
697 | retval = 0; | |
698 | break; | |
699 | } | |
700 | return retval; | |
701 | } | |
702 | ||
83d9ffcc | 703 | static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap_64 bitmap, |
c1359d91 LC |
704 | __u64 start, size_t num, void *in) |
705 | { | |
706 | struct ext2fs_rb_private *bp; | |
fc8ea520 | 707 | unsigned char *cp = in; |
c1359d91 | 708 | size_t i; |
fc8ea520 | 709 | int first_set = -1; |
c1359d91 LC |
710 | |
711 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
712 | ||
713 | for (i = 0; i < num; i++) { | |
e3507739 | 714 | if ((i & 7) == 0) { |
fc8ea520 TT |
715 | unsigned char c = cp[i/8]; |
716 | if (c == 0xFF) { | |
717 | if (first_set == -1) | |
718 | first_set = i; | |
719 | i += 7; | |
720 | continue; | |
721 | } | |
722 | if ((c == 0x00) && (first_set == -1)) { | |
723 | i += 7; | |
724 | continue; | |
725 | } | |
726 | } | |
727 | if (ext2fs_test_bit(i, in)) { | |
728 | if (first_set == -1) | |
729 | first_set = i; | |
730 | continue; | |
731 | } | |
732 | if (first_set == -1) | |
733 | continue; | |
734 | ||
735 | rb_insert_extent(start + first_set - bitmap->start, | |
736 | i - first_set, bp); | |
d954fa40 | 737 | check_tree(&bp->root, __func__); |
fc8ea520 | 738 | first_set = -1; |
c1359d91 | 739 | } |
d954fa40 | 740 | if (first_set != -1) { |
fc8ea520 TT |
741 | rb_insert_extent(start + first_set - bitmap->start, |
742 | num - first_set, bp); | |
d954fa40 TT |
743 | check_tree(&bp->root, __func__); |
744 | } | |
c1359d91 LC |
745 | |
746 | return 0; | |
747 | } | |
748 | ||
83d9ffcc | 749 | static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap_64 bitmap, |
c1359d91 LC |
750 | __u64 start, size_t num, void *out) |
751 | { | |
752 | ||
753 | struct rb_node *parent = NULL, *next, **n; | |
754 | struct ext2fs_rb_private *bp; | |
755 | struct bmap_rb_extent *ext; | |
e50e985d | 756 | __u64 count, pos; |
c1359d91 LC |
757 | |
758 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
759 | n = &bp->root.rb_node; | |
760 | start -= bitmap->start; | |
761 | ||
539d3ae3 | 762 | if (ext2fs_rb_empty_root(&bp->root)) |
c1359d91 LC |
763 | return 0; |
764 | ||
765 | while (*n) { | |
766 | parent = *n; | |
e48bf256 | 767 | ext = node_to_extent(parent); |
c1359d91 LC |
768 | if (start < ext->start) { |
769 | n = &(*n)->rb_left; | |
770 | } else if (start >= (ext->start + ext->count)) { | |
771 | n = &(*n)->rb_right; | |
772 | } else | |
773 | break; | |
774 | } | |
775 | ||
c3f9641e TT |
776 | memset(out, 0, (num + 7) >> 3); |
777 | ||
c1359d91 LC |
778 | for (; parent != NULL; parent = next) { |
779 | next = ext2fs_rb_next(parent); | |
e48bf256 | 780 | ext = node_to_extent(parent); |
c1359d91 | 781 | |
c3f9641e | 782 | pos = ext->start; |
b65ccfc7 TT |
783 | count = ext->count; |
784 | if (pos >= start + num) | |
785 | break; | |
786 | if (pos < start) { | |
e50e985d | 787 | if (pos + count < start) |
b65ccfc7 | 788 | continue; |
e50e985d | 789 | count -= start - pos; |
c3f9641e | 790 | pos = start; |
c1359d91 | 791 | } |
b65ccfc7 TT |
792 | if (pos + count > start + num) |
793 | count = start + num - pos; | |
794 | ||
795 | while (count > 0) { | |
796 | if ((count >= 8) && | |
797 | ((pos - start) % 8) == 0) { | |
798 | int nbytes = count >> 3; | |
799 | int offset = (pos - start) >> 3; | |
800 | ||
e48bf256 | 801 | memset(((char *) out) + offset, 0xFF, nbytes); |
b65ccfc7 TT |
802 | pos += nbytes << 3; |
803 | count -= nbytes << 3; | |
804 | continue; | |
805 | } | |
c1359d91 LC |
806 | ext2fs_fast_set_bit64((pos - start), out); |
807 | pos++; | |
b65ccfc7 | 808 | count--; |
c1359d91 LC |
809 | } |
810 | } | |
c1359d91 LC |
811 | return 0; |
812 | } | |
813 | ||
83d9ffcc | 814 | static void rb_clear_bmap(ext2fs_generic_bitmap_64 bitmap) |
c1359d91 LC |
815 | { |
816 | struct ext2fs_rb_private *bp; | |
817 | ||
818 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
819 | ||
820 | rb_free_tree(&bp->root); | |
0bcba36f | 821 | bp->rcursor = NULL; |
fb129bba | 822 | bp->rcursor_next = NULL; |
0bcba36f | 823 | bp->wcursor = NULL; |
d954fa40 | 824 | check_tree(&bp->root, __func__); |
c1359d91 LC |
825 | } |
826 | ||
83d9ffcc | 827 | static errcode_t rb_find_first_zero(ext2fs_generic_bitmap_64 bitmap, |
3203cd93 TT |
828 | __u64 start, __u64 end, __u64 *out) |
829 | { | |
830 | struct rb_node *parent = NULL, **n; | |
3203cd93 TT |
831 | struct ext2fs_rb_private *bp; |
832 | struct bmap_rb_extent *ext; | |
3203cd93 TT |
833 | |
834 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
835 | n = &bp->root.rb_node; | |
836 | start -= bitmap->start; | |
837 | end -= bitmap->start; | |
838 | ||
839 | if (start > end) | |
840 | return EINVAL; | |
841 | ||
539d3ae3 | 842 | if (ext2fs_rb_empty_root(&bp->root)) |
3203cd93 TT |
843 | return ENOENT; |
844 | ||
845 | while (*n) { | |
846 | parent = *n; | |
847 | ext = node_to_extent(parent); | |
848 | if (start < ext->start) { | |
849 | n = &(*n)->rb_left; | |
850 | } else if (start >= (ext->start + ext->count)) { | |
851 | n = &(*n)->rb_right; | |
852 | } else if (ext->start + ext->count <= end) { | |
853 | *out = ext->start + ext->count + bitmap->start; | |
854 | return 0; | |
855 | } else | |
856 | return ENOENT; | |
857 | } | |
858 | ||
859 | *out = start + bitmap->start; | |
860 | return 0; | |
861 | } | |
862 | ||
83d9ffcc | 863 | static errcode_t rb_find_first_set(ext2fs_generic_bitmap_64 bitmap, |
3203cd93 TT |
864 | __u64 start, __u64 end, __u64 *out) |
865 | { | |
866 | struct rb_node *parent = NULL, **n; | |
d8f401b1 | 867 | struct rb_node *node; |
3203cd93 TT |
868 | struct ext2fs_rb_private *bp; |
869 | struct bmap_rb_extent *ext; | |
3203cd93 TT |
870 | |
871 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
872 | n = &bp->root.rb_node; | |
873 | start -= bitmap->start; | |
874 | end -= bitmap->start; | |
875 | ||
876 | if (start > end) | |
877 | return EINVAL; | |
878 | ||
539d3ae3 | 879 | if (ext2fs_rb_empty_root(&bp->root)) |
3203cd93 TT |
880 | return ENOENT; |
881 | ||
882 | while (*n) { | |
883 | parent = *n; | |
884 | ext = node_to_extent(parent); | |
885 | if (start < ext->start) { | |
886 | n = &(*n)->rb_left; | |
887 | } else if (start >= (ext->start + ext->count)) { | |
888 | n = &(*n)->rb_right; | |
889 | } else { | |
890 | /* The start bit is set */ | |
891 | *out = start + bitmap->start; | |
892 | return 0; | |
893 | } | |
894 | } | |
895 | ||
896 | node = parent; | |
897 | ext = node_to_extent(node); | |
898 | if (ext->start < start) { | |
899 | node = ext2fs_rb_next(node); | |
900 | if (node == NULL) | |
901 | return ENOENT; | |
902 | ext = node_to_extent(node); | |
903 | } | |
904 | if (ext->start <= end) { | |
905 | *out = ext->start + bitmap->start; | |
906 | return 0; | |
907 | } | |
908 | return ENOENT; | |
c1359d91 LC |
909 | } |
910 | ||
1625bf42 | 911 | #ifdef ENABLE_BMAP_STATS |
83d9ffcc | 912 | static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap) |
9288e3be LC |
913 | { |
914 | struct ext2fs_rb_private *bp; | |
915 | struct rb_node *node = NULL; | |
916 | struct bmap_rb_extent *ext; | |
917 | __u64 count = 0; | |
918 | __u64 max_size = 0; | |
919 | __u64 min_size = ULONG_MAX; | |
920 | __u64 size = 0, avg_size = 0; | |
e64e6761 | 921 | double eff; |
1625bf42 | 922 | #ifdef ENABLE_BMAP_STATS_OPS |
9288e3be | 923 | __u64 mark_all, test_all; |
e64e6761 TT |
924 | double m_hit = 0.0, t_hit = 0.0; |
925 | #endif | |
9288e3be LC |
926 | |
927 | bp = (struct ext2fs_rb_private *) bitmap->private; | |
928 | ||
9288e3be LC |
929 | for (node = ext2fs_rb_first(&bp->root); node != NULL; |
930 | node = ext2fs_rb_next(node)) { | |
e48bf256 | 931 | ext = node_to_extent(node); |
9288e3be LC |
932 | count++; |
933 | if (ext->count > max_size) | |
934 | max_size = ext->count; | |
935 | if (ext->count < min_size) | |
936 | min_size = ext->count; | |
937 | size += ext->count; | |
938 | } | |
939 | ||
940 | if (count) | |
941 | avg_size = size / count; | |
942 | if (min_size == ULONG_MAX) | |
943 | min_size = 0; | |
944 | eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) / | |
945 | (bitmap->real_end - bitmap->start); | |
1625bf42 | 946 | #ifdef ENABLE_BMAP_STATS_OPS |
9288e3be LC |
947 | mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count; |
948 | test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count; | |
949 | if (mark_all) | |
950 | m_hit = ((double)bp->mark_hit / mark_all) * 100; | |
951 | if (test_all) | |
952 | t_hit = ((double)bp->test_hit / test_all) * 100; | |
953 | ||
954 | fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n" | |
955 | "%16llu cache hits on mark (%.2f%%)\n", | |
956 | bp->test_hit, t_hit, bp->mark_hit, m_hit); | |
957 | #endif | |
958 | fprintf(stderr, "%16llu extents (%llu bytes)\n", | |
33b9a60c TT |
959 | (unsigned long long) count, (unsigned long long) |
960 | ((count * sizeof(struct bmap_rb_extent)) + | |
961 | sizeof(struct ext2fs_rb_private))); | |
9288e3be | 962 | fprintf(stderr, "%16llu bits minimum size\n", |
33b9a60c | 963 | (unsigned long long) min_size); |
9288e3be LC |
964 | fprintf(stderr, "%16llu bits maximum size\n" |
965 | "%16llu bits average size\n", | |
33b9a60c TT |
966 | (unsigned long long) max_size, (unsigned long long) avg_size); |
967 | fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", | |
968 | (unsigned long long) size, | |
969 | (unsigned long long) bitmap->real_end - bitmap->start); | |
9288e3be LC |
970 | fprintf(stderr, |
971 | "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n", | |
972 | eff); | |
973 | } | |
974 | #else | |
83d9ffcc | 975 | static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused))) |
894eaf85 TT |
976 | { |
977 | } | |
9288e3be LC |
978 | #endif |
979 | ||
c1359d91 LC |
980 | struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { |
981 | .type = EXT2FS_BMAP64_RBTREE, | |
982 | .new_bmap = rb_new_bmap, | |
983 | .free_bmap = rb_free_bmap, | |
984 | .copy_bmap = rb_copy_bmap, | |
985 | .resize_bmap = rb_resize_bmap, | |
986 | .mark_bmap = rb_mark_bmap, | |
987 | .unmark_bmap = rb_unmark_bmap, | |
988 | .test_bmap = rb_test_bmap, | |
989 | .test_clear_bmap_extent = rb_test_clear_bmap_extent, | |
990 | .mark_bmap_extent = rb_mark_bmap_extent, | |
991 | .unmark_bmap_extent = rb_unmark_bmap_extent, | |
992 | .set_bmap_range = rb_set_bmap_range, | |
993 | .get_bmap_range = rb_get_bmap_range, | |
994 | .clear_bmap = rb_clear_bmap, | |
9288e3be | 995 | .print_stats = rb_print_stats, |
3203cd93 TT |
996 | .find_first_zero = rb_find_first_zero, |
997 | .find_first_set = rb_find_first_set, | |
c1359d91 | 998 | }; |