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