balloc.c

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