This source file includes following definitions.
- find_first_zero_bit
- find_next_zero_bit
- find_first_zero_byte
- read_block_bitmap
- load__block_bitmap
- load_block_bitmap
- ext2_free_block
- ext2_new_block
- ext2_count_free_blocks
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 #include <linux/sched.h>
25 #include <linux/ext2_fs.h>
26 #include <linux/stat.h>
27 #include <linux/kernel.h>
28 #include <linux/string.h>
29 #include <linux/locks.h>
30
31 #include <asm/bitops.h>
32
33 #define clear_block(addr,size) \
34 __asm__("cld\n\t" \
35 "rep\n\t" \
36 "stosl" \
37 : \
38 :"a" (0), "c" (size/4), "D" ((long) (addr)) \
39 :"cx", "di")
40
41 static inline int find_first_zero_bit (unsigned *addr, unsigned size)
42 {
43 int res;
44 if (!size)
45 return 0;
46 __asm__("
47 cld
48 movl $-1,%%eax
49 repe; scasl
50 je 1f
51 subl $4,%%edi
52 movl (%%edi),%%eax
53 notl %%eax
54 bsfl %%eax,%%edx
55 jmp 2f
56 1: xorl %%edx,%%edx
57 2: subl %%ebx,%%edi
58 shll $3,%%edi
59 addl %%edi,%%edx"
60 :"=d" (res)
61 :"c" ((size+31)>>5), "D" (addr), "b" (addr)
62 :"ax", "bx", "cx", "di");
63 return res;
64 }
65
66 static inline int find_next_zero_bit (unsigned * addr, int size, int offset)
67 {
68 unsigned *p = ((unsigned *) addr) + (offset >> 5);
69 int set = 0, bit = offset & 31, res;
70
71 if (bit) {
72
73 __asm__("
74 bsfl %1,%0
75 jne 1f
76 movl $32, %0
77 1: "
78 : "=r" (set)
79 : "r" (~(*p >> bit)));
80 if (set < (32 - bit))
81 return set + offset;
82 set = 32 - bit;
83 p++;
84 }
85
86 res = find_first_zero_bit (p, size - 32 * (p - addr));
87 return (offset + set + res);
88 }
89
90 static inline char * find_first_zero_byte (char * addr, int size)
91 {
92 char *res;
93 if (!size)
94 return 0;
95 __asm__("
96 cld
97 mov $0,%%eax
98 repnz; scasb
99 jnz 1f
100 dec %%edi
101 1: "
102 : "=D" (res)
103 : "0" (addr), "c" (size)
104 : "ax");
105 return res;
106 }
107
108 static void read_block_bitmap (struct super_block * sb,
109 unsigned int block_group,
110 unsigned long bitmap_nr)
111 {
112 unsigned long group_desc;
113 unsigned long desc;
114 struct ext2_group_desc * gdp;
115 struct buffer_head * bh;
116
117 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
118 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
119 if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
120 printk ("block_group = %d,group_desc = %d,desc = %d\n",
121 block_group, group_desc, desc);
122 panic ("read_block_bitmap: Group descriptor not loaded");
123 }
124 gdp = (struct ext2_group_desc *)
125 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
126 bh = bread (sb->s_dev, gdp[desc].bg_block_bitmap, sb->s_blocksize);
127 if (!bh) {
128 printk ("block_group = %d,group_desc = %d,"
129 "desc = %d,block_bitmap = %d\n",
130 block_group, group_desc, desc,
131 gdp[desc].bg_block_bitmap);
132 panic ("read_block_bitmap: Cannot read block bitmap");
133 }
134 sb->u.ext2_sb.s_block_bitmap_number[bitmap_nr] = block_group;
135 sb->u.ext2_sb.s_block_bitmap[bitmap_nr] = bh;
136 }
137
138
139
140
141
142
143
144
145
146
147
148
149 static int load__block_bitmap (struct super_block * sb,
150 unsigned int block_group)
151 {
152 int i, j;
153 unsigned long block_bitmap_number;
154 struct buffer_head * block_bitmap;
155
156 if (block_group >= sb->u.ext2_sb.s_groups_count) {
157 printk ("block_group = %d, groups_count = %d\n",
158 block_group, sb->u.ext2_sb.s_groups_count);
159 panic ("load_block_bitmap: block_group >= groups_count");
160 }
161
162 if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
163 if (sb->u.ext2_sb.s_block_bitmap[block_group]) {
164 if (sb->u.ext2_sb.s_block_bitmap_number[block_group] !=
165 block_group)
166 panic ("load_block_bitmap: "
167 "block_group != block_bitmap_number");
168 else
169 return block_group;
170 } else {
171 read_block_bitmap (sb, block_group, block_group);
172 return block_group;
173 }
174 }
175
176 for (i = 0; i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
177 sb->u.ext2_sb.s_block_bitmap_number[i] != block_group; i++)
178 ;
179 if (i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
180 sb->u.ext2_sb.s_block_bitmap_number[i] == block_group) {
181 block_bitmap_number = sb->u.ext2_sb.s_block_bitmap_number[i];
182 block_bitmap = sb->u.ext2_sb.s_block_bitmap[i];
183 for (j = i; j > 0; j--) {
184 sb->u.ext2_sb.s_block_bitmap_number[j] =
185 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
186 sb->u.ext2_sb.s_block_bitmap[j] =
187 sb->u.ext2_sb.s_block_bitmap[j - 1];
188 }
189 sb->u.ext2_sb.s_block_bitmap_number[0] = block_bitmap_number;
190 sb->u.ext2_sb.s_block_bitmap[0] = block_bitmap;
191 } else {
192 if (sb->u.ext2_sb.s_loaded_block_bitmaps <
193 EXT2_MAX_GROUP_LOADED)
194 sb->u.ext2_sb.s_loaded_block_bitmaps++;
195 else
196 brelse (sb->u.ext2_sb.s_block_bitmap
197 [EXT2_MAX_GROUP_LOADED - 1]);
198 for (j = sb->u.ext2_sb.s_loaded_block_bitmaps - 1; j > 0; j--) {
199 sb->u.ext2_sb.s_block_bitmap_number[j] =
200 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
201 sb->u.ext2_sb.s_block_bitmap[j] =
202 sb->u.ext2_sb.s_block_bitmap[j - 1];
203 }
204 read_block_bitmap (sb, block_group, 0);
205 }
206 return 0;
207 }
208
209 static inline int load_block_bitmap (struct super_block * sb,
210 unsigned int block_group)
211 {
212 if (sb->u.ext2_sb.s_loaded_block_bitmaps > 0 &&
213 sb->u.ext2_sb.s_block_bitmap_number[0] == block_group)
214 return 0;
215
216 if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED &&
217 sb->u.ext2_sb.s_block_bitmap_number[block_group] == block_group &&
218 sb->u.ext2_sb.s_block_bitmap[block_group])
219 return block_group;
220
221 return load__block_bitmap (sb, block_group);
222 }
223
224 void ext2_free_block (struct super_block * sb, unsigned long block)
225 {
226 struct buffer_head * bh;
227 struct buffer_head * bh2;
228 unsigned long block_group;
229 unsigned long bit;
230 unsigned long group_desc;
231 unsigned long desc;
232 int bitmap_nr;
233 struct ext2_group_desc * gdp;
234 struct ext2_super_block * es;
235
236 if (!sb) {
237 printk ("ext2_free_block: nonexistant device");
238 return;
239 }
240 lock_super (sb);
241 if (block < sb->u.ext2_sb.s_first_data_block ||
242 block >= sb->u.ext2_sb.s_blocks_count) {
243 printk ("ext2_free_block: block not in datazone\n");
244 unlock_super (sb);
245 return;
246 }
247 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
248 #ifdef EXT2FS_DEBUG
249 printk ("ext2_free_block: freeing block %d\n", block);
250 #endif
251 bh = get_hash_table (sb->s_dev, block, sb->s_blocksize);
252 if (bh)
253 bh->b_dirt = 0;
254 brelse (bh);
255 block_group = (block - sb->u.ext2_sb.s_first_data_block) /
256 EXT2_BLOCKS_PER_GROUP(sb);
257 bit = (block - sb->u.ext2_sb.s_first_data_block) %
258 EXT2_BLOCKS_PER_GROUP(sb);
259 bitmap_nr = load_block_bitmap (sb, block_group);
260 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
261 if (!bh) {
262 printk ("block_group = %d\n", block_group);
263 panic ("ext2_free_block: Unable to load group bitmap");
264 }
265 if (clear_bit (bit, bh->b_data))
266 printk ("ext2_free_block (%04x:%d): bit already cleared\n",
267 sb->s_dev, block);
268 else {
269 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
270 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
271 bh2 = sb->u.ext2_sb.s_group_desc[group_desc];
272 if (!bh2) {
273 printk ("group_desc = %d\n", group_desc);
274 panic ("ext2_free_block: Group descriptor not loaded");
275 }
276 gdp = (struct ext2_group_desc *) bh2->b_data;
277 gdp[desc].bg_free_blocks_count ++;
278 bh2->b_dirt = 1;
279 }
280 bh->b_dirt = 1;
281 es->s_free_blocks_count ++;
282 sb->u.ext2_sb.s_sbh->b_dirt = 1;
283 sb->s_dirt = 1;
284 unlock_super (sb);
285 return;
286 }
287
288
289
290
291
292
293
294
295 int ext2_new_block (struct super_block * sb, unsigned long goal)
296 {
297 struct buffer_head * bh;
298 char *p, *r;
299 int i, j, k;
300 unsigned long lmap;
301 unsigned long group_desc;
302 unsigned long desc;
303 int bitmap_nr;
304 struct ext2_group_desc * gdp;
305 struct ext2_super_block * es;
306
307 #ifdef EXT2FS_DEBUG
308 static int goal_hits = 0, goal_attempts = 0;
309 #endif
310 if (!sb) {
311 printk ("ext2_new_block: nonexistant device");
312 return 0;
313 }
314 lock_super (sb);
315 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
316 if (es->s_free_blocks_count <= es->s_r_blocks_count && !suser()) {
317 unlock_super (sb);
318 return 0;
319 }
320
321 #ifdef EXT2FS_DEBUG
322 printk ("ext2_new_block: goal=%d.\n", goal);
323 #endif
324
325 repeat:
326
327 i = ((goal - sb->u.ext2_sb.s_first_data_block) /
328 EXT2_BLOCKS_PER_GROUP(sb));
329 group_desc = i / EXT2_DESC_PER_BLOCK(sb);
330 desc = i % EXT2_DESC_PER_BLOCK(sb);
331 gdp = (struct ext2_group_desc *)
332 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
333 if (!gdp) {
334 panic ("ext2_new_block: Descriptor not loaded");
335 }
336 if (gdp[desc].bg_free_blocks_count > 0) {
337 j = ((goal - sb->u.ext2_sb.s_first_data_block) %
338 EXT2_BLOCKS_PER_GROUP(sb));
339 #ifdef EXT2FS_DEBUG
340 if (j)
341 goal_attempts++;
342 #endif
343 bitmap_nr = load_block_bitmap (sb, i);
344 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
345 if (!bh) {
346 printk ("Cannot load bitmap_nr %d.\n", bitmap_nr);
347 unlock_super (sb);
348 return 0;
349 }
350 #ifdef EXT2FS_DEBUG
351 printk ("goal is at %d[%d,%d]:%d.\n", i, group_desc, desc, j);
352 #endif
353 if (!test_bit(j, bh->b_data)) {
354 #ifdef EXT2FS_DEBUG
355 goal_hits++;
356 printk ("ext2_new_block: goal bit allocated.\n");
357 #endif
358 goto got_block;
359 }
360 if (j) {
361
362
363 lmap = ((((unsigned long *) bh->b_data)[j >> 5]) >>
364 ((j & 31) + 1));
365 if (j < EXT2_BLOCKS_PER_GROUP(sb) - 32)
366 lmap |= (((unsigned long *) bh->b_data)[(j >> 5) + 1]) <<
367 (31 - (j & 31));
368 else
369 lmap |= 0xffffffff << (31 - (j & 31));
370 if (lmap != 0xffffffffl) {
371 __asm__ ("bsfl %1,%0"
372 : "=r" (k)
373 : "r" (~lmap));
374 k++;
375 if ((j + k) < EXT2_BLOCKS_PER_GROUP(sb)) {
376 j += k;
377 goto got_block;
378 }
379 }
380 }
381
382 #ifdef EXT2FS_DEBUG
383 printk ("Bit not found near goal\n");
384 #endif
385
386
387
388
389
390
391
392 p = ((char *) bh->b_data) + (j >> 3);
393 r = find_first_zero_byte (p,
394 (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
395 k = (r - ((char *) bh->b_data)) << 3;
396 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
397 j = k;
398 goto got_block;
399 }
400 k = find_next_zero_bit ((unsigned long *) bh->b_data,
401 EXT2_BLOCKS_PER_GROUP(sb),
402 j);
403 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
404 j = k;
405 goto got_block;
406 }
407 }
408
409 #ifdef EXT2FS_DEBUG
410 printk ("Bit not found in block group %d.\n", i);
411 #endif
412
413
414 for (k = 0; k < sb->u.ext2_sb.s_groups_count; k++) {
415 i++;
416 if (i >= sb->u.ext2_sb.s_groups_count) {
417 i = 0;
418 group_desc = 0;
419 desc = 0;
420 gdp = (struct ext2_group_desc *)
421 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
422 }
423 else {
424 desc++;
425 if (desc >= EXT2_DESC_PER_BLOCK(sb)) {
426 group_desc++;
427 desc = 0;
428 gdp = (struct ext2_group_desc *)
429 sb->u.ext2_sb.s_group_desc[group_desc]
430 ->b_data;
431 }
432 }
433 if (!gdp) {
434 panic ("ext2_new_block: Descriptor not loaded");
435 }
436 if (gdp[desc].bg_free_blocks_count > 0)
437 break;
438 }
439 if (k >= sb->u.ext2_sb.s_groups_count) {
440 unlock_super (sb);
441 return 0;
442 }
443 bitmap_nr = load_block_bitmap (sb, i);
444 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
445 if (!bh) {
446 printk ("block_group = %d\n", i);
447 panic ("ext2_new_block: Unable to load group bitmap");
448 }
449 r = find_first_zero_byte (bh->b_data,
450 EXT2_BLOCKS_PER_GROUP(sb) >> 3);
451 j = (r - bh->b_data) << 3;
452 if (j >= EXT2_BLOCKS_PER_GROUP(sb))
453 j = find_first_zero_bit ((unsigned long *) bh->b_data,
454 EXT2_BLOCKS_PER_GROUP(sb));
455 if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
456 printk ("ext2_new_block: "
457 "Unable to locate free bit in block group %d.\n",i);
458 unlock_super (sb);
459 return 0;
460 }
461
462 got_block:
463 #ifdef EXT2FS_DEBUG
464 printk ("ext2_new_block: using block group %d(%d,%d,%d)\n",
465 i, group_desc, desc, gdp[desc].bg_free_blocks_count);
466 #endif
467
468 if (set_bit (j, bh->b_data)) {
469 printk ("ext2_new_block: bit already set\n");
470 goto repeat;
471 }
472 bh->b_dirt = 1;
473
474 #ifdef EXT2FS_DEBUG
475 printk ("ext2_new_block: found bit %d\n", j);
476 #endif
477 j += i * EXT2_BLOCKS_PER_GROUP(sb) + sb->u.ext2_sb.s_first_data_block;
478 if (j >= sb->u.ext2_sb.s_blocks_count) {
479 printk ("block_group = %d,block=%d\n", i, j);
480 printk ("ext2_new_block: block >= blocks count");
481 unlock_super (sb);
482 return 0;
483 }
484 if (!(bh = getblk (sb->s_dev, j, sb->s_blocksize))) {
485 printk ("ext2_new_block: cannot get block");
486 unlock_super (sb);
487 return 0;
488 }
489 clear_block (bh->b_data, sb->s_blocksize);
490 bh->b_uptodate = 1;
491 bh->b_dirt = 1;
492 brelse (bh);
493 #ifdef EXT2FS_DEBUG
494 printk("ext2_new_block: allocating block %d. "
495 "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
496 #endif
497 gdp[desc].bg_free_blocks_count --;
498 sb->u.ext2_sb.s_group_desc[group_desc]->b_dirt = 1;
499 es->s_free_blocks_count --;
500 sb->u.ext2_sb.s_sbh->b_dirt = 1;
501 sb->s_dirt = 1;
502 unlock_super (sb);
503 return j;
504 }
505
506 unsigned long ext2_count_free_blocks (struct super_block *sb)
507 {
508 struct ext2_super_block * es;
509 #ifdef EXT2FS_DEBUG
510 unsigned long desc_count, bitmap_count, x;
511 unsigned long group_desc;
512 unsigned long desc;
513 int bitmap_nr;
514 struct ext2_group_desc * gdp;
515 int i;
516
517 lock_super (sb);
518 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
519 desc_count = 0;
520 bitmap_count = 0;
521 group_desc = 0;
522 desc = 0;
523 gdp = NULL;
524 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
525 if (!gdp) {
526 if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
527 printk ("ext2_count_free_block: "
528 "Descriptor not loaded\n");
529 break;
530 }
531 gdp = (struct ext2_group_desc *)
532 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
533 }
534 desc_count += gdp[desc].bg_free_blocks_count;
535 bitmap_nr = load_block_bitmap (sb, i);
536 if (sb->u.ext2_sb.s_block_bitmap[bitmap_nr])
537 x = ext2_count_free
538 (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
539 sb->s_blocksize);
540 else {
541 x = 0;
542 printk ("Cannot load bitmap for group %d\n", i);
543 }
544 printk ("group %d: stored = %d, counted = %d\n",
545 i, gdp[desc].bg_free_blocks_count, x);
546 bitmap_count += x;
547 desc ++;
548 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
549 group_desc ++;
550 desc = 0;
551 gdp = NULL;
552 }
553 }
554 printk("ext2_count_free_blocks: stored = %d, computed = %d, %d\n",
555 es->s_free_blocks_count, desc_count, bitmap_count);
556 unlock_super (sb);
557 return bitmap_count;
558 #else
559 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
560 return es->s_free_blocks_count;
561 #endif
562 }