[unix-history] / usr / src / sys / ufs / ffs / ffs_balloc.c

/*
 * Copyright (c) 1982, 1986, 1989 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the University of California, Berkeley.  The name of the
 * University may not be used to endorse or promote products derived
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 *	@(#)ffs_balloc.c	7.4 (Berkeley) %G%
 */

#include "param.h"
#include "systm.h"
#include "user.h"
#include "buf.h"
#include "proc.h"
#include "file.h"
#include "vnode.h"
#include "../ufs/inode.h"
#include "../ufs/fs.h"

/*
 * Bmap defines the structure of file system storage
 * by returning the physical block number on a device given the
 * inode and the logical block number in a file.
 * When convenient, it also leaves the physical
 * block number of the next block of the file in rablock
 * for use in read-ahead.
 */
bmap(ip, bn, bnp, rablockp, rasizep)
	register struct inode *ip;
	register daddr_t bn;
	daddr_t	*bnp;
	daddr_t	*rablockp;
	int *rasizep;
{
	register struct fs *fs;
	register daddr_t nb;
	struct buf *bp;
	daddr_t *bap;
	int i, j, sh;
	int error;

	if (bn < 0)
		return (EFBIG);
	fs = ip->i_fs;

	/*
	 * The first NDADDR blocks are direct blocks
	 */
	if (bn < NDADDR) {
		nb = ip->i_db[bn];
		if (nb == 0) {
			*bnp = (daddr_t)-1;
			return (0);
		}
		if (rablockp && rasizep) {
			if (bn < NDADDR - 1) {
				*rablockp = fsbtodb(fs, ip->i_db[bn + 1]);
				*rasizep = blksize(fs, ip, bn + 1);
			} else {
				*rablockp = 0;
				*rasizep = 0;
			}
		}
		*bnp = fsbtodb(fs, nb);
		return (0);
	}

	/*
	 * Determine how many levels of indirection.
	 */
	sh = 1;
	bn -= NDADDR;
	for (j = NIADDR; j > 0; j--) {
		sh *= NINDIR(fs);
		if (bn < sh)
			break;
		bn -= sh;
	}
	if (j == 0)
		return (EFBIG);

	/*
	 * fetch the first indirect block
	 */
	nb = ip->i_ib[NIADDR - j];
	if (nb == 0) {
		*bnp = (daddr_t)-1;
		return (0);
	}

	/*
	 * fetch through the indirect blocks
	 */
	for (; j <= NIADDR; j++) {
		if (error = bread(ip->i_devvp, fsbtodb(fs, nb),
		    (int)fs->fs_bsize, &bp)) {
			brelse(bp);
			return (error);
		}
		bap = bp->b_un.b_daddr;
		sh /= NINDIR(fs);
		i = (bn / sh) % NINDIR(fs);
		nb = bap[i];
		if (nb == 0) {
			*bnp = (daddr_t)-1;
			brelse(bp);
			return (0);
		}
		if (j < NIADDR)
			brelse(bp);
	}

	/*
	 * calculate read-ahead.
	 */
	if (rablockp && rasizep) {
		if (i < NINDIR(fs) - 1) {
			*rablockp = fsbtodb(fs, bap[i + 1]);
			*rasizep = fs->fs_bsize;
		} else {
			*rablockp = 0;
			*rasizep = 0;
		}
	}
	*bnp = fsbtodb(fs, nb);
	brelse(bp);
	return (0);
}

/*
 * Balloc defines the structure of file system storage
 * by returning the physical block number on a device given the
 * inode and the logical block number in a file.
 * When unallocated entries are found, new physical blocks
 * are allocated.
 */
