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