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