aboutsummaryrefslogtreecommitdiffstats
path: root/fs/ufs/balloc.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 18:20:36 -0400
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /fs/ufs/balloc.c
Linux-2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'fs/ufs/balloc.c')
-rw-r--r--fs/ufs/balloc.c818
1 files changed, 818 insertions, 0 deletions
diff --git a/fs/ufs/balloc.c b/fs/ufs/balloc.c
new file mode 100644
index 00000000000..997640c99c7
--- /dev/null
+++ b/fs/ufs/balloc.c
@@ -0,0 +1,818 @@
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/sched.h>
17#include <linux/bitops.h>
18#include <asm/byteorder.h>
19
20#include "swab.h"
21#include "util.h"
22
23#undef UFS_BALLOC_DEBUG
24
25#ifdef UFS_BALLOC_DEBUG
26#define UFSD(x) printk("(%s, %d), %s:", __FILE__, __LINE__, __FUNCTION__); printk x;
27#else
28#define UFSD(x)
29#endif
30
31static unsigned ufs_add_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
32static unsigned ufs_alloc_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
33static unsigned ufs_alloccg_block (struct inode *, struct ufs_cg_private_info *, unsigned, int *);
34static unsigned ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, unsigned, unsigned);
35static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
36static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
37
38/*
39 * Free 'count' fragments from fragment number 'fragment'
40 */
41void ufs_free_fragments (struct inode * inode, unsigned fragment, unsigned count) {
42 struct super_block * sb;
43 struct ufs_sb_private_info * uspi;
44 struct ufs_super_block_first * usb1;
45 struct ufs_cg_private_info * ucpi;
46 struct ufs_cylinder_group * ucg;
47 unsigned cgno, bit, end_bit, bbase, blkmap, i, blkno, cylno;
48
49 sb = inode->i_sb;
50 uspi = UFS_SB(sb)->s_uspi;
51 usb1 = ubh_get_usb_first(USPI_UBH);
52
53 UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
54
55 if (ufs_fragnum(fragment) + count > uspi->s_fpg)
56 ufs_error (sb, "ufs_free_fragments", "internal error");
57
58 lock_super(sb);
59
60 cgno = ufs_dtog(fragment);
61 bit = ufs_dtogd(fragment);
62 if (cgno >= uspi->s_ncg) {
63 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
64 goto failed;
65 }
66
67 ucpi = ufs_load_cylinder (sb, cgno);
68 if (!ucpi)
69 goto failed;
70 ucg = ubh_get_ucg (UCPI_UBH);
71 if (!ufs_cg_chkmagic(sb, ucg)) {
72 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
73 goto failed;
74 }
75
76 end_bit = bit + count;
77 bbase = ufs_blknum (bit);
78 blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
79 ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
80 for (i = bit; i < end_bit; i++) {
81 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, i))
82 ubh_setbit (UCPI_UBH, ucpi->c_freeoff, i);
83 else ufs_error (sb, "ufs_free_fragments",
84 "bit already cleared for fragment %u", i);
85 }
86
87 DQUOT_FREE_BLOCK (inode, count);
88
89
90 fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
91 fs32_add(sb, &usb1->fs_cstotal.cs_nffree, count);
92 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
93 blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
94 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
95
96 /*
97 * Trying to reassemble free fragments into block
98 */
99 blkno = ufs_fragstoblks (bbase);
100 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
101 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
102 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, uspi->s_fpb);
103 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
104 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
105 ufs_clusteracct (sb, ucpi, blkno, 1);
106 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
107 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
108 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
109 cylno = ufs_cbtocylno (bbase);
110 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(bbase)), 1);
111 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
112 }
113
114 ubh_mark_buffer_dirty (USPI_UBH);
115 ubh_mark_buffer_dirty (UCPI_UBH);
116 if (sb->s_flags & MS_SYNCHRONOUS) {
117 ubh_wait_on_buffer (UCPI_UBH);
118 ubh_ll_rw_block (WRITE, 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
127failed:
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 */
136void 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
158do_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_wait_on_buffer (UCPI_UBH);
204 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
205 ubh_wait_on_buffer (UCPI_UBH);
206 }
207
208 if (overflow) {
209 fragment += count;
210 count = overflow;
211 goto do_more;
212 }
213
214 sb->s_dirt = 1;
215 unlock_super (sb);
216 UFSD(("EXIT\n"))
217 return;
218
219failed:
220 unlock_super (sb);
221 UFSD(("EXIT (FAILED)\n"))
222 return;
223}
224
225
226
227#define NULLIFY_FRAGMENTS \
228 for (i = oldcount; i < newcount; i++) { \
229 bh = sb_getblk(sb, result + i); \
230 memset (bh->b_data, 0, sb->s_blocksize); \
231 set_buffer_uptodate(bh); \
232 mark_buffer_dirty (bh); \
233 if (IS_SYNC(inode)) \
234 sync_dirty_buffer(bh); \
235 brelse (bh); \
236 }
237
238unsigned ufs_new_fragments (struct inode * inode, __fs32 * p, unsigned fragment,
239 unsigned goal, unsigned count, int * err )
240{
241 struct super_block * sb;
242 struct ufs_sb_private_info * uspi;
243 struct ufs_super_block_first * usb1;
244 struct buffer_head * bh;
245 unsigned cgno, oldcount, newcount, tmp, request, i, result;
246
247 UFSD(("ENTER, ino %lu, fragment %u, goal %u, count %u\n", inode->i_ino, fragment, goal, count))
248
249 sb = inode->i_sb;
250 uspi = UFS_SB(sb)->s_uspi;
251 usb1 = ubh_get_usb_first(USPI_UBH);
252 *err = -ENOSPC;
253
254 lock_super (sb);
255
256 tmp = fs32_to_cpu(sb, *p);
257 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
258 ufs_warning (sb, "ufs_new_fragments", "internal warning"
259 " fragment %u, count %u", fragment, count);
260 count = uspi->s_fpb - ufs_fragnum(fragment);
261 }
262 oldcount = ufs_fragnum (fragment);
263 newcount = oldcount + count;
264
265 /*
266 * Somebody else has just allocated our fragments
267 */
268 if (oldcount) {
269 if (!tmp) {
270 ufs_error (sb, "ufs_new_fragments", "internal error, "
271 "fragment %u, tmp %u\n", fragment, tmp);
272 unlock_super (sb);
273 return (unsigned)-1;
274 }
275 if (fragment < UFS_I(inode)->i_lastfrag) {
276 UFSD(("EXIT (ALREADY ALLOCATED)\n"))
277 unlock_super (sb);
278 return 0;
279 }
280 }
281 else {
282 if (tmp) {
283 UFSD(("EXIT (ALREADY ALLOCATED)\n"))
284 unlock_super(sb);
285 return 0;
286 }
287 }
288
289 /*
290 * There is not enough space for user on the device
291 */
292 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(usb1, UFS_MINFREE) <= 0) {
293 unlock_super (sb);
294 UFSD(("EXIT (FAILED)\n"))
295 return 0;
296 }
297
298 if (goal >= uspi->s_size)
299 goal = 0;
300 if (goal == 0)
301 cgno = ufs_inotocg (inode->i_ino);
302 else
303 cgno = ufs_dtog (goal);
304
305 /*
306 * allocate new fragment
307 */
308 if (oldcount == 0) {
309 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
310 if (result) {
311 *p = cpu_to_fs32(sb, result);
312 *err = 0;
313 inode->i_blocks += count << uspi->s_nspfshift;
314 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
315 NULLIFY_FRAGMENTS
316 }
317 unlock_super(sb);
318 UFSD(("EXIT, result %u\n", result))
319 return result;
320 }
321
322 /*
323 * resize block
324 */
325 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
326 if (result) {
327 *err = 0;
328 inode->i_blocks += count << uspi->s_nspfshift;
329 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
330 NULLIFY_FRAGMENTS
331 unlock_super(sb);
332 UFSD(("EXIT, result %u\n", result))
333 return result;
334 }
335
336 /*
337 * allocate new block and move data
338 */
339 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
340 case UFS_OPTSPACE:
341 request = newcount;
342 if (uspi->s_minfree < 5 || fs32_to_cpu(sb, usb1->fs_cstotal.cs_nffree)
343 > uspi->s_dsize * uspi->s_minfree / (2 * 100) )
344 break;
345 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
346 break;
347 default:
348 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
349
350 case UFS_OPTTIME:
351 request = uspi->s_fpb;
352 if (fs32_to_cpu(sb, usb1->fs_cstotal.cs_nffree) < uspi->s_dsize *
353 (uspi->s_minfree - 2) / 100)
354 break;
355 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
356 break;
357 }
358 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
359 if (result) {
360 for (i = 0; i < oldcount; i++) {
361 bh = sb_bread(sb, tmp + i);
362 if(bh)
363 {
364 clear_buffer_dirty(bh);
365 bh->b_blocknr = result + i;
366 mark_buffer_dirty (bh);
367 if (IS_SYNC(inode))
368 sync_dirty_buffer(bh);
369 brelse (bh);
370 }
371 else
372 {
373 printk(KERN_ERR "ufs_new_fragments: bread fail\n");
374 unlock_super(sb);
375 return 0;
376 }
377 }
378 *p = cpu_to_fs32(sb, result);
379 *err = 0;
380 inode->i_blocks += count << uspi->s_nspfshift;
381 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
382 NULLIFY_FRAGMENTS
383 unlock_super(sb);
384 if (newcount < request)
385 ufs_free_fragments (inode, result + newcount, request - newcount);
386 ufs_free_fragments (inode, tmp, oldcount);
387 UFSD(("EXIT, result %u\n", result))
388 return result;
389 }
390
391 unlock_super(sb);
392 UFSD(("EXIT (FAILED)\n"))
393 return 0;
394}
395
396static unsigned
397ufs_add_fragments (struct inode * inode, unsigned fragment,
398 unsigned oldcount, unsigned newcount, int * err)
399{
400 struct super_block * sb;
401 struct ufs_sb_private_info * uspi;
402 struct ufs_super_block_first * usb1;
403 struct ufs_cg_private_info * ucpi;
404 struct ufs_cylinder_group * ucg;
405 unsigned cgno, fragno, fragoff, count, fragsize, i;
406
407 UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
408
409 sb = inode->i_sb;
410 uspi = UFS_SB(sb)->s_uspi;
411 usb1 = ubh_get_usb_first (USPI_UBH);
412 count = newcount - oldcount;
413
414 cgno = ufs_dtog(fragment);
415 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
416 return 0;
417 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
418 return 0;
419 ucpi = ufs_load_cylinder (sb, cgno);
420 if (!ucpi)
421 return 0;
422 ucg = ubh_get_ucg (UCPI_UBH);
423 if (!ufs_cg_chkmagic(sb, ucg)) {
424 ufs_panic (sb, "ufs_add_fragments",
425 "internal error, bad magic number on cg %u", cgno);
426 return 0;
427 }
428
429 fragno = ufs_dtogd (fragment);
430 fragoff = ufs_fragnum (fragno);
431 for (i = oldcount; i < newcount; i++)
432 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
433 return 0;
434 /*
435 * Block can be extended
436 */
437 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
438 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
439 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
440 break;
441 fragsize = i - oldcount;
442 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
443 ufs_panic (sb, "ufs_add_fragments",
444 "internal error or corrupted bitmap on cg %u", cgno);
445 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
446 if (fragsize != count)
447 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
448 for (i = oldcount; i < newcount; i++)
449 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
450 if(DQUOT_ALLOC_BLOCK(inode, count)) {
451 *err = -EDQUOT;
452 return 0;
453 }
454
455 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
456 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
457 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
458
459 ubh_mark_buffer_dirty (USPI_UBH);
460 ubh_mark_buffer_dirty (UCPI_UBH);
461 if (sb->s_flags & MS_SYNCHRONOUS) {
462 ubh_wait_on_buffer (UCPI_UBH);
463 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
464 ubh_wait_on_buffer (UCPI_UBH);
465 }
466 sb->s_dirt = 1;
467
468 UFSD(("EXIT, fragment %u\n", fragment))
469
470 return fragment;
471}
472
473#define UFS_TEST_FREE_SPACE_CG \
474 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
475 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
476 goto cg_found; \
477 for (k = count; k < uspi->s_fpb; k++) \
478 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
479 goto cg_found;
480
481static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
482 unsigned goal, unsigned count, int * err)
483{
484 struct super_block * sb;
485 struct ufs_sb_private_info * uspi;
486 struct ufs_super_block_first * usb1;
487 struct ufs_cg_private_info * ucpi;
488 struct ufs_cylinder_group * ucg;
489 unsigned oldcg, i, j, k, result, allocsize;
490
491 UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
492
493 sb = inode->i_sb;
494 uspi = UFS_SB(sb)->s_uspi;
495 usb1 = ubh_get_usb_first(USPI_UBH);
496 oldcg = cgno;
497
498 /*
499 * 1. searching on preferred cylinder group
500 */
501 UFS_TEST_FREE_SPACE_CG
502
503 /*
504 * 2. quadratic rehash
505 */
506 for (j = 1; j < uspi->s_ncg; j *= 2) {
507 cgno += j;
508 if (cgno >= uspi->s_ncg)
509 cgno -= uspi->s_ncg;
510 UFS_TEST_FREE_SPACE_CG
511 }
512
513 /*
514 * 3. brute force search
515 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
516 */
517 cgno = (oldcg + 1) % uspi->s_ncg;
518 for (j = 2; j < uspi->s_ncg; j++) {
519 cgno++;
520 if (cgno >= uspi->s_ncg)
521 cgno = 0;
522 UFS_TEST_FREE_SPACE_CG
523 }
524
525 UFSD(("EXIT (FAILED)\n"))
526 return 0;
527
528cg_found:
529 ucpi = ufs_load_cylinder (sb, cgno);
530 if (!ucpi)
531 return 0;
532 ucg = ubh_get_ucg (UCPI_UBH);
533 if (!ufs_cg_chkmagic(sb, ucg))
534 ufs_panic (sb, "ufs_alloc_fragments",
535 "internal error, bad magic number on cg %u", cgno);
536 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
537
538 if (count == uspi->s_fpb) {
539 result = ufs_alloccg_block (inode, ucpi, goal, err);
540 if (result == (unsigned)-1)
541 return 0;
542 goto succed;
543 }
544
545 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
546 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
547 break;
548
549 if (allocsize == uspi->s_fpb) {
550 result = ufs_alloccg_block (inode, ucpi, goal, err);
551 if (result == (unsigned)-1)
552 return 0;
553 goal = ufs_dtogd (result);
554 for (i = count; i < uspi->s_fpb; i++)
555 ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
556 i = uspi->s_fpb - count;
557 DQUOT_FREE_BLOCK(inode, i);
558
559 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
560 fs32_add(sb, &usb1->fs_cstotal.cs_nffree, i);
561 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
562 fs32_add(sb, &ucg->cg_frsum[i], 1);
563 goto succed;
564 }
565
566 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
567 if (result == (unsigned)-1)
568 return 0;
569 if(DQUOT_ALLOC_BLOCK(inode, count)) {
570 *err = -EDQUOT;
571 return 0;
572 }
573 for (i = 0; i < count; i++)
574 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
575
576 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
577 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
578 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
579 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
580
581 if (count != allocsize)
582 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
583
584succed:
585 ubh_mark_buffer_dirty (USPI_UBH);
586 ubh_mark_buffer_dirty (UCPI_UBH);
587 if (sb->s_flags & MS_SYNCHRONOUS) {
588 ubh_wait_on_buffer (UCPI_UBH);
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
599static 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
608 UFSD(("ENTER, goal %u\n", goal))
609
610 sb = inode->i_sb;
611 uspi = UFS_SB(sb)->s_uspi;
612 usb1 = ubh_get_usb_first(USPI_UBH);
613 ucg = ubh_get_ucg(UCPI_UBH);
614
615 if (goal == 0) {
616 goal = ucpi->c_rotor;
617 goto norot;
618 }
619 goal = ufs_blknum (goal);
620 goal = ufs_dtogd (goal);
621
622 /*
623 * If the requested block is available, use it.
624 */
625 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
626 result = goal;
627 goto gotit;
628 }
629
630norot:
631 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
632 if (result == (unsigned)-1)
633 return (unsigned)-1;
634 ucpi->c_rotor = result;
635gotit:
636 blkno = ufs_fragstoblks(result);
637 ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
638 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
639 ufs_clusteracct (sb, ucpi, blkno, -1);
640 if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
641 *err = -EDQUOT;
642 return (unsigned)-1;
643 }
644
645 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
646 fs32_sub(sb, &usb1->fs_cstotal.cs_nbfree, 1);
647 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
648 cylno = ufs_cbtocylno(result);
649 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1);
650 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
651
652 UFSD(("EXIT, result %u\n", result))
653
654 return result;
655}
656
657static 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
666 UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
667
668 uspi = UFS_SB(sb)->s_uspi;
669 usb1 = ubh_get_usb_first (USPI_UBH);
670 ucg = ubh_get_ucg(UCPI_UBH);
671
672 if (goal)
673 start = ufs_dtogd(goal) >> 3;
674 else
675 start = ucpi->c_frotor >> 3;
676
677 length = ((uspi->s_fpg + 7) >> 3) - start;
678 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
679 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
680 1 << (count - 1 + (uspi->s_fpb & 7)));
681 if (location == 0) {
682 length = start + 1;
683 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length,
684 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
685 1 << (count - 1 + (uspi->s_fpb & 7)));
686 if (location == 0) {
687 ufs_error (sb, "ufs_bitmap_search",
688 "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
689 ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
690 return (unsigned)-1;
691 }
692 start = 0;
693 }
694 result = (start + length - location) << 3;
695 ucpi->c_frotor = result;
696
697 /*
698 * found the byte in the map
699 */
700 blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
701 fragsize = 0;
702 for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
703 if (blockmap & mask) {
704 if (!(possition & uspi->s_fpbmask))
705 fragsize = 1;
706 else
707 fragsize++;
708 }
709 else {
710 if (fragsize == count) {
711 result += possition - count;
712 UFSD(("EXIT, result %u\n", result))
713 return result;
714 }
715 fragsize = 0;
716 }
717 }
718 if (fragsize == count) {
719 result += possition - count;
720 UFSD(("EXIT, result %u\n", result))
721 return result;
722 }
723 ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
724 UFSD(("EXIT (FAILED)\n"))
725 return (unsigned)-1;
726}
727
728static void ufs_clusteracct(struct super_block * sb,
729 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
730{
731 struct ufs_sb_private_info * uspi;
732 int i, start, end, forw, back;
733
734 uspi = UFS_SB(sb)->s_uspi;
735 if (uspi->s_contigsumsize <= 0)
736 return;
737
738 if (cnt > 0)
739 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
740 else
741 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
742
743 /*
744 * Find the size of the cluster going forward.
745 */
746 start = blkno + 1;
747 end = start + uspi->s_contigsumsize;
748 if ( end >= ucpi->c_nclusterblks)
749 end = ucpi->c_nclusterblks;
750 i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
751 if (i > end)
752 i = end;
753 forw = i - start;
754
755 /*
756 * Find the size of the cluster going backward.
757 */
758 start = blkno - 1;
759 end = start - uspi->s_contigsumsize;
760 if (end < 0 )
761 end = -1;
762 i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
763 if ( i < end)
764 i = end;
765 back = start - i;
766
767 /*
768 * Account for old cluster and the possibly new forward and
769 * back clusters.
770 */
771 i = back + forw + 1;
772 if (i > uspi->s_contigsumsize)
773 i = uspi->s_contigsumsize;
774 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2)), cnt);
775 if (back > 0)
776 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2)), cnt);
777 if (forw > 0)
778 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2)), cnt);
779}
780
781
782static unsigned char ufs_fragtable_8fpb[] = {
783 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
784 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
785 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
786 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
787 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
788 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
789 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
790 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
791 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
792 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
793 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
794 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
795 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
796 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
797 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
798 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
799};
800
801static unsigned char ufs_fragtable_other[] = {
802 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
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 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
806 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
807 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
808 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
809 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
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 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
813 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
814 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
815 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
816 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
817 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
818};
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-27 02:45:44 -0500