xref: /linux/fs/ufs/balloc.c (revision 0ea5c948cb64bab5bc7a5516774eb8536f05aa0d)
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 	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 
ufs_clear_frags(struct inode * inode,sector_t beg,unsigned int n,int sync)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 
ufs_new_fragments(struct inode * inode,void * p,u64 fragment,u64 goal,unsigned count,int * err,struct page * locked_page)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 
try_add_frags(struct inode * inode,unsigned frags)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 
ufs_add_fragments(struct inode * inode,u64 fragment,unsigned oldcount,unsigned newcount)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 
ufs_alloc_fragments(struct inode * inode,unsigned cgno,u64 goal,unsigned count,int * err)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 
ufs_alloccg_block(struct inode * inode,struct ufs_cg_private_info * ucpi,u64 goal,int * err)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 
ubh_scanc(struct ufs_sb_private_info * uspi,struct ufs_buffer_head * ubh,unsigned begin,unsigned size,unsigned char * table,unsigned char mask)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  */
ufs_bitmap_search(struct super_block * sb,struct ufs_cg_private_info * ucpi,u64 goal,unsigned count)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 
ufs_clusteracct(struct super_block * sb,struct ufs_cg_private_info * ucpi,unsigned blkno,int cnt)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