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
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 /*
42 * Used by previously inlined function, so we have to export this and
43 * not change the function signature
44 */
ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,int code,unsigned long arg)45 void 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
check_magic(ext2fs_generic_bitmap bitmap)57 static 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
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)66 errcode_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 /* Round up to allow for the BT x86 instruction */
107 size = (size + 7) & ~3;
108 retval = ext2fs_get_mem(size, &bitmap->bitmap);
109 if (retval) {
110 ext2fs_free_mem(&bitmap->description);
111 ext2fs_free_mem(&bitmap);
112 return retval;
113 }
114
115 if (init_map)
116 memcpy(bitmap->bitmap, init_map, size);
117 else
118 memset(bitmap->bitmap, 0, size);
119 *ret = bitmap;
120 return 0;
121 }
122
ext2fs_allocate_generic_bitmap(__u32 start,__u32 end,__u32 real_end,const char * descr,ext2fs_generic_bitmap * ret)123 errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
124 __u32 end,
125 __u32 real_end,
126 const char *descr,
127 ext2fs_generic_bitmap *ret)
128 {
129 return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
130 start, end, real_end, descr, 0, ret);
131 }
132
ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,ext2fs_generic_bitmap * dest)133 errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,
134 ext2fs_generic_bitmap *dest)
135 {
136 return (ext2fs_make_generic_bitmap(src->magic, src->fs,
137 src->start, src->end,
138 src->real_end,
139 src->description, src->bitmap,
140 dest));
141 }
142
ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)143 void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)
144 {
145 if (check_magic(bitmap))
146 return;
147
148 bitmap->magic = 0;
149 if (bitmap->description) {
150 ext2fs_free_mem(&bitmap->description);
151 bitmap->description = 0;
152 }
153 if (bitmap->bitmap) {
154 ext2fs_free_mem(&bitmap->bitmap);
155 bitmap->bitmap = 0;
156 }
157 ext2fs_free_mem(&bitmap);
158 }
159
ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,blk_t bitno)160 int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
161 blk_t bitno)
162 {
163 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
164 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
165 return 0;
166 }
167 return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
168 }
169
ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,__u32 bitno)170 int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
171 __u32 bitno)
172 {
173 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
174 ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
175 return 0;
176 }
177 return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
178 }
179
ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,blk_t bitno)180 int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
181 blk_t bitno)
182 {
183 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
184 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
185 return 0;
186 }
187 return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
188 }
189
ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)190 __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
191 {
192 return bitmap->start;
193 }
194
ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)195 __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
196 {
197 return bitmap->end;
198 }
199
ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)200 void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
201 {
202 if (check_magic(bitmap))
203 return;
204
205 memset(bitmap->bitmap, 0,
206 (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
207 }
208
ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,errcode_t magic,errcode_t neq,ext2_ino_t end,ext2_ino_t * oend)209 errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,
210 errcode_t magic, errcode_t neq,
211 ext2_ino_t end, ext2_ino_t *oend)
212 {
213 EXT2_CHECK_MAGIC(bitmap, magic);
214
215 if (end > bitmap->real_end)
216 return neq;
217 if (oend)
218 *oend = bitmap->end;
219 bitmap->end = end;
220 return 0;
221 }
222
ext2fs_resize_generic_bitmap(errcode_t magic,__u32 new_end,__u32 new_real_end,ext2fs_generic_bitmap bmap)223 errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
224 __u32 new_end, __u32 new_real_end,
225 ext2fs_generic_bitmap bmap)
226 {
227 errcode_t retval;
228 size_t size, new_size;
229 __u32 bitno;
230
231 if (!bmap || (bmap->magic != magic))
232 return magic;
233
234 /*
235 * If we're expanding the bitmap, make sure all of the new
236 * parts of the bitmap are zero.
237 */
238 if (new_end > bmap->end) {
239 bitno = bmap->real_end;
240 if (bitno > new_end)
241 bitno = new_end;
242 for (; bitno > bmap->end; bitno--)
243 ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
244 }
245 if (new_real_end == bmap->real_end) {
246 bmap->end = new_end;
247 return 0;
248 }
249
250 size = ((bmap->real_end - bmap->start) / 8) + 1;
251 new_size = ((new_real_end - bmap->start) / 8) + 1;
252
253 if (size != new_size) {
254 retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
255 if (retval)
256 return retval;
257 }
258 if (new_size > size)
259 memset(bmap->bitmap + size, 0, new_size - size);
260
261 bmap->end = new_end;
262 bmap->real_end = new_real_end;
263 return 0;
264 }
265
ext2fs_compare_generic_bitmap(errcode_t magic,errcode_t neq,ext2fs_generic_bitmap bm1,ext2fs_generic_bitmap bm2)266 errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
267 ext2fs_generic_bitmap bm1,
268 ext2fs_generic_bitmap bm2)
269 {
270 blk_t i;
271
272 if (!bm1 || bm1->magic != magic)
273 return magic;
274 if (!bm2 || bm2->magic != magic)
275 return magic;
276
277 if ((bm1->start != bm2->start) ||
278 (bm1->end != bm2->end) ||
279 (memcmp(bm1->bitmap, bm2->bitmap,
280 (size_t) (bm1->end - bm1->start)/8)))
281 return neq;
282
283 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
284 if (ext2fs_fast_test_block_bitmap(bm1, i) !=
285 ext2fs_fast_test_block_bitmap(bm2, i))
286 return neq;
287
288 return 0;
289 }
290
ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)291 void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)
292 {
293 __u32 i, j;
294
295 /* Protect loop from wrap-around if map->real_end is maxed */
296 for (i=map->end+1, j = i - map->start;
297 i <= map->real_end && i > map->end;
298 i++, j++)
299 ext2fs_set_bit(j, map->bitmap);
300 }
301
ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap,errcode_t magic,__u32 start,__u32 num,void * out)302 errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap,
303 errcode_t magic,
304 __u32 start, __u32 num,
305 void *out)
306 {
307 if (!bmap || (bmap->magic != magic))
308 return magic;
309
310 if ((start < bmap->start) || (start+num-1 > bmap->real_end))
311 return EXT2_ET_INVALID_ARGUMENT;
312
313 memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3);
314 return 0;
315 }
316
ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,errcode_t magic,__u32 start,__u32 num,void * in)317 errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
318 errcode_t magic,
319 __u32 start, __u32 num,
320 void *in)
321 {
322 if (!bmap || (bmap->magic != magic))
323 return magic;
324
325 if ((start < bmap->start) || (start+num-1 > bmap->real_end))
326 return EXT2_ET_INVALID_ARGUMENT;
327
328 memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3);
329 return 0;
330 }
331
332 /*
333 * Compare @mem to zero buffer by 256 bytes.
334 * Return 1 if @mem is zeroed memory, otherwise return 0.
335 */
mem_is_zero(const char * mem,size_t len)336 static int mem_is_zero(const char *mem, size_t len)
337 {
338 static const char zero_buf[256];
339
340 while (len >= sizeof(zero_buf)) {
341 if (memcmp(mem, zero_buf, sizeof(zero_buf)))
342 return 0;
343 len -= sizeof(zero_buf);
344 mem += sizeof(zero_buf);
345 }
346 /* Deal with leftover bytes. */
347 if (len)
348 return !memcmp(mem, zero_buf, len);
349 return 1;
350 }
351
352 /*
353 * Return true if all of the bits in a specified range are clear
354 */
ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,unsigned int start,unsigned int len)355 static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,
356 unsigned int start,
357 unsigned int len)
358 {
359 size_t start_byte, len_byte = len >> 3;
360 unsigned int start_bit, len_bit = len % 8;
361 int first_bit = 0;
362 int last_bit = 0;
363 int mark_count = 0;
364 int mark_bit = 0;
365 int i;
366 const char *ADDR = bitmap->bitmap;
367
368 start -= bitmap->start;
369 start_byte = start >> 3;
370 start_bit = start % 8;
371
372 if (start_bit != 0) {
373 /*
374 * The compared start block number or start inode number
375 * is not the first bit in a byte.
376 */
377 mark_count = 8 - start_bit;
378 if (len < 8 - start_bit) {
379 mark_count = (int)len;
380 mark_bit = len + start_bit - 1;
381 } else
382 mark_bit = 7;
383
384 for (i = mark_count; i > 0; i--, mark_bit--)
385 first_bit |= 1 << mark_bit;
386
387 /*
388 * Compare blocks or inodes in the first byte.
389 * If there is any marked bit, this function returns 0.
390 */
391 if (first_bit & ADDR[start_byte])
392 return 0;
393 else if (len <= 8 - start_bit)
394 return 1;
395
396 start_byte++;
397 len_bit = (len - mark_count) % 8;
398 len_byte = (len - mark_count) >> 3;
399 }
400
401 /*
402 * The compared start block number or start inode number is
403 * the first bit in a byte.
404 */
405 if (len_bit != 0) {
406 /*
407 * The compared end block number or end inode number is
408 * not the last bit in a byte.
409 */
410 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
411 last_bit |= 1 << mark_bit;
412
413 /*
414 * Compare blocks or inodes in the last byte.
415 * If there is any marked bit, this function returns 0.
416 */
417 if (last_bit & ADDR[start_byte + len_byte])
418 return 0;
419 else if (len_byte == 0)
420 return 1;
421 }
422
423 /* Check whether all bytes are 0 */
424 return mem_is_zero(ADDR + start_byte, len_byte);
425 }
426
ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,blk_t block,int num)427 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
428 blk_t block, int num)
429 {
430 EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP);
431 if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) {
432 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
433 block, bitmap->description);
434 return 0;
435 }
436 return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
437 bitmap, block, num);
438 }
439
ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap,ino_t inode,int num)440 int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap,
441 ino_t inode, int num)
442 {
443 EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP);
444 if ((inode < bitmap->start) || (inode+num-1 > bitmap->real_end)) {
445 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
446 inode, bitmap->description);
447 return 0;
448 }
449 return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
450 bitmap, inode, num);
451 }
452
ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,blk_t block,int num)453 void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
454 blk_t block, int num)
455 {
456 int i;
457
458 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
459 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
460 bitmap->description);
461 return;
462 }
463 for (i=0; i < num; i++)
464 ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
465 }
466
ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,blk_t block,int num)467 void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
468 blk_t block, int num)
469 {
470 int i;
471
472 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
473 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
474 bitmap->description);
475 return;
476 }
477 for (i=0; i < num; i++)
478 ext2fs_fast_clear_bit(block + i - bitmap->start,
479 bitmap->bitmap);
480 }
481