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