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