Remove Alpha specific header file.
[dragonfly.git] / sys / vfs / gnu / ext2fs / ext2_linux_balloc.c
1 /*
2  *  modified for Lites 1.1
3  *
4  *  Aug 1995, Godmar Back (gback@cs.utah.edu)
5  *  University of Utah, Department of Computer Science
6  *
7  * $FreeBSD: src/sys/gnu/ext2fs/ext2_linux_balloc.c,v 1.11.2.3 2001/08/14 18:03:19 gallatin Exp $
8  * $DragonFly: src/sys/vfs/gnu/ext2fs/ext2_linux_balloc.c,v 1.9 2006/05/12 07:43:56 swildner Exp $
9  */
10 /*
11  *  linux/fs/ext2/balloc.c
12  *
13  * Copyright (C) 1992, 1993, 1994, 1995
14  * Remy Card (card@masi.ibp.fr)
15  * Laboratoire MASI - Institut Blaise Pascal
16  * Universite Pierre et Marie Curie (Paris VI)
17  *
18  *  Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
19  */
20
21 /*
22  * The free blocks are managed by bitmaps.  A file system contains several
23  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
24  * block for inodes, N blocks for the inode table and data blocks.
25  *
26  * The file system contains group descriptors which are located after the
27  * super block.  Each descriptor contains the number of the bitmap block and
28  * the free blocks count in the block.  The descriptors are loaded in memory
29  * when a file system is mounted (see ext2_read_super).
30  */
31
32 #include <sys/param.h>
33 #include <sys/systm.h>
34 #include <sys/buf.h>
35 #include <sys/proc.h>
36 #include <sys/mount.h>
37 #include <sys/vnode.h>
38 #include <sys/buf2.h>
39 #include <sys/thread2.h>
40
41 #include "quota.h"
42 #include "dinode.h"
43 #include "inode.h"
44 #include "ext2mount.h"
45 #include "ext2_extern.h"
46 #include "ext2_fs.h"
47 #include "ext2_fs_sb.h"
48 #include "fs.h"
49
50 #ifdef __i386__
51 #include "i386-bitops.h"
52 #else
53 #error Provide an bitops.h file, please !
54 #endif
55
56 #define in_range(b, first, len)         ((b) >= (first) && (b) <= (first) + (len) - 1)
57
58 /* got rid of get_group_desc since it can already be found in 
59  * ext2_linux_ialloc.c
60  */
61
62 static void
63 read_block_bitmap(struct mount *mp, unsigned int block_group,
64                   unsigned long bitmap_nr)
65 {
66         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
67         struct ext2_group_desc * gdp;
68         struct buffer_head * bh;
69         int    error;
70         
71         gdp = get_group_desc (mp, block_group, NULL);
72         error = bread(VFSTOEXT2(mp)->um_devvp, 
73                       fsbtodoff(sb, gdp->bg_block_bitmap),
74                       sb->s_blocksize, &bh);
75         if (error) {
76                 panic ( "read_block_bitmap: "
77                             "Cannot read block bitmap - "
78                             "block_group = %d, block_bitmap = %lu",
79                             block_group, (unsigned long) gdp->bg_block_bitmap);
80         }
81         sb->s_block_bitmap_number[bitmap_nr] = block_group;
82         sb->s_block_bitmap[bitmap_nr] = bh;
83         LCK_BUF(bh)
84 }
85
86 /*
87  * load_block_bitmap loads the block bitmap for a blocks group
88  *
89  * It maintains a cache for the last bitmaps loaded.  This cache is managed
90  * with a LRU algorithm.
91  *
92  * Notes:
93  * 1/ There is one cache per mounted file system.
94  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
95  *    this function reads the bitmap without maintaining a LRU cache.
96  */
97 static int
98 load__block_bitmap(struct mount *mp, unsigned int block_group)
99 {
100         int i, j;
101         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
102         unsigned long block_bitmap_number;
103         struct buffer_head * block_bitmap;
104
105         if (block_group >= sb->s_groups_count)
106                 panic ( "load_block_bitmap: "
107                             "block_group >= groups_count - "
108                             "block_group = %d, groups_count = %lu",
109                             block_group, sb->s_groups_count);
110
111         if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
112                 if (sb->s_block_bitmap[block_group]) {
113                         if (sb->s_block_bitmap_number[block_group] !=
114                             block_group)
115                                 panic ( "load_block_bitmap: "
116                                             "block_group != block_bitmap_number");
117                         else
118                                 return block_group;
119                 } else {
120                         read_block_bitmap (mp, block_group, block_group);
121                         return block_group;
122                 }
123         }
124
125         for (i = 0; i < sb->s_loaded_block_bitmaps &&
126                     sb->s_block_bitmap_number[i] != block_group; i++)
127                 ;
128         if (i < sb->s_loaded_block_bitmaps &&
129             sb->s_block_bitmap_number[i] == block_group) {
130                 block_bitmap_number = sb->s_block_bitmap_number[i];
131                 block_bitmap = sb->s_block_bitmap[i];
132                 for (j = i; j > 0; j--) {
133                         sb->s_block_bitmap_number[j] =
134                                 sb->s_block_bitmap_number[j - 1];
135                         sb->s_block_bitmap[j] =
136                                 sb->s_block_bitmap[j - 1];
137                 }
138                 sb->s_block_bitmap_number[0] = block_bitmap_number;
139                 sb->s_block_bitmap[0] = block_bitmap;
140         } else {
141                 if (sb->s_loaded_block_bitmaps < EXT2_MAX_GROUP_LOADED)
142                         sb->s_loaded_block_bitmaps++;
143                 else
144                         ULCK_BUF(sb->s_block_bitmap[EXT2_MAX_GROUP_LOADED - 1])
145
146                 for (j = sb->s_loaded_block_bitmaps - 1; j > 0;  j--) {
147                         sb->s_block_bitmap_number[j] =
148                                 sb->s_block_bitmap_number[j - 1];
149                         sb->s_block_bitmap[j] =
150                                 sb->s_block_bitmap[j - 1];
151                 }
152                 read_block_bitmap (mp, block_group, 0);
153         }
154         return 0;
155 }
156
157 static __inline int
158 load_block_bitmap(struct mount * mp, unsigned int block_group)
159 {
160         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
161         if (sb->s_loaded_block_bitmaps > 0 &&
162             sb->s_block_bitmap_number[0] == block_group)
163                 return 0;
164         
165         if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED && 
166             sb->s_block_bitmap_number[block_group] == block_group &&
167             sb->s_block_bitmap[block_group]) 
168                 return block_group;
169
170         return load__block_bitmap (mp, block_group);
171 }
172
173 void
174 ext2_free_blocks(struct mount * mp, unsigned long block,
175                  unsigned long count)
176 {
177         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
178         struct buffer_head * bh;
179         struct buffer_head * bh2;
180         unsigned long block_group;
181         unsigned long bit;
182         unsigned long i;
183         int bitmap_nr;
184         struct ext2_group_desc * gdp;
185         struct ext2_super_block * es = sb->s_es;
186
187         if (!sb) {
188                 printf ("ext2_free_blocks: nonexistent device");
189                 return;
190         }
191         lock_super (VFSTOEXT2(mp)->um_devvp);
192         if (block < es->s_first_data_block || 
193             (block + count) > es->s_blocks_count) {
194                 printf ( "ext2_free_blocks: "
195                             "Freeing blocks not in datazone - "
196                             "block = %lu, count = %lu", block, count);
197                 unlock_super (VFSTOEXT2(mp)->um_devvp);
198                 return;
199         }
200
201         ext2_debug ("freeing blocks %lu to %lu\n", block, block+count-1);
202
203         block_group = (block - es->s_first_data_block) /
204                       EXT2_BLOCKS_PER_GROUP(sb);
205         bit = (block - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb);
206         if (bit + count > EXT2_BLOCKS_PER_GROUP(sb))
207                 panic ( "ext2_free_blocks: "
208                             "Freeing blocks across group boundary - "
209                             "Block = %lu, count = %lu",
210                             block, count);
211         bitmap_nr = load_block_bitmap (mp, block_group);
212         bh = sb->s_block_bitmap[bitmap_nr];
213         gdp = get_group_desc (mp, block_group, &bh2);
214
215         if (/* test_opt (sb, CHECK_STRICT) &&   assume always strict ! */
216             (in_range (gdp->bg_block_bitmap, block, count) ||
217              in_range (gdp->bg_inode_bitmap, block, count) ||
218              in_range (block, gdp->bg_inode_table,
219                        sb->s_itb_per_group) ||
220              in_range (block + count - 1, gdp->bg_inode_table,
221                        sb->s_itb_per_group)))
222                 panic ( "ext2_free_blocks: "
223                             "Freeing blocks in system zones - "
224                             "Block = %lu, count = %lu",
225                             block, count);
226
227         for (i = 0; i < count; i++) {
228                 if (!clear_bit (bit + i, bh->b_data))
229                         printf ("ext2_free_blocks: "
230                                       "bit already cleared for block %lu", 
231                                       block);
232                 else {
233                         gdp->bg_free_blocks_count++;
234                         es->s_free_blocks_count++;
235                 }
236         }
237
238         mark_buffer_dirty(bh2);
239         mark_buffer_dirty(bh);
240 /****
241         if (sb->s_flags & MS_SYNCHRONOUS) {
242                 ll_rw_block (WRITE, 1, &bh);
243                 wait_on_buffer (bh);
244         }
245 ****/
246         sb->s_dirt = 1;
247         unlock_super (VFSTOEXT2(mp)->um_devvp);
248         return;
249 }
250
251 /*
252  * ext2_new_block uses a goal block to assist allocation.  If the goal is
253  * free, or there is a free block within 32 blocks of the goal, that block
254  * is allocated.  Otherwise a forward search is made for a free block; within 
255  * each block group the search first looks for an entire free byte in the block
256  * bitmap, and then for any free bit if that fails.
257  */
258 int
259 ext2_new_block(struct mount * mp, unsigned long goal,
260                u_int32_t * prealloc_count,
261                u_int32_t * prealloc_block)
262 {
263         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
264         struct buffer_head * bh;
265         struct buffer_head * bh2;
266         char * p, * r;
267         int i, j, k, tmp;
268         int bitmap_nr;
269         struct ext2_group_desc * gdp;
270         struct ext2_super_block * es = sb->s_es;
271
272 #ifdef EXT2FS_DEBUG
273         static int goal_hits = 0, goal_attempts = 0;
274 #endif
275         if (!sb) {
276                 printf ("ext2_new_block: nonexistent device");
277                 return 0;
278         }
279         lock_super (VFSTOEXT2(mp)->um_devvp);
280
281         ext2_debug ("goal=%lu.\n", goal);
282
283 repeat:
284         /*
285          * First, test whether the goal block is free.
286          */
287         if (goal < es->s_first_data_block || goal >= es->s_blocks_count)
288                 goal = es->s_first_data_block;
289         i = (goal - es->s_first_data_block) / EXT2_BLOCKS_PER_GROUP(sb);
290         gdp = get_group_desc (mp, i, &bh2);
291         if (gdp->bg_free_blocks_count > 0) {
292                 j = ((goal - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb));
293 #ifdef EXT2FS_DEBUG
294                 if (j)
295                         goal_attempts++;
296 #endif
297                 bitmap_nr = load_block_bitmap (mp, i);
298                 bh = sb->s_block_bitmap[bitmap_nr];
299
300                 ext2_debug ("goal is at %d:%d.\n", i, j); 
301
302                 if (!test_bit(j, bh->b_data)) {
303 #ifdef EXT2FS_DEBUG
304                         goal_hits++;
305                         ext2_debug ("goal bit allocated.\n");
306 #endif
307                         goto got_block;
308                 }
309                 if (j) {
310                         /*
311                          * The goal was occupied; search forward for a free 
312                          * block within the next XX blocks.
313                          *
314                          * end_goal is more or less random, but it has to be
315                          * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
316                          * next 64-bit boundary is simple..
317                          */
318                         int end_goal = (j + 63) & ~63;
319                         j = find_next_zero_bit(bh->b_data, end_goal, j);
320                         if (j < end_goal)
321                                 goto got_block;
322                 }
323         
324                 ext2_debug ("Bit not found near goal\n");
325
326                 /*
327                  * There has been no free block found in the near vicinity
328                  * of the goal: do a search forward through the block groups,
329                  * searching in each group first for an entire free byte in
330                  * the bitmap and then for any free bit.
331                  * 
332                  * Search first in the remainder of the current group; then,
333                  * cyclicly search through the rest of the groups.
334                  */
335                 p = ((char *) bh->b_data) + (j >> 3);
336                 r = memscan(p, 0, (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
337                 k = (r - ((char *) bh->b_data)) << 3;
338                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
339                         j = k;
340                         goto search_back;
341                 }
342                 k = find_next_zero_bit ((unsigned long *) bh->b_data, 
343                                         EXT2_BLOCKS_PER_GROUP(sb),
344                                         j);
345                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
346                         j = k;
347                         goto got_block;
348                 }
349         }
350
351         ext2_debug ("Bit not found in block group %d.\n", i); 
352
353         /*
354          * Now search the rest of the groups.  We assume that 
355          * i and gdp correctly point to the last group visited.
356          */
357         for (k = 0; k < sb->s_groups_count; k++) {
358                 i++;
359                 if (i >= sb->s_groups_count)
360                         i = 0;
361                 gdp = get_group_desc (mp, i, &bh2);
362                 if (gdp->bg_free_blocks_count > 0)
363                         break;
364         }
365         if (k >= sb->s_groups_count) {
366                 unlock_super (VFSTOEXT2(mp)->um_devvp);
367                 return 0;
368         }
369         bitmap_nr = load_block_bitmap (mp, i);
370         bh = sb->s_block_bitmap[bitmap_nr];
371         r = memscan(bh->b_data, 0, EXT2_BLOCKS_PER_GROUP(sb) >> 3);
372         j = (r - bh->b_data) << 3;
373
374         if (j < EXT2_BLOCKS_PER_GROUP(sb))
375                 goto search_back;
376         else
377                 j = find_first_zero_bit ((unsigned long *) bh->b_data,
378                                          EXT2_BLOCKS_PER_GROUP(sb));
379         if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
380                 printf ( "ext2_new_block: "
381                          "Free blocks count corrupted for block group %d", i);
382                 unlock_super (VFSTOEXT2(mp)->um_devvp);
383                 return 0;
384         }
385
386 search_back:
387         /* 
388          * We have succeeded in finding a free byte in the block
389          * bitmap.  Now search backwards up to 7 bits to find the
390          * start of this group of free blocks.
391          */
392         for (k = 0; k < 7 && j > 0 && !test_bit (j - 1, bh->b_data); k++, j--);
393         
394 got_block:
395
396         ext2_debug ("using block group %d(%d)\n", i, gdp->bg_free_blocks_count);
397
398         tmp = j + i * EXT2_BLOCKS_PER_GROUP(sb) + es->s_first_data_block;
399
400         if (/* test_opt (sb, CHECK_STRICT) && we are always strict. */
401             (tmp == gdp->bg_block_bitmap ||
402              tmp == gdp->bg_inode_bitmap ||
403              in_range (tmp, gdp->bg_inode_table, sb->s_itb_per_group)))
404                 panic ( "ext2_new_block: "
405                             "Allocating block in system zone - "
406                             "%dth block = %u in group %u", j, tmp, i);
407
408         if (set_bit (j, bh->b_data)) {
409                 printf ( "ext2_new_block: "
410                          "bit already set for block %d", j);
411                 goto repeat;
412         }
413
414         ext2_debug ("found bit %d\n", j);
415
416         /*
417          * Do block preallocation now if required.
418          */
419 #ifdef EXT2_PREALLOCATE
420         if (prealloc_block) {
421                 *prealloc_count = 0;
422                 *prealloc_block = tmp + 1;
423                 for (k = 1;
424                      k < 8 && (j + k) < EXT2_BLOCKS_PER_GROUP(sb); k++) {
425                         if (set_bit (j + k, bh->b_data))
426                                 break;
427                         (*prealloc_count)++;
428                 }       
429                 gdp->bg_free_blocks_count -= *prealloc_count;
430                 es->s_free_blocks_count -= *prealloc_count;
431                 ext2_debug ("Preallocated a further %lu bits.\n",
432                             *prealloc_count); 
433         }
434 #endif
435
436         j = tmp;
437
438         mark_buffer_dirty(bh);
439 /****
440         if (sb->s_flags & MS_SYNCHRONOUS) {
441                 ll_rw_block (WRITE, 1, &bh);
442                 wait_on_buffer (bh);
443         }
444 ****/
445         if (j >= es->s_blocks_count) {
446                 printf ( "ext2_new_block: "
447                             "block >= blocks count - "
448                             "block_group = %d, block=%d", i, j);
449                 unlock_super (VFSTOEXT2(mp)->um_devvp);
450                 return 0;
451         }
452
453         ext2_debug ("allocating block %d. "
454                     "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
455
456         gdp->bg_free_blocks_count--;
457         mark_buffer_dirty(bh2);
458         es->s_free_blocks_count--;
459         sb->s_dirt = 1;
460         unlock_super (VFSTOEXT2(mp)->um_devvp);
461         return j;
462 }
463
464 #ifdef unused
465 static unsigned long
466 ext2_count_free_blocks(struct mount * mp)
467 {
468         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
469 #ifdef EXT2FS_DEBUG
470         struct ext2_super_block * es;
471         unsigned long desc_count, bitmap_count, x;
472         int bitmap_nr;
473         struct ext2_group_desc * gdp;
474         int i;
475         
476         lock_super (VFSTOEXT2(mp)->um_devvp);
477         es = sb->s_es;
478         desc_count = 0;
479         bitmap_count = 0;
480         gdp = NULL;
481         for (i = 0; i < sb->s_groups_count; i++) {
482                 gdp = get_group_desc (mp, i, NULL);
483                 desc_count += gdp->bg_free_blocks_count;
484                 bitmap_nr = load_block_bitmap (mp, i);
485                 x = ext2_count_free (sb->s_block_bitmap[bitmap_nr],
486                                      sb->s_blocksize);
487                 ext2_debug ("group %d: stored = %d, counted = %lu\n",
488                         i, gdp->bg_free_blocks_count, x);
489                 bitmap_count += x;
490         }
491         ext2_debug( "stored = %lu, computed = %lu, %lu\n",
492                es->s_free_blocks_count, desc_count, bitmap_count);
493         unlock_super (VFSTOEXT2(mp)->um_devvp);
494         return bitmap_count;
495 #else
496         return sb->s_es->s_free_blocks_count;
497 #endif
498 }
499 #endif /* unused */
500
501 static __inline int
502 block_in_use (unsigned long block, struct ext2_sb_info *sb,
503               unsigned char * map)
504 {
505         return test_bit ((block - sb->s_es->s_first_data_block) %
506                          EXT2_BLOCKS_PER_GROUP(sb), map);
507 }
508
509 static int
510 test_root(int a, int b)
511 {
512         if (a == 0)
513                 return 1;
514         while (1) {
515                 if (a == 1)
516                         return 1;
517                 if (a % b)
518                         return 0;
519                 a = a / b;
520         }
521 }
522
523 int
524 ext2_group_sparse(int group)
525 {
526         return (test_root(group, 3) || test_root(group, 5) ||
527                 test_root(group, 7));
528 }
529
530 #ifdef unused
531 static void
532 ext2_check_blocks_bitmap(struct mount * mp)
533 {
534         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
535         struct buffer_head * bh;
536         struct ext2_super_block * es;
537         unsigned long desc_count, bitmap_count, x;
538         unsigned long desc_blocks;
539         int bitmap_nr;
540         struct ext2_group_desc * gdp;
541         int i, j;
542
543         lock_super (VFSTOEXT2(mp)->um_devvp);
544         es = sb->s_es;
545         desc_count = 0;
546         bitmap_count = 0;
547         gdp = NULL;
548         desc_blocks = (sb->s_groups_count + EXT2_DESC_PER_BLOCK(sb) - 1) /
549                       EXT2_DESC_PER_BLOCK(sb);
550         for (i = 0; i < sb->s_groups_count; i++) {
551                 gdp = get_group_desc (mp, i, NULL);
552                 desc_count += gdp->bg_free_blocks_count;
553                 bitmap_nr = load_block_bitmap (mp, i);
554                 bh = sb->s_block_bitmap[bitmap_nr];
555
556                 if (!(es->s_feature_ro_compat &
557                      EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER) ||
558                     ext2_group_sparse(i)) {
559                         if (!test_bit (0, bh->b_data))
560                                 printf ("ext2_check_blocks_bitmap: "
561                                             "Superblock in group %d "
562                                             "is marked free", i);
563
564                         for (j = 0; j < desc_blocks; j++)
565                                 if (!test_bit (j + 1, bh->b_data))
566                                         printf ("ext2_check_blocks_bitmap: "
567                                             "Descriptor block #%d in group "
568                                             "%d is marked free", j, i);
569                 }
570
571                 if (!block_in_use (gdp->bg_block_bitmap, sb, bh->b_data))
572                         printf ("ext2_check_blocks_bitmap: "
573                                     "Block bitmap for group %d is marked free",
574                                     i);
575
576                 if (!block_in_use (gdp->bg_inode_bitmap, sb, bh->b_data))
577                         printf ("ext2_check_blocks_bitmap: "
578                                     "Inode bitmap for group %d is marked free",
579                                     i);
580
581                 for (j = 0; j < sb->s_itb_per_group; j++)
582                         if (!block_in_use (gdp->bg_inode_table + j, sb, bh->b_data))
583                                 printf ("ext2_check_blocks_bitmap: "
584                                             "Block #%d of the inode table in "
585                                             "group %d is marked free", j, i);
586
587                 x = ext2_count_free (bh, sb->s_blocksize);
588                 if (gdp->bg_free_blocks_count != x)
589                         printf ("ext2_check_blocks_bitmap: "
590                                     "Wrong free blocks count for group %d, "
591                                     "stored = %d, counted = %lu", i,
592                                     gdp->bg_free_blocks_count, x);
593                 bitmap_count += x;
594         }
595         if (es->s_free_blocks_count != bitmap_count)
596                 printf ("ext2_check_blocks_bitmap: "
597                             "Wrong free blocks count in super block, "
598                             "stored = %lu, counted = %lu",
599                             (unsigned long) es->s_free_blocks_count, bitmap_count);
600         unlock_super (VFSTOEXT2(mp)->um_devvp);
601 }
602 #endif /* unused */
603
604 /*
605  *  this function is taken from 
606  *  linux/fs/ext2/bitmap.c
607  */
608
609 static int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
610
611 unsigned long ext2_count_free (struct buffer_head * map, unsigned int numchars)
612 {
613         unsigned int i;
614         unsigned long sum = 0;
615
616         if (!map)
617                 return (0);
618         for (i = 0; i < numchars; i++)
619                 sum += nibblemap[map->b_data[i] & 0xf] +
620                         nibblemap[(map->b_data[i] >> 4) & 0xf];
621         return (sum);
622 }