Linux-2.6.12-rc2v2.6.12-rc2

Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.

Let it rip!

19 files changed, 3916 insertions, 0 deletions

diff --git a/fs/befs/ChangeLog b/fs/befs/ChangeLog
new file mode 100644
index 00000000000..ce8c787916b
--- /dev/null
+++ b/fs/befs/ChangeLog
@@ -0,0 +1,417 @@
+Version 0.92 (2002-03-29)
+==========
+* Minor cleanup. Ran Lindent on the sources.
+
+Version 0.92 (2002-03-27)
+==========
+* Fixed module makefile problem. It was not compiling all the correct 
+    source files!
+* Removed duplicated function definition
+* Fixed potential null pointer dereference when reporting an error
+
+Version 0.91 (2002-03-26)
+==========
+* Oy! Fixed stupid bug that would cause an unresolved symbol error.
+	Thanks to Laszlo Boszormenyi for pointing this out to me.
+
+Version 0.9 (2002-03-14)
+==========
+* Added Sergey S. Kostyliov's patch to eliminate memcpy() overhead
+	from b+tree operations. Changes the befs_read_datastream() interface.
+
+* Segregated the functions that interface directly with the linux  vfs 
+	interface into their own file called linuxvfs.c. [WD]
+
+Version 0.64 (2002-02-07)
+==========
+* Did the string comparision really right this time (btree.c) [WD]
+
+* Fixed up some places where I assumed that a long int could hold
+	a pointer value. (btree.c) [WD]
+
+* Andrew Farnham <andrewfarnham@uq.net.au> pointed out that the module
+	wouldn't work on older (<2.4.10) kernels due to an unresolved symbol.
+	This is bad, since 2.4.9 is still the current RedHat kernel. I added
+	a workaround for this problem (compatibility.h) [WD]
+
+* Sergey S. Kostyliov made befs_find_key() use a binary search to find 
+	keys within btree nodes, rather than the linear search we were using 
+	before. (btree.c) [Sergey S. Kostyliov <rathamahata@php4.ru>]
+
+* Made a debian package of the source for use with kernel-package. [WD]
+
+
+Version 0.63 (2002-01-31)
+==========
+* Fixed bug in befs_find_brun_indirect() that would result in the wrong
+	block being read. It was introduced when adding byteswapping in 
+	0.61. (datastream.c) [WD]
+
+* Fixed a longstanding bug in befs_find_key() that would result in it 
+	finding the first key that is a substring of the string it is searching
+	for. For example, this would cause files in the same directory with 
+	names like file1 and file2 to mysteriously be duplicates of each other 
+	(because they have the same inode number). Many thanks to Pavel Roskin 
+	for reporting this serious bug!!!
+	(btree.c) [WD]
+
+* Added support for long symlinks, after Axel Dorfler explained up how 
+	they work. I had forgotten all about them. (inode.c, symlink.c) [WD]
+
+* Documentation improvements in source. [WD]
+
+* Makefile fix for independent module when CONFIG_MODVERSION is set in 
+	kernel config [Pavel Roskin <proski@gnu.org>]
+
+* Compile warning fix for namei.c. [Sergey S. Kostyliov <rathamahata@php4.ru>]
+
+
+Version 0.62
+==========
+* Fixed makefile for module install [WD]
+
+
+Version 0.61 (2002-01-20)
+==========
+* Made functions in endian.h to do the correct byteswapping, no matter
+	the arch. [WD]
+
+* Abbandoned silly checks for a NULL superblock pointer in debug.c. [WD]
+
+* Misc code cleanups. Also cleanup of this changelog file. [WD]
+
+* Added byteswapping to all metadata reads from disk.
+	Uses the functions from endian.h [WD]
+
+* Remove the typedef of struct super_block to vfs_sb, as it offended
+	certain peoples' aesthetic sense. [WD]
+
+* Ditto with the befs_read_block() interface. [WD]
+ 
+
+Version 0.6 (2001-12-15)
+==========
+* Cleanup of NLS functions (util.c) [WD]
+
+* Make directory lookup/read use the NLS if an iocharset is provided. [WD]
+
+* Fixed stupid bug where specifying the uid or gid mount options as '0' 
+	would result in the filesystem using the on-disk uid and gid. [WD]
+
+* Added mount option to control debug printing. 
+	The option is, simply enough, 'debug'. 
+	(super.c, debug.c) [WD]
+
+* Removed notion of btree handle from btree.c. It was unnecessary, as the
+	linux VFS doesn't allow us to keep any state between calls. Updated 
+	dir.c, namei.c befs_fs.h to account for it. [WD]
+
+* Improved handleing of overflow nodes when listing directories. 
+	Now works for overflow nodes hanging off of nodes other than the root 
+	node. This is the cleaner solution to Brent Miszalaski's problem. [WD]
+
+* Added new debug/warning/error print functions in debug.c. 
+	More flexible. Will soon be controllable at mount time 
+	(see TODO). [WD]
+
+* Rewrote datastream positon lookups.
+	(datastream.c) [WD]
+
+* Moved the TODO list to its own file.
+
+
+Version 0.50 (2001-11-13)
+==========
+* Added workaround for mis-understanding of the nature of the b+trees used 
+	in directories. A cleaner solution will come after I've thought about it 
+	for a while. Thanks to Brent Miszalaski for finding and reporting this bug. 
+	(btree.c) [WD]
+
+* Minor cleanups
+
+* Added test for "impossible" condition of empty internal nodes in 
+	seekleaf() in btree.c [WD]
+
+* Implemented the abstracted read_block() in io.c [WD]
+
+* Cleaned up the inode validation in inode.c [WD]
+
+* Anton Altaparmakov figured out (by asking Linus :) ) what was causing the 
+ 	hanging disk io problem. It turns out you need to have the sync_pages 
+	callback defined in your address_space_ops, even if it just uses the 
+	default linux-supplied implementation. Fixed. Works now.
+	(file.c) [WD]
+
+* Anton Altaparmakov and Christoph Hellwig alerted me to the fact that 
+	filesystem code should be using GFP_NOFS instead of GFP_KERNEL as the 
+	priority parameter to kmalloc(). Fixed. 
+	(datastream.c, btree.c super.c inode.c) [WD]
+
+* Anton also told me that the blocksize is not allowed to be larger than 
+	the page size in linux, which is 4k i386. Oops. Added a test for 
+	(blocksize > PAGE_SIZE), and refuse to mount in that case. What this 
+	practicaly means is that 8k blocksize volumes won't work without a major
+	restructuring of the driver (or an alpha or other 64bit hardware). [WD]
+
+* Cleaned up the befs_count_blocks() function. Much smarter now. 
+	And somewhat smaller too. [WD]
+
+* Made inode allocations use a slab cache 
+	(super.c inode.c) [WD]
+
+* Moved the freeing of the private inode section from put_inode() to 
+	clear_inode(). This fixes a potential free twice type bug. Put_inode() 
+	can be called multiple times for each inode struct. [WD]
+
+* Converted all non vfs-callback functions to use befs_sb_info as the 
+	superblock type, rather than struct super_block. This is for 
+	portablity. [WD]
+
+* Fixed a couple of compile warnings due to use of malloc.h, when slab.h 
+	is the new way. (inode.c, super.c) [WD]
+
+* Fixed erronous includes of linux/befs_fs_i.h and linux/befs_fs_sb.h 
+	in inode.c [WD]
+
+Version 0.45 (2001-10-29)
+==========
+* Added functions to get the private superblock and inode structures from 
+	their enclosing public structures. Switched all references to the 
+	private portions to use them. (many files) [WD]
+
+* Made read_super and read_inode allocate the private portions of those 
+	structures into the generic pointer fields of the public structures 
+	with kmalloc(). put_super and put_inode free them. This allows us not 
+	to have to touch the definitions of the public structures in 
+	include/linux/fs.h. Also, befs_inode_info is huge (becuase of the 
+	symlink string). (super.c, inode.c, befs_fs.h) [WD]
+
+* Fixed a thinko that was corrupting file reads after the first block_run 
+	is done being read. (datastream.c) [WD]
+
+* Removed fsync() hooks, since a read-only filesystem doesn't need them. 
+	[Christoph Hellwig].
+
+* Fixed befs_readlink() (symlink.c) [Christoph Hellwig].
+
+* Removed all the Read-Write stuff. I'll redo it when it is time to add 
+	write support (various files) [WD].
+
+* Removed prototypes for functions who's definitions have been removed 
+	(befs_fs.h) [WD].
+
+
+Version 0.4 (2001-10-28)
+==========
+* Made it an option to use the old non-pagecache befs_file_read() for 
+	testing purposes. (fs/Config.in)
+
+* Fixed unused variable warnings when compiling without debugging.
+
+* Fixed a bug where the inode and super_block didn't get their blockbits 
+	fields set (inode.c and super.c). 
+
+* Release patch version 11. AKA befs-driver version 0.4.
+
+* Thats right. New versioning scheme. 
+	I've done some serious testing on it now (on my box anyhow), and it 
+	seems stable and not outragously slow. Existing features are more-or-less 
+	correct (see TODO list). But it isn't 1.0 yet. I think 0.4 gives me some 
+	headroom before the big 1.0.
+
+
+2001-10-26
+==========
+* Fixed date format in this file. Was I smoking crack?
+
+* Removed old datastream code from file.c, since it is nolonger used.
+
+* Generic_read_file() is now used to read regular file data. 
+	It doesn't chew up the buffer cache (it does page io instead), and seems 
+	to be about as fast (even though it has to look up each file block 
+	indivdualy). And it knows about doing readahead, which is a major plus. 
+	So it does i/o in much larger chunks. It is the correct linux way. It 
+	uses befs_get_block() by way of befs_readpage() to find the disk offsets 
+	of blocks, which in turn calls befs_fpos2brun() in datastream.c to do 
+	the hard work of finding the disk block number.
+
+* Changed method of checking for a dirty filesystem in befs_read_super 
+	(super.c). Now we check to see if log_start and log_end differ. If so, 
+	the journal needs to be replayed, and the filesystem cannot be mounted.
+
+* Fixed an extra instance of MOD_DEC_USE_COUNT in super.c
+
+* Fixed a problem with reading the superblock on devices with large sector 
+	sizes (such as cdroms) on linux 2.4.10 and up.
+
+2001-10-24
+==========
+* Fix nasty bug in converting block numbers to struct befs_inode_addr. 
+	Subtle, because the old version was only sometimes wrong. 
+	Probably responsible for lots of problems. (inode.c)
+
+* Fix bug with reading an empty directory. (btree.c and dir.c)
+
+* This one looks good. Release patch version 10
+
+2001-10-23
+==========
+* Added btree searching function.
+
+* Use befs_btree_find in befs_lookup (namei.c)
+
+* Additional comments in btree.c
+
+2001-10-22
+==========
+* Added B+tree reading functions (in btree.c). 
+	Made befs_readdir() use them them instead of the cruft in index.c.
+
+2001-09-11
+==========
+* Converted befs_read_file() to use the new datastream code.
+
+* Finally updated the README file.
+
+* Added many comments.
+
+* Posted version 6
+
+* Removed byte-order conversion code. 
+	I have no intention of supporting it, and it was very ugly. 
+	Flow control with #ifdef (ugh). Maybe I'll redo it once 
+	native byteorder works 100%.
+
+2001-09-10
+==========
+* Finished implementing read_datastream()
+
+* made befs_read_brun() more general
+	Supports an offset to start at and a max bytes to read
+	Added a wrapper function to give the old call
+
+2001-09-30
+==========
+* Discovered that the datastream handleing code in file.c is quite deficient 
+	in several respects. For one thing, it doesn't deal with indirect blocks
+
+* Rewrote datastream handleing.
+
+* Created io.c, for io related functions.
+	Previously, the befs_bread() funtions lived in file.c
+	Created the befs_read_brun() function.
+
+
+2001-09-07
+==========
+* Made a function to actually count the number of fs blocks used by a file.
+	And helper functions.
+	(fs/befs/inode.c)
+
+2001-09-05
+==========
+* Fixed a misunderstanding of the inode fields. 
+	This fixed the problmem with wrong file sizes from du and others.
+	The i_blocks field of the inode struct is not the number of blocks for the
+	inode, it is the number of blocks for the file.	Also, i_blksize is not
+	necessarily the size of the inode, although in  practice it works out.
+	Changed to blocksize of filesystem.
+	(fs/befs/inode.c)
+
+* Permanently removed code that had been provisionally ifdefed out of befs_fs.h
+
+* Since we don't support access time, make that field zero, instead of 
+	copying m_time.
+	(fs/befs/inode.c)
+
+* Added sanity check for inode reading
+	Make sure inode we got was the one we asked for. 
+	(fs/befs/inode.c)
+
+* Code cleanup
+	Local pointers to commonly used structures in inode.c.
+	Got rid of abominations befs_iaddr2inode() and befs_inode2ino(). 
+	Replaced with single function iaddr2blockno().
+	(fs/befs/super.c) (fs/befs/inode.c)
+
+2001-09-01
+==========
+* Fixed the problem with statfs where it would always claim the disk was 
+	half full, due to improper understanding of the statfs fields.
+	(fs/befs/super.c)
+
+* Posted verion 4 of the patch
+
+2001-09-01
+==========
+* Changed the macros in befs_fs.h to inline functions.
+	More readable. Typesafe. Better
+	(include/linux/befs_fs.h)
+
+* Moved type definitions from befs_fs.h to a new file, befs_fs_types.h 
+	Because befs_fs_i.h and befs_fs_sb.h were including befs_fs.h for the 
+	typedefs, and they are inlcuded in <linux/fs.h>, which has definitions 
+	that I want the inline functions in befs_fs.h to be able to see. Nasty
+	circularity.
+	(include/linux/befs_fs.h)
+
+2001-08-30
+==========
+* Cleaned up some wording.
+
+* Added additional consitency checks on mount
+	Check block_size agrees with block_shift
+	Check flags == BEFS_CLEAN
+	(fs/befs/super.c)
+
+* Tell the kernel to only mount befs read-only. 
+	By setting the MS_RDONLY flag in befs_read_super().
+	Not that it was possible to write before. But now the kernel won't even try.
+	(fs/befs/super.c)
+
+* Got rid of kernel warning on mount.
+	The kernel doesn't like it if you call set_blocksize() on a device when 
+	you have some of its blocks open. Moved the second set_blocksize() to the
+	very end of befs_read_super(), after we are done with the disk superblock.
+	(fs/befs/super.c)
+	
+* Fixed wrong number of args bug in befs_dump_inode
+	(fs/befs/debug.c)
+
+* Solved lots of type mismatches in kprint()s
+	(everwhere)
+
+2001-08-27
+==========
+* Cleaned up the fs/Config.in entries a bit, now slightly more descriptive.
+
+* BeFS depends on NLS, so I made activating BeFS enable the NLS questions
+	(fs/nls/Config.in)
+
+* Added Configure.help entries for CONFIG_BEFS_FS and CONFIG_DEBUG_BEFS
+	(Documentation/Configure.help)
+
+2001-08-??
+==========
+* Removed superblock locking calls in befs_read_super(). In 2.4, the VFS 
+	hands us a super_block struct that is already locked.
+
+2001-08-13
+==========
+* Will Dyson <will_dyson@pobox.com> is now attempting to maintain this module
+	Makoto Kato <m_kato@ga2.so-net.ne.jp> is original author.Daniel Berlin 
+	also did some work on it (fixing it up for the later 2.3.x kernels, IIRC).
+
+* Fixed compile errors on 2.4.1 kernel (WD)
+	Resolve rejected patches
+	Accomodate changed NLS interface (util.h)
+	Needed to include <linux/slab.h> in most files
+	Makefile changes
+	fs/Config.in changes
+
+* Tried to niceify the code using the ext2 fs as a guide
+	Declare befs_fs_type using the DECLARE_FSTYPE_DEV() macro
+
+* Made it a configure option to turn on debugging (fs/Config.in)
+
+* Compiles on 2.4.7
diff --git a/fs/befs/Makefile b/fs/befs/Makefile
new file mode 100644
index 00000000000..2f370bd7a50
--- /dev/null
+++ b/fs/befs/Makefile
@@ -0,0 +1,7 @@
+#
+# Makefile for the linux BeOS filesystem routines.
+#
+ 
+obj-$(CONFIG_BEFS_FS) += befs.o
+
+befs-objs := datastream.o btree.o super.o inode.o debug.o io.o linuxvfs.o
diff --git a/fs/befs/TODO b/fs/befs/TODO
new file mode 100644
index 00000000000..3250921aa2e
--- /dev/null
+++ b/fs/befs/TODO
@@ -0,0 +1,14 @@
+TODO
+==========
+
+* Convert comments to the Kernel-Doc format.
+
+* Befs_fs.h has gotten big and messy. No reason not to break it up into 
+	smaller peices.
+
+* See if Alexander Viro's option parser made it into the kernel tree. 
+	Use that if we can. (include/linux/parser.h)
+
+* See if we really need separate types for on-disk and in-memory 
+	representations of the superblock and inode.
+
diff --git a/fs/befs/attribute.c b/fs/befs/attribute.c
new file mode 100644
index 00000000000..e329d727053
--- /dev/null
+++ b/fs/befs/attribute.c
@@ -0,0 +1,117 @@
+/*
+ * linux/fs/befs/attribute.c
+ *
+ * Copyright (C) 2002 Will Dyson <will_dyson@pobox.com>
+ *
+ * Many thanks to Dominic Giampaolo, author of "Practical File System
+ * Design with the Be File System", for such a helpful book.
+ *
+ */
+
+#include <linux/fs.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+
+#include "befs.h"
+#include "endian.h"
+
+#define SD_DATA(sd)\
+	(void*)((char*)sd + sizeof(*sd) + (sd->name_size - sizeof(sd->name)))
+
+#define SD_NEXT(sd)\
+	(befs_small_data*)((char*)sd + sizeof(*sd) + (sd->name_size - \
+	sizeof(sd->name) + sd->data_size))
+
+int
+list_small_data(struct super_block *sb, befs_inode * inode, filldir_t filldir);
+
+befs_small_data *
+find_small_data(struct super_block *sb, befs_inode * inode,
+				 const char *name);
+int
+read_small_data(struct super_block *sb, befs_inode * inode,
+		 befs_small_data * sdata, void *buf, size_t bufsize);
+
+/**
+ *
+ *
+ *
+ *
+ *
+ */
+befs_small_data *
+find_small_data(struct super_block *sb, befs_inode * inode, const char *name)
+{
+	befs_small_data *sdata = inode->small_data;
+
+	while (sdata->type != 0) {
+		if (strcmp(name, sdata->name) != 0) {
+			return sdata;
+		}
+		sdata = SD_NEXT(sdata);
+	}
+	return NULL;
+}
+
+/**
+ *
+ *
+ *
+ *
+ *
+ */
+int
+read_small_data(struct super_block *sb, befs_inode * inode,
+		const char *name, void *buf, size_t bufsize)
+{
+	befs_small_data *sdata;
+
+	sdata = find_small_data(sb, inode, name);
+	if (sdata == NULL)
+		return BEFS_ERR;
+	else if (sdata->data_size > bufsize)
+		return BEFS_ERR;
+
+	memcpy(buf, SD_DATA(sdata), sdata->data_size);
+
+	return BEFS_OK;
+}
+
+/**
+ *
+ *
+ *
+ *
+ *
+ */
+int
+list_small_data(struct super_block *sb, befs_inode * inode)
+{
+
+}
+
+/**
+ *
+ *
+ *
+ *
+ *
+ */
+int
+list_attr(struct super_block *sb, befs_inode * inode)
+{
+
+}
+
+/**
+ *
+ *
+ *
+ *
+ *
+ */
+int
+read_attr(struct super_block *sb, befs_inode * inode)
+{
+
+}
diff --git a/fs/befs/befs.h b/fs/befs/befs.h
new file mode 100644
index 00000000000..057a2c3d73b
--- /dev/null
+++ b/fs/befs/befs.h
@@ -0,0 +1,154 @@
+/*
+ * befs.h
+ *
+ * Copyright (C) 2001-2002 Will Dyson <will_dyson@pobox.com>
+ * Copyright (C) 1999 Makoto Kato (m_kato@ga2.so-net.ne.jp)
+ */
+
+#ifndef _LINUX_BEFS_H
+#define _LINUX_BEFS_H
+
+#include "befs_fs_types.h"
+
+/* used in debug.c */
+#define BEFS_VERSION "0.9.3"
+
+
+typedef u64 befs_blocknr_t;
+/*
+ * BeFS in memory structures
+ */
+
+typedef struct befs_mount_options {
+	gid_t gid;
+	uid_t uid;
+	int use_gid;
+	int use_uid;
+	int debug;
+	char *iocharset;
+} befs_mount_options;
+
+typedef struct befs_sb_info {
+	u32 magic1;
+	u32 block_size;
+	u32 block_shift;
+	int byte_order;
+	befs_off_t num_blocks;
+	befs_off_t used_blocks;
+	u32 inode_size;
+	u32 magic2;
+
+	/* Allocation group information */
+	u32 blocks_per_ag;
+	u32 ag_shift;
+	u32 num_ags;
+
+	/* jornal log entry */
+	befs_block_run log_blocks;
+	befs_off_t log_start;
+	befs_off_t log_end;
+
+	befs_inode_addr root_dir;
+	befs_inode_addr indices;
+	u32 magic3;
+
+	befs_mount_options mount_opts;
+	struct nls_table *nls;
+
+} befs_sb_info;
+
+typedef struct befs_inode_info {
+	u32 i_flags;
+	u32 i_type;
+
+	befs_inode_addr i_inode_num;
+	befs_inode_addr i_parent;
+	befs_inode_addr i_attribute;
+
+	union {
+		befs_data_stream ds;
+		char symlink[BEFS_SYMLINK_LEN];
+	} i_data;
+
+	struct inode vfs_inode;
+
+} befs_inode_info;
+
+enum befs_err {
+	BEFS_OK,
+	BEFS_ERR,
+	BEFS_BAD_INODE,
+	BEFS_BT_END,
+	BEFS_BT_EMPTY,
+	BEFS_BT_MATCH,
+	BEFS_BT_PARMATCH,
+	BEFS_BT_NOT_FOUND
+};
+
+
+/****************************/
+/* debug.c */
+void befs_error(const struct super_block *sb, const char *fmt, ...);
+void befs_warning(const struct super_block *sb, const char *fmt, ...);
+void befs_debug(const struct super_block *sb, const char *fmt, ...);
+
+void befs_dump_super_block(const struct super_block *sb, befs_super_block *);
+void befs_dump_inode(const struct super_block *sb, befs_inode *);
+void befs_dump_index_entry(const struct super_block *sb, befs_btree_super *);
+void befs_dump_index_node(const struct super_block *sb, befs_btree_nodehead *);
+/****************************/
+
+
+/* Gets a pointer to the private portion of the super_block
+ * structure from the public part
+ */
+static inline befs_sb_info *
+BEFS_SB(const struct super_block *super)
+{
+	return (befs_sb_info *) super->s_fs_info;
+}
+
+static inline befs_inode_info *
+BEFS_I(const struct inode *inode)
+{
+	return list_entry(inode, struct befs_inode_info, vfs_inode);
+}
+
+static inline befs_blocknr_t
+iaddr2blockno(struct super_block *sb, befs_inode_addr * iaddr)
+{
+	return ((iaddr->allocation_group << BEFS_SB(sb)->ag_shift) +
+		iaddr->start);
+}
+
+static inline befs_inode_addr
+blockno2iaddr(struct super_block *sb, befs_blocknr_t blockno)
+{
+	befs_inode_addr iaddr;
+	iaddr.allocation_group = blockno >> BEFS_SB(sb)->ag_shift;
+	iaddr.start =
+	    blockno - (iaddr.allocation_group << BEFS_SB(sb)->ag_shift);
+	iaddr.len = 1;
+
+	return iaddr;
+}
+
+static inline unsigned int
+befs_iaddrs_per_block(struct super_block *sb)
+{
+	return BEFS_SB(sb)->block_size / sizeof (befs_inode_addr);
+}
+
+static inline int
+befs_iaddr_is_empty(befs_inode_addr * iaddr)
+{
+	return (!iaddr->allocation_group) && (!iaddr->start) && (!iaddr->len);
+}
+
+static inline size_t
+befs_brun_size(struct super_block *sb, befs_block_run run)
+{
+	return BEFS_SB(sb)->block_size * run.len;
+}
+
+#endif				/* _LINUX_BEFS_H */
diff --git a/fs/befs/befs_fs_types.h b/fs/befs/befs_fs_types.h
new file mode 100644
index 00000000000..9095518e918
--- /dev/null
+++ b/fs/befs/befs_fs_types.h
@@ -0,0 +1,213 @@
+/*
+ * include/linux/befs_fs_types.h
+ *
+ * Copyright (C) 2001 Will Dyson (will@cs.earlham.edu)
+ *
+ *
+ *
+ * from linux/include/linux/befs_fs.h
+ *
+ * Copyright (C) 1999 Makoto Kato (m_kato@ga2.so-net.ne.jp)
+ *
+ */
+
+#ifndef _LINUX_BEFS_FS_TYPES
+#define _LINUX_BEFS_FS_TYPES
+
+#ifdef __KERNEL__
+#include <linux/types.h>
+#endif /*__KERNEL__*/
+
+#define PACKED __attribute__ ((__packed__))
+
+/*
+ * Max name lengths of BFS
+ */
+
+#define BEFS_NAME_LEN 255
+
+#define BEFS_SYMLINK_LEN 144
+#define BEFS_NUM_DIRECT_BLOCKS 12
+#define B_OS_NAME_LENGTH 32
+
+/* The datastream blocks mapped by the double-indirect
+ * block are always 4 fs blocks long.
+ * This eliminates the need for linear searches among
+ * the potentially huge number of indirect blocks
+ *
+ * Err. Should that be 4 fs blocks or 4k???
+ * It matters on large blocksize volumes
+ */
+#define BEFS_DBLINDIR_BRUN_LEN 4
+
+/*
+ * Flags of superblock
+ */
+
+enum super_flags {
+	BEFS_BYTESEX_BE,
+	BEFS_BYTESEX_LE,
+	BEFS_CLEAN = 0x434c454e,
+	BEFS_DIRTY = 0x44495254,
+	BEFS_SUPER_MAGIC1 = 0x42465331,	/* BFS1 */
+	BEFS_SUPER_MAGIC2 = 0xdd121031,
+	BEFS_SUPER_MAGIC3 = 0x15b6830e,
+};
+
+#define BEFS_BYTEORDER_NATIVE 0x42494745
+
+#define BEFS_SUPER_MAGIC BEFS_SUPER_MAGIC1
+
+/*
+ * Flags of inode
+ */
+
+#define BEFS_INODE_MAGIC1 0x3bbe0ad9
+
+enum inode_flags {
+	BEFS_INODE_IN_USE = 0x00000001,
+	BEFS_ATTR_INODE = 0x00000004,
+	BEFS_INODE_LOGGED = 0x00000008,
+	BEFS_INODE_DELETED = 0x00000010,
+	BEFS_LONG_SYMLINK = 0x00000040,
+	BEFS_PERMANENT_FLAG = 0x0000ffff,
+	BEFS_INODE_NO_CREATE = 0x00010000,
+	BEFS_INODE_WAS_WRITTEN = 0x00020000,
+	BEFS_NO_TRANSACTION = 0x00040000,
+};
+/* 
+ * On-Disk datastructures of BeFS
+ */
+
+typedef u64 befs_off_t;
+typedef u64 befs_time_t;
+typedef void befs_binode_etc;
+
+/* Block runs */
+typedef struct {
+	u32 allocation_group;
+	u16 start;
+	u16 len;
+} PACKED befs_block_run;
+
+typedef befs_block_run befs_inode_addr;
+
+/*
+ * The Superblock Structure
+ */
+typedef struct {
+	char name[B_OS_NAME_LENGTH];
+	u32 magic1;
+	u32 fs_byte_order;
+
+	u32 block_size;
+	u32 block_shift;
+
+	befs_off_t num_blocks;
+	befs_off_t used_blocks;
+
+	u32 inode_size;
+
+	u32 magic2;
+	u32 blocks_per_ag;
+	u32 ag_shift;
+	u32 num_ags;
+
+	u32 flags;
+
+	befs_block_run log_blocks;
+	befs_off_t log_start;
+	befs_off_t log_end;
+
+	u32 magic3;
+	befs_inode_addr root_dir;
+	befs_inode_addr indices;
+
+} PACKED befs_super_block;
+
+/* 
+ * Note: the indirect and dbl_indir block_runs may
+ * be longer than one block!
+ */
+typedef struct {
+	befs_block_run direct[BEFS_NUM_DIRECT_BLOCKS];
+	befs_off_t max_direct_range;
+	befs_block_run indirect;
+	befs_off_t max_indirect_range;
+	befs_block_run double_indirect;
+	befs_off_t max_double_indirect_range;
+	befs_off_t size;
+} PACKED befs_data_stream;
+
+/* Attribute */
+typedef struct {
+	u32 type;
+	u16 name_size;
+	u16 data_size;
+	char name[1];
+} PACKED befs_small_data;
+
+/* Inode structure */
+typedef struct {
+	u32 magic1;
+	befs_inode_addr inode_num;
+	u32 uid;
+	u32 gid;
+	u32 mode;
+	u32 flags;
+	befs_time_t create_time;
+	befs_time_t last_modified_time;
+	befs_inode_addr parent;
+	befs_inode_addr attributes;
+	u32 type;
+
+	u32 inode_size;
+	u32 etc;		/* not use */
+
+	union {
+		befs_data_stream datastream;
+		char symlink[BEFS_SYMLINK_LEN];
+	} data;
+
+	u32 pad[4];		/* not use */
+	befs_small_data small_data[1];
+} PACKED befs_inode;
+
+/*
+ * B+tree superblock
+ */
+
+#define BEFS_BTREE_MAGIC 0x69f6c2e8
+
+enum btree_types {
+	BTREE_STRING_TYPE = 0,
+	BTREE_INT32_TYPE = 1,
+	BTREE_UINT32_TYPE = 2,
+	BTREE_INT64_TYPE = 3,
+	BTREE_UINT64_TYPE = 4,
+	BTREE_FLOAT_TYPE = 5,
+	BTREE_DOUBLE_TYPE = 6
+};
+
+typedef struct {
+	u32 magic;
+	u32 node_size;
+	u32 max_depth;
+	u32 data_type;
+	befs_off_t root_node_ptr;
+	befs_off_t free_node_ptr;
+	befs_off_t max_size;
+} PACKED befs_btree_super;
+
+/*
+ * Header stucture of each btree node
+ */
+typedef struct {
+	befs_off_t left;
+	befs_off_t right;
+	befs_off_t overflow;
+	u16 all_key_count;
+	u16 all_key_length;
+} PACKED befs_btree_nodehead;
+
+#endif				/* _LINUX_BEFS_FS_TYPES */
diff --git a/fs/befs/btree.c b/fs/befs/btree.c
new file mode 100644
index 00000000000..76e21979940
--- /dev/null
+++ b/fs/befs/btree.c
@@ -0,0 +1,788 @@
+/*
+ * linux/fs/befs/btree.c
+ *
+ * Copyright (C) 2001-2002 Will Dyson <will_dyson@pobox.com>
+ *
+ * Licensed under the GNU GPL. See the file COPYING for details.
+ *
+ * 2002-02-05: Sergey S. Kostyliov added binary search withing
+ * 		btree nodes.
+ *
+ * Many thanks to:
+ *
+ * Dominic Giampaolo, author of "Practical File System
+ * Design with the Be File System", for such a helpful book.
+ * 
+ * Marcus J. Ranum, author of the b+tree package in 
+ * comp.sources.misc volume 10. This code is not copied from that
+ * work, but it is partially based on it.
+ *
+ * Makoto Kato, author of the original BeFS for linux filesystem
+ * driver.
+ */
+
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/slab.h>
+#include <linux/mm.h>
+#include <linux/buffer_head.h>
+
+#include "befs.h"
+#include "btree.h"
+#include "datastream.h"
+#include "endian.h"
+
+/*
+ * The btree functions in this file are built on top of the
+ * datastream.c interface, which is in turn built on top of the
+ * io.c interface.
+ */
+
+/* Befs B+tree structure:
+ * 
+ * The first thing in the tree is the tree superblock. It tells you
+ * all kinds of useful things about the tree, like where the rootnode
+ * is located, and the size of the nodes (always 1024 with current version
+ * of BeOS).
+ *
+ * The rest of the tree consists of a series of nodes. Nodes contain a header
+ * (struct befs_btree_nodehead), the packed key data, an array of shorts 
+ * containing the ending offsets for each of the keys, and an array of
+ * befs_off_t values. In interior nodes, the keys are the ending keys for 
+ * the childnode they point to, and the values are offsets into the 
+ * datastream containing the tree. 
+ */
+
+/* Note:
+ * 
+ * The book states 2 confusing things about befs b+trees. First, 
+ * it states that the overflow field of node headers is used by internal nodes
+ * to point to another node that "effectively continues this one". Here is what
+ * I believe that means. Each key in internal nodes points to another node that
+ * contains key values less than itself. Inspection reveals that the last key 
+ * in the internal node is not the last key in the index. Keys that are 
+ * greater than the last key in the internal node go into the overflow node. 
+ * I imagine there is a performance reason for this.
+ *
+ * Second, it states that the header of a btree node is sufficient to 
+ * distinguish internal nodes from leaf nodes. Without saying exactly how. 
+ * After figuring out the first, it becomes obvious that internal nodes have
+ * overflow nodes and leafnodes do not.
+ */