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