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