tun: Limit amount of queued packets per device
[linux-2.6] / fs / affs / bitmap.c
1 /*
2  *  linux/fs/affs/bitmap.c
3  *
4  *  (c) 1996 Hans-Joachim Widmaier
5  *
6  *  bitmap.c contains the code that handles all bitmap related stuff -
7  *  block allocation, deallocation, calculation of free space.
8  */
9
10 #include "affs.h"
11
12 /* This is, of course, shamelessly stolen from fs/minix */
13
14 static const int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
15
16 static u32
17 affs_count_free_bits(u32 blocksize, const void *data)
18 {
19         const u32 *map;
20         u32 free;
21         u32 tmp;
22
23         map = data;
24         free = 0;
25         for (blocksize /= 4; blocksize > 0; blocksize--) {
26                 tmp = *map++;
27                 while (tmp) {
28                         free += nibblemap[tmp & 0xf];
29                         tmp >>= 4;
30                 }
31         }
32
33         return free;
34 }
35
36 u32
37 affs_count_free_blocks(struct super_block *sb)
38 {
39         struct affs_bm_info *bm;
40         u32 free;
41         int i;
42
43         pr_debug("AFFS: count_free_blocks()\n");
44
45         if (sb->s_flags & MS_RDONLY)
46                 return 0;
47
48         mutex_lock(&AFFS_SB(sb)->s_bmlock);
49
50         bm = AFFS_SB(sb)->s_bitmap;
51         free = 0;
52         for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
53                 free += bm->bm_free;
54
55         mutex_unlock(&AFFS_SB(sb)->s_bmlock);
56
57         return free;
58 }
59
60 void
61 affs_free_block(struct super_block *sb, u32 block)
62 {
63         struct affs_sb_info *sbi = AFFS_SB(sb);
64         struct affs_bm_info *bm;
65         struct buffer_head *bh;
66         u32 blk, bmap, bit, mask, tmp;
67         __be32 *data;
68
69         pr_debug("AFFS: free_block(%u)\n", block);
70
71         if (block > sbi->s_partition_size)
72                 goto err_range;
73
74         blk     = block - sbi->s_reserved;
75         bmap    = blk / sbi->s_bmap_bits;
76         bit     = blk % sbi->s_bmap_bits;
77         bm      = &sbi->s_bitmap[bmap];
78
79         mutex_lock(&sbi->s_bmlock);
80
81         bh = sbi->s_bmap_bh;
82         if (sbi->s_last_bmap != bmap) {
83                 affs_brelse(bh);
84                 bh = affs_bread(sb, bm->bm_key);
85                 if (!bh)
86                         goto err_bh_read;
87                 sbi->s_bmap_bh = bh;
88                 sbi->s_last_bmap = bmap;
89         }
90
91         mask = 1 << (bit & 31);
92         data = (__be32 *)bh->b_data + bit / 32 + 1;
93
94         /* mark block free */
95         tmp = be32_to_cpu(*data);
96         if (tmp & mask)
97                 goto err_free;
98         *data = cpu_to_be32(tmp | mask);
99
100         /* fix checksum */
101         tmp = be32_to_cpu(*(__be32 *)bh->b_data);
102         *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
103
104         mark_buffer_dirty(bh);
105         sb->s_dirt = 1;
106         bm->bm_free++;
107
108         mutex_unlock(&sbi->s_bmlock);
109         return;
110
111 err_free:
112         affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
113         mutex_unlock(&sbi->s_bmlock);
114         return;
115
116 err_bh_read:
117         affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
118         sbi->s_bmap_bh = NULL;
119         sbi->s_last_bmap = ~0;
120         mutex_unlock(&sbi->s_bmlock);
121         return;
122
123 err_range:
124         affs_error(sb, "affs_free_block","Block %u outside partition", block);
125         return;
126 }
127
128 /*
129  * Allocate a block in the given allocation zone.
130  * Since we have to byte-swap the bitmap on little-endian
131  * machines, this is rather expensive. Therefor we will
132  * preallocate up to 16 blocks from the same word, if
133  * possible. We are not doing preallocations in the
134  * header zone, though.
135  */
136
137 u32
138 affs_alloc_block(struct inode *inode, u32 goal)
139 {
140         struct super_block *sb;
141         struct affs_sb_info *sbi;
142         struct affs_bm_info *bm;
143         struct buffer_head *bh;
144         __be32 *data, *enddata;
145         u32 blk, bmap, bit, mask, mask2, tmp;
146         int i;
147
148         sb = inode->i_sb;
149         sbi = AFFS_SB(sb);
150
151         pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
152
153         if (AFFS_I(inode)->i_pa_cnt) {
154                 pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
155                 AFFS_I(inode)->i_pa_cnt--;
156                 return ++AFFS_I(inode)->i_lastalloc;
157         }
158
159         if (!goal || goal > sbi->s_partition_size) {
160                 if (goal)
161                         affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
162                 //if (!AFFS_I(inode)->i_last_block)
163                 //      affs_warning(sb, "affs_balloc", "no last alloc block");
164                 goal = sbi->s_reserved;
165         }
166
167         blk = goal - sbi->s_reserved;
168         bmap = blk / sbi->s_bmap_bits;
169         bm = &sbi->s_bitmap[bmap];
170
171         mutex_lock(&sbi->s_bmlock);
172
173         if (bm->bm_free)
174                 goto find_bmap_bit;
175
176 find_bmap:
177         /* search for the next bmap buffer with free bits */
178         i = sbi->s_bmap_count;
179         do {
180                 if (--i < 0)
181                         goto err_full;
182                 bmap++;
183                 bm++;
184                 if (bmap < sbi->s_bmap_count)
185                         continue;
186                 /* restart search at zero */
187                 bmap = 0;
188                 bm = sbi->s_bitmap;
189         } while (!bm->bm_free);
190         blk = bmap * sbi->s_bmap_bits;
191
192 find_bmap_bit:
193
194         bh = sbi->s_bmap_bh;
195         if (sbi->s_last_bmap != bmap) {
196                 affs_brelse(bh);
197                 bh = affs_bread(sb, bm->bm_key);
198                 if (!bh)
199                         goto err_bh_read;
200                 sbi->s_bmap_bh = bh;
201                 sbi->s_last_bmap = bmap;
202         }
203
204         /* find an unused block in this bitmap block */
205         bit = blk % sbi->s_bmap_bits;
206         data = (__be32 *)bh->b_data + bit / 32 + 1;
207         enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
208         mask = ~0UL << (bit & 31);
209         blk &= ~31UL;
210
211         tmp = be32_to_cpu(*data);
212         if (tmp & mask)
213                 goto find_bit;
214
215         /* scan the rest of the buffer */
216         do {
217                 blk += 32;
218                 if (++data >= enddata)
219                         /* didn't find something, can only happen
220                          * if scan didn't start at 0, try next bmap
221                          */
222                         goto find_bmap;
223         } while (!*data);
224         tmp = be32_to_cpu(*data);
225         mask = ~0;
226
227 find_bit:
228         /* finally look for a free bit in the word */
229         bit = ffs(tmp & mask) - 1;
230         blk += bit + sbi->s_reserved;
231         mask2 = mask = 1 << (bit & 31);
232         AFFS_I(inode)->i_lastalloc = blk;
233
234         /* prealloc as much as possible within this word */
235         while ((mask2 <<= 1)) {
236                 if (!(tmp & mask2))
237                         break;
238                 AFFS_I(inode)->i_pa_cnt++;
239                 mask |= mask2;
240         }
241         bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
242
243         *data = cpu_to_be32(tmp & ~mask);
244
245         /* fix checksum */
246         tmp = be32_to_cpu(*(__be32 *)bh->b_data);
247         *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
248
249         mark_buffer_dirty(bh);
250         sb->s_dirt = 1;
251
252         mutex_unlock(&sbi->s_bmlock);
253
254         pr_debug("%d\n", blk);
255         return blk;
256
257 err_bh_read:
258         affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
259         sbi->s_bmap_bh = NULL;
260         sbi->s_last_bmap = ~0;
261 err_full:
262         mutex_unlock(&sbi->s_bmlock);
263         pr_debug("failed\n");
264         return 0;
265 }
266
267 int affs_init_bitmap(struct super_block *sb, int *flags)
268 {
269         struct affs_bm_info *bm;
270         struct buffer_head *bmap_bh = NULL, *bh = NULL;
271         __be32 *bmap_blk;
272         u32 size, blk, end, offset, mask;
273         int i, res = 0;
274         struct affs_sb_info *sbi = AFFS_SB(sb);
275
276         if (*flags & MS_RDONLY)
277                 return 0;
278
279         if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
280                 printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
281                         sb->s_id);
282                 *flags |= MS_RDONLY;
283                 return 0;
284         }
285
286         sbi->s_last_bmap = ~0;
287         sbi->s_bmap_bh = NULL;
288         sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
289         sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
290                                  sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
291         size = sbi->s_bmap_count * sizeof(*bm);
292         bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
293         if (!sbi->s_bitmap) {
294                 printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
295                 return -ENOMEM;
296         }
297
298         bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
299         blk = sb->s_blocksize / 4 - 49;
300         end = blk + 25;
301
302         for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
303                 affs_brelse(bh);
304
305                 bm->bm_key = be32_to_cpu(bmap_blk[blk]);
306                 bh = affs_bread(sb, bm->bm_key);
307                 if (!bh) {
308                         printk(KERN_ERR "AFFS: Cannot read bitmap\n");
309                         res = -EIO;
310                         goto out;
311                 }
312                 if (affs_checksum_block(sb, bh)) {
313                         printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
314                                bm->bm_key, sb->s_id);
315                         *flags |= MS_RDONLY;
316                         goto out;
317                 }
318                 pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
319                 bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
320
321                 /* Don't try read the extension if this is the last block,
322                  * but we also need the right bm pointer below
323                  */
324                 if (++blk < end || i == 1)
325                         continue;
326                 if (bmap_bh)
327                         affs_brelse(bmap_bh);
328                 bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
329                 if (!bmap_bh) {
330                         printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
331                         res = -EIO;
332                         goto out;
333                 }
334                 bmap_blk = (__be32 *)bmap_bh->b_data;
335                 blk = 0;
336                 end = sb->s_blocksize / 4 - 1;
337         }
338
339         offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
340         mask = ~(0xFFFFFFFFU << (offset & 31));
341         pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
342         offset = offset / 32 + 1;
343
344         if (mask) {
345                 u32 old, new;
346
347                 /* Mark unused bits in the last word as allocated */
348                 old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
349                 new = old & mask;
350                 //if (old != new) {
351                         ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
352                         /* fix checksum */
353                         //new -= old;
354                         //old = be32_to_cpu(*(__be32 *)bh->b_data);
355                         //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
356                         //mark_buffer_dirty(bh);
357                 //}
358                 /* correct offset for the bitmap count below */
359                 //offset++;
360         }
361         while (++offset < sb->s_blocksize / 4)
362                 ((__be32 *)bh->b_data)[offset] = 0;
363         ((__be32 *)bh->b_data)[0] = 0;
364         ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
365         mark_buffer_dirty(bh);
366
367         /* recalculate bitmap count for last block */
368         bm--;
369         bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
370
371 out:
372         affs_brelse(bh);
373         affs_brelse(bmap_bh);
374         return res;
375 }
376
377 void affs_free_bitmap(struct super_block *sb)
378 {
379         struct affs_sb_info *sbi = AFFS_SB(sb);
380
381         if (!sbi->s_bitmap)
382                 return;
383
384         affs_brelse(sbi->s_bmap_bh);
385         sbi->s_bmap_bh = NULL;
386         sbi->s_last_bmap = ~0;
387         kfree(sbi->s_bitmap);
388         sbi->s_bitmap = NULL;
389 }