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