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
29 static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned);
30 static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *);
31 static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *);
32 static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned);
33 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
34 static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
35
36 /*
37 * Free 'count' fragments from fragment number 'fragment'
38 */
39 void 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
126 failed:
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 */
135 void 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
159 do_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
222 failed_unlock:
223 mutex_unlock(&UFS_SB(sb)->s_lock);
224 failed:
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 */
239 static 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 struct folio *folio, *locked_folio = page_folio(locked_page);
244 const unsigned blks_per_page =
245 1 << (PAGE_SHIFT - inode->i_blkbits);
246 const unsigned mask = blks_per_page - 1;
247 struct address_space * const mapping = inode->i_mapping;
248 pgoff_t index, cur_index, last_index;
249 unsigned pos, j, lblock;
250 sector_t end, i;
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(!folio_test_locked(locked_folio));
258
259 cur_index = locked_folio->index;
260 end = count + beg;
261 last_index = end >> (PAGE_SHIFT - inode->i_blkbits);
262 for (i = beg; i < end; i = (i | mask) + 1) {
263 index = i >> (PAGE_SHIFT - inode->i_blkbits);
264
265 if (likely(cur_index != index)) {
266 folio = ufs_get_locked_folio(mapping, index);
267 if (!folio) /* it was truncated */
268 continue;
269 if (IS_ERR(folio)) {/* or EIO */
270 ufs_error(inode->i_sb, __func__,
271 "read of page %llu failed\n",
272 (unsigned long long)index);
273 continue;
274 }
275 } else
276 folio = locked_folio;
277
278 head = folio_buffers(folio);
279 bh = head;
280 pos = i & mask;
281 for (j = 0; j < pos; ++j)
282 bh = bh->b_this_page;
283
284 if (unlikely(index == last_index))
285 lblock = end & mask;
286 else
287 lblock = blks_per_page;
288
289 do {
290 if (j >= lblock)
291 break;
292 pos = (i - beg) + j;
293
294 if (!buffer_mapped(bh))
295 map_bh(bh, inode->i_sb, oldb + pos);
296 if (bh_read(bh, 0) < 0) {
297 ufs_error(inode->i_sb, __func__,
298 "read of block failed\n");
299 break;
300 }
301
302 UFSD(" change from %llu to %llu, pos %u\n",
303 (unsigned long long)(pos + oldb),
304 (unsigned long long)(pos + newb), pos);
305
306 bh->b_blocknr = newb + pos;
307 clean_bdev_bh_alias(bh);
308 mark_buffer_dirty(bh);
309 ++j;
310 bh = bh->b_this_page;
311 } while (bh != head);
312
313 if (likely(cur_index != index))
314 ufs_put_locked_folio(folio);
315 }
316 UFSD("EXIT\n");
317 }
318
319 static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
320 int sync)
321 {
322 struct buffer_head *bh;
323 sector_t end = beg + n;
324
325 for (; beg < end; ++beg) {
326 bh = sb_getblk(inode->i_sb, beg);
327 lock_buffer(bh);
328 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
329 set_buffer_uptodate(bh);
330 mark_buffer_dirty(bh);
331 unlock_buffer(bh);
332 if (IS_SYNC(inode) || sync)
333 sync_dirty_buffer(bh);
334 brelse(bh);
335 }
336 }
337
338 u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,
339 u64 goal, unsigned count, int *err,
340 struct page *locked_page)
341 {
342 struct super_block * sb;
343 struct ufs_sb_private_info * uspi;
344 struct ufs_super_block_first * usb1;
345 unsigned cgno, oldcount, newcount;
346 u64 tmp, request, result;
347
348 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",
349 inode->i_ino, (unsigned long long)fragment,
350 (unsigned long long)goal, count);
351
352 sb = inode->i_sb;
353 uspi = UFS_SB(sb)->s_uspi;
354 usb1 = ubh_get_usb_first(uspi);
355 *err = -ENOSPC;
356
357 mutex_lock(&UFS_SB(sb)->s_lock);
358 tmp = ufs_data_ptr_to_cpu(sb, p);
359
360 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
361 ufs_warning(sb, "ufs_new_fragments", "internal warning"
362 " fragment %llu, count %u",
363 (unsigned long long)fragment, count);
364 count = uspi->s_fpb - ufs_fragnum(fragment);
365 }
366 oldcount = ufs_fragnum (fragment);
367 newcount = oldcount + count;
368
369 /*
370 * Somebody else has just allocated our fragments
371 */
372 if (oldcount) {
373 if (!tmp) {
374 ufs_error(sb, "ufs_new_fragments", "internal error, "
375 "fragment %llu, tmp %llu\n",
376 (unsigned long long)fragment,
377 (unsigned long long)tmp);
378 mutex_unlock(&UFS_SB(sb)->s_lock);
379 return INVBLOCK;
380 }
381 if (fragment < UFS_I(inode)->i_lastfrag) {
382 UFSD("EXIT (ALREADY ALLOCATED)\n");
383 mutex_unlock(&UFS_SB(sb)->s_lock);
384 return 0;
385 }
386 }
387 else {
388 if (tmp) {
389 UFSD("EXIT (ALREADY ALLOCATED)\n");
390 mutex_unlock(&UFS_SB(sb)->s_lock);
391 return 0;
392 }
393 }
394
395 /*
396 * There is not enough space for user on the device
397 */
398 if (unlikely(ufs_freefrags(uspi) <= uspi->s_root_blocks)) {
399 if (!capable(CAP_SYS_RESOURCE)) {
400 mutex_unlock(&UFS_SB(sb)->s_lock);
401 UFSD("EXIT (FAILED)\n");
402 return 0;
403 }
404 }
405
406 if (goal >= uspi->s_size)
407 goal = 0;
408 if (goal == 0)
409 cgno = ufs_inotocg (inode->i_ino);
410 else
411 cgno = ufs_dtog(uspi, goal);
412
413 /*
414 * allocate new fragment
415 */
416 if (oldcount == 0) {
417 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
418 if (result) {
419 ufs_clear_frags(inode, result + oldcount,
420 newcount - oldcount, locked_page != NULL);
421 *err = 0;
422 write_seqlock(&UFS_I(inode)->meta_lock);
423 ufs_cpu_to_data_ptr(sb, p, result);
424 UFS_I(inode)->i_lastfrag =
425 max(UFS_I(inode)->i_lastfrag, fragment + count);
426 write_sequnlock(&UFS_I(inode)->meta_lock);
427 }
428 mutex_unlock(&UFS_SB(sb)->s_lock);
429 UFSD("EXIT, result %llu\n", (unsigned long long)result);
430 return result;
431 }
432
433 /*
434 * resize block
435 */
436 result = ufs_add_fragments(inode, tmp, oldcount, newcount);
437 if (result) {
438 *err = 0;
439 read_seqlock_excl(&UFS_I(inode)->meta_lock);
440 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
441 fragment + count);
442 read_sequnlock_excl(&UFS_I(inode)->meta_lock);
443 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
444 locked_page != NULL);
445 mutex_unlock(&UFS_SB(sb)->s_lock);
446 UFSD("EXIT, result %llu\n", (unsigned long long)result);
447 return result;
448 }
449
450 /*
451 * allocate new block and move data
452 */
453 if (fs32_to_cpu(sb, usb1->fs_optim) == UFS_OPTSPACE) {
454 request = newcount;
455 if (uspi->cs_total.cs_nffree < uspi->s_space_to_time)
456 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
457 } else {
458 request = uspi->s_fpb;
459 if (uspi->cs_total.cs_nffree > uspi->s_time_to_space)
460 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTSPACE);
461 }
462 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
463 if (result) {
464 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
465 locked_page != NULL);
466 mutex_unlock(&UFS_SB(sb)->s_lock);
467 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
468 uspi->s_sbbase + tmp,
469 uspi->s_sbbase + result, locked_page);
470 *err = 0;
471 write_seqlock(&UFS_I(inode)->meta_lock);
472 ufs_cpu_to_data_ptr(sb, p, result);
473 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
474 fragment + count);
475 write_sequnlock(&UFS_I(inode)->meta_lock);
476 if (newcount < request)
477 ufs_free_fragments (inode, result + newcount, request - newcount);
478 ufs_free_fragments (inode, tmp, oldcount);
479 UFSD("EXIT, result %llu\n", (unsigned long long)result);
480 return result;
481 }
482
483 mutex_unlock(&UFS_SB(sb)->s_lock);
484 UFSD("EXIT (FAILED)\n");
485 return 0;
486 }
487
488 static bool try_add_frags(struct inode *inode, unsigned frags)
489 {
490 unsigned size = frags * i_blocksize(inode);
491 spin_lock(&inode->i_lock);
492 __inode_add_bytes(inode, size);
493 if (unlikely((u32)inode->i_blocks != inode->i_blocks)) {
494 __inode_sub_bytes(inode, size);
495 spin_unlock(&inode->i_lock);
496 return false;
497 }
498 spin_unlock(&inode->i_lock);
499 return true;
500 }
501
502 static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
503 unsigned oldcount, unsigned newcount)
504 {
505 struct super_block * sb;
506 struct ufs_sb_private_info * uspi;
507 struct ufs_cg_private_info * ucpi;
508 struct ufs_cylinder_group * ucg;
509 unsigned cgno, fragno, fragoff, count, fragsize, i;
510
511 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
512 (unsigned long long)fragment, oldcount, newcount);
513
514 sb = inode->i_sb;
515 uspi = UFS_SB(sb)->s_uspi;
516 count = newcount - oldcount;
517
518 cgno = ufs_dtog(uspi, fragment);
519 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
520 return 0;
521 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
522 return 0;
523 ucpi = ufs_load_cylinder (sb, cgno);
524 if (!ucpi)
525 return 0;
526 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
527 if (!ufs_cg_chkmagic(sb, ucg)) {
528 ufs_panic (sb, "ufs_add_fragments",
529 "internal error, bad magic number on cg %u", cgno);
530 return 0;
531 }
532
533 fragno = ufs_dtogd(uspi, fragment);
534 fragoff = ufs_fragnum (fragno);
535 for (i = oldcount; i < newcount; i++)
536 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
537 return 0;
538
539 if (!try_add_frags(inode, count))
540 return 0;
541 /*
542 * Block can be extended
543 */
544 ucg->cg_time = ufs_get_seconds(sb);
545 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
546 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
547 break;
548 fragsize = i - oldcount;
549 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
550 ufs_panic (sb, "ufs_add_fragments",
551 "internal error or corrupted bitmap on cg %u", cgno);
552 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
553 if (fragsize != count)
554 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
555 for (i = oldcount; i < newcount; i++)
556 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
557
558 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
559 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
560 uspi->cs_total.cs_nffree -= count;
561
562 ubh_mark_buffer_dirty (USPI_UBH(uspi));
563 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
564 if (sb->s_flags & SB_SYNCHRONOUS)
565 ubh_sync_block(UCPI_UBH(ucpi));
566 ufs_mark_sb_dirty(sb);
567
568 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
569
570 return fragment;
571 }
572
573 #define UFS_TEST_FREE_SPACE_CG \
574 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
575 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
576 goto cg_found; \
577 for (k = count; k < uspi->s_fpb; k++) \
578 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
579 goto cg_found;
580
581 static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
582 u64 goal, unsigned count, int *err)
583 {
584 struct super_block * sb;
585 struct ufs_sb_private_info * uspi;
586 struct ufs_cg_private_info * ucpi;
587 struct ufs_cylinder_group * ucg;
588 unsigned oldcg, i, j, k, allocsize;
589 u64 result;
590
591 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
592 inode->i_ino, cgno, (unsigned long long)goal, count);
593
594 sb = inode->i_sb;
595 uspi = UFS_SB(sb)->s_uspi;
596 oldcg = cgno;
597
598 /*
599 * 1. searching on preferred cylinder group
600 */
601 UFS_TEST_FREE_SPACE_CG
602
603 /*
604 * 2. quadratic rehash
605 */
606 for (j = 1; j < uspi->s_ncg; j *= 2) {
607 cgno += j;
608 if (cgno >= uspi->s_ncg)
609 cgno -= uspi->s_ncg;
610 UFS_TEST_FREE_SPACE_CG
611 }
612
613 /*
614 * 3. brute force search
615 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
616 */
617 cgno = (oldcg + 1) % uspi->s_ncg;
618 for (j = 2; j < uspi->s_ncg; j++) {
619 cgno++;
620 if (cgno >= uspi->s_ncg)
621 cgno = 0;
622 UFS_TEST_FREE_SPACE_CG
623 }
624
625 UFSD("EXIT (FAILED)\n");
626 return 0;
627
628 cg_found:
629 ucpi = ufs_load_cylinder (sb, cgno);
630 if (!ucpi)
631 return 0;
632 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
633 if (!ufs_cg_chkmagic(sb, ucg))
634 ufs_panic (sb, "ufs_alloc_fragments",
635 "internal error, bad magic number on cg %u", cgno);
636 ucg->cg_time = ufs_get_seconds(sb);
637
638 if (count == uspi->s_fpb) {
639 result = ufs_alloccg_block (inode, ucpi, goal, err);
640 if (result == INVBLOCK)
641 return 0;
642 goto succed;
643 }
644
645 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
646 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
647 break;
648
649 if (allocsize == uspi->s_fpb) {
650 result = ufs_alloccg_block (inode, ucpi, goal, err);
651 if (result == INVBLOCK)
652 return 0;
653 goal = ufs_dtogd(uspi, result);
654 for (i = count; i < uspi->s_fpb; i++)
655 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
656 i = uspi->s_fpb - count;
657
658 inode_sub_bytes(inode, i << uspi->s_fshift);
659 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
660 uspi->cs_total.cs_nffree += i;
661 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
662 fs32_add(sb, &ucg->cg_frsum[i], 1);
663 goto succed;
664 }
665
666 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
667 if (result == INVBLOCK)
668 return 0;
669 if (!try_add_frags(inode, count))
670 return 0;
671 for (i = 0; i < count; i++)
672 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
673
674 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
675 uspi->cs_total.cs_nffree -= count;
676 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
677 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
678
679 if (count != allocsize)
680 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
681
682 succed:
683 ubh_mark_buffer_dirty (USPI_UBH(uspi));
684 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
685 if (sb->s_flags & SB_SYNCHRONOUS)
686 ubh_sync_block(UCPI_UBH(ucpi));
687 ufs_mark_sb_dirty(sb);
688
689 result += cgno * uspi->s_fpg;
690 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
691 return result;
692 }
693
694 static u64 ufs_alloccg_block(struct inode *inode,
695 struct ufs_cg_private_info *ucpi,
696 u64 goal, int *err)
697 {
698 struct super_block * sb;
699 struct ufs_sb_private_info * uspi;
700 struct ufs_cylinder_group * ucg;
701 u64 result, blkno;
702
703 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
704
705 sb = inode->i_sb;
706 uspi = UFS_SB(sb)->s_uspi;
707 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
708
709 if (goal == 0) {
710 goal = ucpi->c_rotor;
711 goto norot;
712 }
713 goal = ufs_blknum (goal);
714 goal = ufs_dtogd(uspi, goal);
715
716 /*
717 * If the requested block is available, use it.
718 */
719 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
720 result = goal;
721 goto gotit;
722 }
723
724 norot:
725 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
726 if (result == INVBLOCK)
727 return INVBLOCK;
728 ucpi->c_rotor = result;
729 gotit:
730 if (!try_add_frags(inode, uspi->s_fpb))
731 return 0;
732 blkno = ufs_fragstoblks(result);
733 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
734 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
735 ufs_clusteracct (sb, ucpi, blkno, -1);
736
737 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
738 uspi->cs_total.cs_nbfree--;
739 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
740
741 if (uspi->fs_magic != UFS2_MAGIC) {
742 unsigned cylno = ufs_cbtocylno((unsigned)result);
743
744 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
745 ufs_cbtorpos((unsigned)result)), 1);
746 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
747 }
748
749 UFSD("EXIT, result %llu\n", (unsigned long long)result);
750
751 return result;
752 }
753
754 static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
755 struct ufs_buffer_head *ubh,
756 unsigned begin, unsigned size,
757 unsigned char *table, unsigned char mask)
758 {
759 unsigned rest, offset;
760 unsigned char *cp;
761
762
763 offset = begin & ~uspi->s_fmask;
764 begin >>= uspi->s_fshift;
765 for (;;) {
766 if ((offset + size) < uspi->s_fsize)
767 rest = size;
768 else
769 rest = uspi->s_fsize - offset;
770 size -= rest;
771 cp = ubh->bh[begin]->b_data + offset;
772 while ((table[*cp++] & mask) == 0 && --rest)
773 ;
774 if (rest || !size)
775 break;
776 begin++;
777 offset = 0;
778 }
779 return (size + rest);
780 }
781
782 /*
783 * Find a block of the specified size in the specified cylinder group.
784 * @sp: pointer to super block
785 * @ucpi: pointer to cylinder group info
786 * @goal: near which block we want find new one
787 * @count: specified size
788 */
789 static u64 ufs_bitmap_search(struct super_block *sb,
790 struct ufs_cg_private_info *ucpi,
791 u64 goal, unsigned count)
792 {
793 /*
794 * Bit patterns for identifying fragments in the block map
795 * used as ((map & mask_arr) == want_arr)
796 */
797 static const int mask_arr[9] = {
798 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
799 };
800 static const int want_arr[9] = {
801 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
802 };
803 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
804 unsigned start, length, loc;
805 unsigned pos, want, blockmap, mask, end;
806 u64 result;
807
808 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
809 (unsigned long long)goal, count);
810
811 if (goal)
812 start = ufs_dtogd(uspi, goal) >> 3;
813 else
814 start = ucpi->c_frotor >> 3;
815
816 length = ((uspi->s_fpg + 7) >> 3) - start;
817 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
818 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
819 1 << (count - 1 + (uspi->s_fpb & 7)));
820 if (loc == 0) {
821 length = start + 1;
822 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
823 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
824 ufs_fragtable_other,
825 1 << (count - 1 + (uspi->s_fpb & 7)));
826 if (loc == 0) {
827 ufs_error(sb, "ufs_bitmap_search",
828 "bitmap corrupted on cg %u, start %u,"
829 " length %u, count %u, freeoff %u\n",
830 ucpi->c_cgx, start, length, count,
831 ucpi->c_freeoff);
832 return INVBLOCK;
833 }
834 start = 0;
835 }
836 result = (start + length - loc) << 3;
837 ucpi->c_frotor = result;
838
839 /*
840 * found the byte in the map
841 */
842
843 for (end = result + 8; result < end; result += uspi->s_fpb) {
844 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
845 blockmap <<= 1;
846 mask = mask_arr[count];
847 want = want_arr[count];
848 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
849 if ((blockmap & mask) == want) {
850 UFSD("EXIT, result %llu\n",
851 (unsigned long long)result);
852 return result + pos;
853 }
854 mask <<= 1;
855 want <<= 1;
856 }
857 }
858
859 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
860 ucpi->c_cgx);
861 UFSD("EXIT (FAILED)\n");
862 return INVBLOCK;
863 }
864
865 static void ufs_clusteracct(struct super_block * sb,
866 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
867 {
868 struct ufs_sb_private_info * uspi;
869 int i, start, end, forw, back;
870
871 uspi = UFS_SB(sb)->s_uspi;
872 if (uspi->s_contigsumsize <= 0)
873 return;
874
875 if (cnt > 0)
876 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
877 else
878 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
879
880 /*
881 * Find the size of the cluster going forward.
882 */
883 start = blkno + 1;
884 end = start + uspi->s_contigsumsize;
885 if ( end >= ucpi->c_nclusterblks)
886 end = ucpi->c_nclusterblks;
887 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
888 if (i > end)
889 i = end;
890 forw = i - start;
891
892 /*
893 * Find the size of the cluster going backward.
894 */
895 start = blkno - 1;
896 end = start - uspi->s_contigsumsize;
897 if (end < 0 )
898 end = -1;
899 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
900 if ( i < end)
901 i = end;
902 back = start - i;
903
904 /*
905 * Account for old cluster and the possibly new forward and
906 * back clusters.
907 */
908 i = back + forw + 1;
909 if (i > uspi->s_contigsumsize)
910 i = uspi->s_contigsumsize;
911 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
912 if (back > 0)
913 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
914 if (forw > 0)
915 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
916 }
917
918
919 static unsigned char ufs_fragtable_8fpb[] = {
920 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
921 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
922 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
923 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
924 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
925 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
926 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
927 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
928 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
929 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
930 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
931 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
932 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
933 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
934 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
935 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
936 };
937
938 static unsigned char ufs_fragtable_other[] = {
939 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
940 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
941 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
942 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
943 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
944 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
945 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
946 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
947 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
948 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
949 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
950 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
951 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
952 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
953 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
954 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
955 };
956
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.