xref: /openbmc/linux/fs/ufs/balloc.c (revision 87c2ce3b)
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 
9 #include <linux/fs.h>
10 #include <linux/ufs_fs.h>
11 #include <linux/stat.h>
12 #include <linux/time.h>
13 #include <linux/string.h>
14 #include <linux/quotaops.h>
15 #include <linux/buffer_head.h>
16 #include <linux/sched.h>
17 #include <linux/bitops.h>
18 #include <asm/byteorder.h>
19 
20 #include "swab.h"
21 #include "util.h"
22 
23 #undef UFS_BALLOC_DEBUG
24 
25 #ifdef UFS_BALLOC_DEBUG
26 #define UFSD(x) printk("(%s, %d), %s:", __FILE__, __LINE__, __FUNCTION__); printk x;
27 #else
28 #define UFSD(x)
29 #endif
30 
31 static unsigned ufs_add_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
32 static unsigned ufs_alloc_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
33 static unsigned ufs_alloccg_block (struct inode *, struct ufs_cg_private_info *, unsigned, int *);
34 static unsigned ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, unsigned, unsigned);
35 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
36 static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
37 
38 /*
39  * Free 'count' fragments from fragment number 'fragment'
40  */
41 void ufs_free_fragments (struct inode * inode, unsigned fragment, unsigned count) {
42 	struct super_block * sb;
43 	struct ufs_sb_private_info * uspi;
44 	struct ufs_super_block_first * usb1;
45 	struct ufs_cg_private_info * ucpi;
46 	struct ufs_cylinder_group * ucg;
47 	unsigned cgno, bit, end_bit, bbase, blkmap, i, blkno, cylno;
48 
49 	sb = inode->i_sb;
50 	uspi = UFS_SB(sb)->s_uspi;
51 	usb1 = ubh_get_usb_first(USPI_UBH);
52 
53 	UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
54 
55 	if (ufs_fragnum(fragment) + count > uspi->s_fpg)
56 		ufs_error (sb, "ufs_free_fragments", "internal error");
57 
58 	lock_super(sb);
59 
60 	cgno = ufs_dtog(fragment);
61 	bit = ufs_dtogd(fragment);
62 	if (cgno >= uspi->s_ncg) {
63 		ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
64 		goto failed;
65 	}
66 
67 	ucpi = ufs_load_cylinder (sb, cgno);
68 	if (!ucpi)
69 		goto failed;
70 	ucg = ubh_get_ucg (UCPI_UBH);
71 	if (!ufs_cg_chkmagic(sb, ucg)) {
72 		ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
73 		goto failed;
74 	}
75 
76 	end_bit = bit + count;
77 	bbase = ufs_blknum (bit);
78 	blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
79 	ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
80 	for (i = bit; i < end_bit; i++) {
81 		if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, i))
82 			ubh_setbit (UCPI_UBH, ucpi->c_freeoff, i);
83 		else 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 	fs32_add(sb, &usb1->fs_cstotal.cs_nffree, count);
92 	fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
93 	blkmap = ubh_blkmap (UCPI_UBH, 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->c_freeoff, blkno)) {
101 		fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
102 		fs32_sub(sb, &usb1->fs_cstotal.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 		fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
108 		fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
109 		cylno = ufs_cbtocylno (bbase);
110 		fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(bbase)), 1);
111 		fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
112 	}
113 
114 	ubh_mark_buffer_dirty (USPI_UBH);
115 	ubh_mark_buffer_dirty (UCPI_UBH);
116 	if (sb->s_flags & MS_SYNCHRONOUS) {
117 		ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
118 		ubh_wait_on_buffer (UCPI_UBH);
119 	}
120 	sb->s_dirt = 1;
121 
122 	unlock_super (sb);
123 	UFSD(("EXIT\n"))
124 	return;
125 
126 failed:
127 	unlock_super (sb);
128 	UFSD(("EXIT (FAILED)\n"))
129 	return;
130 }
131 
132 /*
133  * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
134  */
135 void ufs_free_blocks (struct inode * inode, unsigned fragment, unsigned count) {
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, blkno, i, cylno;
142 
143 	sb = inode->i_sb;
144 	uspi = UFS_SB(sb)->s_uspi;
145 	usb1 = ubh_get_usb_first(USPI_UBH);
146 
147 	UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
148 
149 	if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
150 		ufs_error (sb, "ufs_free_blocks", "internal error, "
151 			"fragment %u, count %u\n", fragment, count);
152 		goto failed;
153 	}
154 
155 	lock_super(sb);
156 
157 do_more:
158 	overflow = 0;
159 	cgno = ufs_dtog (fragment);
160 	bit = ufs_dtogd (fragment);
161 	if (cgno >= uspi->s_ncg) {
162 		ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
163 		goto failed;
164 	}
165 	end_bit = bit + count;
166 	if (end_bit > uspi->s_fpg) {
167 		overflow = bit + count - uspi->s_fpg;
168 		count -= overflow;
169 		end_bit -= overflow;
170 	}
171 
172 	ucpi = ufs_load_cylinder (sb, cgno);
173 	if (!ucpi)
174 		goto failed;
175 	ucg = ubh_get_ucg (UCPI_UBH);
176 	if (!ufs_cg_chkmagic(sb, ucg)) {
177 		ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
178 		goto failed;
179 	}
180 
181 	for (i = bit; i < end_bit; i += uspi->s_fpb) {
182 		blkno = ufs_fragstoblks(i);
183 		if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
184 			ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
185 		}
186 		ubh_setblock(UCPI_UBH, ucpi->c_freeoff, blkno);
187 		if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
188 			ufs_clusteracct (sb, ucpi, blkno, 1);
189 		DQUOT_FREE_BLOCK(inode, uspi->s_fpb);
190 
191 		fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
192 		fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1);
193 		fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
194 		cylno = ufs_cbtocylno(i);
195 		fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(i)), 1);
196 		fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
197 	}
198 
199 	ubh_mark_buffer_dirty (USPI_UBH);
200 	ubh_mark_buffer_dirty (UCPI_UBH);
201 	if (sb->s_flags & MS_SYNCHRONOUS) {
202 		ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
203 		ubh_wait_on_buffer (UCPI_UBH);
204 	}
205 
206 	if (overflow) {
207 		fragment += count;
208 		count = overflow;
209 		goto do_more;
210 	}
211 
212 	sb->s_dirt = 1;
213 	unlock_super (sb);
214 	UFSD(("EXIT\n"))
215 	return;
216 
217 failed:
218 	unlock_super (sb);
219 	UFSD(("EXIT (FAILED)\n"))
220 	return;
221 }
222 
223 
224 
225 #define NULLIFY_FRAGMENTS \
226 	for (i = oldcount; i < newcount; i++) { \
227 		bh = sb_getblk(sb, result + i); \
228 		memset (bh->b_data, 0, sb->s_blocksize); \
229 		set_buffer_uptodate(bh); \
230 		mark_buffer_dirty (bh); \
231 		if (IS_SYNC(inode)) \
232 			sync_dirty_buffer(bh); \
233 		brelse (bh); \
234 	}
235 
236 unsigned ufs_new_fragments (struct inode * inode, __fs32 * p, unsigned fragment,
237 	unsigned goal, unsigned count, int * err )
238 {
239 	struct super_block * sb;
240 	struct ufs_sb_private_info * uspi;
241 	struct ufs_super_block_first * usb1;
242 	struct buffer_head * bh;
243 	unsigned cgno, oldcount, newcount, tmp, request, i, result;
244 
245 	UFSD(("ENTER, ino %lu, fragment %u, goal %u, count %u\n", inode->i_ino, fragment, goal, count))
246 
247 	sb = inode->i_sb;
248 	uspi = UFS_SB(sb)->s_uspi;
249 	usb1 = ubh_get_usb_first(USPI_UBH);
250 	*err = -ENOSPC;
251 
252 	lock_super (sb);
253 
254 	tmp = fs32_to_cpu(sb, *p);
255 	if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
256 		ufs_warning (sb, "ufs_new_fragments", "internal warning"
257 			" fragment %u, count %u", fragment, count);
258 		count = uspi->s_fpb - ufs_fragnum(fragment);
259 	}
260 	oldcount = ufs_fragnum (fragment);
261 	newcount = oldcount + count;
262 
263 	/*
264 	 * Somebody else has just allocated our fragments
265 	 */
266 	if (oldcount) {
267 		if (!tmp) {
268 			ufs_error (sb, "ufs_new_fragments", "internal error, "
269 				"fragment %u, tmp %u\n", fragment, tmp);
270 			unlock_super (sb);
271 			return (unsigned)-1;
272 		}
273 		if (fragment < UFS_I(inode)->i_lastfrag) {
274 			UFSD(("EXIT (ALREADY ALLOCATED)\n"))
275 			unlock_super (sb);
276 			return 0;
277 		}
278 	}
279 	else {
280 		if (tmp) {
281 			UFSD(("EXIT (ALREADY ALLOCATED)\n"))
282 			unlock_super(sb);
283 			return 0;
284 		}
285 	}
286 
287 	/*
288 	 * There is not enough space for user on the device
289 	 */
290 	if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(usb1, UFS_MINFREE) <= 0) {
291 		unlock_super (sb);
292 		UFSD(("EXIT (FAILED)\n"))
293 		return 0;
294 	}
295 
296 	if (goal >= uspi->s_size)
297 		goal = 0;
298 	if (goal == 0)
299 		cgno = ufs_inotocg (inode->i_ino);
300 	else
301 		cgno = ufs_dtog (goal);
302 
303 	/*
304 	 * allocate new fragment
305 	 */
306 	if (oldcount == 0) {
307 		result = ufs_alloc_fragments (inode, cgno, goal, count, err);
308 		if (result) {
309 			*p = cpu_to_fs32(sb, result);
310 			*err = 0;
311 			inode->i_blocks += count << uspi->s_nspfshift;
312 			UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
313 			NULLIFY_FRAGMENTS
314 		}
315 		unlock_super(sb);
316 		UFSD(("EXIT, result %u\n", result))
317 		return result;
318 	}
319 
320 	/*
321 	 * resize block
322 	 */
323 	result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
324 	if (result) {
325 		*err = 0;
326 		inode->i_blocks += count << uspi->s_nspfshift;
327 		UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
328 		NULLIFY_FRAGMENTS
329 		unlock_super(sb);
330 		UFSD(("EXIT, result %u\n", result))
331 		return result;
332 	}
333 
334 	/*
335 	 * allocate new block and move data
336 	 */
337 	switch (fs32_to_cpu(sb, usb1->fs_optim)) {
338 	    case UFS_OPTSPACE:
339 		request = newcount;
340 		if (uspi->s_minfree < 5 || fs32_to_cpu(sb, usb1->fs_cstotal.cs_nffree)
341 		    > uspi->s_dsize * uspi->s_minfree / (2 * 100) )
342 			break;
343 		usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
344 		break;
345 	    default:
346 		usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
347 
348 	    case UFS_OPTTIME:
349 		request = uspi->s_fpb;
350 		if (fs32_to_cpu(sb, usb1->fs_cstotal.cs_nffree) < uspi->s_dsize *
351 		    (uspi->s_minfree - 2) / 100)
352 			break;
353 		usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
354 		break;
355 	}
356 	result = ufs_alloc_fragments (inode, cgno, goal, request, err);
357 	if (result) {
358 		for (i = 0; i < oldcount; i++) {
359 			bh = sb_bread(sb, tmp + i);
360 			if(bh)
361 			{
362 				clear_buffer_dirty(bh);
363 				bh->b_blocknr = result + i;
364 				mark_buffer_dirty (bh);
365 				if (IS_SYNC(inode))
366 					sync_dirty_buffer(bh);
367 				brelse (bh);
368 			}
369 			else
370 			{
371 				printk(KERN_ERR "ufs_new_fragments: bread fail\n");
372 				unlock_super(sb);
373 				return 0;
374 			}
375 		}
376 		*p = cpu_to_fs32(sb, result);
377 		*err = 0;
378 		inode->i_blocks += count << uspi->s_nspfshift;
379 		UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
380 		NULLIFY_FRAGMENTS
381 		unlock_super(sb);
382 		if (newcount < request)
383 			ufs_free_fragments (inode, result + newcount, request - newcount);
384 		ufs_free_fragments (inode, tmp, oldcount);
385 		UFSD(("EXIT, result %u\n", result))
386 		return result;
387 	}
388 
389 	unlock_super(sb);
390 	UFSD(("EXIT (FAILED)\n"))
391 	return 0;
392 }
393 
394 static unsigned
395 ufs_add_fragments (struct inode * inode, unsigned fragment,
396 		   unsigned oldcount, unsigned newcount, int * err)
397 {
398 	struct super_block * sb;
399 	struct ufs_sb_private_info * uspi;
400 	struct ufs_super_block_first * usb1;
401 	struct ufs_cg_private_info * ucpi;
402 	struct ufs_cylinder_group * ucg;
403 	unsigned cgno, fragno, fragoff, count, fragsize, i;
404 
405 	UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
406 
407 	sb = inode->i_sb;
408 	uspi = UFS_SB(sb)->s_uspi;
409 	usb1 = ubh_get_usb_first (USPI_UBH);
410 	count = newcount - oldcount;
411 
412 	cgno = ufs_dtog(fragment);
413 	if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
414 		return 0;
415 	if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
416 		return 0;
417 	ucpi = ufs_load_cylinder (sb, cgno);
418 	if (!ucpi)
419 		return 0;
420 	ucg = ubh_get_ucg (UCPI_UBH);
421 	if (!ufs_cg_chkmagic(sb, ucg)) {
422 		ufs_panic (sb, "ufs_add_fragments",
423 			"internal error, bad magic number on cg %u", cgno);
424 		return 0;
425 	}
426 
427 	fragno = ufs_dtogd (fragment);
428 	fragoff = ufs_fragnum (fragno);
429 	for (i = oldcount; i < newcount; i++)
430 		if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
431 			return 0;
432 	/*
433 	 * Block can be extended
434 	 */
435 	ucg->cg_time = cpu_to_fs32(sb, get_seconds());
436 	for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
437 		if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
438 			break;
439 	fragsize = i - oldcount;
440 	if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
441 		ufs_panic (sb, "ufs_add_fragments",
442 			"internal error or corrupted bitmap on cg %u", cgno);
443 	fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
444 	if (fragsize != count)
445 		fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
446 	for (i = oldcount; i < newcount; i++)
447 		ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
448 	if(DQUOT_ALLOC_BLOCK(inode, count)) {
449 		*err = -EDQUOT;
450 		return 0;
451 	}
452 
453 	fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
454 	fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
455 	fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
456 
457 	ubh_mark_buffer_dirty (USPI_UBH);
458 	ubh_mark_buffer_dirty (UCPI_UBH);
459 	if (sb->s_flags & MS_SYNCHRONOUS) {
460 		ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
461 		ubh_wait_on_buffer (UCPI_UBH);
462 	}
463 	sb->s_dirt = 1;
464 
465 	UFSD(("EXIT, fragment %u\n", fragment))
466 
467 	return fragment;
468 }
469 
470 #define UFS_TEST_FREE_SPACE_CG \
471 	ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
472 	if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
473 		goto cg_found; \
474 	for (k = count; k < uspi->s_fpb; k++) \
475 		if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
476 			goto cg_found;
477 
478 static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
479 	unsigned goal, unsigned count, int * err)
480 {
481 	struct super_block * sb;
482 	struct ufs_sb_private_info * uspi;
483 	struct ufs_super_block_first * usb1;
484 	struct ufs_cg_private_info * ucpi;
485 	struct ufs_cylinder_group * ucg;
486 	unsigned oldcg, i, j, k, result, allocsize;
487 
488 	UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
489 
490 	sb = inode->i_sb;
491 	uspi = UFS_SB(sb)->s_uspi;
492 	usb1 = ubh_get_usb_first(USPI_UBH);
493 	oldcg = cgno;
494 
495 	/*
496 	 * 1. searching on preferred cylinder group
497 	 */
498 	UFS_TEST_FREE_SPACE_CG
499 
500 	/*
501 	 * 2. quadratic rehash
502 	 */
503 	for (j = 1; j < uspi->s_ncg; j *= 2) {
504 		cgno += j;
505 		if (cgno >= uspi->s_ncg)
506 			cgno -= uspi->s_ncg;
507 		UFS_TEST_FREE_SPACE_CG
508 	}
509 
510 	/*
511 	 * 3. brute force search
512 	 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
513 	 */
514 	cgno = (oldcg + 1) % uspi->s_ncg;
515 	for (j = 2; j < uspi->s_ncg; j++) {
516 		cgno++;
517 		if (cgno >= uspi->s_ncg)
518 			cgno = 0;
519 		UFS_TEST_FREE_SPACE_CG
520 	}
521 
522 	UFSD(("EXIT (FAILED)\n"))
523 	return 0;
524 
525 cg_found:
526 	ucpi = ufs_load_cylinder (sb, cgno);
527 	if (!ucpi)
528 		return 0;
529 	ucg = ubh_get_ucg (UCPI_UBH);
530 	if (!ufs_cg_chkmagic(sb, ucg))
531 		ufs_panic (sb, "ufs_alloc_fragments",
532 			"internal error, bad magic number on cg %u", cgno);
533 	ucg->cg_time = cpu_to_fs32(sb, get_seconds());
534 
535 	if (count == uspi->s_fpb) {
536 		result = ufs_alloccg_block (inode, ucpi, goal, err);
537 		if (result == (unsigned)-1)
538 			return 0;
539 		goto succed;
540 	}
541 
542 	for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
543 		if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
544 			break;
545 
546 	if (allocsize == uspi->s_fpb) {
547 		result = ufs_alloccg_block (inode, ucpi, goal, err);
548 		if (result == (unsigned)-1)
549 			return 0;
550 		goal = ufs_dtogd (result);
551 		for (i = count; i < uspi->s_fpb; i++)
552 			ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
553 		i = uspi->s_fpb - count;
554 		DQUOT_FREE_BLOCK(inode, i);
555 
556 		fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
557 		fs32_add(sb, &usb1->fs_cstotal.cs_nffree, i);
558 		fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
559 		fs32_add(sb, &ucg->cg_frsum[i], 1);
560 		goto succed;
561 	}
562 
563 	result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
564 	if (result == (unsigned)-1)
565 		return 0;
566 	if(DQUOT_ALLOC_BLOCK(inode, count)) {
567 		*err = -EDQUOT;
568 		return 0;
569 	}
570 	for (i = 0; i < count; i++)
571 		ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
572 
573 	fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
574 	fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count);
575 	fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
576 	fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
577 
578 	if (count != allocsize)
579 		fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
580 
581 succed:
582 	ubh_mark_buffer_dirty (USPI_UBH);
583 	ubh_mark_buffer_dirty (UCPI_UBH);
584 	if (sb->s_flags & MS_SYNCHRONOUS) {
585 		ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **)&ucpi);
586 		ubh_wait_on_buffer (UCPI_UBH);
587 	}
588 	sb->s_dirt = 1;
589 
590 	result += cgno * uspi->s_fpg;
591 	UFSD(("EXIT3, result %u\n", result))
592 	return result;
593 }
594 
595 static unsigned ufs_alloccg_block (struct inode * inode,
596 	struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
597 {
598 	struct super_block * sb;
599 	struct ufs_sb_private_info * uspi;
600 	struct ufs_super_block_first * usb1;
601 	struct ufs_cylinder_group * ucg;
602 	unsigned result, cylno, blkno;
603 
604 	UFSD(("ENTER, goal %u\n", goal))
605 
606 	sb = inode->i_sb;
607 	uspi = UFS_SB(sb)->s_uspi;
608 	usb1 = ubh_get_usb_first(USPI_UBH);
609 	ucg = ubh_get_ucg(UCPI_UBH);
610 
611 	if (goal == 0) {
612 		goal = ucpi->c_rotor;
613 		goto norot;
614 	}
615 	goal = ufs_blknum (goal);
616 	goal = ufs_dtogd (goal);
617 
618 	/*
619 	 * If the requested block is available, use it.
620 	 */
621 	if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
622 		result = goal;
623 		goto gotit;
624 	}
625 
626 norot:
627 	result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
628 	if (result == (unsigned)-1)
629 		return (unsigned)-1;
630 	ucpi->c_rotor = result;
631 gotit:
632 	blkno = ufs_fragstoblks(result);
633 	ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
634 	if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
635 		ufs_clusteracct (sb, ucpi, blkno, -1);
636 	if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
637 		*err = -EDQUOT;
638 		return (unsigned)-1;
639 	}
640 
641 	fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
642 	fs32_sub(sb, &usb1->fs_cstotal.cs_nbfree, 1);
643 	fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
644 	cylno = ufs_cbtocylno(result);
645 	fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1);
646 	fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
647 
648 	UFSD(("EXIT, result %u\n", result))
649 
650 	return result;
651 }
652 
653 static unsigned ufs_bitmap_search (struct super_block * sb,
654 	struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
655 {
656 	struct ufs_sb_private_info * uspi;
657 	struct ufs_super_block_first * usb1;
658 	struct ufs_cylinder_group * ucg;
659 	unsigned start, length, location, result;
660 	unsigned possition, fragsize, blockmap, mask;
661 
662 	UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
663 
664 	uspi = UFS_SB(sb)->s_uspi;
665 	usb1 = ubh_get_usb_first (USPI_UBH);
666 	ucg = ubh_get_ucg(UCPI_UBH);
667 
668 	if (goal)
669 		start = ufs_dtogd(goal) >> 3;
670 	else
671 		start = ucpi->c_frotor >> 3;
672 
673 	length = ((uspi->s_fpg + 7) >> 3) - start;
674 	location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
675 		(uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
676 		1 << (count - 1 + (uspi->s_fpb & 7)));
677 	if (location == 0) {
678 		length = start + 1;
679 		location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length,
680 			(uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
681 			1 << (count - 1 + (uspi->s_fpb & 7)));
682 		if (location == 0) {
683 			ufs_error (sb, "ufs_bitmap_search",
684 			"bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
685 			ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
686 			return (unsigned)-1;
687 		}
688 		start = 0;
689 	}
690 	result = (start + length - location) << 3;
691 	ucpi->c_frotor = result;
692 
693 	/*
694 	 * found the byte in the map
695 	 */
696 	blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
697 	fragsize = 0;
698 	for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
699 		if (blockmap & mask) {
700 			if (!(possition & uspi->s_fpbmask))
701 				fragsize = 1;
702 			else
703 				fragsize++;
704 		}
705 		else {
706 			if (fragsize == count) {
707 				result += possition - count;
708 				UFSD(("EXIT, result %u\n", result))
709 				return result;
710 			}
711 			fragsize = 0;
712 		}
713 	}
714 	if (fragsize == count) {
715 		result += possition - count;
716 		UFSD(("EXIT, result %u\n", result))
717 		return result;
718 	}
719 	ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
720 	UFSD(("EXIT (FAILED)\n"))
721 	return (unsigned)-1;
722 }
723 
724 static void ufs_clusteracct(struct super_block * sb,
725 	struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
726 {
727 	struct ufs_sb_private_info * uspi;
728 	int i, start, end, forw, back;
729 
730 	uspi = UFS_SB(sb)->s_uspi;
731 	if (uspi->s_contigsumsize <= 0)
732 		return;
733 
734 	if (cnt > 0)
735 		ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
736 	else
737 		ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
738 
739 	/*
740 	 * Find the size of the cluster going forward.
741 	 */
742 	start = blkno + 1;
743 	end = start + uspi->s_contigsumsize;
744 	if ( end >= ucpi->c_nclusterblks)
745 		end = ucpi->c_nclusterblks;
746 	i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
747 	if (i > end)
748 		i = end;
749 	forw = i - start;
750 
751 	/*
752 	 * Find the size of the cluster going backward.
753 	 */
754 	start = blkno - 1;
755 	end = start - uspi->s_contigsumsize;
756 	if (end < 0 )
757 		end = -1;
758 	i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
759 	if ( i < end)
760 		i = end;
761 	back = start - i;
762 
763 	/*
764 	 * Account for old cluster and the possibly new forward and
765 	 * back clusters.
766 	 */
767 	i = back + forw + 1;
768 	if (i > uspi->s_contigsumsize)
769 		i = uspi->s_contigsumsize;
770 	fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2)), cnt);
771 	if (back > 0)
772 		fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2)), cnt);
773 	if (forw > 0)
774 		fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2)), cnt);
775 }
776 
777 
778 static unsigned char ufs_fragtable_8fpb[] = {
779 	0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
780 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
781 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
782 	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
783 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
784 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
785 	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
786 	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
787 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
788 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
789 	0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
790 	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
791 	0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
792 	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
793 	0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
794 	0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
795 };
796 
797 static unsigned char ufs_fragtable_other[] = {
798 	0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
799 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
800 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
801 	0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
802 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
803 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
804 	0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
805 	0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
806 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
807 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
808 	0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
809 	0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
810 	0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
811 	0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E,	0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
812 	0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
813 	0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
814 };
815