Merge branch 'master'
[linux-2.6] / 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);
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 
85                         ufs_error (sb, "ufs_free_fragments",
86                                    "bit already cleared for fragment %u", i);
87         }
88         
89         DQUOT_FREE_BLOCK (inode, count);
90
91         
92         fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
93         fs32_add(sb, &usb1->fs_cstotal.cs_nffree, count);
94         fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
95         blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
96         ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
97
98         /*
99          * Trying to reassemble free fragments into block
100          */
101         blkno = ufs_fragstoblks (bbase);
102         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
103                 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
104                 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, uspi->s_fpb);
105                 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
106                 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
107                         ufs_clusteracct (sb, ucpi, blkno, 1);
108                 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
109                 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
110                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
111                 cylno = ufs_cbtocylno (bbase);
112                 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(bbase)), 1);
113                 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
114         }
115         
116         ubh_mark_buffer_dirty (USPI_UBH);
117         ubh_mark_buffer_dirty (UCPI_UBH);
118         if (sb->s_flags & MS_SYNCHRONOUS) {
119                 ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
120                 ubh_wait_on_buffer (UCPI_UBH);
121         }
122         sb->s_dirt = 1;
123         
124         unlock_super (sb);
125         UFSD(("EXIT\n"))
126         return;
127
128 failed:
129         unlock_super (sb);
130         UFSD(("EXIT (FAILED)\n"))
131         return;
132 }
133
134 /*
135  * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
136  */
137 void ufs_free_blocks (struct inode * inode, unsigned fragment, unsigned count) {
138         struct super_block * sb;
139         struct ufs_sb_private_info * uspi;
140         struct ufs_super_block_first * usb1;
141         struct ufs_cg_private_info * ucpi;
142         struct ufs_cylinder_group * ucg;
143         unsigned overflow, cgno, bit, end_bit, blkno, i, cylno;
144         
145         sb = inode->i_sb;
146         uspi = UFS_SB(sb)->s_uspi;
147         usb1 = ubh_get_usb_first(uspi);
148
149         UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
150         
151         if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
152                 ufs_error (sb, "ufs_free_blocks", "internal error, "
153                         "fragment %u, count %u\n", fragment, count);
154                 goto failed;
155         }
156
157         lock_super(sb);
158         
159 do_more:
160         overflow = 0;
161         cgno = ufs_dtog (fragment);
162         bit = ufs_dtogd (fragment);
163         if (cgno >= uspi->s_ncg) {
164                 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
165                 goto failed;
166         }
167         end_bit = bit + count;
168         if (end_bit > uspi->s_fpg) {
169                 overflow = bit + count - uspi->s_fpg;
170                 count -= overflow;
171                 end_bit -= overflow;
172         }
173
174         ucpi = ufs_load_cylinder (sb, cgno);
175         if (!ucpi) 
176                 goto failed;
177         ucg = ubh_get_ucg (UCPI_UBH);
178         if (!ufs_cg_chkmagic(sb, ucg)) {
179                 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
180                 goto failed;
181         }
182
183         for (i = bit; i < end_bit; i += uspi->s_fpb) {
184                 blkno = ufs_fragstoblks(i);
185                 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
186                         ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
187                 }
188                 ubh_setblock(UCPI_UBH, ucpi->c_freeoff, blkno);
189                 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
190                         ufs_clusteracct (sb, ucpi, blkno, 1);
191                 DQUOT_FREE_BLOCK(inode, uspi->s_fpb);
192
193                 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
194                 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
195                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
196                 cylno = ufs_cbtocylno(i);
197                 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(i)), 1);
198                 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
199         }
200
201         ubh_mark_buffer_dirty (USPI_UBH);
202         ubh_mark_buffer_dirty (UCPI_UBH);
203         if (sb->s_flags & MS_SYNCHRONOUS) {
204                 ubh_ll_rw_block (SWRITE, 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);
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);
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_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
463                 ubh_wait_on_buffer (UCPI_UBH);
464         }
465         sb->s_dirt = 1;
466
467         UFSD(("EXIT, fragment %u\n", fragment))
468         
469         return fragment;
470 }
471
472 #define UFS_TEST_FREE_SPACE_CG \
473         ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
474         if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
475                 goto cg_found; \
476         for (k = count; k < uspi->s_fpb; k++) \
477                 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
478                         goto cg_found; 
479
480 static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
481         unsigned goal, unsigned count, int * err)
482 {
483         struct super_block * sb;
484         struct ufs_sb_private_info * uspi;
485         struct ufs_super_block_first * usb1;
486         struct ufs_cg_private_info * ucpi;
487         struct ufs_cylinder_group * ucg;
488         unsigned oldcg, i, j, k, result, allocsize;
489         
490         UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
491
492         sb = inode->i_sb;
493         uspi = UFS_SB(sb)->s_uspi;
494         usb1 = ubh_get_usb_first(uspi);
495         oldcg = cgno;
496         
497         /*
498          * 1. searching on preferred cylinder group
499          */
500         UFS_TEST_FREE_SPACE_CG
501
502         /*
503          * 2. quadratic rehash
504          */
505         for (j = 1; j < uspi->s_ncg; j *= 2) {
506                 cgno += j;
507                 if (cgno >= uspi->s_ncg) 
508                         cgno -= uspi->s_ncg;
509                 UFS_TEST_FREE_SPACE_CG
510         }
511
512         /*
513          * 3. brute force search
514          * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
515          */
516         cgno = (oldcg + 1) % uspi->s_ncg;
517         for (j = 2; j < uspi->s_ncg; j++) {
518                 cgno++;
519                 if (cgno >= uspi->s_ncg)
520                         cgno = 0;
521                 UFS_TEST_FREE_SPACE_CG
522         }
523         
524         UFSD(("EXIT (FAILED)\n"))
525         return 0;
526
527 cg_found:
528         ucpi = ufs_load_cylinder (sb, cgno);
529         if (!ucpi)
530                 return 0;
531         ucg = ubh_get_ucg (UCPI_UBH);
532         if (!ufs_cg_chkmagic(sb, ucg)) 
533                 ufs_panic (sb, "ufs_alloc_fragments",
534                         "internal error, bad magic number on cg %u", cgno);
535         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
536
537         if (count == uspi->s_fpb) {
538                 result = ufs_alloccg_block (inode, ucpi, goal, err);
539                 if (result == (unsigned)-1)
540                         return 0;
541                 goto succed;
542         }
543
544         for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
545                 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
546                         break;
547         
548         if (allocsize == uspi->s_fpb) {
549                 result = ufs_alloccg_block (inode, ucpi, goal, err);
550                 if (result == (unsigned)-1)
551                         return 0;
552                 goal = ufs_dtogd (result);
553                 for (i = count; i < uspi->s_fpb; i++)
554                         ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
555                 i = uspi->s_fpb - count;
556                 DQUOT_FREE_BLOCK(inode, i);
557
558                 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
559                 fs32_add(sb, &usb1->fs_cstotal.cs_nffree, i);
560                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
561                 fs32_add(sb, &ucg->cg_frsum[i], 1);
562                 goto succed;
563         }
564
565         result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
566         if (result == (unsigned)-1)
567                 return 0;
568         if(DQUOT_ALLOC_BLOCK(inode, count)) {
569                 *err = -EDQUOT;
570                 return 0;
571         }
572         for (i = 0; i < count; i++)
573                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
574         
575         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
576         fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
577         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
578         fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
579
580         if (count != allocsize)
581                 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
582
583 succed:
584         ubh_mark_buffer_dirty (USPI_UBH);
585         ubh_mark_buffer_dirty (UCPI_UBH);
586         if (sb->s_flags & MS_SYNCHRONOUS) {
587                 ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
588                 ubh_wait_on_buffer (UCPI_UBH);
589         }
590         sb->s_dirt = 1;
591
592         result += cgno * uspi->s_fpg;
593         UFSD(("EXIT3, result %u\n", result))
594         return result;
595 }
596
597 static unsigned ufs_alloccg_block (struct inode * inode,
598         struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
599 {
600         struct super_block * sb;
601         struct ufs_sb_private_info * uspi;
602         struct ufs_super_block_first * usb1;
603         struct ufs_cylinder_group * ucg;
604         unsigned result, cylno, blkno;
605
606         UFSD(("ENTER, goal %u\n", goal))
607
608         sb = inode->i_sb;
609         uspi = UFS_SB(sb)->s_uspi;
610         usb1 = ubh_get_usb_first(uspi);
611         ucg = ubh_get_ucg(UCPI_UBH);
612
613         if (goal == 0) {
614                 goal = ucpi->c_rotor;
615                 goto norot;
616         }
617         goal = ufs_blknum (goal);
618         goal = ufs_dtogd (goal);
619         
620         /*
621          * If the requested block is available, use it.
622          */
623         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
624                 result = goal;
625                 goto gotit;
626         }
627         
628 norot:  
629         result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
630         if (result == (unsigned)-1)
631                 return (unsigned)-1;
632         ucpi->c_rotor = result;
633 gotit:
634         blkno = ufs_fragstoblks(result);
635         ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
636         if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
637                 ufs_clusteracct (sb, ucpi, blkno, -1);
638         if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
639                 *err = -EDQUOT;
640                 return (unsigned)-1;
641         }
642
643         fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
644         fs32_sub(sb, &usb1->fs_cstotal.cs_nbfree, 1);
645         fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
646         cylno = ufs_cbtocylno(result);
647         fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1);
648         fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
649         
650         UFSD(("EXIT, result %u\n", result))
651
652         return result;
653 }
654
655 static unsigned ufs_bitmap_search (struct super_block * sb,
656         struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
657 {
658         struct ufs_sb_private_info * uspi;
659         struct ufs_super_block_first * usb1;
660         struct ufs_cylinder_group * ucg;
661         unsigned start, length, location, result;
662         unsigned possition, fragsize, blockmap, mask;
663         
664         UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
665
666         uspi = UFS_SB(sb)->s_uspi;
667         usb1 = ubh_get_usb_first (uspi);
668         ucg = ubh_get_ucg(UCPI_UBH);
669
670         if (goal)
671                 start = ufs_dtogd(goal) >> 3;
672         else
673                 start = ucpi->c_frotor >> 3;
674                 
675         length = ((uspi->s_fpg + 7) >> 3) - start;
676         location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
677                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
678                 1 << (count - 1 + (uspi->s_fpb & 7))); 
679         if (location == 0) {
680                 length = start + 1;
681                 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length, 
682                         (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
683                         1 << (count - 1 + (uspi->s_fpb & 7)));
684                 if (location == 0) {
685                         ufs_error (sb, "ufs_bitmap_search",
686                         "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
687                         ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
688                         return (unsigned)-1;
689                 }
690                 start = 0;
691         }
692         result = (start + length - location) << 3;
693         ucpi->c_frotor = result;
694
695         /*
696          * found the byte in the map
697          */
698         blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
699         fragsize = 0;
700         for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
701                 if (blockmap & mask) {
702                         if (!(possition & uspi->s_fpbmask))
703                                 fragsize = 1;
704                         else 
705                                 fragsize++;
706                 }
707                 else {
708                         if (fragsize == count) {
709                                 result += possition - count;
710                                 UFSD(("EXIT, result %u\n", result))
711                                 return result;
712                         }
713                         fragsize = 0;
714                 }
715         }
716         if (fragsize == count) {
717                 result += possition - count;
718                 UFSD(("EXIT, result %u\n", result))
719                 return result;
720         }
721         ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
722         UFSD(("EXIT (FAILED)\n"))
723         return (unsigned)-1;
724 }
725
726 static void ufs_clusteracct(struct super_block * sb,
727         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
728 {
729         struct ufs_sb_private_info * uspi;
730         int i, start, end, forw, back;
731         
732         uspi = UFS_SB(sb)->s_uspi;
733         if (uspi->s_contigsumsize <= 0)
734                 return;
735
736         if (cnt > 0)
737                 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
738         else
739                 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
740
741         /*
742          * Find the size of the cluster going forward.
743          */
744         start = blkno + 1;
745         end = start + uspi->s_contigsumsize;
746         if ( end >= ucpi->c_nclusterblks)
747                 end = ucpi->c_nclusterblks;
748         i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
749         if (i > end)
750                 i = end;
751         forw = i - start;
752         
753         /*
754          * Find the size of the cluster going backward.
755          */
756         start = blkno - 1;
757         end = start - uspi->s_contigsumsize;
758         if (end < 0 ) 
759                 end = -1;
760         i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
761         if ( i < end) 
762                 i = end;
763         back = start - i;
764         
765         /*
766          * Account for old cluster and the possibly new forward and
767          * back clusters.
768          */
769         i = back + forw + 1;
770         if (i > uspi->s_contigsumsize)
771                 i = uspi->s_contigsumsize;
772         fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2)), cnt);
773         if (back > 0)
774                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2)), cnt);
775         if (forw > 0)
776                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2)), cnt);
777 }
778
779
780 static unsigned char ufs_fragtable_8fpb[] = {
781         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
782         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
783         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
784         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
785         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 
786         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
787         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
788         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
789         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
790         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
791         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
792         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
793         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
794         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
795         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
796         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
797 };
798
799 static unsigned char ufs_fragtable_other[] = {
800         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
801         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
802         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
803         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
804         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
805         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
806         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
807         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
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         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
811         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
812         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
813         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
814         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
815         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
816 };