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