[BACK]Return to efs_dir.h CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / sys / fs / efs

File: [cvs.NetBSD.org] / src / sys / fs / efs / efs_dir.h (download)

Revision 1.1, Fri Jun 29 23:30:27 2007 UTC (13 years, 9 months ago) by rumble
Branch: MAIN
CVS Tags: yamt-x86pmap-base4, yamt-x86pmap-base3, yamt-x86pmap-base2, yamt-x86pmap-base, yamt-x86pmap, yamt-pf42-baseX, yamt-pf42-base4, yamt-pf42-base3, yamt-pf42-base2, yamt-pf42-base, yamt-pf42, yamt-pagecache-tag8, yamt-pagecache-base9, yamt-pagecache-base8, yamt-pagecache-base7, yamt-pagecache-base6, yamt-pagecache-base5, yamt-pagecache-base4, yamt-pagecache-base3, yamt-pagecache-base2, yamt-pagecache-base, yamt-pagecache, yamt-nfs-mp-base9, yamt-nfs-mp-base8, yamt-nfs-mp-base7, yamt-nfs-mp-base6, yamt-nfs-mp-base5, yamt-nfs-mp-base4, yamt-nfs-mp-base3, yamt-nfs-mp-base2, yamt-nfs-mp-base11, yamt-nfs-mp-base10, yamt-nfs-mp-base, yamt-nfs-mp, yamt-lazymbuf-base15, yamt-lazymbuf-base14, yamt-kmem-base3, yamt-kmem-base2, yamt-kmem-base, yamt-kmem, wrstuden-revivesa-base-4, wrstuden-revivesa-base-3, wrstuden-revivesa-base-2, wrstuden-revivesa-base-1, wrstuden-revivesa-base, wrstuden-revivesa, vmlocking2-base3, vmlocking2-base2, vmlocking2-base1, vmlocking2, vmlocking-nbase, vmlocking-base, uebayasi-xip-base4, uebayasi-xip-base3, uebayasi-xip-base2, uebayasi-xip-base1, uebayasi-xip-base, uebayasi-xip, tls-maxphys-base, tls-earlyentropy-base, tls-earlyentropy, simonb-wapbl-nbase, simonb-wapbl-base, simonb-wapbl, rmind-uvmplock-nbase, rmind-uvmplock-base, rmind-uvmplock, rmind-smpnet-nbase, rmind-smpnet-base, rmind-smpnet, riastradh-xf86-video-intel-2-7-1-pre-2-21-15, riastradh-drm2-base3, riastradh-drm2-base2, riastradh-drm2-base1, riastradh-drm2-base, riastradh-drm2, reinoud-bufcleanup-nbase, reinoud-bufcleanup-base, nick-nhusb-base-20160529, nick-nhusb-base-20160422, nick-nhusb-base-20160319, nick-nhusb-base-20151226, nick-nhusb-base-20150921, nick-nhusb-base-20150606, nick-nhusb-base-20150406, nick-nhusb-base, nick-net80211-sync-base, nick-net80211-sync, nick-hppapmap-base4, nick-hppapmap-base3, nick-hppapmap-base2, nick-hppapmap-base, nick-hppapmap, nick-csl-alignment-base5, nick-csl-alignment-base, nick-csl-alignment, netbsd-7-nhusb-base-20170116, netbsd-7-nhusb-base, netbsd-7-nhusb, netbsd-7-base, netbsd-7-2-RELEASE, netbsd-7-1-RELEASE, netbsd-7-1-RC2, netbsd-7-1-RC1, netbsd-7-1-2-RELEASE, netbsd-7-1-1-RELEASE, netbsd-7-1, netbsd-7-0-RELEASE, netbsd-7-0-RC3, netbsd-7-0-RC2, netbsd-7-0-RC1, netbsd-7-0-2-RELEASE, netbsd-7-0-1-RELEASE, netbsd-7-0, netbsd-7, netbsd-6-base, netbsd-6-1-RELEASE, netbsd-6-1-RC4, netbsd-6-1-RC3, netbsd-6-1-RC2, netbsd-6-1-RC1, netbsd-6-1-5-RELEASE, netbsd-6-1-4-RELEASE, netbsd-6-1-3-RELEASE, netbsd-6-1-2-RELEASE, netbsd-6-1-1-RELEASE, netbsd-6-1, netbsd-6-0-RELEASE, netbsd-6-0-RC2, netbsd-6-0-RC1, netbsd-6-0-6-RELEASE, netbsd-6-0-5-RELEASE, netbsd-6-0-4-RELEASE, netbsd-6-0-3-RELEASE, netbsd-6-0-2-RELEASE, netbsd-6-0-1-RELEASE, netbsd-6-0, netbsd-6, netbsd-5-base, netbsd-5-2-RELEASE, netbsd-5-2-RC1, netbsd-5-2-3-RELEASE, netbsd-5-2-2-RELEASE, netbsd-5-2-1-RELEASE, netbsd-5-2, netbsd-5-1-RELEASE, netbsd-5-1-RC4, netbsd-5-1-RC3, netbsd-5-1-RC2, netbsd-5-1-RC1, netbsd-5-1-5-RELEASE, netbsd-5-1-4-RELEASE, netbsd-5-1-3-RELEASE, netbsd-5-1-2-RELEASE, netbsd-5-1-1-RELEASE, netbsd-5-1, netbsd-5-0-RELEASE, netbsd-5-0-RC4, netbsd-5-0-RC3, netbsd-5-0-RC2, netbsd-5-0-RC1, netbsd-5-0-2-RELEASE, netbsd-5-0-1-RELEASE, netbsd-5-0, netbsd-5, mjf-ufs-trans-base, mjf-devfs2-base, mjf-devfs2, mjf-devfs-base, mjf-devfs, matt-premerge-20091211, matt-nb6-plus-nbase, matt-nb6-plus-base, matt-nb6-plus, matt-nb5-pq3-base, matt-nb5-pq3, matt-nb5-mips64-u2-k2-k4-k7-k8-k9, matt-nb5-mips64-u1-k1-k5, matt-nb5-mips64-premerge-20101231, matt-nb5-mips64-premerge-20091211, matt-nb5-mips64-k15, matt-nb5-mips64, matt-nb4-mips64-k7-u2a-k9b, matt-mips64-premerge-20101231, matt-mips64-base2, matt-mips64-base, matt-mips64, matt-armv6-prevmlocking, matt-armv6-nbase, matt-armv6-base, matt-armv6, khorben-n900, keiichi-mipv6-nbase, keiichi-mipv6-base, keiichi-mipv6, jymxensuspend-base, jym-xensuspend-nbase, jym-xensuspend-base, jym-xensuspend, jruoho-x86intr-base, jruoho-x86intr, jmcneill-usbmp-pre-base2, jmcneill-usbmp-base9, jmcneill-usbmp-base8, jmcneill-usbmp-base7, jmcneill-usbmp-base6, jmcneill-usbmp-base5, jmcneill-usbmp-base4, jmcneill-usbmp-base3, jmcneill-usbmp-base2, jmcneill-usbmp-base10, jmcneill-usbmp-base, jmcneill-usbmp, jmcneill-pm-base, jmcneill-pm, jmcneill-base, jmcneill-audiomp3-base, jmcneill-audiomp3, hpcarm-cleanup-nbase, hpcarm-cleanup-base, hpcarm-cleanup, haad-nbase2, haad-dm-base2, haad-dm-base1, haad-dm-base, haad-dm, cube-autoconf-base, cube-autoconf, cherry-xenmp-base, cherry-xenmp, bouyer-xeni386-nbase, bouyer-xeni386-merge1, bouyer-xeni386-base, bouyer-xeni386, bouyer-xenamd64-base2, bouyer-xenamd64-base, bouyer-xenamd64, bouyer-quota2-nbase, bouyer-quota2-base, bouyer-quota2, agc-symver-base, agc-symver, ad-socklock-base1, ad-audiomp2-base, ad-audiomp2
Branch point for: yamt-lazymbuf, vmlocking, tls-maxphys, nick-nhusb

