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