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 if (block < sb->u.ext2_sb.s_first_data_block ||
243 block >= sb->u.ext2_sb.s_blocks_count) {
244 printk ("ext2_free_block: block not in datazone\n");
245 unlock_super (sb);
246 return;
247 }
248 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
249 #ifdef EXT2FS_DEBUG
250 printk ("ext2_free_block: freeing block %d\n", block);
251 #endif
252 bh = get_hash_table (sb->s_dev, block, sb->s_blocksize);
253 if (bh)
254 bh->b_dirt = 0;
255 brelse (bh);
256 block_group = (block - sb->u.ext2_sb.s_first_data_block) /
257 EXT2_BLOCKS_PER_GROUP(sb);
258 bit = (block - sb->u.ext2_sb.s_first_data_block) %
259 EXT2_BLOCKS_PER_GROUP(sb);
260 bitmap_nr = load_block_bitmap (sb, block_group);
261 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
262 if (!bh) {
263 printk ("block_group = %d\n", block_group);
264 panic ("ext2_free_block: Unable to load group bitmap");
265 }
266 if (!clear_bit (bit, bh->b_data))
267 printk ("ext2_free_block (%04x:%d): bit already cleared\n",
268 sb->s_dev, block);
269 else {
270 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
271 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
272 bh2 = sb->u.ext2_sb.s_group_desc[group_desc];
273 if (!bh2) {
274 printk ("group_desc = %d\n", group_desc);
275 panic ("ext2_free_block: Group descriptor not loaded");
276 }
277 gdp = (struct ext2_group_desc *) bh2->b_data;
278 gdp[desc].bg_free_blocks_count ++;
279 bh2->b_dirt = 1;
280 }
281 bh->b_dirt = 1;
282 es->s_free_blocks_count ++;
283 sb->u.ext2_sb.s_sbh->b_dirt = 1;
284 sb->s_dirt = 1;
285 unlock_super (sb);
286 return;
287 }
288
289
290
291
292
293
294
295
296 int ext2_new_block (struct super_block * sb, unsigned long goal)
297 {
298 struct buffer_head * bh;
299 char *p, *r;
300 int i, j, k;
301 unsigned long lmap;
302 unsigned long group_desc;
303 unsigned long desc;
304 int bitmap_nr;
305 struct ext2_group_desc * gdp;
306 struct ext2_super_block * es;
307
308 #ifdef EXT2FS_DEBUG
309 static int goal_hits = 0, goal_attempts = 0;
310 #endif
311 if (!sb) {
312 printk ("ext2_new_block: nonexistant device");
313 return 0;
314 }
315 lock_super (sb);
316 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
317 if (es->s_free_blocks_count <= es->s_r_blocks_count && !suser()) {
318 unlock_super (sb);
319 return 0;
320 }
321
322 #ifdef EXT2FS_DEBUG
323 printk ("ext2_new_block: goal=%d.\n", goal);
324 #endif
325
326 repeat:
327
328 i = ((goal - sb->u.ext2_sb.s_first_data_block) /
329 EXT2_BLOCKS_PER_GROUP(sb));
330 group_desc = i / EXT2_DESC_PER_BLOCK(sb);
331 desc = i % EXT2_DESC_PER_BLOCK(sb);
332 gdp = (struct ext2_group_desc *)
333 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
334 if (!gdp) {
335 panic ("ext2_new_block: Descriptor not loaded");
336 }
337 if (gdp[desc].bg_free_blocks_count > 0) {
338 j = ((goal - sb->u.ext2_sb.s_first_data_block) %
339 EXT2_BLOCKS_PER_GROUP(sb));
340 #ifdef EXT2FS_DEBUG
341 if (j)
342 goal_attempts++;
343 #endif
344 bitmap_nr = load_block_bitmap (sb, i);
345 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
346 if (!bh) {
347 printk ("Cannot load bitmap_nr %d.\n", bitmap_nr);
348 unlock_super (sb);
349 return 0;
350 }
351 #ifdef EXT2FS_DEBUG
352 printk ("goal is at %d[%d,%d]:%d.\n", i, group_desc, desc, j);
353 #endif
354 if (!test_bit(j, bh->b_data)) {
355 #ifdef EXT2FS_DEBUG
356 goal_hits++;
357 printk ("ext2_new_block: goal bit allocated.\n");
358 #endif
359 goto got_block;
360 }
361 if (j) {
362
363
364 lmap = ((((unsigned long *) bh->b_data)[j >> 5]) >>
365 ((j & 31) + 1));
366 if (j < EXT2_BLOCKS_PER_GROUP(sb) - 32)
367 lmap |= (((unsigned long *) bh->b_data)[(j >> 5) + 1]) <<
368 (31 - (j & 31));
369 else
370 lmap |= 0xffffffff << (31 - (j & 31));
371 if (lmap != 0xffffffffl) {
372 __asm__ ("bsfl %1,%0"
373 : "=r" (k)
374 : "r" (~lmap));
375 k++;
376 if ((j + k) < EXT2_BLOCKS_PER_GROUP(sb)) {
377 j += k;
378 goto got_block;
379 }
380 }
381 }
382
383 #ifdef EXT2FS_DEBUG
384 printk ("Bit not found near goal\n");
385 #endif
386
387
388
389
390
391
392
393 p = ((char *) bh->b_data) + (j >> 3);
394 r = find_first_zero_byte (p,
395 (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
396 k = (r - ((char *) bh->b_data)) << 3;
397 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
398 j = k;
399 goto got_block;
400 }
401 k = find_next_zero_bit ((unsigned long *) bh->b_data,
402 EXT2_BLOCKS_PER_GROUP(sb),
403 j);
404 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
405 j = k;
406 goto got_block;
407 }
408 }
409
410 #ifdef EXT2FS_DEBUG
411 printk ("Bit not found in block group %d.\n", i);
412 #endif
413
414
415 for (k = 0; k < sb->u.ext2_sb.s_groups_count; k++) {
416 i++;
417 if (i >= sb->u.ext2_sb.s_groups_count) {
418 i = 0;
419 group_desc = 0;
420 desc = 0;
421 gdp = (struct ext2_group_desc *)
422 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
423 }
424 else {
425 desc++;
426 if (desc >= EXT2_DESC_PER_BLOCK(sb)) {
427 group_desc++;
428 desc = 0;
429 gdp = (struct ext2_group_desc *)
430 sb->u.ext2_sb.s_group_desc[group_desc]
431 ->b_data;
432 }
433 }
434 if (!gdp) {
435 panic ("ext2_new_block: Descriptor not loaded");
436 }
437 if (gdp[desc].bg_free_blocks_count > 0)
438 break;
439 }
440 if (k >= sb->u.ext2_sb.s_groups_count) {
441 unlock_super (sb);
442 return 0;
443 }
444 bitmap_nr = load_block_bitmap (sb, i);
445 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
446 if (!bh) {
447 printk ("block_group = %d\n", i);
448 panic ("ext2_new_block: Unable to load group bitmap");
449 }
450 r = find_first_zero_byte (bh->b_data,
451 EXT2_BLOCKS_PER_GROUP(sb) >> 3);
452 j = (r - bh->b_data) << 3;
453 if (j >= EXT2_BLOCKS_PER_GROUP(sb))
454 j = find_first_zero_bit ((unsigned long *) bh->b_data,
455 EXT2_BLOCKS_PER_GROUP(sb));
456 if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
457 printk ("ext2_new_block: "
458 "Unable to locate free bit in block group %d.\n",i);
459 unlock_super (sb);
460 return 0;
461 }
462
463 got_block:
464 #ifdef EXT2FS_DEBUG
465 printk ("ext2_new_block: using block group %d(%d,%d,%d)\n",
466 i, group_desc, desc, gdp[desc].bg_free_blocks_count);
467 #endif
468
469 if (set_bit (j, bh->b_data)) {
470 printk ("ext2_new_block: bit already set\n");
471 goto repeat;
472 }
473 bh->b_dirt = 1;
474
475 #ifdef EXT2FS_DEBUG
476 printk ("ext2_new_block: found bit %d\n", j);
477 #endif
478 j += i * EXT2_BLOCKS_PER_GROUP(sb) + sb->u.ext2_sb.s_first_data_block;
479 if (j >= sb->u.ext2_sb.s_blocks_count) {
480 printk ("block_group = %d,block=%d\n", i, j);
481 printk ("ext2_new_block: block >= blocks count");
482 unlock_super (sb);
483 return 0;
484 }
485 if (!(bh = getblk (sb->s_dev, j, sb->s_blocksize))) {
486 printk ("ext2_new_block: cannot get block");
487 unlock_super (sb);
488 return 0;
489 }
490 clear_block (bh->b_data, sb->s_blocksize);
491 bh->b_uptodate = 1;
492 bh->b_dirt = 1;
493 brelse (bh);
494 #ifdef EXT2FS_DEBUG
495 printk("ext2_new_block: allocating block %d. "
496 "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
497 #endif
498 gdp[desc].bg_free_blocks_count --;
499 sb->u.ext2_sb.s_group_desc[group_desc]->b_dirt = 1;
500 es->s_free_blocks_count --;
501 sb->u.ext2_sb.s_sbh->b_dirt = 1;
502 sb->s_dirt = 1;
503 unlock_super (sb);
504 return j;
505 }
506
507 unsigned long ext2_count_free_blocks (struct super_block *sb)
508 {
509 struct ext2_super_block * es;
510 #ifdef EXT2FS_DEBUG
511 unsigned long desc_count, bitmap_count, x;
512 unsigned long group_desc;
513 unsigned long desc;
514 int bitmap_nr;
515 struct ext2_group_desc * gdp;
516 int i;
517
518 lock_super (sb);
519 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
520 desc_count = 0;
521 bitmap_count = 0;
522 group_desc = 0;
523 desc = 0;
524 gdp = NULL;
525 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
526 if (!gdp) {
527 if (!sb->u.ext2_sb.s_group_desc[group_desc]) {
528 printk ("ext2_count_free_block: "
529 "Descriptor not loaded\n");
530 break;
531 }
532 gdp = (struct ext2_group_desc *)
533 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
534 }
535 desc_count += gdp[desc].bg_free_blocks_count;
536 bitmap_nr = load_block_bitmap (sb, i);
537 if (sb->u.ext2_sb.s_block_bitmap[bitmap_nr])
538 x = ext2_count_free
539 (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
540 sb->s_blocksize);
541 else {
542 x = 0;
543 printk ("Cannot load bitmap for group %d\n", i);
544 }
545 printk ("group %d: stored = %d, counted = %d\n",
546 i, gdp[desc].bg_free_blocks_count, x);
547 bitmap_count += x;
548 desc ++;
549 if (desc == EXT2_DESC_PER_BLOCK(sb)) {
550 group_desc ++;
551 desc = 0;
552 gdp = NULL;
553 }
554 }
555 printk("ext2_count_free_blocks: stored = %d, computed = %d, %d\n",
556 es->s_free_blocks_count, desc_count, bitmap_count);
557 unlock_super (sb);
558 return bitmap_count;
559 #else
560 es = (struct ext2_super_block *) sb->u.ext2_sb.s_sbh->b_data;
561 return es->s_free_blocks_count;
562 #endif
563 }