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 return (unsigned)-1;
275 }
276 if (fragment < inode->u.ufs_i.i_lastfrag) {
277 UFSD(("EXIT (ALREADY ALLOCATED)\n"))
278 unlock_super (sb);
279 return 0;
280 }
281 }
282 else {
283 if (tmp) {
284 UFSD(("EXIT (ALREADY ALLOCATED)\n"))
285 unlock_super(sb);
286 return 0;
287 }
288 }
289
290 /*
291 * There is not enough space for user on the device
292 */
293 if (!fsuser() && ufs_freespace(usb1, UFS_MINFREE) <= 0) {
294 unlock_super (sb);
295 UFSD(("EXIT (FAILED)\n"))
296 return 0;
297 }
298
299 if (goal >= uspi->s_size)
300 goal = 0;
301 if (goal == 0)
302 cgno = ufs_inotocg (inode->i_ino);
303 else
304 cgno = ufs_dtog (goal);
305
306 /*
307 * allocate new fragment
308 */
309 if (oldcount == 0) {
310 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
311 if (result) {
312 *p = SWAB32(result);
313 *err = 0;
314 inode->i_blocks += count << uspi->s_nspfshift;
315 inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
316 NULLIFY_FRAGMENTS
317 }
318 unlock_super(sb);
319 UFSD(("EXIT, result %u\n", result))
320 return result;
321 }
322
323 /*
324 * resize block
325 */
326 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
327 if (result) {
328 *err = 0;
329 inode->i_blocks += count << uspi->s_nspfshift;
330 inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
331 NULLIFY_FRAGMENTS
332 unlock_super(sb);
333 UFSD(("EXIT, result %u\n", result))
334 return result;
335 }
336
337 /*
338 * allocate new block and move data
339 */
340 switch (SWAB32(usb1->fs_optim)) {
341 case UFS_OPTSPACE:
342 request = newcount;
343 if (uspi->s_minfree < 5 || SWAB32(usb1->fs_cstotal.cs_nffree)
344 > uspi->s_dsize * uspi->s_minfree / (2 * 100) )
345 break;
346 usb1->fs_optim = SWAB32(UFS_OPTTIME);
347 break;
348 default:
349 usb1->fs_optim = SWAB32(UFS_OPTTIME);
350
351 case UFS_OPTTIME:
352 request = uspi->s_fpb;
353 if (SWAB32(usb1->fs_cstotal.cs_nffree) < uspi->s_dsize *
354 (uspi->s_minfree - 2) / 100)
355 break;
356 usb1->fs_optim = SWAB32(UFS_OPTSPACE);
357 break;
358 }
359 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
360 if (result) {
361 for (i = 0; i < oldcount; i++) {
362 bh = bread (sb->s_dev, tmp + i, sb->s_blocksize);
363 if(bh)
364 {
365 mark_buffer_clean (bh);
366 bh->b_blocknr = result + i;
367 mark_buffer_dirty (bh);
368 if (IS_SYNC(inode)) {
369 ll_rw_block (WRITE, 1, &bh);
370 wait_on_buffer (bh);
371 }
372 brelse (bh);
373 }
374 else
375 {
376 printk(KERN_ERR "ufs_new_fragments: bread fail\n");
377 return 0;
378 }
379 }
380 *p = SWAB32(result);
381 *err = 0;
382 inode->i_blocks += count << uspi->s_nspfshift;
383 inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
384 NULLIFY_FRAGMENTS
385 unlock_super(sb);
386 if (newcount < request)
387 ufs_free_fragments (inode, result + newcount, request - newcount);
388 ufs_free_fragments (inode, tmp, oldcount);
389 UFSD(("EXIT, result %u\n", result))
390 return result;
391 }
392
393 unlock_super(sb);
394 UFSD(("EXIT (FAILED)\n"))
395 return 0;
396 }
397
398 unsigned ufs_add_fragments (struct inode * inode, unsigned fragment,
399 unsigned oldcount, unsigned newcount, int * err)
400 {
401 struct super_block * sb;
402 struct ufs_sb_private_info * uspi;
403 struct ufs_super_block_first * usb1;
404 struct ufs_cg_private_info * ucpi;
405 struct ufs_cylinder_group * ucg;
406 unsigned cgno, fragno, fragoff, count, fragsize, i;
407 unsigned swab;
408
409 UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
410
411 sb = inode->i_sb;
412 swab = sb->u.ufs_sb.s_swab;
413 uspi = sb->u.ufs_sb.s_uspi;
414 usb1 = ubh_get_usb_first (USPI_UBH);
415 count = newcount - oldcount;
416
417 cgno = ufs_dtog(fragment);
418 if (sb->fs_cs(cgno).cs_nffree < count)
419 return 0;
420 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
421 return 0;
422 ucpi = ufs_load_cylinder (sb, cgno);
423 if (!ucpi)
424 return 0;
425 ucg = ubh_get_ucg (UCPI_UBH);
426 if (!ufs_cg_chkmagic(ucg)) {
427 ufs_panic (sb, "ufs_add_fragments",
428 "internal error, bad magic number on cg %u", cgno);
429 return 0;
430 }
431
432 fragno = ufs_dtogd (fragment);
433 fragoff = ufs_fragnum (fragno);
434 for (i = oldcount; i < newcount; i++)
435 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
436 return 0;
437 /*
438 * Block can be extended
439 */
440 ucg->cg_time = SWAB32(CURRENT_TIME);
441 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
442 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
443 break;
444 fragsize = i - oldcount;
445 if (!SWAB32(ucg->cg_frsum[fragsize]))
446 ufs_panic (sb, "ufs_add_fragments",
447 "internal error or corrupted bitmap on cg %u", cgno);
448 DEC_SWAB32(ucg->cg_frsum[fragsize]);
449 if (fragsize != count)
450 INC_SWAB32(ucg->cg_frsum[fragsize - count]);
451 for (i = oldcount; i < newcount; i++)
452 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
453 if(DQUOT_ALLOC_BLOCK(sb, inode, count)) {
454 *err = -EDQUOT;
455 return 0;
456 }
457 SUB_SWAB32(ucg->cg_cs.cs_nffree, count);
458 SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
459 SUB_SWAB32(usb1->fs_cstotal.cs_nffree, count);
460
461 ubh_mark_buffer_dirty (USPI_UBH);
462 ubh_mark_buffer_dirty (UCPI_UBH);
463 if (sb->s_flags & MS_SYNCHRONOUS) {
464 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
465 ubh_wait_on_buffer (UCPI_UBH);
466 }
467 sb->s_dirt = 1;
468
469 UFSD(("EXIT, fragment %u\n", fragment))
470
471 return fragment;
472 }
473
474 #define UFS_TEST_FREE_SPACE_CG \
475 ucg = (struct ufs_cylinder_group *) sb->u.ufs_sb.s_ucg[cgno]->b_data; \
476 if (SWAB32(ucg->cg_cs.cs_nbfree)) \
477 goto cg_found; \
478 for (k = count; k < uspi->s_fpb; k++) \
479 if (SWAB32(ucg->cg_frsum[k])) \
480 goto cg_found;
481
482 unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
483 unsigned goal, unsigned count, int * err)
484 {
485 struct super_block * sb;
486 struct ufs_sb_private_info * uspi;
487 struct ufs_super_block_first * usb1;
488 struct ufs_cg_private_info * ucpi;
489 struct ufs_cylinder_group * ucg;
490 unsigned oldcg, i, j, k, result, allocsize;
491 unsigned swab;
492
493 UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
494
495 sb = inode->i_sb;
496 swab = sb->u.ufs_sb.s_swab;
497 uspi = sb->u.ufs_sb.s_uspi;
498 usb1 = ubh_get_usb_first(USPI_UBH);
499 oldcg = cgno;
500
501 /*
502 * 1. searching on preferred cylinder group
503 */
504 UFS_TEST_FREE_SPACE_CG
505
506 /*
507 * 2. quadratic rehash
508 */
509 for (j = 1; j < uspi->s_ncg; j *= 2) {
510 cgno += j;
511 if (cgno >= uspi->s_ncg)
512 cgno -= uspi->s_ncg;
513 UFS_TEST_FREE_SPACE_CG
514 }
515
516 /*
517 * 3. brute force search
518 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
519 */
520 cgno = (oldcg + 1) % uspi->s_ncg;
521 for (j = 2; j < uspi->s_ncg; j++) {
522 cgno++;
523 if (cgno >= uspi->s_ncg)
524 cgno = 0;
525 UFS_TEST_FREE_SPACE_CG
526 }
527
528 UFSD(("EXIT (FAILED)\n"))
529 return 0;
530
531 cg_found:
532 ucpi = ufs_load_cylinder (sb, cgno);
533 if (!ucpi)
534 return 0;
535 ucg = ubh_get_ucg (UCPI_UBH);
536 if (!ufs_cg_chkmagic(ucg))
537 ufs_panic (sb, "ufs_alloc_fragments",
538 "internal error, bad magic number on cg %u", cgno);
539 ucg->cg_time = SWAB32(CURRENT_TIME);
540
541 if (count == uspi->s_fpb) {
542 result = ufs_alloccg_block (inode, ucpi, goal, err);
543 if (result == (unsigned)-1)
544 return 0;
545 goto succed;
546 }
547
548 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
549 if (SWAB32(ucg->cg_frsum[allocsize]) != 0)
550 break;
551
552 if (allocsize == uspi->s_fpb) {
553 result = ufs_alloccg_block (inode, ucpi, goal, err);
554 if (result == (unsigned)-1)
555 return 0;
556 goal = ufs_dtogd (result);
557 for (i = count; i < uspi->s_fpb; i++)
558 ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
559 i = uspi->s_fpb - count;
560 DQUOT_FREE_BLOCK(sb, inode, i);
561 ADD_SWAB32(ucg->cg_cs.cs_nffree, i);
562 ADD_SWAB32(usb1->fs_cstotal.cs_nffree, i);
563 ADD_SWAB32(sb->fs_cs(cgno).cs_nffree, i);
564 INC_SWAB32(ucg->cg_frsum[i]);
565 goto succed;
566 }
567
568 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
569 if (result == (unsigned)-1)
570 return 0;
571 if(DQUOT_ALLOC_BLOCK(sb, inode, count)) {
572 *err = -EDQUOT;
573 return 0;
574 }
575 for (i = 0; i < count; i++)
576 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
577 SUB_SWAB32(ucg->cg_cs.cs_nffree, count);
578 SUB_SWAB32(usb1->fs_cstotal.cs_nffree, count);
579 SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
580 DEC_SWAB32(ucg->cg_frsum[allocsize]);
581 if (count != allocsize)
582 INC_SWAB32(ucg->cg_frsum[allocsize - count]);
583
584 succed:
585 ubh_mark_buffer_dirty (USPI_UBH);
586 ubh_mark_buffer_dirty (UCPI_UBH);
587 if (sb->s_flags & MS_SYNCHRONOUS) {
588 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
589 ubh_wait_on_buffer (UCPI_UBH);
590 }
591 sb->s_dirt = 1;
592
593 result += cgno * uspi->s_fpg;
594 UFSD(("EXIT3, result %u\n", result))
595 return result;
596 }
597
598 unsigned ufs_alloccg_block (struct inode * inode,
599 struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
600 {
601 struct super_block * sb;
602 struct ufs_sb_private_info * uspi;
603 struct ufs_super_block_first * usb1;
604 struct ufs_cylinder_group * ucg;
605 unsigned result, cylno, blkno;
606 unsigned swab;
607
608 UFSD(("ENTER, goal %u\n", goal))
609
610 sb = inode->i_sb;
611 swab = sb->u.ufs_sb.s_swab;
612 uspi = sb->u.ufs_sb.s_uspi;
613 usb1 = ubh_get_usb_first(USPI_UBH);
614 ucg = ubh_get_ucg(UCPI_UBH);
615
616 if (goal == 0) {
617 goal = ucpi->c_rotor;
618 goto norot;
619 }
620 goal = ufs_blknum (goal);
621 goal = ufs_dtogd (goal);
622
623 /*
624 * If the requested block is available, use it.
625 */
626 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
627 result = goal;
628 goto gotit;
629 }
630
631 norot:
632 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
633 if (result == (unsigned)-1)
634 return (unsigned)-1;
635 ucpi->c_rotor = result;
636 gotit:
637 blkno = ufs_fragstoblks(result);
638 ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
639 if ((sb->u.ufs_sb.s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
640 ufs_clusteracct (sb, ucpi, blkno, -1);
641 if(DQUOT_ALLOC_BLOCK(sb, inode, uspi->s_fpb)) {
642 *err = -EDQUOT;
643 return (unsigned)-1;
644 }
645 DEC_SWAB32(ucg->cg_cs.cs_nbfree);
646 DEC_SWAB32(usb1->fs_cstotal.cs_nbfree);
647 DEC_SWAB32(sb->fs_cs(ucpi->c_cgx).cs_nbfree);
648 cylno = ufs_cbtocylno(result);
649 DEC_SWAB16(ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)));
650 DEC_SWAB32(ubh_cg_blktot(ucpi, cylno));
651
652 UFSD(("EXIT, result %u\n", result))
653
654 return result;
655 }
656
657 unsigned ufs_bitmap_search (struct super_block * sb,
658 struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
659 {
660 struct ufs_sb_private_info * uspi;
661 struct ufs_super_block_first * usb1;
662 struct ufs_cylinder_group * ucg;
663 unsigned start, length, location, result;
664 unsigned possition, fragsize, blockmap, mask;
665 unsigned swab;
666
667 UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
668
669 swab = sb->u.ufs_sb.s_swab;
670 uspi = sb->u.ufs_sb.s_uspi;
671 usb1 = ubh_get_usb_first (USPI_UBH);
672 ucg = ubh_get_ucg(UCPI_UBH);
673
674 if (goal)
675 start = ufs_dtogd(goal) >> 3;
676 else
677 start = ucpi->c_frotor >> 3;
678
679 length = ((uspi->s_fpg + 7) >> 3) - start;
680 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
681 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
682 1 << (count - 1 + (uspi->s_fpb & 7)));
683 if (location == 0) {
684 length = start + 1;
685 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length,
686 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
687 1 << (count - 1 + (uspi->s_fpb & 7)));
688 if (location == 0) {
689 ufs_error (sb, "ufs_bitmap_search",
690 "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
691 ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
692 return (unsigned)-1;
693 }
694 start = 0;
695 }
696 result = (start + length - location) << 3;
697 ucpi->c_frotor = result;
698
699 /*
700 * found the byte in the map
701 */
702 blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
703 fragsize = 0;
704 for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
705 if (blockmap & mask) {
706 if (!(possition & uspi->s_fpbmask))
707 fragsize = 1;
708 else
709 fragsize++;
710 }
711 else {
712 if (fragsize == count) {
713 result += possition - count;
714 UFSD(("EXIT, result %u\n", result))
715 return result;
716 }
717 fragsize = 0;
718 }
719 }
720 if (fragsize == count) {
721 result += possition - count;
722 UFSD(("EXIT, result %u\n", result))
723 return result;
724 }
725 ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
726 UFSD(("EXIT (FAILED)\n"))
727 return (unsigned)-1;
728 }
729
730 void ufs_clusteracct(struct super_block * sb,
731 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
732 {
733 struct ufs_sb_private_info * uspi;
734 int i, start, end, forw, back;
735 unsigned swab;
736
737
738 uspi = sb->u.ufs_sb.s_uspi;
739 swab = sb->u.ufs_sb.s_swab;
740
741 if (uspi->s_contigsumsize <= 0)
742 return;
743
744 if (cnt > 0)
745 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
746 else
747 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
748
749 /*
750 * Find the size of the cluster going forward.
751 */
752 start = blkno + 1;
753 end = start + uspi->s_contigsumsize;
754 if ( end >= ucpi->c_nclusterblks)
755 end = ucpi->c_nclusterblks;
756 i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
757 if (i > end)
758 i = end;
759 forw = i - start;
760
761 /*
762 * Find the size of the cluster going backward.
763 */
764 start = blkno - 1;
765 end = start - uspi->s_contigsumsize;
766 if (end < 0 )
767 end = -1;
768 i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
769 if ( i < end)
770 i = end;
771 back = start - i;
772
773 /*
774 * Account for old cluster and the possibly new forward and
775 * back clusters.
776 */
777 i = back + forw + 1;
778 if (i > uspi->s_contigsumsize)
779 i = uspi->s_contigsumsize;
780 ADD_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2))), cnt);
781 if (back > 0)
782 SUB_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2))), cnt);
783 if (forw > 0)
784 SUB_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2))), cnt);
785 }
786
787
788 static unsigned char ufs_fragtable_8fpb[] = {
789 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
790 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
791 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
792 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
793 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
794 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
795 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
796 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
797 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
798 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
799 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
800 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
801 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
802 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
803 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
804 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
805 };
806
807 static unsigned char ufs_fragtable_other[] = {
808 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
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 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
812 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
813 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
814 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
815 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
816 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
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 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
820 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
821 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
822 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
823 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
824 };
825
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.