Adding upstream version 4.19.249.upstream/4.19.249

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

19 files changed, 3883 insertions, 0 deletions

diff --git a/fs/befs/ChangeLog b/fs/befs/ChangeLog
new file mode 100644
index 000000000..aff7eec8f
--- /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 comparison 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 position 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 
+	practically 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 (because 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 SB_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
+	(currently at fs/befs/Kconfig)
+
+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
+	Accommodate 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/Kconfig b/fs/befs/Kconfig
new file mode 100644
index 000000000..edc5cc2ae
--- /dev/null
+++ b/fs/befs/Kconfig
@@ -0,0 +1,26 @@
+config BEFS_FS
+	tristate "BeOS file system (BeFS) support (read only)"
+	depends on BLOCK
+	select NLS
+	help
+	  The BeOS File System (BeFS) is the native file system of Be, Inc's
+	  BeOS. Notable features include support for arbitrary attributes
+	  on files and directories, and database-like indices on selected
+	  attributes. (Also note that this driver doesn't make those features
+	  available at this time). It is a 64 bit filesystem, so it supports
+	  extremely large volumes and files.
+
+	  If you use this filesystem, you should also say Y to at least one
+	  of the NLS (native language support) options below.
+
+	  If you don't know what this is about, say N.
+
+	  To compile this as a module, choose M here: the module will be
+	  called befs.
+
+config BEFS_DEBUG
+	bool "Debug BeFS"
+	depends on BEFS_FS
+	help
+	  If you say Y here, you can use the 'debug' mount option to enable
+	  debugging output from the driver.
diff --git a/fs/befs/Makefile b/fs/befs/Makefile
new file mode 100644
index 000000000..8b9f66642
--- /dev/null
+++ b/fs/befs/Makefile
@@ -0,0 +1,7 @@
+#
+# Makefile for the linux BeOS filesystem routines.
+#
+ 
+obj-$(CONFIG_BEFS_FS) += befs.o
+ccflags-$(CONFIG_BEFS_DEBUG)    += -DDEBUG
+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 000000000..3250921aa
--- /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/befs.h b/fs/befs/befs.h
new file mode 100644
index 000000000..7cd472456
--- /dev/null
+++ b/fs/befs/befs.h
@@ -0,0 +1,150 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * 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
+ */
+
+struct befs_mount_options {
+	kgid_t gid;
+	kuid_t uid;
+	int use_gid;
+	int use_uid;
+	int debug;
+	char *iocharset;
+};
+
+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;
+
+	/* State of the superblock */
+	u32 flags;
+
+	/* Journal 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;
+
+	struct befs_mount_options mount_opts;
+	struct nls_table *nls;
+};
+
+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;
+};
+
+enum befs_err {
+	BEFS_OK,
+	BEFS_ERR,
+	BEFS_BAD_INODE,
+	BEFS_BT_END,
+	BEFS_BT_EMPTY,
+	BEFS_BT_MATCH,
+	BEFS_BT_OVERFLOW,
+	BEFS_BT_NOT_FOUND
+};
+
+
+/****************************/
+/* debug.c */
+__printf(2, 3)
+void befs_error(const struct super_block *sb, const char *fmt, ...);
+__printf(2, 3)
+void befs_warning(const struct super_block *sb, const char *fmt, ...);
+__printf(2, 3)
+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_disk_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 struct befs_sb_info *
+BEFS_SB(const struct super_block *super)
+{
+	return (struct befs_sb_info *) super->s_fs_info;
+}
+
+static inline struct befs_inode_info *
+BEFS_I(const struct inode *inode)
+{
+	return container_of(inode, struct befs_inode_info, vfs_inode);
+}
+
+static inline befs_blocknr_t
+iaddr2blockno(struct super_block *sb, const 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_disk_inode_addr);
+}
+
+#include "endian.h"
+
+#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 000000000..8019fde81
--- /dev/null
+++ b/fs/befs/befs_fs_types.h
@@ -0,0 +1,256 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * fs/befs/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_BYTEORDER_NATIVE_LE ((__force fs32)cpu_to_le32(BEFS_BYTEORDER_NATIVE))
+#define BEFS_BYTEORDER_NATIVE_BE ((__force fs32)cpu_to_be32(BEFS_BYTEORDER_NATIVE))
+
+#define BEFS_SUPER_MAGIC BEFS_SUPER_MAGIC1
+#define BEFS_SUPER_MAGIC1_LE ((__force fs32)cpu_to_le32(BEFS_SUPER_MAGIC1))
+#define BEFS_SUPER_MAGIC1_BE ((__force fs32)cpu_to_be32(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 __bitwise fs64;
+typedef u32 __bitwise fs32;
+typedef u16 __bitwise fs16;
+
+typedef u64 befs_off_t;
+typedef fs64 befs_time_t;
+
+/* Block runs */
+typedef struct {
+	fs32 allocation_group;
+	fs16 start;
+	fs16 len;
+} PACKED befs_disk_block_run;
+
+typedef struct {
+	u32 allocation_group;
+	u16 start;
+	u16 len;
+} PACKED befs_block_run;
+
+typedef befs_disk_block_run befs_disk_inode_addr;
+typedef befs_block_run befs_inode_addr;
+
+/*
+ * The Superblock Structure
+ */
+typedef struct {
+	char name[B_OS_NAME_LENGTH];
+	fs32 magic1;
+	fs32 fs_byte_order;
+
+	fs32 block_size;
+	fs32 block_shift;
+
+	fs64 num_blocks;
+	fs64 used_blocks;
+
+	fs32 inode_size;
+
+	fs32 magic2;
+	fs32 blocks_per_ag;
+	fs32 ag_shift;
+	fs32 num_ags;
+
+	fs32 flags;
+
+	befs_disk_block_run log_blocks;
+	fs64 log_start;
+	fs64 log_end;
+
+	fs32 magic3;
+	befs_disk_inode_addr root_dir;
+	befs_disk_inode_addr indices;
+
+} PACKED befs_super_block;
+
+/*
+ * Note: the indirect and dbl_indir block_runs may
+ * be longer than one block!
+ */
+typedef struct {
+	befs_disk_block_run direct[BEFS_NUM_DIRECT_BLOCKS];
+	fs64 max_direct_range;
+	befs_disk_block_run indirect;
+	fs64 max_indirect_range;
+	befs_disk_block_run double_indirect;
+	fs64 max_double_indirect_range;
+	fs64 size;
+} PACKED befs_disk_data_stream;
+
+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 {
+	fs32 type;
+	fs16 name_size;
+	fs16 data_size;
+	char name[1];
+} PACKED befs_small_data;
+
+/* Inode structure */
+typedef struct {
+	fs32 magic1;
+	befs_disk_inode_addr inode_num;
+	fs32 uid;
+	fs32 gid;
+	fs32 mode;
+	fs32 flags;
+	befs_time_t create_time;
+	befs_time_t last_modified_time;
+	befs_disk_inode_addr parent;
+	befs_disk_inode_addr attributes;
+	fs32 type;
+
+	fs32 inode_size;
+	fs32 etc;		/* not use */
+
+	union {
+		befs_disk_data_stream datastream;
+		char symlink[BEFS_SYMLINK_LEN];
+	} data;
+
+	fs32 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 {
+	fs32 magic;
+	fs32 node_size;
+	fs32 max_depth;
+	fs32 data_type;
+	fs64 root_node_ptr;
+	fs64 free_node_ptr;
+	fs64 max_size;
+} PACKED befs_disk_btree_super;
+
+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 structure of each btree node
+ */
+typedef struct {
+	fs64 left;
+	fs64 right;
+	fs64 overflow;
+	fs16 all_key_count;
+	fs16 all_key_length;
+} PACKED befs_btree_nodehead;
+
+typedef struct {
+	befs_off_t left;
+	befs_off_t right;
+	befs_off_t overflow;
+	u16 all_key_count;
+	u16 all_key_length;
+} PACKED befs_host_btree_nodehead;
+
+#endif				/* _LINUX_BEFS_FS_TYPES */
diff --git a/fs/befs/btree.c b/fs/befs/btree.c
new file mode 100644
index 000000000..1b7e0f712
--- /dev/null
+++ b/fs/befs/btree.c
@@ -0,0 +1,784 @@
+/*
+ * 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 within
+ * 		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"
+
+/*
+ * 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.
+ */
+
+/*
+ * Currently, this code is only good for directory B+trees.
+ * In order to be used for other BFS indexes, it needs to be extended to handle
+ * duplicate keys and non-string keytypes (int32, int64, float, double).
+ */
+
+/*
+ * In memory structure of each btree node
+ */
+struct befs_btree_node {
+	befs_host_btree_nodehead head;	/* head of node converted to cpu byteorder */
+	struct buffer_head *bh;
+	befs_btree_nodehead *od_node;	/* on disk node */
+};
+
+/* local constants */
+static const befs_off_t BEFS_BT_INVAL = 0xffffffffffffffffULL;
+
+/* local functions */
+static int befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
+			       befs_btree_super * bt_super,
+			       struct befs_btree_node *this_node,
+			       befs_off_t * node_off);
+
+static int befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
+			      befs_btree_super * sup);
+
+static int befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
+			     struct befs_btree_node *node,
+			     befs_off_t node_off);
+
+static int befs_leafnode(struct befs_btree_node *node);
+
+static fs16 *befs_bt_keylen_index(struct befs_btree_node *node);
+
+static fs64 *befs_bt_valarray(struct befs_btree_node *node);
+
+static char *befs_bt_keydata(struct befs_btree_node *node);
+
+static int befs_find_key(struct super_block *sb,
+			 struct befs_btree_node *node,
+			 const char *findkey, befs_off_t * value);
+
+static char *befs_bt_get_key(struct super_block *sb,
+			     struct befs_btree_node *node,
+			     int index, u16 * keylen);
+
+static int befs_compare_strings(const void *key1, int keylen1,
+				const void *key2, int keylen2);
+
+/**
+ * befs_bt_read_super() - read in btree superblock convert to cpu byteorder
+ * @sb:        Filesystem superblock
+ * @ds:        Datastream to read from
+ * @sup:       Buffer in which to place the btree superblock
+ *
+ * Calls befs_read_datastream to read in the btree superblock and
+ * makes sure it is in cpu byteorder, byteswapping if necessary.
+ * Return: BEFS_OK on success and if *@sup contains the btree superblock in cpu
+ * byte order. Otherwise return BEFS_ERR on error.
+ */
+static int
+befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
+		   befs_btree_super * sup)
+{
+	struct buffer_head *bh;
+	befs_disk_btree_super *od_sup;
+
+	befs_debug(sb, "---> %s", __func__);
+
+	bh = befs_read_datastream(sb, ds, 0, NULL);
+
+	if (!bh) {
+		befs_error(sb, "Couldn't read index header.");
+		goto error;
+	}
+	od_sup = (befs_disk_btree_super *) bh->b_data;
+	befs_dump_index_entry(sb, od_sup);
+
+	sup->magic = fs32_to_cpu(sb, od_sup->magic);
+	sup->node_size = fs32_to_cpu(sb, od_sup->node_size);
+	sup->max_depth = fs32_to_cpu(sb, od_sup->max_depth);
+	sup->data_type = fs32_to_cpu(sb, od_sup->data_type);
+	sup->root_node_ptr = fs64_to_cpu(sb, od_sup->root_node_ptr);
+
+	brelse(bh);
+	if (sup->magic != BEFS_BTREE_MAGIC) {
+		befs_error(sb, "Index header has bad magic.");
+		goto error;
+	}
+
+	befs_debug(sb, "<--- %s", __func__);
+	return BEFS_OK;
+
+      error:
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_ERR;
+}
+
+/**
+ * befs_bt_read_node - read in btree node and convert to cpu byteorder
+ * @sb: Filesystem superblock
+ * @ds: Datastream to read from
+ * @node: Buffer in which to place the btree node
+ * @node_off: Starting offset (in bytes) of the node in @ds
+ *
+ * Calls befs_read_datastream to read in the indicated btree node and
+ * makes sure its header fields are in cpu byteorder, byteswapping if
+ * necessary.
+ * Note: node->bh must be NULL when this function is called the first time.
+ * Don't forget brelse(node->bh) after last call.
+ *
+ * On success, returns BEFS_OK and *@node contains the btree node that
+ * starts at @node_off, with the node->head fields in cpu byte order.
+ *
+ * On failure, BEFS_ERR is returned.
+ */
+
+static int
+befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
+		  struct befs_btree_node *node, befs_off_t node_off)
+{
+	uint off = 0;
+
+	befs_debug(sb, "---> %s", __func__);
+
+	if (node->bh)
+		brelse(node->bh);
+
+	node->bh = befs_read_datastream(sb, ds, node_off, &off);
+	if (!node->bh) {
+		befs_error(sb, "%s failed to read "
+			   "node at %llu", __func__, node_off);
+		befs_debug(sb, "<--- %s ERROR", __func__);
+
+		return BEFS_ERR;
+	}
+	node->od_node =
+	    (befs_btree_nodehead *) ((void *) node->bh->b_data + off);
+
+	befs_dump_index_node(sb, node->od_node);
+
+	node->head.left = fs64_to_cpu(sb, node->od_node->left);
+	node->head.right = fs64_to_cpu(sb, node->od_node->right);
+	node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);
+	node->head.all_key_count =
+	    fs16_to_cpu(sb, node->od_node->all_key_count);
+	node->head.all_key_length =
+	    fs16_to_cpu(sb, node->od_node->all_key_length);
+
+	befs_debug(sb, "<--- %s", __func__);
+	return BEFS_OK;
+}
+
+/**
+ * befs_btree_find - Find a key in a befs B+tree
+ * @sb: Filesystem superblock
+ * @ds: Datastream containing btree
+ * @key: Key string to lookup in btree
+ * @value: Value stored with @key
+ *
+ * On success, returns BEFS_OK and sets *@value to the value stored
+ * with @key (usually the disk block number of an inode).
+ *
+ * On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND.
+ *
+ * Algorithm:
+ *   Read the superblock and rootnode of the b+tree.
+ *   Drill down through the interior nodes using befs_find_key().
+ *   Once at the correct leaf node, use befs_find_key() again to get the
+ *   actual value stored with the key.
+ */
+int
+befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
+		const char *key, befs_off_t * value)
+{
+	struct befs_btree_node *this_node;
+	befs_btree_super bt_super;
+	befs_off_t node_off;
+	int res;
+
+	befs_debug(sb, "---> %s Key: %s", __func__, key);
+
+	if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
+		befs_error(sb,
+			   "befs_btree_find() failed to read index superblock");
+		goto error;
+	}
+
+	this_node = kmalloc(sizeof(struct befs_btree_node),
+						GFP_NOFS);
+	if (!this_node) {
+		befs_error(sb, "befs_btree_find() failed to allocate %zu "
+			   "bytes of memory", sizeof(struct befs_btree_node));
+		goto error;
+	}
+
+	this_node->bh = NULL;
+
+	/* read in root node */
+	node_off = bt_super.root_node_ptr;
+	if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
+		befs_error(sb, "befs_btree_find() failed to read "
+			   "node at %llu", node_off);
+		goto error_alloc;
+	}
+
+	while (!befs_leafnode(this_node)) {
+		res = befs_find_key(sb, this_node, key, &node_off);
+		/* if no key set, try the overflow node */
+		if (res == BEFS_BT_OVERFLOW)
+			node_off = this_node->head.overflow;
+		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
+			befs_error(sb, "befs_btree_find() failed to read "
+				   "node at %llu", node_off);
+			goto error_alloc;
+		}
+	}
+
+	/* at a leaf node now, check if it is correct */
+	res = befs_find_key(sb, this_node, key, value);
+
+	brelse(this_node->bh);
+	kfree(this_node);
+
+	if (res != BEFS_BT_MATCH) {
+		befs_error(sb, "<--- %s Key %s not found", __func__, key);
+		befs_debug(sb, "<--- %s ERROR", __func__);
+		*value = 0;
+		return BEFS_BT_NOT_FOUND;
+	}
+	befs_debug(sb, "<--- %s Found key %s, value %llu", __func__,
+		   key, *value);
+	return BEFS_OK;
+
+      error_alloc:
+	kfree(this_node);
+      error:
+	*value = 0;
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_ERR;
+}
+
+/**
+ * befs_find_key - Search for a key within a node
+ * @sb: Filesystem superblock
+ * @node: Node to find the key within
+ * @findkey: Keystring to search for
+ * @value: If key is found, the value stored with the key is put here
+ *
+ * Finds exact match if one exists, and returns BEFS_BT_MATCH.
+ * If there is no match and node's value array is too small for key, return
+ * BEFS_BT_OVERFLOW.
+ * If no match and node should countain this key, return BEFS_BT_NOT_FOUND.
+ *
+ * Uses binary search instead of a linear.
+ */
+static int
+befs_find_key(struct super_block *sb, struct befs_btree_node *node,
+	      const char *findkey, befs_off_t * value)
+{
+	int first, last, mid;
+	int eq;
+	u16 keylen;
+	int findkey_len;
+	char *thiskey;
+	fs64 *valarray;
+
+	befs_debug(sb, "---> %s %s", __func__, findkey);
+
+	findkey_len = strlen(findkey);
+
+	/* if node can not contain key, just skip this node */
+	last = node->head.all_key_count - 1;
+	thiskey = befs_bt_get_key(sb, node, last, &keylen);
+
+	eq = befs_compare_strings(thiskey, keylen, findkey, findkey_len);
+	if (eq < 0) {
+		befs_debug(sb, "<--- node can't contain %s", findkey);
+		return BEFS_BT_OVERFLOW;
+	}
+
+	valarray = befs_bt_valarray(node);
+
+	/* simple binary search */
+	first = 0;
+	mid = 0;
+	while (last >= first) {
+		mid = (last + first) / 2;
+		befs_debug(sb, "first: %d, last: %d, mid: %d", first, last,
+			   mid);
+		thiskey = befs_bt_get_key(sb, node, mid, &keylen);
+		eq = befs_compare_strings(thiskey, keylen, findkey,
+					  findkey_len);
+
+		if (eq == 0) {
+			befs_debug(sb, "<--- %s found %s at %d",
+				   __func__, thiskey, mid);
+
+			*value = fs64_to_cpu(sb, valarray[mid]);
+			return BEFS_BT_MATCH;
+		}
+		if (eq > 0)
+			last = mid - 1;
+		else
+			first = mid + 1;
+	}
+
+	/* return an existing value so caller can arrive to a leaf node */
+	if (eq < 0)
+		*value = fs64_to_cpu(sb, valarray[mid + 1]);
+	else
+		*value = fs64_to_cpu(sb, valarray[mid]);
+	befs_error(sb, "<--- %s %s not found", __func__, findkey);
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_BT_NOT_FOUND;
+}
+
+/**
+ * befs_btree_read - Traverse leafnodes of a btree
+ * @sb: Filesystem superblock
+ * @ds: Datastream containing btree
+ * @key_no: Key number (alphabetical order) of key to read
+ * @bufsize: Size of the buffer to return key in
+ * @keybuf: Pointer to a buffer to put the key in
+ * @keysize: Length of the returned key
+ * @value: Value stored with the returned key
+ *
+ * Here's how it works: Key_no is the index of the key/value pair to
+ * return in keybuf/value.
+ * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is
+ * the number of characters in the key (just a convenience).
+ *
+ * Algorithm:
+ *   Get the first leafnode of the tree. See if the requested key is in that
+ *   node. If not, follow the node->right link to the next leafnode. Repeat
+ *   until the (key_no)th key is found or the tree is out of keys.
+ */
+int
+befs_btree_read(struct super_block *sb, const befs_data_stream *ds,
+		loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize,
+		befs_off_t * value)
+{
+	struct befs_btree_node *this_node;
+	befs_btree_super bt_super;
+	befs_off_t node_off;
+	int cur_key;
+	fs64 *valarray;
+	char *keystart;
+	u16 keylen;
+	int res;
+
+	uint key_sum = 0;
+
+	befs_debug(sb, "---> %s", __func__);
+
+	if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
+		befs_error(sb,
+			   "befs_btree_read() failed to read index superblock");
+		goto error;
+	}
+
+	this_node = kmalloc(sizeof(struct befs_btree_node), GFP_NOFS);
+	if (this_node == NULL) {
+		befs_error(sb, "befs_btree_read() failed to allocate %zu "
+			   "bytes of memory", sizeof(struct befs_btree_node));
+		goto error;
+	}
+
+	node_off = bt_super.root_node_ptr;
+	this_node->bh = NULL;
+
+	/* seeks down to first leafnode, reads it into this_node */
+	res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);
+	if (res == BEFS_BT_EMPTY) {
+		brelse(this_node->bh);
+		kfree(this_node);
+		*value = 0;
+		*keysize = 0;
+		befs_debug(sb, "<--- %s Tree is EMPTY", __func__);
+		return BEFS_BT_EMPTY;
+	} else if (res == BEFS_ERR) {
+		goto error_alloc;
+	}
+
+	/* find the leaf node containing the key_no key */
+
+	while (key_sum + this_node->head.all_key_count <= key_no) {
+
+		/* no more nodes to look in: key_no is too large */
+		if (this_node->head.right == BEFS_BT_INVAL) {
+			*keysize = 0;
+			*value = 0;
+			befs_debug(sb,
+				   "<--- %s END of keys at %llu", __func__,
+				   (unsigned long long)
+				   key_sum + this_node->head.all_key_count);
+			brelse(this_node->bh);
+			kfree(this_node);
+			return BEFS_BT_END;
+		}
+
+		key_sum += this_node->head.all_key_count;
+		node_off = this_node->head.right;
+
+		if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
+			befs_error(sb, "%s failed to read node at %llu",
+				  __func__, (unsigned long long)node_off);
+			goto error_alloc;
+		}
+	}
+
+	/* how many keys into this_node is key_no */
+	cur_key = key_no - key_sum;
+
+	/* get pointers to datastructures within the node body */
+	valarray = befs_bt_valarray(this_node);
+
+	keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);
+
+	befs_debug(sb, "Read [%llu,%d]: keysize %d",
+		   (long long unsigned int)node_off, (int)cur_key,
+		   (int)keylen);
+
+	if (bufsize < keylen + 1) {
+		befs_error(sb, "%s keybuf too small (%zu) "
+			   "for key of size %d", __func__, bufsize, keylen);
+		brelse(this_node->bh);
+		goto error_alloc;
+	}
+
+	strlcpy(keybuf, keystart, keylen + 1);
+	*value = fs64_to_cpu(sb, valarray[cur_key]);
+	*keysize = keylen;
+
+	befs_debug(sb, "Read [%llu,%d]: Key \"%.*s\", Value %llu", node_off,
+		   cur_key, keylen, keybuf, *value);
+
+	brelse(this_node->bh);
+	kfree(this_node);
+
+	befs_debug(sb, "<--- %s", __func__);
+
+	return BEFS_OK;
+
+      error_alloc:
+	kfree(this_node);
+
+      error:
+	*keysize = 0;
+	*value = 0;
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_ERR;
+}
+
+/**
+ * befs_btree_seekleaf - Find the first leafnode in the btree
+ * @sb: Filesystem superblock
+ * @ds: Datastream containing btree
+ * @bt_super: Pointer to the superblock of the btree
+ * @this_node: Buffer to return the leafnode in
+ * @node_off: Pointer to offset of current node within datastream. Modified
+ * 		by the function.
+ *
+ * Helper function for btree traverse. Moves the current position to the
+ * start of the first leaf node.
+ *
+ * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY.
+ */
+static int
+befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
+		    befs_btree_super *bt_super,
+		    struct befs_btree_node *this_node,
+		    befs_off_t * node_off)
+{
+
+	befs_debug(sb, "---> %s", __func__);
+
+	if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
+		befs_error(sb, "%s failed to read "
+			   "node at %llu", __func__, *node_off);
+		goto error;
+	}
+	befs_debug(sb, "Seekleaf to root node %llu", *node_off);
+
+	if (this_node->head.all_key_count == 0 && befs_leafnode(this_node)) {
+		befs_debug(sb, "<--- %s Tree is EMPTY", __func__);
+		return BEFS_BT_EMPTY;
+	}
+
+	while (!befs_leafnode(this_node)) {
+
+		if (this_node->head.all_key_count == 0) {
+			befs_debug(sb, "%s encountered "
+				   "an empty interior node: %llu. Using Overflow "
+				   "node: %llu", __func__, *node_off,
+				   this_node->head.overflow);
+			*node_off = this_node->head.overflow;
+		} else {
+			fs64 *valarray = befs_bt_valarray(this_node);
+			*node_off = fs64_to_cpu(sb, valarray[0]);
+		}
+		if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
+			befs_error(sb, "%s failed to read "
+				   "node at %llu", __func__, *node_off);
+			goto error;
+		}
+
+		befs_debug(sb, "Seekleaf to child node %llu", *node_off);
+	}
+	befs_debug(sb, "Node %llu is a leaf node", *node_off);
+
+	return BEFS_OK;
+
+      error:
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_ERR;
+}
+
+/**
+ * befs_leafnode - Determine if the btree node is a leaf node or an
+ * interior node
+ * @node: Pointer to node structure to test
+ *
+ * Return 1 if leaf, 0 if interior
+ */
+static int
+befs_leafnode(struct befs_btree_node *node)
+{
+	/* all interior nodes (and only interior nodes) have an overflow node */
+	if (node->head.overflow == BEFS_BT_INVAL)
+		return 1;
+	else
+		return 0;
+}
+
+/**
+ * befs_bt_keylen_index - Finds start of keylen index in a node
+ * @node: Pointer to the node structure to find the keylen index within
+ *
+ * Returns a pointer to the start of the key length index array
+ * of the B+tree node *@node
+ *
+ * "The length of all the keys in the node is added to the size of the
+ * header and then rounded up to a multiple of four to get the beginning
+ * of the key length index" (p.88, practical filesystem design).
+ *
+ * Except that rounding up to 8 works, and rounding up to 4 doesn't.
+ */
+static fs16 *
+befs_bt_keylen_index(struct befs_btree_node *node)
+{
+	const int keylen_align = 8;
+	unsigned long int off =
+	    (sizeof (befs_btree_nodehead) + node->head.all_key_length);
+	ulong tmp = off % keylen_align;
+
+	if (tmp)
+		off += keylen_align - tmp;
+
+	return (fs16 *) ((void *) node->od_node + off);
+}
+
+/**
+ * befs_bt_valarray - Finds the start of value array in a node
+ * @node: Pointer to the node structure to find the value array within
+ *
+ * Returns a pointer to the start of the value array
+ * of the node pointed to by the node header
+ */
+static fs64 *
+befs_bt_valarray(struct befs_btree_node *node)
+{
+	void *keylen_index_start = (void *) befs_bt_keylen_index(node);
+	size_t keylen_index_size = node->head.all_key_count * sizeof (fs16);
+
+	return (fs64 *) (keylen_index_start + keylen_index_size);
+}
+
+/**
+ * befs_bt_keydata - Finds start of keydata array in a node
+ * @node: Pointer to the node structure to find the keydata array within
+ *
+ * Returns a pointer to the start of the keydata array
+ * of the node pointed to by the node header
+ */
+static char *
+befs_bt_keydata(struct befs_btree_node *node)
+{
+	return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead));
+}
+
+/**
+ * befs_bt_get_key - returns a pointer to the start of a key
+ * @sb: filesystem superblock
+ * @node: node in which to look for the key
+ * @index: the index of the key to get
+ * @keylen: modified to be the length of the key at @index
+ *
+ * Returns a valid pointer into @node on success.
+ * Returns NULL on failure (bad input) and sets *@keylen = 0
+ */
+static char *
+befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
+		int index, u16 * keylen)
+{
+	int prev_key_end;
+	char *keystart;
+	fs16 *keylen_index;
+
+	if (index < 0 || index > node->head.all_key_count) {
+		*keylen = 0;
+		return NULL;
+	}
+
+	keystart = befs_bt_keydata(node);
+	keylen_index = befs_bt_keylen_index(node);
+
+	if (index == 0)
+		prev_key_end = 0;
+	else
+		prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);
+
+	*keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;
+
+	return keystart + prev_key_end;
+}
+
+/**
+ * befs_compare_strings - compare two strings
+ * @key1: pointer to the first key to be compared
+ * @keylen1: length in bytes of key1
+ * @key2: pointer to the second key to be compared
+ * @keylen2: length in bytes of key2
+ *
+ * Returns 0 if @key1 and @key2 are equal.
+ * Returns >0 if @key1 is greater.
+ * Returns <0 if @key2 is greater.
+ */
+static int
+befs_compare_strings(const void *key1, int keylen1,
+		     const void *key2, int keylen2)
+{
+	int len = min_t(int, keylen1, keylen2);
+	int result = strncmp(key1, key2, len);
+	if (result == 0)
+		result = keylen1 - keylen2;
+	return result;
+}
+
+/* These will be used for non-string keyed btrees */
+#if 0
+static int
+btree_compare_int32(cont void *key1, int keylen1, const void *key2, int keylen2)
+{
+	return *(int32_t *) key1 - *(int32_t *) key2;
+}
+
+static int
+btree_compare_uint32(cont void *key1, int keylen1,
+		     const void *key2, int keylen2)
+{
+	if (*(u_int32_t *) key1 == *(u_int32_t *) key2)
+		return 0;
+	else if (*(u_int32_t *) key1 > *(u_int32_t *) key2)
+		return 1;
+
+	return -1;
+}
+static int
+btree_compare_int64(cont void *key1, int keylen1, const void *key2, int keylen2)
+{
+	if (*(int64_t *) key1 == *(int64_t *) key2)
+		return 0;
+	else if (*(int64_t *) key1 > *(int64_t *) key2)
+		return 1;
+
+	return -1;
+}
+
+static int
+btree_compare_uint64(cont void *key1, int keylen1,
+		     const void *key2, int keylen2)
+{
+	if (*(u_int64_t *) key1 == *(u_int64_t *) key2)
+		return 0;
+	else if (*(u_int64_t *) key1 > *(u_int64_t *) key2)
+		return 1;
+
+	return -1;
+}
+
+static int
+btree_compare_float(cont void *key1, int keylen1, const void *key2, int keylen2)
+{
+	float result = *(float *) key1 - *(float *) key2;
+	if (result == 0.0f)
+		return 0;
+
+	return (result < 0.0f) ? -1 : 1;
+}
+
+static int
+btree_compare_double(cont void *key1, int keylen1,
+		     const void *key2, int keylen2)
+{
+	double result = *(double *) key1 - *(double *) key2;
+	if (result == 0.0)
+		return 0;
+
+	return (result < 0.0) ? -1 : 1;
+}
+#endif				//0
diff --git a/fs/befs/btree.h b/fs/befs/btree.h
new file mode 100644
index 000000000..a253a6276
--- /dev/null
+++ b/fs/befs/btree.h
@@ -0,0 +1,12 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * btree.h
+ *
+ */
+
+int befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
+		    const char *key, befs_off_t *value);
+
+int befs_btree_read(struct super_block *sb, const befs_data_stream *ds,
+		    loff_t key_no, size_t bufsize, char *keybuf,
+		    size_t *keysize, befs_off_t *value);
diff --git a/fs/befs/datastream.c b/fs/befs/datastream.c
new file mode 100644
index 000000000..97719a7c7
--- /dev/null
+++ b/fs/befs/datastream.c
@@ -0,0 +1,525 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * linux/fs/befs/datastream.c
+ *
+ * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
+ *
+ * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
+ *
+ * Many thanks to Dominic Giampaolo, author of "Practical File System
+ * Design with the Be File System", for such a helpful book.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/buffer_head.h>
+#include <linux/string.h>
+
+#include "befs.h"
+#include "datastream.h"
+#include "io.h"
+
+const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
+
+static int befs_find_brun_direct(struct super_block *sb,
+				 const befs_data_stream *data,
+				 befs_blocknr_t blockno, befs_block_run *run);
+
+static int befs_find_brun_indirect(struct super_block *sb,
+				   const befs_data_stream *data,
+				   befs_blocknr_t blockno,
+				   befs_block_run *run);
+
+static int befs_find_brun_dblindirect(struct super_block *sb,
+				      const befs_data_stream *data,
+				      befs_blocknr_t blockno,
+				      befs_block_run *run);
+
+/**
+ * befs_read_datastream - get buffer_head containing data, starting from pos.
+ * @sb: Filesystem superblock
+ * @ds: datastream to find data with
+ * @pos: start of data
+ * @off: offset of data in buffer_head->b_data
+ *
+ * Returns pointer to buffer_head containing data starting with offset @off,
+ * if you don't need to know offset just set @off = NULL.
+ */
+struct buffer_head *
+befs_read_datastream(struct super_block *sb, const befs_data_stream *ds,
+		     befs_off_t pos, uint *off)
+{
+	struct buffer_head *bh;
+	befs_block_run run;
+	befs_blocknr_t block;	/* block coresponding to pos */
+
+	befs_debug(sb, "---> %s %llu", __func__, pos);
+	block = pos >> BEFS_SB(sb)->block_shift;
+	if (off)
+		*off = pos - (block << BEFS_SB(sb)->block_shift);
+
+	if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
+		befs_error(sb, "BeFS: Error finding disk addr of block %lu",
+			   (unsigned long)block);
+		befs_debug(sb, "<--- %s ERROR", __func__);
+		return NULL;
+	}
+	bh = befs_bread_iaddr(sb, run);
+	if (!bh) {
+		befs_error(sb, "BeFS: Error reading block %lu from datastream",
+			   (unsigned long)block);
+		return NULL;
+	}
+
+	befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
+
+	return bh;
+}
+
+/**
+ * befs_fblock2brun - give back block run for fblock
+ * @sb: the superblock
+ * @data: datastream to read from
+ * @fblock: the blocknumber with the file position to find
+ * @run: The found run is passed back through this pointer
+ *
+ * Takes a file position and gives back a brun who's starting block
+ * is block number fblock of the file.
+ *
+ * Returns BEFS_OK or BEFS_ERR.
+ *
+ * Calls specialized functions for each of the three possible
+ * datastream regions.
+ */
+int
+befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
+		 befs_blocknr_t fblock, befs_block_run *run)
+{
+	int err;
+	befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
+
+	if (pos < data->max_direct_range) {
+		err = befs_find_brun_direct(sb, data, fblock, run);
+
+	} else if (pos < data->max_indirect_range) {
+		err = befs_find_brun_indirect(sb, data, fblock, run);
+
+	} else if (pos < data->max_double_indirect_range) {
+		err = befs_find_brun_dblindirect(sb, data, fblock, run);
+
+	} else {
+		befs_error(sb,
+			   "befs_fblock2brun() was asked to find block %lu, "
+			   "which is not mapped by the datastream\n",
+			   (unsigned long)fblock);
+		err = BEFS_ERR;
+	}
+	return err;
+}
+
+/**
+ * befs_read_lsmylink - read long symlink from datastream.
+ * @sb: Filesystem superblock
+ * @ds: Datastream to read from
+ * @buff: Buffer in which to place long symlink data
+ * @len: Length of the long symlink in bytes
+ *
+ * Returns the number of bytes read
+ */
+size_t
+befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds,
+		   void *buff, befs_off_t len)
+{
+	befs_off_t bytes_read = 0;	/* bytes readed */
+	u16 plen;
+	struct buffer_head *bh;
+
+	befs_debug(sb, "---> %s length: %llu", __func__, len);
+
+	while (bytes_read < len) {
+		bh = befs_read_datastream(sb, ds, bytes_read, NULL);
+		if (!bh) {
+			befs_error(sb, "BeFS: Error reading datastream block "
+				   "starting from %llu", bytes_read);
+			befs_debug(sb, "<--- %s ERROR", __func__);
+			return bytes_read;
+
+		}
+		plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
+		    BEFS_SB(sb)->block_size : len - bytes_read;
+		memcpy(buff + bytes_read, bh->b_data, plen);
+		brelse(bh);
+		bytes_read += plen;
+	}
+
+	befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int)
+		   bytes_read);
+	return bytes_read;
+}
+
+/**
+ * befs_count_blocks - blocks used by a file
+ * @sb: Filesystem superblock
+ * @ds: Datastream of the file
+ *
+ * Counts the number of fs blocks that the file represented by
+ * inode occupies on the filesystem, counting both regular file
+ * data and filesystem metadata (and eventually attribute data
+ * when we support attributes)
+*/
+
+befs_blocknr_t
+befs_count_blocks(struct super_block *sb, const befs_data_stream *ds)
+{
+	befs_blocknr_t blocks;
+	befs_blocknr_t datablocks;	/* File data blocks */
+	befs_blocknr_t metablocks;	/* FS metadata blocks */
+	struct befs_sb_info *befs_sb = BEFS_SB(sb);
+
+	befs_debug(sb, "---> %s", __func__);
+
+	datablocks = ds->size >> befs_sb->block_shift;
+	if (ds->size & (befs_sb->block_size - 1))
+		datablocks += 1;
+
+	metablocks = 1;		/* Start with 1 block for inode */
+
+	/* Size of indirect block */
+	if (ds->size > ds->max_direct_range)
+		metablocks += ds->indirect.len;
+
+	/*
+	 * Double indir block, plus all the indirect blocks it maps.
+	 * In the double-indirect range, all block runs of data are
+	 * BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
+	 * how many data block runs are in the double-indirect region,
+	 * and from that we know how many indirect blocks it takes to
+	 * map them. We assume that the indirect blocks are also
+	 * BEFS_DBLINDIR_BRUN_LEN blocks long.
+	 */
+	if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
+		uint dbl_bytes;
+		uint dbl_bruns;
+		uint indirblocks;
+
+		dbl_bytes =
+		    ds->max_double_indirect_range - ds->max_indirect_range;
+		dbl_bruns =
+		    dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
+		indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
+
+		metablocks += ds->double_indirect.len;
+		metablocks += indirblocks;
+	}
+
+	blocks = datablocks + metablocks;
+	befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks);
+
+	return blocks;
+}
+
+/**
+ * befs_find_brun_direct - find a direct block run in the datastream
+ * @sb: the superblock
+ * @data: the datastream
+ * @blockno: the blocknumber to find
+ * @run: The found run is passed back through this pointer
+ *
+ * Finds the block run that starts at file block number blockno
+ * in the file represented by the datastream data, if that
+ * blockno is in the direct region of the datastream.
+ *
+ * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
+ * otherwise.
+ *
+ * Algorithm:
+ * Linear search. Checks each element of array[] to see if it
+ * contains the blockno-th filesystem block. This is necessary
+ * because the block runs map variable amounts of data. Simply
+ * keeps a count of the number of blocks searched so far (sum),
+ * incrementing this by the length of each block run as we come
+ * across it. Adds sum to *count before returning (this is so
+ * you can search multiple arrays that are logicaly one array,
+ * as in the indirect region code).
+ *
+ * When/if blockno is found, if blockno is inside of a block
+ * run as stored on disk, we offset the start and length members
+ * of the block run, so that blockno is the start and len is
+ * still valid (the run ends in the same place).
+ */
+static int
+befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data,
+		      befs_blocknr_t blockno, befs_block_run *run)
+{
+	int i;
+	const befs_block_run *array = data->direct;
+	befs_blocknr_t sum;
+
+	befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
+
+	for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
+	     sum += array[i].len, i++) {
+		if (blockno >= sum && blockno < sum + (array[i].len)) {
+			int offset = blockno - sum;
+
+			run->allocation_group = array[i].allocation_group;
+			run->start = array[i].start + offset;
+			run->len = array[i].len - offset;
+
+			befs_debug(sb, "---> %s, "
+				   "found %lu at direct[%d]", __func__,
+				   (unsigned long)blockno, i);
+			return BEFS_OK;
+		}
+	}
+
+	befs_error(sb, "%s failed to find file block %lu", __func__,
+		   (unsigned long)blockno);
+	befs_debug(sb, "---> %s ERROR", __func__);
+	return BEFS_ERR;
+}
+
+/**
+ * befs_find_brun_indirect - find a block run in the datastream
+ * @sb: the superblock
+ * @data: the datastream
+ * @blockno: the blocknumber to find
+ * @run: The found run is passed back through this pointer
+ *
+ * Finds the block run that starts at file block number blockno
+ * in the file represented by the datastream data, if that
+ * blockno is in the indirect region of the datastream.
+ *
+ * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
+ * otherwise.
+ *
+ * Algorithm:
+ * For each block in the indirect run of the datastream, read
+ * it in and search through it for search_blk.
+ *
+ * XXX:
+ * Really should check to make sure blockno is inside indirect
+ * region.
+ */
+static int
+befs_find_brun_indirect(struct super_block *sb,
+			const befs_data_stream *data,
+			befs_blocknr_t blockno,
+			befs_block_run *run)
+{
+	int i, j;
+	befs_blocknr_t sum = 0;
+	befs_blocknr_t indir_start_blk;
+	befs_blocknr_t search_blk;
+	struct buffer_head *indirblock;
+	befs_disk_block_run *array;
+
+	befs_block_run indirect = data->indirect;
+	befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
+	int arraylen = befs_iaddrs_per_block(sb);
+
+	befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
+
+	indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
+	search_blk = blockno - indir_start_blk;
+
+	/* Examine blocks of the indirect run one at a time */
+	for (i = 0; i < indirect.len; i++) {
+		indirblock = sb_bread(sb, indirblockno + i);
+		if (indirblock == NULL) {
+			befs_error(sb, "---> %s failed to read "
+				   "disk block %lu from the indirect brun",
+				   __func__, (unsigned long)indirblockno + i);
+			befs_debug(sb, "<--- %s ERROR", __func__);
+			return BEFS_ERR;
+		}
+
+		array = (befs_disk_block_run *) indirblock->b_data;
+
+		for (j = 0; j < arraylen; ++j) {
+			int len = fs16_to_cpu(sb, array[j].len);
+
+			if (search_blk >= sum && search_blk < sum + len) {
+				int offset = search_blk - sum;
+				run->allocation_group =
+				    fs32_to_cpu(sb, array[j].allocation_group);
+				run->start =
+				    fs16_to_cpu(sb, array[j].start) + offset;
+				run->len =
+				    fs16_to_cpu(sb, array[j].len) - offset;
+
+				brelse(indirblock);
+				befs_debug(sb,
+					   "<--- %s found file block "
+					   "%lu at indirect[%d]", __func__,
+					   (unsigned long)blockno,
+					   j + (i * arraylen));
+				return BEFS_OK;
+			}
+			sum += len;
+		}
+
+		brelse(indirblock);
+	}
+
+	/* Only fallthrough is an error */
+	befs_error(sb, "BeFS: %s failed to find "
+		   "file block %lu", __func__, (unsigned long)blockno);
+
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return BEFS_ERR;
+}
+
+/**
+ * befs_find_brun_dblindirect - find a block run in the datastream
+ * @sb: the superblock
+ * @data: the datastream
+ * @blockno: the blocknumber to find
+ * @run: The found run is passed back through this pointer
+ *
+ * Finds the block run that starts at file block number blockno
+ * in the file represented by the datastream data, if that
+ * blockno is in the double-indirect region of the datastream.
+ *
+ * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
+ * otherwise.
+ *
+ * Algorithm:
+ * The block runs in the double-indirect region are different.
+ * They are always allocated 4 fs blocks at a time, so each
+ * block run maps a constant amount of file data. This means
+ * that we can directly calculate how many block runs into the
+ * double-indirect region we need to go to get to the one that
+ * maps a particular filesystem block.
+ *
+ * We do this in two stages. First we calculate which of the
+ * inode addresses in the double-indirect block will point us
+ * to the indirect block that contains the mapping for the data,
+ * then we calculate which of the inode addresses in that
+ * indirect block maps the data block we are after.
+ *
+ * Oh, and once we've done that, we actually read in the blocks
+ * that contain the inode addresses we calculated above. Even
+ * though the double-indirect run may be several blocks long,
+ * we can calculate which of those blocks will contain the index
+ * we are after and only read that one. We then follow it to
+ * the indirect block and perform a similar process to find
+ * the actual block run that maps the data block we are interested
+ * in.
+ *
+ * Then we offset the run as in befs_find_brun_array() and we are
+ * done.
+ */
+static int
+befs_find_brun_dblindirect(struct super_block *sb,
+			   const befs_data_stream *data,
+			   befs_blocknr_t blockno,
+			   befs_block_run *run)
+{
+	int dblindir_indx;
+	int indir_indx;
+	int offset;
+	int dbl_which_block;
+	int which_block;
+	int dbl_block_indx;
+	int block_indx;
+	off_t dblindir_leftover;
+	befs_blocknr_t blockno_at_run_start;
+	struct buffer_head *dbl_indir_block;
+	struct buffer_head *indir_block;
+	befs_block_run indir_run;
+	befs_disk_inode_addr *iaddr_array;
+
+	befs_blocknr_t indir_start_blk =
+	    data->max_indirect_range >> BEFS_SB(sb)->block_shift;
+
+	off_t dbl_indir_off = blockno - indir_start_blk;
+
+	/* number of data blocks mapped by each of the iaddrs in
+	 * the indirect block pointed to by the double indirect block
+	 */
+	size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
+
+	/* number of data blocks mapped by each of the iaddrs in
+	 * the double indirect block
+	 */
+	size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
+	    * BEFS_DBLINDIR_BRUN_LEN;
+
+	befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno);
+
+	/* First, discover which of the double_indir->indir blocks
+	 * contains pos. Then figure out how much of pos that
+	 * accounted for. Then discover which of the iaddrs in
+	 * the indirect block contains pos.
+	 */
+
+	dblindir_indx = dbl_indir_off / diblklen;
+	dblindir_leftover = dbl_indir_off % diblklen;
+	indir_indx = dblindir_leftover / diblklen;
+
+	/* Read double indirect block */
+	dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
+	if (dbl_which_block > data->double_indirect.len) {
+		befs_error(sb, "The double-indirect index calculated by "
+			   "%s, %d, is outside the range "
+			   "of the double-indirect block", __func__,
+			   dblindir_indx);
+		return BEFS_ERR;
+	}
+
+	dbl_indir_block =
+	    sb_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
+					dbl_which_block);
+	if (dbl_indir_block == NULL) {
+		befs_error(sb, "%s couldn't read the "
+			   "double-indirect block at blockno %lu", __func__,
+			   (unsigned long)
+			   iaddr2blockno(sb, &data->double_indirect) +
+			   dbl_which_block);
+		return BEFS_ERR;
+	}
+
+	dbl_block_indx =
+	    dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
+	iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
+	indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
+	brelse(dbl_indir_block);
+
+	/* Read indirect block */
+	which_block = indir_indx / befs_iaddrs_per_block(sb);
+	if (which_block > indir_run.len) {
+		befs_error(sb, "The indirect index calculated by "
+			   "%s, %d, is outside the range "
+			   "of the indirect block", __func__, indir_indx);
+		return BEFS_ERR;
+	}
+
+	indir_block =
+	    sb_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
+	if (indir_block == NULL) {
+		befs_error(sb, "%s couldn't read the indirect block "
+			   "at blockno %lu", __func__, (unsigned long)
+			   iaddr2blockno(sb, &indir_run) + which_block);
+		return BEFS_ERR;
+	}
+
+	block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
+	iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
+	*run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
+	brelse(indir_block);
+
+	blockno_at_run_start = indir_start_blk;
+	blockno_at_run_start += diblklen * dblindir_indx;
+	blockno_at_run_start += iblklen * indir_indx;
+	offset = blockno - blockno_at_run_start;
+
+	run->start += offset;
+	run->len -= offset;
+
+	befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
+		   " double_indirect_leftover = %lu", (unsigned long)
+		   blockno, dblindir_indx, indir_indx, dblindir_leftover);
+
+	return BEFS_OK;
+}
diff --git a/fs/befs/datastream.h b/fs/befs/datastream.h
new file mode 100644
index 000000000..39b1d4766
--- /dev/null
+++ b/fs/befs/datastream.h
@@ -0,0 +1,20 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * datastream.h
+ *
+ */
+
+struct buffer_head *befs_read_datastream(struct super_block *sb,
+					 const befs_data_stream *ds,
+					 befs_off_t pos, uint *off);
+
+int befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
+		     befs_blocknr_t fblock, befs_block_run *run);
+
+size_t befs_read_lsymlink(struct super_block *sb, const befs_data_stream *data,
+			  void *buff, befs_off_t len);
+
+befs_blocknr_t befs_count_blocks(struct super_block *sb,
+			  const befs_data_stream *ds);
+
+extern const befs_inode_addr BAD_IADDR;
diff --git a/fs/befs/debug.c b/fs/befs/debug.c
new file mode 100644
index 000000000..eb7bd6c69
--- /dev/null
+++ b/fs/befs/debug.c
@@ -0,0 +1,262 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ *  linux/fs/befs/debug.c
+ *
+ * Copyright (C) 2001 Will Dyson (will_dyson at pobox.com)
+ *
+ * With help from the ntfs-tng driver by Anton Altparmakov
+ *
+ * Copyright (C) 1999  Makoto Kato (m_kato@ga2.so-net.ne.jp)
+ *
+ * debug functions
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#ifdef __KERNEL__
+
+#include <stdarg.h>
+#include <linux/string.h>
+#include <linux/spinlock.h>
+#include <linux/kernel.h>
+#include <linux/fs.h>
+#include <linux/slab.h>
+
+#endif				/* __KERNEL__ */
+
+#include "befs.h"
+
+void
+befs_error(const struct super_block *sb, const char *fmt, ...)
+{
+	struct va_format vaf;
+	va_list args;
+
+	va_start(args, fmt);
+	vaf.fmt = fmt;
+	vaf.va = &args;
+	pr_err("(%s): %pV\n", sb->s_id, &vaf);
+	va_end(args);
+}
+
+void
+befs_warning(const struct super_block *sb, const char *fmt, ...)
+{
+	struct va_format vaf;
+	va_list args;
+
+	va_start(args, fmt);
+	vaf.fmt = fmt;
+	vaf.va = &args;
+	pr_warn("(%s): %pV\n", sb->s_id, &vaf);
+	va_end(args);
+}
+
+void
+befs_debug(const struct super_block *sb, const char *fmt, ...)
+{
+#ifdef CONFIG_BEFS_DEBUG
+
+	struct va_format vaf;
+	va_list args;
+
+	va_start(args, fmt);
+	vaf.fmt = fmt;
+	vaf.va = &args;
+	pr_debug("(%s): %pV\n", sb->s_id, &vaf);
+	va_end(args);
+
+#endif				//CONFIG_BEFS_DEBUG
+}
+
+void
+befs_dump_inode(const struct super_block *sb, befs_inode *inode)
+{
+#ifdef CONFIG_BEFS_DEBUG
+
+	befs_block_run tmp_run;
+
+	befs_debug(sb, "befs_inode information");
+
+	befs_debug(sb, "  magic1 %08x", fs32_to_cpu(sb, inode->magic1));
+
+	tmp_run = fsrun_to_cpu(sb, inode->inode_num);
+	befs_debug(sb, "  inode_num %u, %hu, %hu",
+		   tmp_run.allocation_group, tmp_run.start, tmp_run.len);
+
+	befs_debug(sb, "  uid %u", fs32_to_cpu(sb, inode->uid));
+	befs_debug(sb, "  gid %u", fs32_to_cpu(sb, inode->gid));
+	befs_debug(sb, "  mode %08x", fs32_to_cpu(sb, inode->mode));
+	befs_debug(sb, "  flags %08x", fs32_to_cpu(sb, inode->flags));
+	befs_debug(sb, "  create_time %llu",
+		   fs64_to_cpu(sb, inode->create_time));
+	befs_debug(sb, "  last_modified_time %llu",
+		   fs64_to_cpu(sb, inode->last_modified_time));
+
+	tmp_run = fsrun_to_cpu(sb, inode->parent);
+	befs_debug(sb, "  parent [%u, %hu, %hu]",
+		   tmp_run.allocation_group, tmp_run.start, tmp_run.len);
+
+	tmp_run = fsrun_to_cpu(sb, inode->attributes);
+	befs_debug(sb, "  attributes [%u, %hu, %hu]",
+		   tmp_run.allocation_group, tmp_run.start, tmp_run.len);
+
+	befs_debug(sb, "  type %08x", fs32_to_cpu(sb, inode->type));
+	befs_debug(sb, "  inode_size %u", fs32_to_cpu(sb, inode->inode_size));
+
+	if (S_ISLNK(fs32_to_cpu(sb, inode->mode))) {
+		befs_debug(sb, "  Symbolic link [%s]", inode->data.symlink);
+	} else {
+		int i;
+
+		for (i = 0; i < BEFS_NUM_DIRECT_BLOCKS; i++) {
+			tmp_run =
+			    fsrun_to_cpu(sb, inode->data.datastream.direct[i]);
+			befs_debug(sb, "  direct %d [%u, %hu, %hu]", i,
+				   tmp_run.allocation_group, tmp_run.start,
+				   tmp_run.len);
+		}
+		befs_debug(sb, "  max_direct_range %llu",
+			   fs64_to_cpu(sb,
+				       inode->data.datastream.
+				       max_direct_range));
+
+		tmp_run = fsrun_to_cpu(sb, inode->data.datastream.indirect);
+		befs_debug(sb, "  indirect [%u, %hu, %hu]",
+			   tmp_run.allocation_group,
+			   tmp_run.start, tmp_run.len);
+
+		befs_debug(sb, "  max_indirect_range %llu",
+			   fs64_to_cpu(sb,
+				       inode->data.datastream.
+				       max_indirect_range));
+
+		tmp_run =
+		    fsrun_to_cpu(sb, inode->data.datastream.double_indirect);
+		befs_debug(sb, "  double indirect [%u, %hu, %hu]",
+			   tmp_run.allocation_group, tmp_run.start,
+			   tmp_run.len);
+
+		befs_debug(sb, "  max_double_indirect_range %llu",
+			   fs64_to_cpu(sb,
+				       inode->data.datastream.
+				       max_double_indirect_range));
+
+		befs_debug(sb, "  size %llu",
+			   fs64_to_cpu(sb, inode->data.datastream.size));
+	}
+
+#endif				//CONFIG_BEFS_DEBUG
+}
+
+/*
+ * Display super block structure for debug.
+ */
+
+void
+befs_dump_super_block(const struct super_block *sb, befs_super_block *sup)
+{
+#ifdef CONFIG_BEFS_DEBUG
+
+	befs_block_run tmp_run;
+
+	befs_debug(sb, "befs_super_block information");
+
+	befs_debug(sb, "  name %s", sup->name);
+	befs_debug(sb, "  magic1 %08x", fs32_to_cpu(sb, sup->magic1));
+	befs_debug(sb, "  fs_byte_order %08x",
+		   fs32_to_cpu(sb, sup->fs_byte_order));
+
+	befs_debug(sb, "  block_size %u", fs32_to_cpu(sb, sup->block_size));
+	befs_debug(sb, "  block_shift %u", fs32_to_cpu(sb, sup->block_shift));
+
+	befs_debug(sb, "  num_blocks %llu", fs64_to_cpu(sb, sup->num_blocks));
+	befs_debug(sb, "  used_blocks %llu", fs64_to_cpu(sb, sup->used_blocks));
+	befs_debug(sb, "  inode_size %u", fs32_to_cpu(sb, sup->inode_size));
+
+	befs_debug(sb, "  magic2 %08x", fs32_to_cpu(sb, sup->magic2));
+	befs_debug(sb, "  blocks_per_ag %u",
+		   fs32_to_cpu(sb, sup->blocks_per_ag));
+	befs_debug(sb, "  ag_shift %u", fs32_to_cpu(sb, sup->ag_shift));
+	befs_debug(sb, "  num_ags %u", fs32_to_cpu(sb, sup->num_ags));
+
+	befs_debug(sb, "  flags %08x", fs32_to_cpu(sb, sup->flags));
+
+	tmp_run = fsrun_to_cpu(sb, sup->log_blocks);
+	befs_debug(sb, "  log_blocks %u, %hu, %hu",
+		   tmp_run.allocation_group, tmp_run.start, tmp_run.len);
+
+	befs_debug(sb, "  log_start %lld", fs64_to_cpu(sb, sup->log_start));
+	befs_debug(sb, "  log_end %lld", fs64_to_cpu(sb, sup->log_end));
+
+	befs_debug(sb, "  magic3 %08x", fs32_to_cpu(sb, sup->magic3));
+
+	tmp_run = fsrun_to_cpu(sb, sup->root_dir);
+	befs_debug(sb, "  root_dir %u, %hu, %hu",
+		   tmp_run.allocation_group, tmp_run.start, tmp_run.len);
+
+	tmp_run = fsrun_to_cpu(sb, sup->indices);
+	befs_debug(sb, "  indices %u, %hu, %hu",
+		   tmp_run.allocation_group, tmp_run.start, tmp_run.len);
+
+#endif				//CONFIG_BEFS_DEBUG
+}
+
+#if 0
+/* unused */
+void
+befs_dump_small_data(const struct super_block *sb, befs_small_data *sd)
+{
+}
+
+/* unused */
+void
+befs_dump_run(const struct super_block *sb, befs_disk_block_run run)
+{
+#ifdef CONFIG_BEFS_DEBUG
+
+	befs_block_run n = fsrun_to_cpu(sb, run);
+
+	befs_debug(sb, "[%u, %hu, %hu]", n.allocation_group, n.start, n.len);
+
+#endif				//CONFIG_BEFS_DEBUG
+}
+#endif  /*  0  */
+
+void
+befs_dump_index_entry(const struct super_block *sb,
+		      befs_disk_btree_super *super)
+{
+#ifdef CONFIG_BEFS_DEBUG
+
+	befs_debug(sb, "Btree super structure");
+	befs_debug(sb, "  magic %08x", fs32_to_cpu(sb, super->magic));
+	befs_debug(sb, "  node_size %u", fs32_to_cpu(sb, super->node_size));
+	befs_debug(sb, "  max_depth %08x", fs32_to_cpu(sb, super->max_depth));
+
+	befs_debug(sb, "  data_type %08x", fs32_to_cpu(sb, super->data_type));
+	befs_debug(sb, "  root_node_pointer %016LX",
+		   fs64_to_cpu(sb, super->root_node_ptr));
+	befs_debug(sb, "  free_node_pointer %016LX",
+		   fs64_to_cpu(sb, super->free_node_ptr));
+	befs_debug(sb, "  maximum size %016LX",
+		   fs64_to_cpu(sb, super->max_size));
+
+#endif				//CONFIG_BEFS_DEBUG
+}
+
+void
+befs_dump_index_node(const struct super_block *sb, befs_btree_nodehead *node)
+{
+#ifdef CONFIG_BEFS_DEBUG
+
+	befs_debug(sb, "Btree node structure");
+	befs_debug(sb, "  left %016LX", fs64_to_cpu(sb, node->left));
+	befs_debug(sb, "  right %016LX", fs64_to_cpu(sb, node->right));
+	befs_debug(sb, "  overflow %016LX", fs64_to_cpu(sb, node->overflow));
+	befs_debug(sb, "  all_key_count %hu",
+		   fs16_to_cpu(sb, node->all_key_count));
+	befs_debug(sb, "  all_key_length %hu",
+		   fs16_to_cpu(sb, node->all_key_length));
+
+#endif				//CONFIG_BEFS_DEBUG
+}
diff --git a/fs/befs/endian.h b/fs/befs/endian.h
new file mode 100644
index 000000000..bb55a54c2
--- /dev/null
+++ b/fs/befs/endian.h
@@ -0,0 +1,126 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * linux/fs/befs/endian.h
+ *
+ * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
+ *
+ * Partially based on similar funtions in the sysv driver.
+ */
+
+#ifndef LINUX_BEFS_ENDIAN
+#define LINUX_BEFS_ENDIAN
+
+#include <asm/byteorder.h>
+
+static inline u64
+fs64_to_cpu(const struct super_block *sb, fs64 n)
+{
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE)
+		return le64_to_cpu((__force __le64)n);
+	else
+		return be64_to_cpu((__force __be64)n);
+}
+
+static inline fs64
+cpu_to_fs64(const struct super_block *sb, u64 n)
+{
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE)
+		return (__force fs64)cpu_to_le64(n);
+	else
+		return (__force fs64)cpu_to_be64(n);
+}
+
+static inline u32
+fs32_to_cpu(const struct super_block *sb, fs32 n)
+{
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE)
+		return le32_to_cpu((__force __le32)n);
+	else
+		return be32_to_cpu((__force __be32)n);
+}
+
+static inline fs32
+cpu_to_fs32(const struct super_block *sb, u32 n)
+{
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE)
+		return (__force fs32)cpu_to_le32(n);
+	else
+		return (__force fs32)cpu_to_be32(n);
+}
+
+static inline u16
+fs16_to_cpu(const struct super_block *sb, fs16 n)
+{
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE)
+		return le16_to_cpu((__force __le16)n);
+	else
+		return be16_to_cpu((__force __be16)n);
+}
+
+static inline fs16
+cpu_to_fs16(const struct super_block *sb, u16 n)
+{
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE)
+		return (__force fs16)cpu_to_le16(n);
+	else
+		return (__force fs16)cpu_to_be16(n);
+}
+
+/* Composite types below here */
+
+static inline befs_block_run
+fsrun_to_cpu(const struct super_block *sb, befs_disk_block_run n)
+{
+	befs_block_run run;
+
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) {
+		run.allocation_group = le32_to_cpu((__force __le32)n.allocation_group);
+		run.start = le16_to_cpu((__force __le16)n.start);
+		run.len = le16_to_cpu((__force __le16)n.len);
+	} else {
+		run.allocation_group = be32_to_cpu((__force __be32)n.allocation_group);
+		run.start = be16_to_cpu((__force __be16)n.start);
+		run.len = be16_to_cpu((__force __be16)n.len);
+	}
+	return run;
+}
+
+static inline befs_disk_block_run
+cpu_to_fsrun(const struct super_block *sb, befs_block_run n)
+{
+	befs_disk_block_run run;
+
+	if (BEFS_SB(sb)->byte_order == BEFS_BYTESEX_LE) {
+		run.allocation_group = cpu_to_le32(n.allocation_group);
+		run.start = cpu_to_le16(n.start);
+		run.len = cpu_to_le16(n.len);
+	} else {
+		run.allocation_group = cpu_to_be32(n.allocation_group);
+		run.start = cpu_to_be16(n.start);
+		run.len = cpu_to_be16(n.len);
+	}
+	return run;
+}
+
+static inline befs_data_stream
+fsds_to_cpu(const struct super_block *sb, const befs_disk_data_stream *n)
+{
+	befs_data_stream data;
+	int i;
+
+	for (i = 0; i < BEFS_NUM_DIRECT_BLOCKS; ++i)
+		data.direct[i] = fsrun_to_cpu(sb, n->direct[i]);
+
+	data.max_direct_range = fs64_to_cpu(sb, n->max_direct_range);
+	data.indirect = fsrun_to_cpu(sb, n->indirect);
+	data.max_indirect_range = fs64_to_cpu(sb, n->max_indirect_range);
+	data.double_indirect = fsrun_to_cpu(sb, n->double_indirect);
+	data.max_double_indirect_range = fs64_to_cpu(sb,
+						     n->
+						     max_double_indirect_range);
+	data.size = fs64_to_cpu(sb, n->size);
+
+	return data;
+}
+
+#endif				//LINUX_BEFS_ENDIAN
diff --git a/fs/befs/inode.c b/fs/befs/inode.c
new file mode 100644
index 000000000..791b46a6f
--- /dev/null
+++ b/fs/befs/inode.c
@@ -0,0 +1,55 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * inode.c
+ *
+ * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
+ */
+
+#include <linux/fs.h>
+
+#include "befs.h"
+#include "inode.h"
+
+/*
+ * Validates the correctness of the befs inode
+ * Returns BEFS_OK if the inode should be used, otherwise
+ * returns BEFS_BAD_INODE
+ */
+int
+befs_check_inode(struct super_block *sb, befs_inode *raw_inode,
+		 befs_blocknr_t inode)
+{
+	u32 magic1 = fs32_to_cpu(sb, raw_inode->magic1);
+	befs_inode_addr ino_num = fsrun_to_cpu(sb, raw_inode->inode_num);
+	u32 flags = fs32_to_cpu(sb, raw_inode->flags);
+
+	/* check magic header. */
+	if (magic1 != BEFS_INODE_MAGIC1) {
+		befs_error(sb,
+			   "Inode has a bad magic header - inode = %lu",
+			   (unsigned long)inode);
+		return BEFS_BAD_INODE;
+	}
+
+	/*
+	 * Sanity check2: inodes store their own block address. Check it.
+	 */
+	if (inode != iaddr2blockno(sb, &ino_num)) {
+		befs_error(sb, "inode blocknr field disagrees with vfs "
+			   "VFS: %lu, Inode %lu", (unsigned long)
+			   inode, (unsigned long)iaddr2blockno(sb, &ino_num));
+		return BEFS_BAD_INODE;
+	}
+
+	/*
+	 * check flag
+	 */
+
+	if (!(flags & BEFS_INODE_IN_USE)) {
+		befs_error(sb, "inode is not used - inode = %lu",
+			   (unsigned long)inode);
+		return BEFS_BAD_INODE;
+	}
+
+	return BEFS_OK;
+}
diff --git a/fs/befs/inode.h b/fs/befs/inode.h
new file mode 100644
index 000000000..2219e412f
--- /dev/null
+++ b/fs/befs/inode.h
@@ -0,0 +1,7 @@
+/*
+ * inode.h
+ *
+ */
+
+int befs_check_inode(struct super_block *sb, befs_inode *raw_inode,
+		     befs_blocknr_t inode);
diff --git a/fs/befs/io.c b/fs/befs/io.c
new file mode 100644
index 000000000..2caf50a4a
--- /dev/null
+++ b/fs/befs/io.c
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * linux/fs/befs/io.c
+ *
+ * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com
+ *
+ * Based on portions of file.c and inode.c
+ * by Makoto Kato (m_kato@ga2.so-net.ne.jp)
+ *
+ * Many thanks to Dominic Giampaolo, author of Practical File System
+ * Design with the Be File System, for such a helpful book.
+ *
+ */
+
+#include <linux/buffer_head.h>
+
+#include "befs.h"
+#include "io.h"
+
+/*
+ * Converts befs notion of disk addr to a disk offset and uses
+ * linux kernel function sb_bread() to get the buffer containing
+ * the offset.
+ */
+
+struct buffer_head *
+befs_bread_iaddr(struct super_block *sb, befs_inode_addr iaddr)
+{
+	struct buffer_head *bh;
+	befs_blocknr_t block;
+	struct befs_sb_info *befs_sb = BEFS_SB(sb);
+
+	befs_debug(sb, "---> Enter %s "
+		   "[%u, %hu, %hu]", __func__, iaddr.allocation_group,
+		   iaddr.start, iaddr.len);
+
+	if (iaddr.allocation_group > befs_sb->num_ags) {
+		befs_error(sb, "BEFS: Invalid allocation group %u, max is %u",
+			   iaddr.allocation_group, befs_sb->num_ags);
+		goto error;
+	}
+
+	block = iaddr2blockno(sb, &iaddr);
+
+	befs_debug(sb, "%s: offset = %lu", __func__, (unsigned long)block);
+
+	bh = sb_bread(sb, block);
+
+	if (bh == NULL) {
+		befs_error(sb, "Failed to read block %lu",
+			   (unsigned long)block);
+		goto error;
+	}
+
+	befs_debug(sb, "<--- %s", __func__);
+	return bh;
+
+error:
+	befs_debug(sb, "<--- %s ERROR", __func__);
+	return NULL;
+}
diff --git a/fs/befs/io.h b/fs/befs/io.h
new file mode 100644
index 000000000..9b3e1967c
--- /dev/null
+++ b/fs/befs/io.h
@@ -0,0 +1,6 @@
+/*
+ * io.h
+ */
+
+struct buffer_head *befs_bread_iaddr(struct super_block *sb,
+				     befs_inode_addr iaddr);
diff --git a/fs/befs/linuxvfs.c b/fs/befs/linuxvfs.c
new file mode 100644
index 000000000..4700b4534
--- /dev/null
+++ b/fs/befs/linuxvfs.c
@@ -0,0 +1,1031 @@
+/*
+ * linux/fs/befs/linuxvfs.c
+ *
+ * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com
+ *
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/fs.h>
+#include <linux/errno.h>
+#include <linux/stat.h>
+#include <linux/nls.h>
+#include <linux/buffer_head.h>
+#include <linux/vfs.h>
+#include <linux/parser.h>
+#include <linux/namei.h>
+#include <linux/sched.h>
+#include <linux/cred.h>
+#include <linux/exportfs.h>
+#include <linux/seq_file.h>
+
+#include "befs.h"
+#include "btree.h"
+#include "inode.h"
+#include "datastream.h"
+#include "super.h"
+#include "io.h"
+
+MODULE_DESCRIPTION("BeOS File System (BeFS) driver");
+MODULE_AUTHOR("Will Dyson");
+MODULE_LICENSE("GPL");
+
+/* The units the vfs expects inode->i_blocks to be in */
+#define VFS_BLOCK_SIZE 512
+
+static int befs_readdir(struct file *, struct dir_context *);
+static int befs_get_block(struct inode *, sector_t, struct buffer_head *, int);
+static int befs_readpage(struct file *file, struct page *page);
+static sector_t befs_bmap(struct address_space *mapping, sector_t block);
+static struct dentry *befs_lookup(struct inode *, struct dentry *,
+				  unsigned int);
+static struct inode *befs_iget(struct super_block *, unsigned long);
+static struct inode *befs_alloc_inode(struct super_block *sb);
+static void befs_destroy_inode(struct inode *inode);
+static void befs_destroy_inodecache(void);
+static int befs_symlink_readpage(struct file *, struct page *);
+static int befs_utf2nls(struct super_block *sb, const char *in, int in_len,
+			char **out, int *out_len);
+static int befs_nls2utf(struct super_block *sb, const char *in, int in_len,
+			char **out, int *out_len);
+static void befs_put_super(struct super_block *);
+static int befs_remount(struct super_block *, int *, char *);
+static int befs_statfs(struct dentry *, struct kstatfs *);
+static int befs_show_options(struct seq_file *, struct dentry *);
+static int parse_options(char *, struct befs_mount_options *);
+static struct dentry *befs_fh_to_dentry(struct super_block *sb,
+				struct fid *fid, int fh_len, int fh_type);
+static struct dentry *befs_fh_to_parent(struct super_block *sb,
+				struct fid *fid, int fh_len, int fh_type);
+static struct dentry *befs_get_parent(struct dentry *child);
+
+static const struct super_operations befs_sops = {
+	.alloc_inode	= befs_alloc_inode,	/* allocate a new inode */
+	.destroy_inode	= befs_destroy_inode, /* deallocate an inode */
+	.put_super	= befs_put_super,	/* uninit super */
+	.statfs		= befs_statfs,	/* statfs */
+	.remount_fs	= befs_remount,
+	.show_options	= befs_show_options,
+};
+
+/* slab cache for befs_inode_info objects */
+static struct kmem_cache *befs_inode_cachep;
+
+static const struct file_operations befs_dir_operations = {
+	.read		= generic_read_dir,
+	.iterate_shared	= befs_readdir,
+	.llseek		= generic_file_llseek,
+};
+
+static const struct inode_operations befs_dir_inode_operations = {
+	.lookup		= befs_lookup,
+};
+
+static const struct address_space_operations befs_aops = {
+	.readpage	= befs_readpage,
+	.bmap		= befs_bmap,
+};
+
+static const struct address_space_operations befs_symlink_aops = {
+	.readpage	= befs_symlink_readpage,
+};
+
+static const struct export_operations befs_export_operations = {
+	.fh_to_dentry	= befs_fh_to_dentry,
+	.fh_to_parent	= befs_fh_to_parent,
+	.get_parent	= befs_get_parent,
+};
+
+/*
+ * Called by generic_file_read() to read a page of data
+ *
+ * In turn, simply calls a generic block read function and
+ * passes it the address of befs_get_block, for mapping file
+ * positions to disk blocks.
+ */
+static int
+befs_readpage(struct file *file, struct page *page)
+{
+	return block_read_full_page(page, befs_get_block);
+}
+
+static sector_t
+befs_bmap(struct address_space *mapping, sector_t block)
+{
+	return generic_block_bmap(mapping, block, befs_get_block);
+}
+
+/*
+ * Generic function to map a file position (block) to a
+ * disk offset (passed back in bh_result).
+ *
+ * Used by many higher level functions.
+ *
+ * Calls befs_fblock2brun() in datastream.c to do the real work.
+ */
+
+static int
+befs_get_block(struct inode *inode, sector_t block,
+	       struct buffer_head *bh_result, int create)
+{
+	struct super_block *sb = inode->i_sb;
+	befs_data_stream *ds = &BEFS_I(inode)->i_data.ds;
+	befs_block_run run = BAD_IADDR;
+	int res;
+	ulong disk_off;
+
+	befs_debug(sb, "---> befs_get_block() for inode %lu, block %ld",
+		   (unsigned long)inode->i_ino, (long)block);
+	if (create) {
+		befs_error(sb, "befs_get_block() was asked to write to "
+			   "block %ld in inode %lu", (long)block,
+			   (unsigned long)inode->i_ino);
+		return -EPERM;
+	}
+
+	res = befs_fblock2brun(sb, ds, block, &run);
+	if (res != BEFS_OK) {
+		befs_error(sb,
+			   "<--- %s for inode %lu, block %ld ERROR",
+			   __func__, (unsigned long)inode->i_ino,
+			   (long)block);
+		return -EFBIG;
+	}
+
+	disk_off = (ulong) iaddr2blockno(sb, &run);
+
+	map_bh(bh_result, inode->i_sb, disk_off);
+
+	befs_debug(sb, "<--- %s for inode %lu, block %ld, disk address %lu",
+		  __func__, (unsigned long)inode->i_ino, (long)block,
+		  (unsigned long)disk_off);
+
+	return 0;
+}
+
+static struct dentry *
+befs_lookup(struct inode *dir, struct dentry *dentry, unsigned int flags)
+{
+	struct inode *inode;
+	struct super_block *sb = dir->i_sb;
+	const befs_data_stream *ds = &BEFS_I(dir)->i_data.ds;
+	befs_off_t offset;
+	int ret;
+	int utfnamelen;
+	char *utfname;
+	const char *name = dentry->d_name.name;
+
+	befs_debug(sb, "---> %s name %pd inode %ld", __func__,
+		   dentry, dir->i_ino);
+
+	/* Convert to UTF-8 */
+	if (BEFS_SB(sb)->nls) {
+		ret =
+		    befs_nls2utf(sb, name, strlen(name), &utfname, &utfnamelen);
+		if (ret < 0) {
+			befs_debug(sb, "<--- %s ERROR", __func__);
+			return ERR_PTR(ret);
+		}
+		ret = befs_btree_find(sb, ds, utfname, &offset);
+		kfree(utfname);
+
+	} else {
+		ret = befs_btree_find(sb, ds, name, &offset);
+	}
+
+	if (ret == BEFS_BT_NOT_FOUND) {
+		befs_debug(sb, "<--- %s %pd not found", __func__, dentry);
+		inode = NULL;
+	} else if (ret != BEFS_OK || offset == 0) {
+		befs_error(sb, "<--- %s Error", __func__);
+		inode = ERR_PTR(-ENODATA);
+	} else {
+		inode = befs_iget(dir->i_sb, (ino_t) offset);
+	}
+	befs_debug(sb, "<--- %s", __func__);
+
+	return d_splice_alias(inode, dentry);
+}
+
+static int
+befs_readdir(struct file *file, struct dir_context *ctx)
+{
+	struct inode *inode = file_inode(file);
+	struct super_block *sb = inode->i_sb;
+	const befs_data_stream *ds = &BEFS_I(inode)->i_data.ds;
+	befs_off_t value;
+	int result;
+	size_t keysize;
+	char keybuf[BEFS_NAME_LEN + 1];
+
+	befs_debug(sb, "---> %s name %pD, inode %ld, ctx->pos %lld",
+		  __func__, file, inode->i_ino, ctx->pos);
+
+	while (1) {
+		result = befs_btree_read(sb, ds, ctx->pos, BEFS_NAME_LEN + 1,
+					 keybuf, &keysize, &value);
+
+		if (result == BEFS_ERR) {
+			befs_debug(sb, "<--- %s ERROR", __func__);
+			befs_error(sb, "IO error reading %pD (inode %lu)",
+				   file, inode->i_ino);
+			return -EIO;
+
+		} else if (result == BEFS_BT_END) {
+			befs_debug(sb, "<--- %s END", __func__);
+			return 0;
+
+		} else if (result == BEFS_BT_EMPTY) {
+			befs_debug(sb, "<--- %s Empty directory", __func__);
+			return 0;
+		}
+
+		/* Convert to NLS */
+		if (BEFS_SB(sb)->nls) {
+			char *nlsname;
+			int nlsnamelen;
+
+			result =
+			    befs_utf2nls(sb, keybuf, keysize, &nlsname,
+					 &nlsnamelen);
+			if (result < 0) {
+				befs_debug(sb, "<--- %s ERROR", __func__);
+				return result;
+			}
+			if (!dir_emit(ctx, nlsname, nlsnamelen,
+				      (ino_t) value, DT_UNKNOWN)) {
+				kfree(nlsname);
+				return 0;
+			}
+			kfree(nlsname);
+		} else {
+			if (!dir_emit(ctx, keybuf, keysize,
+				      (ino_t) value, DT_UNKNOWN))
+				return 0;
+		}
+		ctx->pos++;
+	}
+}
+
+static struct inode *
+befs_alloc_inode(struct super_block *sb)
+{
+	struct befs_inode_info *bi;
+
+	bi = kmem_cache_alloc(befs_inode_cachep, GFP_KERNEL);
+	if (!bi)
+		return NULL;
+	return &bi->vfs_inode;
+}
+
+static void befs_i_callback(struct rcu_head *head)
+{
+	struct inode *inode = container_of(head, struct inode, i_rcu);
+	kmem_cache_free(befs_inode_cachep, BEFS_I(inode));
+}
+
+static void befs_destroy_inode(struct inode *inode)
+{
+	call_rcu(&inode->i_rcu, befs_i_callback);
+}
+
+static void init_once(void *foo)
+{
+	struct befs_inode_info *bi = (struct befs_inode_info *) foo;
+
+	inode_init_once(&bi->vfs_inode);
+}
+
+static struct inode *befs_iget(struct super_block *sb, unsigned long ino)
+{
+	struct buffer_head *bh;
+	befs_inode *raw_inode;
+	struct befs_sb_info *befs_sb = BEFS_SB(sb);
+	struct befs_inode_info *befs_ino;
+	struct inode *inode;
+
+	befs_debug(sb, "---> %s inode = %lu", __func__, ino);
+
+	inode = iget_locked(sb, ino);
+	if (!inode)
+		return ERR_PTR(-ENOMEM);
+	if (!(inode->i_state & I_NEW))
+		return inode;
+
+	befs_ino = BEFS_I(inode);
+
+	/* convert from vfs's inode number to befs's inode number */
+	befs_ino->i_inode_num = blockno2iaddr(sb, inode->i_ino);
+
+	befs_debug(sb, "  real inode number [%u, %hu, %hu]",
+		   befs_ino->i_inode_num.allocation_group,
+		   befs_ino->i_inode_num.start, befs_ino->i_inode_num.len);
+
+	bh = sb_bread(sb, inode->i_ino);
+	if (!bh) {
+		befs_error(sb, "unable to read inode block - "
+			   "inode = %lu", inode->i_ino);
+		goto unacquire_none;
+	}
+
+	raw_inode = (befs_inode *) bh->b_data;
+
+	befs_dump_inode(sb, raw_inode);
+
+	if (befs_check_inode(sb, raw_inode, inode->i_ino) != BEFS_OK) {
+		befs_error(sb, "Bad inode: %lu", inode->i_ino);
+		goto unacquire_bh;
+	}
+
+	inode->i_mode = (umode_t) fs32_to_cpu(sb, raw_inode->mode);
+
+	/*
+	 * set uid and gid.  But since current BeOS is single user OS, so
+	 * you can change by "uid" or "gid" options.
+	 */
+
+	inode->i_uid = befs_sb->mount_opts.use_uid ?
+		befs_sb->mount_opts.uid :
+		make_kuid(&init_user_ns, fs32_to_cpu(sb, raw_inode->uid));
+	inode->i_gid = befs_sb->mount_opts.use_gid ?
+		befs_sb->mount_opts.gid :
+		make_kgid(&init_user_ns, fs32_to_cpu(sb, raw_inode->gid));
+
+	set_nlink(inode, 1);
+
+	/*
+	 * BEFS's time is 64 bits, but current VFS is 32 bits...
+	 * BEFS don't have access time. Nor inode change time. VFS
+	 * doesn't have creation time.
+	 * Also, the lower 16 bits of the last_modified_time and
+	 * create_time are just a counter to help ensure uniqueness
+	 * for indexing purposes. (PFD, page 54)
+	 */
+
+	inode->i_mtime.tv_sec =
+	    fs64_to_cpu(sb, raw_inode->last_modified_time) >> 16;
+	inode->i_mtime.tv_nsec = 0;   /* lower 16 bits are not a time */
+	inode->i_ctime = inode->i_mtime;
+	inode->i_atime = inode->i_mtime;
+
+	befs_ino->i_inode_num = fsrun_to_cpu(sb, raw_inode->inode_num);
+	befs_ino->i_parent = fsrun_to_cpu(sb, raw_inode->parent);
+	befs_ino->i_attribute = fsrun_to_cpu(sb, raw_inode->attributes);
+	befs_ino->i_flags = fs32_to_cpu(sb, raw_inode->flags);
+
+	if (S_ISLNK(inode->i_mode) && !(befs_ino->i_flags & BEFS_LONG_SYMLINK)){
+		inode->i_size = 0;
+		inode->i_blocks = befs_sb->block_size / VFS_BLOCK_SIZE;
+		strlcpy(befs_ino->i_data.symlink, raw_inode->data.symlink,
+			BEFS_SYMLINK_LEN);
+	} else {
+		int num_blks;
+
+		befs_ino->i_data.ds =
+		    fsds_to_cpu(sb, &raw_inode->data.datastream);
+
+		num_blks = befs_count_blocks(sb, &befs_ino->i_data.ds);
+		inode->i_blocks =
+		    num_blks * (befs_sb->block_size / VFS_BLOCK_SIZE);
+		inode->i_size = befs_ino->i_data.ds.size;
+	}
+
+	inode->i_mapping->a_ops = &befs_aops;
+
+	if (S_ISREG(inode->i_mode)) {
+		inode->i_fop = &generic_ro_fops;
+	} else if (S_ISDIR(inode->i_mode)) {
+		inode->i_op = &befs_dir_inode_operations;
+		inode->i_fop = &befs_dir_operations;
+	} else if (S_ISLNK(inode->i_mode)) {
+		if (befs_ino->i_flags & BEFS_LONG_SYMLINK) {
+			inode->i_op = &page_symlink_inode_operations;
+			inode_nohighmem(inode);
+			inode->i_mapping->a_ops = &befs_symlink_aops;
+		} else {
+			inode->i_link = befs_ino->i_data.symlink;
+			inode->i_op = &simple_symlink_inode_operations;
+		}
+	} else {
+		befs_error(sb, "Inode %lu is not a regular file, "
+			   "directory or symlink. THAT IS WRONG! BeFS has no "
+			   "on disk special files", inode->i_ino);
+		goto unacquire_bh;
+	}
+
+	brelse(bh);
+	befs_debug(sb, "<--- %s", __func__);
+	unlock_new_inode(inode);
+	return inode;
+
+unacquire_bh:
+	brelse(bh);
+
+unacquire_none:
+	iget_failed(inode);
+	befs_debug(sb, "<--- %s - Bad inode", __func__);
+	return ERR_PTR(-EIO);
+}
+
+/* Initialize the inode cache. Called at fs setup.
+ *
+ * Taken from NFS implementation by Al Viro.
+ */
+static int __init
+befs_init_inodecache(void)
+{
+	befs_inode_cachep = kmem_cache_create_usercopy("befs_inode_cache",
+				sizeof(struct befs_inode_info), 0,
+				(SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD|
+					SLAB_ACCOUNT),
+				offsetof(struct befs_inode_info,
+					i_data.symlink),
+				sizeof_field(struct befs_inode_info,
+					i_data.symlink),
+				init_once);
+	if (befs_inode_cachep == NULL)
+		return -ENOMEM;
+
+	return 0;
+}
+
+/* Called at fs teardown.
+ *
+ * Taken from NFS implementation by Al Viro.
+ */
+static void
+befs_destroy_inodecache(void)
+{
+	/*
+	 * Make sure all delayed rcu free inodes are flushed before we
+	 * destroy cache.
+	 */
+	rcu_barrier();
+	kmem_cache_destroy(befs_inode_cachep);
+}
+
+/*
+ * The inode of symbolic link is different to data stream.
+ * The data stream become link name. Unless the LONG_SYMLINK
+ * flag is set.
+ */
+static int befs_symlink_readpage(struct file *unused, struct page *page)
+{
+	struct inode *inode = page->mapping->host;
+	struct super_block *sb = inode->i_sb;
+	struct befs_inode_info *befs_ino = BEFS_I(inode);
+	befs_data_stream *data = &befs_ino->i_data.ds;
+	befs_off_t len = data->size;
+	char *link = page_address(page);
+
+	if (len == 0 || len > PAGE_SIZE) {
+		befs_error(sb, "Long symlink with illegal length");
+		goto fail;
+	}
+	befs_debug(sb, "Follow long symlink");
+
+	if (befs_read_lsymlink(sb, data, link, len) != len) {
+		befs_error(sb, "Failed to read entire long symlink");
+		goto fail;
+	}
+	link[len - 1] = '\0';
+	SetPageUptodate(page);
+	unlock_page(page);
+	return 0;
+fail:
+	SetPageError(page);
+	unlock_page(page);
+	return -EIO;
+}
+
+/*
+ * UTF-8 to NLS charset convert routine
+ *
+ * Uses uni2char() / char2uni() rather than the nls tables directly
+ */
+static int
+befs_utf2nls(struct super_block *sb, const char *in,
+	     int in_len, char **out, int *out_len)
+{
+	struct nls_table *nls = BEFS_SB(sb)->nls;
+	int i, o;
+	unicode_t uni;
+	int unilen, utflen;
+	char *result;
+	/* The utf8->nls conversion won't make the final nls string bigger
+	 * than the utf one, but if the string is pure ascii they'll have the
+	 * same width and an extra char is needed to save the additional \0
+	 */
+	int maxlen = in_len + 1;
+
+	befs_debug(sb, "---> %s", __func__);
+
+	if (!nls) {
+		befs_error(sb, "%s called with no NLS table loaded", __func__);
+		return -EINVAL;
+	}
+
+	*out = result = kmalloc(maxlen, GFP_NOFS);
+	if (!*out)
+		return -ENOMEM;
+
+	for (i = o = 0; i < in_len; i += utflen, o += unilen) {
+
+		/* convert from UTF-8 to Unicode */
+		utflen = utf8_to_utf32(&in[i], in_len - i, &uni);
+		if (utflen < 0)
+			goto conv_err;
+
+		/* convert from Unicode to nls */
+		if (uni > MAX_WCHAR_T)
+			goto conv_err;
+		unilen = nls->uni2char(uni, &result[o], in_len - o);
+		if (unilen < 0)
+			goto conv_err;
+	}
+	result[o] = '\0';
+	*out_len = o;
+
+	befs_debug(sb, "<--- %s", __func__);
+
+	return o;
+
+conv_err:
+	befs_error(sb, "Name using character set %s contains a character that "
+		   "cannot be converted to unicode.", nls->charset);
+	befs_debug(sb, "<--- %s", __func__);
+	kfree(result);
+	return -EILSEQ;
+}
+
+/**
+ * befs_nls2utf - Convert NLS string to utf8 encodeing
+ * @sb: Superblock
+ * @in: Input string buffer in NLS format
+ * @in_len: Length of input string in bytes
+ * @out: The output string in UTF-8 format
+ * @out_len: Length of the output buffer
+ *
+ * Converts input string @in, which is in the format of the loaded NLS map,
+ * into a utf8 string.
+ *
+ * The destination string @out is allocated by this function and the caller is
+ * responsible for freeing it with kfree()
+ *
+ * On return, *@out_len is the length of @out in bytes.
+ *
+ * On success, the return value is the number of utf8 characters written to
+ * the output buffer @out.
+ *
+ * On Failure, a negative number coresponding to the error code is returned.
+ */
+
+static int
+befs_nls2utf(struct super_block *sb, const char *in,
+	     int in_len, char **out, int *out_len)
+{
+	struct nls_table *nls = BEFS_SB(sb)->nls;
+	int i, o;
+	wchar_t uni;
+	int unilen, utflen;
+	char *result;
+	/*
+	 * There are nls characters that will translate to 3-chars-wide UTF-8
+	 * characters, an additional byte is needed to save the final \0
+	 * in special cases
+	 */
+	int maxlen = (3 * in_len) + 1;
+
+	befs_debug(sb, "---> %s\n", __func__);
+
+	if (!nls) {
+		befs_error(sb, "%s called with no NLS table loaded.",
+			   __func__);
+		return -EINVAL;
+	}
+
+	*out = result = kmalloc(maxlen, GFP_NOFS);
+	if (!*out) {
+		*out_len = 0;
+		return -ENOMEM;
+	}
+
+	for (i = o = 0; i < in_len; i += unilen, o += utflen) {
+
+		/* convert from nls to unicode */
+		unilen = nls->char2uni(&in[i], in_len - i, &uni);
+		if (unilen < 0)
+			goto conv_err;
+
+		/* convert from unicode to UTF-8 */
+		utflen = utf32_to_utf8(uni, &result[o], 3);
+		if (utflen <= 0)
+			goto conv_err;
+	}
+
+	result[o] = '\0';
+	*out_len = o;
+
+	befs_debug(sb, "<--- %s", __func__);
+
+	return i;
+
+conv_err:
+	befs_error(sb, "Name using character set %s contains a character that "
+		   "cannot be converted to unicode.", nls->charset);
+	befs_debug(sb, "<--- %s", __func__);
+	kfree(result);
+	return -EILSEQ;
+}
+
+static struct inode *befs_nfs_get_inode(struct super_block *sb, uint64_t ino,
+					 uint32_t generation)
+{
+	/* No need to handle i_generation */
+	return befs_iget(sb, ino);
+}
+
+/*
+ * Map a NFS file handle to a corresponding dentry
+ */
+static struct dentry *befs_fh_to_dentry(struct super_block *sb,
+				struct fid *fid, int fh_len, int fh_type)
+{
+	return generic_fh_to_dentry(sb, fid, fh_len, fh_type,
+				    befs_nfs_get_inode);
+}
+
+/*
+ * Find the parent for a file specified by NFS handle
+ */
+static struct dentry *befs_fh_to_parent(struct super_block *sb,
+				struct fid *fid, int fh_len, int fh_type)
+{
+	return generic_fh_to_parent(sb, fid, fh_len, fh_type,
+				    befs_nfs_get_inode);
+}
+
+static struct dentry *befs_get_parent(struct dentry *child)
+{
+	struct inode *parent;
+	struct befs_inode_info *befs_ino = BEFS_I(d_inode(child));
+
+	parent = befs_iget(child->d_sb,
+			   (unsigned long)befs_ino->i_parent.start);
+	if (IS_ERR(parent))
+		return ERR_CAST(parent);
+
+	return d_obtain_alias(parent);
+}
+
+enum {
+	Opt_uid, Opt_gid, Opt_charset, Opt_debug, Opt_err,
+};
+
+static const match_table_t befs_tokens = {
+	{Opt_uid, "uid=%d"},
+	{Opt_gid, "gid=%d"},
+	{Opt_charset, "iocharset=%s"},
+	{Opt_debug, "debug"},
+	{Opt_err, NULL}
+};
+
+static int
+parse_options(char *options, struct befs_mount_options *opts)
+{
+	char *p;
+	substring_t args[MAX_OPT_ARGS];
+	int option;
+	kuid_t uid;
+	kgid_t gid;
+
+	/* Initialize options */
+	opts->uid = GLOBAL_ROOT_UID;
+	opts->gid = GLOBAL_ROOT_GID;
+	opts->use_uid = 0;
+	opts->use_gid = 0;
+	opts->iocharset = NULL;
+	opts->debug = 0;
+
+	if (!options)
+		return 1;
+
+	while ((p = strsep(&options, ",")) != NULL) {
+		int token;
+
+		if (!*p)
+			continue;
+
+		token = match_token(p, befs_tokens, args);
+		switch (token) {
+		case Opt_uid:
+			if (match_int(&args[0], &option))
+				return 0;
+			uid = INVALID_UID;
+			if (option >= 0)
+				uid = make_kuid(current_user_ns(), option);
+			if (!uid_valid(uid)) {
+				pr_err("Invalid uid %d, "
+				       "using default\n", option);
+				break;
+			}
+			opts->uid = uid;
+			opts->use_uid = 1;
+			break;
+		case Opt_gid:
+			if (match_int(&args[0], &option))
+				return 0;
+			gid = INVALID_GID;
+			if (option >= 0)
+				gid = make_kgid(current_user_ns(), option);
+			if (!gid_valid(gid)) {
+				pr_err("Invalid gid %d, "
+				       "using default\n", option);
+				break;
+			}
+			opts->gid = gid;
+			opts->use_gid = 1;
+			break;
+		case Opt_charset:
+			kfree(opts->iocharset);
+			opts->iocharset = match_strdup(&args[0]);
+			if (!opts->iocharset) {
+				pr_err("allocation failure for "
+				       "iocharset string\n");
+				return 0;
+			}
+			break;
+		case Opt_debug:
+			opts->debug = 1;
+			break;
+		default:
+			pr_err("Unrecognized mount option \"%s\" "
+			       "or missing value\n", p);
+			return 0;
+		}
+	}
+	return 1;
+}
+
+static int befs_show_options(struct seq_file *m, struct dentry *root)
+{
+	struct befs_sb_info *befs_sb = BEFS_SB(root->d_sb);
+	struct befs_mount_options *opts = &befs_sb->mount_opts;
+
+	if (!uid_eq(opts->uid, GLOBAL_ROOT_UID))
+		seq_printf(m, ",uid=%u",
+			   from_kuid_munged(&init_user_ns, opts->uid));
+	if (!gid_eq(opts->gid, GLOBAL_ROOT_GID))
+		seq_printf(m, ",gid=%u",
+			   from_kgid_munged(&init_user_ns, opts->gid));
+	if (opts->iocharset)
+		seq_printf(m, ",charset=%s", opts->iocharset);
+	if (opts->debug)
+		seq_puts(m, ",debug");
+	return 0;
+}
+
+/* This function has the responsibiltiy of getting the
+ * filesystem ready for unmounting.
+ * Basically, we free everything that we allocated in
+ * befs_read_inode
+ */
+static void
+befs_put_super(struct super_block *sb)
+{
+	kfree(BEFS_SB(sb)->mount_opts.iocharset);
+	BEFS_SB(sb)->mount_opts.iocharset = NULL;
+	unload_nls(BEFS_SB(sb)->nls);
+	kfree(sb->s_fs_info);
+	sb->s_fs_info = NULL;
+}
+
+/* Allocate private field of the superblock, fill it.
+ *
+ * Finish filling the public superblock fields
+ * Make the root directory
+ * Load a set of NLS translations if needed.
+ */
+static int
+befs_fill_super(struct super_block *sb, void *data, int silent)
+{
+	struct buffer_head *bh;
+	struct befs_sb_info *befs_sb;
+	befs_super_block *disk_sb;
+	struct inode *root;
+	long ret = -EINVAL;
+	const unsigned long sb_block = 0;
+	const off_t x86_sb_off = 512;
+	int blocksize;
+
+	sb->s_fs_info = kzalloc(sizeof(*befs_sb), GFP_KERNEL);
+	if (sb->s_fs_info == NULL)
+		goto unacquire_none;
+
+	befs_sb = BEFS_SB(sb);
+
+	if (!parse_options((char *) data, &befs_sb->mount_opts)) {
+		if (!silent)
+			befs_error(sb, "cannot parse mount options");
+		goto unacquire_priv_sbp;
+	}
+
+	befs_debug(sb, "---> %s", __func__);
+
+	if (!sb_rdonly(sb)) {
+		befs_warning(sb,
+			     "No write support. Marking filesystem read-only");
+		sb->s_flags |= SB_RDONLY;
+	}
+
+	/*
+	 * Set dummy blocksize to read super block.
+	 * Will be set to real fs blocksize later.
+	 *
+	 * Linux 2.4.10 and later refuse to read blocks smaller than
+	 * the logical block size for the device. But we also need to read at
+	 * least 1k to get the second 512 bytes of the volume.
+	 */
+	blocksize = sb_min_blocksize(sb, 1024);
+	if (!blocksize) {
+		if (!silent)
+			befs_error(sb, "unable to set blocksize");
+		goto unacquire_priv_sbp;
+	}
+
+	bh = sb_bread(sb, sb_block);
+	if (!bh) {
+		if (!silent)
+			befs_error(sb, "unable to read superblock");
+		goto unacquire_priv_sbp;
+	}
+
+	/* account for offset of super block on x86 */
+	disk_sb = (befs_super_block *) bh->b_data;
+	if ((disk_sb->magic1 == BEFS_SUPER_MAGIC1_LE) ||
+	    (disk_sb->magic1 == BEFS_SUPER_MAGIC1_BE)) {
+		befs_debug(sb, "Using PPC superblock location");
+	} else {
+		befs_debug(sb, "Using x86 superblock location");
+		disk_sb =
+		    (befs_super_block *) ((void *) bh->b_data + x86_sb_off);
+	}
+
+	if ((befs_load_sb(sb, disk_sb) != BEFS_OK) ||
+	    (befs_check_sb(sb) != BEFS_OK))
+		goto unacquire_bh;
+
+	befs_dump_super_block(sb, disk_sb);
+
+	brelse(bh);
+
+	if (befs_sb->num_blocks > ~((sector_t)0)) {
+		if (!silent)
+			befs_error(sb, "blocks count: %llu is larger than the host can use",
+					befs_sb->num_blocks);
+		goto unacquire_priv_sbp;
+	}
+
+	/*
+	 * set up enough so that it can read an inode
+	 * Fill in kernel superblock fields from private sb
+	 */
+	sb->s_magic = BEFS_SUPER_MAGIC;
+	/* Set real blocksize of fs */
+	sb_set_blocksize(sb, (ulong) befs_sb->block_size);
+	sb->s_op = &befs_sops;
+	sb->s_export_op = &befs_export_operations;
+	root = befs_iget(sb, iaddr2blockno(sb, &(befs_sb->root_dir)));
+	if (IS_ERR(root)) {
+		ret = PTR_ERR(root);
+		goto unacquire_priv_sbp;
+	}
+	sb->s_root = d_make_root(root);
+	if (!sb->s_root) {
+		if (!silent)
+			befs_error(sb, "get root inode failed");
+		goto unacquire_priv_sbp;
+	}
+
+	/* load nls library */
+	if (befs_sb->mount_opts.iocharset) {
+		befs_debug(sb, "Loading nls: %s",
+			   befs_sb->mount_opts.iocharset);
+		befs_sb->nls = load_nls(befs_sb->mount_opts.iocharset);
+		if (!befs_sb->nls) {
+			befs_warning(sb, "Cannot load nls %s"
+					" loading default nls",
+					befs_sb->mount_opts.iocharset);
+			befs_sb->nls = load_nls_default();
+		}
+	/* load default nls if none is specified  in mount options */
+	} else {
+		befs_debug(sb, "Loading default nls");
+		befs_sb->nls = load_nls_default();
+	}
+
+	return 0;
+
+unacquire_bh:
+	brelse(bh);
+
+unacquire_priv_sbp:
+	kfree(befs_sb->mount_opts.iocharset);
+	kfree(sb->s_fs_info);
+	sb->s_fs_info = NULL;
+
+unacquire_none:
+	return ret;
+}
+
+static int
+befs_remount(struct super_block *sb, int *flags, char *data)
+{
+	sync_filesystem(sb);
+	if (!(*flags & SB_RDONLY))
+		return -EINVAL;
+	return 0;
+}
+
+static int
+befs_statfs(struct dentry *dentry, struct kstatfs *buf)
+{
+	struct super_block *sb = dentry->d_sb;
+	u64 id = huge_encode_dev(sb->s_bdev->bd_dev);
+
+	befs_debug(sb, "---> %s", __func__);
+
+	buf->f_type = BEFS_SUPER_MAGIC;
+	buf->f_bsize = sb->s_blocksize;
+	buf->f_blocks = BEFS_SB(sb)->num_blocks;
+	buf->f_bfree = BEFS_SB(sb)->num_blocks - BEFS_SB(sb)->used_blocks;
+	buf->f_bavail = buf->f_bfree;
+	buf->f_files = 0;	/* UNKNOWN */
+	buf->f_ffree = 0;	/* UNKNOWN */
+	buf->f_fsid.val[0] = (u32)id;
+	buf->f_fsid.val[1] = (u32)(id >> 32);
+	buf->f_namelen = BEFS_NAME_LEN;
+
+	befs_debug(sb, "<--- %s", __func__);
+
+	return 0;
+}
+
+static struct dentry *
+befs_mount(struct file_system_type *fs_type, int flags, const char *dev_name,
+	    void *data)
+{
+	return mount_bdev(fs_type, flags, dev_name, data, befs_fill_super);
+}
+
+static struct file_system_type befs_fs_type = {
+	.owner		= THIS_MODULE,
+	.name		= "befs",
+	.mount		= befs_mount,
+	.kill_sb	= kill_block_super,
+	.fs_flags	= FS_REQUIRES_DEV,
+};
+MODULE_ALIAS_FS("befs");
+
+static int __init
+init_befs_fs(void)
+{
+	int err;
+
+	pr_info("version: %s\n", BEFS_VERSION);
+
+	err = befs_init_inodecache();
+	if (err)
+		goto unacquire_none;
+
+	err = register_filesystem(&befs_fs_type);
+	if (err)
+		goto unacquire_inodecache;
+
+	return 0;
+
+unacquire_inodecache:
+	befs_destroy_inodecache();
+
+unacquire_none:
+	return err;
+}
+
+static void __exit
+exit_befs_fs(void)
+{
+	befs_destroy_inodecache();
+
+	unregister_filesystem(&befs_fs_type);
+}
+
+/*
+ * Macros that typecheck the init and exit functions,
+ * ensures that they are called at init and cleanup,
+ * and eliminates warnings about unused functions.
+ */
+module_init(init_befs_fs)
+module_exit(exit_befs_fs)
diff --git a/fs/befs/super.c b/fs/befs/super.c
new file mode 100644
index 000000000..7c50025c9
--- /dev/null
+++ b/fs/befs/super.c
@@ -0,0 +1,118 @@
+/*
+ * super.c
+ *
+ * Copyright (C) 2001-2002 Will Dyson <will_dyson@pobox.com>
+ *
+ * Licensed under the GNU GPL. See the file COPYING for details.
+ *
+ */
+
+#include <linux/fs.h>
+#include <asm/page.h> /* for PAGE_SIZE */
+
+#include "befs.h"
+#include "super.h"
+
+/*
+ * befs_load_sb -- Read from disk and properly byteswap all the fields
+ * of the befs superblock
+ */
+int
+befs_load_sb(struct super_block *sb, befs_super_block *disk_sb)
+{
+	struct befs_sb_info *befs_sb = BEFS_SB(sb);
+
+	/* Check the byte order of the filesystem */
+	if (disk_sb->fs_byte_order == BEFS_BYTEORDER_NATIVE_LE)
+		befs_sb->byte_order = BEFS_BYTESEX_LE;
+	else if (disk_sb->fs_byte_order == BEFS_BYTEORDER_NATIVE_BE)
+		befs_sb->byte_order = BEFS_BYTESEX_BE;
+
+	befs_sb->magic1 = fs32_to_cpu(sb, disk_sb->magic1);
+	befs_sb->magic2 = fs32_to_cpu(sb, disk_sb->magic2);
+	befs_sb->magic3 = fs32_to_cpu(sb, disk_sb->magic3);
+	befs_sb->block_size = fs32_to_cpu(sb, disk_sb->block_size);
+	befs_sb->block_shift = fs32_to_cpu(sb, disk_sb->block_shift);
+	befs_sb->num_blocks = fs64_to_cpu(sb, disk_sb->num_blocks);
+	befs_sb->used_blocks = fs64_to_cpu(sb, disk_sb->used_blocks);
+	befs_sb->inode_size = fs32_to_cpu(sb, disk_sb->inode_size);
+
+	befs_sb->blocks_per_ag = fs32_to_cpu(sb, disk_sb->blocks_per_ag);
+	befs_sb->ag_shift = fs32_to_cpu(sb, disk_sb->ag_shift);
+	befs_sb->num_ags = fs32_to_cpu(sb, disk_sb->num_ags);
+
+	befs_sb->flags = fs32_to_cpu(sb, disk_sb->flags);
+
+	befs_sb->log_blocks = fsrun_to_cpu(sb, disk_sb->log_blocks);
+	befs_sb->log_start = fs64_to_cpu(sb, disk_sb->log_start);
+	befs_sb->log_end = fs64_to_cpu(sb, disk_sb->log_end);
+
+	befs_sb->root_dir = fsrun_to_cpu(sb, disk_sb->root_dir);
+	befs_sb->indices = fsrun_to_cpu(sb, disk_sb->indices);
+	befs_sb->nls = NULL;
+
+	return BEFS_OK;
+}
+
+int
+befs_check_sb(struct super_block *sb)
+{
+	struct befs_sb_info *befs_sb = BEFS_SB(sb);
+
+	/* Check magic headers of super block */
+	if ((befs_sb->magic1 != BEFS_SUPER_MAGIC1)
+	    || (befs_sb->magic2 != BEFS_SUPER_MAGIC2)
+	    || (befs_sb->magic3 != BEFS_SUPER_MAGIC3)) {
+		befs_error(sb, "invalid magic header");
+		return BEFS_ERR;
+	}
+
+	/*
+	 * Check blocksize of BEFS.
+	 *
+	 * Blocksize of BEFS is 1024, 2048, 4096 or 8192.
+	 */
+
+	if ((befs_sb->block_size != 1024)
+	    && (befs_sb->block_size != 2048)
+	    && (befs_sb->block_size != 4096)
+	    && (befs_sb->block_size != 8192)) {
+		befs_error(sb, "invalid blocksize: %u", befs_sb->block_size);
+		return BEFS_ERR;
+	}
+
+	if (befs_sb->block_size > PAGE_SIZE) {
+		befs_error(sb, "blocksize(%u) cannot be larger "
+			   "than system pagesize(%lu)", befs_sb->block_size,
+			   PAGE_SIZE);
+		return BEFS_ERR;
+	}
+
+	/*
+	 * block_shift and block_size encode the same information
+	 * in different ways as a consistency check.
+	 */
+
+	if ((1 << befs_sb->block_shift) != befs_sb->block_size) {
+		befs_error(sb, "block_shift disagrees with block_size. "
+			   "Corruption likely.");
+		return BEFS_ERR;
+	}
+
+
+	/* ag_shift also encodes the same information as blocks_per_ag in a
+	 * different way, non-fatal consistency check
+	 */
+	if ((1 << befs_sb->ag_shift) != befs_sb->blocks_per_ag)
+		befs_error(sb, "ag_shift disagrees with blocks_per_ag.");
+
+	if (befs_sb->log_start != befs_sb->log_end ||
+	    befs_sb->flags == BEFS_DIRTY) {
+		befs_error(sb, "Filesystem not clean! There are blocks in the "
+			   "journal. You must boot into BeOS and mount this "
+			   "volume to make it clean.");
+		return BEFS_ERR;
+	}
+
+	return BEFS_OK;
+}
diff --git a/fs/befs/super.h b/fs/befs/super.h
new file mode 100644
index 000000000..ec1df30a7
--- /dev/null
+++ b/fs/befs/super.h
@@ -0,0 +1,6 @@
+/*
+ * super.h
+ */
+
+int befs_load_sb(struct super_block *sb, befs_super_block *disk_sb);
+int befs_check_sb(struct super_block *sb);