Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 1 | /* |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 2 | * gen_bitmap.c --- Generic (32-bit) bitmap routines |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 3 | * |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 4 | * Copyright (C) 2001 Theodore Ts'o. |
| 5 | * |
| 6 | * %Begin-Header% |
Theodore Ts'o | 543547a | 2010-05-17 21:31:56 -0400 | [diff] [blame] | 7 | * This file may be redistributed under the terms of the GNU Library |
| 8 | * General Public License, version 2. |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 9 | * %End-Header% |
| 10 | */ |
| 11 | |
| 12 | |
Theodore Ts'o | d1154eb | 2011-09-18 17:34:37 -0400 | [diff] [blame] | 13 | #include "config.h" |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 14 | #include <stdio.h> |
| 15 | #include <string.h> |
| 16 | #if HAVE_UNISTD_H |
| 17 | #include <unistd.h> |
| 18 | #endif |
| 19 | #include <fcntl.h> |
| 20 | #include <time.h> |
| 21 | #if HAVE_SYS_STAT_H |
| 22 | #include <sys/stat.h> |
| 23 | #endif |
| 24 | #if HAVE_SYS_TYPES_H |
| 25 | #include <sys/types.h> |
| 26 | #endif |
| 27 | |
| 28 | #include "ext2_fs.h" |
Theodore Ts'o | 69365c6 | 2009-08-22 13:27:40 -0400 | [diff] [blame] | 29 | #include "ext2fsP.h" |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 30 | |
Theodore Ts'o | f1f115a | 2007-07-23 04:32:48 -0400 | [diff] [blame] | 31 | struct ext2fs_struct_generic_bitmap { |
| 32 | errcode_t magic; |
| 33 | ext2_filsys fs; |
| 34 | __u32 start, end; |
| 35 | __u32 real_end; |
| 36 | char * description; |
| 37 | char * bitmap; |
| 38 | errcode_t base_error_code; |
| 39 | __u32 reserved[7]; |
| 40 | }; |
| 41 | |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 42 | #define EXT2FS_IS_32_BITMAP(bmap) \ |
| 43 | (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || \ |
| 44 | ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP) || \ |
| 45 | ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP)) |
| 46 | |
| 47 | #define EXT2FS_IS_64_BITMAP(bmap) \ |
| 48 | (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP64) || \ |
| 49 | ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP64) || \ |
| 50 | ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP64)) |
| 51 | |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 52 | /* |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 53 | * Used by previously inlined function, so we have to export this and |
| 54 | * not change the function signature |
| 55 | */ |
| 56 | void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap, |
| 57 | int code, unsigned long arg) |
| 58 | { |
| 59 | #ifndef OMIT_COM_ERR |
| 60 | if (bitmap->description) |
| 61 | com_err(0, bitmap->base_error_code+code, |
| 62 | "#%lu for %s", arg, bitmap->description); |
| 63 | else |
| 64 | com_err(0, bitmap->base_error_code + code, "#%lu", arg); |
| 65 | #endif |
| 66 | } |
| 67 | |
| 68 | static errcode_t check_magic(ext2fs_generic_bitmap bitmap) |
| 69 | { |
| 70 | if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || |
| 71 | (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) || |
| 72 | (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP))) |
| 73 | return EXT2_ET_MAGIC_GENERIC_BITMAP; |
| 74 | return 0; |
| 75 | } |
| 76 | |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 77 | errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs, |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 78 | __u32 start, __u32 end, __u32 real_end, |
| 79 | const char *descr, char *init_map, |
| 80 | ext2fs_generic_bitmap *ret) |
| 81 | { |
| 82 | ext2fs_generic_bitmap bitmap; |
| 83 | errcode_t retval; |
| 84 | size_t size; |
| 85 | |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 86 | retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap), |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 87 | &bitmap); |
| 88 | if (retval) |
| 89 | return retval; |
| 90 | |
| 91 | bitmap->magic = magic; |
| 92 | bitmap->fs = fs; |
| 93 | bitmap->start = start; |
| 94 | bitmap->end = end; |
| 95 | bitmap->real_end = real_end; |
| 96 | switch (magic) { |
| 97 | case EXT2_ET_MAGIC_INODE_BITMAP: |
| 98 | bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK; |
| 99 | break; |
| 100 | case EXT2_ET_MAGIC_BLOCK_BITMAP: |
| 101 | bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK; |
| 102 | break; |
| 103 | default: |
| 104 | bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; |
| 105 | } |
| 106 | if (descr) { |
| 107 | retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); |
| 108 | if (retval) { |
| 109 | ext2fs_free_mem(&bitmap); |
| 110 | return retval; |
| 111 | } |
| 112 | strcpy(bitmap->description, descr); |
| 113 | } else |
| 114 | bitmap->description = 0; |
| 115 | |
| 116 | size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); |
Theodore Ts'o | 51e6459 | 2009-09-07 16:21:49 -0400 | [diff] [blame] | 117 | /* Round up to allow for the BT x86 instruction */ |
| 118 | size = (size + 7) & ~3; |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 119 | retval = ext2fs_get_mem(size, &bitmap->bitmap); |
| 120 | if (retval) { |
| 121 | ext2fs_free_mem(&bitmap->description); |
| 122 | ext2fs_free_mem(&bitmap); |
| 123 | return retval; |
| 124 | } |
| 125 | |
| 126 | if (init_map) |
| 127 | memcpy(bitmap->bitmap, init_map, size); |
| 128 | else |
| 129 | memset(bitmap->bitmap, 0, size); |
| 130 | *ret = bitmap; |
| 131 | return 0; |
| 132 | } |
| 133 | |
| 134 | errcode_t ext2fs_allocate_generic_bitmap(__u32 start, |
| 135 | __u32 end, |
| 136 | __u32 real_end, |
| 137 | const char *descr, |
| 138 | ext2fs_generic_bitmap *ret) |
| 139 | { |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 140 | return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0, |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 141 | start, end, real_end, descr, 0, ret); |
| 142 | } |
| 143 | |
| 144 | errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src, |
| 145 | ext2fs_generic_bitmap *dest) |
| 146 | { |
| 147 | return (ext2fs_make_generic_bitmap(src->magic, src->fs, |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 148 | src->start, src->end, |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 149 | src->real_end, |
| 150 | src->description, src->bitmap, |
| 151 | dest)); |
| 152 | } |
| 153 | |
| 154 | void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap) |
| 155 | { |
| 156 | if (check_magic(bitmap)) |
| 157 | return; |
| 158 | |
| 159 | bitmap->magic = 0; |
| 160 | if (bitmap->description) { |
| 161 | ext2fs_free_mem(&bitmap->description); |
| 162 | bitmap->description = 0; |
| 163 | } |
| 164 | if (bitmap->bitmap) { |
| 165 | ext2fs_free_mem(&bitmap->bitmap); |
| 166 | bitmap->bitmap = 0; |
| 167 | } |
| 168 | ext2fs_free_mem(&bitmap); |
| 169 | } |
| 170 | |
Theodore Ts'o | b15beaa | 2007-07-22 17:42:52 -0400 | [diff] [blame] | 171 | int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap, |
| 172 | blk_t bitno) |
| 173 | { |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 174 | if (!EXT2FS_IS_32_BITMAP(bitmap)) { |
| 175 | if (EXT2FS_IS_64_BITMAP(bitmap)) { |
| 176 | ext2fs_warn_bitmap32(bitmap, __func__); |
| 177 | return ext2fs_test_generic_bmap(bitmap, bitno); |
| 178 | } |
| 179 | #ifndef OMIT_COM_ERR |
| 180 | com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, |
| 181 | "test_bitmap(%lu)", (unsigned long) bitno); |
Namhyung Kim | beb4295 | 2010-12-20 10:07:10 -0500 | [diff] [blame] | 182 | #endif |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 183 | return 0; |
| 184 | } |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 185 | |
Theodore Ts'o | b15beaa | 2007-07-22 17:42:52 -0400 | [diff] [blame] | 186 | if ((bitno < bitmap->start) || (bitno > bitmap->end)) { |
| 187 | ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno); |
| 188 | return 0; |
| 189 | } |
| 190 | return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap); |
| 191 | } |
| 192 | |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 193 | int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap, |
| 194 | __u32 bitno) |
| 195 | { |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 196 | if (!EXT2FS_IS_32_BITMAP(bitmap)) { |
| 197 | if (EXT2FS_IS_64_BITMAP(bitmap)) { |
| 198 | ext2fs_warn_bitmap32(bitmap, __func__); |
| 199 | return ext2fs_mark_generic_bmap(bitmap, bitno); |
| 200 | } |
| 201 | #ifndef OMIT_COM_ERR |
| 202 | com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, |
| 203 | "mark_bitmap(%lu)", (unsigned long) bitno); |
Namhyung Kim | beb4295 | 2010-12-20 10:07:10 -0500 | [diff] [blame] | 204 | #endif |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 205 | return 0; |
| 206 | } |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 207 | |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 208 | if ((bitno < bitmap->start) || (bitno > bitmap->end)) { |
| 209 | ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno); |
| 210 | return 0; |
| 211 | } |
| 212 | return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap); |
| 213 | } |
| 214 | |
| 215 | int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap, |
| 216 | blk_t bitno) |
| 217 | { |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 218 | if (!EXT2FS_IS_32_BITMAP(bitmap)) { |
| 219 | if (EXT2FS_IS_64_BITMAP(bitmap)) { |
| 220 | ext2fs_warn_bitmap32(bitmap, __func__); |
Namhyung Kim | f57e64a | 2010-11-29 17:55:07 +0900 | [diff] [blame] | 221 | return ext2fs_unmark_generic_bmap(bitmap, bitno); |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 222 | } |
| 223 | #ifndef OMIT_COM_ERR |
| 224 | com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, |
| 225 | "mark_bitmap(%lu)", (unsigned long) bitno); |
Namhyung Kim | beb4295 | 2010-12-20 10:07:10 -0500 | [diff] [blame] | 226 | #endif |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 227 | return 0; |
| 228 | } |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 229 | |
Theodore Ts'o | 3034f62 | 2001-06-11 15:17:45 +0000 | [diff] [blame] | 230 | if ((bitno < bitmap->start) || (bitno > bitmap->end)) { |
| 231 | ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno); |
| 232 | return 0; |
| 233 | } |
| 234 | return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap); |
| 235 | } |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 236 | |
Theodore Ts'o | 271a375 | 2007-07-22 19:16:08 -0400 | [diff] [blame] | 237 | __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap) |
| 238 | { |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 239 | if (!EXT2FS_IS_32_BITMAP(bitmap)) { |
| 240 | if (EXT2FS_IS_64_BITMAP(bitmap)) { |
| 241 | ext2fs_warn_bitmap32(bitmap, __func__); |
| 242 | return ext2fs_get_generic_bmap_start(bitmap); |
| 243 | } |
| 244 | #ifndef OMIT_COM_ERR |
| 245 | com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, |
| 246 | "get_bitmap_start"); |
Namhyung Kim | beb4295 | 2010-12-20 10:07:10 -0500 | [diff] [blame] | 247 | #endif |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 248 | return 0; |
| 249 | } |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 250 | |
Theodore Ts'o | 271a375 | 2007-07-22 19:16:08 -0400 | [diff] [blame] | 251 | return bitmap->start; |
| 252 | } |
| 253 | |
| 254 | __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap) |
| 255 | { |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 256 | if (!EXT2FS_IS_32_BITMAP(bitmap)) { |
| 257 | if (EXT2FS_IS_64_BITMAP(bitmap)) { |
| 258 | ext2fs_warn_bitmap32(bitmap, __func__); |
| 259 | return ext2fs_get_generic_bmap_end(bitmap); |
| 260 | } |
| 261 | #ifndef OMIT_COM_ERR |
| 262 | com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, |
| 263 | "get_bitmap_end"); |
Namhyung Kim | beb4295 | 2010-12-20 10:07:10 -0500 | [diff] [blame] | 264 | #endif |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 265 | return 0; |
| 266 | } |
Theodore Ts'o | 271a375 | 2007-07-22 19:16:08 -0400 | [diff] [blame] | 267 | return bitmap->end; |
| 268 | } |
| 269 | |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 270 | void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap) |
| 271 | { |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 272 | if (!EXT2FS_IS_32_BITMAP(bitmap)) { |
| 273 | if (EXT2FS_IS_64_BITMAP(bitmap)) { |
| 274 | ext2fs_warn_bitmap32(bitmap, __func__); |
| 275 | ext2fs_clear_generic_bmap(bitmap); |
| 276 | return; |
| 277 | } |
| 278 | #ifndef OMIT_COM_ERR |
| 279 | com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP, |
| 280 | "clear_generic_bitmap"); |
Namhyung Kim | beb4295 | 2010-12-20 10:07:10 -0500 | [diff] [blame] | 281 | #endif |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 282 | return; |
Theodore Ts'o | c21cde9 | 2010-01-30 20:08:11 -0500 | [diff] [blame] | 283 | } |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 284 | |
| 285 | memset(bitmap->bitmap, 0, |
| 286 | (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); |
| 287 | } |
| 288 | |
| 289 | errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap, |
| 290 | errcode_t magic, errcode_t neq, |
| 291 | ext2_ino_t end, ext2_ino_t *oend) |
| 292 | { |
| 293 | EXT2_CHECK_MAGIC(bitmap, magic); |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 294 | |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 295 | if (end > bitmap->real_end) |
| 296 | return neq; |
| 297 | if (oend) |
| 298 | *oend = bitmap->end; |
| 299 | bitmap->end = end; |
| 300 | return 0; |
| 301 | } |
| 302 | |
Theodore Ts'o | 50448d3 | 2007-07-22 23:42:14 -0400 | [diff] [blame] | 303 | errcode_t ext2fs_resize_generic_bitmap(errcode_t magic, |
| 304 | __u32 new_end, __u32 new_real_end, |
| 305 | ext2fs_generic_bitmap bmap) |
| 306 | { |
| 307 | errcode_t retval; |
| 308 | size_t size, new_size; |
| 309 | __u32 bitno; |
| 310 | |
| 311 | if (!bmap || (bmap->magic != magic)) |
| 312 | return magic; |
| 313 | |
| 314 | /* |
| 315 | * If we're expanding the bitmap, make sure all of the new |
| 316 | * parts of the bitmap are zero. |
| 317 | */ |
| 318 | if (new_end > bmap->end) { |
| 319 | bitno = bmap->real_end; |
| 320 | if (bitno > new_end) |
| 321 | bitno = new_end; |
| 322 | for (; bitno > bmap->end; bitno--) |
| 323 | ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap); |
| 324 | } |
| 325 | if (new_real_end == bmap->real_end) { |
| 326 | bmap->end = new_end; |
| 327 | return 0; |
| 328 | } |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 329 | |
Theodore Ts'o | 50448d3 | 2007-07-22 23:42:14 -0400 | [diff] [blame] | 330 | size = ((bmap->real_end - bmap->start) / 8) + 1; |
| 331 | new_size = ((new_real_end - bmap->start) / 8) + 1; |
| 332 | |
| 333 | if (size != new_size) { |
| 334 | retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap); |
| 335 | if (retval) |
| 336 | return retval; |
| 337 | } |
| 338 | if (new_size > size) |
| 339 | memset(bmap->bitmap + size, 0, new_size - size); |
| 340 | |
| 341 | bmap->end = new_end; |
| 342 | bmap->real_end = new_real_end; |
| 343 | return 0; |
| 344 | } |
| 345 | |
| 346 | errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq, |
| 347 | ext2fs_generic_bitmap bm1, |
| 348 | ext2fs_generic_bitmap bm2) |
| 349 | { |
| 350 | blk_t i; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 351 | |
Theodore Ts'o | 50448d3 | 2007-07-22 23:42:14 -0400 | [diff] [blame] | 352 | if (!bm1 || bm1->magic != magic) |
| 353 | return magic; |
| 354 | if (!bm2 || bm2->magic != magic) |
| 355 | return magic; |
| 356 | |
| 357 | if ((bm1->start != bm2->start) || |
| 358 | (bm1->end != bm2->end) || |
| 359 | (memcmp(bm1->bitmap, bm2->bitmap, |
| 360 | (size_t) (bm1->end - bm1->start)/8))) |
| 361 | return neq; |
| 362 | |
| 363 | for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) |
| 364 | if (ext2fs_fast_test_block_bitmap(bm1, i) != |
| 365 | ext2fs_fast_test_block_bitmap(bm2, i)) |
| 366 | return neq; |
| 367 | |
| 368 | return 0; |
| 369 | } |
| 370 | |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 371 | void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map) |
| 372 | { |
| 373 | __u32 i, j; |
| 374 | |
| 375 | /* Protect loop from wrap-around if map->real_end is maxed */ |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 376 | for (i=map->end+1, j = i - map->start; |
| 377 | i <= map->real_end && i > map->end; |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 378 | i++, j++) |
| 379 | ext2fs_set_bit(j, map->bitmap); |
Theodore Ts'o | f1f115a | 2007-07-23 04:32:48 -0400 | [diff] [blame] | 380 | } |
| 381 | |
| 382 | errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap, |
| 383 | errcode_t magic, |
| 384 | __u32 start, __u32 num, |
| 385 | void *out) |
| 386 | { |
| 387 | if (!bmap || (bmap->magic != magic)) |
| 388 | return magic; |
| 389 | |
| 390 | if ((start < bmap->start) || (start+num-1 > bmap->real_end)) |
| 391 | return EXT2_ET_INVALID_ARGUMENT; |
| 392 | |
| 393 | memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3); |
| 394 | return 0; |
| 395 | } |
| 396 | |
| 397 | errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap, |
| 398 | errcode_t magic, |
| 399 | __u32 start, __u32 num, |
| 400 | void *in) |
| 401 | { |
| 402 | if (!bmap || (bmap->magic != magic)) |
| 403 | return magic; |
| 404 | |
| 405 | if ((start < bmap->start) || (start+num-1 > bmap->real_end)) |
| 406 | return EXT2_ET_INVALID_ARGUMENT; |
| 407 | |
| 408 | memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3); |
| 409 | return 0; |
| 410 | } |
Theodore Ts'o | a0553c9 | 2007-07-22 22:59:50 -0400 | [diff] [blame] | 411 | |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 412 | /* |
| 413 | * Compare @mem to zero buffer by 256 bytes. |
| 414 | * Return 1 if @mem is zeroed memory, otherwise return 0. |
| 415 | */ |
Theodore Ts'o | 69365c6 | 2009-08-22 13:27:40 -0400 | [diff] [blame] | 416 | int ext2fs_mem_is_zero(const char *mem, size_t len) |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 417 | { |
| 418 | static const char zero_buf[256]; |
| 419 | |
| 420 | while (len >= sizeof(zero_buf)) { |
| 421 | if (memcmp(mem, zero_buf, sizeof(zero_buf))) |
| 422 | return 0; |
| 423 | len -= sizeof(zero_buf); |
| 424 | mem += sizeof(zero_buf); |
| 425 | } |
| 426 | /* Deal with leftover bytes. */ |
| 427 | if (len) |
| 428 | return !memcmp(mem, zero_buf, len); |
| 429 | return 1; |
| 430 | } |
| 431 | |
| 432 | /* |
| 433 | * Return true if all of the bits in a specified range are clear |
| 434 | */ |
| 435 | static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap, |
| 436 | unsigned int start, |
| 437 | unsigned int len) |
| 438 | { |
| 439 | size_t start_byte, len_byte = len >> 3; |
Theodore Ts'o | 25c7e0c | 2009-07-12 01:13:06 -0400 | [diff] [blame] | 440 | unsigned int start_bit, len_bit = len % 8; |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 441 | int first_bit = 0; |
| 442 | int last_bit = 0; |
| 443 | int mark_count = 0; |
| 444 | int mark_bit = 0; |
| 445 | int i; |
| 446 | const char *ADDR = bitmap->bitmap; |
| 447 | |
| 448 | start -= bitmap->start; |
| 449 | start_byte = start >> 3; |
| 450 | start_bit = start % 8; |
| 451 | |
| 452 | if (start_bit != 0) { |
| 453 | /* |
| 454 | * The compared start block number or start inode number |
| 455 | * is not the first bit in a byte. |
| 456 | */ |
| 457 | mark_count = 8 - start_bit; |
| 458 | if (len < 8 - start_bit) { |
| 459 | mark_count = (int)len; |
| 460 | mark_bit = len + start_bit - 1; |
| 461 | } else |
| 462 | mark_bit = 7; |
| 463 | |
| 464 | for (i = mark_count; i > 0; i--, mark_bit--) |
| 465 | first_bit |= 1 << mark_bit; |
| 466 | |
| 467 | /* |
| 468 | * Compare blocks or inodes in the first byte. |
| 469 | * If there is any marked bit, this function returns 0. |
| 470 | */ |
| 471 | if (first_bit & ADDR[start_byte]) |
| 472 | return 0; |
| 473 | else if (len <= 8 - start_bit) |
| 474 | return 1; |
| 475 | |
| 476 | start_byte++; |
| 477 | len_bit = (len - mark_count) % 8; |
| 478 | len_byte = (len - mark_count) >> 3; |
| 479 | } |
| 480 | |
| 481 | /* |
| 482 | * The compared start block number or start inode number is |
| 483 | * the first bit in a byte. |
| 484 | */ |
| 485 | if (len_bit != 0) { |
| 486 | /* |
| 487 | * The compared end block number or end inode number is |
| 488 | * not the last bit in a byte. |
| 489 | */ |
| 490 | for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) |
| 491 | last_bit |= 1 << mark_bit; |
| 492 | |
| 493 | /* |
| 494 | * Compare blocks or inodes in the last byte. |
| 495 | * If there is any marked bit, this function returns 0. |
| 496 | */ |
| 497 | if (last_bit & ADDR[start_byte + len_byte]) |
| 498 | return 0; |
| 499 | else if (len_byte == 0) |
| 500 | return 1; |
| 501 | } |
| 502 | |
| 503 | /* Check whether all bytes are 0 */ |
Theodore Ts'o | 69365c6 | 2009-08-22 13:27:40 -0400 | [diff] [blame] | 504 | return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 505 | } |
| 506 | |
Theodore Ts'o | 664c332 | 2012-04-06 11:44:54 -0700 | [diff] [blame] | 507 | errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap, |
| 508 | __u32 start, __u32 end, |
| 509 | __u32 *out) |
| 510 | { |
| 511 | blk_t b; |
| 512 | |
| 513 | if (start < bitmap->start || end > bitmap->end || start > end) { |
| 514 | ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start); |
| 515 | return EINVAL; |
| 516 | } |
| 517 | |
| 518 | while (start <= end) { |
| 519 | b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap); |
| 520 | if (!b) { |
| 521 | *out = start; |
| 522 | return 0; |
| 523 | } |
| 524 | start++; |
| 525 | } |
| 526 | |
| 527 | return ENOENT; |
| 528 | } |
| 529 | |
| 530 | |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 531 | int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, |
| 532 | blk_t block, int num) |
| 533 | { |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 534 | EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP); |
Theodore Ts'o | f1f115a | 2007-07-23 04:32:48 -0400 | [diff] [blame] | 535 | if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) { |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 536 | ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, |
| 537 | block, bitmap->description); |
| 538 | return 0; |
| 539 | } |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 540 | return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap) |
| 541 | bitmap, block, num); |
| 542 | } |
| 543 | |
| 544 | int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap, |
| 545 | ino_t inode, int num) |
| 546 | { |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 547 | EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP); |
| 548 | if ((inode < bitmap->start) || (inode+num-1 > bitmap->real_end)) { |
| 549 | ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST, |
| 550 | inode, bitmap->description); |
| 551 | return 0; |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 552 | } |
Theodore Ts'o | ef1a526 | 2009-07-09 14:32:52 -0400 | [diff] [blame] | 553 | return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap) |
| 554 | bitmap, inode, num); |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 555 | } |
| 556 | |
| 557 | void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, |
| 558 | blk_t block, int num) |
| 559 | { |
| 560 | int i; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 561 | |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 562 | if ((block < bitmap->start) || (block+num-1 > bitmap->end)) { |
| 563 | ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, |
| 564 | bitmap->description); |
| 565 | return; |
| 566 | } |
| 567 | for (i=0; i < num; i++) |
| 568 | ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap); |
| 569 | } |
| 570 | |
| 571 | void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, |
| 572 | blk_t block, int num) |
| 573 | { |
| 574 | int i; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 575 | |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 576 | if ((block < bitmap->start) || (block+num-1 > bitmap->end)) { |
| 577 | ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, |
| 578 | bitmap->description); |
| 579 | return; |
| 580 | } |
| 581 | for (i=0; i < num; i++) |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 582 | ext2fs_fast_clear_bit(block + i - bitmap->start, |
Theodore Ts'o | 8df1827 | 2007-07-22 18:54:10 -0400 | [diff] [blame] | 583 | bitmap->bitmap); |
| 584 | } |
Theodore Ts'o | 664c332 | 2012-04-06 11:44:54 -0700 | [diff] [blame] | 585 | |