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