?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
mtd: sst25l: fix multi-part messages with broken spi masters
[linux-2.6/kvm.git] / fs / ufs / balloc.c
blob5cfa4d85ccf23b787b58838bbfde2a9f260fda23
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 * UFS2 write support Evgeniy Dushistov <dushistov@mail.ru>, 2007
9 */
10
11 #include <linux/fs.h>
12 #include <linux/stat.h>
13 #include <linux/time.h>
14 #include <linux/string.h>
15 #include <linux/quotaops.h>
16 #include <linux/buffer_head.h>
17 #include <linux/capability.h>
18 #include <linux/bitops.h>
19 #include <asm/byteorder.h>
20
21 #include "ufs_fs.h"
22 #include "ufs.h"
23 #include "swab.h"
24 #include "util.h"
25
26 #define INVBLOCK ((u64)-1L)
27
28 static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned, int *);
29 static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *);
30 static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *);
31 static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned);
32 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
33 static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
34
35 /*
36 * Free 'count' fragments from fragment number 'fragment'
37 */
38 void ufs_free_fragments(struct inode *inode, u64 fragment, unsigned count)
39 {
40 struct super_block * sb;
41 struct ufs_sb_private_info * uspi;
42 struct ufs_super_block_first * usb1;
43 struct ufs_cg_private_info * ucpi;
44 struct ufs_cylinder_group * ucg;
45 unsigned cgno, bit, end_bit, bbase, blkmap, i;
46 u64 blkno;
47
48 sb = inode->i_sb;
49 uspi = UFS_SB(sb)->s_uspi;
50 usb1 = ubh_get_usb_first(uspi);
51
52 UFSD("ENTER, fragment %llu, count %u\n",
53 (unsigned long long)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(uspi, fragment);
61 bit = ufs_dtogd(uspi, 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(ucpi));
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), 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), ucpi->c_freeoff, i))
82 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, i);
83 else
84 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 uspi->cs_total.cs_nffree += count;
93 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
94 blkmap = ubh_blkmap (UCPI_UBH(ucpi), 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), ucpi->c_freeoff, blkno)) {
102 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
103 uspi->cs_total.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 uspi->cs_total.cs_nbfree++;
109 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
110 if (uspi->fs_magic != UFS2_MAGIC) {
111 unsigned cylno = ufs_cbtocylno (bbase);
112
113 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
114 ufs_cbtorpos(bbase)), 1);
115 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
116 }
117 }
118
119 ubh_mark_buffer_dirty (USPI_UBH(uspi));
120 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
121 if (sb->s_flags & MS_SYNCHRONOUS) {
122 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
123 ubh_wait_on_buffer (UCPI_UBH(ucpi));
124 }
125 sb->s_dirt = 1;
126
127 unlock_super (sb);
128 UFSD("EXIT\n");
129 return;
130
131 failed:
132 unlock_super (sb);
133 UFSD("EXIT (FAILED)\n");
134 return;
135 }
136
137 /*
138 * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
139 */
140 void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count)
141 {
142 struct super_block * sb;
143 struct ufs_sb_private_info * uspi;
144 struct ufs_super_block_first * usb1;
145 struct ufs_cg_private_info * ucpi;
146 struct ufs_cylinder_group * ucg;
147 unsigned overflow, cgno, bit, end_bit, i;
148 u64 blkno;
149
150 sb = inode->i_sb;
151 uspi = UFS_SB(sb)->s_uspi;
152 usb1 = ubh_get_usb_first(uspi);
153
154 UFSD("ENTER, fragment %llu, count %u\n",
155 (unsigned long long)fragment, count);
156
157 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
158 ufs_error (sb, "ufs_free_blocks", "internal error, "
159 "fragment %llu, count %u\n",
160 (unsigned long long)fragment, count);
161 goto failed;
162 }
163
164 lock_super(sb);
165
166 do_more:
167 overflow = 0;
168 cgno = ufs_dtog(uspi, fragment);
169 bit = ufs_dtogd(uspi, fragment);
170 if (cgno >= uspi->s_ncg) {
171 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
172 goto failed_unlock;
173 }
174 end_bit = bit + count;
175 if (end_bit > uspi->s_fpg) {
176 overflow = bit + count - uspi->s_fpg;
177 count -= overflow;
178 end_bit -= overflow;
179 }
180
181 ucpi = ufs_load_cylinder (sb, cgno);
182 if (!ucpi)
183 goto failed_unlock;
184 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
185 if (!ufs_cg_chkmagic(sb, ucg)) {
186 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
187 goto failed_unlock;
188 }
189
190 for (i = bit; i < end_bit; i += uspi->s_fpb) {
191 blkno = ufs_fragstoblks(i);
192 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
193 ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
194 }
195 ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
196 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
197 ufs_clusteracct (sb, ucpi, blkno, 1);
198 dquot_free_block(inode, uspi->s_fpb);
199
200 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
201 uspi->cs_total.cs_nbfree++;
202 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
203
204 if (uspi->fs_magic != UFS2_MAGIC) {
205 unsigned cylno = ufs_cbtocylno(i);
206
207 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
208 ufs_cbtorpos(i)), 1);
209 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
210 }
211 }
212
213 ubh_mark_buffer_dirty (USPI_UBH(uspi));
214 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
215 if (sb->s_flags & MS_SYNCHRONOUS) {
216 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
217 ubh_wait_on_buffer (UCPI_UBH(ucpi));
218 }
219
220 if (overflow) {
221 fragment += count;
222 count = overflow;
223 goto do_more;
224 }
225
226 sb->s_dirt = 1;
227 unlock_super (sb);
228 UFSD("EXIT\n");
229 return;
230
231 failed_unlock:
232 unlock_super (sb);
233 failed:
234 UFSD("EXIT (FAILED)\n");
235 return;
236 }
237
238 /*
239 * Modify inode page cache in such way:
240 * have - blocks with b_blocknr equal to oldb...oldb+count-1
241 * get - blocks with b_blocknr equal to newb...newb+count-1
242 * also we suppose that oldb...oldb+count-1 blocks
243 * situated at the end of file.
244 *
245 * We can come here from ufs_writepage or ufs_prepare_write,
246 * locked_page is argument of these functions, so we already lock it.
247 */
248 static void ufs_change_blocknr(struct inode *inode, sector_t beg,
249 unsigned int count, sector_t oldb,
250 sector_t newb, struct page *locked_page)
251 {
252 const unsigned blks_per_page =
253 1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);
254 const unsigned mask = blks_per_page - 1;
255 struct address_space * const mapping = inode->i_mapping;
256 pgoff_t index, cur_index, last_index;
257 unsigned pos, j, lblock;
258 sector_t end, i;
259 struct page *page;
260 struct buffer_head *head, *bh;
261
262 UFSD("ENTER, ino %lu, count %u, oldb %llu, newb %llu\n",
263 inode->i_ino, count,
264 (unsigned long long)oldb, (unsigned long long)newb);
265
266 BUG_ON(!locked_page);
267 BUG_ON(!PageLocked(locked_page));
268
269 cur_index = locked_page->index;
270 end = count + beg;
271 last_index = end >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
272 for (i = beg; i < end; i = (i | mask) + 1) {
273 index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
274
275 if (likely(cur_index != index)) {
276 page = ufs_get_locked_page(mapping, index);
277 if (!page)/* it was truncated */
278 continue;
279 if (IS_ERR(page)) {/* or EIO */
280 ufs_error(inode->i_sb, __func__,
281 "read of page %llu failed\n",
282 (unsigned long long)index);
283 continue;
284 }
285 } else
286 page = locked_page;
287
288 head = page_buffers(page);
289 bh = head;
290 pos = i & mask;
291 for (j = 0; j < pos; ++j)
292 bh = bh->b_this_page;
293
294
295 if (unlikely(index == last_index))
296 lblock = end & mask;
297 else
298 lblock = blks_per_page;
299
300 do {
301 if (j >= lblock)
302 break;
303 pos = (i - beg) + j;
304
305 if (!buffer_mapped(bh))
306 map_bh(bh, inode->i_sb, oldb + pos);
307 if (!buffer_uptodate(bh)) {
308 ll_rw_block(READ, 1, &bh);
309 wait_on_buffer(bh);
310 if (!buffer_uptodate(bh)) {
311 ufs_error(inode->i_sb, __func__,
312 "read of block failed\n");
313 break;
314 }
315 }
316
317 UFSD(" change from %llu to %llu, pos %u\n",
318 (unsigned long long)(pos + oldb),
319 (unsigned long long)(pos + newb), pos);
320
321 bh->b_blocknr = newb + pos;
322 unmap_underlying_metadata(bh->b_bdev,
323 bh->b_blocknr);
324 mark_buffer_dirty(bh);
325 ++j;
326 bh = bh->b_this_page;
327 } while (bh != head);
328
329 if (likely(cur_index != index))
330 ufs_put_locked_page(page);
331 }
332 UFSD("EXIT\n");
333 }
334
335 static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
336 int sync)
337 {
338 struct buffer_head *bh;
339 sector_t end = beg + n;
340
341 for (; beg < end; ++beg) {
342 bh = sb_getblk(inode->i_sb, beg);
343 lock_buffer(bh);
344 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
345 set_buffer_uptodate(bh);
346 mark_buffer_dirty(bh);
347 unlock_buffer(bh);
348 if (IS_SYNC(inode) || sync)
349 sync_dirty_buffer(bh);
350 brelse(bh);
351 }
352 }
353
354 u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,
355 u64 goal, unsigned count, int *err,
356 struct page *locked_page)
357 {
358 struct super_block * sb;
359 struct ufs_sb_private_info * uspi;
360 struct ufs_super_block_first * usb1;
361 unsigned cgno, oldcount, newcount;
362 u64 tmp, request, result;
363
364 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",
365 inode->i_ino, (unsigned long long)fragment,
366 (unsigned long long)goal, count);
367
368 sb = inode->i_sb;
369 uspi = UFS_SB(sb)->s_uspi;
370 usb1 = ubh_get_usb_first(uspi);
371 *err = -ENOSPC;
372
373 lock_super (sb);
374 tmp = ufs_data_ptr_to_cpu(sb, p);
375
376 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
377 ufs_warning(sb, "ufs_new_fragments", "internal warning"
378 " fragment %llu, count %u",
379 (unsigned long long)fragment, count);
380 count = uspi->s_fpb - ufs_fragnum(fragment);
381 }
382 oldcount = ufs_fragnum (fragment);
383 newcount = oldcount + count;
384
385 /*
386 * Somebody else has just allocated our fragments
387 */
388 if (oldcount) {
389 if (!tmp) {
390 ufs_error(sb, "ufs_new_fragments", "internal error, "
391 "fragment %llu, tmp %llu\n",
392 (unsigned long long)fragment,
393 (unsigned long long)tmp);
394 unlock_super(sb);
395 return INVBLOCK;
396 }
397 if (fragment < UFS_I(inode)->i_lastfrag) {
398 UFSD("EXIT (ALREADY ALLOCATED)\n");
399 unlock_super (sb);
400 return 0;
401 }
402 }
403 else {
404 if (tmp) {
405 UFSD("EXIT (ALREADY ALLOCATED)\n");
406 unlock_super(sb);
407 return 0;
408 }
409 }
410
411 /*
412 * There is not enough space for user on the device
413 */
414 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {
415 unlock_super (sb);
416 UFSD("EXIT (FAILED)\n");
417 return 0;
418 }
419
420 if (goal >= uspi->s_size)
421 goal = 0;
422 if (goal == 0)
423 cgno = ufs_inotocg (inode->i_ino);
424 else
425 cgno = ufs_dtog(uspi, goal);
426
427 /*
428 * allocate new fragment
429 */
430 if (oldcount == 0) {
431 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
432 if (result) {
433 ufs_cpu_to_data_ptr(sb, p, result);
434 *err = 0;
435 UFS_I(inode)->i_lastfrag =
436 max_t(u32, UFS_I(inode)->i_lastfrag,
437 fragment + count);
438 ufs_clear_frags(inode, result + oldcount,
439 newcount - oldcount, locked_page != NULL);
440 }
441 unlock_super(sb);
442 UFSD("EXIT, result %llu\n", (unsigned long long)result);
443 return result;
444 }
445
446 /*
447 * resize block
448 */
449 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
450 if (result) {
451 *err = 0;
452 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
453 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
454 locked_page != NULL);
455 unlock_super(sb);
456 UFSD("EXIT, result %llu\n", (unsigned long long)result);
457 return result;
458 }
459
460 /*
461 * allocate new block and move data
462 */
463 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
464 case UFS_OPTSPACE:
465 request = newcount;
466 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
467 > uspi->s_dsize * uspi->s_minfree / (2 * 100))
468 break;
469 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
470 break;
471 default:
472 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
473
474 case UFS_OPTTIME:
475 request = uspi->s_fpb;
476 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
477 (uspi->s_minfree - 2) / 100)
478 break;
479 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
480 break;
481 }
482 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
483 if (result) {
484 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
485 locked_page != NULL);
486 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
487 uspi->s_sbbase + tmp,
488 uspi->s_sbbase + result, locked_page);
489 ufs_cpu_to_data_ptr(sb, p, result);
490 *err = 0;
491 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
492 unlock_super(sb);
493 if (newcount < request)
494 ufs_free_fragments (inode, result + newcount, request - newcount);
495 ufs_free_fragments (inode, tmp, oldcount);
496 UFSD("EXIT, result %llu\n", (unsigned long long)result);
497 return result;
498 }
499
500 unlock_super(sb);
501 UFSD("EXIT (FAILED)\n");
502 return 0;
503 }
504
505 static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
506 unsigned oldcount, unsigned newcount, int *err)
507 {
508 struct super_block * sb;
509 struct ufs_sb_private_info * uspi;
510 struct ufs_super_block_first * usb1;
511 struct ufs_cg_private_info * ucpi;
512 struct ufs_cylinder_group * ucg;
513 unsigned cgno, fragno, fragoff, count, fragsize, i;
514 int ret;
515
516 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
517 (unsigned long long)fragment, oldcount, newcount);
518
519 sb = inode->i_sb;
520 uspi = UFS_SB(sb)->s_uspi;
521 usb1 = ubh_get_usb_first (uspi);
522 count = newcount - oldcount;
523
524 cgno = ufs_dtog(uspi, fragment);
525 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
526 return 0;
527 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
528 return 0;
529 ucpi = ufs_load_cylinder (sb, cgno);
530 if (!ucpi)
531 return 0;
532 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
533 if (!ufs_cg_chkmagic(sb, ucg)) {
534 ufs_panic (sb, "ufs_add_fragments",
535 "internal error, bad magic number on cg %u", cgno);
536 return 0;
537 }
538
539 fragno = ufs_dtogd(uspi, fragment);
540 fragoff = ufs_fragnum (fragno);
541 for (i = oldcount; i < newcount; i++)
542 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
543 return 0;
544 /*
545 * Block can be extended
546 */
547 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
548 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
549 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
550 break;
551 fragsize = i - oldcount;
552 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
553 ufs_panic (sb, "ufs_add_fragments",
554 "internal error or corrupted bitmap on cg %u", cgno);
555 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
556 if (fragsize != count)
557 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
558 for (i = oldcount; i < newcount; i++)
559 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
560 ret = dquot_alloc_block(inode, count);
561 if (ret) {
562 *err = ret;
563 return 0;
564 }
565
566 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
567 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
568 uspi->cs_total.cs_nffree -= count;
569
570 ubh_mark_buffer_dirty (USPI_UBH(uspi));
571 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
572 if (sb->s_flags & MS_SYNCHRONOUS) {
573 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
574 ubh_wait_on_buffer (UCPI_UBH(ucpi));
575 }
576 sb->s_dirt = 1;
577
578 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
579
580 return fragment;
581 }
582
583 #define UFS_TEST_FREE_SPACE_CG \
584 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
585 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
586 goto cg_found; \
587 for (k = count; k < uspi->s_fpb; k++) \
588 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
589 goto cg_found;
590
591 static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
592 u64 goal, unsigned count, int *err)
593 {
594 struct super_block * sb;
595 struct ufs_sb_private_info * uspi;
596 struct ufs_super_block_first * usb1;
597 struct ufs_cg_private_info * ucpi;
598 struct ufs_cylinder_group * ucg;
599 unsigned oldcg, i, j, k, allocsize;
600 u64 result;
601 int ret;
602
603 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
604 inode->i_ino, cgno, (unsigned long long)goal, count);
605
606 sb = inode->i_sb;
607 uspi = UFS_SB(sb)->s_uspi;
608 usb1 = ubh_get_usb_first(uspi);
609 oldcg = cgno;
610
611 /*
612 * 1. searching on preferred cylinder group
613 */
614 UFS_TEST_FREE_SPACE_CG
615
616 /*
617 * 2. quadratic rehash
618 */
619 for (j = 1; j < uspi->s_ncg; j *= 2) {
620 cgno += j;
621 if (cgno >= uspi->s_ncg)
622 cgno -= uspi->s_ncg;
623 UFS_TEST_FREE_SPACE_CG
624 }
625
626 /*
627 * 3. brute force search
628 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
629 */
630 cgno = (oldcg + 1) % uspi->s_ncg;
631 for (j = 2; j < uspi->s_ncg; j++) {
632 cgno++;
633 if (cgno >= uspi->s_ncg)
634 cgno = 0;
635 UFS_TEST_FREE_SPACE_CG
636 }
637
638 UFSD("EXIT (FAILED)\n");
639 return 0;
640
641 cg_found:
642 ucpi = ufs_load_cylinder (sb, cgno);
643 if (!ucpi)
644 return 0;
645 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
646 if (!ufs_cg_chkmagic(sb, ucg))
647 ufs_panic (sb, "ufs_alloc_fragments",
648 "internal error, bad magic number on cg %u", cgno);
649 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
650
651 if (count == uspi->s_fpb) {
652 result = ufs_alloccg_block (inode, ucpi, goal, err);
653 if (result == INVBLOCK)
654 return 0;
655 goto succed;
656 }
657
658 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
659 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
660 break;
661
662 if (allocsize == uspi->s_fpb) {
663 result = ufs_alloccg_block (inode, ucpi, goal, err);
664 if (result == INVBLOCK)
665 return 0;
666 goal = ufs_dtogd(uspi, result);
667 for (i = count; i < uspi->s_fpb; i++)
668 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
669 i = uspi->s_fpb - count;
670 dquot_free_block(inode, i);
671
672 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
673 uspi->cs_total.cs_nffree += i;
674 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
675 fs32_add(sb, &ucg->cg_frsum[i], 1);
676 goto succed;
677 }
678
679 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
680 if (result == INVBLOCK)
681 return 0;
682 ret = dquot_alloc_block(inode, count);
683 if (ret) {
684 *err = ret;
685 return 0;
686 }
687 for (i = 0; i < count; i++)
688 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
689
690 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
691 uspi->cs_total.cs_nffree -= count;
692 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
693 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
694
695 if (count != allocsize)
696 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
697
698 succed:
699 ubh_mark_buffer_dirty (USPI_UBH(uspi));
700 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
701 if (sb->s_flags & MS_SYNCHRONOUS) {
702 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
703 ubh_wait_on_buffer (UCPI_UBH(ucpi));
704 }
705 sb->s_dirt = 1;
706
707 result += cgno * uspi->s_fpg;
708 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
709 return result;
710 }
711
712 static u64 ufs_alloccg_block(struct inode *inode,
713 struct ufs_cg_private_info *ucpi,
714 u64 goal, int *err)
715 {
716 struct super_block * sb;
717 struct ufs_sb_private_info * uspi;
718 struct ufs_super_block_first * usb1;
719 struct ufs_cylinder_group * ucg;
720 u64 result, blkno;
721 int ret;
722
723 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
724
725 sb = inode->i_sb;
726 uspi = UFS_SB(sb)->s_uspi;
727 usb1 = ubh_get_usb_first(uspi);
728 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
729
730 if (goal == 0) {
731 goal = ucpi->c_rotor;
732 goto norot;
733 }
734 goal = ufs_blknum (goal);
735 goal = ufs_dtogd(uspi, goal);
736
737 /*
738 * If the requested block is available, use it.
739 */
740 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
741 result = goal;
742 goto gotit;
743 }
744
745 norot:
746 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
747 if (result == INVBLOCK)
748 return INVBLOCK;
749 ucpi->c_rotor = result;
750 gotit:
751 blkno = ufs_fragstoblks(result);
752 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
753 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
754 ufs_clusteracct (sb, ucpi, blkno, -1);
755 ret = dquot_alloc_block(inode, uspi->s_fpb);
756 if (ret) {
757 *err = ret;
758 return INVBLOCK;
759 }
760
761 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
762 uspi->cs_total.cs_nbfree--;
763 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
764
765 if (uspi->fs_magic != UFS2_MAGIC) {
766 unsigned cylno = ufs_cbtocylno((unsigned)result);
767
768 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
769 ufs_cbtorpos((unsigned)result)), 1);
770 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
771 }
772
773 UFSD("EXIT, result %llu\n", (unsigned long long)result);
774
775 return result;
776 }
777
778 static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
779 struct ufs_buffer_head *ubh,
780 unsigned begin, unsigned size,
781 unsigned char *table, unsigned char mask)
782 {
783 unsigned rest, offset;
784 unsigned char *cp;
785
786
787 offset = begin & ~uspi->s_fmask;
788 begin >>= uspi->s_fshift;
789 for (;;) {
790 if ((offset + size) < uspi->s_fsize)
791 rest = size;
792 else
793 rest = uspi->s_fsize - offset;
794 size -= rest;
795 cp = ubh->bh[begin]->b_data + offset;
796 while ((table[*cp++] & mask) == 0 && --rest)
797 ;
798 if (rest || !size)
799 break;
800 begin++;
801 offset = 0;
802 }
803 return (size + rest);
804 }
805
806 /*
807 * Find a block of the specified size in the specified cylinder group.
808 * @sp: pointer to super block
809 * @ucpi: pointer to cylinder group info
810 * @goal: near which block we want find new one
811 * @count: specified size
812 */
813 static u64 ufs_bitmap_search(struct super_block *sb,
814 struct ufs_cg_private_info *ucpi,
815 u64 goal, unsigned count)
816 {
817 /*
818 * Bit patterns for identifying fragments in the block map
819 * used as ((map & mask_arr) == want_arr)
820 */
821 static const int mask_arr[9] = {
822 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
823 };
824 static const int want_arr[9] = {
825 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
826 };
827 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
828 struct ufs_super_block_first *usb1;
829 struct ufs_cylinder_group *ucg;
830 unsigned start, length, loc;
831 unsigned pos, want, blockmap, mask, end;
832 u64 result;
833
834 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
835 (unsigned long long)goal, count);
836
837 usb1 = ubh_get_usb_first (uspi);
838 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
839
840 if (goal)
841 start = ufs_dtogd(uspi, goal) >> 3;
842 else
843 start = ucpi->c_frotor >> 3;
844
845 length = ((uspi->s_fpg + 7) >> 3) - start;
846 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
847 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
848 1 << (count - 1 + (uspi->s_fpb & 7)));
849 if (loc == 0) {
850 length = start + 1;
851 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
852 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
853 ufs_fragtable_other,
854 1 << (count - 1 + (uspi->s_fpb & 7)));
855 if (loc == 0) {
856 ufs_error(sb, "ufs_bitmap_search",
857 "bitmap corrupted on cg %u, start %u,"
858 " length %u, count %u, freeoff %u\n",
859 ucpi->c_cgx, start, length, count,
860 ucpi->c_freeoff);
861 return INVBLOCK;
862 }
863 start = 0;
864 }
865 result = (start + length - loc) << 3;
866 ucpi->c_frotor = result;
867
868 /*
869 * found the byte in the map
870 */
871
872 for (end = result + 8; result < end; result += uspi->s_fpb) {
873 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
874 blockmap <<= 1;
875 mask = mask_arr[count];
876 want = want_arr[count];
877 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
878 if ((blockmap & mask) == want) {
879 UFSD("EXIT, result %llu\n",
880 (unsigned long long)result);
881 return result + pos;
882 }
883 mask <<= 1;
884 want <<= 1;
885 }
886 }
887
888 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
889 ucpi->c_cgx);
890 UFSD("EXIT (FAILED)\n");
891 return INVBLOCK;
892 }
893
894 static void ufs_clusteracct(struct super_block * sb,
895 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
896 {
897 struct ufs_sb_private_info * uspi;
898 int i, start, end, forw, back;
899
900 uspi = UFS_SB(sb)->s_uspi;
901 if (uspi->s_contigsumsize <= 0)
902 return;
903
904 if (cnt > 0)
905 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
906 else
907 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
908
909 /*
910 * Find the size of the cluster going forward.
911 */
912 start = blkno + 1;
913 end = start + uspi->s_contigsumsize;
914 if ( end >= ucpi->c_nclusterblks)
915 end = ucpi->c_nclusterblks;
916 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
917 if (i > end)
918 i = end;
919 forw = i - start;
920
921 /*
922 * Find the size of the cluster going backward.
923 */
924 start = blkno - 1;
925 end = start - uspi->s_contigsumsize;
926 if (end < 0 )
927 end = -1;
928 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
929 if ( i < end)
930 i = end;
931 back = start - i;
932
933 /*
934 * Account for old cluster and the possibly new forward and
935 * back clusters.
936 */
937 i = back + forw + 1;
938 if (i > uspi->s_contigsumsize)
939 i = uspi->s_contigsumsize;
940 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
941 if (back > 0)
942 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
943 if (forw > 0)
944 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
945 }
946
947
948 static unsigned char ufs_fragtable_8fpb[] = {
949 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
950 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
951 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
952 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
953 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
954 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
955 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
956 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
957 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
958 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
959 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
960 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
961 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
962 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
963 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
964 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
965 };
966
967 static unsigned char ufs_fragtable_other[] = {
968 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
969 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
970 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
971 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
972 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
973 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
974 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
975 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
976 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
977 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
978 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
979 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
980 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
981 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
982 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
983 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
984 };
kernel-based virtual machine