Add read-only support for SGI's Extent File System.

Reviewed by pooka@.

/*	$NetBSD: efs_dir.h,v 1.1 2007/06/29 23:30:27 rumble Exp $	*/

/*
 * Copyright (c) 2006 Stephen M. Rumble <rumble@ephemeral.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * EFS directory block and directory entry formats.
 *
 * See IRIX dir(4)
 */

#ifndef _FS_EFS_EFS_DIR_H_
#define _FS_EFS_EFS_DIR_H_

/*
 * EFS directory block (512 bytes on disk) 
 */

#define EFS_DIRBLK_MAGIC	0xbeef
#define EFS_DIRBLK_SIZE		EFS_BB_SIZE
#define EFS_DIRBLK_HEADER_SIZE	4
#define EFS_DIRBLK_SPACE_SIZE	(EFS_DIRBLK_SIZE - EFS_DIRBLK_HEADER_SIZE)

struct efs_dirblk {
	uint16_t	db_magic;	/* must be EFS_DIRBLK_MAGIC */
	uint8_t		db_firstused;	/* first dir entry offset (compacted) */
	uint8_t		db_slots;	/* total number of entry offsets */

	/*
	 * The following db_space is used for three things:
	 *  1) Array of entry offsets, one byte each, relative to the
	 *     efs_dirblk structure (not db_space!). These are stored right
	 *     shifted by one, thus providing 9 bits to address the entries.
	 *  2) Array of even-sized directory entries, which exist at even
	 *     offsets, of course.
	 *  3) Free space between the two arrays used for expanding either.
	 *
	 * The entry offsets exist in the lower offset range of de_space,
	 * followed by efs_dirent structures higher up:
	 *
	 *  db_space[sizeof(db_space)]  _______________________  _
	 *                             |                       |  |
	 *                             |  efs_dirent at z << 1 |  |
	 *                             |_______________________|  |
	 *                             |                       |  |
	 *                             |  efs_dirent at x << 1 |  |-- directory
	 *                             |                       |  |    entries
	 *                             |_______________________|  |
	 *                             |                       |  |
	 *                             |  efs_dirent at y << 1 |  |
	 * db_space[db_firstused << 1] |_______________________| _|
	 *                             |          ...          |
         *                             |       free space      |
	 *                             |          ...          |
	 *          db_space[db_slots] |_______________________| _
	 *                             |___________z___________|  |
	 *                             |___________0___________|  |-- directory
	 *                             |___________y___________|  |    entry
	 *                 db_space[0] |___________x___________| _|     offsets
	 *
	 * In the above diagram, db_firstused would be equal to y. Note that
	 * directory entry offsets need not occur in the same order as their
	 * corresponding entries. The size of the offset array is indicated
	 * by 'db_slots'. Unused slots in the middle of the array are zeroed.
	 *
	 * A range of free space between the end of the offset array and the
	 * first directory entry is used for allocating new entry offsets and
	 * directory entries. Its size is equal to ('db_firstused' << 1) -
	 * 'db_slots'.
	 *
	 * When a directory entry is added, the directory offset array is
	 * searched for a zeroed entry to use. If none is available and space
	 * permits, it is allocated from the bottom of the free space region
	 * and 'db_slots' is incremented. The space for the directory entry is
	 * allocated from the top of free space, and the offset is stored.
	 *
	 * When a directory entry is removed, all directory entries below it
	 * are moved up in order to expand the free space region. If the
	 * corresponding entry offset borders the free space (it is last in the
	 * array), it is coalesced into the free space region and 'db_slots' is
	 * decremented.
	 *
	 * XXX when all entries removed, (how) do we free the dirblk?
	 *
	 * According to IRIX dir(4), the offset of a directory entry's offset
	 * within the array of offsets does not change (say what?). That is, if
	 * directory entry P's offset is contained in db_space[3], it will
	 * remain in db_space[3] until it is removed. In other words, they do
	 * not reshuffle the entry offsets in order to coalesce the unused
	 * offset array entries into the free space region. Since we allocate
	 * from zeroed ones before dipping into free space, this is typically
	 * not a problem. However, it leaves open the case where many older
	 * files are removed, thus leaving a valid array offset at the top,
	 * which reduces free space and potentially keeps a large directory
	 * entry from being added. Since there's no technical reason why moving
	 * them around would violate the format, I'm guessing that IRIX does
	 * some sort of caching of index offsets within the array. A few quick
	 * tests seems to indicate that coalescing can be slightly more
	 * performant. One could also sort array offsets by de_namelen and
	 * binary search on lookup, but I am not sure how much performance could
	 * be gained since there are only 72 entries at maximum, far less on
	 * average, and many unix files have similar length. Quick tests show
	 * no appreciable difference when using binary search, as one would
	 * suspect.
	 */
	uint8_t		db_space[EFS_DIRBLK_SPACE_SIZE];
} __packed; 

