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