|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* blkmap64_ba.c --- Simple bitarray implementation for bitmaps
|
|
Packit Service |
6dc5fa |
*
|
|
Packit Service |
6dc5fa |
* Copyright (C) 2008 Theodore Ts'o.
|
|
Packit Service |
6dc5fa |
*
|
|
Packit Service |
6dc5fa |
* %Begin-Header%
|
|
Packit Service |
6dc5fa |
* This file may be redistributed under the terms of the GNU Public
|
|
Packit Service |
6dc5fa |
* License.
|
|
Packit Service |
6dc5fa |
* %End-Header%
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
#include "config.h"
|
|
Packit Service |
6dc5fa |
#include <stdio.h>
|
|
Packit Service |
6dc5fa |
#include <string.h>
|
|
Packit Service |
6dc5fa |
#if HAVE_UNISTD_H
|
|
Packit Service |
6dc5fa |
#include <unistd.h>
|
|
Packit Service |
6dc5fa |
#endif
|
|
Packit Service |
6dc5fa |
#include <fcntl.h>
|
|
Packit Service |
6dc5fa |
#include <time.h>
|
|
Packit Service |
6dc5fa |
#if HAVE_SYS_STAT_H
|
|
Packit Service |
6dc5fa |
#include <sys/stat.h>
|
|
Packit Service |
6dc5fa |
#endif
|
|
Packit Service |
6dc5fa |
#if HAVE_SYS_TYPES_H
|
|
Packit Service |
6dc5fa |
#include <sys/types.h>
|
|
Packit Service |
6dc5fa |
#endif
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
#include "ext2_fs.h"
|
|
Packit Service |
6dc5fa |
#include "ext2fsP.h"
|
|
Packit Service |
6dc5fa |
#include "bmap64.h"
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* Private data for bit array implementation of bitmap ops.
|
|
Packit Service |
6dc5fa |
* Currently, this is just a pointer to our big flat hunk of memory,
|
|
Packit Service |
6dc5fa |
* exactly equivalent to the old-skool char * bitmap member.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
struct ext2fs_ba_private_struct {
|
|
Packit Service |
6dc5fa |
char *bitarray;
|
|
Packit Service |
6dc5fa |
};
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp;
|
|
Packit Service |
6dc5fa |
errcode_t retval;
|
|
Packit Service |
6dc5fa |
size_t size;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* Since we only have the one pointer, we could just shove our
|
|
Packit Service |
6dc5fa |
* private data in the void *private field itself, but then
|
|
Packit Service |
6dc5fa |
* we'd have to do a fair bit of rewriting if we ever added a
|
|
Packit Service |
6dc5fa |
* field. I'm agnostic.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
|
|
Packit Service |
6dc5fa |
if (retval)
|
|
Packit Service |
6dc5fa |
return retval;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
retval = ext2fs_get_mem(size, &bp->bitarray);
|
|
Packit Service |
6dc5fa |
if (retval) {
|
|
Packit Service |
6dc5fa |
ext2fs_free_mem(&bp);
|
|
Packit Service |
6dc5fa |
bp = 0;
|
|
Packit Service |
6dc5fa |
return retval;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
bitmap->private = (void *) bp;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
|
|
Packit Service |
76ee5c |
ext2fs_generic_bitmap bitmap)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp;
|
|
Packit Service |
6dc5fa |
errcode_t retval;
|
|
Packit Service |
6dc5fa |
size_t size;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
retval = ba_alloc_private_data (bitmap);
|
|
Packit Service |
6dc5fa |
if (retval)
|
|
Packit Service |
6dc5fa |
return retval;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
|
|
Packit Service |
6dc5fa |
memset(bp->bitarray, 0, size);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static void ba_free_bmap(ext2fs_generic_bitmap bitmap)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (!bp)
|
|
Packit Service |
6dc5fa |
return;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (bp->bitarray) {
|
|
Packit Service |
6dc5fa |
ext2fs_free_mem (&bp->bitarray);
|
|
Packit Service |
6dc5fa |
bp->bitarray = 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
ext2fs_free_mem (&bp);
|
|
Packit Service |
6dc5fa |
bp = 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src,
|
|
Packit Service |
76ee5c |
ext2fs_generic_bitmap dest)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private dest_bp;
|
|
Packit Service |
6dc5fa |
errcode_t retval;
|
|
Packit Service |
6dc5fa |
size_t size;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
retval = ba_alloc_private_data (dest);
|
|
Packit Service |
6dc5fa |
if (retval)
|
|
Packit Service |
6dc5fa |
return retval;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
dest_bp = (ext2fs_ba_private) dest->private;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
size = (size_t) (((src->real_end - src->start) / 8) + 1);
|
|
Packit Service |
6dc5fa |
memcpy (dest_bp->bitarray, src_bp->bitarray, size);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap,
|
|
Packit Service |
6dc5fa |
__u64 new_end, __u64 new_real_end)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
|
|
Packit Service |
6dc5fa |
errcode_t retval;
|
|
Packit Service |
6dc5fa |
size_t size, new_size;
|
|
Packit Service |
6dc5fa |
__u64 bitno;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* If we're expanding the bitmap, make sure all of the new
|
|
Packit Service |
6dc5fa |
* parts of the bitmap are zero.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
if (new_end > bmap->end) {
|
|
Packit Service |
6dc5fa |
bitno = bmap->real_end;
|
|
Packit Service |
6dc5fa |
if (bitno > new_end)
|
|
Packit Service |
6dc5fa |
bitno = new_end;
|
|
Packit Service |
6dc5fa |
for (; bitno > bmap->end; bitno--)
|
|
Packit Service |
6dc5fa |
ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
if (new_real_end == bmap->real_end) {
|
|
Packit Service |
6dc5fa |
bmap->end = new_end;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
size = ((bmap->real_end - bmap->start) / 8) + 1;
|
|
Packit Service |
6dc5fa |
new_size = ((new_real_end - bmap->start) / 8) + 1;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (size != new_size) {
|
|
Packit Service |
6dc5fa |
retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
|
|
Packit Service |
6dc5fa |
if (retval)
|
|
Packit Service |
6dc5fa |
return retval;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
if (new_size > size)
|
|
Packit Service |
6dc5fa |
memset(bp->bitarray + size, 0, new_size - size);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
bmap->end = new_end;
|
|
Packit Service |
6dc5fa |
bmap->real_end = new_real_end;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
blk64_t bitno = (blk64_t) arg;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
blk64_t bitno = (blk64_t) arg;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
blk64_t bitno = (blk64_t) arg;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
|
|
Packit Service |
6dc5fa |
unsigned int num)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
blk64_t bitno = (blk64_t) arg;
|
|
Packit Service |
6dc5fa |
unsigned int i;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
for (i = 0; i < num; i++)
|
|
Packit Service |
6dc5fa |
ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
|
|
Packit Service |
6dc5fa |
unsigned int num)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
blk64_t bitno = (blk64_t) arg;
|
|
Packit Service |
6dc5fa |
unsigned int i;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
for (i = 0; i < num; i++)
|
|
Packit Service |
6dc5fa |
ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
|
|
Packit Service |
6dc5fa |
__u64 start, unsigned int len)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
__u64 start_byte, len_byte = len >> 3;
|
|
Packit Service |
6dc5fa |
unsigned int start_bit, len_bit = len % 8;
|
|
Packit Service |
6dc5fa |
unsigned int first_bit = 0;
|
|
Packit Service |
6dc5fa |
unsigned int last_bit = 0;
|
|
Packit Service |
6dc5fa |
int mark_count = 0;
|
|
Packit Service |
6dc5fa |
int mark_bit = 0;
|
|
Packit Service |
6dc5fa |
int i;
|
|
Packit Service |
6dc5fa |
const char *ADDR;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
ADDR = bp->bitarray;
|
|
Packit Service |
6dc5fa |
start -= bitmap->start;
|
|
Packit Service |
6dc5fa |
start_byte = start >> 3;
|
|
Packit Service |
6dc5fa |
start_bit = start % 8;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (start_bit != 0) {
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* The compared start block number or start inode number
|
|
Packit Service |
6dc5fa |
* is not the first bit in a byte.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
mark_count = 8 - start_bit;
|
|
Packit Service |
6dc5fa |
if (len < 8 - start_bit) {
|
|
Packit Service |
6dc5fa |
mark_count = (int)len;
|
|
Packit Service |
6dc5fa |
mark_bit = len + start_bit - 1;
|
|
Packit Service |
6dc5fa |
} else
|
|
Packit Service |
6dc5fa |
mark_bit = 7;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
for (i = mark_count; i > 0; i--, mark_bit--)
|
|
Packit Service |
6dc5fa |
first_bit |= 1 << mark_bit;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* Compare blocks or inodes in the first byte.
|
|
Packit Service |
6dc5fa |
* If there is any marked bit, this function returns 0.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
if (first_bit & ADDR[start_byte])
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
else if (len <= 8 - start_bit)
|
|
Packit Service |
6dc5fa |
return 1;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
start_byte++;
|
|
Packit Service |
6dc5fa |
len_bit = (len - mark_count) % 8;
|
|
Packit Service |
6dc5fa |
len_byte = (len - mark_count) >> 3;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* The compared start block number or start inode number is
|
|
Packit Service |
6dc5fa |
* the first bit in a byte.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
if (len_bit != 0) {
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* The compared end block number or end inode number is
|
|
Packit Service |
6dc5fa |
* not the last bit in a byte.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
|
|
Packit Service |
6dc5fa |
last_bit |= 1 << mark_bit;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/*
|
|
Packit Service |
6dc5fa |
* Compare blocks or inodes in the last byte.
|
|
Packit Service |
6dc5fa |
* If there is any marked bit, this function returns 0.
|
|
Packit Service |
6dc5fa |
*/
|
|
Packit Service |
6dc5fa |
if (last_bit & ADDR[start_byte + len_byte])
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
else if (len_byte == 0)
|
|
Packit Service |
6dc5fa |
return 1;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* Check whether all bytes are 0 */
|
|
Packit Service |
6dc5fa |
return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap,
|
|
Packit Service |
6dc5fa |
__u64 start, size_t num, void *in)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap,
|
|
Packit Service |
6dc5fa |
__u64 start, size_t num, void *out)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
76ee5c |
static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
memset(bp->bitarray, 0,
|
|
Packit Service |
6dc5fa |
(size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
#ifdef ENABLE_BMAP_STATS
|
|
Packit Service |
76ee5c |
static void ba_print_stats(ext2fs_generic_bitmap bitmap)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
fprintf(stderr, "%16llu Bytes used by bitarray\n",
|
|
Packit Service |
6dc5fa |
((bitmap->real_end - bitmap->start) >> 3) + 1 +
|
|
Packit Service |
6dc5fa |
sizeof(struct ext2fs_ba_private_struct));
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
#else
|
|
Packit Service |
76ee5c |
static void ba_print_stats(ext2fs_generic_bitmap bitmap EXT2FS_ATTR((unused)))
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
#endif
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* Find the first zero bit between start and end, inclusive. */
|
|
Packit Service |
76ee5c |
static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
|
|
Packit Service |
6dc5fa |
__u64 start, __u64 end, __u64 *out)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
|
|
Packit Service |
6dc5fa |
unsigned long bitpos = start - bitmap->start;
|
|
Packit Service |
6dc5fa |
unsigned long count = end - start + 1;
|
|
Packit Service |
6dc5fa |
int byte_found = 0; /* whether a != 0xff byte has been found */
|
|
Packit Service |
6dc5fa |
const unsigned char *pos;
|
|
Packit Service |
6dc5fa |
unsigned long max_loop_count, i;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* scan bits until we hit a byte boundary */
|
|
Packit Service |
6dc5fa |
while ((bitpos & 0x7) != 0 && count > 0) {
|
|
Packit Service |
6dc5fa |
if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
|
|
Packit Service |
6dc5fa |
*out = bitpos + bitmap->start;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
bitpos++;
|
|
Packit Service |
6dc5fa |
count--;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (!count)
|
|
Packit Service |
6dc5fa |
return ENOENT;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
|
|
Packit Service |
6dc5fa |
/* scan bytes until 8-byte (64-bit) aligned */
|
|
Packit Service |
6dc5fa |
while (count >= 8 && (((uintptr_t)pos) & 0x07)) {
|
|
Packit Service |
6dc5fa |
if (*pos != 0xff) {
|
|
Packit Service |
6dc5fa |
byte_found = 1;
|
|
Packit Service |
6dc5fa |
break;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
pos++;
|
|
Packit Service |
6dc5fa |
count -= 8;
|
|
Packit Service |
6dc5fa |
bitpos += 8;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (!byte_found) {
|
|
Packit Service |
6dc5fa |
max_loop_count = count >> 6; /* 8-byte blocks */
|
|
Packit Service |
6dc5fa |
i = max_loop_count;
|
|
Packit Service |
6dc5fa |
while (i) {
|
|
Packit Service |
6dc5fa |
if (*((const __u64 *)pos) != ((__u64)-1))
|
|
Packit Service |
6dc5fa |
break;
|
|
Packit Service |
6dc5fa |
pos += 8;
|
|
Packit Service |
6dc5fa |
i--;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
count -= 64 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
bitpos += 64 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
max_loop_count = count >> 3;
|
|
Packit Service |
6dc5fa |
i = max_loop_count;
|
|
Packit Service |
6dc5fa |
while (i) {
|
|
Packit Service |
6dc5fa |
if (*pos != 0xff) {
|
|
Packit Service |
6dc5fa |
byte_found = 1;
|
|
Packit Service |
6dc5fa |
break;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
pos++;
|
|
Packit Service |
6dc5fa |
i--;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
count -= 8 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
bitpos += 8 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* Here either count < 8 or byte_found == 1. */
|
|
Packit Service |
6dc5fa |
while (count-- > 0) {
|
|
Packit Service |
6dc5fa |
if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
|
|
Packit Service |
6dc5fa |
*out = bitpos + bitmap->start;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
bitpos++;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return ENOENT;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* Find the first one bit between start and end, inclusive. */
|
|
Packit Service |
76ee5c |
static errcode_t ba_find_first_set(ext2fs_generic_bitmap bitmap,
|
|
Packit Service |
6dc5fa |
__u64 start, __u64 end, __u64 *out)
|
|
Packit Service |
6dc5fa |
{
|
|
Packit Service |
6dc5fa |
ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
|
|
Packit Service |
6dc5fa |
unsigned long bitpos = start - bitmap->start;
|
|
Packit Service |
6dc5fa |
unsigned long count = end - start + 1;
|
|
Packit Service |
6dc5fa |
int byte_found = 0; /* whether a != 0xff byte has been found */
|
|
Packit Service |
6dc5fa |
const unsigned char *pos;
|
|
Packit Service |
6dc5fa |
unsigned long max_loop_count, i;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* scan bits until we hit a byte boundary */
|
|
Packit Service |
6dc5fa |
while ((bitpos & 0x7) != 0 && count > 0) {
|
|
Packit Service |
6dc5fa |
if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
|
|
Packit Service |
6dc5fa |
*out = bitpos + bitmap->start;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
bitpos++;
|
|
Packit Service |
6dc5fa |
count--;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (!count)
|
|
Packit Service |
6dc5fa |
return ENOENT;
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
|
|
Packit Service |
6dc5fa |
/* scan bytes until 8-byte (64-bit) aligned */
|
|
Packit Service |
6dc5fa |
while (count >= 8 && (((uintptr_t)pos) & 0x07)) {
|
|
Packit Service |
6dc5fa |
if (*pos != 0) {
|
|
Packit Service |
6dc5fa |
byte_found = 1;
|
|
Packit Service |
6dc5fa |
break;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
pos++;
|
|
Packit Service |
6dc5fa |
count -= 8;
|
|
Packit Service |
6dc5fa |
bitpos += 8;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
if (!byte_found) {
|
|
Packit Service |
6dc5fa |
max_loop_count = count >> 6; /* 8-byte blocks */
|
|
Packit Service |
6dc5fa |
i = max_loop_count;
|
|
Packit Service |
6dc5fa |
while (i) {
|
|
Packit Service |
6dc5fa |
if (*((const __u64 *)pos) != 0)
|
|
Packit Service |
6dc5fa |
break;
|
|
Packit Service |
6dc5fa |
pos += 8;
|
|
Packit Service |
6dc5fa |
i--;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
count -= 64 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
bitpos += 64 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
max_loop_count = count >> 3;
|
|
Packit Service |
6dc5fa |
i = max_loop_count;
|
|
Packit Service |
6dc5fa |
while (i) {
|
|
Packit Service |
6dc5fa |
if (*pos != 0) {
|
|
Packit Service |
6dc5fa |
byte_found = 1;
|
|
Packit Service |
6dc5fa |
break;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
pos++;
|
|
Packit Service |
6dc5fa |
i--;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
count -= 8 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
bitpos += 8 * (max_loop_count - i);
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
/* Here either count < 8 or byte_found == 1. */
|
|
Packit Service |
6dc5fa |
while (count-- > 0) {
|
|
Packit Service |
6dc5fa |
if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
|
|
Packit Service |
6dc5fa |
*out = bitpos + bitmap->start;
|
|
Packit Service |
6dc5fa |
return 0;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
bitpos++;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
return ENOENT;
|
|
Packit Service |
6dc5fa |
}
|
|
Packit Service |
6dc5fa |
|
|
Packit Service |
6dc5fa |
struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
|
|
Packit Service |
6dc5fa |
.type = EXT2FS_BMAP64_BITARRAY,
|
|
Packit Service |
6dc5fa |
.new_bmap = ba_new_bmap,
|
|
Packit Service |
6dc5fa |
.free_bmap = ba_free_bmap,
|
|
Packit Service |
6dc5fa |
.copy_bmap = ba_copy_bmap,
|
|
Packit Service |
6dc5fa |
.resize_bmap = ba_resize_bmap,
|
|
Packit Service |
6dc5fa |
.mark_bmap = ba_mark_bmap,
|
|
Packit Service |
6dc5fa |
.unmark_bmap = ba_unmark_bmap,
|
|
Packit Service |
6dc5fa |
.test_bmap = ba_test_bmap,
|
|
Packit Service |
6dc5fa |
.test_clear_bmap_extent = ba_test_clear_bmap_extent,
|
|
Packit Service |
6dc5fa |
.mark_bmap_extent = ba_mark_bmap_extent,
|
|
Packit Service |
6dc5fa |
.unmark_bmap_extent = ba_unmark_bmap_extent,
|
|
Packit Service |
6dc5fa |
.set_bmap_range = ba_set_bmap_range,
|
|
Packit Service |
6dc5fa |
.get_bmap_range = ba_get_bmap_range,
|
|
Packit Service |
6dc5fa |
.clear_bmap = ba_clear_bmap,
|
|
Packit Service |
6dc5fa |
.print_stats = ba_print_stats,
|
|
Packit Service |
6dc5fa |
.find_first_zero = ba_find_first_zero,
|
|
Packit Service |
6dc5fa |
.find_first_set = ba_find_first_set
|
|
Packit Service |
6dc5fa |
};
|