169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o/* 269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * blkmap64_ba.c --- Simple bitarray implementation for bitmaps 369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * 469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * Copyright (C) 2008 Theodore Ts'o. 569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * 669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * %Begin-Header% 769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * This file may be redistributed under the terms of the GNU Public 869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * License. 969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * %End-Header% 1069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 1169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 12d1154eb460efe588eaed3d439c1caaca149fa362Theodore Ts'o#include "config.h" 1369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <stdio.h> 1469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <string.h> 1569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#if HAVE_UNISTD_H 1669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <unistd.h> 1769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#endif 1869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <fcntl.h> 1969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <time.h> 2069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#if HAVE_SYS_STAT_H 2169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <sys/stat.h> 2269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#endif 2369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#if HAVE_SYS_TYPES_H 2469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include <sys/types.h> 2569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#endif 2669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 2769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include "ext2_fs.h" 2869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include "ext2fsP.h" 2969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o#include "bmap64.h" 3069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 3169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o/* 3269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * Private data for bit array implementation of bitmap ops. 3369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * Currently, this is just a pointer to our big flat hunk of memory, 3469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * exactly equivalent to the old-skool char * bitmap member. 3569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 3669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 3769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostruct ext2fs_ba_private_struct { 3869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o char *bitarray; 3969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o}; 4069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 4169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'otypedef struct ext2fs_ba_private_struct *ext2fs_ba_private; 4269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 4369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap) 4469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 4569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp; 4669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o errcode_t retval; 4769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size_t size; 4869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 4969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 5069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * Since we only have the one pointer, we could just shove our 5169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * private data in the void *private field itself, but then 5269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * we'd have to do a fair bit of rewriting if we ever added a 5369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * field. I'm agnostic. 5469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 5569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp); 5669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (retval) 5769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return retval; 5869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 5969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); 6069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 6169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o retval = ext2fs_get_mem(size, &bp->bitarray); 6269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (retval) { 6369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_free_mem(&bp); 6469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bp = 0; 6569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return retval; 6669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 6769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bitmap->private = (void *) bp; 6869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 6969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 7069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 7169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), 7269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_generic_bitmap bitmap) 7369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 7469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp; 7569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o errcode_t retval; 7669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size_t size; 7769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 7869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o retval = ba_alloc_private_data (bitmap); 7969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (retval) 8069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return retval; 8169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 8269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bp = (ext2fs_ba_private) bitmap->private; 8369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); 8469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o memset(bp->bitarray, 0, size); 8569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 8669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 8769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 8869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 8969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic void ba_free_bmap(ext2fs_generic_bitmap bitmap) 9069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 9169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 9269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 9369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (!bp) 9469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return; 9569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 9669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (bp->bitarray) { 9769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_free_mem (&bp->bitarray); 9869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bp->bitarray = 0; 9969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 10069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_free_mem (&bp); 10169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bp = 0; 10269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 10369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 10469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic errcode_t ba_copy_bmap(ext2fs_generic_bitmap src, 10569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_generic_bitmap dest) 10669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 10769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private; 10869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private dest_bp; 10969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o errcode_t retval; 11069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size_t size; 11169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 11269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o retval = ba_alloc_private_data (dest); 11369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (retval) 11469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return retval; 11569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 11669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o dest_bp = (ext2fs_ba_private) dest->private; 11769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 11869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size = (size_t) (((src->real_end - src->start) / 8) + 1); 11969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o memcpy (dest_bp->bitarray, src_bp->bitarray, size); 12069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 12169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 12269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 12369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 12469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap, 12569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o __u64 new_end, __u64 new_real_end) 12669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 12769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private; 12869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o errcode_t retval; 12969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size_t size, new_size; 13069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o __u64 bitno; 13169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 13269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 13369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * If we're expanding the bitmap, make sure all of the new 13469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * parts of the bitmap are zero. 13569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 13669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (new_end > bmap->end) { 13769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bitno = bmap->real_end; 13869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (bitno > new_end) 13969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bitno = new_end; 14069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o for (; bitno > bmap->end; bitno--) 14169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray); 14269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 14369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (new_real_end == bmap->real_end) { 14469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bmap->end = new_end; 14569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 14669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 14769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 14869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o size = ((bmap->real_end - bmap->start) / 8) + 1; 14969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o new_size = ((new_real_end - bmap->start) / 8) + 1; 15069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 15169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (size != new_size) { 15269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o retval = ext2fs_resize_mem(size, new_size, &bp->bitarray); 15369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (retval) 15469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return retval; 15569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 15669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (new_size > size) 15769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o memset(bp->bitarray + size, 0, new_size - size); 15869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 15969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bmap->end = new_end; 16069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o bmap->real_end = new_real_end; 16169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 16269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 16369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 16469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 16569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) 16669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 16769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 16869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o blk64_t bitno = (blk64_t) arg; 16969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 17069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray); 17169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 17269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 17369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) 17469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 17569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 17669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o blk64_t bitno = (blk64_t) arg; 17769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 17869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray); 17969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 18069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 18169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) 18269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 18369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 18469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o blk64_t bitno = (blk64_t) arg; 18569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 18669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray); 18769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 18869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 18969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, 19069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int num) 19169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 19269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 19369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o blk64_t bitno = (blk64_t) arg; 19469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int i; 19569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 19669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o for (i = 0; i < num; i++) 19769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray); 19869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 19969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 20069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, 20169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int num) 20269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 20369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 20469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o blk64_t bitno = (blk64_t) arg; 20569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int i; 20669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 20769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o for (i = 0; i < num; i++) 20869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray); 20969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 21069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 21169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, 21269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o __u64 start, unsigned int len) 21369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 21469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 21569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o __u64 start_byte, len_byte = len >> 3; 21669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int start_bit, len_bit = len % 8; 21769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int first_bit = 0; 21869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o unsigned int last_bit = 0; 21969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o int mark_count = 0; 22069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o int mark_bit = 0; 22169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o int i; 22269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o const char *ADDR; 22369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 22469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ADDR = bp->bitarray; 22569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o start -= bitmap->start; 22669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o start_byte = start >> 3; 22769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o start_bit = start % 8; 22869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 22969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (start_bit != 0) { 23069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 23169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * The compared start block number or start inode number 23269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * is not the first bit in a byte. 23369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 23469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o mark_count = 8 - start_bit; 23569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (len < 8 - start_bit) { 23669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o mark_count = (int)len; 23769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o mark_bit = len + start_bit - 1; 23869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } else 23969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o mark_bit = 7; 24069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 24169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o for (i = mark_count; i > 0; i--, mark_bit--) 24269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o first_bit |= 1 << mark_bit; 24369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 24469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 24569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * Compare blocks or inodes in the first byte. 24669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * If there is any marked bit, this function returns 0. 24769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 24869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (first_bit & ADDR[start_byte]) 24969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 25069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o else if (len <= 8 - start_bit) 25169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 1; 25269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 25369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o start_byte++; 25469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o len_bit = (len - mark_count) % 8; 25569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o len_byte = (len - mark_count) >> 3; 25669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 25769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 25869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 25969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * The compared start block number or start inode number is 26069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * the first bit in a byte. 26169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 26269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (len_bit != 0) { 26369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 26469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * The compared end block number or end inode number is 26569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * not the last bit in a byte. 26669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 26769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) 26869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o last_bit |= 1 << mark_bit; 26969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 27069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* 27169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * Compare blocks or inodes in the last byte. 27269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o * If there is any marked bit, this function returns 0. 27369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o */ 27469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o if (last_bit & ADDR[start_byte + len_byte]) 27569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 27669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o else if (len_byte == 0) 27769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 1; 27869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o } 27969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 28069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o /* Check whether all bytes are 0 */ 28169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); 28269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 28369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 28469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 28569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap, 28669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o __u64 start, size_t num, void *in) 28769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 28869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 28969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 29069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3); 29169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 29269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 29369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 29469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 29569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap, 29669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o __u64 start, size_t num, void *out) 29769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 29869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 29969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 30069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3); 30169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 30269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o return 0; 30369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 30469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 30569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostatic void ba_clear_bmap(ext2fs_generic_bitmap bitmap) 30669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o{ 30769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; 30869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 30969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o memset(bp->bitarray, 0, 31069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); 31169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o} 31269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o 313567e7a36ee840b7258b154929ae10759ba2ac597Tony Breeds#ifdef ENABLE_BMAP_STATS 3149288e3be665bb8d5657d7f710687a50fad859acfLukas Czernerstatic void ba_print_stats(ext2fs_generic_bitmap bitmap) 3159288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner{ 3169288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner fprintf(stderr, "%16llu Bytes used by bitarray\n", 3179288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner ((bitmap->real_end - bitmap->start) >> 3) + 1 + 3189288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner sizeof(struct ext2fs_ba_private_struct)); 3199288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner} 320567e7a36ee840b7258b154929ae10759ba2ac597Tony Breeds#else 32125f291c9b32d8017e6969c72a75e37d354c0570bTheodore Ts'ostatic void ba_print_stats(ext2fs_generic_bitmap bitmap EXT2FS_ATTR((unused))) 32225f291c9b32d8017e6969c72a75e37d354c0570bTheodore Ts'o{ 32325f291c9b32d8017e6969c72a75e37d354c0570bTheodore Ts'o} 324567e7a36ee840b7258b154929ae10759ba2ac597Tony Breeds#endif 3259288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner 32611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes/* Find the first zero bit between start and end, inclusive. */ 32711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedesstatic errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap, 32811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes __u64 start, __u64 end, __u64 *out) 32911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes{ 33011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private; 33111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes unsigned long bitpos = start - bitmap->start; 33211f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes unsigned long count = end - start + 1; 33311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes int byte_found = 0; /* whether a != 0xff byte has been found */ 33411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes const unsigned char *pos; 33511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes unsigned long max_loop_count, i; 33611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 33711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes /* scan bits until we hit a byte boundary */ 33811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes while ((bitpos & 0x7) != 0 && count > 0) { 33911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (!ext2fs_test_bit64(bitpos, bp->bitarray)) { 34011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes *out = bitpos + bitmap->start; 34111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes return 0; 34211f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 34311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes bitpos++; 34411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes count--; 34511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 34611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 34711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (!count) 34811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes return ENOENT; 34911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 35011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); 35111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes /* scan bytes until 8-byte (64-bit) aligned */ 352d4e5abfb1bb990a029005c1a801961fc1a0ba866Adrien Schildknecht while (count >= 8 && (((uintptr_t)pos) & 0x07)) { 35311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (*pos != 0xff) { 35411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes byte_found = 1; 35511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes break; 35611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 35711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes pos++; 35811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes count -= 8; 35911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes bitpos += 8; 36011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 36111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 36211f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (!byte_found) { 36311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes max_loop_count = count >> 6; /* 8-byte blocks */ 36411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes i = max_loop_count; 36511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes while (i) { 36611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (*((const __u64 *)pos) != ((__u64)-1)) 36711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes break; 36811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes pos += 8; 36911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes i--; 37011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 37111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes count -= 64 * (max_loop_count - i); 37211f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes bitpos += 64 * (max_loop_count - i); 37311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 37411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes max_loop_count = count >> 3; 37511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes i = max_loop_count; 37611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes while (i) { 37711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (*pos != 0xff) { 37811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes byte_found = 1; 37911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes break; 38011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 38111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes pos++; 38211f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes i--; 38311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 38411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes count -= 8 * (max_loop_count - i); 38511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes bitpos += 8 * (max_loop_count - i); 38611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 38711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 38811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes /* Here either count < 8 or byte_found == 1. */ 38911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes while (count-- > 0) { 39011f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes if (!ext2fs_test_bit64(bitpos, bp->bitarray)) { 39111f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes *out = bitpos + bitmap->start; 39211f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes return 0; 39311f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 39411f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes bitpos++; 39511f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes } 39611f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 39711f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes return ENOENT; 39811f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes} 39911f359f7660f0194ac1752ea83a704e6db1d5f9fSami Liedes 40014717832dd76322d95d24685b425e3b560556034Theodore Ts'o/* Find the first one bit between start and end, inclusive. */ 40114717832dd76322d95d24685b425e3b560556034Theodore Ts'ostatic errcode_t ba_find_first_set(ext2fs_generic_bitmap bitmap, 40214717832dd76322d95d24685b425e3b560556034Theodore Ts'o __u64 start, __u64 end, __u64 *out) 40314717832dd76322d95d24685b425e3b560556034Theodore Ts'o{ 40414717832dd76322d95d24685b425e3b560556034Theodore Ts'o ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private; 40514717832dd76322d95d24685b425e3b560556034Theodore Ts'o unsigned long bitpos = start - bitmap->start; 40614717832dd76322d95d24685b425e3b560556034Theodore Ts'o unsigned long count = end - start + 1; 40714717832dd76322d95d24685b425e3b560556034Theodore Ts'o int byte_found = 0; /* whether a != 0xff byte has been found */ 40814717832dd76322d95d24685b425e3b560556034Theodore Ts'o const unsigned char *pos; 40914717832dd76322d95d24685b425e3b560556034Theodore Ts'o unsigned long max_loop_count, i; 41014717832dd76322d95d24685b425e3b560556034Theodore Ts'o 41114717832dd76322d95d24685b425e3b560556034Theodore Ts'o /* scan bits until we hit a byte boundary */ 41214717832dd76322d95d24685b425e3b560556034Theodore Ts'o while ((bitpos & 0x7) != 0 && count > 0) { 41314717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (ext2fs_test_bit64(bitpos, bp->bitarray)) { 41414717832dd76322d95d24685b425e3b560556034Theodore Ts'o *out = bitpos + bitmap->start; 41514717832dd76322d95d24685b425e3b560556034Theodore Ts'o return 0; 41614717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 41714717832dd76322d95d24685b425e3b560556034Theodore Ts'o bitpos++; 41814717832dd76322d95d24685b425e3b560556034Theodore Ts'o count--; 41914717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 42014717832dd76322d95d24685b425e3b560556034Theodore Ts'o 42114717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (!count) 42214717832dd76322d95d24685b425e3b560556034Theodore Ts'o return ENOENT; 42314717832dd76322d95d24685b425e3b560556034Theodore Ts'o 42414717832dd76322d95d24685b425e3b560556034Theodore Ts'o pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); 42514717832dd76322d95d24685b425e3b560556034Theodore Ts'o /* scan bytes until 8-byte (64-bit) aligned */ 426d4e5abfb1bb990a029005c1a801961fc1a0ba866Adrien Schildknecht while (count >= 8 && (((uintptr_t)pos) & 0x07)) { 42714717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (*pos != 0) { 42814717832dd76322d95d24685b425e3b560556034Theodore Ts'o byte_found = 1; 42914717832dd76322d95d24685b425e3b560556034Theodore Ts'o break; 43014717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 43114717832dd76322d95d24685b425e3b560556034Theodore Ts'o pos++; 43214717832dd76322d95d24685b425e3b560556034Theodore Ts'o count -= 8; 43314717832dd76322d95d24685b425e3b560556034Theodore Ts'o bitpos += 8; 43414717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 43514717832dd76322d95d24685b425e3b560556034Theodore Ts'o 43614717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (!byte_found) { 43714717832dd76322d95d24685b425e3b560556034Theodore Ts'o max_loop_count = count >> 6; /* 8-byte blocks */ 43814717832dd76322d95d24685b425e3b560556034Theodore Ts'o i = max_loop_count; 43914717832dd76322d95d24685b425e3b560556034Theodore Ts'o while (i) { 44014717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (*((const __u64 *)pos) != 0) 44114717832dd76322d95d24685b425e3b560556034Theodore Ts'o break; 44214717832dd76322d95d24685b425e3b560556034Theodore Ts'o pos += 8; 44314717832dd76322d95d24685b425e3b560556034Theodore Ts'o i--; 44414717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 44514717832dd76322d95d24685b425e3b560556034Theodore Ts'o count -= 64 * (max_loop_count - i); 44614717832dd76322d95d24685b425e3b560556034Theodore Ts'o bitpos += 64 * (max_loop_count - i); 44714717832dd76322d95d24685b425e3b560556034Theodore Ts'o 44814717832dd76322d95d24685b425e3b560556034Theodore Ts'o max_loop_count = count >> 3; 44914717832dd76322d95d24685b425e3b560556034Theodore Ts'o i = max_loop_count; 45014717832dd76322d95d24685b425e3b560556034Theodore Ts'o while (i) { 45114717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (*pos != 0) { 45214717832dd76322d95d24685b425e3b560556034Theodore Ts'o byte_found = 1; 45314717832dd76322d95d24685b425e3b560556034Theodore Ts'o break; 45414717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 45514717832dd76322d95d24685b425e3b560556034Theodore Ts'o pos++; 45614717832dd76322d95d24685b425e3b560556034Theodore Ts'o i--; 45714717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 45814717832dd76322d95d24685b425e3b560556034Theodore Ts'o count -= 8 * (max_loop_count - i); 45914717832dd76322d95d24685b425e3b560556034Theodore Ts'o bitpos += 8 * (max_loop_count - i); 46014717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 46114717832dd76322d95d24685b425e3b560556034Theodore Ts'o 46214717832dd76322d95d24685b425e3b560556034Theodore Ts'o /* Here either count < 8 or byte_found == 1. */ 46314717832dd76322d95d24685b425e3b560556034Theodore Ts'o while (count-- > 0) { 46414717832dd76322d95d24685b425e3b560556034Theodore Ts'o if (ext2fs_test_bit64(bitpos, bp->bitarray)) { 46514717832dd76322d95d24685b425e3b560556034Theodore Ts'o *out = bitpos + bitmap->start; 46614717832dd76322d95d24685b425e3b560556034Theodore Ts'o return 0; 46714717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 46814717832dd76322d95d24685b425e3b560556034Theodore Ts'o bitpos++; 46914717832dd76322d95d24685b425e3b560556034Theodore Ts'o } 47014717832dd76322d95d24685b425e3b560556034Theodore Ts'o 47114717832dd76322d95d24685b425e3b560556034Theodore Ts'o return ENOENT; 47214717832dd76322d95d24685b425e3b560556034Theodore Ts'o} 47314717832dd76322d95d24685b425e3b560556034Theodore Ts'o 47469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'ostruct ext2_bitmap_ops ext2fs_blkmap64_bitarray = { 47569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .type = EXT2FS_BMAP64_BITARRAY, 47669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .new_bmap = ba_new_bmap, 47769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .free_bmap = ba_free_bmap, 47869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .copy_bmap = ba_copy_bmap, 47969365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .resize_bmap = ba_resize_bmap, 48069365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .mark_bmap = ba_mark_bmap, 48169365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .unmark_bmap = ba_unmark_bmap, 48269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .test_bmap = ba_test_bmap, 48369365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .test_clear_bmap_extent = ba_test_clear_bmap_extent, 48469365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .mark_bmap_extent = ba_mark_bmap_extent, 48569365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .unmark_bmap_extent = ba_unmark_bmap_extent, 48669365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .set_bmap_range = ba_set_bmap_range, 48769365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .get_bmap_range = ba_get_bmap_range, 48869365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o .clear_bmap = ba_clear_bmap, 4899288e3be665bb8d5657d7f710687a50fad859acfLukas Czerner .print_stats = ba_print_stats, 49014717832dd76322d95d24685b425e3b560556034Theodore Ts'o .find_first_zero = ba_find_first_zero, 49114717832dd76322d95d24685b425e3b560556034Theodore Ts'o .find_first_set = ba_find_first_set 49269365c689b7164014e539b40ef62fc8eb804a05cTheodore Ts'o}; 493