balloc(ip, bn, size, bnp, flags)
	register struct inode *ip;
	register daddr_t bn;
	int size;
	daddr_t	*bnp;
	int flags;
{
	register struct fs *fs;
	register daddr_t nb;
	struct buf *bp, *nbp;
	int osize, nsize, i, j, sh, error;
	daddr_t lbn, *bap, pref, blkpref();

	if (bn < 0)
		return (EFBIG);
	fs = ip->i_fs;

	/*
	 * If the next write will extend the file into a new block,
	 * and the file is currently composed of a fragment
	 * this fragment has to be extended to be a full block.
	 */
	nb = lblkno(fs, ip->i_size);
	if (nb < NDADDR && nb < bn) {
		osize = blksize(fs, ip, nb);
		if (osize < fs->fs_bsize && osize > 0) {
			error = realloccg(ip, ip->i_db[nb],
				blkpref(ip, nb, (int)nb, &ip->i_db[0]),
				osize, (int)fs->fs_bsize, &bp);
			if (error) {
				*bnp = (daddr_t)-1;
				return (error);
			}
			ip->i_size = (nb + 1) * fs->fs_bsize;
			ip->i_db[nb] = dbtofsb(fs, bp->b_blkno);
			ip->i_flag |= IUPD|ICHG;
			bdwrite(bp);
		}
	}
	/*
	 * The first NDADDR blocks are direct blocks
	 */
	if (bn < NDADDR) {
		nb = ip->i_db[bn];
		if (nb == 0 || ip->i_size < (bn + 1) * fs->fs_bsize) {
			if (nb != 0) {
				/* consider need to reallocate a frag */
				osize = fragroundup(fs, blkoff(fs, ip->i_size));
				nsize = fragroundup(fs, size);
				if (nsize <= osize)
					goto gotit;
				error = realloccg(ip, nb,
					blkpref(ip, bn, (int)bn, &ip->i_db[0]),
					osize, nsize, &bp);
			} else {
				if (ip->i_size < (bn + 1) * fs->fs_bsize)
					nsize = fragroundup(fs, size);
				else
					nsize = fs->fs_bsize;
				error = alloc(ip,
					blkpref(ip, bn, (int)bn, &ip->i_db[0]),
					nsize, &bp, flags);
			}
			if (error) {
				*bnp = (daddr_t)-1;
				return (error);
			}
			nb = dbtofsb(fs, bp->b_blkno);
			if ((ip->i_mode & IFMT) == IFDIR)
				/*
				 * Write directory blocks synchronously
				 * so they never appear with garbage in
				 * them on the disk.
				 * 
				 * NB: Should free space and return error
				 * if bwrite returns an error.
				 */
				error = bwrite(bp);
			else
				bdwrite(bp);
			ip->i_db[bn] = nb;
			ip->i_flag |= IUPD|ICHG;
		}
gotit:
		*bnp = fsbtodb(fs, nb);
		return (0);
	}

	/*
	 * Determine how many levels of indirection.
	 */
	pref = 0;
	sh = 1;
	lbn = bn;
	bn -= NDADDR;
	for (j = NIADDR; j > 0; j--) {
		sh *= NINDIR(fs);
		if (bn < sh)
			break;
		bn -= sh;
	}
	if (j == 0)
		return (EFBIG);

	/*
	 * fetch the first indirect block
	 */
	nb = ip->i_ib[NIADDR - j];
	if (nb == 0) {
		pref = blkpref(ip, lbn, 0, (daddr_t *)0);
	        error = alloc(ip, pref, (int)fs->fs_bsize, &bp, B_CLRBUF);
		if (error) {
			*bnp = (daddr_t)-1;
			return (error);
		}
		nb = dbtofsb(fs, bp->b_blkno);
		/*
		 * Write synchronously so that indirect blocks
		 * never point at garbage.
		 * 
		 * NB: Should free space and return error
		 * if bwrite returns an error.
		 */
		error = bwrite(bp);
		ip->i_ib[NIADDR - j] = nb;
		ip->i_flag |= IUPD|ICHG;
	}

	/*
	 * fetch through the indirect blocks
	 */
	for (; j <= NIADDR; j++) {
#ifdef SECSIZE
		bp = bread(ip->i_dev, fsbtodb(fs, nb), (int)fs->fs_bsize,
		    fs->fs_dbsize);
#else SECSIZE
		if (error = bread(ip->i_devvp, fsbtodb(fs, nb),
		    (int)fs->fs_bsize, &bp)) {
			brelse(bp);
			return (error);
		}
		bap = bp->b_un.b_daddr;
		sh /= NINDIR(fs);
		i = (bn / sh) % NINDIR(fs);
		nb = bap[i];
		if (nb == 0) {
			if (pref == 0)
				if (j < NIADDR)
					pref = blkpref(ip, lbn, 0,
						(daddr_t *)0);
				else
					pref = blkpref(ip, lbn, i, &bap[0]);
		        error = alloc(ip, pref, (int)fs->fs_bsize, &nbp,
				(j < NIADDR) ? B_CLRBUF : flags);
			if (error) {
				brelse(bp);
				*bnp = (daddr_t)-1;
				return (error);
			}
			nb = dbtofsb(fs, nbp->b_blkno);
			if (j < NIADDR || (ip->i_mode & IFMT) == IFDIR)
				/*
				 * Write synchronously so indirect blocks
				 * never point at garbage and blocks
				 * in directories never contain garbage.
				 * 
				 * NB: Should free space and return error
				 * if bwrite returns an error.
				 */
				error = bwrite(nbp);
			else
				bdwrite(nbp);
			bap[i] = nb;
			bdwrite(bp);
		} else
			brelse(bp);
	}

	*bnp = fsbtodb(fs, nb);
	return (0);
}
Commit	Line	Data
da7c5cc6	1	/*
7188ac27 KM	2	* Copyright (c) 1982, 1986, 1989 Regents of the University of California.
7188ac27 KM	3	* All rights reserved.
da7c5cc6	4	*
7188ac27 KM	5	* Redistribution and use in source and binary forms are permitted
	6	* provided that the above copyright notice and this paragraph are
	7	* duplicated in all such forms and that any documentation,
	8	* advertising materials, and other materials related to such
	9	* distribution and use acknowledge that the software was developed
	10	* by the University of California, Berkeley. The name of the
	11	* University may not be used to endorse or promote products derived
	12	* from this software without specific prior written permission.
	13	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
	14	* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
	15	* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
	16	*
56d4e5e8	17	* @(#)ffs_balloc.c 7.4 (Berkeley) %G%
da7c5cc6	18	*/
52212483	19
94368568 JB	20	#include "param.h"
94368568 JB	21	#include "systm.h"
94368568 JB	22	#include "user.h"
	23	#include "buf.h"
	24	#include "proc.h"
