1 /*
2 * PROJECT: Mke2fs
3 * FILE: Bitmap.c
4 * PROGRAMMER: Matt Wu <mattwu@163.com>
5 * HOMEPAGE: http://ext2.yeah.net
6 */
7
8 /* INCLUDES **************************************************************/
9
10 #include "Mke2fs.h"
11 #include <debug.h>
12
13 /* DEFINITIONS ***********************************************************/
14
15 /* FUNCTIONS *************************************************************/
16
17
ext2_set_bit(int nr,void * addr)18 bool ext2_set_bit(int nr,void * addr)
19 {
20 int mask;
21 unsigned char *ADDR = (unsigned char *) addr;
22
23 ADDR += nr >> 3;
24 mask = 1 << (nr & 0x07);
25 *ADDR |= mask;
26
27 return true;
28 }
29
ext2_clear_bit(int nr,void * addr)30 bool ext2_clear_bit(int nr, void * addr)
31 {
32 int mask;
33 unsigned char *ADDR = (unsigned char *) addr;
34
35 ADDR += nr >> 3;
36 mask = 1 << (nr & 0x07);
37 *ADDR &= ~mask;
38 return true;
39 }
40
ext2_test_bit(int nr,void * addr)41 bool ext2_test_bit(int nr, void * addr)
42 {
43 int mask;
44 const unsigned char *ADDR = (const unsigned char *) addr;
45
46 ADDR += nr >> 3;
47 mask = 1 << (nr & 0x07);
48
49 return ((mask & *ADDR) != 0);
50 }
51
ext2_mark_bitmap(PEXT2_BITMAP bitmap,ULONG bitno)52 bool ext2_mark_bitmap(PEXT2_BITMAP bitmap, ULONG bitno)
53 {
54 if ((bitno < bitmap->start) || (bitno > bitmap->end))
55 {
56 return false;
57 }
58
59 return ext2_set_bit(bitno - bitmap->start, bitmap->bitmap);
60 }
61
ext2_unmark_bitmap(PEXT2_BITMAP bitmap,ULONG bitno)62 bool ext2_unmark_bitmap(PEXT2_BITMAP bitmap, ULONG bitno)
63 {
64 if ((bitno < bitmap->start) || (bitno > bitmap->end))
65 {
66 return false;
67 }
68
69 return ext2_clear_bit(bitno - bitmap->start, bitmap->bitmap);
70 }
71
72
ext2_test_block_bitmap(PEXT2_BLOCK_BITMAP bitmap,ULONG block)73 bool ext2_test_block_bitmap(PEXT2_BLOCK_BITMAP bitmap,
74 ULONG block)
75 {
76 return ext2_test_bit(block - bitmap->start, bitmap->bitmap);
77 }
78
79
ext2_test_block_bitmap_range(PEXT2_BLOCK_BITMAP bitmap,ULONG block,int num)80 bool ext2_test_block_bitmap_range(PEXT2_BLOCK_BITMAP bitmap,
81 ULONG block, int num)
82 {
83 int i;
84
85 for (i=0; i < num; i++)
86 {
87 if (ext2_test_block_bitmap(bitmap, block+i))
88 return false;
89 }
90 return true;
91 }
92
ext2_test_inode_bitmap(PEXT2_BLOCK_BITMAP bitmap,ULONG inode)93 bool ext2_test_inode_bitmap(PEXT2_BLOCK_BITMAP bitmap,
94 ULONG inode)
95 {
96 return ext2_test_bit(inode - bitmap->start, bitmap->bitmap);
97 }
98
99
ext2_allocate_block_bitmap(PEXT2_FILESYS Ext2Sys)100 bool ext2_allocate_block_bitmap(PEXT2_FILESYS Ext2Sys)
101 {
102 ULONG size = 0;
103
104 PEXT2_SUPER_BLOCK pExt2Sb = Ext2Sys->ext2_sb;
105 Ext2Sys->block_map = (PEXT2_BLOCK_BITMAP)
106 RtlAllocateHeap(RtlGetProcessHeap(), 0, sizeof(EXT2_BLOCK_BITMAP));
107
108 if (!Ext2Sys->block_map)
109 {
110 DPRINT1("Mke2fs: error allocating block bitmap...\n");
111 return false;
112 }
113
114 memset(Ext2Sys->block_map, 0, sizeof(EXT2_BLOCK_BITMAP));
115
116 Ext2Sys->block_map->start = pExt2Sb->s_first_data_block;
117 Ext2Sys->block_map->end = pExt2Sb->s_blocks_count-1;
118 Ext2Sys->block_map->real_end = (EXT2_BLOCKS_PER_GROUP(pExt2Sb)
119 * Ext2Sys->group_desc_count) -1 + Ext2Sys->block_map->start;
120
121 size = (((Ext2Sys->block_map->real_end - Ext2Sys->block_map->start) / 8) + 1);
122
123 Ext2Sys->block_map->bitmap =
124 (char *)RtlAllocateHeap(RtlGetProcessHeap(), 0, size);
125
126 if (!Ext2Sys->block_map->bitmap)
127 {
128 RtlFreeHeap(RtlGetProcessHeap(), 0, Ext2Sys->block_map);
129 Ext2Sys->block_map = NULL;
130 DPRINT1("Mke2fs: error allocating block bitmap...\n");
131 return false;
132 }
133
134 memset(Ext2Sys->block_map->bitmap, 0, size);
135
136 return true;
137 }
138
139
ext2_allocate_inode_bitmap(PEXT2_FILESYS Ext2Sys)140 bool ext2_allocate_inode_bitmap(PEXT2_FILESYS Ext2Sys)
141 {
142 ULONG size = 0;
143
144 PEXT2_SUPER_BLOCK pExt2Sb = Ext2Sys->ext2_sb;
145
146 Ext2Sys->inode_map = (PEXT2_INODE_BITMAP)
147 RtlAllocateHeap(RtlGetProcessHeap(), 0, sizeof(EXT2_INODE_BITMAP));
148
149 if (!Ext2Sys->inode_map)
150 {
151 DPRINT1("Mke2fs: error allocating inode bitmap...\n");
152 return false;
153 }
154
155 memset(Ext2Sys->inode_map, 0, sizeof(EXT2_INODE_BITMAP));
156
157 Ext2Sys->inode_map->start = 1;
158 Ext2Sys->inode_map->end = pExt2Sb->s_inodes_count;
159 Ext2Sys->inode_map->real_end = (EXT2_INODES_PER_GROUP(pExt2Sb)
160 * Ext2Sys->group_desc_count);
161
162 size = (((Ext2Sys->inode_map->real_end - Ext2Sys->inode_map->start) / 8) + 1);
163
164 Ext2Sys->inode_map->bitmap =
165 (char *)RtlAllocateHeap(RtlGetProcessHeap(), 0, size);
166
167 if (!Ext2Sys->inode_map->bitmap)
168 {
169 RtlFreeHeap(RtlGetProcessHeap(), 0, Ext2Sys->inode_map);
170 Ext2Sys->inode_map = NULL;
171 DPRINT1("Mke2fs: error allocating block bitmap...\n");
172 return false;
173 }
174
175 memset(Ext2Sys->inode_map->bitmap, 0, size);
176
177 return true;
178 }
179
ext2_free_generic_bitmap(PEXT2_GENERIC_BITMAP bitmap)180 void ext2_free_generic_bitmap(PEXT2_GENERIC_BITMAP bitmap)
181 {
182 if (!bitmap)
183 return;
184
185 if (bitmap->bitmap)
186 {
187 RtlFreeHeap(RtlGetProcessHeap(), 0, bitmap->bitmap);
188 bitmap->bitmap = 0;
189 }
190
191 RtlFreeHeap(RtlGetProcessHeap(), 0, bitmap);
192 }
193
ext2_free_inode_bitmap(PEXT2_FILESYS Ext2Sys)194 void ext2_free_inode_bitmap(PEXT2_FILESYS Ext2Sys)
195 {
196 PEXT2_INODE_BITMAP bitmap = Ext2Sys->inode_map;
197 if (!bitmap)
198 return;
199
200 ext2_free_generic_bitmap(bitmap);
201
202 Ext2Sys->inode_map = NULL;
203 }
204
ext2_free_block_bitmap(PEXT2_FILESYS Ext2Sys)205 void ext2_free_block_bitmap(PEXT2_FILESYS Ext2Sys)
206 {
207 PEXT2_BLOCK_BITMAP bitmap = Ext2Sys->block_map;
208 if (!bitmap)
209 return;
210
211 ext2_free_generic_bitmap(bitmap);
212
213 Ext2Sys->block_map = NULL;
214 }
215
ext2_write_inode_bitmap(PEXT2_FILESYS fs)216 bool ext2_write_inode_bitmap(PEXT2_FILESYS fs)
217 {
218 ULONG i;
219 ULONG nbytes;
220 bool retval;
221 char *inode_bitmap = fs->inode_map->bitmap;
222 char *bitmap_block = NULL;
223 ULONG blk;
224
225 if (!inode_bitmap)
226 return false;
227
228 nbytes = (size_t) ((EXT2_INODES_PER_GROUP(fs->ext2_sb)+7) / 8);
229
230 bitmap_block = (char *)RtlAllocateHeap(RtlGetProcessHeap(), 0, fs->blocksize);
231 if (!bitmap_block) return false;
232
233 memset(bitmap_block, 0xff, fs->blocksize);
234
235 for (i = 0; i < fs->group_desc_count; i++)
236 {
237 memcpy(bitmap_block, inode_bitmap, nbytes);
238 blk = fs->group_desc[i].bg_inode_bitmap;
239
240 if (blk)
241 {
242 /*
243 #ifdef EXT2_BIG_ENDIAN_BITMAPS
244 if (!((fs->flags & EXT2_FLAG_SWAP_BYTES) ||
245 (fs->flags & EXT2_FLAG_SWAP_BYTES_WRITE)))
246 ext2_swap_bitmap(fs, bitmap_block, nbytes);
247 #endif
248 */
249 retval = NT_SUCCESS(Ext2WriteDisk(
250 fs,
251 ((ULONGLONG)blk * fs->blocksize),
252 fs->blocksize,
253 (unsigned char *)bitmap_block));
254
255 if (!retval)
256 {
257 RtlFreeHeap(RtlGetProcessHeap(), 0, bitmap_block);
258 return false;
259 }
260 }
261
262 inode_bitmap += nbytes;
263 }
264
265 RtlFreeHeap(RtlGetProcessHeap(), 0, bitmap_block);
266
267 return true;
268 }
269
ext2_write_block_bitmap(PEXT2_FILESYS fs)270 bool ext2_write_block_bitmap (PEXT2_FILESYS fs)
271 {
272 ULONG i;
273 int j;
274 int nbytes;
275 int nbits;
276 bool retval;
277 char *block_bitmap = fs->block_map->bitmap;
278 char *bitmap_block = NULL;
279 ULONG blk;
280
281 if (!block_bitmap)
282 return false;
283
284 nbytes = EXT2_BLOCKS_PER_GROUP(fs->ext2_sb) / 8;
285
286 bitmap_block = (char *)RtlAllocateHeap(RtlGetProcessHeap(), 0, fs->blocksize);
287 if (!bitmap_block)
288 return false;
289
290 memset(bitmap_block, 0xff, fs->blocksize);
291
292 for (i = 0; i < fs->group_desc_count; i++)
293 {
294 memcpy(bitmap_block, block_bitmap, nbytes);
295
296 if (i == fs->group_desc_count - 1)
297 {
298 /* Force bitmap padding for the last group */
299 nbits = (int) ((fs->ext2_sb->s_blocks_count
300 - fs->ext2_sb->s_first_data_block)
301 % EXT2_BLOCKS_PER_GROUP(fs->ext2_sb));
302
303 if (nbits)
304 {
305 for (j = nbits; j < fs->blocksize * 8; j++)
306 {
307 ext2_set_bit(j, bitmap_block);
308 }
309 }
310 }
311
312 blk = fs->group_desc[i].bg_block_bitmap;
313
314 if (blk)
315 {
316 #ifdef EXT2_BIG_ENDIAN_BITMAPS
317 if (!((fs->flags & EXT2_FLAG_SWAP_BYTES) ||
318 (fs->flags & EXT2_FLAG_SWAP_BYTES_WRITE)))
319 ext2_swap_bitmap(fs, bitmap_block, nbytes);
320 #endif
321 retval = NT_SUCCESS(Ext2WriteDisk(
322 fs,
323 ((ULONGLONG)blk * fs->blocksize),
324 fs->blocksize,
325 (unsigned char *)bitmap_block));
326
327 if (!retval)
328 {
329 RtlFreeHeap(RtlGetProcessHeap(), 0, bitmap_block);
330 return false;
331 }
332 }
333
334 block_bitmap += nbytes;
335 }
336
337 RtlFreeHeap(RtlGetProcessHeap(), 0, bitmap_block);
338
339 return true;
340 }
341
ext2_write_bitmaps(PEXT2_FILESYS fs)342 bool ext2_write_bitmaps(PEXT2_FILESYS fs)
343 {
344 bool retval;
345
346 if (fs->block_map) // && ext2fs_test_bb_dirty(fs))
347 {
348 retval = ext2_write_block_bitmap(fs);
349 if (!retval)
350 return retval;
351 }
352
353 if (fs->inode_map) // && ext2fs_test_ib_dirty(fs))
354 {
355 retval = ext2_write_inode_bitmap(fs);
356 if (!retval)
357 return retval;
358 }
359
360 return true;
361 }
362
363
read_bitmaps(PEXT2_FILESYS fs,int do_inode,int do_block)364 bool read_bitmaps(PEXT2_FILESYS fs, int do_inode, int do_block)
365 {
366 ULONG i;
367 char *block_bitmap = 0, *inode_bitmap = 0;
368 bool retval = false;
369 ULONG block_nbytes = EXT2_BLOCKS_PER_GROUP(fs->ext2_sb) / 8;
370 ULONG inode_nbytes = EXT2_INODES_PER_GROUP(fs->ext2_sb) / 8;
371 ULONG blk;
372
373 // fs->write_bitmaps = ext2_write_bitmaps;
374
375 if (do_block)
376 {
377 if (fs->block_map)
378 ext2_free_block_bitmap(fs);
379
380 retval = ext2_allocate_block_bitmap(fs);
381
382 if (!retval)
383 goto cleanup;
384
385 block_bitmap = fs->block_map->bitmap;
386 }
387
388 if (do_inode)
389 {
390 if (fs->inode_map)
391 ext2_free_inode_bitmap(fs);
392
393 retval = ext2_allocate_inode_bitmap(fs);
394 if (!retval)
395 goto cleanup;
396
397 inode_bitmap = fs->inode_map->bitmap;
398 }
399
400 for (i = 0; i < fs->group_desc_count; i++)
401 {
402 if (block_bitmap)
403 {
404 blk = fs->group_desc[i].bg_block_bitmap;
405
406 if (blk)
407 {
408 retval = NT_SUCCESS(Ext2ReadDisk(
409 fs,
410 ((ULONGLONG)blk * fs->blocksize),
411 block_nbytes,
412 (unsigned char *) block_bitmap));
413
414 if (!retval)
415 {
416 goto cleanup;
417 }
418
419 #ifdef EXT2_BIG_ENDIAN_BITMAPS
420 if (!((fs->flags & EXT2_FLAG_SWAP_BYTES) ||
421 (fs->flags & EXT2_FLAG_SWAP_BYTES_READ)))
422 ext2_swap_bitmap(fs, block_bitmap, block_nbytes);
423 #endif
424 }
425 else
426 {
427 memset(block_bitmap, 0, block_nbytes);
428 }
429
430 block_bitmap += block_nbytes;
431 }
432
433 if (inode_bitmap)
434 {
435 blk = fs->group_desc[i].bg_inode_bitmap;
436 if (blk)
437 {
438 retval = NT_SUCCESS(Ext2ReadDisk(
439 fs, ((LONGLONG)blk * fs->blocksize),
440 inode_nbytes,
441 (unsigned char *)inode_bitmap));
442
443 if (!retval)
444 {
445 goto cleanup;
446 }
447
448 #ifdef EXT2_BIG_ENDIAN_BITMAPS
449 if (!((fs->flags & EXT2_FLAG_SWAP_BYTES) ||
450 (fs->flags & EXT2_FLAG_SWAP_BYTES_READ)))
451 ext2_swap_bitmap(fs, inode_bitmap, inode_nbytes);
452 #endif
453 }
454 else
455 {
456 memset(inode_bitmap, 0, inode_nbytes);
457 }
458
459 inode_bitmap += inode_nbytes;
460 }
461 }
462
463 return true;
464
465 cleanup:
466
467 if (do_block)
468 {
469 RtlFreeHeap(RtlGetProcessHeap(), 0, fs->block_map);
470 fs->block_map = NULL;
471 }
472
473 if (do_inode)
474 {
475 RtlFreeHeap(RtlGetProcessHeap(), 0, fs->inode_map);
476 fs->inode_map = 0;
477 }
478
479 return false;
480 }
481
ext2_read_inode_bitmap(PEXT2_FILESYS fs)482 bool ext2_read_inode_bitmap (PEXT2_FILESYS fs)
483 {
484 return read_bitmaps(fs, 1, 0);
485 }
486
ext2_read_block_bitmap(PEXT2_FILESYS fs)487 bool ext2_read_block_bitmap(PEXT2_FILESYS fs)
488 {
489 return read_bitmaps(fs, 0, 1);
490 }
491
ext2_read_bitmaps(PEXT2_FILESYS fs)492 bool ext2_read_bitmaps(PEXT2_FILESYS fs)
493 {
494
495 if (fs->inode_map && fs->block_map)
496 return 0;
497
498 return read_bitmaps(fs, !fs->inode_map, !fs->block_map);
499 }
500
501