?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] Fix bugs in analog tv i2c-helper chipset drivers
[linux-2.6/history.git] / fs / ufs / balloc.c
blob4209eb7f238d6afc59376dd1d18a0441e93b365c
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 <asm/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
31 unsigned ufs_add_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
32 unsigned ufs_alloc_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
33 unsigned ufs_alloccg_block (struct inode *, struct ufs_cg_private_info *, unsigned, int *);
34 unsigned ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, unsigned, unsigned);
35 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
36 void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
37
38 /*
39 * Free 'count' fragments from fragment number 'fragment'
40 */
41 void 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
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_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
219 failed:
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
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
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 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 unsigned ufs_add_fragments (struct inode * inode, unsigned fragment,
396 unsigned oldcount, unsigned newcount, int * err)
397 {
398 struct super_block * sb;
399 struct ufs_sb_private_info * uspi;
400 struct ufs_super_block_first * usb1;
401 struct ufs_cg_private_info * ucpi;
402 struct ufs_cylinder_group * ucg;
403 unsigned cgno, fragno, fragoff, count, fragsize, i;
404
405 UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
406
407 sb = inode->i_sb;
408 uspi = UFS_SB(sb)->s_uspi;
409 usb1 = ubh_get_usb_first (USPI_UBH);
410 count = newcount - oldcount;
411
412 cgno = ufs_dtog(fragment);
413 if (UFS_SB(sb)->fs_cs(cgno).cs_nffree < count)
414 return 0;
415 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
416 return 0;
417 ucpi = ufs_load_cylinder (sb, cgno);
418 if (!ucpi)
419 return 0;
420 ucg = ubh_get_ucg (UCPI_UBH);
421 if (!ufs_cg_chkmagic(sb, ucg)) {
422 ufs_panic (sb, "ufs_add_fragments",
423 "internal error, bad magic number on cg %u", cgno);
424 return 0;
425 }
426
427 fragno = ufs_dtogd (fragment);
428 fragoff = ufs_fragnum (fragno);
429 for (i = oldcount; i < newcount; i++)
430 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
431 return 0;
432 /*
433 * Block can be extended
434 */
435 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
436 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
437 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
438 break;
439 fragsize = i - oldcount;
440 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
441 ufs_panic (sb, "ufs_add_fragments",
442 "internal error or corrupted bitmap on cg %u", cgno);
443 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
444 if (fragsize != count)
445 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
446 for (i = oldcount; i < newcount; i++)
447 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
448 if(DQUOT_ALLOC_BLOCK(inode, count)) {
449 *err = -EDQUOT;
450 return 0;
451 }
452
453 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
454 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
455 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
456
457 ubh_mark_buffer_dirty (USPI_UBH);
458 ubh_mark_buffer_dirty (UCPI_UBH);
459 if (sb->s_flags & MS_SYNCHRONOUS) {
460 ubh_wait_on_buffer (UCPI_UBH);
461 ubh_ll_rw_block (WRITE, 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 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_wait_on_buffer (UCPI_UBH);
587 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
588 ubh_wait_on_buffer (UCPI_UBH);
589 }
590 sb->s_dirt = 1;
591
592 result += cgno * uspi->s_fpg;
593 UFSD(("EXIT3, result %u\n", result))
594 return result;
595 }
596
597 unsigned ufs_alloccg_block (struct inode * inode,
598 struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
599 {
600 struct super_block * sb;
601 struct ufs_sb_private_info * uspi;
602 struct ufs_super_block_first * usb1;
603 struct ufs_cylinder_group * ucg;
604 unsigned result, cylno, blkno;
605
606 UFSD(("ENTER, goal %u\n", goal))
607
608 sb = inode->i_sb;
609 uspi = UFS_SB(sb)->s_uspi;
610 usb1 = ubh_get_usb_first(USPI_UBH);
611 ucg = ubh_get_ucg(UCPI_UBH);
612
613 if (goal == 0) {
614 goal = ucpi->c_rotor;
615 goto norot;
616 }
617 goal = ufs_blknum (goal);
618 goal = ufs_dtogd (goal);
619
620 /*
621 * If the requested block is available, use it.
622 */
623 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
624 result = goal;
625 goto gotit;
626 }
627
628 norot:
629 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
630 if (result == (unsigned)-1)
631 return (unsigned)-1;
632 ucpi->c_rotor = result;
633 gotit:
634 blkno = ufs_fragstoblks(result);
635 ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
636 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
637 ufs_clusteracct (sb, ucpi, blkno, -1);
638 if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
639 *err = -EDQUOT;
640 return (unsigned)-1;
641 }
642
643 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
644 fs32_sub(sb, &usb1->fs_cstotal.cs_nbfree, 1);
645 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
646 cylno = ufs_cbtocylno(result);
647 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1);
648 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
649
650 UFSD(("EXIT, result %u\n", result))
651
652 return result;
653 }
654
655 unsigned ufs_bitmap_search (struct super_block * sb,
656 struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
657 {
658 struct ufs_sb_private_info * uspi;
659 struct ufs_super_block_first * usb1;
660 struct ufs_cylinder_group * ucg;
661 unsigned start, length, location, result;
662 unsigned possition, fragsize, blockmap, mask;
663
664 UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
665
666 uspi = UFS_SB(sb)->s_uspi;
667 usb1 = ubh_get_usb_first (USPI_UBH);
668 ucg = ubh_get_ucg(UCPI_UBH);
669
670 if (goal)
671 start = ufs_dtogd(goal) >> 3;
672 else
673 start = ucpi->c_frotor >> 3;
674
675 length = ((uspi->s_fpg + 7) >> 3) - start;
676 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
677 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
678 1 << (count - 1 + (uspi->s_fpb & 7)));
679 if (location == 0) {
680 length = start + 1;
681 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, 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 ufs_error (sb, "ufs_bitmap_search",
686 "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
687 ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
688 return (unsigned)-1;
689 }
690 start = 0;
691 }
692 result = (start + length - location) << 3;
693 ucpi->c_frotor = result;
694
695 /*
696 * found the byte in the map
697 */
698 blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
699 fragsize = 0;
700 for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
701 if (blockmap & mask) {
702 if (!(possition & uspi->s_fpbmask))
703 fragsize = 1;
704 else
705 fragsize++;
706 }
707 else {
708 if (fragsize == count) {
709 result += possition - count;
710 UFSD(("EXIT, result %u\n", result))
711 return result;
712 }
713 fragsize = 0;
714 }
715 }
716 if (fragsize == count) {
717 result += possition - count;
718 UFSD(("EXIT, result %u\n", result))
719 return result;
720 }
721 ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
722 UFSD(("EXIT (FAILED)\n"))
723 return (unsigned)-1;
724 }
725
726 void ufs_clusteracct(struct super_block * sb,
727 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
728 {
729 struct ufs_sb_private_info * uspi;
730 int i, start, end, forw, back;
731
732 uspi = UFS_SB(sb)->s_uspi;
733 if (uspi->s_contigsumsize <= 0)
734 return;
735
736 if (cnt > 0)
737 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
738 else
739 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
740
741 /*
742 * Find the size of the cluster going forward.
743 */
744 start = blkno + 1;
745 end = start + uspi->s_contigsumsize;
746 if ( end >= ucpi->c_nclusterblks)
747 end = ucpi->c_nclusterblks;
748 i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
749 if (i > end)
750 i = end;
751 forw = i - start;
752
753 /*
754 * Find the size of the cluster going backward.
755 */
756 start = blkno - 1;
757 end = start - uspi->s_contigsumsize;
758 if (end < 0 )
759 end = -1;
760 i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
761 if ( i < end)
762 i = end;
763 back = start - i;
764
765 /*
766 * Account for old cluster and the possibly new forward and
767 * back clusters.
768 */
769 i = back + forw + 1;
770 if (i > uspi->s_contigsumsize)
771 i = uspi->s_contigsumsize;
772 fs32_add(sb, (u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2)), cnt);
773 if (back > 0)
774 fs32_sub(sb, (u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2)), cnt);
775 if (forw > 0)
776 fs32_sub(sb, (u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2)), cnt);
777 }
778
779
780 static unsigned char ufs_fragtable_8fpb[] = {
781 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
782 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
783 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
784 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
785 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
786 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
787 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
788 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
789 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
790 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
791 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
792 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
793 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
794 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
795 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
796 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
797 };
798
799 static unsigned char ufs_fragtable_other[] = {
800 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
801 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
802 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
803 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
804 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
805 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
806 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
807 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
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 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
811 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
812 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
813 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
814 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
815 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
816 };
Historical 2.5/2.6 development