7188ac27 KM	25	#include "file.h"
	26	#include "vnode.h"
	27	#include "../ufs/inode.h"
	28	#include "../ufs/fs.h"
52212483 BJ	29
	30	/*
	31	* Bmap defines the structure of file system storage
	32	* by returning the physical block number on a device given the
	33	* inode and the logical block number in a file.
	34	* When convenient, it also leaves the physical
	35	* block number of the next block of the file in rablock
	36	* for use in read-ahead.
	37	*/
7188ac27	38	bmap(ip, bn, bnp, rablockp, rasizep)
52212483	39	register struct inode *ip;
7188ac27 KM	40	register daddr_t bn;
	41	daddr_t *bnp;
	42	daddr_t *rablockp;
	43	int *rasizep;
52212483	44	{
7188ac27 KM	45	register struct fs *fs;
	46	register daddr_t nb;
	47	struct buf *bp;
	48	daddr_t *bap;
	49	int i, j, sh;
	50	int error;
	51
	52	if (bn < 0)
	53	return (EFBIG);
	54	fs = ip->i_fs;
	55
	56	/*
	57	* The first NDADDR blocks are direct blocks
	58	*/
	59	if (bn < NDADDR) {
	60	nb = ip->i_db[bn];
	61	if (nb == 0) {
	62	*bnp = (daddr_t)-1;
	63	return (0);
	64	}
	65	if (rablockp && rasizep) {
	66	if (bn < NDADDR - 1) {
	67	*rablockp = fsbtodb(fs, ip->i_db[bn + 1]);
	68	*rasizep = blksize(fs, ip, bn + 1);
	69	} else {
	70	*rablockp = 0;
	71	*rasizep = 0;
	72	}
	73	}
	74	*bnp = fsbtodb(fs, nb);
	75	return (0);
	76	}
	77
	78	/*
	79	* Determine how many levels of indirection.
	80	*/
	81	sh = 1;
	82	bn -= NDADDR;
	83	for (j = NIADDR; j > 0; j--) {
	84	sh *= NINDIR(fs);
	85	if (bn < sh)
	86	break;
	87	bn -= sh;
	88	}
	89	if (j == 0)
	90	return (EFBIG);
52212483	91
7188ac27 KM	92	/*
	93	* fetch the first indirect block
	94	*/
	95	nb = ip->i_ib[NIADDR - j];
	96	if (nb == 0) {
	97	*bnp = (daddr_t)-1;
	98	return (0);
52212483	99	}
7188ac27 KM	100
	101	/*
	102	* fetch through the indirect blocks
	103	*/
	104	for (; j <= NIADDR; j++) {
	105	if (error = bread(ip->i_devvp, fsbtodb(fs, nb),
	106	(int)fs->fs_bsize, &bp)) {
	107	brelse(bp);
	108	return (error);
	109	}
	110	bap = bp->b_un.b_daddr;
	111	sh /= NINDIR(fs);
	112	i = (bn / sh) % NINDIR(fs);
	113	nb = bap[i];
	114	if (nb == 0) {
	115	*bnp = (daddr_t)-1;
	116	brelse(bp);
	117	return (0);
	118	}
56d4e5e8 KM	119	if (j < NIADDR)
56d4e5e8 KM	120	brelse(bp);
7188ac27 KM	121	}
	122
	123	/*
	124	* calculate read-ahead.
	125	*/
	126	if (rablockp && rasizep) {
	127	if (i < NINDIR(fs) - 1) {
	128	*rablockp = fsbtodb(fs, bap[i + 1]);
	129	*rasizep = fs->fs_bsize;
	130	} else {
	131	*rablockp = 0;
	132	*rasizep = 0;
	133	}
	134	}
	135	*bnp = fsbtodb(fs, nb);
	136	brelse(bp);
	137	return (0);
	138	}
	139
	140	/*
	141	* Balloc defines the structure of file system storage
	142	* by returning the physical block number on a device given the
	143	* inode and the logical block number in a file.
	144	* When unallocated entries are found, new physical blocks
	145	* are allocated.
	146	*/
	147	balloc(ip, bn, size, bnp, flags)
	148	register struct inode *ip;
	149	register daddr_t bn;
	150	int size;
	151	daddr_t *bnp;
	152	int flags;
	153	{
	154	register struct fs *fs;
	155	register daddr_t nb;
	156	struct buf bp, nbp;
	157	int osize, nsize, i, j, sh, error;
	158	daddr_t lbn, *bap, pref, blkpref();
	159
	160	if (bn < 0)
	161	return (EFBIG);
52212483	162	fs = ip->i_fs;
52212483 BJ	163
	164	/*
	165	* If the next write will extend the file into a new block,
	166	* and the file is currently composed of a fragment
	167	* this fragment has to be extended to be a full block.
	168	*/
	169	nb = lblkno(fs, ip->i_size);
7188ac27	170	if (nb < NDADDR && nb < bn) {
52212483 BJ	171	osize = blksize(fs, ip, nb);
52212483 BJ	172	if (osize < fs->fs_bsize && osize > 0) {
7188ac27	173	error = realloccg(ip, ip->i_db[nb],
4f083fd7	174	blkpref(ip, nb, (int)nb, &ip->i_db[0]),
7188ac27 KM	175	osize, (int)fs->fs_bsize, &bp);
	176	if (error) {
	177	*bnp = (daddr_t)-1;
	178	return (error);
	179	}
52212483 BJ	180	ip->i_size = (nb + 1) * fs->fs_bsize;
	181	ip->i_db[nb] = dbtofsb(fs, bp->b_blkno);
	182	ip->i_flag \|= IUPD\|ICHG;
	183	bdwrite(bp);
	184	}
	185	}
	186	/*
	187	* The first NDADDR blocks are direct blocks
	188	*/
	189	if (bn < NDADDR) {
a6e7e3c6	190	nb = ip->i_db[bn];
a6e7e3c6	191	if (nb == 0 \|\| ip->i_size < (bn + 1) * fs->fs_bsize) {
52212483 BJ	192	if (nb != 0) {
	193	/* consider need to reallocate a frag */
	194	osize = fragroundup(fs, blkoff(fs, ip->i_size));
	195	nsize = fragroundup(fs, size);
	196	if (nsize <= osize)
	197	goto gotit;
7188ac27	198	error = realloccg(ip, nb,
4f083fd7	199	blkpref(ip, bn, (int)bn, &ip->i_db[0]),
7188ac27	200	osize, nsize, &bp);
52212483	201	} else {
a6e7e3c6	202	if (ip->i_size < (bn + 1) * fs->fs_bsize)
52212483 BJ	203	nsize = fragroundup(fs, size);
	204	else
	205	nsize = fs->fs_bsize;
7188ac27	206	error = alloc(ip,
4f083fd7	207	blkpref(ip, bn, (int)bn, &ip->i_db[0]),
7188ac27 KM	208	nsize, &bp, flags);
	209	}
	210	if (error) {
	211	*bnp = (daddr_t)-1;
	212	return (error);
52212483	213	}
52212483	214	nb = dbtofsb(fs, bp->b_blkno);
7188ac27	215	if ((ip->i_mode & IFMT) == IFDIR)
52212483 BJ	216	/*
	217	* Write directory blocks synchronously
	218	* so they never appear with garbage in
	219	* them on the disk.
7188ac27 KM	220	*
	221	* NB: Should free space and return error
	222	* if bwrite returns an error.
52212483	223	*/
7188ac27	224	error = bwrite(bp);
52212483 BJ	225	else
52212483 BJ	226	bdwrite(bp);
a6e7e3c6	227	ip->i_db[bn] = nb;
52212483 BJ	228	ip->i_flag \|= IUPD\|ICHG;
	229	}
	230	gotit:
7188ac27 KM	231	*bnp = fsbtodb(fs, nb);
7188ac27 KM	232	return (0);
52212483 BJ	233	}
	234
	235	/*
	236	* Determine how many levels of indirection.
	237	*/
a6e7e3c6	238	pref = 0;
52212483	239	sh = 1;
a6e7e3c6	240	lbn = bn;
52212483	241	bn -= NDADDR;
7188ac27	242	for (j = NIADDR; j > 0; j--) {
52212483 BJ	243	sh *= NINDIR(fs);
	244	if (bn < sh)
	245	break;
	246	bn -= sh;
	247	}
7188ac27 KM	248	if (j == 0)
7188ac27 KM	249	return (EFBIG);
52212483 BJ	250
	251	/*
	252	* fetch the first indirect block
	253	*/
	254	nb = ip->i_ib[NIADDR - j];
	255	if (nb == 0) {
4f083fd7	256	pref = blkpref(ip, lbn, 0, (daddr_t *)0);
7188ac27 KM	257	error = alloc(ip, pref, (int)fs->fs_bsize, &bp, B_CLRBUF);
	258	if (error) {
	259	*bnp = (daddr_t)-1;
	260	return (error);
	261	}
52212483 BJ	262	nb = dbtofsb(fs, bp->b_blkno);
	263	/*
	264	* Write synchronously so that indirect blocks
	265	* never point at garbage.
7188ac27 KM	266	*
	267	* NB: Should free space and return error
	268	* if bwrite returns an error.
52212483	269	*/
7188ac27	270	error = bwrite(bp);
52212483 BJ	271	ip->i_ib[NIADDR - j] = nb;
	272	ip->i_flag \|= IUPD\|ICHG;
	273	}
	274
	275	/*
	276	* fetch through the indirect blocks
	277	*/
	278	for (; j <= NIADDR; j++) {
ec67a3ce MK	279	#ifdef SECSIZE
	280	bp = bread(ip->i_dev, fsbtodb(fs, nb), (int)fs->fs_bsize,
	281	fs->fs_dbsize);
	282	#else SECSIZE
7188ac27 KM	283	if (error = bread(ip->i_devvp, fsbtodb(fs, nb),
7188ac27 KM	284	(int)fs->fs_bsize, &bp)) {
52212483	285	brelse(bp);
7188ac27	286	return (error);
52212483 BJ	287	}
	288	bap = bp->b_un.b_daddr;
	289	sh /= NINDIR(fs);
	290	i = (bn / sh) % NINDIR(fs);
	291	nb = bap[i];
	292	if (nb == 0) {
a6e7e3c6 KM	293	if (pref == 0)
a6e7e3c6 KM	294	if (j < NIADDR)
4f083fd7 SL	295	pref = blkpref(ip, lbn, 0,
4f083fd7 SL	296	(daddr_t *)0);
a6e7e3c6 KM	297	else
a6e7e3c6 KM	298	pref = blkpref(ip, lbn, i, &bap[0]);
7188ac27 KM	299	error = alloc(ip, pref, (int)fs->fs_bsize, &nbp,
	300	(j < NIADDR) ? B_CLRBUF : flags);
	301	if (error) {
52212483	302	brelse(bp);
7188ac27 KM	303	*bnp = (daddr_t)-1;
7188ac27 KM	304	return (error);
52212483 BJ	305	}
52212483 BJ	306	nb = dbtofsb(fs, nbp->b_blkno);
7188ac27	307	if (j < NIADDR \|\| (ip->i_mode & IFMT) == IFDIR)
52212483 BJ	308	/*
	309	* Write synchronously so indirect blocks
	310	* never point at garbage and blocks
	311	* in directories never contain garbage.
7188ac27 KM	312	*
	313	* NB: Should free space and return error
	314	* if bwrite returns an error.
52212483	315	*/
7188ac27	316	error = bwrite(nbp);
52212483 BJ	317	else
	318	bdwrite(nbp);
	319	bap[i] = nb;
	320	bdwrite(bp);
	321	} else
	322	brelse(bp);
	323	}
	324
7188ac27 KM	325	*bnp = fsbtodb(fs, nb);
7188ac27 KM	326	return (0);
52212483	327	}