xref: /original-bsd/sys/ufs/ffs/fs.h (revision 7bd6ee9e)
1 /*
2  * Copyright (c) 1982, 1986, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * %sccs.include.redist.c%
6  *
7  *	@(#)fs.h	8.5 (Berkeley) 02/27/94
8  */
9 
10 /*
11  * Each disk drive contains some number of file systems.
12  * A file system consists of a number of cylinder groups.
13  * Each cylinder group has inodes and data.
14  *
15  * A file system is described by its super-block, which in turn
16  * describes the cylinder groups.  The super-block is critical
17  * data and is replicated in each cylinder group to protect against
18  * catastrophic loss.  This is done at `newfs' time and the critical
19  * super-block data does not change, so the copies need not be
20  * referenced further unless disaster strikes.
21  *
22  * For file system fs, the offsets of the various blocks of interest
23  * are given in the super block as:
24  *	[fs->fs_sblkno]		Super-block
25  *	[fs->fs_cblkno]		Cylinder group block
26  *	[fs->fs_iblkno]		Inode blocks
27  *	[fs->fs_dblkno]		Data blocks
28  * The beginning of cylinder group cg in fs, is given by
29  * the ``cgbase(fs, cg)'' macro.
30  *
31  * The first boot and super blocks are given in absolute disk addresses.
32  * The byte-offset forms are preferred, as they don't imply a sector size.
33  */
34 #define BBSIZE		8192
35 #define SBSIZE		8192
36 #define	BBOFF		((off_t)(0))
37 #define	SBOFF		((off_t)(BBOFF + BBSIZE))
38 #define	BBLOCK		((daddr_t)(0))
39 #define	SBLOCK		((daddr_t)(BBLOCK + BBSIZE / DEV_BSIZE))
40 
41 /*
42  * Addresses stored in inodes are capable of addressing fragments
43  * of `blocks'. File system blocks of at most size MAXBSIZE can
44  * be optionally broken into 2, 4, or 8 pieces, each of which is
45  * addressible; these pieces may be DEV_BSIZE, or some multiple of
46  * a DEV_BSIZE unit.
47  *
48  * Large files consist of exclusively large data blocks.  To avoid
49  * undue wasted disk space, the last data block of a small file may be
50  * allocated as only as many fragments of a large block as are
51  * necessary.  The file system format retains only a single pointer
52  * to such a fragment, which is a piece of a single large block that
53  * has been divided.  The size of such a fragment is determinable from
54  * information in the inode, using the ``blksize(fs, ip, lbn)'' macro.
55  *
56  * The file system records space availability at the fragment level;
57  * to determine block availability, aligned fragments are examined.
58  */
59 
60 /*
61  * MINBSIZE is the smallest allowable block size.
62  * In order to insure that it is possible to create files of size
63  * 2^32 with only two levels of indirection, MINBSIZE is set to 4096.
64  * MINBSIZE must be big enough to hold a cylinder group block,
65  * thus changes to (struct cg) must keep its size within MINBSIZE.
66  * Note that super blocks are always of size SBSIZE,
67  * and that both SBSIZE and MAXBSIZE must be >= MINBSIZE.
68  */
69 #define MINBSIZE	4096
70 
71 /*
72  * The path name on which the file system is mounted is maintained
73  * in fs_fsmnt. MAXMNTLEN defines the amount of space allocated in
74  * the super block for this name.
75  * The limit on the amount of summary information per file system
76  * is defined by MAXCSBUFS. It is currently parameterized for a
77  * maximum of two million cylinders.
78  */
79 #define MAXMNTLEN 512
80 #define MAXCSBUFS 32
81 
82 /*
83  * A summary of contiguous blocks of various sizes is maintained
84  * in each cylinder group. Normally this is set by the initial
85  * value of fs_maxcontig. To conserve space, a maximum summary size
86  * is set by FS_MAXCONTIG.
87  */
88 #define FS_MAXCONTIG	16
89 
90 /*
91  * Per cylinder group information; summarized in blocks allocated
92  * from first cylinder group data blocks.  These blocks have to be
93  * read in from fs_csaddr (size fs_cssize) in addition to the
94  * super block.
95  *
96  * N.B. sizeof(struct csum) must be a power of two in order for
97  * the ``fs_cs'' macro to work (see below).
98  */
99 struct csum {
100 	long	cs_ndir;	/* number of directories */
101 	long	cs_nbfree;	/* number of free blocks */
102 	long	cs_nifree;	/* number of free inodes */
103 	long	cs_nffree;	/* number of free frags */
104 };
105 
106 /*
107  * Super block for a file system.
108  */
109 struct fs {
110 	struct	fs *fs_link;		/* linked list of file systems */
111 	struct	fs *fs_rlink;		/*     used for incore super blocks */
112 	daddr_t	fs_sblkno;		/* addr of super-block in filesys */
113 	daddr_t	fs_cblkno;		/* offset of cyl-block in filesys */
114 	daddr_t	fs_iblkno;		/* offset of inode-blocks in filesys */
115 	daddr_t	fs_dblkno;		/* offset of first data after cg */
116 	long	fs_cgoffset;		/* cylinder group offset in cylinder */
117 	long	fs_cgmask;		/* used to calc mod fs_ntrak */
118 	time_t 	fs_time;    		/* last time written */
119 	long	fs_size;		/* number of blocks in fs */
120 	long	fs_dsize;		/* number of data blocks in fs */
121 	long	fs_ncg;			/* number of cylinder groups */
122 	long	fs_bsize;		/* size of basic blocks in fs */
123 	long	fs_fsize;		/* size of frag blocks in fs */
124 	long	fs_frag;		/* number of frags in a block in fs */
125 /* these are configuration parameters */
126 	long	fs_minfree;		/* minimum percentage of free blocks */
127 	long	fs_rotdelay;		/* num of ms for optimal next block */
128 	long	fs_rps;			/* disk revolutions per second */
129 /* these fields can be computed from the others */
130 	long	fs_bmask;		/* ``blkoff'' calc of blk offsets */
131 	long	fs_fmask;		/* ``fragoff'' calc of frag offsets */
132 	long	fs_bshift;		/* ``lblkno'' calc of logical blkno */
133 	long	fs_fshift;		/* ``numfrags'' calc number of frags */
134 /* these are configuration parameters */
135 	long	fs_maxcontig;		/* max number of contiguous blks */
136 	long	fs_maxbpg;		/* max number of blks per cyl group */
137 /* these fields can be computed from the others */
138 	long	fs_fragshift;		/* block to frag shift */
139 	long	fs_fsbtodb;		/* fsbtodb and dbtofsb shift constant */
140 	long	fs_sbsize;		/* actual size of super block */
141 	long	fs_csmask;		/* csum block offset */
142 	long	fs_csshift;		/* csum block number */
143 	long	fs_nindir;		/* value of NINDIR */
144 	long	fs_inopb;		/* value of INOPB */
145 	long	fs_nspf;		/* value of NSPF */
146 /* yet another configuration parameter */
147 	long	fs_optim;		/* optimization preference, see below */
148 /* these fields are derived from the hardware */
149 	long	fs_npsect;		/* # sectors/track including spares */
150 	long	fs_interleave;		/* hardware sector interleave */
151 	long	fs_trackskew;		/* sector 0 skew, per track */
152 	long	fs_headswitch;		/* head switch time, usec */
153 	long	fs_trkseek;		/* track-to-track seek, usec */
154 /* sizes determined by number of cylinder groups and their sizes */
155 	daddr_t fs_csaddr;		/* blk addr of cyl grp summary area */
156 	long	fs_cssize;		/* size of cyl grp summary area */
157 	long	fs_cgsize;		/* cylinder group size */
158 /* these fields are derived from the hardware */
159 	long	fs_ntrak;		/* tracks per cylinder */
160 	long	fs_nsect;		/* sectors per track */
161 	long  	fs_spc;   		/* sectors per cylinder */
162 /* this comes from the disk driver partitioning */
163 	long	fs_ncyl;   		/* cylinders in file system */
164 /* these fields can be computed from the others */
165 	long	fs_cpg;			/* cylinders per group */
166 	long	fs_ipg;			/* inodes per group */
167 	long	fs_fpg;			/* blocks per group * fs_frag */
168 /* this data must be re-computed after crashes */
169 	struct	csum fs_cstotal;	/* cylinder summary information */
170 /* these fields are cleared at mount time */
171 	char   	fs_fmod;    		/* super block modified flag */
172 	char   	fs_clean;    		/* file system is clean flag */
173 	char   	fs_ronly;   		/* mounted read-only flag */
174 	char   	fs_flags;   		/* currently unused flag */
175 	char	fs_fsmnt[MAXMNTLEN];	/* name mounted on */
176 /* these fields retain the current block allocation info */
177 	long	fs_cgrotor;		/* last cg searched */
178 	struct	csum *fs_csp[MAXCSBUFS];/* list of fs_cs info buffers */
179 	long	fs_cpc;			/* cyl per cycle in postbl */
180 	short	fs_opostbl[16][8];	/* old rotation block list head */
181 	long	fs_sparecon[50];	/* reserved for future constants */
182 	long	fs_contigsumsize;	/* size of cluster summary array */
183 	long	fs_maxsymlinklen;	/* max length of an internal symlink */
184 	long	fs_inodefmt;		/* format of on-disk inodes */
185 	u_quad_t fs_maxfilesize;	/* maximum representable file size */
186 	quad_t	fs_qbmask;		/* ~fs_bmask - for use with quad size */
187 	quad_t	fs_qfmask;		/* ~fs_fmask - for use with quad size */
188 	long	fs_state;		/* validate fs_clean field */
189 	long	fs_postblformat;	/* format of positional layout tables */
190 	long	fs_nrpos;		/* number of rotaional positions */
191 	long	fs_postbloff;		/* (short) rotation block list head */
192 	long	fs_rotbloff;		/* (u_char) blocks for each rotation */
193 	long	fs_magic;		/* magic number */
194 	u_char	fs_space[1];		/* list of blocks for each rotation */
195 /* actually longer */
196 };
197 /*
198  * Filesystem idetification
199  */
200 #define	FS_MAGIC	0x011954	/* the fast filesystem magic number */
201 #define	FS_OKAY		0x7c269d38	/* superblock checksum */
202 #define FS_42INODEFMT	-1		/* 4.2BSD inode format */
203 #define FS_44INODEFMT	2		/* 4.4BSD inode format */
204 /*
205  * Preference for optimization.
206  */
207 #define FS_OPTTIME	0	/* minimize allocation time */
208 #define FS_OPTSPACE	1	/* minimize disk fragmentation */
209 
210 /*
211  * Rotational layout table format types
212  */
213 #define FS_42POSTBLFMT		-1	/* 4.2BSD rotational table format */
214 #define FS_DYNAMICPOSTBLFMT	1	/* dynamic rotational table format */
215 /*
216  * Macros for access to superblock array structures
217  */
218 #define fs_postbl(fs, cylno) \
219     (((fs)->fs_postblformat == FS_42POSTBLFMT) \
220     ? ((fs)->fs_opostbl[cylno]) \
221     : ((short *)((char *)(fs) + (fs)->fs_postbloff) + (cylno) * (fs)->fs_nrpos))
222 #define fs_rotbl(fs) \
223     (((fs)->fs_postblformat == FS_42POSTBLFMT) \
224     ? ((fs)->fs_space) \
225     : ((u_char *)((char *)(fs) + (fs)->fs_rotbloff)))
226 
227 /*
228  * The size of a cylinder group is calculated by CGSIZE. The maximum size
229  * is limited by the fact that cylinder groups are at most one block.
230  * Its size is derived from the size of the maps maintained in the
231  * cylinder group and the (struct cg) size.
232  */
233 #define CGSIZE(fs) \
234     /* base cg */	(sizeof(struct cg) + sizeof(long) + \
235     /* blktot size */	(fs)->fs_cpg * sizeof(long) + \
236     /* blks size */	(fs)->fs_cpg * (fs)->fs_nrpos * sizeof(short) + \
237     /* inode map */	howmany((fs)->fs_ipg, NBBY) + \
238     /* block map */	howmany((fs)->fs_cpg * (fs)->fs_spc / NSPF(fs), NBBY) +\
239     /* if present */	((fs)->fs_contigsumsize <= 0 ? 0 : \
240     /* cluster sum */	(fs)->fs_contigsumsize * sizeof(long) + \
241     /* cluster map */	howmany((fs)->fs_cpg * (fs)->fs_spc / NSPB(fs), NBBY)))
242 
243 /*
244  * Convert cylinder group to base address of its global summary info.
245  *
246  * N.B. This macro assumes that sizeof(struct csum) is a power of two.
247  */
248 #define fs_cs(fs, indx) \
249 	fs_csp[(indx) >> (fs)->fs_csshift][(indx) & ~(fs)->fs_csmask]
250 
251 /*
252  * Cylinder group block for a file system.
253  */
254 #define	CG_MAGIC	0x090255
255 struct	cg {
256 	struct	cg *cg_link;		/* linked list of cyl groups */
257 	long	cg_magic;		/* magic number */
258 	time_t	cg_time;		/* time last written */
259 	long	cg_cgx;			/* we are the cgx'th cylinder group */
260 	short	cg_ncyl;		/* number of cyl's this cg */
261 	short	cg_niblk;		/* number of inode blocks this cg */
262 	long	cg_ndblk;		/* number of data blocks this cg */
263 	struct	csum cg_cs;		/* cylinder summary information */
264 	long	cg_rotor;		/* position of last used block */
265 	long	cg_frotor;		/* position of last used frag */
266 	long	cg_irotor;		/* position of last used inode */
267 	long	cg_frsum[MAXFRAG];	/* counts of available frags */
268 	long	cg_btotoff;		/* (long) block totals per cylinder */
269 	long	cg_boff;		/* (short) free block positions */
270 	long	cg_iusedoff;		/* (char) used inode map */
271 	long	cg_freeoff;		/* (u_char) free block map */
272 	long	cg_nextfreeoff;		/* (u_char) next available space */
273 	long	cg_clustersumoff;	/* (long) counts of avail clusters */
274 	long	cg_clusteroff;		/* (char) free cluster map */
275 	long	cg_nclusterblks;	/* number of clusters this cg */
276 	long	cg_sparecon[13];	/* reserved for future use */
277 	u_char	cg_space[1];		/* space for cylinder group maps */
278 /* actually longer */
279 };
280 /*
281  * Macros for access to cylinder group array structures
282  */
283 #define cg_blktot(cgp) \
284     (((cgp)->cg_magic != CG_MAGIC) \
285     ? (((struct ocg *)(cgp))->cg_btot) \
286     : ((long *)((char *)(cgp) + (cgp)->cg_btotoff)))
287 #define cg_blks(fs, cgp, cylno) \
288     (((cgp)->cg_magic != CG_MAGIC) \
289     ? (((struct ocg *)(cgp))->cg_b[cylno]) \
290     : ((short *)((char *)(cgp) + (cgp)->cg_boff) + (cylno) * (fs)->fs_nrpos))
291 #define cg_inosused(cgp) \
292     (((cgp)->cg_magic != CG_MAGIC) \
293     ? (((struct ocg *)(cgp))->cg_iused) \
294     : ((char *)((char *)(cgp) + (cgp)->cg_iusedoff)))
295 #define cg_blksfree(cgp) \
296     (((cgp)->cg_magic != CG_MAGIC) \
297     ? (((struct ocg *)(cgp))->cg_free) \
298     : ((u_char *)((char *)(cgp) + (cgp)->cg_freeoff)))
299 #define cg_chkmagic(cgp) \
300     ((cgp)->cg_magic == CG_MAGIC || ((struct ocg *)(cgp))->cg_magic == CG_MAGIC)
301 #define cg_clustersfree(cgp) \
302     ((u_char *)((char *)(cgp) + (cgp)->cg_clusteroff))
303 #define cg_clustersum(cgp) \
304     ((long *)((char *)(cgp) + (cgp)->cg_clustersumoff))
305 
306 /*
307  * The following structure is defined
308  * for compatibility with old file systems.
309  */
310 struct	ocg {
311 	struct	ocg *cg_link;		/* linked list of cyl groups */
312 	struct	ocg *cg_rlink;		/*     used for incore cyl groups */
313 	time_t	cg_time;		/* time last written */
314 	long	cg_cgx;			/* we are the cgx'th cylinder group */
315 	short	cg_ncyl;		/* number of cyl's this cg */
316 	short	cg_niblk;		/* number of inode blocks this cg */
317 	long	cg_ndblk;		/* number of data blocks this cg */
318 	struct	csum cg_cs;		/* cylinder summary information */
319 	long	cg_rotor;		/* position of last used block */
320 	long	cg_frotor;		/* position of last used frag */
321 	long	cg_irotor;		/* position of last used inode */
322 	long	cg_frsum[8];		/* counts of available frags */
323 	long	cg_btot[32];		/* block totals per cylinder */
324 	short	cg_b[32][8];		/* positions of free blocks */
325 	char	cg_iused[256];		/* used inode map */
326 	long	cg_magic;		/* magic number */
327 	u_char	cg_free[1];		/* free block map */
328 /* actually longer */
329 };
330 
331 /*
332  * Turn file system block numbers into disk block addresses.
333  * This maps file system blocks to device size blocks.
334  */
335 #define fsbtodb(fs, b)	((b) << (fs)->fs_fsbtodb)
336 #define	dbtofsb(fs, b)	((b) >> (fs)->fs_fsbtodb)
337 
338 /*
339  * Cylinder group macros to locate things in cylinder groups.
340  * They calc file system addresses of cylinder group data structures.
341  */
342 #define	cgbase(fs, c)	((daddr_t)((fs)->fs_fpg * (c)))
343 #define	cgdmin(fs, c)	(cgstart(fs, c) + (fs)->fs_dblkno)	/* 1st data */
344 #define	cgimin(fs, c)	(cgstart(fs, c) + (fs)->fs_iblkno)	/* inode blk */
345 #define	cgsblock(fs, c)	(cgstart(fs, c) + (fs)->fs_sblkno)	/* super blk */
346 #define	cgtod(fs, c)	(cgstart(fs, c) + (fs)->fs_cblkno)	/* cg block */
347 #define cgstart(fs, c)							\
348 	(cgbase(fs, c) + (fs)->fs_cgoffset * ((c) & ~((fs)->fs_cgmask)))
349 
350 /*
351  * Macros for handling inode numbers:
352  *     inode number to file system block offset.
353  *     inode number to cylinder group number.
354  *     inode number to file system block address.
355  */
356 #define	ino_to_cg(fs, x)	((x) / (fs)->fs_ipg)
357 #define	ino_to_fsba(fs, x)						\
358 	((daddr_t)(cgimin(fs, ino_to_cg(fs, x)) +			\
359 	    (blkstofrags((fs), (((x) % (fs)->fs_ipg) / INOPB(fs))))))
360 #define	ino_to_fsbo(fs, x)	((x) % INOPB(fs))
361 
362 /*
363  * Give cylinder group number for a file system block.
364  * Give cylinder group block number for a file system block.
365  */
366 #define	dtog(fs, d)	((d) / (fs)->fs_fpg)
367 #define	dtogd(fs, d)	((d) % (fs)->fs_fpg)
368 
369 /*
370  * Extract the bits for a block from a map.
371  * Compute the cylinder and rotational position of a cyl block addr.
372  */
373 #define blkmap(fs, map, loc) \
374     (((map)[(loc) / NBBY] >> ((loc) % NBBY)) & (0xff >> (NBBY - (fs)->fs_frag)))
375 #define cbtocylno(fs, bno) \
376     ((bno) * NSPF(fs) / (fs)->fs_spc)
377 #define cbtorpos(fs, bno) \
378     (((bno) * NSPF(fs) % (fs)->fs_spc / (fs)->fs_nsect * (fs)->fs_trackskew + \
379      (bno) * NSPF(fs) % (fs)->fs_spc % (fs)->fs_nsect * (fs)->fs_interleave) % \
380      (fs)->fs_nsect * (fs)->fs_nrpos / (fs)->fs_npsect)
381 
382 /*
383  * The following macros optimize certain frequently calculated
384  * quantities by using shifts and masks in place of divisions
385  * modulos and multiplications.
386  */
387 #define blkoff(fs, loc)		/* calculates (loc % fs->fs_bsize) */ \
388 	((loc) & (fs)->fs_qbmask)
389 #define fragoff(fs, loc)	/* calculates (loc % fs->fs_fsize) */ \
390 	((loc) & (fs)->fs_qfmask)
391 #define lblktosize(fs, blk)	/* calculates (blk * fs->fs_bsize) */ \
392 	((blk) << (fs)->fs_bshift)
393 #define lblkno(fs, loc)		/* calculates (loc / fs->fs_bsize) */ \
394 	((loc) >> (fs)->fs_bshift)
395 #define numfrags(fs, loc)	/* calculates (loc / fs->fs_fsize) */ \
396 	((loc) >> (fs)->fs_fshift)
397 #define blkroundup(fs, size)	/* calculates roundup(size, fs->fs_bsize) */ \
398 	(((size) + (fs)->fs_qbmask) & (fs)->fs_bmask)
399 #define fragroundup(fs, size)	/* calculates roundup(size, fs->fs_fsize) */ \
400 	(((size) + (fs)->fs_qfmask) & (fs)->fs_fmask)
401 #define fragstoblks(fs, frags)	/* calculates (frags / fs->fs_frag) */ \
402 	((frags) >> (fs)->fs_fragshift)
403 #define blkstofrags(fs, blks)	/* calculates (blks * fs->fs_frag) */ \
404 	((blks) << (fs)->fs_fragshift)
405 #define fragnum(fs, fsb)	/* calculates (fsb % fs->fs_frag) */ \
406 	((fsb) & ((fs)->fs_frag - 1))
407 #define blknum(fs, fsb)		/* calculates rounddown(fsb, fs->fs_frag) */ \
408 	((fsb) &~ ((fs)->fs_frag - 1))
409 
410 /*
411  * Determine the number of available frags given a
412  * percentage to hold in reserve
413  */
414 #define freespace(fs, percentreserved) \
415 	(blkstofrags((fs), (fs)->fs_cstotal.cs_nbfree) + \
416 	(fs)->fs_cstotal.cs_nffree - ((fs)->fs_dsize * (percentreserved) / 100))
417 
418 /*
419  * Determining the size of a file block in the file system.
420  */
421 #define blksize(fs, ip, lbn) \
422 	(((lbn) >= NDADDR || (ip)->i_size >= ((lbn) + 1) << (fs)->fs_bshift) \
423 	    ? (fs)->fs_bsize \
424 	    : (fragroundup(fs, blkoff(fs, (ip)->i_size))))
425 #define dblksize(fs, dip, lbn) \
426 	(((lbn) >= NDADDR || (dip)->di_size >= ((lbn) + 1) << (fs)->fs_bshift) \
427 	    ? (fs)->fs_bsize \
428 	    : (fragroundup(fs, blkoff(fs, (dip)->di_size))))
429 
430 /*
431  * Number of disk sectors per block; assumes DEV_BSIZE byte sector size.
432  */
433 #define	NSPB(fs)	((fs)->fs_nspf << (fs)->fs_fragshift)
434 #define	NSPF(fs)	((fs)->fs_nspf)
435 
436 /*
437  * INOPB is the number of inodes in a secondary storage block.
438  */
439 #define	INOPB(fs)	((fs)->fs_inopb)
440 #define	INOPF(fs)	((fs)->fs_inopb >> (fs)->fs_fragshift)
441 
442 /*
443  * NINDIR is the number of indirects in a file system block.
444  */
445 #define	NINDIR(fs)	((fs)->fs_nindir)
446 
447 extern int inside[], around[];
448 extern u_char *fragtbl[];
449