/*
 * 'db_slots' (directory entry offset array size) can be no larger
 * than (EFS_DIRBLK_SPACE_SIZE / 9), as each efs_dirent struct is
 * minimally 6 bytes and requires one 1-byte offset entry.
 */
#define EFS_DIRBLK_SLOTS_MAX	(EFS_DIRBLK_SPACE_SIZE / 7)

#define EFS_DIRBLK_SLOT_FREE	(0)	/* free, uncoalesced slots are zeroed */

/*
 * Directory entry structure, which resides in efs_dirblk->space. Minimally
 * 6 bytes on-disk, maximally 260 bytes.
 *
 * The allocation within efs_dirblk->space must always be even, so the
 * structure is always padded by one byte if the efs_dirent struct is odd. This
 * occurs when de_namelen is even. The macros below handle this irregularity. It
 * should be noted that despite this, de_namelen will always reflect the true
 * length of de_name, which is NOT nul-terminated. Therefore without a priori
 * knowledge of this scheme, one cannot accurately calculate the efs_dirent size
 * based on the de_namelen field alone, rather EFS_DIRENT_SIZE() must be used.
 */
struct efs_dirent {
	/* entry's inode number */
	union {
		uint32_t l;
		uint16_t s[2];
	} de_u;

	/*
	 * de_name is of variable length (1 <= de_namelen <= 255). Note that
	 * the string is NOT nul-terminated.
	 */
	uint8_t		de_namelen;
	char		de_name[1];	/* variably sized */
} __packed; 

