KVM: Don't pre-reserve xarray entries when storing empty/NULL attributesgrafted

Skip the xarray reservation loop when clearing all memory attributes, as
storing NULL only erases the entry and never needs to allocate, so no
reservation (and no cleanup of a failed one) is required in that case.

Suggested-by: Sean Christopherson <seanjc@google.com>
Cc: David Ballesteros <davimaba.v@proton.me>
Signed-off-by: Zeng Chi <zengchi@kylinos.cn>
Link: https://patch.msgid.link/20260921102442.1232375-1-zeng_chi911@163.com
[sean: split to separate patch]
Signed-off-by: Sean Christopherson <seanjc@google.com>

18 files changed, 3870 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..5fcfc4024
--- /dev/null
+++ b/fs/befs/Kconfig
@@ -0,0 +1,28 @@
+# SPDX-License-Identifier: GPL-2.0-only
+config BEFS_FS
+	tristate "BeOS file system (BeFS) support (read only)"
+	depends on BLOCK
+	select BUFFER_HEAD
+	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..6c9c3cbc5
--- /dev/null
+++ b/fs/befs/Makefile
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-2.0-only
+#
+# 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/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..aa24f1dac
--- /dev/null
+++ b/fs/befs/btree.c
@@ -0,0 +1,783 @@
+/*
+ * 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_obj(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_obj(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;
+	}
+
+	strscpy(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..02fa66fb8
--- /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 <linux/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..ee0cbae52
--- /dev/null
+++ b/fs/befs/linuxvfs.c
@@ -0,0 +1,1030 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * 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/fs_context.h>
+#include <linux/fs_parser.h>
+#include <linux/errno.h>
+#include <linux/filelock.h>
+#include <linux/stat.h>
+#include <linux/nls.h>
+#include <linux/buffer_head.h>
+#include <linux/vfs.h>
+#include <linux/namei.h>
+#include <linux/sched.h>
+#include <linux/cred.h>
+#include <linux/exportfs.h>
+#include <linux/seq_file.h>
+#include <linux/blkdev.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_read_folio(struct file *file, struct folio *folio);
+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_free_inode(struct inode *inode);
+static void befs_destroy_inodecache(void);
+static int befs_symlink_read_folio(struct file *, struct folio *);
+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_statfs(struct dentry *, struct kstatfs *);
+static int befs_show_options(struct seq_file *, struct dentry *);
+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 void befs_free_fc(struct fs_context *fc);
+
+static const struct super_operations befs_sops = {
+	.alloc_inode	= befs_alloc_inode,	/* allocate a new inode */
+	.free_inode	= befs_free_inode, /* deallocate an inode */
+	.put_super	= befs_put_super,	/* uninit super */
+	.statfs		= befs_statfs,	/* statfs */
+	.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,
+	.setlease	= generic_setlease,
+};
+
+static const struct inode_operations befs_dir_inode_operations = {
+	.lookup		= befs_lookup,
+};
+
+static const struct address_space_operations befs_aops = {
+	.read_folio	= befs_read_folio,
+	.bmap		= befs_bmap,
+};
+
+static const struct address_space_operations befs_symlink_aops = {
+	.read_folio	= befs_symlink_read_folio,
+};
+
+static const struct export_operations befs_export_operations = {
+	.encode_fh	= generic_encode_ino32_fh,
+	.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 folio 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_read_folio(struct file *file, struct folio *folio)
+{
+	return block_read_full_folio(folio, 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 %llu, block %ld",
+		   inode->i_ino, (long)block);
+	if (create) {
+		befs_error(sb, "befs_get_block() was asked to write to "
+			   "block %ld in inode %llu", (long)block,
+			   inode->i_ino);
+		return -EPERM;
+	}
+
+	res = befs_fblock2brun(sb, ds, block, &run);
+	if (res != BEFS_OK) {
+		befs_error(sb,
+			   "<--- %s for inode %llu, block %ld ERROR",
+			   __func__, 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 %llu, block %ld, disk address %lu",
+		  __func__, 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 %llu", __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 %llu, 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 %llu)",
+				   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 = alloc_inode_sb(sb, befs_inode_cachep, GFP_KERNEL);
+	if (!bi)
+		return NULL;
+	return &bi->vfs_inode;
+}
+
+static void befs_free_inode(struct inode *inode)
+{
+	kmem_cache_free(befs_inode_cachep, BEFS_I(inode));
+}
+
+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_state_read_once(inode) & 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 = %llu", 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: %llu", 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_set_mtime(inode,
+			fs64_to_cpu(sb, raw_inode->last_modified_time) >> 16,
+			0);/* lower 16 bits are not a time */
+	inode_set_ctime_to_ts(inode, inode_get_mtime(inode));
+	inode_set_atime_to_ts(inode, inode_get_mtime(inode));
+
+	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;
+		strscpy(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 %llu 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_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_read_folio(struct file *unused, struct folio *folio)
+{
+	struct inode *inode = folio->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 = folio_address(folio);
+	int err = -EIO;
+
+	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';
+	err = 0;
+fail:
+	folio_end_read(folio, err == 0);
+	return err;
+}
+
+/*
+ * 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);
+	return d_obtain_alias(parent);
+}
+
+enum {
+	Opt_uid, Opt_gid, Opt_charset, Opt_debug,
+};
+
+static const struct fs_parameter_spec befs_param_spec[] = {
+	fsparam_uid	("uid",		Opt_uid),
+	fsparam_gid	("gid",		Opt_gid),
+	fsparam_string	("iocharset",	Opt_charset),
+	fsparam_flag	("debug",	Opt_debug),
+	{}
+};
+
+static int
+befs_parse_param(struct fs_context *fc, struct fs_parameter *param)
+{
+	struct befs_mount_options *opts = fc->fs_private;
+	int token;
+	struct fs_parse_result result;
+
+	/* befs ignores all options on remount */
+	if (fc->purpose == FS_CONTEXT_FOR_RECONFIGURE)
+		return 0;
+
+	token = fs_parse(fc, befs_param_spec, param, &result);
+	if (token < 0)
+		return token;
+
+	switch (token) {
+	case Opt_uid:
+		opts->uid = result.uid;
+		opts->use_uid = 1;
+		break;
+	case Opt_gid:
+		opts->gid = result.gid;
+		opts->use_gid = 1;
+		break;
+	case Opt_charset:
+		kfree(opts->iocharset);
+		opts->iocharset = param->string;
+		param->string = NULL;
+		break;
+	case Opt_debug:
+		opts->debug = 1;
+		break;
+	default:
+		return -EINVAL;
+	}
+	return 0;
+}
+
+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;
+}
+
+/*
+ * Copy the parsed options into the sbi mount_options member
+ */
+static void
+befs_set_options(struct befs_sb_info *sbi, struct befs_mount_options *opts)
+{
+	sbi->mount_opts.uid = opts->uid;
+	sbi->mount_opts.gid = opts->gid;
+	sbi->mount_opts.use_uid = opts->use_uid;
+	sbi->mount_opts.use_gid = opts->use_gid;
+	sbi->mount_opts.debug = opts->debug;
+	sbi->mount_opts.iocharset = opts->iocharset;
+	opts->iocharset = 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, struct fs_context *fc)
+{
+	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;
+	struct befs_mount_options *parsed_opts = fc->fs_private;
+	int silent = fc->sb_flags & SB_SILENT;
+
+	sb->s_fs_info = kzalloc_obj(*befs_sb);
+	if (sb->s_fs_info == NULL)
+		goto unacquire_none;
+
+	befs_sb = BEFS_SB(sb);
+
+	befs_set_options(befs_sb, parsed_opts);
+
+	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 */
+	if (!sb_set_blocksize(sb, (ulong) befs_sb->block_size))
+		goto unacquire_priv_sbp;
+	sb->s_op = &befs_sops;
+	sb->s_export_op = &befs_export_operations;
+	sb->s_time_min = 0;
+	sb->s_time_max = 0xffffffffffffll;
+	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_reconfigure(struct fs_context *fc)
+{
+	sync_filesystem(fc->root->d_sb);
+	if (!(fc->sb_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 = u64_to_fsid(id);
+	buf->f_namelen = BEFS_NAME_LEN;
+
+	befs_debug(sb, "<--- %s", __func__);
+
+	return 0;
+}
+
+static int befs_get_tree(struct fs_context *fc)
+{
+	return get_tree_bdev(fc, befs_fill_super);
+}
+
+static const struct fs_context_operations befs_context_ops = {
+	.parse_param	= befs_parse_param,
+	.get_tree	= befs_get_tree,
+	.reconfigure	= befs_reconfigure,
+	.free		= befs_free_fc,
+};
+
+static int befs_init_fs_context(struct fs_context *fc)
+{
+	struct befs_mount_options *opts;
+
+	opts = kzalloc_obj(*opts);
+	if (!opts)
+		return -ENOMEM;
+
+	/* Initialize options */
+	opts->uid = GLOBAL_ROOT_UID;
+	opts->gid = GLOBAL_ROOT_GID;
+
+	fc->fs_private = opts;
+	fc->ops = &befs_context_ops;
+
+	return 0;
+}
+
+static void befs_free_fc(struct fs_context *fc)
+{
+	struct befs_mount_options *opts = fc->fs_private;
+
+	kfree(opts->iocharset);
+	kfree(fc->fs_private);
+}
+
+static struct file_system_type befs_fs_type = {
+	.owner		= THIS_MODULE,
+	.name		= "befs",
+	.kill_sb	= kill_block_super,
+	.fs_flags	= FS_REQUIRES_DEV,
+	.init_fs_context = befs_init_fs_context,
+	.parameters	= befs_param_spec,
+};
+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);