gen_bitmap.c revision efc6f628e15de95bcd13e4f0ee223cb42115d520
1/* 2 * gen_bitmap.c --- Generic (32-bit) bitmap routines 3 * 4 * Copyright (C) 2001 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 */ 11 12 13#include <stdio.h> 14#include <string.h> 15#if HAVE_UNISTD_H 16#include <unistd.h> 17#endif 18#include <fcntl.h> 19#include <time.h> 20#if HAVE_SYS_STAT_H 21#include <sys/stat.h> 22#endif 23#if HAVE_SYS_TYPES_H 24#include <sys/types.h> 25#endif 26 27#include "ext2_fs.h" 28#include "ext2fs.h" 29 30struct ext2fs_struct_generic_bitmap { 31 errcode_t magic; 32 ext2_filsys fs; 33 __u32 start, end; 34 __u32 real_end; 35 char * description; 36 char * bitmap; 37 errcode_t base_error_code; 38 __u32 reserved[7]; 39}; 40 41/* 42 * Used by previously inlined function, so we have to export this and 43 * not change the function signature 44 */ 45void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap, 46 int code, unsigned long arg) 47{ 48#ifndef OMIT_COM_ERR 49 if (bitmap->description) 50 com_err(0, bitmap->base_error_code+code, 51 "#%lu for %s", arg, bitmap->description); 52 else 53 com_err(0, bitmap->base_error_code + code, "#%lu", arg); 54#endif 55} 56 57static errcode_t check_magic(ext2fs_generic_bitmap bitmap) 58{ 59 if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || 60 (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) || 61 (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP))) 62 return EXT2_ET_MAGIC_GENERIC_BITMAP; 63 return 0; 64} 65 66errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs, 67 __u32 start, __u32 end, __u32 real_end, 68 const char *descr, char *init_map, 69 ext2fs_generic_bitmap *ret) 70{ 71 ext2fs_generic_bitmap bitmap; 72 errcode_t retval; 73 size_t size; 74 75 retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap), 76 &bitmap); 77 if (retval) 78 return retval; 79 80 bitmap->magic = magic; 81 bitmap->fs = fs; 82 bitmap->start = start; 83 bitmap->end = end; 84 bitmap->real_end = real_end; 85 switch (magic) { 86 case EXT2_ET_MAGIC_INODE_BITMAP: 87 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK; 88 break; 89 case EXT2_ET_MAGIC_BLOCK_BITMAP: 90 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK; 91 break; 92 default: 93 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK; 94 } 95 if (descr) { 96 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description); 97 if (retval) { 98 ext2fs_free_mem(&bitmap); 99 return retval; 100 } 101 strcpy(bitmap->description, descr); 102 } else 103 bitmap->description = 0; 104 105 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); 106 retval = ext2fs_get_mem(size, &bitmap->bitmap); 107 if (retval) { 108 ext2fs_free_mem(&bitmap->description); 109 ext2fs_free_mem(&bitmap); 110 return retval; 111 } 112 113 if (init_map) 114 memcpy(bitmap->bitmap, init_map, size); 115 else 116 memset(bitmap->bitmap, 0, size); 117 *ret = bitmap; 118 return 0; 119} 120 121errcode_t ext2fs_allocate_generic_bitmap(__u32 start, 122 __u32 end, 123 __u32 real_end, 124 const char *descr, 125 ext2fs_generic_bitmap *ret) 126{ 127 return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0, 128 start, end, real_end, descr, 0, ret); 129} 130 131errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src, 132 ext2fs_generic_bitmap *dest) 133{ 134 return (ext2fs_make_generic_bitmap(src->magic, src->fs, 135 src->start, src->end, 136 src->real_end, 137 src->description, src->bitmap, 138 dest)); 139} 140 141void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap) 142{ 143 if (check_magic(bitmap)) 144 return; 145 146 bitmap->magic = 0; 147 if (bitmap->description) { 148 ext2fs_free_mem(&bitmap->description); 149 bitmap->description = 0; 150 } 151 if (bitmap->bitmap) { 152 ext2fs_free_mem(&bitmap->bitmap); 153 bitmap->bitmap = 0; 154 } 155 ext2fs_free_mem(&bitmap); 156} 157 158int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap, 159 blk_t bitno) 160{ 161 if ((bitno < bitmap->start) || (bitno > bitmap->end)) { 162 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno); 163 return 0; 164 } 165 return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap); 166} 167 168int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap, 169 __u32 bitno) 170{ 171 if ((bitno < bitmap->start) || (bitno > bitmap->end)) { 172 ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno); 173 return 0; 174 } 175 return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap); 176} 177 178int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap, 179 blk_t bitno) 180{ 181 if ((bitno < bitmap->start) || (bitno > bitmap->end)) { 182 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno); 183 return 0; 184 } 185 return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap); 186} 187 188__u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap) 189{ 190 return bitmap->start; 191} 192 193__u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap) 194{ 195 return bitmap->end; 196} 197 198void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap) 199{ 200 if (check_magic(bitmap)) 201 return; 202 203 memset(bitmap->bitmap, 0, 204 (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); 205} 206 207errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap, 208 errcode_t magic, errcode_t neq, 209 ext2_ino_t end, ext2_ino_t *oend) 210{ 211 EXT2_CHECK_MAGIC(bitmap, magic); 212 213 if (end > bitmap->real_end) 214 return neq; 215 if (oend) 216 *oend = bitmap->end; 217 bitmap->end = end; 218 return 0; 219} 220 221errcode_t ext2fs_resize_generic_bitmap(errcode_t magic, 222 __u32 new_end, __u32 new_real_end, 223 ext2fs_generic_bitmap bmap) 224{ 225 errcode_t retval; 226 size_t size, new_size; 227 __u32 bitno; 228 229 if (!bmap || (bmap->magic != magic)) 230 return magic; 231 232 /* 233 * If we're expanding the bitmap, make sure all of the new 234 * parts of the bitmap are zero. 235 */ 236 if (new_end > bmap->end) { 237 bitno = bmap->real_end; 238 if (bitno > new_end) 239 bitno = new_end; 240 for (; bitno > bmap->end; bitno--) 241 ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap); 242 } 243 if (new_real_end == bmap->real_end) { 244 bmap->end = new_end; 245 return 0; 246 } 247 248 size = ((bmap->real_end - bmap->start) / 8) + 1; 249 new_size = ((new_real_end - bmap->start) / 8) + 1; 250 251 if (size != new_size) { 252 retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap); 253 if (retval) 254 return retval; 255 } 256 if (new_size > size) 257 memset(bmap->bitmap + size, 0, new_size - size); 258 259 bmap->end = new_end; 260 bmap->real_end = new_real_end; 261 return 0; 262} 263 264errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq, 265 ext2fs_generic_bitmap bm1, 266 ext2fs_generic_bitmap bm2) 267{ 268 blk_t i; 269 270 if (!bm1 || bm1->magic != magic) 271 return magic; 272 if (!bm2 || bm2->magic != magic) 273 return magic; 274 275 if ((bm1->start != bm2->start) || 276 (bm1->end != bm2->end) || 277 (memcmp(bm1->bitmap, bm2->bitmap, 278 (size_t) (bm1->end - bm1->start)/8))) 279 return neq; 280 281 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++) 282 if (ext2fs_fast_test_block_bitmap(bm1, i) != 283 ext2fs_fast_test_block_bitmap(bm2, i)) 284 return neq; 285 286 return 0; 287} 288 289void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map) 290{ 291 __u32 i, j; 292 293 /* Protect loop from wrap-around if map->real_end is maxed */ 294 for (i=map->end+1, j = i - map->start; 295 i <= map->real_end && i > map->end; 296 i++, j++) 297 ext2fs_set_bit(j, map->bitmap); 298} 299 300errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap, 301 errcode_t magic, 302 __u32 start, __u32 num, 303 void *out) 304{ 305 if (!bmap || (bmap->magic != magic)) 306 return magic; 307 308 if ((start < bmap->start) || (start+num-1 > bmap->real_end)) 309 return EXT2_ET_INVALID_ARGUMENT; 310 311 memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3); 312 return 0; 313} 314 315errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap, 316 errcode_t magic, 317 __u32 start, __u32 num, 318 void *in) 319{ 320 if (!bmap || (bmap->magic != magic)) 321 return magic; 322 323 if ((start < bmap->start) || (start+num-1 > bmap->real_end)) 324 return EXT2_ET_INVALID_ARGUMENT; 325 326 memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3); 327 return 0; 328} 329 330int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap, 331 blk_t block, int num) 332{ 333 int i; 334 335 if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) { 336 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, 337 block, bitmap->description); 338 return 0; 339 } 340 for (i=0; i < num; i++) { 341 if (ext2fs_fast_test_block_bitmap(bitmap, block+i)) 342 return 0; 343 } 344 return 1; 345} 346 347void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap, 348 blk_t block, int num) 349{ 350 int i; 351 352 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) { 353 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block, 354 bitmap->description); 355 return; 356 } 357 for (i=0; i < num; i++) 358 ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap); 359} 360 361void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap, 362 blk_t block, int num) 363{ 364 int i; 365 366 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) { 367 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block, 368 bitmap->description); 369 return; 370 } 371 for (i=0; i < num; i++) 372 ext2fs_fast_clear_bit(block + i - bitmap->start, 373 bitmap->bitmap); 374} 375