#define de_inumber	de_u.l

#define EFS_DIRBLK_TO_DIRENT(_d, _o)	(struct efs_dirent *)((char *)(_d) + _o)

/*
 * Offsets are stored on-disk right shifted one to squeeze 512 even-byte
 * boundary offsets into a uint8_t. Before being compacted, the least
 * significant bits of an offset must, of course, be zero.
 */
#define EFS_DIRENT_OFF_SHFT		1
#define EFS_DIRENT_OFF_EXPND(_x)	((_x) << EFS_DIRENT_OFF_SHFT)
#define EFS_DIRENT_OFF_COMPT(_x)	((_x) >> EFS_DIRENT_OFF_SHFT)
#define EFS_DIRENT_OFF_VALID(_x)	(((_x) & 0x1) == 0 && (_x) < \
					 EFS_DIRBLK_SPACE_SIZE) /*if expanded*/

#define EFS_DIRENT_NAMELEN_MAX		255

#define EFS_DIRENT_SIZE_MIN	(sizeof(struct efs_dirent))
#define EFS_DIRENT_SIZE_MAX	(EFS_DIRENT_SIZE_MIN+EFS_DIRENT_NAMELEN_MAX - 1)

/*
 * Calculate the size of struct efs_dirent given the provided namelen. If our
 * namelen were even, then struct efs_dirent's size would be odd. In such a case
 * we must pad to ensure 16-bit alignment of the structure.
 */
#define EFS_DIRENT_SIZE(_x)	(EFS_DIRENT_SIZE_MIN + (_x) - ((_x) & 0x1))

#endif /* !_FS_EFS_EFS_DIR_H_ */