[PATCH] capable/capability.h (fs/)
[linux-2.6.git] / fs / ufs / balloc.c
1 /*
2  *  linux/fs/ufs/balloc.c
3  *
4  * Copyright (C) 1998
5  * Daniel Pirkl <daniel.pirkl@email.cz>
6  * Charles University, Faculty of Mathematics and Physics
7  */
8
9 #include <linux/fs.h>
10 #include <linux/ufs_fs.h>
11 #include <linux/stat.h>
12 #include <linux/time.h>
13 #include <linux/string.h>
14 #include <linux/quotaops.h>
15 #include <linux/buffer_head.h>
16 #include <linux/capability.h>
17 #include <linux/sched.h>
18 #include <linux/bitops.h>
19 #include <asm/byteorder.h>
20
21 #include "swab.h"
22 #include "util.h"
23
24 #undef UFS_BALLOC_DEBUG
25
26 #ifdef UFS_BALLOC_DEBUG
27 #define UFSD(x) printk("(%s, %d), %s:", __FILE__, __LINE__, __FUNCTION__); printk x;
28 #else
29 #define UFSD(x)
30 #endif
31
32 static unsigned ufs_add_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
33 static unsigned ufs_alloc_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
34 static unsigned ufs_alloccg_block (struct inode *, struct ufs_cg_private_info *, unsigned, int *);
35 static unsigned ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, unsigned, unsigned);
36 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
37 static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
38
39 /*
40  * Free 'count' fragments from fragment number 'fragment'
41  */
42 void ufs_free_fragments (struct inode * inode, unsigned fragment, unsigned count) {
43         struct super_block * sb;
44         struct ufs_sb_private_info * uspi;
45         struct ufs_super_block_first * usb1;
46         struct ufs_cg_private_info * ucpi;
47         struct ufs_cylinder_group * ucg;
48         unsigned cgno, bit, end_bit, bbase, blkmap, i, blkno, cylno;
49         
50         sb = inode->i_sb;
51         uspi = UFS_SB(sb)->s_uspi;
52         usb1 = ubh_get_usb_first(USPI_UBH);
53         
54         UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
55         
56         if (ufs_fragnum(fragment) + count > uspi->s_fpg)
57                 ufs_error (sb, "ufs_free_fragments", "internal error");
58         
59         lock_super(sb);
60         
61         cgno = ufs_dtog(fragment);
62         bit = ufs_dtogd(fragment);
63         if (cgno >= uspi->s_ncg) {
64                 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
65                 goto failed;
66         }
67                 
68         ucpi = ufs_load_cylinder (sb, cgno);
69         if (!ucpi) 
70                 goto failed;
71         ucg = ubh_get_ucg (UCPI_UBH);
72         if (!ufs_cg_chkmagic(sb, ucg)) {
73                 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
74                 goto failed;
75         }
76
77         end_bit = bit + count;
78         bbase = ufs_blknum (bit);
79         blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
80         ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
81         for (i = bit; i < end_bit; i++) {
82                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, i))
83                         ubh_setbit (UCPI_UBH, ucpi->c_freeoff, i);
84                 else ufs_error (sb, "ufs_free_fragments",
85                         "bit already cleared for fragment %u", i);
86         }
87         
88         DQUOT_FREE_BLOCK (inode, count);
89
90         
91         fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
92         fs32_add(sb, &usb1->fs_cstotal.cs_nffree, count);
93         fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
94         blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
95         ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
96
97         /*
98          * Trying to reassemble free fragments into block
99          */
100         blkno = ufs_fragstoblks (bbase);
101         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
102                 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
103                 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, uspi->s_fpb);
104                 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
105                 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
106                         ufs_clusteracct (sb, ucpi, blkno, 1);
107                 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
108                 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
109                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
110                 cylno = ufs_cbtocylno (bbase);
111                 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(bbase)), 1);
112                 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
113         }
114         
115         ubh_mark_buffer_dirty (USPI_UBH);
116         ubh_mark_buffer_dirty (UCPI_UBH);
117         if (sb->s_flags & MS_SYNCHRONOUS) {
118                 ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
119                 ubh_wait_on_buffer (UCPI_UBH);
120         }
121         sb->s_dirt = 1;
122         
123         unlock_super (sb);
124         UFSD(("EXIT\n"))
125         return;
126
127 failed:
128         unlock_super (sb);
129         UFSD(("EXIT (FAILED)\n"))
130         return;
131 }
132
133 /*
134  * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
135  */
136 void ufs_free_blocks (struct inode * inode, unsigned fragment, unsigned count) {
137         struct super_block * sb;
138         struct ufs_sb_private_info * uspi;
139         struct ufs_super_block_first * usb1;
140         struct ufs_cg_private_info * ucpi;
141         struct ufs_cylinder_group * ucg;
142         unsigned overflow, cgno, bit, end_bit, blkno, i, cylno;
143         
144         sb = inode->i_sb;
145         uspi = UFS_SB(sb)->s_uspi;
146         usb1 = ubh_get_usb_first(USPI_UBH);
147
148         UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
149         
150         if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
151                 ufs_error (sb, "ufs_free_blocks", "internal error, "
152                         "fragment %u, count %u\n", fragment, count);
153                 goto failed;
154         }
155
156         lock_super(sb);
157         
158 do_more:
159         overflow = 0;
160         cgno = ufs_dtog (fragment);
161         bit = ufs_dtogd (fragment);
162         if (cgno >= uspi->s_ncg) {
163                 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
164                 goto failed;
165         }
166         end_bit = bit + count;
167         if (end_bit > uspi->s_fpg) {
168                 overflow = bit + count - uspi->s_fpg;
169                 count -= overflow;
170                 end_bit -= overflow;
171         }
172
173         ucpi = ufs_load_cylinder (sb, cgno);
174         if (!ucpi) 
175                 goto failed;
176         ucg = ubh_get_ucg (UCPI_UBH);
177         if (!ufs_cg_chkmagic(sb, ucg)) {
178                 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
179                 goto failed;
180         }
181
182         for (i = bit; i < end_bit; i += uspi->s_fpb) {
183                 blkno = ufs_fragstoblks(i);
184                 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
185                         ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
186                 }
187                 ubh_setblock(UCPI_UBH, ucpi->c_freeoff, blkno);
188                 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
189                         ufs_clusteracct (sb, ucpi, blkno, 1);
190                 DQUOT_FREE_BLOCK(inode, uspi->s_fpb);
191
192                 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
193                 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
194                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
195                 cylno = ufs_cbtocylno(i);
196                 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(i)), 1);
197                 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
198         }
199
200         ubh_mark_buffer_dirty (USPI_UBH);
201         ubh_mark_buffer_dirty (UCPI_UBH);
202         if (sb->s_flags & MS_SYNCHRONOUS) {
203                 ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
204                 ubh_wait_on_buffer (UCPI_UBH);
205         }
206
207         if (overflow) {
208                 fragment += count;
209                 count = overflow;
210                 goto do_more;
211         }
212
213         sb->s_dirt = 1;
214         unlock_super (sb);
215         UFSD(("EXIT\n"))
216         return;
217
218 failed:
219         unlock_super (sb);
220         UFSD(("EXIT (FAILED)\n"))
221         return;
222 }
223
224
225
226 #define NULLIFY_FRAGMENTS \
227         for (i = oldcount; i < newcount; i++) { \
228                 bh = sb_getblk(sb, result + i); \
229                 memset (bh->b_data, 0, sb->s_blocksize); \
230                 set_buffer_uptodate(bh); \
231                 mark_buffer_dirty (bh); \
232                 if (IS_SYNC(inode)) \
233                         sync_dirty_buffer(bh); \
234                 brelse (bh); \
235         }
236
237 unsigned ufs_new_fragments (struct inode * inode, __fs32 * p, unsigned fragment,
238         unsigned goal, unsigned count, int * err )
239 {
240         struct super_block * sb;
241         struct ufs_sb_private_info * uspi;
242         struct ufs_super_block_first * usb1;
243         struct buffer_head * bh;
244         unsigned cgno, oldcount, newcount, tmp, request, i, result;
245         
246         UFSD(("ENTER, ino %lu, fragment %u, goal %u, count %u\n", inode->i_ino, fragment, goal, count))
247         
248         sb = inode->i_sb;
249         uspi = UFS_SB(sb)->s_uspi;
250         usb1 = ubh_get_usb_first(USPI_UBH);
251         *err = -ENOSPC;
252
253         lock_super (sb);
254         
255         tmp = fs32_to_cpu(sb, *p);
256         if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
257                 ufs_warning (sb, "ufs_new_fragments", "internal warning"
258                         " fragment %u, count %u", fragment, count);
259                 count = uspi->s_fpb - ufs_fragnum(fragment); 
260         }
261         oldcount = ufs_fragnum (fragment);
262         newcount = oldcount + count;
263
264         /*
265          * Somebody else has just allocated our fragments
266          */
267         if (oldcount) {
268                 if (!tmp) {
269                         ufs_error (sb, "ufs_new_fragments", "internal error, "
270                                 "fragment %u, tmp %u\n", fragment, tmp);
271                         unlock_super (sb);
272                         return (unsigned)-1;
273                 }
274                 if (fragment < UFS_I(inode)->i_lastfrag) {
275                         UFSD(("EXIT (ALREADY ALLOCATED)\n"))
276                         unlock_super (sb);
277                         return 0;
278                 }
279         }
280         else {
281                 if (tmp) {
282                         UFSD(("EXIT (ALREADY ALLOCATED)\n"))
283                         unlock_super(sb);
284                         return 0;
285                 }
286         }
287
288         /*
289          * There is not enough space for user on the device
290          */
291         if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(usb1, UFS_MINFREE) <= 0) {
292                 unlock_super (sb);
293                 UFSD(("EXIT (FAILED)\n"))
294                 return 0;
295         }
296
297         if (goal >= uspi->s_size) 
298                 goal = 0;
299         if (goal == 0) 
300                 cgno = ufs_inotocg (inode->i_ino);
301         else
302                 cgno = ufs_dtog (goal);
303          
304         /*
305          * allocate new fragment
306          */
307         if (oldcount == 0) {
308                 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
309                 if (result) {
310                         *p = cpu_to_fs32(sb, result);
311                         *err = 0;
312                         inode->i_blocks += count << uspi->s_nspfshift;
313                         UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
314                         NULLIFY_FRAGMENTS
315                 }
316                 unlock_super(sb);
317                 UFSD(("EXIT, result %u\n", result))
318                 return result;
319         }
320
321         /*
322          * resize block
323          */
324         result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
325         if (result) {
326                 *err = 0;
327                 inode->i_blocks += count << uspi->s_nspfshift;
328                 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
329                 NULLIFY_FRAGMENTS
330                 unlock_super(sb);
331                 UFSD(("EXIT, result %u\n", result))
332                 return result;
333         }
334
335         /*
336          * allocate new block and move data
337          */
338         switch (fs32_to_cpu(sb, usb1->fs_optim)) {
339             case UFS_OPTSPACE:
340                 request = newcount;
341                 if (uspi->s_minfree < 5 || fs32_to_cpu(sb, usb1->fs_cstotal.cs_nffree) 
342                     > uspi->s_dsize * uspi->s_minfree / (2 * 100) )
343                         break;
344                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
345                 break;
346             default:
347                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
348         
349             case UFS_OPTTIME:
350                 request = uspi->s_fpb;
351                 if (fs32_to_cpu(sb, usb1->fs_cstotal.cs_nffree) < uspi->s_dsize *
352                     (uspi->s_minfree - 2) / 100)
353                         break;
354                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
355                 break;
356         }
357         result = ufs_alloc_fragments (inode, cgno, goal, request, err);
358         if (result) {
359                 for (i = 0; i < oldcount; i++) {
360                         bh = sb_bread(sb, tmp + i);
361                         if(bh)
362                         {
363                                 clear_buffer_dirty(bh);
364                                 bh->b_blocknr = result + i;
365                                 mark_buffer_dirty (bh);
366                                 if (IS_SYNC(inode))
367                                         sync_dirty_buffer(bh);
368                                 brelse (bh);
369                         }
370                         else
371                         {
372                                 printk(KERN_ERR "ufs_new_fragments: bread fail\n");
373                                 unlock_super(sb);
374                                 return 0;
375                         }
376                 }
377                 *p = cpu_to_fs32(sb, result);
378                 *err = 0;
379                 inode->i_blocks += count << uspi->s_nspfshift;
380                 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
381                 NULLIFY_FRAGMENTS
382                 unlock_super(sb);
383                 if (newcount < request)
384                         ufs_free_fragments (inode, result + newcount, request - newcount);
385                 ufs_free_fragments (inode, tmp, oldcount);
386                 UFSD(("EXIT, result %u\n", result))
387                 return result;
388         }
389
390         unlock_super(sb);
391         UFSD(("EXIT (FAILED)\n"))
392         return 0;
393 }               
394
395 static unsigned
396 ufs_add_fragments (struct inode * inode, unsigned fragment,
397                    unsigned oldcount, unsigned newcount, int * err)
398 {
399         struct super_block * sb;
400         struct ufs_sb_private_info * uspi;
401         struct ufs_super_block_first * usb1;
402         struct ufs_cg_private_info * ucpi;
403         struct ufs_cylinder_group * ucg;
404         unsigned cgno, fragno, fragoff, count, fragsize, i;
405         
406         UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
407         
408         sb = inode->i_sb;
409         uspi = UFS_SB(sb)->s_uspi;
410         usb1 = ubh_get_usb_first (USPI_UBH);
411         count = newcount - oldcount;
412         
413         cgno = ufs_dtog(fragment);
414         if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
415                 return 0;
416         if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
417                 return 0;
418         ucpi = ufs_load_cylinder (sb, cgno);
419         if (!ucpi)
420                 return 0;
421         ucg = ubh_get_ucg (UCPI_UBH);
422         if (!ufs_cg_chkmagic(sb, ucg)) {
423                 ufs_panic (sb, "ufs_add_fragments",
424                         "internal error, bad magic number on cg %u", cgno);
425                 return 0;
426         }
427
428         fragno = ufs_dtogd (fragment);
429         fragoff = ufs_fragnum (fragno);
430         for (i = oldcount; i < newcount; i++)
431                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
432                         return 0;
433         /*
434          * Block can be extended
435          */
436         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
437         for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
438                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
439                         break;
440         fragsize = i - oldcount;
441         if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
442                 ufs_panic (sb, "ufs_add_fragments",
443                         "internal error or corrupted bitmap on cg %u", cgno);
444         fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
445         if (fragsize != count)
446                 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
447         for (i = oldcount; i < newcount; i++)
448                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
449         if(DQUOT_ALLOC_BLOCK(inode, count)) {
450                 *err = -EDQUOT;
451                 return 0;
452         }
453
454         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
455         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
456         fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
457         
458         ubh_mark_buffer_dirty (USPI_UBH);
459         ubh_mark_buffer_dirty (UCPI_UBH);
460         if (sb->s_flags & MS_SYNCHRONOUS) {
461                 ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
462                 ubh_wait_on_buffer (UCPI_UBH);
463         }
464         sb->s_dirt = 1;
465
466         UFSD(("EXIT, fragment %u\n", fragment))
467         
468         return fragment;
469 }
470
471 #define UFS_TEST_FREE_SPACE_CG \
472         ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
473         if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
474                 goto cg_found; \
475         for (k = count; k < uspi->s_fpb; k++) \
476                 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
477                         goto cg_found; 
478
479 static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
480         unsigned goal, unsigned count, int * err)
481 {
482         struct super_block * sb;
483         struct ufs_sb_private_info * uspi;
484         struct ufs_super_block_first * usb1;
485         struct ufs_cg_private_info * ucpi;
486         struct ufs_cylinder_group * ucg;
487         unsigned oldcg, i, j, k, result, allocsize;
488         
489         UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
490
491         sb = inode->i_sb;
492         uspi = UFS_SB(sb)->s_uspi;
493         usb1 = ubh_get_usb_first(USPI_UBH);
494         oldcg = cgno;
495         
496         /*
497          * 1. searching on preferred cylinder group
498          */
499         UFS_TEST_FREE_SPACE_CG
500
501         /*
502          * 2. quadratic rehash
503          */
504         for (j = 1; j < uspi->s_ncg; j *= 2) {
505                 cgno += j;
506                 if (cgno >= uspi->s_ncg) 
507                         cgno -= uspi->s_ncg;
508                 UFS_TEST_FREE_SPACE_CG
509         }
510
511         /*
512          * 3. brute force search
513          * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
514          */
515         cgno = (oldcg + 1) % uspi->s_ncg;
516         for (j = 2; j < uspi->s_ncg; j++) {
517                 cgno++;
518                 if (cgno >= uspi->s_ncg)
519                         cgno = 0;
520                 UFS_TEST_FREE_SPACE_CG
521         }
522         
523         UFSD(("EXIT (FAILED)\n"))
524         return 0;
525
526 cg_found:
527         ucpi = ufs_load_cylinder (sb, cgno);
528         if (!ucpi)
529                 return 0;
530         ucg = ubh_get_ucg (UCPI_UBH);
531         if (!ufs_cg_chkmagic(sb, ucg)) 
532                 ufs_panic (sb, "ufs_alloc_fragments",
533                         "internal error, bad magic number on cg %u", cgno);
534         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
535
536         if (count == uspi->s_fpb) {
537                 result = ufs_alloccg_block (inode, ucpi, goal, err);
538                 if (result == (unsigned)-1)
539                         return 0;
540                 goto succed;
541         }
542
543         for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
544                 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
545                         break;
546         
547         if (allocsize == uspi->s_fpb) {
548                 result = ufs_alloccg_block (inode, ucpi, goal, err);
549                 if (result == (unsigned)-1)
550                         return 0;
551                 goal = ufs_dtogd (result);
552                 for (i = count; i < uspi->s_fpb; i++)
553                         ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
554                 i = uspi->s_fpb - count;
555                 DQUOT_FREE_BLOCK(inode, i);
556
557                 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
558                 fs32_add(sb, &usb1->fs_cstotal.cs_nffree, i);
559                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
560                 fs32_add(sb, &ucg->cg_frsum[i], 1);
561                 goto succed;
562         }
563
564         result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
565         if (result == (unsigned)-1)
566                 return 0;
567         if(DQUOT_ALLOC_BLOCK(inode, count)) {
568                 *err = -EDQUOT;
569                 return 0;
570         }
571         for (i = 0; i < count; i++)
572                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
573         
574         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
575         fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
576         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
577         fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
578
579         if (count != allocsize)
580                 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
581
582 succed:
583         ubh_mark_buffer_dirty (USPI_UBH);
584         ubh_mark_buffer_dirty (UCPI_UBH);
585         if (sb->s_flags & MS_SYNCHRONOUS) {
586                 ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
587                 ubh_wait_on_buffer (UCPI_UBH);
588         }
589         sb->s_dirt = 1;
590
591         result += cgno * uspi->s_fpg;
592         UFSD(("EXIT3, result %u\n", result))
593         return result;
594 }
595
596 static unsigned ufs_alloccg_block (struct inode * inode,
597         struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
598 {
599         struct super_block * sb;
600         struct ufs_sb_private_info * uspi;
601         struct ufs_super_block_first * usb1;
602         struct ufs_cylinder_group * ucg;
603         unsigned result, cylno, blkno;
604
605         UFSD(("ENTER, goal %u\n", goal))
606
607         sb = inode->i_sb;
608         uspi = UFS_SB(sb)->s_uspi;
609         usb1 = ubh_get_usb_first(USPI_UBH);
610         ucg = ubh_get_ucg(UCPI_UBH);
611
612         if (goal == 0) {
613                 goal = ucpi->c_rotor;
614                 goto norot;
615         }
616         goal = ufs_blknum (goal);
617         goal = ufs_dtogd (goal);
618         
619         /*
620          * If the requested block is available, use it.
621          */
622         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
623                 result = goal;
624                 goto gotit;
625         }
626         
627 norot:  
628         result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
629         if (result == (unsigned)-1)
630                 return (unsigned)-1;
631         ucpi->c_rotor = result;
632 gotit:
633         blkno = ufs_fragstoblks(result);
634         ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
635         if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
636                 ufs_clusteracct (sb, ucpi, blkno, -1);
637         if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
638                 *err = -EDQUOT;
639                 return (unsigned)-1;
640         }
641
642         fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
643         fs32_sub(sb, &usb1->fs_cstotal.cs_nbfree, 1);
644         fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
645         cylno = ufs_cbtocylno(result);
646         fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1);
647         fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
648         
649         UFSD(("EXIT, result %u\n", result))
650
651         return result;
652 }
653
654 static unsigned ufs_bitmap_search (struct super_block * sb,
655         struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
656 {
657         struct ufs_sb_private_info * uspi;
658         struct ufs_super_block_first * usb1;
659         struct ufs_cylinder_group * ucg;
660         unsigned start, length, location, result;
661         unsigned possition, fragsize, blockmap, mask;
662         
663         UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
664
665         uspi = UFS_SB(sb)->s_uspi;
666         usb1 = ubh_get_usb_first (USPI_UBH);
667         ucg = ubh_get_ucg(UCPI_UBH);
668
669         if (goal)
670                 start = ufs_dtogd(goal) >> 3;
671         else
672                 start = ucpi->c_frotor >> 3;
673                 
674         length = ((uspi->s_fpg + 7) >> 3) - start;
675         location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
676                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
677                 1 << (count - 1 + (uspi->s_fpb & 7))); 
678         if (location == 0) {
679                 length = start + 1;
680                 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length, 
681                         (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
682                         1 << (count - 1 + (uspi->s_fpb & 7)));
683                 if (location == 0) {
684                         ufs_error (sb, "ufs_bitmap_search",
685                         "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
686                         ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
687                         return (unsigned)-1;
688                 }
689                 start = 0;
690         }
691         result = (start + length - location) << 3;
692         ucpi->c_frotor = result;
693
694         /*
695          * found the byte in the map
696          */
697         blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
698         fragsize = 0;
699         for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
700                 if (blockmap & mask) {
701                         if (!(possition & uspi->s_fpbmask))
702                                 fragsize = 1;
703                         else 
704                                 fragsize++;
705                 }
706                 else {
707                         if (fragsize == count) {
708                                 result += possition - count;
709                                 UFSD(("EXIT, result %u\n", result))
710                                 return result;
711                         }
712                         fragsize = 0;
713                 }
714         }
715         if (fragsize == count) {
716                 result += possition - count;
717                 UFSD(("EXIT, result %u\n", result))
718                 return result;
719         }
720         ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
721         UFSD(("EXIT (FAILED)\n"))
722         return (unsigned)-1;
723 }
724
725 static void ufs_clusteracct(struct super_block * sb,
726         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
727 {
728         struct ufs_sb_private_info * uspi;
729         int i, start, end, forw, back;
730         
731         uspi = UFS_SB(sb)->s_uspi;
732         if (uspi->s_contigsumsize <= 0)
733                 return;
734
735         if (cnt > 0)
736                 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
737         else
738                 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
739
740         /*
741          * Find the size of the cluster going forward.
742          */
743         start = blkno + 1;
744         end = start + uspi->s_contigsumsize;
745         if ( end >= ucpi->c_nclusterblks)
746                 end = ucpi->c_nclusterblks;
747         i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
748         if (i > end)
749                 i = end;
750         forw = i - start;
751         
752         /*
753          * Find the size of the cluster going backward.
754          */
755         start = blkno - 1;
756         end = start - uspi->s_contigsumsize;
757         if (end < 0 ) 
758                 end = -1;
759         i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
760         if ( i < end) 
761                 i = end;
762         back = start - i;
763         
764         /*
765          * Account for old cluster and the possibly new forward and
766          * back clusters.
767          */
768         i = back + forw + 1;
769         if (i > uspi->s_contigsumsize)
770                 i = uspi->s_contigsumsize;
771         fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2)), cnt);
772         if (back > 0)
773                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2)), cnt);
774         if (forw > 0)
775                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2)), cnt);
776 }
777
778
779 static unsigned char ufs_fragtable_8fpb[] = {
780         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
781         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
782         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
783         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
784         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 
785         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
786         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
787         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
788         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
789         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
790         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
791         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
792         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
793         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
794         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
795         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
796 };
797
798 static unsigned char ufs_fragtable_other[] = {
799         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
800         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
801         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
802         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
803         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
804         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
805         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
806         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
807         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
808         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
809         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
810         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
811         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
812         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
813         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
814         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
815 };